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

资源描述

<p><span id="_baidu_bookmark_start_0" style="display: none; line-height: 0px;">‍</span>/* c1、h (程序名) */ #include</p><string、h>#include<ctype、h>#include<malloc、h>/* malloc()等 */ #include<limits、h>/* INT_MAX等 */ #include<stdio、h>/* EOF(=^Z或F6),NULL */ #include<stdlib、h>/* atoi() */ #include<io、h>/* eof() */ #include<math、h>/* floor(),ceil(),abs() */ #include<process、h>/* 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已存在，1≤i≤ListLength(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;   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   {     *next_e=*++p;     return OK;   } } Status ListInsert(SqList *L,int i,ElemType e) /* 算法2、4 */ { /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(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已存在，1≤i≤ListLength(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)     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;   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)     {       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,a[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20};   InitList(&La); /* 创建空表La */   for(j=1;j<=4;j++) /* 在表La中插入4个元素 */     ListInsert(&La,j,a[j-1]);   printf("La= "); /* 输出表La得内容 */   ListTraverse(La,print);   InitList(&Lb); /* 创建空表Lb */   for(j=1;j<=7;j++) /* 在表Lb中插入7个元素 */     ListInsert(&Lb,j,b[j-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<=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空 */     *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&&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 *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得内容 */   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;     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&&j<i) p="p-">next;     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&&j<i-1) p="p-">next;     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&&j<i-1) p="p-">next;     j++;   }   if(!p->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<</i-1)></i-1)></i)></process、h></math、h></io、h></stdlib、h></stdio、h></limits、h></malloc、h></ctype、h></string、h>

展开阅读全文