文档介绍：:..数据结构关于链表的研究摘要:链表是数据结构中的重要概念,是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表屮的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元索的数据域,另i个是存储下i个结点地址的指针域。相比于线性表顺序结构,链表比较方便插入和删除操作。关键词:链表;指针;插入;(Linkedlist)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)o由于不必按顺序存储,链表在插入的时候可以达到0(1)的复杂度,比另一种线性表:顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要0(n)的时间,而顺序表相应的时间复杂度分别是0(logn)和0(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表市于增加了结点的指针域,空间开销比较大。在计算机科学中,链表作为一•种基础的数据结构可以用來生成其它类型的数据结构。链表通常由一连串节点组成,每个节点包含任意的实例数据(datafields)和一或两个用来指向明上一个/或下一个节点的位置的链接("links")。链表最明显的好处就是,常规数组排列关联项目的方式可能不同丁这些数据项目在记忆体或磁盘上顺序,数据的存取往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型,因为它包含指向另一个相同类型的数据的指针(链接)。链表允许插入和移除表上任意位置上的节点,但是不允许随机存取⑴。链表有很多种不同的类型:单向链表,双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言,如C,C++和兀眼依靠易变工具來生成链表。。因此,为了表示每个数据元素Ai与一数据元素Ai+1的逻辑关系,对数拯元素Ai来说,除了存储其本身的信息之外,还需存储一个其直接后继的信息。这两部分信息组成数据元素Ai的存储映像,称为结点,其结构如下:姒氓獅十域其屮,data为数据域,存储直接后继存储位置。用于存储数据元素信息;next为指针域,用于单链表的类型定义如下:TypedfstructLnode{ElemTypedata;StructLnode*next;}Inode,*LinkLise;2・2单链表的插入运算单链表的插入运算可分为头插入(前插法)、尾插法(后插法)。,将链表的左边称为链头,右边称为链尾。头插法建单链表是将链表右端看成固定的,链表不断向左延伸而得到的。头插法最先得到的是尾结点。由于链表的长度是随机的,故用一个while循环来控制链表屮结点个数。假设每个结点的值都大于0,则循环条件为输入的值大于o。申请存储空间可使用malloc()