数据结构单链表课程设计设计报告.docx
- 文档编号:4077422
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:35
- 大小:23.41KB
数据结构单链表课程设计设计报告.docx
《数据结构单链表课程设计设计报告.docx》由会员分享,可在线阅读,更多相关《数据结构单链表课程设计设计报告.docx(35页珍藏版)》请在冰点文库上搜索。
数据结构单链表课程设计设计报告
《数据结构》课程设计报告
1)需求分析
此程序主要用来实现单链表的创建、插入、删除、排序、并、交、差运算及输出等基本操作。
程序需要根据使用者的需要来运算得出符合要求的结果
①在程序运行的过程中根据提示进行输入,使用了scanf函数;
②使用了printf函数进行输出;
③程序输出符合使用者的需要的结果;
④程序能够输出任意运算的正确结果。
2)概要设计
1.定义所需的数据结构
data*next
typedefstructLNode{
//数据域intdata;
//structLNode*next;指针域}LNode,*LinkList;
2.模块划分//创建voidLinkListCreat(LinkList&L,intn);
//voidListInsert(LinkListhead,inti,inte);插入
voidListDelete(LinkListhead,inti,inte);//删除输出//voidprintList(LinkList&head);
voidLinkListsort(LinkList&L);排序//
//&Lc);&Lb,LinkList&La,LinkListMerge(LinkListvoidLinkList
并voidLinkListJiao(LinkList&La,LinkList&Lb,LinkList&Lc);交//1
//&La,LinkList&Lb,LinkList&Lc);voidLinkListcha(LinkList
差//差集的并voidLinkListhebing(LinkList&La,LinkList&Lb,LinkList&Lc);
主函数,分别调用以上的子函数//voidmain();
3.功能设计
首先利用元素逆序插入法建立链表,然后导出菜单,用switch调用各个子函数,实现链表的创建,插入,删除,排序,交,并,差等运算,其中排序用的是冒泡法。
3)详细设计
//单链表的创建
voidCreatList(Lnode*L)/*建立链表CreastList函数*/
{Lnode*p;
intvalue;
L->next=NULL;
while
(1)/*当输入非0数值时*/
{scanf(%d,&value);
if(value==NULL)
return;
p=(Lnode*)malloc(sizeof(Lnode));/*建立P链表*/
p->data=value;
p->next=L->next;/*把后输入的插到前面*/
L->next=p;
}
}
//单链表的输出
voidprintList(Lnode*head)
{
牰湩晴尨输出的结果如下:
\n);
Lnode*p=head->next;//头结点赋给P
if(p==NULL)
{
printf(Listisempty!
\n);
return;
2
}
while(p!
=NULL)
{
printf(%d,p->data);
p=p->next;
}
printf(\
);
}
//单链表的插入
voidListInsert(LinkListhead,inti,inte)//在单链表中第i个位置之前插入e元素
{
LinkListp,s;
intj=0;
p=head;
while(p&&j { p=p->next; ++j; } if(! p||j>i-1) { );牰湩晴尨要插入的位置错误! } 给插入的元素开辟空间s=(LNode*)malloc(sizeof(LNode));//改变指针指向s->data=e;//s->next=p->next; p->next=s; } //单链表的删除 intListDelete_L(Lnode*L,inti)/*删除函数*/ 3 { Lnode*p=L->next; intj=0; Lnode*q; while(p->next&&j if(! p->next||j>i-1)return0; q=p->next; p->next=q->next; free(q); return1; } //单链表的差运算 Lnode*c,*a,*t; c=C=(Lnode*)malloc(sizeof(Lnode)); a=A->next; while(a) { p=B->next; while(p&&a->data! =p->data) { p=p->next; } if(! (p&&p->data==a->data)) { t=(Lnode*)malloc(sizeof(Lnode)); t->data=a->data; c->next=t; c=t; } a=a->next; } c->next=NULL; printf(\n进行差运算,结果为: \n); printList(C); C=(Lnode*)malloc(sizeof(Lnode));/*必须再分配一次地址空间以用来把原链表清空,否则每次运行都会使链表元素增加*/ 4 break; //单链表的交运算 Lnode*d; d=D=(Lnode*)malloc(sizeof(Lnode)); a=A->next; while(a) { p=B->next; while(p&&a->data! =p->data) { p=p->next; } if(p&&p->data==a->data) { t=(Lnode*)malloc(sizeof(Lnode)); t->data=a->data; d->next=t; d=t; } a=a->next; } d->next=NULL; printf(\n进行差运算,结果为: \n); printList(D); D=(Lnode*)malloc(sizeof(Lnode)); break; 单链表的并运算//Lnode*e; a=A->next; p=B->next; 的头的头结点作为用e=E=A;//LaLc结点while(a&&p) { pa->data if(a->datap->data)//<=如果5 <=pb->data,将pa所指节点链接到pc所指节点之后 { e->next=a; e=a; a=a->next; } else//否则将pb所指节点链接到pc所指节点之后 { e->next=p; e=p; p=p->next; } } e->next=a? a: p;//插入剩余段 free(B);//释放Lb printList(E); E=(Lnode*)malloc(sizeof(Lnode)); break; //主函数 main() { intsign,sign1,signa,signb,signc,i,x,ca,cb,cc; intchoice=1; Lnode*A,*B,*C,*D,*E,*L,*p,*q,*n,*m; A=(Lnode*)malloc(sizeof(Lnode));/*开辟地址空间*/ B=(Lnode*)malloc(sizeof(Lnode)); C=(Lnode*)malloc(sizeof(Lnode)); D=(Lnode*)malloc(sizeof(Lnode)); E=(Lnode*)malloc(sizeof(Lnode)); printf(\《数据结构课程设计--单链表的基本操作》\n\n); while(choice) { printf(\请选择您想进行的操作: \n1: 对A链表操作\n2: 对B链表操作\n3: 两链表运算\n4: 退出程序\n\n您的选择是: ); 6 scanf(%d,&sign1);/*输入选项*/ if(sign1==1)/*如果选择1则输出下列选项界面*/ {L=A;/*选择1对链表A进行操作*/ ca=1; while(ca) { printf(\请选择对A链表进行的操作: \n1: 建立链表\n 2: 对链表排序\n3: 在链表中插入元素\n4: 在链表中删除元素\n5: 返回上一级菜单\n您的选择是: ); scanf(%d,&signa);/*输入对链表A的操作选项*/ switch(signa) { case1: printf(\ 请输入链表元素(输入去0结束)\n); CreatList(A); /*调用CreatList函数*/ PrintList(A); /*调用PrintList函数*/ break; case2: 牰湩晴尨对A链表进行排序,结果为: \n); paixu(A); /*调用排序函数*/ PrintList(A); /*调用PrintList函数*/ break; case3: 牰湩晴尨请输入想要插入的位置及插入的数值(以逗号分隔): ); scanf(%d,%d,&i,&x); if(ListInsert_L(L,i,x)==1) 灻楲瑮? 修改成功! 目前A链表为: \n); PrintList(L);} else 牰湩晴尨警告! 您输入的插入位置超过链表长度。 \n); break; 7 case4: 牰湩晴尨请输入想要删除的元素位置: ); scanf(%d,&i); if(ListDelete_L(L,i)==1) 灻楲瑮? 删除元素成功! 目前A链表为: \n); PrintList(L);} else 牰湩晴尨警告! 您输入的删除位置超过链表长度。 \n); break; case5: ca=0; break; default: 牰湩晴尨警告! 只能选择1-5。 \n); break; } } } elseif(sign1==2) {L=B; cb=1; while(cb) {printf(\请选择对B链表进行的操作: \n1: 建立链表\n 2: 对链表排序\n3: 在链表中插入元素\n4: 在链表中删除元素\n5: 返回上一级菜单\n您的选择是: ); scanf(%d,&signb); switch(signb) { case1: printf(\ 请输入链表元素(输入0结束)\n); CreatList(B); PrintList(B); break; case2: 牰湩晴尨对B链表进行排序,结果为: \n); 8 paixu(B); PrintList(B); break; case3: 牰湩晴尨请输入想要插入的位置及插入的数值(以逗号分隔): ); scanf(%d,%d,&i,&x); if(ListInsert_L(L,i,x)==1) 灻楲瑮? 修改成功! 目前B链表为: \n); PrintList(L);} else 牰湩晴尨警告! 您输入的插入位置超过链表长度。 \n); break; case4: 牰湩晴尨请输入想要删除的元素位置: ); scanf(%d,&i); if(ListDelete_L(L,i)==1) 灻楲瑮? 删除元素成功! 目前B链表为: \n); PrintList(L);} else 牰湩晴尨警告! 您输入的删除位置超过链表长度。 \n); break; case5: cb=0; break; default: 牰湩晴尨警告! 只能选择1-5。 \n); break; } } } elseif(sign1==3) {cc=1; while(cc) 9 {printf(\请选择操作的名称: \n1: 显示当前的A、B链表\n2: 进行差运算\n3: 进行交运算\n4: 进行并运算\n5: 返回上一级菜单\n您的选择是: ); scanf(%d,&signc); switch(signc) { case1: printf(\n当前A); PrintList(A); printf(\n当前B); PrintList(B); break; case2: Lnode*c,*a,*t; c=C=(Lnode*)malloc(sizeof(Lnode)); a=A->next; while(a) { p=B->next; while(p&&a->data! =p->data) { p=p->next; } if(! (p&&p->data==a->data)) { t=(Lnode*)malloc(sizeof(Lnode)); t->data=a->data; c->next=t; c=t; } a=a->next; } c->next=NULL; printf(\n进行差运算,结果为: \n); printList(C); C=(Lnode*)malloc(sizeof(Lnode));/*必须再分配一次地址空间以用来把原链表清空,否则每次运行都会使链表元素增加*/ 10 break; case3: Lnode*d; d=D=(Lnode*)malloc(sizeof(Lnode)); a=A->next; while(a) { p=B->next; while(p&&a->data! =p->data) { p=p->next; } if(p&&p->data==a->data) { t=(Lnode*)malloc(sizeof(Lnode)); t->data=a->data; d->next=t; d=t; } a=a->next; } d->next=NULL; printf(\n进行差运算,结果为: \n); printList(D); D=(Lnode*)malloc(sizeof(Lnode)); break; case4: Lnode*e; a=A->next; p=B->next; e=E=A;//用La的头结点作为Lc的头结点 while(a&&p) { if(a->data<=p->data)//如果pa->data <=pb->data,将pa所指节点链接到pc所指节点之后 { e->next=a; 11 e=a; a=a->next; } else//否则将pb所指节点链接到pc所指节点之后 { e->next=p; e=p; p=p->next; } } e->next=a? a: p;//插入剩余段 Lbfree(B);//释放 printList(E); E=(Lnode*)malloc(sizeof(Lnode)); break; case5: cc=0; break; default: \n);1-5。 牰湩晴尨警告! 只能选择 break; } } } elseif(sign1==4) { ! \n);牰湩晴尨谢谢使用,请按任意键退出 break; } else \n);1-4之间选择! 仅能在灻楲瑮? 提示: break; } } return0; 12 } 4.流程图 图1-1单链表基本操作功能模块流程图 13 4)调试分析 前边程序没什么问题,但到了最后发现运算程序的时候程序结果虽然正确,但是程序会出现崩溃现象,经过分析应该是指针存在指向重复的问题,后来发现如果单纯去找问题的所在会很麻烦,也不一定能找出来具体的地方,因为程序本身是没有问题的,所以我遍采用重新开辟空间,讲之前的A和B链表赋给新的空间来避免指针重复的问题 5)测试结果 下面为部分运算截图单链表的创建 14 单链表的插入 单链表的删除 15 单链表的排序 单链表的差运算 16 单链表的交运算 测试程序,进行全面的数据输入,频繁的运行各种运算,人工检验运算的准确度。 6)用户使用说明 由于我们考虑到用户知识层次的不同,我们做了很贴心的服务,用户只需要按照提示一步步操作即可。 7)课设总结 通过这周的课程设计,我们对数据结构中单链表的应用有了更深刻的理解,并且使我们深刻认识到时间的重要性,只有理论与实践相结合才能达到很好的学习效果,特别是程序语言的学习,只有将知识运用到实践中,能力才能的发哦提高。 在我进行课程设计时,虽然大体上算法是正确的,但是常常会出现一些小的问题,是我们不得不花大量的时间来查找和修改错误。 基本上是基本功的问题,一般都是格式上的错误。 通过这次课程设计,让我们充分认识到在编写代码的时候,程序书写规范的重要性。 并且在做课程设计中也让我们充分认识到数据结构在编写程序方面的重要地位,因此我们希望在以后的17 学习过程中,能够多多的学习这方面的知识来弥补不足的地方。 8)附录(源代码) #include #include #include typedefstructLnode {intdata; structLnode*next; }*Linklist,Lnode; voidCreatList(Lnode*L)/*建立链表CreastList函数*/ {Lnode*p; intvalue; L->next=NULL; while (1)/*当输入非0数值时*/ {scanf(%d,&value); if(value==NULL) return; p=(Lnode*)malloc(sizeof(Lnode));/*建立P链表*/ p->data=value; p->next=L->next;/*把后输入的插到前面*/ L->next=p; } } //单链表的输出 voidprintList(Lnode*head) { 牰湩晴尨输出的结果如下: \n); Lnode*p=head->next;//头结点赋给P if(p==NULL) { 18 printf(Listisempty! \n); return; } while(p! =NULL) { printf(%d,p->data); p=p->next; } printf(\ ); } voidpaixu(Lnode*L)/*排序函数*/ { Linklistr,q,small;inttemp; for(r=L->next;r->next! =NULL;r=r->next) {small=r; for(q=r->next;q;q=q->next)/*找到链表中最小元素*/ if(q->data small=q; if(small! =r) {temp=r->data; r->data=small->data;/*把最小的数值换到P指针所指的位置数值上(原P指针的next指向不变)*/ small->data=temp;/*把原先p指针所指位置的数值填入被置换出的最小元素位置*/ } } } voidPrintList(Lnode*L)/*打印链表PrintList函数*/ 19 { Lnode*p=L->next;/*带头节点,把指针置于第一个数*/ if(p==0) 灻楲瑮? 链表为空);} else 牰湩晴尨链表为: ); {while(p) { printf(%d>>,p->data); p=p->next; } } printf(\ ); } inter(Lnode*L,inti) { Lnode*k=L->next; while(k) {if(k->data==i) return1; k=k->next
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 单链表 课程设计 设计 报告