数据结构课程设计-单链表

1、目录1 选题背景 12 方案与论证 2链表的概念和作用 2算法的设计思想 3相关图例 4单链表的结点结构 4算法流程图 43 实验结果 5链表的建立 5单链表的插入 5单链表的输出 6查找元素 6单链表的删除 6显示链表中的元素个数（计数） 74 结果分析 8单链表的结构 8单链表的操作特点 8顺链操作技术 8指针保留技术 8链表处理中的相关技术 85 设计体会及今后的改进意见 9参考文献 10附录代码： 111 选题背景陈火旺院士把计算机 60 多年的发展成就概括为五个 “一”：开辟一个新时代 信息时代，形成一个新产业 信息产业，产生一个新科学 计算机科学 与技术，开创一种新的科研方法 计算

2、方法，开辟一种新文化 计算机文化， 这一概括深刻影响了计算机对社会发展所产生的广泛而深远的影响。数据结构和算法是计算机求解问题过程的两大基石。 著名的计算机科学家指 出，“在工业革命中其核心作用的是能量，而在计算机革命中其核心作用的是信 息”。计算机科学就是“一种关于信息结构转换的科学” 。信息结构（数据结构） 是计算机科学研究的基本课题，数据结构又是算法研究的基础。2 方案与论证链表的概念和作用链表是一种链式存储结构， 链表属于线性表， 采用链式存储结构， 也是常用 的动态存储方法。链表中的数据是以结点来表示的，每个结点的构成：元素 （ 数 据元素的映象 ） + 指针（指示后继元素存储位置

3、） ，元素就是存储数据的存储单 元，指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性链表（单链表）单链表是链式存取的结构， 为找第 i 个数据元素， 必须先找到第 i-1 个数 据元素。因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i 单链表1、链接存储方法 链接方式存储的线性表简称为链表（ Linked List ）。 链表的具体存储表示为： 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连 续的，也可以是不连续的） 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间 的逻辑关系， 在存储每个结点值的同时， 还必须存储指示其后继

4、结点的地址 （或 位置）信息（称为指针（ pointer ）或链 （link） ）、I 、+ :注意：链式存储是最常用的存储方式之一， 它不仅可用来表示线性表， 而且可用来 表示各种非线性的数据结构。2、链表的结点结构IIII data | next Idata 域- 存放结点值的数据域next 域- 存放结点的直接后继的地址（位置）的指针域（链域）链表通过每个结点的链域将线性表的 n 个结点按其逻辑顺序链接在一起 的。每个结点只有一个链域的链表称为单链表（Sin gle Linked List ）3、头指针 head 和终端结点指针域的表示 单链表中每个结点的存储地址是存放在其前趋结点 ne

5、xt 域中，而开始结点 无前趋，故应设头指针 head 指向开始结点。链表由头指针唯一确定，单链表可以用头指针的名字来命名。 终端结点无后继，故终端结点的指针域为空，即 NULL。实验的基本要求（软硬件）用VC+软件平台，操作系统：Windows XP硬件：内存要求：内存大小在 256MB其他配置一般就行。算法的设计思想（a）定义一个创建链表的函数，通过该头插法创建一个带头结点的链表，在接下来的链表操作中使用。（b）定义输出链表的算法，遍历结点的指针域判断是否为空， 如果不为空则输出其数据域，直到指针域为空为止。（c）定义一个遍历查找的算法，通过遍历的数据域，分别与要查询的元素进行比较，如果查

6、找到则返回并输出，如入查找失败则返回错误提示信息。（d）定义插入结点的算法，首先查找指针域为空的结点，并申请空间插入在结点的后边，并且将其指针域置空。（e）定义删除节点的操作，这个算法用于对链表中某个多余节点的删除工作，其关键在于前驱结点的保留，查找到需删除的结点，将其删除，并将其后 继结点连到其前驱结点。相关图例单链表的结点结构如图2-1所示,为单链表的结点结构示意图:Data 域Next域图2-1单链表的结点结构算法流程图如图2-2所示，为此算法流程图：图2-2算法流程图3 实验结果链表的建立链表的建立图 3-1单链表的插入图 3- 2单链表的插入单链表的输出图 3-3 输出单链表元素查找

7、元素图 3-4 查找成功图 3-5 查找失败单链表的删除图 3-6 删除成功图 3-6 删除失败显示链表中的元素个数（计数）图 3-7 输出长度4结果分析单链表的结构一般情况下，使用链表，只关心链表中结点间的逻辑顺序，并不关心每个结 点的实际存储位置，因此通常情况下用箭头来表示链域中的指针， 于是链表就可 以更直观的画成用箭头链接起来的结点序列，如下图所示：图4-1单链表的示例图单链表的操作特点顺链操作技术从“头”开始，访问单链表L中的结点i （p指向该节点）时，由于第i个 结点的地址在第i-1个结点（pre指向该结点，为p的前驱）的指针域中存放， 查找必须从单链表的“首结点”开始（p=L）；

8、通过p=p-next并辅助计数器来实 现。指针保留技术通过对第i个结点进行插入、删除等操作时，需要对第i-1个结点的指针域 进行链址操作（pre-next），因此在处理过程中始终需要维持当前指针 p与其前 驱指针pre的关系，将这种技术称为“指针保留技术”。链表处理中的相关技术1）单链表与多重链表的差别在于指针域的个数。2） 判断当前结点p是否为表尾。一半链表中，p结点是表尾的条件是：该节点 的后继结点为空指针，即p- next=NULL;3）链表的长度并未显示保存。由于链表是动态生成的结构，其长度要通过顺链 查找到表尾得到。因此在处理链表时，往往是以当前处理结点p是否为表尾作为 控制条件，而

9、不是长度n作为控制条件。5 设计体会及今后的改进意见通过这次实验加深了我对于单链表的进一步了解， 了解到了单链表在内存中 的存储结构，最重要的是学会了如何运用 C 语言将单链表的建立，插入、删除、 添加等操作。在程序实现中也遇到了一些困难，在单链表初始化时，使用了 0 作为结束输入符，导致单链表不能存储数据 0；单链表中只能存储相同类型的数 据，在存储不同类型的数据时需要改变输入结束标志，程序通用性比较差。在进行程序设计的时候没有考虑好删除和查找的方式， 只进行了输入元素的 查找和删除， 而且进行链表的插入时， 只考虑了头插法在结尾插入， 而没有考虑 输入结点插入等，程序的灵活性比较低。通过这

10、次课程设计，让我充分认识到数据结构在编写程序方面的重要地位。 不仅仅是单链表的操作， 还有栈和队列等特殊的单链表操作， 以及其他一些常用 的数据结构对于程序的效率和内存使用有很大的帮助。 我希望在接下来的学习中 收获更多的东西。参考文献1 耿国华.数据结构-用C语言描述M.北京：高等教育出版社,.2 谭浩强.C程序设计M.北京:清华大学出版社,.附录代码:结构体定义：#pragma once#inelude #inelude enum my_enum_EXIT,_CREATE,_INSERT,_PRINT,_SEARCH,_DELETE,_COUNT,;static int count = 0

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

12、 e); / 查找指定的元素void Deletelist(LinkList I, 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 void main_menu()pri

13、 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( sizeof (Nod);if (* l = NULLprintf(申请空间失败！ n);return ;(* l )-next = NULLwhile (flag)scanf( %d, &c)

14、;if (c != 0)s = ( Node)malloc( sizeof (Nod);if (s = NULLprintf(申请空间失败！n);return ;s-data = c;s-next = (* 丨)-next;(* l )_next = 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 , Elem

15、type e) 查找指定的元素while ( l != NULL & ( l-data !=e)l = l -next;if ( l = 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(*

16、head); l )/* 头插法建立单链表 */ 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 -next;s-data = in sert;s-next

17、 =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 *

18、head)pri ntf(单链表的输岀为：“)；Print(* head);void SEARCHLinkList * head)int search = 0;int ret = 0;printf(请输入需要查找的元素：); scanf( %d, &search); |ret = Search(* head, search);if (1 = ret)printf(查找成功n)elseprintf(查找失败n)void DELET(LinkList * head)int delet = 0;printf(请输入需要删除的元素：); scanf( %d, &delet);Deletelist(* head, delet);printf(删除之后的单链表为：“)； Print(* head);void COUNT()Cou nt();主菜单函数:#defi ne _CRT_SECURE_NO_WARNINGS#i nclude int main() /* 主函数 */test();return 0;void test() /测试函数int in put = 1;Node * head = NULLmain_me nu();while (i