数据结构单链表课程设计设计报告

数据结构单链表课程设计设计报告

《数据结构》课程设计报告

1） 需求分析

此程序主要用来实现单链表的创建、插入、删除、排序、并、交、差运算及输出等基本操作。

程序需要根据使用者的需要来运算得出符合要求的结果

①在程序运行的过程中根据提示进行输入，使用了scanf函数；

②使用了printf函数进行输出； ③程序输出符合使用者的需要的结果； ④程序能够输出任意运算的正确结果。 2） 概要设计

1. 定义所需的数据结构

data *next

typedef struct LNode{

int data; //数据域 struct LNode *next; //指针域 }LNode, *LinkList; 2. 模块划分

void LinkListCreat(LinkList &L,int n); //创建 void ListInsert(LinkList head,int i,int e); //插入 void ListDelete(LinkList head,int i,int e); //删除 void printList(LinkList &head); //输出

2

void LinkListsort(LinkList &L); //排序

void

LinkListMerge(LinkList

&La,

LinkList

&Lb,LinkList &Lc); //并

void LinkListJiao(LinkList &La, LinkList &Lb,LinkList &Lc); //交

void LinkListcha(LinkList &La, LinkList &Lb,LinkList &Lc); //差

void LinkListhebing(LinkList &La, LinkList &Lb,LinkList &Lc); //差集的并

void main(); //主函数，分别调用以上的子

函数

3 .功能设计

首先利用元素逆序插入法建立链表，然后导出菜单，用switch调用各个子函数，实现链表的创建，插入，删除，排序，交，并，差等运算，其中排序用的是冒泡法。

3） 详细设计 //单链表的创建

void CreatList(Lnode *L) /*建立链表CreastList函数*/ { Lnode *p; int value; L->next=NULL;

while (1) /*当输

3

入非0数值时*/

{scanf( \"%d\ if (value==NULL) return; p=(Lnode

*)malloc(sizeof(Lnode)); /*建立P链表*/

p->data=value;

p->next=L->next; /*把后输入的插到前面*/ L->next=p; } }

//单链表的输出

void printList(Lnode *head) {

printf(\"输出的结果如下： \\n\"); Lnode *p = head->next;//头结点赋给P

4

if (p == NULL) {

printf(\"List is empty!\\n\"); return; }

while (p != NULL) {

printf(\"%d \ p = p->next; }

printf(\"\\n\"); }

//单链表的插入

void ListInsert(LinkList head,int i,int e)//在单链表中第i个位置之前插入e元素 {

LinkList p,s; int j=0; p=head;

while(p&&j5

{

p = p->next; ++j; }

if(!p||j>i-1) {

printf(\"要插入的位置错误！\"); } s = (LNode *)malloc(sizeof(LNode));//给插入的元素开辟空间

s->data = e;//改变指针指向 s->next = p->next; p->next = s; }

//单链表的删除

int ListDelete_L(Lnode *L,int i) /*删除函数*/ {

Lnode *p=L->next; int j=0; Lnode *q; while

(p->next

&&

j{p=p->next; ++j;} /*找出第i节点，

6

并令p指向其前趋*/

if (!p->next || j>i-1) return 0; q=p->next; p->next=q->next; free(q); return 1; }

//单链表的差运算

Lnode

*c,*a,*t;

c=C=(Lnode *)malloc(sizeof(Lnode)); a = A->next; while(a) { p = B->next; while(p a->data != p->data) {

7

&&

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\");

=

8

printList(C);

C=(Lnode *)malloc(sizeof(Lnode)); /*必须再分配一次地址空间以用来把原链表清空，否则每次运行都会使链表元素增加*/

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;

9

&&

}

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);

=

10

D=(Lnode *)malloc(sizeof(Lnode)); break;

//单链表的并运算

Lnode *e;

a =A->next; p = B->next; e = E = A; //用La的头结点作为Lc的头结点 while(a&&p) {

if(a->data p->data)//如果指节点之后 {

e->next = a; e = a;

11

<=

pa->data <=

pb->data，将pa所指节点链接到pc所

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;

//主函数

12

main() { int

sign,sign1,signa,signb,signc,i,x,ca,cb,cc; int choice=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

13

*)malloc(sizeof(Lnode));

printf(\"\ 《数据结构课程设计--单链表的基本操作》\\n\\n\"); while (choice) {

printf(\"\ 请选择您想进行的操作:\\n 1:对A链表操作 \\n 2:对B链表操作 \\n 3:两链表运算 \\n 4:退出程序 \\n \\n 您的选择是：\");

scanf(\"%d\输入选项*/

if (sign1==1) /*如果选择1则输出下列选项界面*/

{L=A; /*选择1对链表A进行操作*/ ca=1; while (ca) {

14

printf(\"\ 请选择对A链表进行的操作:\\n 1:建立链表 \\n 2:对链表排序 \\n 3:在链表中插入元素 \\n 4:在链表中删除元素 \\n 5:返回上一级菜单 \\n 您的选择是：\");

scanf(\"%d\/*输入对链表A的操作选项*/ switch(signa) { case 1:

printf(\"\\n请输入链表元素(输入去0结束)\\n\"); /*调用CreatList函数*/

PrintList(A); /*调用PrintList函数*/

break;

15

CreatList(A);

case 2:

printf(\"对A链表进行排序，结果为：\\n \"); paixu(A); /*调用排序函数*/

PrintList(A); /*调用PrintList函数*/ break; case 3:

printf(\"请输入想要插入的位置及插入的数值（以逗号分隔）: \"); scanf(\"%d,%d\ if (ListInsert_L(L,i,x)==1)

{printf(\"修改成功!

16

目前A链表为：\\n\");

PrintList(L);} else printf(\"警告!您输入的插入位置超过链表长度。 \\n\"); break; case 4:

printf(\"请输入想要删除的元素位置: \");

scanf(\"%d\ if (ListDelete_L(L,i)==1)

{printf(\"删除元素成功!目前A链表为：\\n\");

PrintList(L);} else printf(\"警告!您输入的删除位置超过链表长度。 \\n\");

17

break; case 5: ca=0; break; default:

printf(\"警告!只能选择1-5。 \\n\"); break; } } }

else if (sign1==2) {L=B; cb=1; while (cb)

{printf(\"\ 请选择对B链表进行的操作:\\n 1:建立链表 \\n 2:

18

对链表排序 \\n 3:在链表中插入元素 \\n 4:在链表中删除元素 \\n 5:返回上一级菜单 \\n 您的选择是：\"); scanf(\"%d\ switch(signb) { case 1:

printf(\"\\n请输入链表元素(输入0结束)\\n\"); CreatList(B); PrintList(B); break; case 2:

printf(\"对B链表进行排序，结果为：\\n \"); paixu(B); PrintList(B);

19

break; case 3:

printf(\"请输入想要插入的位置及插入的数值（以逗号分隔）: \"); scanf(\"%d,%d\ if (ListInsert_L(L,i,x)==1)

{printf(\"修改成功!目前B链表为：\\n\");

PrintList(L);} else printf(\"警告!您输入的插入位置超过链表长度。 \\n\"); break; case 4:

printf(\"请输入想要

20

删除的元素位置: \");

scanf(\"%d\ if (ListDelete_L(L,i)==1)

{printf(\"删除元素成功!目前B链表为：\\n\");

PrintList(L);} else printf(\"警告!您输入的删除位置超过链表长度。 \\n\"); break; case 5: cb=0; break; default:

printf(\"警告!只能选择1-5。 \\n\"); break;

21

} } }

else if (sign1==3) {cc=1; while (cc)

{printf(\"\ 请选择操作的名称:\\n 1:显示当前的A、B链表 \\n 2:进行差运算 \\n 3:进行交运算 \\n 4:进行并运算 \\n 5:返回上一级菜单 \\n 您的选择是：\");

scanf(\"%d\ switch(signc) { case 1:

printf(\" \\n 当前A\");

22

PrintList(A);

printf(\" \\n 当前B\");

PrintList(B);

break; case 2: Lnode *c,*a,*t; c=C=(Lnode *)malloc(sizeof(Lnode)); a = A->next; while(a) { p = B->next; while(p a->data != p->data) {

23

&&

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\");

=

24

printList(C);

C=(Lnode *)malloc(sizeof(Lnode)); /*必须再分配一次地址空间以用来把原链表清空，否则每次运行都会使链表元素增加*/

break;

case 3:Lnode *d;

d=D=(Lnode *)malloc(sizeof(Lnode)); a = A->next; while(a) { p = B->next; while(p a->data != p->data) {

25

&&

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\");

=

26

printList(D);

D=(Lnode *)malloc(sizeof(Lnode)); break; case 4: Lnode *e; a =A->next; p = B->next; e = E = A; //用La的头结点作为Lc的头结点 while(a&&p) {

if(a->data p->data)//如果指节点之后 {

e->next = a;

27

<=

pa->data <=

pb->data，将pa所指节点链接到pc所

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;

28

case 5: cc=0; break; default:

printf(\"警告!只能选择1-5。 \\n\"); break; } } }

else if (sign1==4) {

printf(\"谢谢使用，请按任意键退出!\\n\"); break; } else

{printf(\"提示:仅能在1-4

29

之间选择！\\n\"); break; } }

return 0; }

4. 流程图

30

图1-1 单链表基本操作功能模块流程

图

4） 调试分析

31

前边程序没什么问题，但到了最后发现运算程序的时候程序结果虽然正确，但是程序会出现崩溃现象，经过分析应该是指针存在指向重复的问题，后来发现如果单纯去找问题的所在会很麻烦，也不一定能找出来具体的地方，因为程序本身是没有问题的，所以我遍采用重新开辟空间，讲之前的A和B链表赋给新的空间来避免指针重复的问题

5） 测试结果

下面为部分运算截图

单链表的创建

单链表的插入

32

单链表的删除

33

单链表的排序

单链表的差运算

34

单链表的交运算

测试程序，进行全面的数据输入，频繁的运行各种运算，人工检验运算的准确度。 6） 用户使用说明

由于我们考虑到用户知识层次的不同，我们做了很贴心的服

35

务，用户只需要按照提示一步步操作即可。 7） 课设总结

通过这周的课程设计，我们对数据结构中单链表的应用有了更深刻的理解，并且使我们深刻认识到时间的重要性，只有理论与实践相结合才能达到很好的学习效果，特别是程序语言的学习，只有将知识运用到实践中，能力才能的发哦提高。

在我进行课程设计时，虽然大体上算法是正确的，但是常常会出现一些小的问题，是我们不得不花大量的时间来查找和修改错误。基本上是基本功的问题，一般都是格式上的错误。

通过这次课程设计，让我们充分认识到在编写代码的时候，程序书写规范的重要性。并且在做课程设计中也让我们充分认识到数据结构在编写程序方面的重要地位，因此我们希望在以后的学习过程中，能够多多的学习这方面的知识来弥补不足的地方。 8）附录（源代码）

#include #include #include typedef struct Lnode {int data;

struct Lnode *next;

}*Linklist,Lnode;

void CreatList(Lnode *L) /*建立链表CreastList函数*/

{ Lnode *p; int value; L->next=NULL;

while (1) /*当输入非0数值时*/ {scanf( \"%d\ if (value==NULL) return;

p=(Lnode *)malloc(sizeof(Lnode)); /*建立P链表*/ p->data=value;

p->next=L->next; /*把后输入的插到前面*/

36

L->next=p; } }

//单链表的输出

void printList(Lnode *head) {

printf(\"输出的结果如下： \\n\"); Lnode *p = head->next;//头结点赋给P if (p == NULL) {

printf(\"List is empty!\\n\"); return; }

while (p != NULL) {

printf(\"%d \ p = p->next; }

printf(\"\\n\"); }

void paixu(Lnode *L) /*排序函数*/ {

37

Linklist r,q,small;int temp;

for(r=L->next;r->next!=NULL;r=r->next) {small=r;

for(q=r->next;q;q=q->next) /*找到链表中最小元素*/ if(q->datadata) small=q; if(small!=r) {temp=r->data;

r->data=small->data; /*把最小的数值换到P指针所指的位置数值上（原P指针的next指向不变）*/

small->data=temp; /*把原先p指针所指位置的数值填入被置换出的最小元素位置*/

} } }

void PrintList(Lnode *L) /*打印链表PrintList函数*/ {

Lnode *p=L->next; /*带头节点，把指针置于第一个数*/

if(p==0)

{printf(\"链表为空\");} else

printf(\"链表为：\"); {while(p) {

printf(\"%d>>\ p=p->next; } }

printf(\"\\n\"); }

inter(Lnode *L,int i) {

Lnode *k=L->next; while(k)

{if (k->data==i)

38

return 1; k=k->next; }

return 0; }

int ListInsert_L(Lnode *L, int i, int e) /*插入函数*/

{

Lnode *p=L->next; Lnode *s; int j=0;

while (p && jnext; ++j;} if (!p || j>i-1) return 0;

s=(Lnode *)malloc(sizeof(Lnode)); s->data=e;

s->next=p->next; p->next=s; return 1; }

int ListDelete_L(Lnode *L,int i) /*删除函数*/ {

Lnode *p=L->next; int j=0; Lnode *q;

while (p->next && jnext; ++j;} /*找出第i节点，并令p指向其前趋*/

if (!p->next || j>i-1) return 0; q=p->next;

p->next=q->next; free(q); return 1; }

main() {

39

int sign,sign1,signa,signb,signc,i,x,ca,cb,cc; int choice=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(\"\ 请选择您想进行的操作:\\n 1:对A链表操作 \\n 2:对B链表操作 \\n 3:两链表运算 \\n 4:退出程序 \\n \\n 您的选择是：\");

scanf(\"%d\输入选项*/

if (sign1==1) /*如果选择1则输出下列选项界面*/

{L=A; /*选择1对链表A进行操作*/ ca=1; while (ca) {

printf(\"\ 请选择对A链表进行的操作:\\n 1:建立链表 \\n 2:对链表排序 \\n 3:在链表中插入元素 \\n 4:在链表中删除元素 \\n 5:返回上一级菜单 \\n 您的选择是：\");

scanf(\"%d\/*输入对链表A的操作选项*/

switch(signa) {

case 1:

printf(\"\\n请输入链表元素(输入去0结束)\\n\");

CreatList(A); /*调用CreatList函数*/

PrintList(A); /*调用PrintList函数*/

break;

40

case 2:

printf(\"对A链表进行排序，结果为：\\n \");

paixu(A); /*调用排序函数*/

PrintList(A); /*调用PrintList函数*/

break; case 3:

printf(\"请输入想要插入的位置及插入的数值（以逗号分隔）: \");

scanf(\"%d,%d\

if (ListInsert_L(L,i,x)==1) {printf(\"修改成功!目前A链表为：\\n\");

PrintList(L);} else

printf(\"警告!您输入的插入位置超过链表长度。 \\n\");

break; case 4: printf(\"请输入想要删除的元素位置: \");

scanf(\"%d\

if (ListDelete_L(L,i)==1)

{printf(\"删除元素成功!目前A链表为：\\n\");

PrintList(L);} else

printf(\"警告!您输入的删除位置超过链表长度。 \\n\");

break; case 5: ca=0; break; default:

printf(\"警告!只能选择1-5。 \\n\");

41

break; } } }

else if (sign1==2) {L=B; cb=1; while (cb)

{printf(\"\ 请选择对B链表进行的操作:\\n 1:建立链表 \\n 2:对链表排序 \\n 3:在链表中插入元素 \\n 4:在链表中删除元素 \\n 5:返回上一级菜单 \\n 您的选择是：\");

scanf(\"%d\ switch(signb) {

case 1:

printf(\"\\n请输入链表元素(输入0结束)\\n\");

CreatList(B); PrintList(B); break; case 2:

printf(\"对B链表进行排序，结果为：\\n \");

paixu(B);

PrintList(B); break; case 3:

printf(\"请输入想要插入的位置及插入的数值（以逗号分隔）: \");

scanf(\"%d,%d\

if (ListInsert_L(L,i,x)==1) {printf(\"修改成功!目前B链表为：\\n\");

PrintList(L);} else

printf(\"警告!您输入的插入位置超过链表长度。 \\n\");

42

\");

break; case 4: printf(\"请输入想要删除的元素位置:

scanf(\"%d\

if (ListDelete_L(L,i)==1)

{printf(\"删除元素成功!目前B链表为：\\n\");

PrintList(L);} else

printf(\"警告!您输入的删除位置超过链表长度。 \\n\");

break; case 5: cb=0; break; default:

printf(\"警告!只能选择1-5。 \\n\"); break; } } }

else if (sign1==3) {cc=1;

while (cc)

{printf(\"\ 请选择操作的名称:\\n 1:显示当前的A、B链表 \\n 2:进行差运算 \\n 3:进行交运算 \\n 4:进行并运算 \\n 5:返回上一级菜单 \\n 您的选择是：\");

scanf(\"%d\ switch(signc) {

case 1:

printf(\" \\n 当前A\"); PrintList(A);

printf(\" \\n 当前B\"); PrintList(B);

43

break; case 2:

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)); /*必须再分配一次地址空间以用来把原链表清空，否则每次运行都会使链表元素增加*/

break;

case 3:Lnode *d; d=D=(Lnode *)malloc(sizeof(Lnode));

a = A->next; while(a) {

44

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; case 4:

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; e = a;

a = a->next;

45

}

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; case 5: cc=0; break; default:

printf(\"警告!只能选择1-5。 \\n\"); break; } } }

else if (sign1==4) {

printf(\"谢谢使用，请按任意键退出!\\n\"); break; } else

{printf(\"提示:仅能在1-4之间选择！\\n\"); break; } }

return 0;

46

}

47