C语言线性链表

1、1，1，线性表链存储结构，每个元素由节点组成；节点之间的逻辑关系是线性的，即线性表；节点可以不连续地存储在计算机中。链表可以扩展，只受存储介质大小的限制；数据和数据之间的关系是分开存储的，节点：2，链表分类，根据链式存储的原理，可以有各种形式的链表线性链表(单链表)循环链表双向链表，3，3，typedef int elementtypetypedef结构LNode ElemType数据；/节点下一个数据字段结构LNode *；/lnode *的指针字段LNode，LinkList，单个链表的定义，4，单个链表的存储图像，5，初始化：初始化列表(步骤2:p-next=s；什么时候！什么时候？什么

2、时候？万无一失吗？有什么问题吗？7，7，单链表插入操作的特例(1)，核心语句：s-next=p；/头；head=s。在第一个节点之前插入原始语句：s-next=p-next；p-next=s；p，8，8，单链表插入操作的特例(2)，在末尾插入，核心语句：s-next=NULL；p-next=s；p，b，a，head，原始语句：s-next=p-next；p-next=s；9，9，单链表插入操作的特例(3)，空表插入，核心语句：s-next=NULL；head=s。head=NULL，原始语句：s-next=p-next；p-next=s；太麻烦了！快点想办法！10，10，解决方案：带有标题节点

3、的单个链表，空表：第一个节点：存储第一个数据元素，11，11，s-next=p-next；p-next=s；带表头节点的单链表的插入操作，(1)表头插入：(2)空表插入：Ouye！太棒了！12，单个链表插入操作的算法描述，状态列表insert _ l(link list/list insert _ lp29算法2.9，13，13，summary:位于表前面的带标题节点的单个链表本身没有数据，只有标记。有时它可以用来存储附加信息。设置表头节点的优点：统一链表第一个位置和其他位置的操作；统一空表和非空表的操作；以空间赢得时间，从而可以区分各种链表(单向链表、双向链表、单向循环链表和双向循环链表)的

4、空链表状态；它还表明，各种空链表的结构是不同的。注意：只要没有特殊说明，就使用前导节点的链表。14，14，课后作业，比较两种单链表的插入操作，即非前导节点和前导节点，并分析两种单链表的删除操作的差异。(书面作业)描述：必须完成！虽然不是说话，但却是考试内容！15，2.3.3链表的基本算法：(1)初始化，生成一个带有前导节点的空链表，状态init list _ l(链表，16，16，链表的基本算法)(2)建立一个单独的链表，建立链表的过程是一个动态生成过程：从空链表状态开始，依次建立每个元素节点，并逐个插入。(2)插入新节点。尾插入法，17，方法1:调用基本算法建立链表；使用基本算法： void

5、 InitList(int I=0；初始列表(L)；/初始化链表I=1；Scanf(，输入：67，23，10，45，36，20，T(n)=O(n)，如果没有最后一个指针，T(n)=O(n2)就不用担心了，所以一定要记住页脚。如何改进？通过尾部插入法、头部插入法、21、头部插入法(P30算法2.11)、void CREAT LIST _ L(链表CREAT LIST _ L，输入：36、45、10、23、67、22、22)对单个链表进行性能分析，总结：单个链表的优缺点，可以有效利用存储空间。指针用于指示数据元素之间的后续关系，便于插入和删除；缺点：数据元素不能随机访问。与此同时，顺序表的一些优势

6、也丧失了，例如线性表中数据元素的“位顺序”，这在单个链表中是“不可见的”。在页脚中插入元素并不方便，因此需要遍历整个表格来查找页脚。23、23、其他类型的链表双链表、a1、an、a3、a2、h、typedef int elementtypetypedef结构DuLNode ElemType数据；结构DuLNode *优先；结构模块节点*下一步；DuLNode，* DuLinkList，24，24，summary:如果sel的长度为主要操作特征顺序表：插入和删除耗时的移动数据，快速获取数据；链表：插入和删除都很快，而且获取数据需要时间。25，25，多项式，n阶多项式Pn(x)有n个1项。系数是A

7、0、a1、a2和x，指数是0、1、2和n.按升序排列，2.4线性表应用：一元多项式的表示和加法，多项式26，26的存储表示，方法1:将所有项的系数按指数从0到n的顺序保存。每个数据项的系数类型为float，多项式存储为float coef maxDegree，问题：对于不完全指数的多项式来说太浪费了，例如P2000(x)=3 5x 1000 14 x 2000。27，27，方法2:仅保存非零系数项的系数和指数，方法2:改进的序列表，typedef结构浮点系数；/系数int exp/指数多边形节点；多节点SqPolym 1；28，28，方法3:使用单链表，typedef struct poly

8、_ list node float coef；/系数int exp/下一个指数结构多边形列表节点*；多边形列表节点；多边形列表节点*正方形多边形；29，1。如果学生记录信息为：学号、姓名、年级，则需要在订单表中实现。请以静态存储和动态存储的形式写出数据结构描述。#定义ListSize 100 typedef int ElemTypetypedef结构ElemType elemListSize整数长度；Sqlist。typedef结构整数；char name10积分；ElemType，30，静态分配存储结构，#定义列表大小100 typedef struct int数；char name10积分

9、；学生；typedef结构学生elemListSize整数长度；Sqlist。#定义ListSize 100 typedef int ElemTypetypedef结构ElemType elemListSize整数长度；Sqlist。typedef结构整数；char name10积分；学生；31，动态分配存储结构，# define list _ init _ size 100 # define list increment 10 typedef int element type；typedef结构ElemType * elem整数长度；int listsizeSqlist。typedef结构整数；char n