课程设计(论文)题目名称单链表的基本操作课程名称C语言程序课程设计学生姓名学号系、专业信息工程系、网络工程专业指导教师成娅辉2013年6月6 日目录1 前言 (3)2 需求分析 (3)2.1 课程设计目的 (3)2.2 课程设计任务 (3)2.3 设计环境 (3)2.4 开发语言 (3)3 分析和设计 (3)3.1 模块设计 (3)3.2 系统流程图 (4)3.3 主要模块的流程图 (6)4 具体代码实现 (9)5 课程设计总结 (12)5.1 程序运行结果 (12)5.2 课程设计体会 (12)参考文献 (13)致谢 (13)1 前言我们这学期学习了开关语句，循环语句、链表、函数体、指针等的应用，我们在完成课程设计任务时就主要用到这些知识点，本课题是单链表的简单操作，定义四个子函数分别用来创建链表、输出链表、插入数据以及删除数据，主函数中主要用到开关语句来进行选择调用哪个子函数，下面就是课程设计的主要内容。

2 需求分析2.1 课程设计目的学生在教师指导下运用所学课程的知识来研究、解决一些具有一定综合性问题的专业课题。

通过课程设计（论文），提高学生综合运用所学知识来解决实际问题、使用文献资料、及进行科学实验或技术设计的初步能力，为毕业设计（论文）打基础。

2.2 课程设计任务输入一组正整数，以-1标志结束，用函数实现：（1）将这些正整数作为链表结点的data域建立一个非递减有序的单链表，并输出该单链表；（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 node{int data;struct node *next;}NODE;定义函数NODE *create_llist_sorted()，用来创建非递减有序带头结点的单链表，定义四个指针NODE*h,*p,*q,*s，头指针指向第一个结点，并且分配空间给头指针h，使头指针不为空，*p指向单链表中某一结点，*q指向*p的前驱,*s指向输入的数据，将数据逐个输入，将输入的数据通过循环语句不断进行比较，其中先使*q指向*h所指位置，*p指向*h的下一个位置，不断将输入的每一个数据与链表中的数据相比较，找到插入位置，然后移动*p，*q，直到*p为空指针且*s所指数据小于等于*p所指数据，从而使数据有序，最后返回头指针。

详细程序见后文中的具体代码实现。

定义函数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，将数据插入链表中去后将数据不断进行比较，直至*p为空指针且*m所指数据小于等于*p所指数据，移动*p,*q,使数据仍然有序。

详细程序见后文中的具体代码实现。

定义函数NODE *del(NODE *h, int i)，用于删除单链表h中第i个结点，定义两个指针*p，*q，用指针p来从第一个结点开始查找需要删除的结点，指针q是指针p的前驱，查找过程中，不断移动指针p，q，直至找到需要删除的结点，如果*p为空指针，则表示链表中没有需要删除的结点，最后返回头指针。

详细程序见后文中的具体代码实现。

主函数主要是采用开关分支语句对几个子函数进行调用。

3.2系统模块流程图图3.1系统模块流程图3.3主要模块的流程图（1）输出函数流程图（如图3.2）图3.2. 输出函数流程图（2）插入函数流程图（如图3.3）图3.3插入函数流程图（3）删除函数流程图（如图3.4）图3.4删除函数流程图（4）创建单链表函数流程图（如图3.5）图3.5创建单链表函数流程图4 具体代码实现/*单链表的基本操作*/#include"stdio.h"#include"math.h"#include"string.h"#include"stdlib.h"typedef struct node{int data;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("********单链表的基本操作********\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;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->next;p!=NULL&&s->data>p->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->data); 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 find\n");else{q->next=p->next;free(p);}return(h);}void insert(NODE *h, int x)/*将元素x插入到单链表h中仍有序*/ {NODE *p,*q,*m;m=(NODE *)malloc(sizeof(NODE));m->data=x; q=h;p=q->next;while(p!=NULL&&m->data>p->data){q=q->next; p=p->next;}m->next=p; q->next=m;}5 课程设计总结5.1 程序运行结果输入源程序后，先进行调试，经调试无错误后开始运行，屏幕上会显示菜单，会出现提示语“请选择”，选择1即建立了一个链表，然后键入一组正整数，以-1标志结束，按回车键；继续选择2即执行输出函数，按回车键后屏幕上会输出之前键入的数据，按回车键；继续选择3即执行插入函数，按回车键后键入一个需要插入的数据，按回车键屏幕上输出插入数据后的一组新数据，按回车键；继续选择4即执行删除函数，按回车键后键入一个需要删除的数的所在的节点，继续按回车键屏幕上会输出删除节点后的一组新数据，按回车键；继续选择0即退出程序，运行结果如下图所示图5.1运行结果示意图5.2 课程设计体会总体来说，这个课程设计的优势在于条理较为清晰，内容比较充实，源程序也是比较清晰明了的，方便使用，不足之处在于流程图不够规范整洁，其他地方都还有待提高。

我觉得课程设计中最核心的部分是编程，在编程的过程中，最关键的是要有扎实的知识功底，最重要的是需要细心和耐心。