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

.

课程设计(论文)

题 目 名 称 单链表的基本操作
课 程 名 称 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系统模块流程图

开 始

输出菜单

1
N

Y
输入n

n=1
N

Y
调用创建单链表函NODE*create_llist_sorted();
数
n=3
n=2?

N

Y
调用输出函数void output(NODE *h)

N

n=0??
n=4
n=4?
Y

调用插入函数void insert(NODE *h, int x);并输出
N

结 束
调用删除函数NODE *del(NODE *h, int i)
退出
Y

结束

Y

图3.1系统模块流程图

3.3主要模块的流程图
（1）输出函数流程图（如图3.2）

p=h->next

p!=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->data>p->data

N

Y
q=q->next;p=p->next;

m->next=p;q->next=m;

图3.3插入函数流程图
（3）删除函数流程图（如图3.4）

p=h

输入待删结点i

p!=NULL&&p->data!=i？

N

Y
q=p;p=p->next;

p=h？

N

Y p=NULL？

N N

h=h->next;free(p);
Y
q->next=p->next;free(p);

printf("not been find\n”)

图3.4删除函数流程图

（4）创建单链表函数流程图（如图3.5）

h=(NODE *)malloc(sizeof(NODE));
h->next=NULL

输入x

x!= -1

N
Y
s=(NODE *)malloc(sizeof(NODE))

q=h,p=h->next ;s->data=x; s->next=NULL;

p!=NULL&&s->data>p->data？

N

Y
q->next=s

s->next=p;s->next=p;p=p->next,q=q->next

输入x

图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 课程设计体会
总体来说，这个课程设计的优势在于条理较为清晰，内容比较充实，源程序也是比较清晰明了的，方便使用，不足之处在于流程图不够规范整洁，其他地方都还有待提高。
我觉得课程设计中最核心的部分是编程，在编程的过程中，最关键的是要有扎实的知识功底，最重要的是需要细心和耐心。拥有扎实的知识功底，看到课题，我们便能灵活运用老师所教的知识，较为清晰地、快速地想出大概的程序框架，然后再正式地进行编程。在编程时，细心是必要的，因为一个小小的错误便会导致整个程序不能正常运行，便要进行一系列的复杂的调试工作，所以细心能避免一些不必要的麻烦。同时，耐心也是必不可少的，当我们在编程过程中可能会遇到一些困惑和难点以及错误，需要我们有一定的耐心坚持下去，不轻言放弃，不断地进行调试和运行，有不懂的地方和同学讨论，向老师请教，直到使程序正常运行。
通过这次的课程设计，我收获了许多，了解了如何正确规范地进行课程设计，为以后能快速高效进行课程设计打下一定的基础。
参考文献
[1]黄同成，周红波．程序设计基础教程（C语言）[M]．湖南人民出版社，2011．
[2]黄同成，黄磊．程序设计实践教程（C语言）[M]．湖南人民出版社，2011．
[3]谭浩强．C程序设计（第三版）[M]．北京：清华大学出版社，2005．
致 谢
首先，我想要感谢编写C语言相关书籍的各位老师以及我们的授课老师，让我们了解并掌握了有关C语言的大量的基础知识，让我们有足够的知识储备和扎实的知识功底来顺利地进行我们的课程设计。
然后，我要感谢那些在我编写程序时给予我许多帮助和指导的同学和老师，因为是他们让我在百思不得其解的时候豁然开朗，让我理清思路，然后经过不断试验，不断调试运行，才得以把这个程序很好地完成。在同学的帮助、老师的指导过程中，我也学到了许多自己所缺乏的知识，让我又多了几种编程的方法及思路。在这个过程中，我也学会了如何撰写课程设计论文，了解了撰写的格式以及方式。
同时，我也要感谢学校领导们给予我们在课程设计过程中的支持与帮助，正是因为他们给我们提供了良好的实验室以及实验器材，才能让我们能在良好舒适的环境内顺利地进行实验，进而顺利完成我们的编程以及课程设计。

部分内容来源于网络，有侵权请联系删除！