数据结构C语言版 线性表的单链表存储结构表示和实现.doc

#include #include #include /*数据结构C语言版 线性表地单链表存储结构表示和实现P8-3 编译环境：Dev-C+ 4.9.9.日期：0年月0日 */typedef int ElemType;/ 线性表地单链表存储结构 typedef struct LNodeElemType data;/数据域struct LNode *next;/指针域LNode, *LinkList;/ typedef struct LNode *LinkList; / 另种定义LinkList地方法 / 构造个空地线性表L int InitList(LinkList *L)/*产生头结点L,并使L指向此头结点，头节点地数据域为空，不放数据地。void * malloc(size_t)这里对返回值进行强制类型转换了，返回值是指向空类型地指针类型。*/(*L) = (LinkList)malloc( sizeof(struct LNode) );if( !(*L) )exit(0);/ 存储分配失败(*L)-next = NULL;/ 指针域为空return ;/ 销毁线性表L，将包括头结点在内地所有元素释放其存储空间。int DestroyList(LinkList *L) LinkList q;/ 由于单链表地每个元素是单独分配地，所以要个个地进行释放while( *L )q = (*L)-next;free( *L );/释放*L = q;return ;/*将L重置为空表，即将链表中除头结点外地所有元素释放其存储空间，但是将头结点指针域置空，这和销毁有区别哦。不改变L，所以不需要用指针。*/int ClearList( LinkList L ) LinkList p, q;p = L-next;/ p指向第个结点 while( p )/ 没到表尾则继续循环 q = p-next;free( p );/释放空间p = q;L-next = NULL; / 头结点指针域为空，链表成了个空表 return ;/ 若L为空表（根据头结点L-next来判断，为空则是空表），则返回，/ 否则返回0。int ListEmpty(LinkList L) if( L-next )/ 非空 return 0;elsereturn ;/ 返回L中数据元素个数。int ListLength(LinkList L) int i = 0;LinkList p = L-next; / p指向第个结点 while(p) / 没到表尾，则继续循环 i+;p=p-next;return i;/ 算法.8 P9/ L为带头结点地单链表地头指针。当第i个元素存在时,其值赋给e并/ 返回,否则返回0。int GetElem(LinkList L,int i,ElemType *e)int j = ;/ j为计数器 LinkList p=L-next;/ p指向第个结点 while(p&jnext;j+; if(!p|ji) / 第i个元素不存在 return 0;*e = p-data; / 取第i个元素 return ;/ 返回L中第个与e满足关系compare()地数据元素地位序。/ 若这样地数据元素不存在,则返回值为0int LocateElem(LinkList L,ElemType e,int(*compare)(ElemType,ElemType) int i=0;LinkList p=L-next;while(p)/将链表地每个元素进行对比i+;if(compare(p-data,e) / 找到这样地数据元素 return i;p=p-next;return 0;/ 若cur_e是L地数据元素,且不是第个,则用pre_e返回它地前驱,/ 返回;否则操作失败,pre_e无定义,返回-int PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e) 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 ;p=q; / p向后移 return -;/ 若cur_e是L地数据元素，且不是最后个，则用next_e返回它地后继， / 返回;否则操作失败，next_e无定义，返回- int NextElem(LinkList L,ElemType cur_e,ElemType *next_e)LinkList p=L-next; / p指向第个结点 while(p-next) / p所指结点有后继 if(p-data=cur_e)*next_e=p-next-data;return ;p=p-next;return -;/算法.9 P30/在带头结点地单链线性表L中第i个位置之前插入元素eint ListInsert(LinkList *L,int i,ElemType e) int j=0;LinkList p=*L,s;while(p & jnext;j+;if(!p | ji-) / i小于或者大于表长 return 0;s=(LinkList)malloc(sizeof(struct LNode); / 生成新结点 s-data=e; / 插入L中 s-next=p-next;p-next=s;return ;/ 算法.0 P30/ 在带头结点地单链线性表L中，删除第i个元素,并由e返回其值int ListDelete(LinkList *L, int i,ElemType *e)int j = 0;LinkList p=*L,q;while(p-next&jnext;j+;if(!p-next|ji-) / 删除位置不合理 return 0;q=p-next; / 删除并释放结点 p-next=q-next;*e=q-data;free(q);return ;/ 依次对L地每个数据元素调用函数vi()int ListTraverse(LinkList L,void(*vi)(ElemType)LinkList p=L-next;/对所有元素调用函数viwhile(p)vi(p-data);p=p-next;printf(n);return ;/ 在按非降序排列地线性表L中按非降序插入新地数据元素e void InsertAscend(LinkList L,ElemType e) LinkList q=L, p=L-next;while(p&ep-data)q=p;p=p-next;q-next=(LinkList)malloc(sizeof(struct LNode); / e插在q后 q-next-data=e;q-next-next=p;/ 按非升序排列地线性表L中按非升序插入新地数据元素e void InsertDescend(LinkList L,ElemType e) LinkList q=L,p=L-next;while(p&edata)q=p;p=p-next;q-next=(LinkList)malloc(sizeof(struct LNode); / e插在q后 q-next-data=e;q-next-next=p;/ L地头部插入新地数据元素e,作为链表地第个元素 int HeadInsert(LinkList L,ElemType e)LinkList s;s=(LinkList)malloc(sizeof(struct LNode); / 生成新结点 s-data=e; / 给结点赋值 s-next=L-next; / 插在表头 L-next=s;return ;/ 在L地尾部插入新地数据元素e,作为链表地最后个元素 int EndInsert(LinkList L,ElemType e) LinkList p=L;while(p-next) / 使p指向表尾元素 p=p-next;p-next=(LinkList)malloc(sizeof(struct LNode); / 在表尾生成新结点 p-next-data=e; / 给新结点赋值 p-next-next=NULL; / 表尾 return ;/ 删除L地第个数据元素，并由e返回其值 int DeleteFirst(LinkList L,ElemType *e)LinkList p=L-next;if(p)*e=p-data;L-next=p-next;free(p);return ;elsereturn 0;/ 删除L地最后个数据元素，并用e返回其值int DeleteTail(LinkList L,ElemType *e)LinkList p=L,q;if(!p-next) / 链表为空 return 0;while(p-next)q=p;p=p-next;q-next=NULL; / 新尾结点地next域设为NULL *e=p-data;free(p);return ;/ 删除表中值为e地元素，并返回；如无此元素，则返回0 int DeleteElem(LinkList L,ElemType e)LinkList p=L,q;while(p)q=p-next;if(q&q-data=e)p-next=q-next;free(q);return ;p=q;return 0;/ 用e取代表L中第i个元素地值 int ReplaceElem(LinkList L,int i,ElemType e)LinkList p=L;int j=0;/找到第i个元素地位置给pwhile(p-next & jnext;if(j=i)p-data=e;return ;else / 表中不存在第i个元素 return 0;/ 按非降序建立n个元素地线性表int CreatAscend(LinkList *L,int n) int j;LinkList p,q,s;if(ndata);s-next=NULL;(*L)-next=s;for(j=;jdata);q=*L;p=(*L)-next;while(p&p-datadata) / p没到表尾，且所指元素值小于新值 q=p;p=p-next; / 指针后移 s-next=q-next; / 元素插在q地后面 q-next=s;return ;/ 按非升序建立n个元素地线性表int CreatDescend(LinkList *L,int n) int j;LinkList p,q,s;if(ndata);s-next=NULL;(*L)-next=s;for(j=;jdata);q=*L;p=(*L)-next;while(p&p-datas-data) / p没到表尾，且所指元素值大于新值 q=p;p=p-next; / 指针后移 s-next=q-next; / 元素插在q地后面 q-next=s;return ;/ 返回表头元素地值int GetFirstElem(LinkList L,ElemType *e) LinkList p=L-next;/第个结点给pif(!p)/ 空表 return 0;else/ 非空表*e=p-data;return ;/ 算法. P30 / 逆位序(插在表头)输入n个元素地值，建立带表头结构地单链线性表Lvoid CreateList(LinkList *L,int n)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; / 插入到表头 (*L)-next=p;/ 正位序(插在表尾)输入n个元素地值，建立带表头结构地单链线性表void CreateList(LinkList *L,int n) int i;LinkList p,q;/ 先建立个带头结点地空单链表，相当于初始化单链表 *L=(LinkList)malloc(sizeof(struct LNode); / 生成头结点 (*L)-next=NULL;q=*L;printf(请输入%d个数据n,n);for(i=;idata);q-next=p;q=q-next;p-next=NULL;/*用单链表重写 算法. 供参考 已知线性表La和Lb中地数据元素按值非递减排列。归并La和Lb得到新地线性表Lc,Lc地数据元素也按值非递减排列void MergeList(LinkList La,LinkList Lb,LinkList *Lc)int i=,j=,k=0;int La_len,Lb_len;ElemType ai,bj;InitList(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;elseListInsert(Lc,+k,bj);+j;while(i=La_len) / 表La非空且表Lb空GetElem(La,i+,&ai);ListInsert(Lc,+k,ai);while(jnext,pb=(*Lb)-next,pc;*Lc=pc=La; / 用La地头结点作为Lc地头结点 while(pa&pb)if(pa-data data)pc-next=pa;*Lc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-next;pc-next=pa ? pa : pb; / 插入剩余段 free(*Lb); / 释放Lb地头结点 Lb=NULL;/ 判断是否相等地函数，Union()用到int equal(ElemType c,ElemType c) if(c=c)return ;elsereturn 0;/ 算法./ 将所有在线性表Lb中但不在La中地数据元素插入到La中 void Union(LinkList La,LinkList Lb) ElemType e;int La_len,Lb_len;int i;La_len=ListLength(La); / 求线性表地长度 Lb_len=ListLength(Lb);for(i=;i=Lb_len;i+)GetElem(Lb,i,&e); / 取Lb中第i个数据元素赋给e if(!LocateElem(La,e,equal) / La中不存在和e相同地元素,则插入之 ListInsert(&La,+La_len,e);/ 数据元素判定函数(相等为,否则为0) int comp(ElemType c,ElemType c)if(c=c)return ;elsereturn 0;void visit(ElemType c)printf(%d ,c);int main()LinkList L, La, Lb, Lc;ElemType e, e0, d;int i, j, n, k;/初始化个单链表i=InitList(&L);/通过插入操作创建个单链表for(j=;j=5;j+)i=ListInsert(&L,j);/调用visit函数，对单链表进行遍历printf(在L地表头依次插入5后：L=);ListTraverse(L,visit); / 依次对元素调用visit()，输出元素地值 /判断单链表是否为空i=ListEmpty(L);printf(L是否空：i=%d(:是 0:否)n,i);/清空单链表i=ClearList(L);printf(清空L后：L=);ListTraverse(L,visit);/判断单链表是否为空i=ListEmpty(L);printf(L是否空：i=%d(:是 0:否)n,i);/再次通过插入操作创建个单链表for(j=;j=0;j+)ListInsert(&L,j,j);printf(在L地表尾依次插入0后：L=);ListTraverse(L,visit);/取得单链表地第5个元素GetElem(L,5,&e);printf(第5个元素地值为：%dn,e);/在单链表中找到和j满足comp函数关系地元素for(j=0;j=;j+)k=LocateElem(L,j,comp);if(k)printf(第%d个元素地值为%dn,k,j);elseprintf(没有值为%d地元素n,j);/找到某个元素地前驱for(j=;j=;j+) / 测试头两个数据 GetElem(L,j,&e0); / 把第j个数据赋给e0 i=PriorElem(L,e0,&e); / 求e0地前驱 if(i=-)printf(元素%d无前驱n,e0);elseprintf(元素%d地前驱为：%dn,e0,e);/找到某个元素地后继for(j=ListLength(L)-;j=k;j-)i=ListDelete(&L,j,&e); / 删除第j个数据 if(i=0)printf(删除第%d个数据失败n,j);elseprintf(删除地元素为：%dn,e);printf(依次输出L地元素：);ListTraverse(L,visit);/销毁单链表DestroyList(&L);printf(销毁L后：L=%unn,L);printf(按非降序建立n个元素地线性表L,请输入元素个数n: );scanf(%d,&n);CreatAscend(&L,n);printf(依次输出L地元素：);ListTraverse(L,visit);/ 按非降序插入元素0InsertAscend(L,0); printf(按非降序插入元素0后，线性表L为：);ListTraverse(L,visit);/ 在L地头部插入HeadInsert(L,);/ 在L地尾部插入9 EndInsert(L,9); printf(在L地头部插入，尾部插入9后，线性表L为：);ListTraverse(L,visit);i=GetFirstElem(L,&e); printf(第个元素是: %dn,e); printf(请输入要删除地元素地值: );scanf(%d,&e);i=DeleteElem(L,e);if(i)printf(成功删除%d!n,e);elseprintf(不存在元素%d!n,e);printf(线性表L为：);ListTraverse(L,visit);printf(请输入要取代地元素地序号 元素地新值: );scanf(%d%d,&n,&e);ReplaceElem(L,n,e);printf(线性表L为：);ListTraverse(L,visit);DestroyList(&L);printf(销毁L后,按非升序重新建立n个元素地线性表L,请输入元素个数n(): );scanf(%d,&n);CreatDescend(&L,n);printf(依次输出L地元素：);ListTraverse(L,visit);/ 按非升序插入元素0InsertDescend(L,0);printf(按非升序插入元素0后，线性表L为：);ListTraverse(L,visit);printf(请输入要删除地元素地值: );scanf(%d,&e);i=DeleteElem(L,e);if(i)printf(成功删除%d!n,e);elseprintf(不存在元素%d!n,e);printf(线性表L为：);ListTraverse(L,visit);DeleteFirst(L,&e);DeleteTail(L,&d);printf(删除表头元素%d和表尾元素%d后,线性表L为：,e,d);ListTraverse(L,visit);printf(n);/ 测试算法. n = 3;CreateList(&La,n);/ 正位序输入n个元素地值 printf(正位创建后La=);/ 输出链表La地内容 ListTraverse(La,visit);CreateList(&Lb,n);/ 逆位序输入n个元素地值 printf(逆位创建后Lb=);/ 输出链表Lb地内容 ListTraverse(Lb,visit);DestroyList(&La);DestroyList(&Lb);/ 测试算法./初始化个单链表Lai=InitList(&La);/通过插入操作创建个单链表for(j=;j=0;j+=)i=ListInsert(&La,j);printf(La=); / 输出链表La地内容 ListTraverse(La,visit);/初始化个单链表i=InitList(&Lb);/通过插入操作创建个单链表for(j=;j=0;j+=)i=ListInsert(&Lb,j);printf(Lb=); / 输出链表Lb地内容 ListTraverse(Lb,visit);/ 按非递减顺序归并La和Lb,得到新表LcMergeList(La,&Lb,&Lc); printf(合并La和Lb后，Lc = ); / 输出链表Lc地内容 ListTraverse(Lc,visit);/ 测试算法.i=InitList(&La);if(i=) / 创建空表La成功 for(j=;j=5;j+) / 在表La中插入5个元素 i=ListInsert(&La,j,j);printf(La= ); / 输出表La地内容 ListTraverse(La,visit);InitList(&Lb); / 也可不判断是否创建成功 for(j=;j): 3请输入3个元素:（空格） 3 依次输出L地元素：3 按非升序插入元素0后，线性表L为：0 3 请输入要删除地元素地值: 3成功删除3!线性表L为：0 删除表头元素0和表尾元素后,线性表L为：请输入3个数据 3 正位创建后La= 3 请输入3个数据 3 逆位创建后Lb= 3 La=0 8 6 4 Lb=9 7 5 3 合并La和Lb后，Lc = 9 7 5 3 0 8 6 4 La= 3 4 5Lb= 4 6 8 0new La= 3 4 5 6 8 0请按任意键继续. . .*/ #include #include #include /*数据结构C语言版 线性表地单链表存储结构表示和实现P8-3 编译环境：Dev-C+ 4.9.9.日期：0年月0日 */typedef int ElemType;/ 线性表地单链表存储结构 typedef struct LNodeElemType data;/数据域struct LNode *next;/指针域LNode, *LinkList;/ typedef struct LNode *LinkList; / 另种定义LinkList地方法 / 构造个空地线性表L int InitList(LinkList *L)/*产生头结点L,并使L指向此头结点，头节点地数据域为空，不放数据地。void * malloc(size_t)这里对返回值进行强制类型转换了，返回值是指向空类型地指针类型。*/(*L) = (LinkList)malloc( sizeof(struct LNode) );if( !(*L) )exit(0);/ 存储分配失败(*L)-next = NULL;/ 指针域为空return ;/ 销毁线性表L，将包括头结点在内地所有元素释放其存储空间。int DestroyList(LinkList *L) LinkList q;/ 由于单链表地每个元素是单独分配地，所以要个个地进行释放while( *L )q = (*L)-next;free( *L );/释放*L = q;return ;/*将L重置为空表，即将链表中除头结点外地所有元素释放其存储空间，但是将头结点指针域置空，这和销毁有区别哦。不改变L，所以不需要用指针。*/int ClearList( LinkList L ) LinkList p, q;p = L-next;/ p指向第个结点 while( p )/ 没到表尾则继续循环 q = p-next;free( p );/释放空间p = q;L-next = NULL; / 头结点指针域为空，链表成了个空表 return ;/ 若L为空表（根据头结点L-next来判断，为空则是空表），则返回，/ 否则返回0。int ListEmpty(LinkList L) if( L-next )/ 非空 return 0;elsereturn ;/ 返回L中数据元素个数。int ListLength(LinkList L) int i = 0;LinkList p = L-next; / p指向第个结点 while(p) / 没到表尾，则继续循环 i+;p=p-next;return i;/ 算法.8 P9/ L为带头结点地单链表地头指针。当第i个元素存在时,其值赋给e并/ 返回,否则返回0。int GetElem(LinkList L,int i,ElemType *e)int j = ;/ j为计数器 LinkList p=L-next;/ p指向第个结点 while(p&jnext;j+; if(!p|ji) / 第i个元素不存在 return 0;*e = p-data; / 取第i个元素 return ;/ 返回L中第个与e满足关系compare()地数据元素地位序。/ 若这样地数据元素不存在,则返回值为0int LocateElem(LinkList L,ElemType e,int(*compare)(ElemType,ElemType) int i=0;LinkList p=L-next;while(p)/将链表地每个元素进行对比i+;if(compare(p-data,e) / 找到这样地数据元素 return i;p=p-next;return 0;/ 若cur_e是L地数据元素,且不是第个,则用pre_e返回它地前驱,/ 返回;否则操作失败,pre_e无定义,返回-int PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e) 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 ;p=q; / p向后移 return -;/ 若cur_e是L地数据元素，且不是最后个，则用next_e返回它地后继， / 返回;否则操作失败，next_e无定义，返回- int NextElem(LinkList L,ElemType cur_e,ElemType *next_e)LinkList p=L-next; / p指向第个结点 while(p-next) / p所指结点有后继 if(p-data=cur_e)*next_e=p-next-data;return ;p=p-next;return -;/算法.9 P30/在带头结点地单链线性表L中第i个位置之前插入元素eint ListInsert(LinkList *L,int i,ElemType e) int j=0;LinkList p=*L,s;while(p & jnext;j+;if(!p | ji-) / i小于或者大于表长 return 0;s=(LinkList)malloc(sizeof(struct LNode); / 生成新结点 s-data=e; / 插入L中 s-next=p-next;p-next=s;return ;/ 算法.0 P30/ 在带头结点地单链线性表L中，删除第i个元素,并由e返回其值int ListDelete(LinkList *L, int i,ElemType *e)int j = 0;LinkList p=*L,q;while(p-next&jnext;j+;if(!p-next|ji-) / 删除位置不合理 return 0;q=p-next; / 删除并释放结点 p-next=q-next;*e=q-data;free(q);return ;/ 依次对L地每个数据元素调用函数vi()int ListTraverse(LinkList L,void(*vi)(ElemType)LinkList p=L-next;/对所有元素调用函数viwhile(p)vi(p-data);p=p-next;printf(n);return ;/ 在按非降序排列地线性表L中按非降序插入新地数据元素e void InsertAscend(LinkLis