《单链表的基本操作 c语言课程设计》由会员分享，可在线阅读，更多相关《单链表的基本操作 c语言课程设计（14页珍藏版）》请在金锄头文库上搜索。
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致 谢131 前言 我们这学期学习了开关语句，循环语句、链表、函数体、指针等的应用，我们在完成课程设计任务时就主要
2、用到这些知识点，本课题是单链表的简单操作，定义四个子函数分别用来创建链表、输出链表、插入数据以及删除数据，主函数中主要用到开关语句来进行选择调用哪个子函数，下面就是课程设计的主要内容。2 需求分析2.1 课程设计目的学生在教师指导下运用所学课程的知识来研究、解决一些具有一定综合性问题的专业课题。通过课程设计（论文），提高学生综合运用所学知识来解决实际问题、使用文献资料、及进行科学实验或技术设计的初步能力，为毕业设计（论文）打基础。2.2 课程设计任务输入一组正整数，以-1标志结束，用函数实现：（1）将这些正整数作为链表结点的data域建立一个非递减有序的单链表，并输出该单链表；（2）往该链表中
3、插入一个正整数，使其仍保持非递减有序，输出插入操作后的单链表；（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;定义函数NODE *create_llist_sort
4、ed()，用来创建非递减有序带头结点的单链表，定义四个指针NODE*h,*p,*q,*s，头指针指向第一个结点，并且分配空间给头指针h，使头指针不为空，*p指向单链表中某一结点，*q指向*p的前驱,*s指向输入的数据，将数据逐个输入，将输入的数据通过循环语句不断进行比较，其中先使*q指向*h所指位置，*p指向*h的下一个位置，不断将输入的每一个数据与链表中的数据相比较，找到插入位置，然后移动*p，*q，直到*p为空指针且*s所指数据小于等于*p所指数据，从而使数据有序，最后返回头指针。详细程序见后文中的具体代码实现。定义函数void output()，用来输出头指针h所指的单链表，因为此链表有
5、头结点， 所以定义一个指针NODE *p，*p指向h的下一个位置，不断地将*p所指数据输出并且移动*p，直到*p为空指针。详细程序见后文中的具体代码实现。定义函数void insert(NODE *h, int x)，使元素x插入到单链表h中之后链表中数据仍有序，定义三个指针NODE *p,*q,*m，*q指向头指针所指位置，*p指向*q的下一个位置，*m指向要插入的数据x，将数据插入链表中去后将数据不断进行比较，直至*p为空指针且*m所指数据小于等于*p所指数据，移动*p,*q,使数据仍然有序。详细程序见后文中的具体代码实现。定义函数NODE *del(NODE *h, int i)，用于删
6、除单链表h中第i个结点，定义两个指针*p，*q，用指针p来从第一个结点开始查找需要删除的结点，指针q是指针p的前驱，查找过程中，不断移动指针p，q，直至找到需要删除的结点，如果*p为空指针，则表示链表中没有需要删除的结点，最后返回头指针。详细程序见后文中的具体代码实现。主函数主要是采用开关分支语句对几个子函数进行调用。3.2系统模块流程图开 始输出菜单 1N Y输入n n=1 N Y调用创建单链表函NODE*create_llist_sorted();数n=3n=2?NY调用输出函数void output(NODE *h)Nn=0?n=4n=4?Y调用插入函数void insert(NODE
7、*h, int x);并输出N结 束调用删除函数NODE *del(NODE *h, int i)退出Y结束Y 图3.1系统模块流程图3.3主要模块的流程图（1）输出函数流程图（如图3.2）p=h-nextp!=NULL？N Y输出p-data p=p-next 图3.2. 输出函数流程图（2）插入函数流程图（如图3.3）m=(NODE *)malloc(sizeof(NODE);m-data=x; q=h；p=q-next;m-data=x; q=h;p=q-next;q=h;p=q-next;p!=NULL&m-datap-dataN Yq=q-next;p=p-next;m-next=p
8、;q-next=m;图3.3插入函数流程图（3）删除函数流程图（如图3.4）p=h输入待删结点ip!=NULL&p-data!=i？NYq=p;p=p-next;p=h？NYp=NULL？NNh=h-next;free(p); Yq-next=p-next;free(p);printf(not been findn”)图3.4删除函数流程图（4）创建单链表函数流程图（如图3.5）h=(NODE *)malloc(sizeof(NODE);h-next=NULL输入xx!= -1N Ys=(NODE *)malloc(sizeof(NODE) q=h,p=h-next ;s-data=x; s-
9、next=NULL;p!=NULL&s-datap-data？NYq-next=ss-next=p;s-next=p;p=p-next,q=q-next输入x图3.5创建单链表函数流程图4 具体代码实现/*单链表的基本操作*/#includestdio.h#includemath.h#includestring.h#includestdlib.htypedef struct nodeint data; struct node *next;NODE;/*链表结点类型定义*/*函数声明*/NODE *create_llist_sorted();/*建立一个非递减有序的带头结点的单链表，返回其头指针
10、*/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(*单链表的基本操作*n); /*输出菜单*/ printf( 1. 建立n); printf( 2. 输出n); printf( 3. 插入n); printf( 4. 删除n); printf( 0. 退出n); while(1) printf(请选择
11、：); 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; case 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(%d,&x); while(x!=-1) s=(NODE *)malloc(sizeof(NODE); s-data=x; s-next=NULL; for(q=h,p=h-n
