清华严蔚敏《数据结构》的全部代码实现C语言46611

《清华严蔚敏《数据结构》的全部代码实现C语言46611》由会员分享，可在线阅读，更多相关《清华严蔚敏《数据结构》的全部代码实现C语言46611（127页珍藏版）》请在金锄头文库上搜索。

1、 /* c1.h (程序名) */ #include #include #include /* malloc()等 */ #include /* INT_MAX 等 */ #include /* EOF(=Z 或 F6),NULL */ #include /* atoi() */ #include /* eof() */ #include /* floor(),ceil(),abs() */ #include /* exit() */ /* 函数结果状态代码 */ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #defi

2、ne INFEASIBLE -1 /* #define OVERFLOW -2 因为在 math.h 中已定义 OVERFLOW 的值为 3,故去掉此行 */ typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码，如OK 等 */ typedef int Boolean; /* Boolean 是布尔类型,其值是 TRUE 或 FALSE */ /* algo2-1.c 实现算法 2.1 的程序 */ #includec1.h typedef int ElemType; #includec2-1.h /*c2-1.h 线性表的动态分配顺序存储结构 *

3、/ #define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量 */ #define LISTINCREMENT 2 /* 线性表存储空间的分配增量 */ typedef struct ElemType *elem; /* 存储空间基址 */ int length; /* 当前长度 */ int listsize; /* 当前分配的存储容量(以 sizeof(ElemType)为单位) */ SqList; #includebo2-1.c /* bo2-1.c 顺序表示的线性表(存储结构由 c2-1.h 定义)的基本操作(12 个) */ Status InitLis

4、t(SqList *L) /* 算法 2.3 */ /* 操作结果：构造一个空的顺序线性表 */ (*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!(*L).elem) exit(OVERFLOW); /* 存储分配失败 */ (*L).length=0; /* 空表长度为 0 */ (*L).listsize=LIST_INIT_SIZE; /* 初始存储容量 */ return OK; Status DestroyList(SqList *L) /* 初始条件：顺序线性表 L 已存在。操作结果：销毁顺序线性表

5、L */ free(*L).elem); (*L).elem=NULL; (*L).length=0; (*L).listsize=0; return OK; Status ClearList(SqList *L) /* 初始条件：顺序线性表 L 已存在。操作结果：将 L 重置为空表 */ (*L).length=0; return OK; Status ListEmpty(SqList L) /* 初始条件：顺序线性表 L 已存在。操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE */ if(L.length=0) return TRUE; else return FALSE

6、; int ListLength(SqList L) /* 初始条件：顺序线性表 L 已存在。操作结果：返回 L 中数据元素个数 */ return L.length; Status GetElem(SqList L,int i,ElemType *e) /* 初始条件：顺序线性表 L 已存在，1iListLength(L) */ /* 操作结果：用 e 返回 L 中第 i 个数据元素的值 */ if(iL.length) exit(ERROR); *e=*(L.elem+i-1); return OK; int LocateElem(SqList L,ElemType e,Status(*c

7、ompare)(ElemType,ElemType) /* 初始条件：顺序线性表 L 已存在，compare()是数据元素判定函数(满足为1,否则为 0) */ /* 操作结果： 返回 L 中第 1 个与 e 满足关系 compare()的数据元素的位序。 */ /* 若这样的数据元素不存在，则返回值为 0。算法 2.6 */ ElemType *p; int i=1; /* i 的初值为第 1 个元素的位序 */ p=L.elem; /* p 的初值为第 1 个元素的存储位置 */ while(i=L.length&!compare(*p+,e) +i; if(i=L.length) ret

8、urn i; else return 0; Status PriorElem(SqList L,ElemType cur_e,ElemType *pre_e) /* 初始条件：顺序线性表 L 已存在 */ /* 操作结果：若 cur_e 是 L 的数据元素，且不是第一个，则用 pre_e 返回它的前驱， */ /* 否则操作失败，pre_e 无定义 */ int i=2; ElemType *p=L.elem+1; while(iL.length) return INFEASIBLE; else *pre_e=*-p; return OK; Status NextElem(SqList L,E

9、lemType cur_e,ElemType *next_e) /* 初始条件：顺序线性表 L 已存在 */ /* 操作结果：若 cur_e 是 L 的数据元素，且不是最后一个，则用 next_e 返回它的后继， */ /* 否则操作失败，next_e 无定义 */ int i=1; ElemType *p=L.elem; while(iL.length&*p!=cur_e) i+; p+; if(i=L.length) return INFEASIBLE; else *next_e=*+p; return OK; Status ListInsert(SqList *L,int i,ElemT

10、ype e) /* 算法 2.4 */ /* 初始条件：顺序线性表 L 已存在，1iListLength(L)+1 */ /* 操作结果：在 L 中第 i 个位置之前插入新的数据元素 e，L 的长度加 1 */ ElemType *newbase,*q,*p; if(i(*L).length+1) /* i 值不合法 */ return ERROR; if(*L).length=(*L).listsize) /* 当前存储空间已满,增加分配 */ newbase=(ElemType *)realloc(*L).elem,(*L).listsize+LISTINCREMENT)*sizeof(E

11、lemType); if(!newbase) exit(OVERFLOW); /* 存储分配失败 */ (*L).elem=newbase; /* 新基址 */ (*L).listsize+=LISTINCREMENT; /* 增加存储容量 */ q=(*L).elem+i-1; /* q 为插入位置 */ for(p=(*L).elem+(*L).length-1;p=q;-p) /* 插入位置及之后的元素右移 */ *(p+1)=*p; *q=e; /* 插入 e */ +(*L).length; /* 表长增 1 */ return OK; Status ListDelete(SqLis

12、t *L,int i,ElemType *e) /* 算法 2.5 */ /* 初始条件：顺序线性表 L 已存在，1iListLength(L) */ /* 操作结果：删除 L 的第 i 个数据元素，并用 e 返回其值，L 的长度减 1 */ ElemType *p,*q; if(i(*L).length) /* i 值不合法 */ return ERROR; p=(*L).elem+i-1; /* p 为被删除元素的位置 */ *e=*p; /* 被删除元素的值赋给 e */ q=(*L).elem+(*L).length-1; /* 表尾元素的位置 */ for(+p;p=q;+p) /*

13、 被删除元素之后的元素左移 */ *(p-1)=*p; (*L).length-; /* 表长减 1 */ return OK; Status ListTraverse(SqList L,void(*vi)(ElemType*) /* 初始条件：顺序线性表 L 已存在 */ /* 操作结果：依次对 L 的每个数据元素调用函数 vi()。一旦 vi()失败，则操作失败 */ /* vi()的形参加&，表明可通过调用 vi()改变元素的值 */ ElemType *p; int i; p=L.elem; for(i=1;i=L.length;i+) vi(p+); printf(n); retur

14、n OK; Status equal(ElemType c1,ElemType c2) /* 判断是否相等的函数，Union()用到 */ if(c1=c2) return TRUE; else return FALSE; void Union(SqList *La,SqList Lb) /* 算法 2.1 */ /* 将所有在线性表 Lb 中但不在 La 中的数据元素插入到 La 中 */ ElemType e; int La_len,Lb_len; int i; La_len=ListLength(*La); /* 求线性表的长度 */ Lb_len=ListLength(Lb); for

15、(i=1;i=Lb_len;i+) GetElem(Lb,i,&e); /* 取 Lb 中第 i 个数据元素赋给 e */ if(!LocateElem(*La,e,equal) /* La 中不存在和 e 相同的元素,则插入之 */ ListInsert(La,+La_len,e); void print(ElemType *c) printf(%d ,*c); void main() SqList La,Lb; Status i; int j; i=InitList(&La); if(i=1) /* 创建空表 La 成功 */ for(j=1;j=5;j+) /* 在表 La 中插入 5

16、个元素 */ i=ListInsert(&La,j,j); printf(La= ); /* 输出表 La 的内容 */ ListTraverse(La,print); InitList(&Lb); /* 也可不判断是否创建成功 */ for(j=1;j=5;j+) /* 在表 Lb 中插入 5 个元素 */ i=ListInsert(&Lb,j,2*j); printf(Lb= ); /* 输出表 Lb 的内容 */ ListTraverse(Lb,print); Union(&La,Lb); printf(new La= ); /* 输出新表 La 的内容 */ ListTraverse(

17、La,print); /* algo2-2.c 实现算法 2.2 的程序 */ #includec1.h typedef int ElemType; #includec2-1.h #includebo2-1.c void MergeList(SqList La,SqList Lb,SqList *Lc) /* 算法 2.2 */ /* 已知线性表 La 和 Lb 中的数据元素按值非递减排列。 */ /* 归并 La 和 Lb 得到新的线性表 Lc,Lc 的数据元素也按值非递减排列 */ int i=1,j=1,k=0; int La_len,Lb_len; ElemType ai,bj; In

18、itList(Lc); /* 创建空表 Lc */ La_len=ListLength(La); Lb_len=ListLength(Lb); while(i=La_len&j=Lb_len) /* 表 La 和表 Lb 均非空 */ GetElem(La,i,&ai); GetElem(Lb,j,&bj); if(ai=bj) ListInsert(Lc,+k,ai); +i; else ListInsert(Lc,+k,bj); +j; while(i=La_len) /* 表 La 非空且表 Lb 空 */ GetElem(La,i+,&ai); ListInsert(Lc,+k,ai)

19、; while(j=Lb_len) /* 表 Lb 非空且表 La 空 */ GetElem(Lb,j+,&bj); ListInsert(Lc,+k,bj); void print(ElemType *c) printf(%d ,*c); void main() SqList La,Lb,Lc; int j,a4=3,5,8,11,b7=2,6,8,9,11,15,20; InitList(&La); /* 创建空表 La */ for(j=1;j=4;j+) /* 在表 La 中插入 4 个元素 */ ListInsert(&La,j,aj-1); printf(La= ); /* 输出表

20、 La 的内容 */ ListTraverse(La,print); InitList(&Lb); /* 创建空表 Lb */ for(j=1;j=7;j+) /* 在表 Lb 中插入 7 个元素 */ ListInsert(&Lb,j,bj-1); printf(Lb= ); /* 输出表 Lb 的内容 */ ListTraverse(Lb,print); MergeList(La,Lb,&Lc); printf(Lc= ); /* 输出表 Lc 的内容 */ ListTraverse(Lc,print); /* algo2-3.c 实现算法 2.7 的程序 */ #includec1.h

21、typedef int ElemType; #includec2-1.h #includebo2-1.c void MergeList(SqList La,SqList Lb,SqList *Lc) /* 算法 2.7 */ /* 已知顺序线性表 La 和 Lb 的元素按值非递减排列。 */ /* 归并 La 和 Lb 得到新的顺序线性表 Lc,Lc 的元素也按值非递减排列 */ ElemType *pa,*pa_last,*pb,*pb_last,*pc; pa=La.elem; pb=Lb.elem; (*Lc).listsize=(*Lc).length=La.length+Lb.len

22、gth;/*不用 InitList()创建空表 Lc */ pc=(*Lc).elem=(ElemType *)malloc(*Lc).listsize*sizeof(ElemType); if(!(*Lc).elem) /* 存储分配失败 */ exit(OVERFLOW); pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; while(pa=pa_last&pb=pb_last) /* 表 La 和表 Lb 均非空 */ /* 归并 */ if(*pa=*pb) *pc+=*pa+; else *pc+=*pb+; whil

23、e(pa=pa_last) /* 表 La 非空且表 Lb 空 */ *pc+=*pa+; /* 插入 La 的剩余元素 */ while(pb=pb_last) /* 表 Lb 非空且表 La 空 */ *pc+=*pb+; /* 插入 Lb 的剩余元素 */ void print(ElemType *c) printf(%d ,*c); void main() SqList La,Lb,Lc; int j; InitList(&La); /* 创建空表 La */ for(j=1;j=5;j+) /* 在表 La 中插入 5 个元素 */ ListInsert(&La,j,j); prin

24、tf(La= ); /* 输出表 La 的内容 */ ListTraverse(La,print); InitList(&Lb); /* 创建空表 Lb */ for(j=1;j=5;j+) /* 在表 Lb 中插入 5 个元素 */ ListInsert(&Lb,j,2*j); printf(Lb= ); /* 输出表 Lb 的内容 */ ListTraverse(Lb,print); MergeList(La,Lb,&Lc); printf(Lc= ); /* 输出表 Lc 的内容 */ ListTraverse(Lc,print); /* algo2-4.c 修改算法 2.7 的第一个循

25、环语句中的条件语句为开关语句， 且当 */ /* *pa=*pb 时，只将两者中之一插入 Lc。此操作的结果和算法 2.1 相同 */ #includec1.h typedef int ElemType; #includec2-1.h #includebo2-1.c int comp(ElemType c1,ElemType c2) int i; if(c1c2) i=1; else if(c1=c2) i=0; else i=-1; return i; void MergeList(SqList La,SqList Lb,SqList *Lc) /* 另一种合并线性表的方法（根据算法 2.7

26、 下的要求修改算法 2.7） */ ElemType *pa,*pa_last,*pb,*pb_last,*pc; pa=La.elem; pb=Lb.elem; (*Lc).listsize=La.length+Lb.length; /* 此句与算法 2.7 不同 */ pc=(*Lc).elem=(ElemType *)malloc(*Lc).listsize*sizeof(ElemType); if(!(*Lc).elem) exit(OVERFLOW); pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; while(pa

27、=pa_last&pb=pb_last) /* 表 La 和表 Lb 均非空 */ switch(comp(*pa,*pb) /* 此句与算法 2.7 不同 */ case 0: pb+; case 1: *pc+=*pa+; break; case -1: *pc+=*pb+; while(pa=pa_last) /* 表 La 非空且表 Lb 空 */ *pc+=*pa+; while(pb=pb_last) /* 表 Lb 非空且表 La 空 */ *pc+=*pb+; (*Lc).length=pc-(*Lc).elem; /* 加此句 */ void print(ElemType *

28、c) printf(%d ,*c); void main() SqList La,Lb,Lc; int j; InitList(&La); /* 创建空表 La */ for(j=1;j=5;j+) /* 在表 La 中插入 5 个元素 */ ListInsert(&La,j,j); printf(La= ); /* 输出表 La 的内容 */ ListTraverse(La,print); InitList(&Lb); /* 创建空表 Lb */ for(j=1;jnext=NULL; /* 指针域为空 */ return OK; Status DestroyList(LinkList *L

29、) /* 初始条件：线性表 L 已存在。操作结果：销毁线性表 L */ LinkList q; while(*L) q=(*L)-next; free(*L); *L=q; return OK; Status ClearList(LinkList L) /* 不改变 L */ /* 初始条件：线性表 L 已存在。操作结果：将 L 重置为空表 */ LinkList p,q; p=L-next; /* p 指向第一个结点 */ while(p) /* 没到表尾 */ q=p-next; free(p); p=q; L-next=NULL; /* 头结点指针域为空 */ return OK; St

30、atus ListEmpty(LinkList L) /* 初始条件：线性表 L 已存在。操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE */ if(L-next) /* 非空 */ return FALSE; else return TRUE; int ListLength(LinkList L) /* 初始条件：线性表 L 已存在。操作结果：返回 L 中数据元素个数 */ int i=0; LinkList p=L-next; /* p 指向第一个结点 */ while(p) /* 没到表尾 */ i+; p=p-next; return i; Status GetEle

31、m(LinkList L,int i,ElemType *e) /* 算法 2.8 */ /* L 为带头结点的单链表的头指针。当第 i 个元素存在时,其值赋给 e 并返回OK,否则返回 ERROR */ int j=1; /* j 为计数器 */ LinkList p=L-next; /* p 指向第一个结点 */ while(p&jnext; j+; if(!p|ji) /* 第 i 个元素不存在 */ return ERROR; *e=p-data; /* 取第 i 个元素 */ return OK; int LocateElem(LinkList L,ElemType e,Status

32、(*compare)(ElemType,ElemType) /* 初始条件: 线性表 L 已存在,compare()是数据元素判定函数(满足为 1,否则为 0) */ /* 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。 */ /* 若这样的数据元素不存在,则返回值为 0 */ int i=0; LinkList p=L-next; while(p) i+; if(compare(p-data,e) /* 找到这样的数据元素 */ return i; p=p-next; return 0; Status PriorElem(LinkList L,ElemType c

33、ur_e,ElemType *pre_e) /* 初始条件: 线性表 L 已存在 */ /* 操作结果: 若 cur_e 是 L 的数据元素,且不是第一个,则用 pre_e 返回它的前驱, */ /* 返回 OK;否则操作失败,pre_e 无定义,返回 INFEASIBLE */ LinkList q,p=L-next; /* p 指向第一个结点 */ while(p-next) /* p 所指结点有后继 */ q=p-next; /* q 为 p 的后继 */ if(q-data=cur_e) *pre_e=p-data; return OK; p=q; /* p 向后移 */ return

34、 INFEASIBLE; Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e) /* 初始条件：线性表 L 已存在 */ /* 操作结果：若 cur_e 是 L 的数据元素，且不是最后一个，则用 next_e 返回它的后继， */ /* 返回 OK;否则操作失败，next_e 无定义，返回 INFEASIBLE */ LinkList p=L-next; /* p 指向第一个结点 */ while(p-next) /* p 所指结点有后继 */ if(p-data=cur_e) *next_e=p-next-data; retu

35、rn OK; p=p-next; return INFEASIBLE; Status ListInsert(LinkList L,int i,ElemType e) /* 算法 2.9。不改变 L */ /* 在带头结点的单链线性表 L 中第 i 个位置之前插入元素 e */ int j=0; LinkList p=L,s; while(p&jnext; j+; if(!p|ji-1) /* i 小于 1 或者大于表长 */ return ERROR; s=(LinkList)malloc(sizeof(struct LNode); /* 生成新结点 */ s-data=e; /* 插入 L

36、中 */ s-next=p-next; p-next=s; return OK; Status ListDelete(LinkList L,int i,ElemType *e) /* 算法 2.10。不改变 L */ /* 在带头结点的单链线性表 L 中，删除第 i 个元素,并由 e 返回其值 */ int j=0; LinkList p=L,q; while(p-next&jnext; j+; if(!p-next|ji-1) /* 删除位置不合理 */ return ERROR; q=p-next; /* 删除并释放结点 */ p-next=q-next; *e=q-data; free(

37、q); return OK; Status ListTraverse(LinkList L,void(*vi)(ElemType) /* vi 的形参类型为 ElemType，与 bo2-1.c 中相应函数的形参类型 ElemType&不同 */ /* 初始条件：线性表 L 已存在 */ /* 操作结果:依次对 L 的每个数据元素调用函数 vi()。 一旦 vi()失败,则操作失败 */ LinkList p=L-next; while(p) vi(p-data); p=p-next; printf(n); return OK; void CreateList(LinkList *L,int

38、n) /* 算法 2.11 */ /* 逆位序(插在表头)输入 n 个元素的值，建立带表头结构的单链线性表 L */ int i; LinkList p; *L=(LinkList)malloc(sizeof(struct LNode); (*L)-next=NULL; /* 先建立一个带头结点的单链表 */ printf(请输入%d 个数据n,n); for(i=n;i0;-i) p=(LinkList)malloc(sizeof(struct LNode); /* 生成新结点 */ scanf(%d,&p-data); /* 输入元素值 */ p-next=(*L)-next; /* 插入

39、到表头 */ (*L)-next=p; void CreateList2(LinkList *L,int n) /* 正位序(插在表尾)输入 n 个元素的值，建立带表头结构的单链线性表 */ int i; LinkList p,q; *L=(LinkList)malloc(sizeof(struct LNode); /* 生成头结点 */ (*L)-next=NULL; q=*L; printf(请输入%d 个数据n,n); for(i=1;idata); q-next=p; q=q-next; p-next=NULL; void MergeList(LinkList La,LinkList

40、*Lb,LinkList *Lc)/* 算法 2.12 */ /* 已知单链线性表 La 和 Lb 的元素按值非递减排列。 */ /* 归并 La 和 Lb 得到新的单链线性表 Lc，Lc 的元素也按值非递减排列 */ LinkList pa=La-next,pb=(*Lb)-next,pc; *Lc=pc=La; /* 用 La 的头结点作为 Lc 的头结点 */ while(pa&pb) if(pa-datadata) pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next; pc-next=pa?pa:pb; /

41、* 插入剩余段 */ free(*Lb); /* 释放 Lb 的头结点 */ Lb=NULL; void visit(ElemType c) /* ListTraverse()调用的函数(类型要一致) */ printf(%d ,c); void main() int n=5; LinkList La,Lb,Lc; printf(按非递减顺序, ); CreateList2(&La,n); /* 正位序输入 n 个元素的值 */ printf(La=); /* 输出链表 La 的内容 */ ListTraverse(La,visit); printf(按非递增顺序, ); CreateList

42、(&Lb,n); /* 逆位序输入 n 个元素的值 */ printf(Lb=); /* 输出链表 Lb 的内容 */ ListTraverse(Lb,visit); MergeList(La,&Lb,&Lc); /* 按非递减顺序归并 La 和 Lb,得到新表 Lc */ printf(Lc=); /* 输出链表 Lc 的内容 */ ListTraverse(Lc,visit); /* algo2-6.c 利用单链表结构处理教科书图 2.1(学生健康登记表) */ #includec1.h #define NAMELEN 8 /* 姓名最大长度 */ #define CLASSLEN 4 /

43、* 班级名最大长度 */ struct stud /* 记录的结构 */ char nameNAMELEN+1; long num; char sex; int age; char ClassCLASSLEN+1; int health; ; typedef struct stud ElemType; /* 链表结点元素类型为结构体 */ #includec2-2.h char sta39=健康 ,一般 ,神经衰弱; /* 健康状况(3 类) */ FILE *fp; Status InitList(LinkList *L) /* 拷自 bo2-2.c */ /* 操作结果：构造一个空的线性表

44、 L */ *L=(LinkList)malloc(sizeof(struct LNode); /* 产生头结点,并使 L 指向此头结点 */ if(!*L) /* 存储分配失败 */ exit(OVERFLOW); (*L)-next=NULL; /* 指针域为空 */ return OK; Status ListTraverse(LinkList L,void(*vi)(ElemType) /* 拷自 bo2-2.c */ /* 初始条件：线性表 L 已存在 */ /* 操作结果:依次对 L 的每个数据元素调用函数 vi()。一旦 vi()失败,则操作失败 */ LinkList p=L-

45、next; while(p) vi(p-data); p=p-next; printf(n); return OK; void InsertAscend(LinkList L,ElemType e) /* 此函数是由 bo2-9.c 中的同名函数改写 */ /* 按学号非降序插入 */ LinkList q=L,p=L-next; while(p&e.nump-data.num) q=p; p=p-next; q-next=(LinkList)malloc(sizeof(struct LNode); /* 插在 q 后 */ q-next-data=e; q-next-next=p; void

46、 Print(struct stud e) /* 显示记录 e 的内容 */ printf(%-8s %6ld,e.name,e.num); if(e.sex=m) printf( 男); else printf( 女); printf(%5d %-4s,e.age,e.Class); printf(%9sn,stae.health); void ReadIn(struct stud *e) /* 由键盘输入结点信息 */ printf(请输入姓名(name); printf(请输入学号: ); scanf(%ld,&e-num); printf(请输入性别(m:男 f:女): ); scan

47、f(%*c%c,&e-sex); printf(请输入年龄: ); scanf(%d,&e-age); printf(请输入班级(Class); printf(请输入健康状况(0:%s 1:%s 2:%s):,sta0,sta1,sta2); scanf(%d,&e-health); void WriteToFile(struct stud e) /* 将结点信息写入 fp 指定的文件 */ fwrite(&e,sizeof(struct stud),1,fp); Status ReadFromFile(struct stud *e) /* 由 fp 指定的文件读取结点信息到 e */ int

48、 i; i=fread(e,sizeof(struct stud),1,fp); if(i=1) /* 读取文件成功 */ return OK; else return ERROR; Status FindFromNum(LinkList L,long num,LinkList *p,LinkList *q) /* 查找表中学号为 num 的结点,如找到,q 指向此结点,p 指向 q 的前驱, */ /* 并返回 TRUE;如无此元素,则返回 FALSE */ *p=L; while(*p) *q=(*p)-next; if(*q&(*q)-data.numnum) /* 因为是按学号非降序排

49、列 */ break; if(*q&(*q)-data.num=num) /* 找到该学号 */ return TRUE; *p=*q; return FALSE; Status FindFromName(LinkList L,char name,LinkList *p,LinkList *q) /* 查找表中姓名为 name 的结点,如找到,q 指向此结点,p 指向 q 的前驱, */ /* 并返回 TRUE;如无此元素,则返回 FALSE */ *p=L; while(*p) *q=(*p)-next; if(*q&!strcmp(*q)-data.name,name) /* 找到该姓名

50、*/ return TRUE; *p=*q; return FALSE; Status DeleteElemNum(LinkList L,long num) /* 删除表中学号为 num 的元素，并返回 TRUE；如无此元素，则返回 FALSE */ LinkList p,q; if(FindFromNum(L,num,&p,&q) /* 找到此结点,且q指向其,p指向其前驱 */ p-next=q-next; free(q); return TRUE; return FALSE; Status DeleteElemName(LinkList L,char name) /* 删除表中姓名为 n

51、ame 的元素，并返回 TRUE；如无此元素，则返回 FALSE */ LinkList p,q; if(FindFromName(L,name,&p,&q) /* 找到此结点,且 q 指向其,p 指向其前驱 */ p-next=q-next; free(q); return TRUE; return FALSE; void Modify(ElemType *e) /* 修改结点内容 */ char s80; Print(*e); /* 显示原内容 */ printf(请输入待修改项的内容，不修改的项按回车键保持原值:n); printf(请输入姓名(name,s); printf(请输入学号

52、: ); gets(s); if(strlen(s) e-num=atol(s); printf(请输入性别(m:男 f:女): ); gets(s); if(strlen(s) e-sex=s0; printf(请输入年龄: ); gets(s); if(strlen(s) e-age=atoi(s); printf(请输入班级(Class,s); printf(请输入健康状况(0:%s 1:%s 2:%s):,sta0,sta1,sta2); gets(s); if(strlen(s) e-health=atoi(s); /* 修改完毕 */ #define N 4 /* student

53、记录的个数 */ void main() struct stud studentN=王小林,790631,m,18,计 91,0, 陈红,790632,f,20,计 91,1, 刘建平,790633,m,21,计 91,0, 张立立,790634,m,17,计 91,2; /* 表的初始记录 */ int i,j,flag=1; long num; char filename13,nameNAMELEN+1; ElemType e; LinkList T,p,q; InitList(&T); /* 初始化链表 */ while(flag) printf(1:将结构体数组 student 中的记

54、录按学号非降序插入链表n); printf(2:将文件中的记录按学号非降序插入链表n); printf(3:键盘输入新记录，并将其按学号非降序插入链表n); printf(4:删除链表中第一个有给定学号的记录n); printf(5:删除链表中第一个有给定姓名的记录n); printf(6:修改链表中第一个有给定学号的记录n); printf(7:修改链表中第一个有给定姓名的记录n); printf(8:查找链表中第一个有给定学号的记录n); printf(9:查找链表中第一个有给定姓名的记录n); printf(10:显示所有记录 11:将链表中的所有记录存入文件 12:结束n); prin

55、tf(请选择操作命令: ); scanf(%d,&i); switch(i) case 1: for(j=0;jdata); if(q-data.num!=num) /* 学号被修改 */ p-next=q-next; /* 把 q 所指的结点从 L 中删除 */ InsertAscend(T,q-data); /* 把元素插入 L */ free(q); /* 删除 q */ break; case 7: printf(请输入待修改记录的姓名: ); scanf(%s%*c,name); /* %*c 吃掉回车符 */ if(!FindFromName(T,name,&p,&q) print

56、f(没有姓名为%s 的记录n,name); else num=q-data.num; /* 学号存入 num */ Modify(&q-data); if(q-data.num!=num) /* 学号被修改 */ p-next=q-next; /* 把 q 所指的结点从 L 中删除 */ InsertAscend(T,q-data); /* 把元素插入 L */ free(q); /* 删除 q */ break; case 8: printf(请输入待查找记录的学号: ); scanf(%ld,&num); if(!FindFromNum(T,num,&p,&q) printf(没有学号为%

57、ld 的记录n,num); else Print(q-data); break; case 9: printf(请输入待查找记录的姓名: ); scanf(%s,name); if(!FindFromName(T,name,&p,&q) printf(没有姓名为%s 的记录n,name); else Print(q-data); break; case 10:printf( 姓名 学号 性别 年龄 班级 健康状况n); ListTraverse(T,Print); break; case 11:printf(请输入文件名: ); scanf(%s,filename); if(fp=fopen(

58、filename,wb)=NULL) printf(打开文件失败!n); else ListTraverse(T,WriteToFile); fclose(fp); break; case 12:flag=0; /* algo2-7.c 教科书中图 2.10 静态链表示例 */ /* 第一个结点的位置在0.cur 中，成员 cur 的值为 0，则到链表尾 */ #includec1.h #define N 6 /* 字符串长度 */ typedef char ElemTypeN; #includec2-3.h /* c2-3.h 线性表的静态单链表存储结构 */ #define MAXSIZE

59、 100 /* 链表的最大长度 */ typedef struct ElemType data; int cur; component,SLinkListMAXSIZE; void main() SLinkList s=,1,ZHAO,2,QIAN,3,SUN,4,LI,5,ZHOU,6,WU,7,ZHENG,8,WANG,0; int i; i=s0.cur; while(i) /* 输出教科书中图 2.10(a)的状态 */ printf(%s ,si.data); /* 输出链表的当前值 */ i=si.cur; /* 找到下一个 */ printf(n); s4.cur=9; /* 按

60、教科书中图 2.10(b)修改 */ s6.cur=8; s9.cur=5; strcpy(s9.data,SHI); i=s0.cur; while(i) /* 输出教科书中图 2.10(b)的状态 */ printf(%s ,si.data); /* 输出链表的当前值 */ i=si.cur; /* 找到下一个 */ printf(n); /* algo2-8.c 实现算法 2.17 的程序 */ #includec1.h #define N 2 typedef char ElemType; #includec2-3.h #includebo2-3.c /* bo2-3.c 实现算法 2.

61、15、2.16 的程序 (数据结构由 c2-3.h 定义) (3 个) */ int Malloc(SLinkList space) /* 算法 2.15 */ /* 若备用链表非空,则返回分配的结点下标(备用链表的第一个结点),否则返回 0 */ int i=space0.cur; if(i) /* 备用链表非空 */ space0.cur=spacei.cur; /* 备用链表的头结点指向原备用链表的第二个结点 */ return i; /* 返回新开辟结点的坐标 */ void Free(SLinkList space,int k) /* 算法 2.16 */ /* 将下标为 k 的空闲

62、结点回收到备用链表(成为备用链表的第一个结点) */ spacek.cur=space0.cur; /* 回收结点的游标指向备用链表的第一个结点 */ space0.cur=k; /* 备用链表的头结点指向新回收的结点 */ void DestroyList() /* 静态数组不能被销毁 */ #includebo2-32.c /* bo2-32.c 一个数组可生成若干静态链表(数据结构由 c2-3.h 定义)的基本操作(12 个) */ void InitSpace(SLinkList L) /* 算法 2.14。另加 */ /* 将一维数组 L 中各分量链成一个备用链表，L0.cur 为头

63、指针。 “0”表示空指针 */ int i; for(i=0;iMAXSIZE-1;i+) Li.cur=i+1; LMAXSIZE-1.cur=0; int InitList(SLinkList L) /* 构造一个空链表，返回值为空表在数组中的位序 */ int i; i=Malloc(L); /* 调用 Malloc()，简化程序 */ Li.cur=0; /* 空链表的表头指针为空(0) */ return i; Status ClearList(SLinkList L,int n) /* 初始条件：L 中表头位序为 n 的静态链表已存在。操作结果：将此表重置为空表 */ int j,

64、k,i=Ln.cur; /* 链表第一个结点的位置 */ Ln.cur=0; /* 链表空 */ k=L0.cur; /* 备用链表第一个结点的位置 */ L0.cur=i; /* 把链表的结点连到备用链表的表头 */ while(i) /* 没到链表尾 */ j=i; i=Li.cur; /* 指向下一个元素 */ Lj.cur=k; /* 备用链表的第一个结点接到链表的尾部 */ return OK; Status ListEmpty(SLinkList L,int n) /* 判断 L 中表头位序为 n 的链表是否空,若是空表返回 TRUE;否则返回 FALSE */ if(Ln.cur

65、=0) /* 空表 */ return TRUE; else return FALSE; int ListLength(SLinkList L,int n) /* 返回 L 中表头位序为 n 的链表的数据元素个数 */ int j=0,i=Ln.cur; /* i 指向第一个元素 */ while(i) /* 没到静态链表尾 */ i=Li.cur; /* 指向下一个元素 */ j+; return j; Status GetElem(SLinkList L,int n, int i,ElemType *e) /* 用 e 返回 L 中表头位序为 n 的链表的第 i 个元素的值 */ int

66、l,k=n; /* k 指向表头序号 */ if(iListLength(L,n) /* i 值不合理 */ return ERROR; for(l=1;l=i;l+) /* 移动 i-1 个元素 */ k=Lk.cur; *e=Lk.data; return OK; int LocateElem(SLinkList L,int n,ElemType e) /* 在 L 中表头位序为 n 的静态单链表中查找第 1 个值为 e 的元素。 */ /* 若找到，则返回它在 L 中的位序，否则返回 0 */ int i=Ln.cur; /* i 指示表中第一个结点 */ while(i&Li.data

67、!=e) /* 在表中顺链查找(e 不能是字符串) */ i=Li.cur; return i; Status PriorElem(SLinkList L,int n,ElemType cur_e,ElemType *pre_e) /* 初始条件：在 L 中表头位序为 n 的静态单链表已存在 */ /* 操作结果：若 cur_e 是此单链表的数据元素，且不是第一个， */ /* 则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义 */ int j,i=Ln.cur; /* i 为链表第一个结点的位置 */ do /* 向后移动结点 */ j=i; i=Li.cur; while(

68、i&cur_e!=Li.data); if(i) /* 找到该元素 */ *pre_e=Lj.data; return OK; return ERROR; Status NextElem(SLinkList L,int n,ElemType cur_e,ElemType *next_e) /* 初始条件：在 L 中表头位序为 n 的静态单链表已存在 */ /* 操作结果：若 cur_e 是此单链表的数据元素，且不是最后一个， */ /* 则用 next_e 返回它的后继，否则操作失败，next_e 无定义 */ int i; i=LocateElem(L,n,cur_e); /* 在链表中查找

69、第一个值为 cur_e 的元素的位置 */ if(i) /* 在静态单链表中存在元素 cur_e */ i=Li.cur; /* cur_e 的后继的位置 */ if(i) /* cur_e 有后继 */ *next_e=Li.data; return OK; /* cur_e 元素有后继 */ return ERROR; /* L 不存在 cur_e 元素,cur_e 元素无后继 */ Status ListInsert(SLinkList L,int n,int i,ElemType e) /* 在 L 中表头位序为 n 的链表的第 i 个元素之前插入新的数据元素 e */ int l,j

70、,k=n; /* k 指向表头 */ if(iListLength(L,n)+1) return ERROR; j=Malloc(L); /* 申请新单元 */ if(j) /* 申请成功 */ Lj.data=e; /* 赋值给新单元 */ for(l=1;li;l+) /* 移动 i-1 个元素 */ k=Lk.cur; Lj.cur=Lk.cur; Lk.cur=j; return OK; return ERROR; Status ListDelete(SLinkList L,int n,int i,ElemType *e) /* 删除在 L 中表头位序为 n 的链表的第 i 个数据元素

71、 e，并返回其值 */ int j,k=n; /* k 指向表头 */ if(iListLength(L,n) return ERROR; for(j=1;ji;j+) /* 移动 i-1 个元素 */ k=Lk.cur; j=Lk.cur; Lk.cur=Lj.cur; *e=Lj.data; Free(L,j); return OK; Status ListTraverse(SLinkList L,int n,void(*vi)(ElemType) /* 依次对 L 中表头位序为 n 的链表的每个数据元素,调用函数 vi()。 一旦 vi()失败,则操作失败 */ int i=Ln.cur

72、; /* 指向第一个元素 */ while(i) /* 没到静态链表尾 */ vi(Li.data); /* 调用 vi() */ i=Li.cur; /* 指向下一个元素 */ printf(n); return OK; void difference(SLinkList space,int *S) /* 算法 2.17 */ /* 依次输入集合A和B的元素， 在一维数组space中建立表示集合(A-B)(B-A) */ /* 的静态链表，S 为其头指针。假设备用空间足够大，space0.cur 为备用空间的头指针 */ int r,p,m,n,i,j,k; ElemType b; Init

73、Space(space); /* 初始化备用空间 */ *S=Malloc(space); /* 生成 S 的头结点 */ r=*S; /* r 指向 S 的当前最后结点 */ printf(请输入集合 A 和 B 的元素个数 m,n:); scanf(%d,%d%*c,&m,&n); /* %*c 吃掉回车符 */ printf(请输入集合 A 的元素（共%d 个）:,m); for(j=1;j=m;j+) /* 建立集合 A 的链表 */ i=Malloc(space); /* 分配结点 */ scanf(%c,&spacei.data); /* 输入 A 的元素值 */ spacer.c

74、ur=i; /* 插入到表尾 */ r=i; scanf(%*c); /* %*c 吃掉回车符 */ spacer.cur=0; /* 尾结点的指针为空 */ printf(请输入集合 B 的元素（共%d 个）:,n); for(j=1;j=n;j+) /* 依次输入 B 的元素,若不在当前表中,则插入,否则删除 */ scanf(%c,&b); p=*S; k=space*S.cur; /* k 指向集合 A 中的第一个结点 */ while(k!=spacer.cur&spacek.data!=b) /* 在当前表中查找 */ p=k; k=spacek.cur; if(k=spacer.

75、cur) /* 当前表中不存在该元素，插入在 r 所指结点之后，且 r 的位置不变 */ i=Malloc(space); spacei.data=b; spacei.cur=spacer.cur; spacer.cur=i; else /* 该元素已在表中，删除之 */ spacep.cur=spacek.cur; Free(space,k); if(r=k) r=p; /* 若删除的是尾元素，则需修改尾指针 */ void visit(ElemType c) printf(%c ,c); void main() int k; SLinkList s; difference(s,&k); L

76、istTraverse(s,k,visit); /* algo2-9.c 尽量采用 bo2-32.c 中的基本操作实现算法 2.17 的功能 */ #includec1.h #define N 2 typedef char ElemType; #includec2-3.h #includebo2-3.c #includebo2-32.c void visit(ElemType c) printf(%c ,c); int difference(SLinkList space) /* 改进算法 2.17(尽量利用基本操作实现) */ /* 依次输入集合A和B的元素， 在一维数组space中建立表示

77、集合(A-B)(B-A) */ /* 的静态链表，并返回其头指针。假设备用空间足够大，space0.cur 为备用空间的头指针 */ int m,n,i,j,k,S; ElemType b,c; InitSpace(space); /* 初始化备用空间 */ S=InitList(space); /* 生成链表 S 的头结点 */ printf(请输入集合 A 和 B 的元素个数 m,n:); scanf(%d,%d%*c,&m,&n); /* %*c 吃掉回车符 */ printf(请输入集合 A 的元素（共%d 个）:,m); for(j=1;j=m;j+) /* 建立集合 A 的链表 *

78、/ scanf(%c,&b); /* 输入 A 的元素值 */ ListInsert(space,S,j,b); /* 插入到表尾 */ scanf(%*c); /* 吃掉回车符 */ printf(请输入集合 B 的元素（共%d 个）:,n); for(j=1;jnext=*L; /* 指针域指向头结点 */ return OK; Status DestroyList_CL(LinkList *L) /* 操作结果：销毁线性表 L */ LinkList q,p=(*L)-next; /* p 指向头结点 */ while(p!=*L) /* 没到表尾 */ q=p-next; free(p

79、); p=q; free(*L); *L=NULL; return OK; Status ClearList_CL(LinkList *L) /* 改变 L */ /* 初始条件：线性表 L 已存在。操作结果：将 L 重置为空表 */ LinkList p,q; *L=(*L)-next; /* L 指向头结点 */ p=(*L)-next; /* p 指向第一个结点 */ while(p!=*L) /* 没到表尾 */ q=p-next; free(p); p=q; (*L)-next=*L; /* 头结点指针域指向自身 */ return OK; Status ListEmpty_CL(L

80、inkList L) /* 初始条件：线性表 L 已存在。操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE */ if(L-next=L) /* 空 */ return TRUE; else return FALSE; int ListLength_CL(LinkList L) /* 初始条件：L 已存在。操作结果：返回 L 中数据元素个数 */ int i=0; LinkList p=L-next; /* p 指向头结点 */ while(p!=L) /* 没到表尾 */ i+; p=p-next; return i; Status GetElem_CL(LinkList L

81、,int i,ElemType *e) /* 当第 i 个元素存在时,其值赋给 e 并返回 OK,否则返回 ERROR */ int j=1; /* 初始化,j 为计数器 */ LinkList p=L-next-next; /* p 指向第一个结点 */ if(iListLength_CL(L) /* 第 i 个元素不存在 */ return ERROR; while(jnext; j+; *e=p-data; /* 取第 i 个元素 */ return OK; int LocateElem_CL(LinkList L,ElemType e,Status(*compare)(ElemType

82、,ElemType) /* 初始条件：线性表 L 已存在，compare()是数据元素判定函数 */ /* 操作结果： 返回 L 中第 1 个与 e 满足关系 compare()的数据元素的位序。 */ /* 若这样的数据元素不存在，则返回值为 0 */ int i=0; LinkList p=L-next-next; /* p 指向第一个结点 */ while(p!=L-next) i+; if(compare(p-data,e) /* 满足关系 */ return i; p=p-next; return 0; Status PriorElem_CL(LinkList L,ElemType

83、cur_e,ElemType *pre_e) /* 初始条件：线性表 L 已存在 */ /* 操作结果：若 cur_e 是 L 的数据元素，且不是第一个，则用 pre_e 返回它 的前驱， */ /* 否则操作失败，pre_e 无定义 */ LinkList q,p=L-next-next; /* p 指向第一个结点 */ q=p-next; while(q!=L-next) /* p 没到表尾 */ if(q-data=cur_e) *pre_e=p-data; return TRUE; p=q; q=q-next; return FALSE; Status NextElem_CL(Link

84、List L,ElemType cur_e,ElemType *next_e) /* 初始条件：线性表 L 已存在 */ /* 操作结果： 若 cur_e 是 L 的数据元素,且不是最后一个,则用 next_e 返回它的后继， */ /* 否则操作失败，next_e 无定义 */ LinkList p=L-next-next; /* p 指向第一个结点 */ while(p!=L) /* p 没到表尾 */ if(p-data=cur_e) *next_e=p-next-data; return TRUE; p=p-next; return FALSE; Status ListInsert_C

85、L(LinkList *L,int i,ElemType e) /* 改变 L */ /* 在 L 的第 i 个位置之前插入元素 e */ LinkList p=(*L)-next,s; /* p 指向头结点 */ int j=0; if(iListLength_CL(*L)+1) /* 无法在第 i 个元素之前插入 */ return ERROR; while(jnext; j+; s=(LinkList)malloc(sizeof(struct LNode); /* 生成新结点 */ s-data=e; /* 插入 L 中 */ s-next=p-next; p-next=s; if(p=

86、*L) /* 改变尾结点 */ *L=s; return OK; Status ListDelete_CL(LinkList *L,int i,ElemType *e) /* 改变 L */ /* 删除 L 的第 i 个元素,并由 e 返回其值 */ LinkList p=(*L)-next,q; /* p 指向头结点 */ int j=0; if(iListLength_CL(*L) /* 第 i 个元素不存在 */ return ERROR; while(jnext; j+; q=p-next; /* q 指向待删除结点 */ p-next=q-next; *e=q-data; if(*L

87、=q) /* 删除的是表尾元素 */ *L=p; free(q); /* 释放待删除结点 */ return OK; Status ListTraverse_CL(LinkList L,void(*vi)(ElemType) /* 初始条件:L 已存在。操作结果:依次对 L 的每个数据元素调用函数 vi()。一旦 vi()失败,则操作失败 */ LinkList p=L-next-next; while(p!=L-next) vi(p-data); p=p-next; printf(n); return OK; void MergeList_CL(LinkList *La,LinkList L

88、b) LinkList p=Lb-next; Lb-next=(*La)-next; (*La)-next=p-next; free(p); *La=Lb; void visit(ElemType c) printf(%d ,c); void main() int n=5,i; LinkList La,Lb; InitList_CL(&La); for(i=1;i=n;i+) ListInsert_CL(&La,i,i); printf(La=); /* 输出链表 La 的内容 */ ListTraverse_CL(La,visit); InitList_CL(&Lb); for(i=1;id

89、ata=e; return OK; void FreeNode(Link *p) /* 释放 p 所指结点 */ free(*p); *p=NULL; Status InitList(LinkList *L) /* 构造一个空的线性链表 */ Link p; p=(Link)malloc(sizeof(LNode); /* 生成头结点 */ if(p) p-next=NULL; (*L).head=(*L).tail=p; (*L).len=0; return OK; else return ERROR; Status ClearList(LinkList *L) /* 将线性链表 L 重置为

90、空表，并释放原链表的结点空间 */ Link p,q; if(*L).head!=(*L).tail)/* 不是空表 */ p=q=(*L).head-next; (*L).head-next=NULL; while(p!=(*L).tail) p=q-next; free(q); q=p; free(q); (*L).tail=(*L).head; (*L).len=0; return OK; Status DestroyList(LinkList *L) /* 销毁线性链表 L，L 不再存在 */ ClearList(L); /* 清空链表 */ FreeNode(&(*L).head);

91、 (*L).tail=NULL; (*L).len=0; return OK; Status InsFirst(LinkList *L,Link h,Link s) /* 形参增加 L,因为需修改 L */ /* h 指向 L 的一个结点，把 h 当做头结点，将 s 所指结点插入在第一个结点之前 */ s-next=h-next; h-next=s; if(h=(*L).tail) /* h 指向尾结点 */ (*L).tail=h-next; /* 修改尾指针 */ (*L).len+; return OK; Status DelFirst(LinkList *L,Link h,Link *

92、q) /* 形参增加 L,因为需修改 L */ /* h 指向 L 的一个结点，把 h 当做头结点，删除链表中的第一个结点并以 q返回。 */ /* 若链表为空(h 指向尾结点)，q=NULL，返回 FALSE */ *q=h-next; if(*q) /* 链表非空 */ h-next=(*q)-next; if(!h-next) /* 删除尾结点 */ (*L).tail=h; /* 修改尾指针 */ (*L).len-; return OK; else return FALSE; /* 链表空 */ Status Append(LinkList *L,Link s) /* 将指针 s(s

93、-data 为第一个数据元素)所指(彼此以指针相链,以 NULL 结尾)的 */ /* 一串结点链接在线性链表L的最后一个结点之后,并改变链表L的尾指针指向新 */ /* 的尾结点 */ int i=1; (*L).tail-next=s; while(s-next) s=s-next; i+; (*L).tail=s; (*L).len+=i; return OK; Position PriorPos(LinkList L,Link p) /* 已知p指向线性链表L中的一个结点， 返回p所指结点的直接前驱的位置 */ /* 若无前驱，则返回 NULL */ Link q; q=L.head-

94、next; if(q=p) /* 无前驱 */ return NULL; else while(q-next!=p) /* q 不是 p 的直接前驱 */ q=q-next; return q; Status Remove(LinkList *L,Link *q) /* 删除线性链表 L 中的尾结点并以 q 返回，改变链表 L 的尾指针指向新的尾结点 */ Link p=(*L).head; if(*L).len=0) /* 空表 */ *q=NULL; return FALSE; while(p-next!=(*L).tail) p=p-next; *q=(*L).tail; p-next=

95、NULL; (*L).tail=p; (*L).len-; return OK; Status InsBefore(LinkList *L,Link *p,Link s) /* 已知 p 指向线性链表 L 中的一个结点，将 s 所指结点插入在 p 所指结点之前， */ /* 并修改指针 p 指向新插入的结点 */ Link q; q=PriorPos(*L,*p); /* q 是 p 的前驱 */ if(!q) /* p 无前驱 */ q=(*L).head; s-next=*p; q-next=s; *p=s; (*L).len+; return OK; Status InsAfter(Li

96、nkList *L,Link *p,Link s) /* 已知 p 指向线性链表 L 中的一个结点，将 s 所指结点插入在 p 所指结点之后， */ /* 并修改指针 p 指向新插入的结点 */ if(*p=(*L).tail) /* 修改尾指针 */ (*L).tail=s; s-next=(*p)-next; (*p)-next=s; *p=s; (*L).len+; return OK; Status SetCurElem(Link p,ElemType e) /* 已知p指向线性链表中的一个结点， 用e更新p所指结点中数据元素的值 */ p-data=e; return OK; Ele

97、mType GetCurElem(Link p) /* 已知 p 指向线性链表中的一个结点，返回 p 所指结点中数据元素的值 */ return p-data; Status ListEmpty(LinkList L) /* 若线性链表 L 为空表，则返回 TRUE，否则返回 FALSE */ if(L.len) return FALSE; else return TRUE; int ListLength(LinkList L) /* 返回线性链表 L 中元素个数 */ return L.len; Position GetHead(LinkList L) /* 返回线性链表 L 中头结点的位置

98、 */ return L.head; Position GetLast(LinkList L) /* 返回线性链表 L 中最后一个结点的位置 */ return L.tail; Position NextPos(Link p) /* 已知p指向线性链表L中的一个结点， 返回p所指结点的直接后继的位置 */ /* 若无后继，则返回 NULL */ return p-next; Status LocatePos(LinkList L,int i,Link *p) /* 返回 p 指示线性链表 L 中第 i 个结点的位置，并返回 OK，i 值不合法时返回 ERROR */ /* i=0 为头结点 *

99、/ int j; if(iL.len) return ERROR; else *p=L.head; for(j=1;jnext; return OK; Position LocateElem(LinkList L,ElemType e,Status (*compare)(ElemType,ElemType) /* 返回线性链表 L 中第 1 个与 e 满足函数 compare()判定关系的元素的位置， */ /* 若不存在这样的元素，则返回 NULL */ Link p=L.head; do p=p-next; while(p&!(compare(p-data,e); /* 没到表尾且没找到满

100、足关系的元素 */ return p; Status ListTraverse(LinkList L,void(*visit)(ElemType) /* 依次对 L 的每个数据元素调用函数 visit()。一旦 visit()失败，则操作失败 */ Link p=L.head-next; int j; for(j=1;jdata); p=p-next; printf(n); return OK; Status OrderInsert(LinkList *L,ElemType e,int (*comp)(ElemType,ElemType) /* 已知 L 为有序线性链表， 将元素 e 按非降序

101、插入在 L 中。 （用于一元多项式） */ Link o,p,q; q=(*L).head; p=q-next; while(p!=NULL&comp(p-data,e)next; o=(Link)malloc(sizeof(LNode); /* 生成结点 */ o-data=e; /* 赋值 */ q-next=o; /* 插入 */ o-next=p; (*L).len+; /* 表长加 1 */ if(!p) /* 插在表尾 */ (*L).tail=o; /* 修改尾结点 */ return OK; Status LocateElemP(LinkList L,ElemType e,Po

102、sition *q,int(*compare)(ElemType,ElemType) /* 若升序链表 L 中存在与 e 满足判定函数 compare()取值为 0 的元素，则 q指示 L 中 */ /* 第一个值为 e 的结点的位置，并返回 TRUE；否则 q 指示第一个与 e 满足判定函数 */ /* compare()取值0 的元素的前驱的位置。并返回 FALSE。 （用于一元多项式） */ Link p=L.head,pp; do pp=p; p=p-next; while(p&(compare(p-data,e)data.expndata,e)0) /* 到表尾或 compare(p

103、-data,e)0 */ *q=pp; return FALSE; else /* 找到 */ *q=p; return TRUE; Status ListInsert_L(LinkList *L,int i,ElemType e) /* 算法 2.20 */ /* 在带头结点的单链线性表 L 的第 i 个元素之前插入元素 e */ Link h,s; if(!LocatePos(*L,i-1,&h) return ERROR; /* i 值不合法 */ if(!MakeNode(&s,e) return ERROR; /* 结点分配失败 */ InsFirst(L,h,s); /*对于从第

104、i 个结点开始的链表,第 i-1 个结点是它的头结点 */ return OK; Status MergeList_L(LinkList La,LinkList Lb,LinkList *Lc,int(*compare)(ElemType,ElemType) /* 已知单链线性表 La 和 Lb 的元素按值非递减排列。归并 La 和 Lb 得到新的单链 */ /* 线性表 Lc，Lc 的元素也按值非递减排列。 （不改变 La、Lb）算法 2.21 */ Link ha,hb,pa,pb,q; ElemType a,b; if(!InitList(Lc) return ERROR; /* 存储空

105、间分配失败 */ ha=GetHead(La); /* ha 和 hb 分别指向 La 和 Lb 的头结点 */ hb=GetHead(Lb); pa=NextPos(ha); /* pa 和 pb 分别指向 La 和 Lb 的第一个结点 */ pb=NextPos(hb); while(!ListEmpty(La)&!ListEmpty(Lb) /* La 和 Lb 均非空 */ a=GetCurElem(pa); /* a 和 b 为两表中当前比较元素 */ b=GetCurElem(pb); if(compare(a,b)b */ DelFirst(&Lb,hb,&q); InsFirs

106、t(Lc,(*Lc).tail,q); pb=NextPos(hb); if(!ListEmpty(La) Append(Lc,pa); else Append(Lc,pb); FreeNode(&ha); FreeNode(&hb); return OK; int comp(ElemType c1,ElemType c2) return c1-c2; void visit(ElemType c) printf(%d ,c); /* 整型 */ void main() LinkList La,Lb,Lc; int j; InitList(&La); for(j=1;j=5;j+) ListIn

107、sert_L(&La,j,j); /* 顺序插入 1 2 3 4 5 */ printf(La=); ListTraverse(La,visit); InitList(&Lb); for(j=1;j=5;j+) ListInsert_L(&Lb,j,2*j); /* 顺序插入 2 4 6 8 10 */ printf(Lb=); ListTraverse(Lb,visit); InitList(&Lc); MergeList_L(La,Lb,&Lc,comp); /* 归并 La 和 Lb，产生 Lc */ printf(Lc=); ListTraverse(Lc,visit); Destro

108、yList(&Lc); /* algo2-12.c 用单链表实现算法 2.1,仅有 4 句与 algo2-1.c 不同 */ #includec1.h typedef int ElemType; #includec2-2.h /* 此句与 algo2-1.c 不同(因为采用不同的结构) */ #includebo2-2.c /* 此句与 algo2-1.c 不同(因为采用不同的结构) */ Status equal(ElemType c1,ElemType c2) /* 判断是否相等的函数，Union()用到 */ if(c1=c2) return TRUE; else return FALS

109、E; void Union(LinkList La,LinkList Lb) /* 算法 2.1,此句与 algo2-1.c 不同 */ /* 将所有在线性表 Lb 中但不在 La 中的数据元素插入到 La 中 */ ElemType e; int La_len,Lb_len; int i; La_len=ListLength(La); /* 求线性表的长度 */ Lb_len=ListLength(Lb); for(i=1;i=Lb_len;i+) GetElem(Lb,i,&e); /* 取 Lb 中第 i 个数据元素赋给 e */ if(!LocateElem(La,e,equal) /

110、* La 中不存在和 e 相同的元素,则插入之 */ ListInsert(La,+La_len,e); void print(ElemType c) printf(%d ,c); void main() LinkList La,Lb; /* 此句与 algo2-1.c 不同(因为采用不同的结构) */ Status i; int j; i=InitList(&La); if(i=1) /* 创建空表 La 成功 */ for(j=1;j=5;j+) /* 在表 La 中插入 5 个元素 */ i=ListInsert(La,j,j); printf(La= ); /* 输出表 La 的内容

111、*/ ListTraverse(La,print); InitList(&Lb); /* 也可不判断是否创建成功 */ for(j=1;j=5;j+) /* 在表 Lb 中插入 5 个元素 */ i=ListInsert(Lb,j,2*j); printf(Lb= ); /* 输出表 Lb 的内容 */ ListTraverse(Lb,print); Union(La,Lb); printf(new La= ); /* 输出新表 La 的内容 */ ListTraverse(La,print); /* algo2-13.c 采用链表结构实现算法2.2的程序， 仅有4句与algo2-2.c不同

112、*/ #includec1.h typedef int ElemType; #includec2-2.h /* 此句与 algo2-2.c 不同 */ #includebo2-2.c /* 此句与 algo2-2.c 不同 */ void MergeList(LinkList La,LinkList Lb,LinkList *Lc) /* 算法 2.2,此句与algo2-2.c 不同 */ /* 已知线性表 La 和 Lb 中的数据元素按值非递减排列。 */ /* 归并 La 和 Lb 得到新的线性表 Lc,Lc 的数据元素也按值非递减排列 */ int i=1,j=1,k=0; int La

113、_len,Lb_len; ElemType ai,bj; InitList(Lc); /* 创建空表 Lc */ La_len=ListLength(La); Lb_len=ListLength(Lb); while(i=La_len&j=Lb_len) /* 表 La 和表 Lb 均非空 */ GetElem(La,i,&ai); GetElem(Lb,j,&bj); if(ai=bj) ListInsert(*Lc,+k,ai); +i; else ListInsert(*Lc,+k,bj); +j; while(i=La_len) /* 表 La 非空且表 Lb 空 */ GetElem

114、(La,i+,&ai); ListInsert(*Lc,+k,ai); while(j=Lb_len) /* 表 Lb 非空且表 La 空 */ GetElem(Lb,j+,&bj); ListInsert(*Lc,+k,bj); void print(ElemType c) printf(%d ,c); void main() LinkList La,Lb,Lc; /* 此句与 algo2-2.c 不同 */ int j,a4=3,5,8,11,b7=2,6,8,9,11,15,20; InitList(&La); /* 创建空表 La */ for(j=1;j=4;j+) /* 在表 La

115、 中插入 4 个元素 */ ListInsert(La,j,aj-1); printf(La= ); /* 输出表 La 的内容 */ ListTraverse(La,print); InitList(&Lb); /* 创建空表 Lb */ for(j=1;jMAXSTRLEN) return ERROR; else T0=strlen(chars); for(i=1;i=T0;i+) Ti=*(chars+i-1); return OK; Status StrCopy(SString T,SString S) /* 由串 S 复制得串 T */ int i; for(i=0;iT,则返回值0

116、;若 S=T,则返回值=0;若 ST,则返回值0 */ int i; for(i=1;i=S0&i=T0;+i) if(Si!=Ti) return Si-Ti; return S0-T0; int StrLength(SString S) /* 返回串的元素个数 */ return S0; Status ClearString(SString S) /* 初始条件:串 S 存在。操作结果:将 S 清为空串 */ S0=0;/* 令串长为零 */ return OK; Status Concat(SString T,SString S1,SString S2) /* 算法 4.2 改 */ /

117、* 用 T 返回 S1 和 S2 联接而成的新串。 若未截断， 则返回 TRUE， 否则 FALSE */ int i; if(S10+S20=MAXSTRLEN) /* 未截断 */ for(i=1;i=S10;i+) Ti=S1i; for(i=1;i=S20;i+) TS10+i=S2i; T0=S10+S20; return TRUE; else /* 截断 S2 */ for(i=1;i=S10;i+) Ti=S1i; for(i=1;i=MAXSTRLEN-S10;i+) TS10+i=S2i; T0=MAXSTRLEN; return FALSE; Status SubStrin

118、g(SString Sub,SString S,int pos,int len) /* 用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。算法 4.3 */ int i; if(posS0|lenS0-pos+1) return ERROR; for(i=1;i=len;i+) Subi=Spos+i-1; Sub0=len; return OK; int Index(SString S,SString T,int pos) /* 返回子串 T 在主串 S 中第 pos 个字符之后的位置。 若不存在,则函数值为 0。 */ /* 其中,T 非空,1posStrLength(

119、S)。算法 4.5 */ int i,j; if(1=pos&pos=S0) i=pos; j=1; while(i=S0&jT0) return i-T0; else return 0; else return 0; Status StrInsert(SString S,int pos,SString T) /* 初始条件: 串 S 和 T 存在,1posStrLength(S)+1 */ /* 操作结果: 在串 S 的第 pos 个字符之前插入串 T。 完全插入返回 TRUE,部分插入返回 FALSE */ int i; if(posS0+1) return ERROR; if(S0+T0

120、=pos;i-) Si+T0=Si; for(i=pos;ipos+T0;i+) Si=Ti-pos+1; S0=S0+T0; return TRUE; else /* 部分插入 */ for(i=MAXSTRLEN;i=pos;i-) Si=Si-T0; for(i=pos;ipos+T0;i+) Si=Ti-pos+1; S0=MAXSTRLEN; return FALSE; Status StrDelete(SString S,int pos,int len) /* 初始条件: 串 S 存在,1posStrLength(S)-len+1 */ /* 操作结果: 从串 S 中删除第 pos

121、 个字符起长度为 len 的子串 */ int i; if(posS0-len+1|len0) return ERROR; for(i=pos+len;i=S0;i+) Si-len=Si; S0-=len; return OK; Status Replace(SString S,SString T,SString V) /* 初始条件: 串 S,T 和 V 存在,T 是非空串（此函数与串的存储结构无关） */ /* 操作结果: 用 V 替换主串 S 中出现的所有与 T 相等的不重叠的子串 */ int i=1; /* 从串 S 的第一个字符起查找串 T */ if(StrEmpty(T) /

122、* T 是空串 */ return ERROR; do i=Index(S,T,i); /* 结果 i 为从上一个 i 之后找到的子串 T 的位置 */ if(i) /* 串 S 中存在串 T */ StrDelete(S,i,StrLength(T); /* 删除该串 T */ StrInsert(S,i,V); /* 在原串 T 的位置插入串 V */ i+=StrLength(V); /* 在插入的串 V 后面继续查找串 T */ while(i); return OK; void DestroyString() /* 由于 SString 是定长类型,无法销毁 */ void StrP

123、rint(SString T) /* 输出字符串 T。另加 */ int i; for(i=1;i=T0;i+) printf(%c,Ti); printf(n); void get_next(SString T,int next) /* 求模式串 T 的 next 函数值并存入数组 next 算法 4.7 */ int i=1,j=0; next1=0; while(iT0) if(j=0|Ti=Tj) +i; +j; nexti=j; else j=nextj; int Index_KMP(SString S,SString T,int pos,int next) /* 利用模式串 T 的

124、 next 函数求 T 在主串 S 中第 pos 个字符之后的位置的 KMP算法。 */ /* 其中,T 非空,1posStrLength(S)。算法 4.6 */ int i=pos,j=1; while(i=S0&jT0) /* 匹配成功 */ return i-T0; else return 0; void main() int i,j,*p; SString s1,s2; /* 以教科书中图 4.5 为例 */ StrAssign(s1,acabaabaabcacaabc); printf(主串为: ); StrPrint(s1); StrAssign(s2,abaabcac); pr

125、intf(子串为: ); StrPrint(s2); i=StrLength(s2); p=(int*)malloc(i+1)*sizeof(int); /* 生成 s2 的 next 数组 */ get_next(s2,p); printf(子串的 next 函数为: ); for(j=1;j=i;j+) printf(%d ,*(p+j); printf(n); i=Index_KMP(s1,s2,1,p); if(i) printf(主串和子串在第%d 个字符处首次匹配n,i); else printf(主串和子串匹配不成功n); /* algo5-1.c 实现算法 5.2 的程序 */

126、 #includec1.h typedef int ElemType; #includec5-2.h /* c5-2.h 稀疏矩阵的三元组顺序表存储表示 */ #define MAXSIZE 100 /* 非零元个数的最大值 */ typedef struct int i,j; /* 行下标,列下标 */ ElemType e; /* 非零元素值 */ Triple; typedef struct Triple dataMAXSIZE+1; /* 非零元三元组表,data0未用 */ int mu,nu,tu; /* 矩阵的行数、列数和非零元个数 */ TSMatrix; #includebo

127、5-2.c /* bo5-2.c 三元组稀疏矩阵的基本操作,包括算法 5.1(9 个) */ Status CreateSMatrix(TSMatrix *M) /* 创建稀疏矩阵 M */ int i,m,n; ElemType e; Status k; printf(请输入矩阵的行数,列数,非零元素数：); scanf(%d,%d,%d,&(*M).mu,&(*M).nu,&(*M).tu); (*M).data0.i=0; /* 为以下比较顺序做准备 */ for(i=1;i=(*M).tu;i+) do printf(请按行序顺序输入第%d个非零元素所在的行(1%d),列(1%d),元

128、素值：,i,(*M).mu,(*M).nu); scanf(%d,%d,%d,&m,&n,&e); k=0; if(m(*M).mu|n(*M).nu) /* 行或列超出范围 */ k=1; if(m(*M).datai-1.i|m=(*M).datai-1.i&n=(*M).datai-1.j) /* 行或列的顺序有错 */ k=1; while(k); (*M).datai.i=m; (*M).datai.j=n; (*M).datai.e=e; return OK; void DestroySMatrix(TSMatrix *M) /* 销毁稀疏矩阵 M */ (*M).mu=0; (*

129、M).nu=0; (*M).tu=0; void PrintSMatrix(TSMatrix M) /* 输出稀疏矩阵 M */ int i; printf(%d 行%d 列%d 个非零元素。n,M.mu,M.nu,M.tu); printf(行 列 元素值n); for(i=1;i=M.tu;i+) printf(%2d%4d%8dn,M.datai.i,M.datai.j,M.datai.e); Status CopySMatrix(TSMatrix M,TSMatrix *T) /* 由稀疏矩阵 M 复制得到 T */ (*T)=M; return OK; int comp(int c1

130、,int c2) /* 另加 */ /* AddSMatrix 函数要用到 */ int i; if(c1c2) i=1; else if(c1=c2) i=0; else i=-1; return i; Status AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q) /* 求稀疏矩阵的和 Q=M+N */ Triple *Mp,*Me,*Np,*Ne,*Qh,*Qe; if(M.mu!=N.mu) return ERROR; if(M.nu!=N.nu) return ERROR; (*Q).mu=M.mu; (*Q).nu=M.nu; Mp=&M.

131、data1; /* Mp 的初值指向矩阵 M 的非零元素首地址 */ Np=&N.data1; /* Np 的初值指向矩阵 N 的非零元素首地址 */ Me=&M.dataM.tu; /* Me 指向矩阵 M 的非零元素尾地址 */ Ne=&N.dataN.tu; /* Ne 指向矩阵 N 的非零元素尾地址 */ Qh=Qe=(*Q).data; /* Qh、Qe 的初值指向矩阵 Q 的非零元素首地址的前一地址 */ while(Mp=Me&Npi,Np-i) case 1: *Qe=*Mp; Mp+; break; case 0: switch(comp(Mp-j,Np-j) /* M、N

132、矩阵当前非零元素的行相等,继续比较列 */ case 1: *Qe=*Mp; Mp+; break; case 0: *Qe=*Mp; Qe-e+=Np-e; if(!Qe-e) /* 元素值为 0，不存入压缩矩阵 */ Qe-; Mp+; Np+; break; case -1: *Qe=*Np; Np+; break; case -1: *Qe=*Np; Np+; if(MpMe) /* 矩阵 M 的元素全部处理完毕 */ while(NpNe) /* 矩阵 N 的元素全部处理完毕 */ while(Mp=Me) Qe+; *Qe=*Mp; Mp+; (*Q).tu=Qe-Qh; /* 矩

133、阵 Q 的非零元素个数 */ return OK; Status SubtSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q) /* 求稀疏矩阵的差 Q=M-N */ int i; for(i=1;i=N.tu;i+) N.datai.e*=-1; AddSMatrix(M,N,Q); return OK; Status MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q) /* 求稀疏矩阵的乘积 Q=M*N */ int i,j,h=M.mu,l=N.nu,Qn=0; /* h,l 分别为矩阵 Q 的行、列值,Qn 为矩

134、阵 Q 的非零元素个数，初值为 0 */ ElemType *Qe; if(M.nu!=N.mu) return ERROR; (*Q).mu=M.mu; (*Q).nu=N.nu; Qe=(ElemType *)malloc(h*l*sizeof(ElemType); /* Qe 为矩阵 Q 的临时数组 */ /* 矩阵 Q 的第 i 行 j 列的元素值存于*(Qe+(i-1)*l+j-1)中，初值为 0 */ for(i=0;ih*l;i+) *(Qe+i)=0; /* 赋初值 0 */ for(i=1;i=M.tu;i+) /* 矩阵元素相乘，结果累加到 Qe */ for(j=1;j=

135、N.tu;j+) if(M.datai.j=N.dataj.i) *(Qe+(M.datai.i-1)*l+N.dataj.j-1)+=M.datai.e*N.dataj.e; for(i=1;i=M.mu;i+) for(j=1;j=N.nu;j+) if(*(Qe+(i-1)*l+j-1)!=0) Qn+; (*Q).dataQn.e=*(Qe+(i-1)*l+j-1); (*Q).dataQn.i=i; (*Q).dataQn.j=j; free(Qe); (*Q).tu=Qn; return OK; Status TransposeSMatrix(TSMatrix M,TSMatrix

136、 *T) /* 求稀疏矩阵 M 的转置矩阵 T。算法 5.1 */ int p,q,col; (*T).mu=M.nu; (*T).nu=M.mu; (*T).tu=M.tu; if(*T).tu) q=1; for(col=1;col=M.nu;+col) for(p=1;p=M.tu;+p) if(M.datap.j=col) (*T).dataq.i=M.datap.j; (*T).dataq.j=M.datap.i; (*T).dataq.e=M.datap.e; +q; return OK; Status FastTransposeSMatrix(TSMatrix M,TSMatri

137、x *T) /* 快速求稀疏矩阵 M 的转置矩阵 T。算法 5.2 */ int p,q,t,col,*num,*cpot; num=(int *)malloc(M.nu+1)*sizeof(int); /* 生成数组（0不用） */ cpot=(int *)malloc(M.nu+1)*sizeof(int); /* 生成数组（0不用） */ (*T).mu=M.nu; (*T).nu=M.mu; (*T).tu=M.tu; if(*T).tu) for(col=1;col=M.nu;+col) numcol=0; /* 设初值 */ for(t=1;t=M.tu;+t) /* 求 M 中每

138、一列含非零元素个数 */ +numM.datat.j; cpot1=1; for(col=2;col=M.nu;+col) /* 求第 col 列中第一个非零元在(*T).data中的序号 */ cpotcol=cpotcol-1+numcol-1; for(p=1;pS.base) *e=*(S.top-1); return OK; else return ERROR; Status Push(SqStack *S,SElemType e) /* 插入元素 e 为新的栈顶元素 */ if(*S).top-(*S).base=(*S).stacksize) /* 栈满，追加存储空间 */ (*

139、S).base=(SElemType *)realloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(SElemType); if(!(*S).base) exit(OVERFLOW); /* 存储分配失败 */ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; *(*S).top)+=e; return OK; Status Pop(SqStack *S,SElemType *e) /* 若栈不空， 则删除 S 的栈顶元素， 用 e 返回其值， 并返回 OK；

140、 否则返回 ERROR */ if(*S).top=(*S).base) return ERROR; *e=*-(*S).top; return OK; Status StackTraverse(SqStack S,Status(*visit)(SElemType) /* 从栈底到栈顶依次对栈中每个元素调用函数 visit()。 */ /* 一旦 visit()失败，则操作失败 */ while(S.topS.base) visit(*S.base+); printf(n); return OK; Status visit(SElemType c) printf(%d ,c); return

141、OK; void main() int j; SqStack s; SElemType e; if(InitStack(&s)=OK) for(j=1;jnext=NULL; return OK; Status DestroyQueue(LinkQueue *Q) /* 销毁队列 Q(无论空否均可) */ while(*Q).front) (*Q).rear=(*Q).front-next; free(*Q).front); (*Q).front=(*Q).rear; return OK; Status ClearQueue(LinkQueue *Q) /* 将 Q 清为空队列 */ Queu

142、ePtr p,q; (*Q).rear=(*Q).front; p=(*Q).front-next; (*Q).front-next=NULL; while(p) q=p; p=p-next; free(q); return OK; Status QueueEmpty(LinkQueue Q) /* 若 Q 为空队列,则返回 TRUE,否则返回 FALSE */ if(Q.front=Q.rear) return TRUE; else return FALSE; int QueueLength(LinkQueue Q) /* 求队列的长度 */ int i=0; QueuePtr p; p=Q

143、.front; while(Q.rear!=p) i+; p=p-next; return i; Status GetHead_Q(LinkQueue Q,QElemType *e) /* 若队列不空,则用 e 返回 Q 的队头元素,并返回 OK,否则返回 ERROR */ QueuePtr p; if(Q.front=Q.rear) return ERROR; p=Q.front-next; *e=p-data; return OK; Status EnQueue(LinkQueue *Q,QElemType e) /* 插入元素 e 为 Q 的新的队尾元素 */ QueuePtr p=(Q

144、ueuePtr)malloc(sizeof(QNode); if(!p) /* 存储分配失败 */ exit(OVERFLOW); p-data=e; p-next=NULL; (*Q).rear-next=p; (*Q).rear=p; return OK; Status DeQueue(LinkQueue *Q,QElemType *e) /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */ QueuePtr p; if(*Q).front=(*Q).rear) return ERROR; p=(*Q).front-next; *e=p-data; (*Q

145、).front-next=p-next; if(*Q).rear=p) (*Q).rear=(*Q).front; free(p); return OK; Status QueueTraverse(LinkQueue Q,void(*vi)(QElemType) /* 从队头到队尾依次对队列 Q 中每个元素调用函数 vi()。一旦 vi 失败,则操作失败 */ QueuePtr p; p=Q.front-next; while(p) vi(p-data); p=p-next; printf(n); return OK; void visit(QElemType i) printf(%d ,i)

146、; void main() int i; QElemType d; LinkQueue q; i=InitQueue(&q); if(i) printf(InitQueue success!n); printf(Queue empty or not?%d(1:empty 0:not empty) ,QueueEmpty(q); printf(The length of Queue is %dn,QueueLength(q); EnQueue(&q,-5); EnQueue(&q,5); EnQueue(&q,10); printf(After insert(-5,5,10),The lengt

147、h of Queue is %dn,QueueLength(q); printf(Queue empty or not?%d(1:empty 0:not empty) ,QueueEmpty(q); printf(Output the Queue in term is:); QueueTraverse(q,visit); i=GetHead_Q(q,&d); if(i=OK) printf(The front of Queue is: %dn,d); DeQueue(&q,&d); printf(After delete the front ElemType%dn,d); i=GetHead_Q(q,&d); if(i=OK) printf(The new front of Queue is: %dn,d); ClearQueue(&q); printf(After clear the Queue,q.front=%u q.rear=%u q.front-next=%un,q.front,q.rear,q.front-next); DestroyQueue(&q); printf(After destory the Queue,q.front=%u q.rear=%un,q.front, q.rear);