华中科技大学：《C语言程序设计》数据结构算法C程序

元素所占空间和表长合并为C语言的一个结构类型 #define maxleng 10 typedef struct Elem Type elem maxlengI:∥下标.0,1,, maxing-1 int length ∥表长 其中: typedef-别名定义, Sqlist-结构类型名 La--结构类型变量名 La length-表长 La elem[o]----al La elem La lengt 算法举例: #include"stdio. h" #define OVERFLOW -2 #define OK #define error typedef int ElemType; 假定数据元素为int #define maxlen 100 线性表最大容量 typedef struct Elem Type elem(maxlen]:/连续存储单元* int length: /线性表长度 Sqlist;:/" Sqlist为结构类型,用其说明的变量在程序中作为线性表* /***亲率幸本***幸本**亲*率本幸本*****亲率本 ★功能:线性表插入操作,将某数据元素插入到线性表 的第i个数据元素之前 输入:线性表指针L、位置i、待插入的数据元素e 输出:成功时返回OK 本本本*幸举*幸**幸本本本******本本幸*客*本*****/ int insert sq(sqlist*L, int i, Elem Type e if(i<1‖p>L-> ength+1) return error,/*i的合法取值为1至n+1 if(L-> length>= maxlen)/溢出* { printi(“超过线性表最大容量”) return ERROR; for(=L-> length-1j>=i-1j-)陣*向后移动元素,空出第i个元素的分量elem[i-1]/ L->elem[j+1=L->elemnT L->elem[i-1=e 新元素插入*

元素所占空间和表长合并为 C 语言的一个结构类型： #define maxleng 100 typedef struct { ElemType elem[maxleng]；//下标:0,1,...,maxleng-1 int length； //表长 } SqList； SqList La； 其中：typedef---别名定义，SqList----结构类型名 La----结构类型变量名 La.length---表长 La.elem[0]----a1 La.elem[La.length-1]---an 算法举例： #include "stdio.h" #define OVERFLOW -2 #define OK 1 #define ERROR 0 typedef int ElemType; /*假定数据元素为 int*/ #define maxlen 100 /*线性表最大容量*/ typedef struct { ElemType elem[maxlen]；/*连续存储单元*/ int length； /*线性表长度*/ } SqList； /*SqList 为结构类型，用其说明的变量在程序中作为线性表*/ /********************************************************** ** 功能：线性表插入操作，将某数据元素插入到线性表 ** ** 的第 i 个数据元素之前 ** ** 输入：线性表指针 L、位置 i、待插入的数据元素 e ** ** 输出： 成功时返回 OK ** **********************************************************/ int insert_sq(SqList *L,int i, ElemType e) { int j; if (i<1 || i>L->length+1) return ERROR; /*i 的合法取值为 1 至 n+1*/ if (L->length>=maxlen) /*溢出*/ {printf(“超过线性表最大容量”); return ERROR; } for(j=L->length-1;j>=i-1;j--) /*向后移动元素，空出第 i 个元素的分量 elem[i-1]*/ L->elem[j+1]=L->elem[j]; L->elem[i-1]=e; /*新元素插入*/

L->length++ /*线性表长度加1* 功能:线性表删除操作,删除线性表的第i个数据元素 输入:线性表指针L、位置i 输出:成功时返回OK 客*幸率**幸率幸*客春幸***幸*幸**幸*幸**/ int delete sq(sqlist "L, int i) if(i<1 Il>L->length) return ERROR; for(j=ij<L> length j++)/向前移动元素* L->elem[j-1=L->elem jil L->length- /*线性表长度减1*/ ★功能:显示线性表的所有数据元素 输入:线性表L 输出:无 率本本*率举本***亲幸本本客本本本**率幸本幸**春率本****幸*/ void display(sqlist L) for(i=0; K<L length,; i++) intf("na[%d]=%od", i+l, L elem[) maino Sqlist La La length=0; /*初始化线性表La,表长度设置为0*/ insert so(&Lan1,1);/*数据元素1插入到线性表La的第1个数据元素之前* Insert_sq(&La1,2);,/*数据元素2插入到线性表La的第1个数据元素之前* Insert_sq(&La1,3),/数据元素3插入到线性表La的第1个数据元素之前* Insert sq&La4,5);/*数据元素5插入到线性表La的第4个数据元素之前* delete sq(&La,1);/删除线性表La的第1个数据元素* display (La) /*显示线性表La的数据元素*

L->length++; /*线性表长度加 1*/ return OK; } /********************************************************** ** 功能：线性表删除操作，删除线性表的第 i 个数据元素 ** ** 输入：线性表指针 L、位置 i ** ** 输出： 成功时返回 OK ** **********************************************************/ int delete_sq(SqList *L,int i) { int j; if (i<1 || i>L->length) return ERROR; for(j=i;j<L->length;j++) /*向前移动元素*/ L->elem[j-1]=L->elem[j]; L->length--; /*线性表长度减 1*/ return OK; } /********************************************************** ** 功能：显示线性表的所有数据元素 ** ** 输入：线性表 L ** ** 输出： 无 ** **********************************************************/ void display(SqList L) { int i; for (i=0;i<L.length;i++) printf("\na[%d]=%d",i+1,L.elem[i]); } main() { SqList La; clrscr(); La.length=0; /*初始化线性表 La, 表长度设置为 0*/ insert_sq(&La,1, 1); /*数据元素１插入到线性表 La 的第１个数据元素之前*/ insert_sq(&La,1, 2); /*数据元素 2 插入到线性表 La 的第１个数据元素之前*/ insert_sq(&La,1, 3); /*数据元素 3 插入到线性表 La 的第１个数据元素之前*/ insert_sq(&La,4 , 5); /*数据元素 5 插入到线性表 La 的第 4 个数据元素之前*/ delete_sq(&La,1); /*删除线性表 La 的第１个数据元素*/ display(La) /*显示线性表 La 的数据元素*/;

2单链表 算法举例(带表头结点的单链表 typedef int Elem Type typedef struct LNod i Elem Type data; struct lnode /*可理解为定义两个类型 LNode 结构类型; Linklist---结点指针类型,指向结点 由于头指针是结点指针,所以该类型变量可定义为链表 LNode*p等价于 Linklist p*/ ***客水客客宗水客客水水水水**亦水客容水客水市客水称水*涂**水*客水 索六功能:初始化单链表,产生头结点 六输入:无 六输出:成功时返回头结点指针 涂本涂*凇称水水客水客水水容水 LinkList ListlnitO L Node *s. LinkList) malloc( sizeof( L Node),/*产生头结点* s->data=0: s->next=NULL return S, /*返回头结点指针* /容****幸亲**春本*****春本李春本**幸春本**春春** 功能:线性表插入操作,将某数据元素插入到单链表* 的第i个数据元素之前 输入:单链表的头指针L、位置i、待插入的数据元素e☆ 六输出:成功时返回OK 本客家本**亲*本*举***本李*本***幸**家率*家幸幸本*本率*亲**本*家*/ int ListInsert(LinkList L, int 1, Elem Type e) LNode"p, s, J p=(LNode *)L; /*p指向链表头结点* while(p &&j<i-1) ip=p->next; ++3; 3 /*执行i-1次定位第i-1个结点*

} 2 单链表 算法举例（带表头结点的单链表）： typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; /*可理解为定义两个类型: LNode ----- 结构类型; LinkList ----- 结点指针类型，指向结点, 由于头指针是结点指针，所以该类型变量可定义为链表 LNode *p 等价于 LinkList p */ /**************************************************** ** 功能：初始化单链表，产生头结点 ** ** 输入：无 ** ** 输出： 成功时返回头结点指针 ** ****************************************************/ LinkList ListInit() { LNode *s; s=(LinkList) malloc(sizeof(LNode)); /*产生头结点*/ s->data=0;s->next=NULL; return s; /*返回头结点指针*/ } /********************************************************** ** 功能：线性表插入操作，将某数据元素插入到单链表 ** ** 的第 i 个数据元素之前 ** ** 输入：单链表的头指针 L、位置 i、待插入的数据元素 e ** ** 输出： 成功时返回 OK ** **********************************************************/ int ListInsert(LinkList L,int i, ElemType e) { LNode *p,*s; int j; p=(LNode *) L; /*p 指向链表头结点*/ j=0; while (p && j<i-1) {p=p->next;++j;} /* 执行 i-1 次定位第 i-1 个结点 */

f(pj>i-1) return ERROR,/*p为NULL时表示没有第i-1个结点 j-1表示i<=0时插入序号错* S->next=p-next p->next=s, /*s所指新结点插入p所指第i-1个结点之后 /***幸家**幸春**率***幸*率春*率本幸幸* 功能:线性表删除操作,删除单链表的第i个结点 输入:单链表的头指针L、位置i 六输出:成功时返回OK int List Delete( LinkList L, int 1) LNode "p, "q Int J; p=( LNode*)L;,/*p指向链表头结点* while(p->next &&j<i-1) {p=p->next++j;}/*执行i-l次,使p定位第i-1个结点* p->next指向结点第i个结点, search for ith node* if(!(p->next)lP>i-1)return ERROR; free(q) return OK /*****本*容*本*****客春**幸*幸本布*****本幸*率*****本** 功能:读取线性表第i个结点的值 ★输入:单链表的头指针L、位置 输出:成功时返回OK、通过指针e返回第i个结点的值 失败返回 ERROR int Get Elem(LinkList L, int i, Elem Type *e) lode*p, 's Int j; p=( LNode*)L->next,/p指向链表第1个结点* while(p &&j< {p=p->next;++j;}/*执行i-1次,使p定位第i个结点* if(plj>i) return ERROR; return OF 客*称水*客水容水*称水容水水容客*客客水客客*客水*客水水*称水*凇称水*水客客水*水客水水水*

if (!p || j>i-1) return ERROR; /*p 为 NULL 时表示没有第 i-1 个结点 j>i-1 表示 i<=0 时插入序号错*/ s=(LinkList) malloc(sizeof(LNode)); s->data=e; s->next=p->next;p->next=s; /*s 所指新结点插入 p 所指第 i-1 个结点之后*/ return OK; } /********************************************************** ** 功能：线性表删除操作，删除单链表的第 i 个结点 ** ** 输入：单链表的头指针 L、位置 i ** ** 输出： 成功时返回 OK ** **********************************************************/ int ListDelete(LinkList L,int i) { LNode *p,*q; int j; p=(LNode *) L; /*p 指向链表头结点*/ j=0; while (p->next && j<i-1) {p=p->next;++j;} /* 执行 i-1 次，使 p 定位第 i-1 个结点 */ p->next 指向结点第 i 个结点, search for ith node*/ if (!(p->next)||j>i-1) return ERROR; q=p->next;p->next=q->next; free(q); return OK; } /********************************************************** ** 功能：读取线性表第 i 个结点的值 ** ** 输入：单链表的头指针 L、位置 i ** ** 输出： 成功时返回 OK、通过指针 e 返回第 i 个结点的值 ** ** 失败返回ＥＲＲＯＲ ** **********************************************************/ int GetElem(LinkList L,int i, ElemType *e) { LNode *p,*s; int j; p=(LNode *) L->next; /*p 指向链表第 1 个结点*/ j=1; while (p && j<i) {p=p->next;++j;} /* 执行 i-1 次，使 p 定位第 i 个结点 */ if (!p||j>i) return ERROR; *e=p->data; return OK; } /**********************************************************

★功能:显示单链表表示的线性表的所有数据元素 输入:线性表L ★输出:无 void display (LinkList L) while(p) printf("\n%d",p->data) p=p->next maino LinkList La, Lb, /only define head pointer, no head node*/ int a La=distinto Lb=listlnito ListInsert(La, 1, 7) ListInsert(La, 2, 9) ListInsert(La, 3, 12) ListDelete(La, 1) Get Elem( La, 3, &a) printf("a=%od", a) display (La);

** 功能：显示单链表表示的线性表的所有数据元素 ** ** 输入：线性表 L ** ** 输出： 无 ** **********************************************************/ void display(LinkList L) { LNode *p; p=L->next; while (p) { printf("\n%d",p->data); p=p->next; } } main() { LinkList La,Lb; /*only define head pointer,no head node*/ int a; clrscr(); La=ListInit(); Lb=ListInit(); ListInsert(La,1, 7); ListInsert(La,2, 9); ListInsert(La,3, 6); ListInsert(La,3, 12); ListDelete(La,1); GetElem(La,3,&a); printf("a=%d",a); display(La); }