《2022年2022年链表及其应用 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年链表及其应用 .pdf（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、wilyes11 收集博客 (与学习无关 )：http:/ 1、选择合适的存储结构，完成链表的建立，并设计链表的基本操作； 2、运用直接插入法完成建立有序链表，并在此基础上实现链表的连接合并、有序合并等操作； 3、完成链表的并、交、差等集合运算； 4、采用链式存储结构完成多项式的加法和乘法运算。三、测试数据 1、链表的合并链表的直接合并：1,3,5,7,9和2,5,6,8,9,16链表的有序合并：1,3,5,7,9和2,5,6,8,9,16 2、链表的集合运算（交、并、差）集合 1：1,3,5,7,9 集合 2：2,5,6,8,9,16 3、多项式的加法和乘法：1) 多项式的加法多项式 1：1
2、10205710 xxx多项式 2：257510100 xxx2) 多项式的乘法：多项式 1：1251035xxx多项式 2：12x四、算法思想选择链式存储结构，先完成链表的基本操作，再完成链表的多种集合运算，以及链表的排序与合并等操作，并利用链表完成多项式的加法和乘法运算。链表的直接合并：先将链表L1 复制到链表L 中，再依次将L2 中的元素添加到L 中。链表的有序合并：先将链表L1 复制到链表L 中，再依次将L2 中的元素有序添加到L 中。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -
3、- 第 1 页，共 19 页 - - - - - - - - - wilyes11 收集博客 (与学习无关 )：http:/ 中与 L1 中不同的元素插入L2 中；链表的交运算：先取L1 中的一个元素，遍历L2，把与其相同的元素添加到新链表中，直到遍历完L1 中元素；链表的差运算：先取L1 中的一个元素，遍历L2，把与其相同的元素从L1 中删去，直到遍历完L1中元素。多项式加法：两个一元多项式其中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别复制到多项式中去。多项式乘法：两个多项式相乘时，只要第一个多项式的每一项的系数乘
4、以第二个多项式每一项的系数，指数加上第二个多项式的指数。可以得到新的多项式。然后遍历这个多项式并按照指数相同的项进行相加，合并成一个多项式即可。五、模块划分1、选择合适的存储结构，完成链表的建立，并设计链表的基本操作 2、以下函数用于完成链表的基本操作 1)void InitList(LinkList *L)，初始化链表。2)void DestroyList(LinkList *L)，销毁链表。3)void ClearList(LinkList *L)，清空链表。4)int ListEmpty(LinkList L) ，判断链表是否为空。若为空，则返回1；反之，则返回0。5)int ListL
5、ength(LinkList L)，求链表的长度。6)void GetElem(LinkList L, int i, ElemType *e)，取链表中第i 个元素。7)LinkList LocateElem(LinkList L,ElemType e)，在表中查找指定元素，并返回其指针。8)void ListInsert(LinkList *L, int n, ElemType e)，在链表中的指定位置插入指定元素。9)void DeleteRepElem(LinkList *L)，删除链表中的重复元素。10)void ListTraverse(LinkList L)，遍历链表并输出。11)
6、void Deletex(LinkList *L, ElemType x)，删除链表中指定值的所有元素。12)void Copy(LinkList La,LinkList *Lb)，将一个链表复制到另个一个链表中。3、 链表的并、交、差等集合运算；直接插入法完成建立有序链表（输入的是无序数据，得到的是有序链表） ，并在此基础上实现链表的连接合并、有序合并等操作1）void CreateList1(LinkList *L, ElemType a, int n)，插入法建立有序链表。2）void CreateList2(LinkList *L, ElemType a, int n)，后接法建立有序
7、链表。 3）void Union1(LinkList La, LinkList Lb,LinkList *L)，链表的直接合并。 4）void Union2(LinkList La, LinkList Lb, LinkList *L)，有序链表允许重复元素的有序合并。 5）void Union(LinkList *La, LinkList Lb)，链表的并运算。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 19 页 - - - - - - - - - wilyes11
8、收集博客 (与学习无关 )：http:/ 6）void intersection(LinkList La,LinkList Lb,LinkList *L)，链表的交运算。 7）.void differenceset(LinkList La,LinkList Lb,LinkList *L)，链表的差运算。4、多项式的加法和乘法 1）int sort_list(List* list)，链表排序，幂数相同的项，系数合并。 2）int add_poly(List* dest, List* src)，多项式加法运算，结果保存在dest 链表中。 3）int mul_poly(List* dest, Li
9、st* src) ，多项式相乘运算，结果保存在dest 链表中。4）int main()，主函数。六、数据结构 /(ADT) 1 、链表的存储结构： typedef struct LNode ElemType data;/数据 struct LNode *next;/下一个节点 LNode,*LinkList; 2、多项式的存储结构： typedef struct polynomiallist int factor;/系数 int power;/幂 struct polynomiallist* next;/下一节点 List; 七、源程序#includestdio.h #includestdl
10、ib.h #define LIST_OK 0 #define LIST_ERROR -1 typedef int Status; typedef int ElemType; /* 链表的存储结构 */ typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList; / 链表实现多项式加法和乘法typedef struct polynomiallist int factor;/系数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - -
11、- - - - - 第 3 页，共 19 页 - - - - - - - - - wilyes11 收集博客 (与学习无关 )：http:/ int power;/幂 struct polynomiallist* next;/下一节点List; /* 1.初始化链表 */ void InitList(LinkList *L) *L=(LinkList)malloc(sizeof(LNode); (*L)-next=NULL; /* 2.销毁链表 */ void DestroyList(LinkList *L) LinkList p; while(*L!=NULL) p=*L; *L=(*L)-
12、next; free(p); /* 3.清空链表 */ void ClearList(LinkList *L) LinkList p; p=(*L)-next; while(p!=NULL) (*L)-next=p-next; free(p); p=(*L)-next; /* 4.判断链表是否为空 */ int ListEmpty(LinkList L) if (L-next=NULL) return 1; else return 0; /* 5.求链表的长度 */ int ListLength(LinkList L) LinkList p; int n=0; p=L-next; while
13、(p!=NULL) n+; p=p-next; return n; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 19 页 - - - - - - - - - wilyes11 收集博客 (与学习无关 )：http:/ 6.取链表中第i 个元素 */ void GetElem(LinkList L, int i, ElemType *e) LinkList p; int j=1; p=L-next; while (p!=NULL & jnext; j+; *e=p-da
14、ta; /* 7.在链表中查找元素 */ LinkList LocateElem(LinkList L,ElemType e) LinkList p; p=L-next; while (p!=NULL & p-data!=e) p=p-next; return p; /* 8.在顺序表第n 个位置插入元素e */ void ListInsert(LinkList *L, int n, ElemType e) LinkList p,q,t; int i; q=*L; p=(*L)-next; i=1; while (p!=NULL & inext; i+; t=(LinkList)malloc(
15、sizeof(LNode); t-data=e; q-next=t; t-next=p; /*9、删除重复元素*/ void DeleteRepElem(LinkList *L) LinkList r,p,q; r=(*L)-next; while (r!=NULL) q=r; p=r-next; while (p!=NULL) if (p-data=r-data) q-next=p-next; free(p); p=q-next; else q=p; p=p-next; r=r-next; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -
16、- - - 名师精心整理 - - - - - - - 第 5 页，共 19 页 - - - - - - - - - wilyes11 收集博客 (与学习无关 )：http:/ */ void ListTraverse(LinkList L) LinkList p; p=L-next; while (p!=NULL) printf(%dt,p-data); p=p-next; /*10.插入法建立有序链表 */ void CreateList1(LinkList *L, ElemType a, int n) LinkList p,q,t; int i; for(i=0; inext; while
17、(p!=NULL & p-datanext; t=(LinkList)malloc(sizeof(LNode); t-data=ai; q-next=t; t-next=p; /* 11、后接法建立顺序链表 */ void CreateList2(LinkList *L, ElemType a, int n) LinkList p,t; int i; p=*L; for(i=0; idata=ai; p-next=t; p=p-next; p-next=NULL; /* 11.删除指定值的所有元素 */ void Deletex(LinkList *L, ElemType x) LinkLis
18、t p,q; q=*L; p=(*L)-next; while (p!=NULL) if (p-data=x) q-next=p-next; free(p); p=q-next; else q=p; p=p-next; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 19 页 - - - - - - - - - wilyes11 收集博客 (与学习无关 )：http:/ /*12.链表的排序 */ LinkList sort(LNode *La) LNode *p,*p1
19、,*p2,*p3; LNode h, t; if (La = NULL) return NULL; h.next=La; p=&h; while (p-next!=NULL) p=p-next; p=p-next=&t; while (p!=h.next) p3=&h; p1=p3-next; p2=p1-next; while (p2!=p) /p指向的是已就序的节点 if (p1-data)(p2-data) p1-next=p2-next; p2-next=p1; p3-next=p2; p3=p2; p2=p1-next; else p3=p1; p1=p2; p2=p2-next;
20、p=p1; while (p-next!=&t) p=p-next; p-next=NULL; return h.next; /*13.复制链表 La 到 Lb*/ void Copy(LinkList La,LinkList *Lb) int i,len; ElemType t; len=ListLength(La); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 19 页 - - - - - - - - - wilyes11 收集博客 (与学习无关 )：http:/
21、 for(i=1;i=len;i+) GetElem(La,i,&t); ListInsert(Lb,i,t); /* 14、 链表的直接合并 */ void Union1(LinkList La, LinkList Lb,LinkList *L) int i,alen,blen; ElemType e; InitList(L); alen=ListLength(La); blen=ListLength(Lb); Copy(La,L); for(i=1; i=blen; i+) GetElem(Lb,i,&e); ListInsert(L,+alen,e); ListTraverse(*L);
22、 /* 15、链表允许重复元素的有序合并 */ void Union2(LinkList La, LinkList Lb, LinkList *L) int i,j,k,alen,blen; ElemType ai,bj; InitList(L); i=j=k=1; alen=ListLength(La); blen=ListLength(Lb); while(i=alen & j=blen) GetElem(La,i,&ai); GetElem(Lb,j,&bj); if (ai=bj) ListInsert(L,k,ai); i+; k+; else ListInsert(L,k,bj);
23、 j+; k+; while(i=alen) GetElem(La,i,&ai); ListInsert(L,k,ai); i+; k+; while(j=blen) GetElem(Lb,j,&bj); ListInsert(L,k,bj); j+; k+; sort(*L); ListTraverse(*L); /* 16.链表的并运算 */ void Union(LinkList *La, LinkList Lb) int i,alen,blen; ElemType e; alen=ListLength(*La); blen=ListLength(Lb); for(i=1; i=blen
24、; i+) GetElem(Lb,i,&e); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 19 页 - - - - - - - - - wilyes11 收集博客 (与学习无关 )：http:/ if (!LocateElem(*La,e) ListInsert(La,+alen,e); /*17.链表的交运算 */ void intersection(LinkList La,LinkList Lb,LinkList *L) int i,j,t,alen,blen;
25、 InitList(L); ElemType e1,e2;t=1; alen=ListLength(La); blen=ListLength(Lb); for(i=1;i=alen;i+) GetElem(La,i,&e1); for(j=1;j=blen;j+) GetElem(Lb,j,&e2); if(e1=e2) ListInsert(L,+t,e1); /*18.链表的差运算 */ void diffrenceset(LinkList La,LinkList Lb,LinkList *L) int i,j,alen,blen; ElemType e1,e2; InitList(L);
26、 alen=ListLength(La); blen=ListLength(Lb); Copy(La,L); for(i=1;i=alen;i+) GetElem(La,i,&e1); for(j=1;jnext=NULL; return LIST_OK; / 向链表中输入节点int insert_node(List* list, List* node) if( list=NULL ) printf(链表还没有初始化，无法插入节点！n); return LIST_ERROR; while( list-next!=NULL ) list=list-next; list-next=(List*)m
27、alloc(sizeof(List); if( list=NULL ) printf(分配内存出错！n); return LIST_ERROR; list=list-next; list-factor=node-factor; list-power=node-power; list-next=NULL; return LIST_OK; / 从链表中删除节点int delete_node(List* list, List* node) List* tmp=NULL; if(list=NULL ) printf(链表还没有初始化，无法删除节点！n); return LIST_ERROR; 名师资料
28、总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 19 页 - - - - - - - - - wilyes11 收集博客 (与学习无关 )：http:/ while(list-next!=NULL ) if（(node-factor=list-next-factor) & (node-power=list-next-power) tmp=list-next; list-next=list-next-next; free(tmp); printf(删除节点成功！n); retur
29、n LIST_OK; list=list-next; printf(没有找到你要删除的节点！n); return LIST_ERROR; / 删除链表int delete_list(List* list) List* tmp=NULL; while( *list!=NULL ) tmp=*list; *list=(*list)-next; free(tmp); return LIST_OK; / 求链表元素个数int list_cnt(List* list) int i=0; if( list=NULL ) return 0; while(list!=NULL ) i+; list=list-
30、next; return i-1;/首个节点不存储数据 / 链表排序，幂数相同的项，系数合并int sort_list(List* list) /标记元素是否排序 int sorted=0; List* node; List*tmp; List* const head=list; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 19 页 - - - - - - - - - wilyes11 收集博客 (与学习无关 )：http:/ if( list=NULL ) pri
31、ntf(链表没有初始化，无法排序！n); return LIST_ERROR; /如果链表中的元素个数小于2 个，就不需要排序 if( list_cnt(list)next; head-next=NULL; while(node!=NULL ) sorted=0; list=head; while(list-next!=NULL ) /如果是幂数相同，则合并系数 if( node-power=list-next-power ) list-next-factor+=node-factor; node=node-next; sorted=1; break; else if(node-powerli
32、st-next-power) tmp=node; node=node-next; tmp-next=list-next; list-next=tmp; sorted=1; break; list=list-next; /如果 node 的幂数最小，插入链表最后 if( sorted=0 ) tmp=node; node=node-next; list-next=tmp; tmp-next=NULL; return LIST_OK; / 多项式加法运算，结果保存在dest 链表中int add_poly(List* dest, List* src) List* head=dest; if( li
33、st_cnt(dest)=0 | list_cnt(*src)=0) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 19 页 - - - - - - - - - wilyes11 收集博客 (与学习无关 )：http:/ printf(无法进行多项式加法运算！n); return LIST_ERROR; while( dest-next!=NULL ) dest=dest-next; dest-next=(*src)-next; /销毁 *src的头节点，并置NULL
34、 free(*src); *src=NULL; sort_list(head); return LIST_OK; / 多项式相乘运算，结果保存在dest 链表中。int mul_poly(List* dest, List* src) List data; /构造新链表存储乘法运算结果 List* pNew=NULL; List* head1=*dest; List* head2=*src; init_list(&pNew); if( list_cnt(*dest)=0 | list_cnt(*src)=0 ) printf(无法进行多项式的乘法运算！n); return LIST_ERROR;
35、 while( (*dest)-next!=NULL ) while( (*src)-next!=NULL ) data.factor=(*dest)-next-factor)*(*src)-next-factor); data.power=(*dest)-next-power)+(*src)-next-power); data.next=NULL; insert_node(pNew, &data); *src=(*src)-next; *src=head2; *dest=(*dest)-next; sort_list(pNew); delete_list(&head1); delete_li
36、st(&head2); *dest=pNew; return LIST_OK; int display_poly(List* list) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 19 页 - - - - - - - - - wilyes11 收集博客 (与学习无关 )：http:/ if( list_cnt(list)=0 ) printf(链表中没有元素，无法输出！n); return LIST_ERROR; if( list-next-power!=0 )
37、printf(%dX%d, list-next-factor, list-next-power); else printf(%d, list-next-factor); list=list-next; while( list-next!=NULL ) if( list-next-factor0 ) if(list-next-power=0 ) printf(+%d, list-next-factor); else printf(+%dX%d, list-next-factor, list-next-power); else if( list-next-factornext-power=0 )
38、if(list-next-factor!=0 ) printf(%d, list-next-factor); else printf(%dX%d, list-next-factor, list-next-power); list=list-next; return LIST_OK; /*链表的操作 */ void listplay() LinkList La,Lb,L1,L2,L3,L4; ElemType a=1,3,5,7,9,b=16,9,8,6,5,2; InitList(&La); InitList(&Lb); InitList(&L1); InitList(&L2); InitLi
39、st(&L3); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 19 页 - - - - - - - - - wilyes11 收集博客 (与学习无关 )：http:/ printf(List La:n); ListTraverse(La); printf(n); CreateList2(&Lb,b,6); printf(List Lb:n); ListTraverse(Lb); printf(n); printf(n直接合并链表 :n); Union1(La,Lb,
40、&L1); printf(n有序合并链表 :n); Union2(La,Lb,&L2); printf(n); intersection(La,Lb,&L3); printf(List LaLb:n); ListTraverse(L3);/*交运算 */ printf(n); diffrenceset(La,Lb,&L4); printf(List La-Lb:n); ListTraverse(L4);/*差运算 */ printf(n); Union(&La,Lb); printf(List LaULb:n); ListTraverse(La);/*并运算 */ /*多项式加法的操作*/ v
41、oid add_poly_play() int n; int i; List data; List* dest=NULL; List* src=NULL; init_list(&dest); init_list(&src); printf(n多项式 1 有多少项： n); scanf(%d,&n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 19 页 - - - - - - - - - wilyes11 收集博客 (与学习无关 )：http:/ printf(请分
42、别输入多项式1 的系数和幂数，中间用空格隔开：n); for( i=0; in; i+) scanf(%d%d, &data.factor, &data.power); insert_node(dest, &data); printf(多项式 2 有多少项： n); scanf(%d,&n); printf(请分别输入多项式2 的系数和幂数，中间用空格隔开：n); for( i=0; in; i+) scanf(%d%d, &data.factor, &data.power); insert_node(src, &data); printf(); display_poly(dest); pri
43、ntf()+(); display_poly(src); printf()=); add_poly(dest, &src); display_poly(dest); printf(n); /*多项式乘法的操作*/ void mul_poly_play() int n; int i; List data; List* dest=NULL; List* src=NULL; init_list(&dest); init_list(&src); printf(n多项式 1 有多少项： n); scanf(%d,&n); printf(请分别输入多项式1 的系数和幂数，中间用空格隔开：n); for(
44、i=0; in; i+) scanf(%d%d, &data.factor, &data.power); insert_node(dest, &data); printf(多项式 2 有多少项： n); scanf(%d,&n); printf(请分别输入多项式2 的系数和幂数，中间用空格隔开：n); for( i=0; in; i+) scanf(%d%d, &data.factor, &data.power); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 19
45、页 - - - - - - - - - wilyes11 收集博客 (与学习无关 )：http:/ insert_node(src, &data); printf(); display_poly(dest); printf()*(); display_poly(src); printf()=); mul_poly(&dest, &src); display_poly(dest); printf(n); /*主菜单 */ void MainMenue() fflush( stdin ); printf(n* Main Menue *n); printf(* *n); printf(* 1. 链表
46、操作 *n); printf(* 2. 多项式加法操作 *n); printf(* 3. 多项式乘法操作 *n); printf(* 4. 退出 *n); printf(* *n); printf(*n); void main() int flag = 1; while ( flag ) MainMenue(); char ch10; printf(Please input your choice(16): ); gets( ch ); switch ( ch0 ) case 1: listplay(); break; case 2: add_poly_play(); break; case
47、3: mul_poly_play(); break; case 4: exit(1); default: printf(Input error!n); break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 19 页 - - - - - - - - - wilyes11 收集博客 (与学习无关 )：http:/ 八、测试情况程序的测试结果如下：对链表的交、并、差、有序合并、直接合并都正确。多项式加法运算正确。多项式乘法运算正确。九、参考文献 1、严蔚敏，数据结构
48、C 语言 ，清华大学出版社。 2、谭浩强，c 语言程序设计，清华大学出版社。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 19 页 - - - - - - - - - wilyes11 收集博客 (与学习无关 )：http:/ 比较简单。 后一部分是应用链表结构实现一元多项式的表示及相加相乘，这部分需要自己思考算法实现，也是我们认为比较难、比较有挑战的部分。而多项式部分主要是编写多项式相加和相乘两个函数，是我们遇到问题比较多的地方。现在完成课程设计，再回头思考这中间所
49、遇到的各种问题，最根本的原因是我们对链表的理解还不够深刻，掌握的还不够熟练，编程能力不足。通过本次课程设计，我们发现考试并不是最重要的，最重要的是能运用所学的知识解决遇到的实际问题；其次，我们完成课程设计过程中学会积极的同团队成员交流，取长补短，共同进步。 “独学而无友则孤陋而寡闻”，只有和同学多交流多学习才能不断的提高自身水平；最后，我们真正体会到什么是团队协作，真正的了解到团队合作的有利之处，真正感受到团队成员为了共同的目标联合在一起时的强大力量。在本次课程设计中，我的主要任务是建立链表、运用直接插入法完成建立有序链表的建立以及对链表直接完成连接合并、有序合并等操作。虽然以前对这些操作不是很了解，但在组长的帮组下我还是顺利地完成了。对于链表的交、并、差运算，我也基本熟悉其操作，但是采用链式存储结构完成多项式的加法和乘法运算比较难，我开始基本不会，后来在我们几个的共同探讨下我对其有了一定的了解。通过这次课程设计，我明白团队合作及分工协作的重要性；当然，我在这次课程设计中收获了很多关于链表应用方面的知识等。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 19 页 - - - - - - - - -