《数据结构》的全部代码实现C语言.doc

/* 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 #define 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得程序 */ #include"c1、h" typedef int ElemType;#include"c2-1、h" /*c2-1、h 线性表得动态分配顺序存储结构 */ #define LIST_INIT_SIZE 10 /* 线性表存储空间得初始分配量 */ #define LISTINCREMENT 2 /* 线性表存储空间得分配增量 */ typedef struct   ElemType *elem; /* 存储空间基址 */   int length; /* 当前长度 */   int listsize; /* 当前分配得存储容量(以sizeof(ElemType)为单位) */ SqList;#include"bo2-1、c"/* bo2-1、c 顺序表示得线性表(存储结构由c2-1、h定义)得基本操作(12个) */ Status InitList(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已存在。操作结果：销毁顺序线性表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; int ListLength(SqList L) /* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */   return L、length; Status GetElem(SqList L,int i,ElemType *e) /* 初始条件：顺序线性表L已存在，1iListLength(L) */   /* 操作结果：用e返回L中第i个数据元素得值 */   if(i<1|i>L、length)     exit(ERROR);   *e=*(L、elem+i-1);   return OK; int LocateElem(SqList L,ElemType e,Status(*compare)(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)     return 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; &nbsp; while(i<=l、length&&*p!=cur_e) i="">L、length)     return INFEASIBLE;   else       *pre_e=*-p;     return OK;   Status NextElem(SqList L,ElemType cur_e,ElemType *next_e) /* 初始条件：顺序线性表L已存在 */   /* 操作结果：若cur_e就是L得数据元素，且不就是最后一个，则用next_e返回它得后继， */   /*           否则操作失败，next_e无定义 */   int i=1;   ElemType *p=L、elem;   while(i<L、length&&*p!=cur_e)       i+;     p+;     if(i=L、length)     return INFEASIBLE;   else   &nbsp;   *next_e=*+p;     return OK;   Status ListInsert(SqList *L,int i,ElemType e) /* 算法2、4 */ /* 初始条件：顺序线性表L已存在，1iListLength(L)+1 */   /* 操作结果：在L中第i个位置之前插入新得数据元素e，L得长度加1 */   ElemType *newbase,*q,*p;   if(i<1|i>(*L)、length+1) /* i值不合法 */     return ERROR;   if(*L)、length>=(*L)、listsize) /* 当前存储空间已满,增加分配 */       newbase=(ElemType *)realloc(*L)、elem,(*L)、listsize+LISTINCREMENT)*sizeof(ElemType);     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(SqList *L,int i,ElemType *e) /* 算法2、5 */ /* 初始条件：顺序线性表L已存在，1iListLength(L) */   /* 操作结果：删除L得第i个数据元素，并用e返回其值，L得长度减1 */   ElemType *p,*q;   if(i<1|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) /* 被删除元素之后得元素左移 */     *(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");   return OK; Status equal(ElemType c1,ElemType c2) /* 判断就是否相等得函数，Union()用到 */   if(c1=c2)   &nbsp; 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(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; &nbsp; 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得程序 */ #include"c1、h" typedef int ElemType; #include"c2-1、h" #include"bo2-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;   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)       &nbsp;   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);     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; &nbsp; InitList(&La); /* 创建空表La */   for(j=1;j<=4;j+) /* 在表La中插入4个元素 */     ListInsert(&La,j,aj-1);   printf("La= "); /* 输出表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得程序 */ #include"c1、h" typedef int ElemType; #include"c2-1、h" #include"bo2-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、length;/*不用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&lt;=pb_last) /* 表La与表Lb均非空 */   /* 归并 */     if(*pa<=*pb)       *pc+=*pa+;     else       *pc+=*pb+;     while(pa<=pa_last) /* 表La非空且表Lb空 */     *pc+=*pa+; /* 插入La得剩余元素 */   while(pb<=pb_last) /* 表Lb非空且表La空 */ &nbsp;   *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);   printf("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得第一个循环语句中得条件语句为开关语句，且当 */ /* *pa=*pb时，只将两者中之一插入Lc。此操作得结果与算法2、1相同 */ #include"c1、h" typedef int ElemType; #include"c2-1、h" #include"bo2-1、c" int comp(ElemType c1,ElemType c2)   int i;   if(c1<c2)     i=1;   else if(c1=c2)     i=0;   else     i=-1;   return i; void MergeList(SqList La,SqList Lb,SqList *Lc) /* 另一种合并线性表得方法（根据算法2、7下得要求修改算法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<=pa_last&&amp;pb<=pb_last) /* 表La与表Lb均非空 */     switch(comp(*pa,*pb) /* 此句与算法2、7不同 */           case  0: pb+;       case  1: *pc+=*pa+;                break;       case -1: *pc+=*pb+;   &nbsp;   while(pa<=pa_last) /* 表La非空且表Lb空 */     *pc+=*pa+;   while(pb<=pb_last) /* 表Lb非空且表La空 */     *pc+=*pb+;   (*Lc)、length=pc-(*Lc)、elem; /* 加此句 */ 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);   printf("La= "); /* 输出表La得内容 */   ListTraverse(La,print);   InitList(&Lb); /* 创建空表Lb */   for(j=1;j<=5;j+) lb="); /* 输出表Lb得内容 */ &nbsp; ListTraverse(Lb,print);   MergeList(La,Lb,&Lc);   printf(" lc="); /* 输出表Lc得内容 */   ListTraverse(Lc,print); /* algo2-5、c 实现算法2、11、2、12得程序 */ #include" typedef="" int="" h="" struct="" lnode="" elemtype="" c="" status="" linklist="" l="(LinkList)malloc(sizeof(struct" -="">next=NULL; /* 指针域为空 */   return OK; Status DestroyList(LinkList *L) /* 初始条件：线性表L已存在。操作结果：销毁线性表L */   LinkList q;   while(*L)       q=(*L)->next; &nbsp;   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; Status 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 GetElem(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|j>i) /* 第i个元素不存在 */     return ERROR;   *e=p->data; /* 取第i个元素 */   return OK; int LocateElem(LinkList L,ElemType e,Status(*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 cur_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 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;       return 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|j>i-1) /* i小于1或者大于表长 */     return ERROR;   s=(LinkList)malloc(sizeof(struct LNode); /* 生成新结点 */   s->data=e; /* 插入L中 */   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-&gt;next|j>i-1) /* 删除位置不合理 */     return ERROR;   q=p->next; /* 删除并释放结点 */   p->next=q->next;   *e=q->data;   free(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 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;i>0;-i)       p=(LinkList)malloc(sizeof(struct LNode); /* 生成新结点 */     scanf("%d",&p->data); /* 输入元素值 */     p->next=(*L)->next; /* 插入到表头 */     (*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;i<