c++课程设计《链表的实现-增删改查》

河南城建学院 课 程 设 计 报 告 书



业:课程设计名称: 《数据结构课程设计》



目:



号:



名:

同 组 人 员:

指 导 老 师: 完 成 时 间:2012 年 2 月 17 日

摘要

现在是信息爆炸的时代,整个生活空间都充斥着无尽的数据信息,随时随地都可 能要存储一些信息,或者删除一些信息。然而有时候又不确定信息的数量和对信息操 作的不同需求,这时,有一个动态的存储的系统是很必须的。这个系统要基本满足客 户对信息的处理,诸如一些简单的操作:插入,删除,查找,输出,计数等,并且, 这个系统要能够像电脑上的操作系统一样,能够执行很多操作之后,仍然能够回到主 菜单界面,不能执行一个操作就需要重新启动,那样的话,先前存储的信息会丢失不 说,对使用的客户来说,也很不方便。所以,这时给用户更多的选择就很必要了。 本文采用 C 作为前台的开发工具,Visual C++6.0 作为后台数据库平台,建立基 于 C/C++两层模式的链表操作系统, 旨在实现对生活中一些信息进行基本简单高效的 操作。 关键词:C,Visual C++6.0,链表,建表,查找,删除,插入,计数,输出

目录
目 录 ................................................................................................................................... 1 第一章 1.1 开发环境和开发工具 .......................................................................................... 1 C 语言简介 .......................................................................................................... 1

1.2 开发背景 ................................................................................................................. 1 1.3 开发环境 ................................................................................................................. 1 第二章 算法思想 ............................................................................................................... 3

2.1 系统需求分析 ......................................................................................................... 3 2.2 系统总体设计 ......................................................................................................... 3 2.2.1 系统设计目标 ............................................................................................. 3 2.2.2 开发设计思想 ............................................................................................. 3 2.2.3 系统功能模块设计 ..................................................................................... 4 2.3 算法思想描述 ......................................................................................................... 6 第三章 算法实现 .............................................................................................................. 9

3.1 数据结构 ................................................................................................................. 9 3.2 程序模块 ................................................................................................................. 9 3.3 各模块之间的调用关系 ....................................................................................... 10 3.4 源程序代码 ........................................................................................................... 12 第四章 测试与分析 ........................................................................................................ 21

4.1 测试数据选择 ....................................................................................................... 21 4.2 测试结果分析 ....................................................................................................... 23 总 结 ............................................................................................................................. 24

心得体会 ............................................................................................................................. 25 参 考 文 献 ..................................................................................................................... 26

第一章
1.1.1 C/ C ++语言简介

开发环境和开发工具

C 语言是一种计算机程序设计语言。它既具有高级语言的特点,又具有汇编语 言的特点。C 语言已先后被移植到大、中、小及微型机上。它可以作为工作系统设计 语言,编写系统应用程序,也可以作为应用程序设计语言,编写不依赖计算机硬件的 应用程序。它的应用范围广泛,具备很强的数据处理能力,不仅仅是在软件开发上, 而且各类科研都需要用到 C 语言,适于编写系统软件,三维,二维图形和动画。 C 语言具有简洁紧凑、灵活方便运算符丰富数据类型丰富语法限制不太严 格,程序设计自由度大允许直接访问物理地址,对硬件进行操作生成目标代码 质量高,程序执行效率高 缺点。 适用范围大,可移植性好等优点。但它也有一定的

1.2 开发背景
随着科学技术的不断发展,计算机科学日渐成熟,其强大的功能已为人们所深 刻认识,它己进入人类社会的各个领域并发挥着越来越重要的作用。采用计算机进行 信息管理已成为社会生活中的普遍现象。而数据信息管理的全面自动化、信息化则是 其中重要的组成部分。数据信息管理的好坏对于每个人来说都至关重要,在很大程度 上影响着我们的生活质量。因此,本文所研究的链表操作系统具有一定的使用价值和 现实意义。

1.3 开发环境
本文所采用的开发环境主要是基于 C 为开发工具,并以 Visual C++6.0 作为后台 数据库平台的基于 C/C++的双层管理模式。 在进入 Visual C++6.0 工作界面,选择建立 Win 32 Console Application 工程 文件, 并为该工程文件命名, 确定后进入下一步, 建立以 C/C++为头文件的目标程序,

1

并以.c 为文件格式命名。完成后,即可键盘录入源程序。
录入完成后,点击右上方“! ! ”可以进行编译,并对该程序进行上机调试,直至程序能够完 整并正确的运行出来。

2

第二章
2.1 系统需求分析

算法思想

本程序为链表操作系统,是用自定义数据类型(结构体)及指针的应用来实现链 表的建立,插入,查找,删除,计数,输出。 程序用结构体来记录数据信息。数据由用户通过键盘输入,然后通过内存的动态 应用来建立一个链表。再通过指针的灵活应用来实现各项其他操作。 在建立系统的过程中, 细节性的提示一定要全面到位, 应为这是内存的动态应用, 所以存在很大的变数,一定要让用户能够清楚的知道应该怎么做,并且能对用户的错 误输入给出正确的提示,争取做到无论用户如何输入都会又回应,不能出现死机的状 况。

2.2 系统总体设计
2.2.1 系统设计目标

本文研究开发数据信息的链式动态存储来满足人们日常生活的需要,有以下三个 方面的目标: ●数据信息的多少没有上限。 ●支持高效率完成人们日常生活中对信息的操作需求,包括新信息的插入,旧信 息的查找和删除。 ● 支持动态管理要存储的信息, 令人们能及时的对数据信息进行处理, 提高生活 效率等目标。

2.2.2 开发设计思想

基于以上系统设计目标,本文在开发链表操作系统时遵循了以下开发设计思 想:

3

●采用现有的软硬件环境及先进的链表操作系统开发方案, 从而达到充分利用

现有资源,提高系统开发水平和应用效果的目的。
●尽量达到操作过程中的直观、方便、实用、安全等要求。 ●系统采用模块化程序设计方法, 既便于系统功能的各种组合和修改, 又便于未

参与开发的技术维护人员补充、维护。

2.2.3 系统功能模块设计

本系统分为六个模块:建表模块、插入模块、删除模块、查找模块、计数模块、 输出模块。 ●1.程序主要功能函数 时间复杂度为 struct line * made (int *count) 实现链表的建立 时间复杂度为 O(n) struct line * Insert(struct line *head,int *count) 实现对链表进行插入操作 时间复杂度为 O(n) struct line * Delate(struct line *head,int *count) 实现对链表的已有信息的 删除操作 时间复杂度为 O(n) void counter(int *count) 实现对链表数据信息个数统计操作 时间复杂度为 O(1) 实现按序号找结点 结点的操作 void Search1(struct line *head,int *count) 实现按序号找结点的操作 时间复杂度为 O(n) 实现按结点 结点找序号的操作 void Search2(struct line *head,int *count) 实现按结点找序号的操作 时间复杂度为 O(n) void output(struct line *head,int Count) 实现对信息的输出操作 时间复杂度为 O(n) void main () 主函数 ●2.主流程图

4

开始 总流程图

输出各项操作

输入 order 值

判 断 order 值 order 为 0 或 大于 5 的数

order 为 1

order 为 2

order 为 3

order 为 4

order 为 5

插入

删除

查找

计数

输出

输入 order 的值

判断 order 的值

结束

图 2.2.3-1 2.2.35

2.3 算法思想描述

在各个操作流程中,一定要考虑到用户的错误信息的输入,尽可能对用户的输入 作出应该有的回应。 这就要求在各个模块中使用到很多的循环, 对于循环变量的要求, 也是一个很大的挑战,正如一下流程图所展示的:

开始 插入流程图

输入插入的位置 a

false a<1 或 a>count?

true

输入插入的值 num

完成插入

结束

图 2.3-1

在用户输入要插入的位置时,一定要判断用户的输入是否合法:一个只有 6 个结 点的链表, 用户却要把新的结点插入到第 9 个结点的前面, 显然这是不可能的, 这时, 就要要求用户重新输入,并且同时给用户正确的提示。 同时插入的过程中,利用循环找到要插入的位置,然后插入。插入的时候,指针的 变换必须是插入的元素的指针先指向下下一个,然后前面的指针指向这个。如果不是 这个顺序,就会丢失后面的部分链表。所以这个也是一定要注意的。

6

开始 删除流程图

输入要删除的元素序号 n

true n<1 或 n>count

false

找到该元素并删除

结束

图 2.3-2

同理,在删除的过程中,一定要判断用户的输入的是否合法。因为删除的元素序 号必须是链表范围的内的,超出这个范围是无法执行的。在指针指向改动的时候,一 定要注意是哪个指针的变换,不要删错元素。

7

开始 查找流程图 输入 order2 的值

判断 order2 的值

order2 值为 1

order2 值为 2

按序号查找

按元素值查找

输出元素值

输出序号

完成查找

结束

图 2.3-3

查找时,会有两种查找,一种是输入结点值查找其序号;一种是输入序号,找结 点值。 所以设置的变量 order2 用来让用户选择要查找的方式。 同时一定要给用户清晰的提 示,实现用户所要达到的目标等。
8

第三章 算法实现
3.1 数据结构
链表操作系统是一个内存动态应用系统, 用户所有的要处理的数据信息都存储在 链表中。 本系统采用结构体的形式来存储用户的信息,并且,大量的使用循环,来实现系 统的多次使用。

3.2 程序模块
在程序中又分为 6 个模块:建表模块、插入模块、删除模块、计数模块、输出模 块、函数。 其中,查找模块又分为了两个模块: 模块一:通过序号找结点 void Search1(struct line *head,int *count) //按照给定序号查找函数 //head 为链表的头指针 //整型指针 count 指向结点个数计数器 void Search1(struct line *head,int *count) { struct line *p;//接受链表头指针 int i,j,e;//i 用来存储用户要查找的结点的序号,j 用来控制循环次数,e 用 来存储该结点的值 printf ("请输入你要查找的结点的序号\n"); scanf ("%d",&i); while(i<1||i>*count) { printf("请输入正确的序号:\n"); printf("%d~~%d\n",1,*count); printf ("请输入你要查找的元素的序号\n"); scanf("%d",&i); } p=head;

9

j=1; while (j!=i)//顺指针向后查找,直到 p 指向第 i 个元素或 p 为空 { p=p->next; j++; } e=p->num;//取第 i 个元素 printf("你要查找的元素值为%d\n",e); }

模块二:通过结点找序号 //给定数值查找其在链表中的位置即序号 //head 为链表的头指针 //整型指针 count 指向结点个数计数器 void { int e,j,tell=0;//e 用来存储用户要查找的结点的值,j 用来控制循环,tell 判断是否找到了存储该值的结点 struct line *p;//接受链表头指针 printf ("请输入你要查找的元素值: \n"); scanf ("%d",&e); p=head; j=1; for(j=1;j<=*count;j++) { if(e==p->num) { printf("你要查找的值的序号为%d.\n",j);//找到所查找值的位置即 第 j 个元素 tell++; p=p->next; } else p=p->next; } if(tell==0) printf("您要查找的值不存在.\n"); } Search2(struct line *head,int *count)

10

3.3 各模块之间的调用关系
主函数在用户不停止系统的情况下调用各个模块,从而实现用户的需求:

主函数

判断

插入

删除

查找

计数

输出

判断

结束

图 3.3-1

11

3.4 源程序代码
#include <stdio.h> #include <stdlib.h> //结构体的定义 struct line { int num;//用来存储已知的数据 struct line *next;//用来指向下一个结点 };

//输出函数 //head 为链表头指针,Count 为链表结点计数器 void Output(struct line *head,int Count) { struct line *p;//接受链表头指针 int i=0;//控制下面的循环 p=head; printf("链表中的元素值为:\n"); for(i=0;i<Count;i++)//遍历链表 { printf("%d ",p->num); p=p->next; } printf("\n"); } //链表构造函数,返回值为指向 struct line 结构体的指针 //参数为指向整型的指针 count //作用:构建线性链表并计数 //当输入的值为零时,默认结束输入 struct line * made (int *count) { struct line *p1=NULL,*p2=NULL;//建立链表的辅助指针 struct line *head=NULL; p2=p1=(struct line *)malloc(sizeof(struct line));
12

printf("输入 0 表示建表结束,请输入至少一个元素。\n"); printf("请输入第%d 个元素的值:\n",*count+1); scanf("%d",&p1->num); while(p1->num!=0) { if(*count==0) { head=p1; (*count)++; } else { p2->next=p1; p2=p2->next; (*count)++; } p1=(struct line *)malloc(sizeof(struct line)); printf("请输入第%d 个元素的值:\n",*count+1); scanf("%d",&p1->num); } free(p1); return head; }

//插入函数,返回值为指向 struct line 结构体的指针 //参数为一个指向结构体的指针和两个整型指针与一个整型数 //结构体指针 head 式链表的头指针,整型指针 count 指向计数器 struct line * Insert(struct line *head,int *count) { int a,num;//a 存储插入的位置,b 存储插入的数据 struct line *p1=head,*p2=NULL; printf("请输入要插入的位置:\n"); scanf("%d",&a); while(a<1||a>(*count+1))//判断用户的输入是否正确,如果不合法,提醒用户 正确输入 { printf("请输入正确位置:\n"); printf("%d~%d\n",1,*count+1); scanf("%d",&a); }

13

printf("请输入要插入的元素值:\n"); scanf("%d",&num); if(a==1) { p2=(struct line *)malloc(sizeof(struct line)); p2->num=num; p2->next=p1; head=p2; } else if(a==2) { p2=(struct line *)malloc(sizeof(struct line)); p2->num=num; p2->next=p1->next; p1->next=p2; head=p1; } else { while (a-2!=0) { p1=p1->next; a--; } p2=(struct line *)malloc(sizeof(struct line)); p2->num=num; p2->next=p1->next; p1->next=p2; } printf("插入成功。\n"); return head; } //删除函数 //参数一个指向结构体的指针和一个整型指针 //结构体指针 head 为链表头指针 //整型指针 count 为结点个数计数器 struct line * Delate(struct line *head,int *count) { int n;//用来存储用户要删除的结点序号 struct line *p1=head,*p2=head;//删除过程中的辅助指针 printf("请输入要删除的元素序号:\n");

14

scanf("%d",&n); while(n>*count||n<0)//判断用户的输入是否合法,如果不合法,提醒用户正确 输入 { printf("请输入正确的数:\n"); printf("%d~%d\n",1,*count); scanf("%d",&n); } if(n==1) { head=p1->next; free(p1); } else if(n==2) { p1=p1->next; p2->next=p1->next; } else { p1=p1->next; while(n-2!=0) { p2=p2->next; p1=p1->next; n--; } p2->next=p1->next; } printf("删除成功\n"); return head; }

//计数函数 //参数为一个整型指针,指向结点个数计数器 void counter(int *count) { printf("链表的元素个数为:\n"); printf("%d\n",*count); }

15

//按照给定序号查找函数 //head 为链表的头指针 //整型指针 count 指向结点个数计数器 void Search1(struct line *head,int *count) { struct line *p;//接受链表头指针 int i,j,e;//i 用来存储用户要查找的结点的序号,j 用来控制循环次数,e 用 来存储该结点的值 printf ("请输入你要查找的结点的序号\n"); scanf ("%d",&i); while(i<1||i>*count) { printf("请输入正确的序号:\n"); printf("%d~~%d\n",1,*count); printf ("请输入你要查找的元素的序号\n"); scanf("%d",&i); } p=head; j=1; while (j!=i)//顺指针向后查找,直到 p 指向第 i 个元素或 p 为空 { p=p->next; j++; } e=p->num;//取第 i 个元素 printf("你要查找的元素值为%d\n",e); }

//给定数值查找其在链表中的位置即序号 //head 为链表的头指针 //整型指针 count 指向结点个数计数器 void { int e,j,tell=0;//e 用来存储用户要查找的结点的值,j 用来控制循环,tell 判断是否找到了存储该值的结点 struct line *p;//接受链表头指针 printf ("请输入你要查找的元素值: \n"); Search2(struct line *head,int *count)

16

scanf ("%d",&e); p=head; j=1; for(j=1;j<=*count;j++) { if(e==p->num) { printf("你要查找的值的序号为%d.\n",j);//找到所查找值的位置即 第 j 个元素 tell++; p=p->next; } else p=p->next; } if(tell==0) printf("您要查找的值不存在.\n"); }

//主函数 void main () { struct line * made (int *count); void counter(int *count); struct line * Delate(struct line *head,int *count); struct line * Insert(struct line *head,int *count); void output(struct line *head); void Search1(struct line *head,int *count); void Search2(struct line *head,int *count); int order,order1,order2;//存储用户输入的指令 struct line *head;//链表的头指针 int Count=0,*count=NULL;//结点计数器和指向结点计数器的指针 count=&Count; printf("首先,建立一个链表。\n"); head=made(count); while(!head) { printf("请建立至少一个结点的链表\n"); *count=0; head=made(count); }

17

printf("************** 1 插入*****************\n"); printf("************** 2 删除*****************\n"); printf("************** 3 查找*****************\n"); printf("************** 4 计数*****************\n"); printf("************** 5 输出*****************\n"); printf("************** 0 退出*****************\n"); printf("\n\n"); printf("请输入您要选择的操作:\n"); printf("如果输入账单中不存在的数,程序退出.\n"); scanf("%d",&order); while(order>0&&order<6) { switch(order)//判断用户输入的指令 { case 1: printf("您选择了插入?\n"); printf("确认请输入 1,重新选择输入 0 或者任意非 1 的数\n"); scanf("%d",&order1); if(order1==1) { head=Insert(head,count); Count++; break; } else break; case 2: printf("您选择了删除?\n"); printf("确认请输入 2,重新选择输入 0 或者任意非 2 的数\n"); scanf("%d",&order1); if(order1==2) { head=Delate(head,count); Count--; break; } else break; case 3: printf("您选择了查找?\n"); printf("确认请输入 3,重新选择输入 0 或者任意非 3 的数\n"); scanf("%d",&order1); if(order1==3)

18

{ printf("***************** 1 按 序 号 查 找 , 返 回 元 素 值 。 ******************\n"); printf("***************** 2 按 元 素 值 查 找 , 返 回 序 号 。 ******************\n"); printf("\n\n"); scanf("%d",&order2); if(order2==1) { Search1(head,count); break; } else { Search2(head,count); break; } } else break; case 4: printf("您选择了计数?\n"); printf("确认请输入 4,重新选择输入 0 或者任意非 4 的数\n"); scanf("%d",&order1); if(order1==4) { counter(count); break; } else break; case 5: printf("您选择了输出?\n"); printf("确认请输入 5,重新选择输入 0 或者任意非 5 的数\n"); scanf("%d",&order1); if(order1==5) { Output(head,Count); break; } else break; case 0:

19

break; } printf("************** 1 插入*****************\n"); printf("************** 2 删除*****************\n"); printf("************** 3 查找*****************\n"); printf("************** 4 计数*****************\n"); printf("************** 5 输出*****************\n"); printf("************** 0 退出*****************\n"); printf("\n\n"); printf("请输入您要选择的操作:\n"); printf("如果输入账单中不存在的数,程序退出.\n"); scanf("%d",&order); } }

20

第四章 测试与分析

4.1 测试数据选择

图 4.1-1 图 4.1-1 中首先建立了一个简单的链表,然后进行了插入操作并且插入成功了。

21

图 4.1-2 图 4.1-2 中是删除操作和输出操作的结果

22

图 4.1-3 图 4.1-3 中显示的是查找操作运行过程和结果

4.2 测试结果分析
在测试的过程中,成功的实现了数据的插入、删除、查找、计数、输出等操作。 并且,提示也相当令人满意,让人能够正确的操作这个系统。 基本上实现了原本设计这个系统的目标。
23





此链表操作系统,是通过自定义数据类型(结构体)及指针的应用来实现链表的 建立,插入,查找,删除,计数,输出的。其中主要包括数学模型的建立、算法的设 计、各个函数的编写以至于整个程序的完成。其中要特别注意的是:首先,在编译的 过程中,指针的使用导致很多细节性的东西容易出错。因为指针是比较抽象的东西, 在使用的过程中一不小心就可能导致程序运行的错误,并且,只有通过调试才能找出 错误的所在。其次,就是链表中的循环,很难实现精确的控制,一定要正确地选择控 制循环的变量,能够令操作准确高效的进行。 此链表操作系统主要有以下特色与不足: 主要特色 1. 对于此链表操作系统,只有有用户的控制(主要是通过键盘)时,才能退出, 不然将会一直进行下去。 2. 此系统的提示也很人性化,让人能够正确地操作这个系统,同时,对于错误 的输入,也给出了很令人满意的回应,例如,给出正确提示,并让用户重新输入正确 指令,从而能够更好地好的使用此系统,更好地实现了人机交流。 3. 循环的多次使用,也是这个程序的特色,能够让系统在执行用户的输入的时 候,尽可能的减少错误的出现。 4. 最重要的是指针的使用,实现了数据的及时变化,能够更好地满足用户的需 求。 5. 此链表操作系统地进步之处在于把计数函数的时间复杂度由 O(n)改进为了 O(1)。 6. 程序中在某些地方是使用了 free( )函数,节省了空间。 不足之处 1.虽然在某些地方进行了改进,但时间复杂度还不是很低,即程序的效率还不是 很高,有待于更进一步得改进。
2.操作功能还不是十分完善,尚有不足之处。

24

心得体会
此次课程设计,我选的题目是链表操作系统的实现。刚看到这个题目时,感觉很 简单,可是,真正认真地去思考时,才发现,要想成功的实现链表的操作却不是一件 简单的事。 通过数学模型的建立、算法的设计、各个函数的编写以至于整个程序的完成,很 好地复习了以前所学的东西。 但由于初次执行的不成功, 又开始寻找问题, 思考问题, 解决问题,又通过程序调试,直到整个系统的成功实现。当程序执行中遇到问题却又 找不到好的解决方法时,真的很郁闷。例如,在编译的过程中,指针的使用导致很多 细节性的东西容易出错。因为指针是比较抽象的东西,在使用的过程中一不小心就可 能导致程序运行的错误, 并且, 只有通过调试才能找出错误的所在。 当时心里很着急, 但是,光心急是没有用的,于是使自己平静下来好好思考。当通过查阅资料,共同讨 论,经过冥思苦想后,成功地解决问题时,却又是那么地高兴、欣慰。 完成了这个链表操作系统之后,感觉收获了很多。在数学模型的建立、算法的设 计及程序的编写中,温习了很多知识结构,例如链表各个基本操作的算法,指针和循 环结构的使用等。与此同时,活跃了思维,提高了解决问题,分析问题的能力。在撰 写实验报告时,通过摘要的总结概括,各程序模块及其调用关系的分析,更加明白了 数据结构着门课的含义,即数学模型加算法,同时也增强了逻辑思维能力。 此次的课程设计及深化了以前所学的知识,达到了温故而知新的效果,也提高了 实践能力。但最重要的是认识到了自己的一些不足之处,我觉得这是我最大的收获。 在以后的日子中,我一定,加倍努力,科学、高效率地学习,因为我知道在专业知识 的熟练掌握上,我还有很长的一段路要走。

25

参考文献
[1] 徐士良. 计算机软件技术基础[M] . 北京:清华大学出版社,2004. [2] 廖雷.C程序设计实践教程[M] .北京: 高等教育出版社,2003. [3] 杨晓光. 数据结构实例教程 .北京:清华大学出版社,2008. [4] 严蔚敏版《数据结构》.(C 语言版)北京:清华大学出版社, 2010.

26


相关文档

C语言链表实现增删改查
C语言指针链表(增、删、改、查)
c言语链表的增删查改(最简单)
C语言课程设计链表操作
链表的增删改查
J2EE实现增删改查课程设计报告书
城市链表课程设计(C语言)
学生成绩管理系统完整版 C程序设计源代码 不用链表 有添加 删除 查找 修改等功能
通讯录管理 C程序设计源代码不用链表 完整版 有添加 删除 查找 修改等功能
C语言课程设计报告——十字交叉链表的应用
电脑版