数据结构课程设计单链表

1、目录1 选题背景 12 方案与论证 22.1 链表的概念和作用 22.3 算法的设计思想 32.4 相关图例 42.4.1 单链表的结点结构 42.4.2 算法流程图 43 实验结果 53.1 链表的建立 53.2 单链表的插入 53.3 单链表的输出 63.4 查找元素 63.5 单链表的删除 73.6 显示链表中的元素个数（计数） 84 结果分析 94.1 单链表的结构 94.2 单链表的操作特点 94.2.1 顺链操作技术 94.2.2 指针保留技术 94.3 链表处理中的相关技术 95 设计体会及今后的改进意见 10参考文献 11附录代码： 121 选题背景陈火旺院士把计算机 60 多

2、年的发展成就概括为五个 “一”：开辟一个新时代 信息时代，形成一个新产业 信息产业，产生一个新科学 计算机科学 与技术，开创一种新的科研方法 计算方法，开辟一种新文化 计算机文化，这一概括深刻影响了计算机对社会发展所产生的广泛而深远的影响。数据结构和算法是计算机求解问题过程的两大基石。著名的计算机科学家P.Wegner指出，“在工业革命中其核心作用的是能量，而在计算机革命中其核心 作用的是信息”。计算机科学就是“一种关于信息结构转换的科学” 。信息结构（数 据结构）是计算机科学研究的基本课题，数据结构又是算法研究的基础。2 方案与论证2.1 链表的概念和作用链表是一种链式存储结构， 链表属于线

3、性表， 采用链式存储结构， 也是常用 的动态存储方法。链表中的数据是以结点来表示的，每个结点的构成：元素 （ 数 据元素的映象 ） + 指针（指示后继元素存储位置 ） ，元素就是存储数据的存储单 元，指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性链表（单链表）单链表是链式存取的结构， 为找第 i 个数据元素， 必须先找到第 i-1 个数 据元素。因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i 单链表1、链接存储方法 链接方式存储的线性表简称为链表（ Linked List ）。 链表的具体存储表示为： 用一组任意的存储单元来存放线性表的结点（这组存储单

4、元既可以是连 续的，也可以是不连续的） 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间 的逻辑关系， 在存储每个结点值的同时， 还必须存储指示其后继结点的地址 （或 位置）信息（称为指针（ pointer ）或链 （link） ）、I 、+ :注意：链式存储是最常用的存储方式之一， 它不仅可用来表示线性表， 而且可用来 表示各种非线性的数据结构。2、链表的结点结构IIII data | next Idata 域- 存放结点值的数据域next 域- 存放结点的直接后继的地址（位置）的指针域（链域）链表通过每个结点的链域将线性表的 n 个结点按其逻辑顺序链接在一起 的。每个结点只有

5、一个链域的链表称为单链表（Sin gle Linked List ）3、头指针 head 和终端结点指针域的表示 单链表中每个结点的存储地址是存放在其前趋结点 next 域中，而开始结点 无前趋，故应设头指针 head 指向开始结点。链表由头指针唯一确定，单链表可以用头指针的名字来命名。 终端结点无后继，故终端结点的指针域为空，即 NULL。2.2 实验的基本要求（软硬件）用 VC+6.0 软件平台，操作系统： WindowsXP 硬件：内存要求：内存大小 在256MB其他配置一般就行。2.3 算法的设计思想（a）定义一个创建链表的函数，通过该头插法创建一个带头结点的链表，在接下来的链表操作中

6、使用。（b）定义输出链表的算法，遍历结点的指针域判断是否为空， 如果不为空则输出其数据域，直到指针域为空为止。（c）定义一个遍历查找的算法，通过遍历的数据域，分别与要查询的元素进行比较，如果查找到则返回并输出，如入查找失败则返回错误提示信息。（d）定义插入结点的算法，首先查找指针域为空的结点，并申请空间插入在结点的后边，并且将其指针域置空。（e）定义删除节点的操作，这个算法用于对链表中某个多余节点的删除工作，其关键在于前驱结点的保留，查找到需删除的结点，将其删除，并将其后 继结点连到其前驱结点。2.4相关图例单链表的结点结构如图2-1所示,为单链表的结点结构示意图:Data 域Next域图2-

7、1单链表的结点结构算法流程图如图2-2所示，为此算法流程图：图2-2算法流程图3实验结果3.1链表的建立I E;氐仲溢握戢谭程设ttV舉覆设计占毡詞.Debug'遲程设t单槌表的茴单操作1单毬表的建立2单槌表的插入2单機表的输岀4单梯表的查找5单锂表的删除6单槌表的长度0逋出1帝建立单错表用"0"来结東输入1 8 7 6 4 10 -3 5 0初始化后的单错表为：5 -8 10 4 6 7 8 1 单错表的简单操作图3-1链表的建立3.2单链表的插入E:便铀癣誰粽程迓计辭说计-筆頤2曲ug锻单链表的面单操作1单槌表的建立2单链表的插入3单链表的输出4单链表的查找5单

8、链表的删除&单链表的长度0退岀2请输入需要插入的元素，22插入后的单链表为；5 -8 10 4 6 7 8 1 22罩链表的简单操作图3- 2单链表的插入3.3单链表的输出B E:仪伸站结槪课程设til保囹S计-单謹表0命罔荀单IS表的简单操作1单链表的建立2单铸表的插入3单链表的输出4单链表的査找5单链裘的删除&单链表的长度0退岀3单链表的输岀为：5 -8 10 4 6 7 8 1 22 单槌表的简单握作图3-3输出单链表元素3.4查找元素单链表的输出为：5吃10 4 6 7 E 1 22 单槌表的简单撫作1单链表的建立2单链表的插入3单链表的输岀4单链表的查找5单番表的删除

9、6单锻表的长度0退岀4请输入需要查找的?£>= 10 匿找成功单槌耒的简单攧作图3-4查找成功卑链表的简单操作1单槌耒的建立2单销表的插人3单链表的输岀4单错表的査找6单错表的删除5单链表的长度0退岀4请输入需要查找的元素：0 查找失败单错表的简单操作图3-5查找失败3.5单链表的删除«呂懐件傭矚结构憔程童计、课程设计臺链歸DEbug蜡若单链表的面单操作1单榊表的建立2单错表的插入3单链表的输岀4单错表的查找5单错表的删除6单错表的长度0退出r谙输入需要删除的元素泪删除之后的单链表为；5 10 4 6 7 3 1 22 单链表的简单操作图3-6删除成功-丘懐件昨结枸谭

10、程没计课程没计-单链飄加brg煤程设单链表的简单操作1单链表的建立2单的插入3单链表的输岀4单琏表的查找5单琏表的删除6单链表的长度0邁出5请输人需要删除的兀素：0刪除失晦没有找到相应的元素删除之后的单链表为：5 10 4 6 7 8 1 22单槌表的简单操作图3-6删除失败3.6显示链表中的元素个数（计数）E;懐件腳瞬构谭程设计鴉程设计单与偉程ii删除失败*没有找到相应的兀案删除之后的单错表为：6 10 4 6 7 8 1 22 单链表的简单操作1单链表的建立2单链表的插入3单链表的输岀4单链表的查找5单链表的删除5单链表的长度0退岀u单链耒中一共有汁元素单琏表的简单操作图3-7输出长度4结

11、果分析4.1单链表的结构一般情况下，使用链表，只关心链表中结点间的逻辑顺序，并不关心每个结 点的实际存储位置，因此通常情况下用箭头来表示链域中的指针， 于是链表就可 以更直观的画成用箭头链接起来的结点序列，如下图所示：图4-1单链表的示例图4.2单链表的操作特点顺链操作技术从“头”开始，访问单链表L中的结点i （p指向该节点）时，由于第i个 结点的地址在第i-1个结点（pre指向该结点，为p的前驱）的指针域中存放， 查找必须从单链表的“首结点”开始（p=L）；通过p=p->next并辅助计数器来实 现。指针保留技术通过对第i个结点进行插入、删除等操作时，需要对第i-1个结点的指针域 进行

12、链址操作（pre->next），因此在处理过程中始终需要维持当前指针 p与其前 驱指针pre的关系，将这种技术称为“指针保留技术”。4.3链表处理中的相关技术1）单链表与多重链表的差别在于指针域的个数。2） 判断当前结点p是否为表尾。一半链表中，p结点是表尾的条件是：该节点 的后继结点为空指针，即p-> next=NULL;3）链表的长度并未显示保存。由于链表是动态生成的结构，其长度要通过顺链 查找到表尾得到。因此在处理链表时，往往是以当前处理结点p是否为表尾作为 控制条件，而不是长度n作为控制条件。5 设计体会及今后的改进意见通过这次实验加深了我对于单链表的进一步了解， 了解到了

13、单链表在内存中 的存储结构，最重要的是学会了如何运用 C 语言将单链表的建立，插入、删除、 添加等操作。在程序实现中也遇到了一些困难，在单链表初始化时，使用了 0 作为结束输入符，导致单链表不能存储数据 0；单链表中只能存储相同类型的数 据，在存储不同类型的数据时需要改变输入结束标志，程序通用性比较差。在进行程序设计的时候没有考虑好删除和查找的方式， 只进行了输入元素的 查找和删除， 而且进行链表的插入时， 只考虑了头插法在结尾插入， 而没有考虑 输入结点插入等，程序的灵活性比较低。通过这次课程设计，让我充分认识到数据结构在编写程序方面的重要地位。 不仅仅是单链表的操作， 还有栈和队列等特殊的

14、单链表操作， 以及其他一些常用 的数据结构对于程序的效率和内存使用有很大的帮助。 我希望在接下来的学习中 收获更多的东西。参考文献1 耿国华.数据结构-用C语言描述M.北京：高等教育出版社，201162 谭浩强.C程序设计M.北京：清华大学出版社，20046附录代码：结构体定义：#pragma once#include <stdio.h>#inelude <stdlib.h> enum my_enum_EXIT,_CREATE,_INSERT,_PRINT,_SEARCH,_DELETE,_COUNT,;static int count = 0;typedef int

15、Elemtype;typedef struct Nodd*单链表结构体的定义*/Elemtype data;struct Node *n ext;Node * LinkList ;void test(); /* 测试函数 */void main_menu(); / 主菜单函数void CreatFromHead( LinkList *l);/* 头插法建立单链表 */void Insert(LinkList l); / 单链表的插入void Print( LinkList l); /* 单链表的输岀 */int Search( LinkList l, Elemtype e); / 查找指定的元

16、素void Deletelist( LinkList l, Elemtype e); / 删除元素 void Count(); / 计数void CREATE(_inkList *head);void INSERT(LinkList *head);void PRINT( LinkList *head);void SEARCHLinkList * head);void DELET(LinkList *head);void COUNT();单链表操作函数:#defi ne _CRT_SECURE_NO_WARNINGS#in elude "li nklist.h" void m

17、ain_menu()pri ntf("t单链表的简单操作ttnnpri ntf("t 1单链表的建立n“)；pri ntf("t 2单链表的插入n");pri ntf("t 3单链表的输出n");pri ntf("t 4单链表的查找n");pri ntf("t 5单链表的删除n");pri ntf("t 6单链表的长度n");pri ntf("t 0退岀n");void CreatFromHead( LinkList l = ( Nodb)malloc(

18、sizeof (Nod©);if (* l = NULLprintf("申请空间失败！ n");return ;(* l )->next = NULLwhile (flag)scanf( "%d", &c);if (c != 0)s = ( Node")malloc( sizeof (Nod©);if (s = NULLprintf("申请空间失败！n");return ;s->data = c;s->next = (* l )->next;(* l )_>next

19、= s;cou nt+;l ->next = s;cou nt+;void Print( LinkList l)/* 单链表的遍历 */Node *p;p = l _>next;while (p != NULLprintf( "%d ", p->data);p = p_>n ext;printf( "n");int Search( LinkList l , Elemtype e) 查找指定的元素while ( l != NULL && ( l->data !=e)l = l ->next;if ( l

20、= NULI)return -1; /查找失败elseq = p; /*保留前驱节点*/p = p_>n ext;if (p = NULLprintf("删除失败，没有找到相应的元素n");void Count()printf("单链表中一共有个元素n" , count); void CREATEDnkList * head)printf("请建立单链表用“ 0”来结束输入n");CreatFromHead(head);printf("初始化后的单链表为：“)；Print(* head); l )/* 头插法建立单链表

21、 */ Node *s;int c = 0;int flag = 1;else flag = 0;void Insert( LinkList l)/ 单链表的插入int insert = 0;Node * s =NULLprintf("请输入需要插入的元素：")；scanf( "%d", &insert);s = ( Nodb)malloc( sizeof ( Node);if (s = NULLprintf("申请空间失败！n");return ;while ( l ->next != NULLl = l ->n

22、ext;s->data = in sert;s->next =l ->next;二elsereturn 1; II查找成功void Deletelist( LinkList l , Elemtype e) II 删除节点Node *p, *r, *q;p = l _>next; q = l ;while (p != NULLif (p->data = e)r = p;p = r->n ext;q_>n ext = p;cou nt-;free(r);break;void INSERT(LinkList * head)In sert(* head);pri ntf("插入后的单链表为：“)；Print(* head);void PRINT( LinkList * head)pri ntf("单链表的输岀为：“)；Print(* head);void SEARCHLinkList * head)int search = 0;int ret = 0;printf("请输入需要查找的元素："); scanf( "%d", &search); |ret = Search(* head, search);if (1 = re