《数据结构》的全部代码实现C语言.doc
《数据结构》的全部代码实现C语言.doc
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- 数据结构 华严 全部 代码 实现 语言
- 资源描述：
-
<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)><!--=5;j++)--><!--1||i--><!--1||i--><!--=l、length&&*p!=cur_e)--><!--1||i--></process、h></math、h></io、h></stdlib、h></stdio、h></limits、h></malloc、h></ctype、h></string、h>展开阅读全文
咨信网温馨提示：1、咨信平台为文档C2C交易模式，即用户上传的文档直接被用户下载，收益归上传人（含作者）所有；本站仅是提供信息存储空间和展示预览，仅对用户上传内容的表现方式做保护处理，对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿，我们不确定上传用户享有完全著作权，根据《信息网络传播权保护条例》，如果侵犯了您的版权、权益或隐私，请联系我们，核实后会尽快下架及时删除，并可随时和客服了解处理情况，尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确)，网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据，个别因单元格分列造成显示页码不一将协商解决，平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺，下载前须认真查看，确认无误后再购买，务必慎重购买；若有违法违纪将进行移交司法处理，若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传，付费前请自行鉴别，如您付费，意味着您已接受本站规则且自行承担风险，本站不进行额外附加服务，虚拟产品一经售出概不退款（未进行购买下载可退充值款），文档一经付费（服务费）、不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印，是因预览和防盗链等技术需要对页面进行转换压缩成图而已，我们并不对上传的文档进行任何编辑或修改，文档下载后都不会有水印标识（原文档上传前个别存留的除外），下载后原文更清晰；试题试卷类文档，如果标题没有明确说明有答案则都视为没有答案，请知晓；PPT和DOC文档可被视为“模板”，允许上传人保留章节、目录结构的情况下删减部份的内容；PDF文档不管是原文档转换或图片扫描而得，本站不作要求视为允许，下载前可先查看【教您几个在下载文档中可以更好的避免被坑】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用；网站提供的党政主题相关内容(国旗、国徽、党徽－－等)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
6、文档遇到问题，请及时联系平台进行协调解决，联系【微信客服】、【QQ客服】，若有其他问题请点击或扫码反馈【服务填表】；文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“【版权申诉】”，意见反馈和侵权处理邮箱：1219186828@qq.com；也可以拔打客服电话：0574-28810668；投诉电话：18658249818。
实名认证
平台协调中心【客服】
自信AI助手
微信客服
客服QQ
发送邮件
意见反馈
链接地址：https://www.zixin.com.cn/doc/4373672.html