链表的表示
链式存储特点
逻辑上相邻，物理上不一定相邻
链表存放示意图：
每个存储结点都包含两部分：数据域和指针域(链域) 。
在单链表中，除了首元结点外，任一结点的存储位置由 其直接前驱结点的链域的值 指示。
与链式存储有关的术语
1）结点：数据元素的存储映像。由数据域和指针域两部分组成；
2）链表： n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。
3）单链表、双链表、多链表、循环链表：
结点只有一个指针域的链表，称为单链表或线性链表；
有两个指针域的链表，称为双链表；
有多个指针域的链表，称为多链表；
首尾相接的链表称为循环链表。
4）头指针、头结点和首元结点
头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。
单链表可由一个头指针唯一确定。
头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息;
首元结点是指链表中存储线性表第一个数据元素a1的结点。
无头结点 有头结点
在链表中设置头结点有什么好处？
头结点即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。
(1) 对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。
(2) 对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。这样可以区分空链表和空指针，也减少了程序的复杂性和出现bug的机会。
在进行删除操作时，L为头指针，p指针指向被删结点，q指针指向被删结点的前驱，对于非空的单链表:
1.带头结点时 删除第1个结点(q指向的是头结点):q->next=p->next; free(p);
删除第i个结点(i不等于1):q->next=p->next;free(p);
2.不带头结点时 删除第1个结点时(q为空):L=p->next; free(p);
删除第i个结点(i不等于1):q->next=p->next;free(p);
结论:带头结点时，不论删除哪个位置上的结点，用到的代码都一样;不带头结点时，删除第1个元素和删除其它位置上的元素用到的代码不同，相对比较麻烦。
无头结点时，当头指针的值为空时表示空表；
有头结点时，当头结点的指针域为空时表示空表。
头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。
链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？因每个结点至少有两个分量，所以要采用结构数据类型。
单链表存储结构
Typedef struct Lnode {
ElemType data; //数据域
struct Lnode *next; //指针域
}Lnode, *LinkList; // LinkList为指向Lnode类型的指针
补充：结构数据类型及其C语言表示法
每个结点的分量如何表示？
方式1：直接用 test.data＝‘a’； test.next=q；
方式2：先让指针变量p指向该结点的首地址，然后用： p->data='a'; p->next=q;
方式3：先让指针变量p指向该结点的首地址，然后用： (*p).data=‘a’； (*p).next＝q；
链表的实现{线性链表，循环链表，双向链表}
1. 单链表的读取 (或修改）
难点：单链表中想取得第i个元素，必须从头指针出发寻找（顺藤摸瓜），不能随机存取 。 注意：判断i不合法的情况，和表空的情况。
思路：要修改第i个数据元素，关键是要先找到该结点的指针p，然后用p->data=new_value 即可。
Status GetElem_L(LinkList L, int i, ElemType &e){
P=L->next;
j=1; //j用来计数
while(p && j p=p->next; ++j; } if (!p || j>i) return ERROR; //!p即p为空，有两种情况，第一是表为空，第二是i的值超过了表的长度，while循环执行完后p走到最后一个元素还没有找到i的位置。j >i 就是i是0或者负数的情况。 e=p->data; return OK; } // 注意：L为带头结点的单链表的头指针 // 当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR 2. 单链表的插入 在链表中插入一个元素的示意图如下：P指向要插入的位置的前面的那个元素。 元素x结点应预先生成： S=(ElemType*)malloc(m); S->data=x; 插入步骤（即核心语句）：Step 1：s->next=p->next; Step 2：p->next=s ； Status ListInsert_L(LinkList &L,int i,ElemType e){ p=L; j=0; while(p && j p=p->next; ++j }//p将指向第i-1个元素 if(!p || j>i-1) return ERROR; s=(LinkList)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; return OK; } 3. 单链表的删除 删除步骤（即核心语句）： q = p->next; //保存b的指针，靠它才能指向c p->next=q->next; //a、c两结点相连 free(q) ； //删除b结点，彻底释放 Status ListDelete_L(LinkList &L,int i,ElemType &e){ p=L; j=0; while(p->next && j p=p->next;++j } if(!p->next || j>i-1) return ERROR; //p指向第i-1个结点 //判断p->next ，是要保证p的后面还有结点。 q=p->next; e=q->data; p->next=q->next; free(q) return OK; } 4. 单链表的建立和输出 实现思路：先开辟头指针，然后陆续为每个数据元素开辟存储空间并赋值，并及时将地址送给前面的指针。 实现方法：头插法和尾插法。 头插法：每次都插入到头结点的后面，即链表的最前面。 Void CreateList_L (LinkList &L, int n) { //逆位序输入n个元素的值,建立带表头结点的单链线性表L. L = (LinkList) malloc (sizeof(LNode)); L→next = NULL; // 先建立一个带头结点的单链表 for ( i =n; i>0; --i) { p = (LinkList) malloc (sizeof(LNode)); // 生成新结点 scanf (&p →data); // 输入元素值 p→next = L→next ; L→next = p; // 插入到表头 } } // CreateList_L 尾插法：要有一个指针总是指向最后一个元素 Void CreateList_L (LinkList &L, int n) { //正序输入n个元素的值,建立带表头结点的单链线性表L. L = (LinkList) malloc (sizeof(LNode)); L→next = NULL; // 先建立一个带头结点的单链表 q=L;//q总是指向最后一个元素 for ( i =n; i>0; --i) { p = (LinkList) malloc (sizeof(LNode)); //新结点 scanf (&p →data); p->next=null; // 输入元素值 q→next = p; //把新结点p放到q的后面 q=q→next ; } } // CreateList_L 5. 应用举例 1、设计算法实现单链表的遍历。 void travle(LinkList L){ LinkList p cout<<"建立的链表为："; for(p=L->next;p!=NULL;p=p->next) cout< } 2、求单链表的长度。 void len_LL (LinkList L,int &len){ LinkList p; for(p=L->next;p!=NULL;p=p->next) len++; } 3、将单链表逆置。 提示：参考头插法，从头依次读取链表上的结点，每次读取的结点都插入到一个新链表的头部。 4、两个链表的归并 已知：线性表 A、B，分别由单链表 LA , LB 存储，其中数据元素按值非递减有序排列 要求：将 A ，B 归并为一个新的线性表C , C 的数据元素仍按值非递减排列 。设线性表 C 由单链表 LC 存储。 假设：A=（3，5，8，11），B=（2，6，8，9，11） 预测：合并后 C =（ 2 , 3 , 5 , 6 , 8 , 8 , 9 , 11，11 ） 算法分析：算法主要包括：搜索、比较、插入三个操作： 搜索：需要两个指针搜索两个链表； 比较：比较结点数据域中数据的大小； 插入：将两个结点中数据小的结点插入新链表。 Void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){ //按值排序的单链表LA,LB，归并为LC后也按值排序 pa=La->next; pb=Lb->next; Lc=La；pc=La //用La的头结点，作为Lc的头结点 while(pa&&pb){ //将pa 、pb结点按大小依次插入C中 if(pa->data<=pb->data){ pc->next=pa; pc=pa; pa=pa->next; } else { pc->next=pb; pc=pb; pb=pb->next } } pc->next = pa?pa:pb ; //插入剩余段 free(Lb); //释放Lb的头结点 } //MergeList_L 可以看出：归并两个链表时，不需要另建新的 存储空间，只需将原来链表中的节点之间的关 系解除，重新安排顺序。 6. 其它链表形式 用一维数组存放链表，只要定义一个结构类型（含数据域和指示域）数组，就可以完全描述链表，这种链表称为静态链表。 注：数据域含义与前面相同，指示域相当于前面的指针域。 静态链表的插入与删除操作与普通链表一样，不需要移动元素，只需修改指示器就可以了。 静态链表 #define MAXSIZE 1000 typedef struct{ ElemType data; int cur; }component,SLinkList[MAXSIZE] 链表首尾相连，只要将表中最后一个结点的指针域指向头结点即可 (P->next=head;) 。这种形成环路的链表称为循环链表。 循环链表：表中最后一个结点的指针域指向头结点，整个链表形成一个环。 循环链表的实现无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。从任一结点出发均可找到表中其他结点。 循环链表的操作与线性链表基本一致，差别在于算法中的循环条件不是p或p->next是否为空，而是它们是否等于头指针。 单链表查找直接前驱，只要把单链表再多开一个指针域即可(例如用*next和*prior;) 。 这种有两个指针的链表称为双向链表。其特点是可以双向查找表中结点。 特别：带头结点的空双向链表样式： 双向链表在非线性结构（如树结构）中将大量使用。 双向链表：结点有两个指针域，一个指向直接前驱，一个指向直接后继。 克服了单链表的单向性（查后继O(1)，查前驱O(n)）的缺点。 双链表是由头指针head惟一决定的。 双链表进行插入和删除操作时必须要同时修改两个方向的指针。 Status ListInsert_DuL(DuLinkList &L,int i, ElemType e){ if(!(p=GetElemP_DuL(L,i))) return ERROR; if(!(s=(DuLinkList)malloc(sizeof(DulNode)))) return ERROR; s->data=e; s->prior=p->prior; p->prior->next=s; s->next=p; p->prior=s; return Ok; } Status ListDelete_DuL(DuLinkList &L,int i, ElemType &e){ if(!(p=GetElemP_DuL(L,i))) return ERROR; e=s->data; p->prior->next=p->next; p->next->prior= p->prior; //两行的顺序是否可以颠倒？ free(p); return Ok; } 链表的运算效率分析 时间效率分析 1. 查找 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。 2. 插入和删除 因线性链表不需要移动元素，在给出某个合适位置的指什后，插入和删除操作所需的时间仅为 O(1)。 但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为 O(n)。 空间效率分析 链表中每个结点都要增加一个指针空间，相当于总共增加了n 个整型变量，空间复杂度为 O(n)。 顺序存储和链式存储各有哪些优缺点？ 顺序存储的优点是存储密度大(＝1)，存储空间利用率高。缺点是插入或删除元素时不方便。 链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小（<1），存储空间利用率低。 事实上，链表插入、删除运算的快慢是以空间代价来换取时间。 存储密度=结点数据本身所占的存储量/结点结构所占的存储总量 如何选择？ 顺序表适宜于做查找这样的静态操作； 链表宜于做插入、删除这样的动态操作。 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表； 若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。 顺序表 链表 基于空间考虑 分配方式 静态分配。程序执行之前必须明确规定存储规模，若线性表长度n变化较大，则存储规模难于预先确定，估计过大将造成空间浪费，估计过小又将使空间溢出机会增多。 动态分配。只要内存空间尚有空闲就不会产生溢出，因此当线性表的长度变化较大，难以估计其存储规模时，以采用动态链表作为存储结构为好。 存储密度 =1.当线性表的长度变化不大，易于事先估计其大小时，为了节约存储空间，宜采用顺序存储作为存储结构。 <1 基于时间考虑 存取方法 随机存取结构。对表中任一结点都可在O(1)时间内直接取得。若线性表的操作主要是进行查找，很少做插入和删除操作，则采用顺序表作为存储结构为宜。 顺序存取结构。链表中的结点需从头指针起顺着链扫描才能取得。 插入删除操作 在顺序表中进行插入和删除操作，平均要移动表中一半的结点，尤其是每个结点的信息量较大时，移动结点的开销就相当可观。 在链表中的任何位置插入和删除，都只需要修改指针。对于频繁进行插入和删除操作的线性表，宜采用链表作存储结构。若表的插入和删除主要发生表的首尾两端，则采用尾指针表示的单循环链表为宜。 代码实现：链表的基本操作https://blog.csdn.net/qq1457346557/article/details/107122832