《整理数据结构源码》由会员分享,可在线阅读,更多相关《整理数据结构源码(230页珍藏版)》请在金锄头文库上搜索。
1、/* bo1-1.c 抽象数据类型Triplet和ElemType(由c1-1.h定义)的基本操作(8个) */ Status InitTriplet(Triplet *T,ElemType v1,ElemType v2,ElemType v3) /* 操作结果:构造三元组T,依次置T的三个元素的初值为v1,v2和v3 */ *T=(ElemType *)malloc(3*sizeof(ElemType); if(!*T) exit(OVERFLOW); (*T)0=v1,(*T)1=v2,(*T)2=v3; return OK; Status DestroyTriplet(Triplet *
2、T) /* 操作结果:三元组T被销毁 */ free(*T); *T=NULL; return OK; Status Get(Triplet T,int i, ElemType *e) /* 初始条件:三元组T已存在,1i3。操作结果:用e返回T的第i元的值 */ if(i3) return ERROR; *e=Ti-1; return OK; Status Put(Triplet T,int i,ElemType e) /* 初始条件:三元组T已存在,1i3。操作结果:改变T的第i元的值为e */ if(i3) return ERROR; Ti-1=e; return OK; Status
3、IsAscending(Triplet T) /* 初始条件:三元组T已存在。操作结果:如果T的三个元素按升序排列,返回1,否则返回0 */ return(T0=T1&T1=T1&T1=T2); Status Max(Triplet T,ElemType *e) /* 初始条件:三元组T已存在。操作结果:用e返回T的三个元素中的最大值 */ *e=T0=T1?T0=T2?T0:T2:T1=T2?T1:T2; return OK; Status Min(Triplet T,ElemType *e) /* 初始条件:三元组T已存在。操作结果:用e返回T的三个元素中的最小值 */ *e=T0=T1?
4、T0=T2?T0:T2:T1=T2?T1:T2; return OK;/* main1-1.c 检验基本操作bo1-1.c的主函数 */ #includec1.h /* 要将程序中所有#include命令所包含的文件拷贝到当前目录下 */ /* 以下2行可根据需要选用一个(且只能选用一个),而不需改变基本操作bo1-1.c */ typedef int ElemType; /* 定义抽象数据类型ElemType在本程序中为整型 */ /*typedef double ElemType; /* 定义抽象数据类型ElemType在本程序中为双精度型 */ #includec1-1.h /* 在此命
5、令之前要定义ElemType的类型 */ #includebo1-1.c /* 在此命令之前要包括c1-1.h文件(因为其中定义了Triplet) */ void main()Triplet T; ElemType m; Status i; i=InitTriplet(&T,5,7,9); /*i=InitTriplet(&T,5.0,7.1,9.3); /* 当ElemType为双精度型时,可取代上句 */ printf(调用初始化函数后,i=%d(1:成功) T的三个值为:%d %d %dn,i,T0,T1,T2); /* 当ElemType的类型变化时,要相应改变printf()的格式符
6、。 */ i=Get(T,2,&m); if(i=OK) printf(T的第2个值为:%dn,m); i=Put(T,2,6); if(i=OK) printf(将T的第2个值改为6后,T的三个值为:%d %d %dn,T0,T1,T2); i=IsAscending(T); /* 此类函数实参与ElemType的类型无关,当ElemType的类型变化时,实参不需改变 */ printf(调用测试升序的函数后,i=%d(0:否 1:是)n,i); i=IsDescending(T); printf(调用测试降序的函数后,i=%d(0:否 1:是)n,i); if(i=Max(T,&m)=OK
7、) /* 先赋值再比较 */ printf(T中的最大值为:%dn,m); if(i=Min(T,&m)=OK) printf(T中的最小值为:%dn,m); DestroyTriplet(&T); /* 函数也可以不带回返回值 */ printf(销毁T后,T=%u(NULL)n,T);/* c2-1.h 线性表的动态分配顺序存储结构 */ #define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量 */ #define LISTINCREMENT 2 /* 线性表存储空间的分配增量 */ typedef struct ElemType *elem; /* 存储空间
8、基址 */ int length; /* 当前长度 */ int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */ SqList;/* c2-2.h 线性表的单链表存储结构 */ struct LNode ElemType data; struct LNode *next; ; typedef struct LNode *LinkList; /* 另一种定义LinkList的方法 */* c2-3.h 线性表的静态单链表存储结构 */ #define MAXSIZE 100 /* 链表的最大长度 */ typedef struct ElemType
9、 data; int cur; component,SLinkListMAXSIZE;/* c2-4.h 线性表的双向链表存储结构 */ typedef struct DuLNode ElemType data; struct DuLNode *prior,*next; DuLNode,*DuLinkList;/* c2-5.h 带头结点的线性链表类型 */ typedef struct LNode /* 结点类型 */ ElemType data; struct LNode *next; LNode,*Link,*Position; typedef struct LinkList /* 链表
10、类型 */ Link head,tail; /* 分别指向线性链表中的头结点和最后一个结点 */ int len; /* 指示线性链表中数据元素的个数 */ LinkList;/* c2-6.h 抽象数据类型Polynomial的实现 */ typedef struct /* 项的表示,多项式的项作为LinkList的数据元素 */ float coef; /* 系数 */ int expn; /* 指数 */ term,ElemType; /* 两个类型名:term用于本ADT,ElemType为LinkList的数据对象名 */* algo2-1.c 实现算法2.1的程序 */ #incl
11、udec1.h typedef int ElemType; #includec2-1.h /* 采用线性表的动态分配顺序存储结构 */ #includebo2-1.c /* 可以使用bo2-1.c中的基本操作 */ 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中 */ ElemTyp
12、e 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) /* La中不存在和e相同的元素,则插入之 */ ListInsert(La,+La_len,e); void print(ElemType *c) printf(%d ,*c); void main() SqList La,Lb; Sta
13、tus 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的内容 */ 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-2.c 实现算法2.2的程序:线性表归并 */ #includec1.h typedef int ElemType; #includec2-1.h #includebo2-1.c void