单链表的基本操作C语言课程设计

1、课程设计 ( 论文 )题目 名 称单链表的基本操作课程 名 称C 语言程序课程设计学生 姓 名学号系、专 业信息工程系、网络工程专业指导 教 师成娅辉2013 年 6 月 6 日.目 录1前言.32需求分析 .32.1课程设计目的 .32.2课程设计任务 .32.3设计环境 .32.4开发语言 .33分析和设计 .33.1模块设计 .33.2系统流程图 .43.3主要模块的流程图 .64具体代码实现 .95课程设计总结 .125.1程序运行结果 .125.2课程设计体会 .12参考文献 .13致谢.13.1 前言我们这学期学习了开关语句，循环语句、链表、函数体、指针等的应用，我们在完成课程设计

2、任务时就主要用到这些知识点，本课题是单链表的简单操作， 定义四个子函数分别用来创建链表、 输出链表、插入数据以及删除数据， 主函数中主要用到开关语句来进行选择调用哪个子函数，下面就是课程设计的主要内容。2 需求分析2.1 课程设计目的学生在教师指导下运用所学课程的知识来研究、解决一些具有一定综合性问题的专业课题。通过课程设计（论文） ，提高学生综合运用所学知识来解决实际问题、使用文献资料、及进行科学实验或技术设计的初步能力，为毕业设计（论文）打基础。2.2 课程设计任务输入一组正整数，以 -1 标志结束，用函数实现： （1）将这些正整数作为链表结点的 data 域建立一个非递减有序的单链表，并

3、输出该单链表；（ 2）往该链表中插入一个正整数，使其仍保持非递减有序，输出插入操作后的单链表；（3）删除链表中第i 个结点，输出删除操作后的单链表，i 从键盘输入。2.3 设计环境（1）WINDOWS 7 系统（2）Visual C+2.4 开发语言C 语言3 分析和设计3.1 模块设计定义链表结点类型struct node 表示结点中的信息 , 信息包括数据域 data（用于存放结点中的有用数据）以及指针域next（用于存放下一个结点的地址） ，并将链表结点类型名改为 NODE 。如下所示：.typedef struct nodeint data;struct node *next;NODE

4、;定义函数 NODE *create_llist_sorted()，用来创建非递减有序带头结点的单链表，定义四个指针 NODE*h,*p,*q,*s ，头指针指向第一个结点，并且分配空间给头指针 h，使头指针不为空， *p 指向单链表中某一结点， *q 指向 *p 的前驱 , *s 指向输入的数据， 将数据逐个输入， 将输入的数据通过循环语句不断进行比较， 其中先使 *q 指向*h 所指位置， *p 指向 * h 的下一个位置，不断将输入的每一个数据与链表中的数据相比较，找到插入位置，然后移动 *p ，*q ，直到 * p 为空指针且 *s 所指数据小于等于 *p 所指数据，从而使数据有序，最

5、后返回头指针。详细程序见后文中的具体代码实现。定义函数 void output()，用来输出头指针 h 所指的单链表，因为此链表有头结点， 所以定义一个指针 NODE *p ，*p 指向 h 的下一个位置，不断地将 *p 所指数据输出并且移动 *p ，直到 *p 为空指针。详细程序见后文中的具体代码实现。定义函数 void insert(NODE *h, int x) ，使元素 x 插入到单链表 h 中之后链表中数据仍有序，定义三个指针NODE *p,*q,*m ，*q 指向头指针所指位置 ，*p 指向 *q 的下一个位置， *m 指向要插入的数据 x，将数据插入链表中去后将数据不断进行比较，

6、直至 *p 为空指针且 *m 所指数据小于等于 *p 所指数据，移动 *p , *q , 使数据仍然有序。详细程序见后文中的具体代码实现。定义函数 NODE *del(NODE *h, int i) ，用于删除单链表 h 中第 i 个结点，定义两个指针 *p ，*q ，用指针 p 来从第一个结点开始查找需要删除的结点，指针 q 是指针 p 的前驱，查找过程中，不断移动指针 p，q，直至找到需要删除的结点，如果 *p 为空指针，则表示链表中没有需要删除的结点，最后返回头指针。详细程序见后文中的具体代码实现。主函数主要是采用开关分支语句对几个子函数进行调用。3.2 系统模块流程图.开 始输出菜单1

7、NY输入 nn=1NY调用创建单链表函NODE*create_llist_sn=2Norted();Y数调 用 输 出 函 数voidn=3Noutput(NODEY*h)调用插入函数voidNinsert(NODE*h, intn=4Yx);并输出调 用 删 除 函 数NODEn=0*del(NODE*h, int i)Y结 束图 3.1 系统模块流程图.3.3 主要模块的流程图（1）输出函数流程图（如图3.2）p=h-nextNp!=NULL ？Y输出 p-datap=p-next图 3.2. 输出函数流程图（2）插入函数流程图（如图3.3）m=(NODE *)malloc(sizeof(

8、NODE);m-data=x; q=h ； p=q-next;p!=NULL&m-dNatap-dataYq=q-next;p=p-next;m-next=p;q-next=m;图 3.3 插入函数流程图.（3）删除函数流程图 （如图 3.4）p=h输入待删结点iNp!=NULL&p-data!=i ？Yq=p;p=p-next ;p=h？NYN ？Np=NULLYh=h-next;free(p);q-next=p-next;free(p);printf(not been findn ”)图 3.4 删除函数流程图.（ 4） 创建单链表函数流程图（如图 3.5）h=(NODE *)malloc

9、(sizeof(NODE);h-next=NULL输入 xx!= -1NYs=(NODE * )malloc(sizeof(NODE)q=h,p=h-next ;s-data=x; s-next=NULL;Np!=NULL&s-datap-data？Yq-next=ss-next=p;p=ps-next=p;-next,q=q-next输入 x图 3.5 创建单链表函数流程图.4 具体代码实现/* 单链表的基本操作 */#includestdio.h#includemath.h#includestring.h#includestdlib.htypedef struct nodeint data

10、;struct node *next;NODE;/ * 链表结点类型定义 */*函数声明 */NODE *create_llist_sorted();/* 建立一个非递减有序的带头结点的单链表，返回其头指针*/void output(NODE *h);/ * 输出头指针 h 所指单链表 */void insert(NODE *h, int x);/ * 将元素 x 插入到单链表 h 中仍有序 */ NODE *del(NODE *h, int i);/ * 删除单链表 h 中第 i 个结点 */*主函数 */void main()NODE *head;int x,i,n;printf( *单链

11、表的基本操作 *n); /* 输出菜单 */printf(1.建立 n);printf(2.输出 n);printf(3.插入 n);printf(4.删除 n);printf(0.退出 n);while(1)printf( 请选择： );scanf(%d,&n);switch(n)case 1:head=create_llist_sorted();break;case 2:output(head);break;.case 3:printf(please input inserted data:);scanf(%d,&x);insert(head,x);output(head);break;c

12、ase 4:printf(please input deleted location:);scanf(%d,&i);del(head,i);output(head);break;case 0:exit(0);default:printf( 输入错误，请重新选择 !n);/*子函数 */NODE *create_llist_sorted()/* 建立一个非递减有序的带头结点的单链表，返回其头指针*/int x;NODE *h,*p,*q,*s; /*p指向单链表中某一结点，q 指向 *p 的前驱 */h=(NODE *)malloc(sizeof(NODE);h-next=NULL;scanf(

13、%d,&x);while(x!=-1)s=(NODE *)malloc(sizeof(NODE);s-data=x; s-next=NULL;for(q=h,p=h-next;p!=NULL&s-datap-data;p=p-next,q=q-next);/* 不断比较，找到插入位置。注意：循环条件p!=NULL必须先判断，即放在 &左边 */q-next=s;s-next=p;scanf(%d,&x);return h;void output(NODE *h)/ * 输出头指针 h 所指单链表 */NODE *p;p=h-next;while(p!=NULL).printf(%d ,p-da

14、ta); p=p-next;printf(n);NODE *del(NODE *h, int i)/ * 删除单链表 h 中第 i 个结点 */NODE*p,*q;p=h;while(p!=NULL&p-data!=i)q=p;p=p-next;if(p=h)h=h-next;free(p);else if(p=NULL)printf(not been findn);elseq-next=p-next;free(p);return(h);void insert(NODE *h, int x)/ * 将元素 x 插入到单链表 h 中仍有序 */ NODE *p,*q,*m;m=(NODE *)m

15、alloc(sizeof(NODE);m-data=x; q=h;p=q-next;while(p!=NULL&m-datap-data)q=q-next; p=p-next;m-next=p; q-next=m;.5 课程设计总结5.1 程序运行结果输入源程序后，先进行调试，经调试无错误后开始运行，屏幕上会显示菜单，会出现提示语“请选择” ，选择 1 即建立了一个链表，然后键入一组正整数，以-1 标志结束，按回车键；继续选择2 即执行输出函数，按回车键后屏幕上会输出之前键入的数据，按回车键；继续选择3 即执行插入函数，按回车键后键入一个需要插入的数据，按回车键屏幕上输出插入数据后的一组新数据

16、，按回车键；继续选择4 即执行删除函数，按回车键后键入一个需要删除的数的所在的节点，继续按回车键屏幕上会输出删除节点后的一组新数据，按回车键；继续选择0 即退出程序，运行结果如下图所示图 5.1 运行结果示意图5.2 课程设计体会总体来说，这个课程设计的优势在于条理较为清晰，内容比较充实，源程序也是比较清晰明了的， 方便使用，不足之处在于流程图不够规范整洁，其他地方都还有待.提高。我觉得课程设计中最核心的部分是编程， 在编程的过程中， 最关键的是要有扎实的知识功底，最重要的是需要细心和耐心。拥有扎实的知识功底，看到课题，我们便能灵活运用老师所教的知识， 较为清晰地、 快速地想出大概的程序框架，

17、 然后再正式地进行编程。 在编程时，细心是必要的， 因为一个小小的错误便会导致整个程序不能正常运行，便要进行一系列的复杂的调试工作，所以细心能避免一些不必要的麻烦。同时，耐心也是必不可少的， 当我们在编程过程中可能会遇到一些困惑和难点以及错误，需要我们有一定的耐心坚持下去，不轻言放弃，不断地进行调试和运行，有不懂的地方和同学讨论，向老师请教，直到使程序正常运行。通过这次的课程设计， 我收获了许多， 了解了如何正确规范地进行课程设计， 为以后能快速高效进行课程设计打下一定的基础。参考文献1 黄同成，周红波程序设计基础教程（C 语言） M 湖南人民出版社，20112 黄同成，黄磊程序设计实践教程（C 语言） M 湖南人民出版社， 20113 谭浩强 C 程序设计（第三版）M 北京：清华大学出版社，2005致谢首先，我想要感谢编写 C 语言相关书籍的各位老师以及我们的授课老师，让我们了解并掌握了有关 C 语言的大量的基础知识，让我们有足够的知识储备和扎实的知识功底来顺利地进行我们的课程设计。然后，我要感谢