单链表的操作实现

1、武汉理工大学数据结构课程设计学 号： 课 程 设 计题 目单链表的操作实现学 院计算机科学与技术学院专 业软件工程专业班 级班姓 名指导教师夏红霞20年月日单链表的操作实现摘要随着社会的发展，电脑的作用已经愈加明显。数据结构对人们的生活也起到了很大的改善作用，尤其是线性表的出现将很多复杂的东西简便化了。而线性表中最简单的就是单链表了。单向链表是最基本的所有链接的数据结构。单链表是一个简单的序列动态分配的对象，其中每个指的是其继任者的名单。尽管这种明显的简单性，有无数的实施情况的变化。但是其基本操作也只有建立、插入、删除和输出。关键字：单链表；基本操作；C语言AbstractWith the d

2、evelopment of society, the computer has become increasingly obvious. Data-Structure also played a significant effect. Especially the appearance of Linear List makes some complex things simpler. And the simplest of Linear List is the singly-linked list. The singly-linked list is the most basic of all

3、 the linked data structures. A singly-linked list is simply a sequence of dynamically allocated objects, each of which refers to its successor in the list. Despite this obvious simplicity, there are myriad implementation variations. The basic operations are creating, inserting, deleting and output.K

4、eywords: the singly-linked list; the basic operations; C language1 引言1.1 选题背景及意义中国正在大步跨入信息化社会，人们的生活工作与通信、信息的关系日益紧密，信息化社会在改变着我们的生活方式与工作习惯。当然，计算机在信息化时代有着不可替代的作用。计算机产生的各类程序大大方便了人们的生活和工作。计算机诞生之初，受到硬件的影响，它所运行的速度并不快，且不能完成较为复杂的指令，这时，数据结构诞生了。数据结构是计算机编程的基础，有一个好的数据结构，设计的程序才会更简洁，条理更清晰。而数据结构中最基本的元素之一就是单链表。1.2 单

5、链表用一组地址任意的存储单元存放线性表中的数据元素。以元素(数据元素的映象) + 指针(指示后继元素存储位置)= 结点(表示数据元素 或 数据元素的映象)。以“结点的序列”表示线性表称作线性链表（单链表）。单链表是一种链式存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i。2 需求分析单链表在C语言中是一种非常常见的结构，而在C+中的实现却又有不同，在一些地方更简单，更严密。同时，由于C+的一些特点，使它具有C语言所不具有的“安全化”。本程序实现了单链表的创建、插入、删除和查找。本演示程序用VC+6.0编写

6、，完成单链表的生成，任意位置的插入、删除，以及确定在单链表中的某一位置的元素。输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的位置。在所有输入中，元素的值都是整数。输出的形式：在所有操作中都显示操作是否正确以及操作后单链表的内容。 其中删除操作后显示删除的元素的值，查找操作后显示要查找的元素。程序所能达到的功能：完成单链表的建立、插入、删除、查找和输出操作。3 数据结构设计与算法设计本课程设计只要求实现链表的几项基本操作，任务相对比较简单，建立一个单链表然后再对它其中的元素进行插入等操作。大致过程如下：插入节点删除节点查找

7、节点显示单链表创建单链表3.1 详细设计流程单链表的存储结构为：typedef struct LNodeint data;struct LNode *next;LNode,*LinkList;3.1.1 创建单链表开始定义结构体变量p=NULL,q=L定义整型变量i=0Ni<n输出LY为p分配内存空间结束输入数值并存入p->datai+p->next = q->nextq->next = pq=q->next其主要代码如下：LinkList CreateList_L(LinkList L,int n) /创建链表 int i; LinkList p = NU

8、LL; LinkList q=L; for(i=0;i<n;i+) p = (LinkList)malloc(sizeof(LNode); scanf("%d",&p->data); p->next = q->next; q->next = p;q=q->next; return L;3.1.2 显示单链表开始输出“现在的链表元素为：”L=L->nextN输出L->dataYL-next=NULL结束其主要代码如下：void output_list(LinkList L) /输出printf("现在链表的元素

9、为：");doL=L->next;printf("%d->",L->data);while(L->next);printf("n");3.1.3 插入节点开始结束定义结构体变量s=NULL,p=L输出LY定义整型变量j=0Np!=NULLp=NULL&&j<i-1|j>i-1NYp=p->next s->data = ej+s->next = p->nextp->next = s其主要代码如下：LinkList ListInsert(LinkList L,int

10、i,int e) /插入 int j = 0; LinkList s = NULL,p = NULL; p = L; while(p&&j<i-1) p = p->next; j+; if(!p|j>i-1) printf("输入的位置不合法！n"); return L; s = (LinkList)malloc(sizeof(LNode); s->data = e; s->next = p->next; p->next = s; return L;3.1.4 删除节点开始结束定义结构体变量q=NULL,p=L输出L

11、Y定义整型变量j=0Np!=NULLp=NULL&&j<i-1|j>i-1NYp=p->next q =->nextj+p->next = q->next其主要代码如下：LinkList ListDelete(LinkList L,int i) /删除 int j; LinkList q = NULL,p = NULL; p = L; j = 0; while(p->next&&j<i-1) p = p->next; j+; if(!(p->next)|j>i-1) printf("输入

12、的位置不合法！n"); return L; printf("删除的是%d",p->next->data); q = p->next; p->next = q->next; free(q); return L;3.1.5 查找节点其主要代码如下：void GetElem(LinkList L,int i) /查找 int j,e; LinkList p = NULL; if(i<1|i>ListLength(L) printf("输入的位置不合法！n"); else p = L->next;j =

13、1;while(j<i)p = p->next; j+; e = p->data; printf("第%d位的数据元素为%dn",i,e);开始定义结构体变量p=NULL定义整型变量j,eY I<1| 结束i>L.lengthNp = L->next 输出ej=1Nj<ie=p->dataYp = p->nextj+4 程序实现及测试4.1 运行环境在本课程设计中，系统开发平台为Windows7,程序设计语言为Visual C+6.0，程序的运行环境为Visual C+ 6.0。Visual C+一般分为三个版本:学习版

14、、专业版和企业版，不同的版本适合于不同类型的应用开发。实验中可以使用这三个版本的任意一种，在本课程设计中，以Visual C+ 6.0为编程环境。Microsoft Visual C+ 6.0是Microsoft公司的Microsoft Visual Studio 6.0开发工具箱中的一个C+程序开发包。Visual C+包中除包括C+编译器外，还包括所有的库、例子和为创建Windows应用程序所需要的文档。自1993年Microsoft公司推出Visual C+1.0后，随着其新版本的不断问世，Visual C+已成为专业程序员进行软件开发的首选工具。Visual C+从最早期的1.0版本，

15、发展到最新的7.0版本，Visual C+已经有了很大的变化，在界面、功能、库支持方面都有许多的增强。最新的7.0版本在编译器、MFC类库、编辑器以及联机帮助系统等方面都比以前的版本做了较大改进。 虽然微软公司推出了Visual C+.NET(Visual C+7.0)，但它的应用的很大的局限性，只适用于Windows 2000,Windows XP和Windows NT4.0。所以实际中，更多的是以Visual C+6.0为平台。Visual C+ 6.0是Microsoft公司推出的目前使用最广泛的基于Windows平台的可视化编程环境。Visual C+ 6.0是在以往版本不断更新的基础

16、上形成的，由于其功能强大，灵活性好，完全课扩展以及具有强大的Internet支持，因而在各种C+语言开发工具中脱颖而出，成为目前最为流行的C+语言集成开发环境。 Visual C+ 6.0秉承Visual C+以前版本的优异特性，为用户提供了一套良好的可视化开发环境：主要包括文本编辑器、资源编辑器、工程创建工具、Debugger调试器等等。用户可以在集成开发环境中创建工程、打开工程、建立、打开和编辑文件、编译、链接、运行、调试应用程序。 4.2 部分运行结果4.2.1 链表的建立程序运行之初会看到系统提示，输入链表的内容，结果如下：4.2.2 节点的插入在第三个节点处插入6，其结果如下：4.2

17、.3 节点的删除将第二个节点删除，其结果如下：4.2.4 查找节点查找第五个节点的数值，其结果如下：4.2.5 结束程序选择“0”结束程序，结果如下：5 结束语数据结构是一门纯属于设计的科目，它需用把理论变为上机调试。在学习科目的第一节课起，夏老师就为我们阐述了它的重要性。对我们来说它具有一定的难度。不仅由于本身它很难，还因为在学习C语言时其中的指针结构体没掌握，而这两个知识点恰好是学习数据结构的前提。正如老师所说，由于基础没打好，所以学起来特别困难，老师布置的练习题也经常不会做，很感谢老师的不厌其烦的讲解自己不懂的地方，以及学委在平时学习中对我的帮助。在学习数据结构的课程中，由于c语言的基础并不是很扎实，所以学起来很吃力。每次老师布置的作业都要经过千思万虑后才能完成，而老师布置的上机实验更是让我郁闷之极，发展到最后看到数据结构的实验就如沐秋风般瑟瑟发抖。而如今的我，在完成这次课程设计后已经能够沉着应对部分问题。我已经走出了关键的一步，相信数据结构不会再成为我的绊脚石了。通过本次课程设计感觉自己有较大的提高。对于问题的思考要全面，各种情况都要考虑到以备特殊情况的发生。对待学习和生活中遇到的问题也是这样，只有这样才能在遇到突发情况的时候临危不惧。数据结构我掌握得不是很好，在这条道路上还有很漫长的路要走，但是，因为尚未成熟所以才有发展的空间，我会更努力地学习，