链表小结

前面已经讲解了单链表，除此之外还有双链表，循环链表和静态链表等，那就让我们一起认识链表家族中的其他成员吧

此文参考博客： https://blog.csdn.net/daijin888888/article/details/68925248 详情请移步

一、顺序存储结构

1.1 存储方式

因为每个数据元素的类型都相同，所以可以使用一位数组来实现。结构代码如下：

//线性表的顺序存储结构  
#define MAXSIZE 20;//存储空间初始分配量为20  
typedef int ElemType;//数据类型为int  
type struct  
{  
    ElemType data[MAXSIZE];//数组存储数据元素  
    int length;//线性表长度  
}SqList;

这里可以看到，顺序存储结构需要三个属性：

存储空间的起始位置：数组data ，它的存储位置就是存储空间的存储位置
线性表的最大存储容量：数组长度MaxSize
线性表的当前长度：length

1.2 地址计算方法

若每个存储元素占用c个存储但愿，那么线性表中元素的位置可以由此计算出：

LOC(ai) = LOC(ai) + (i-1)*c

通过这个公式，可随时算出线性表中任意位置的地址，使用相同的时间。它的存取时间性能为O（1），这一特点的存储结构称之为随机存取结构。

二、链式存储结构的线性表

2.1 单链表

头指针：链表中第一个结点的存储位置

头结点：有时为了便于操作，在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存信息，可以存线性表的长度等附加信息，头结点的指针域指向第一个结点的指针。

头指针和头结点的区别：
头指针

头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
头指针具有标识作用，常用头指针冠以链表的名字
无论链表是否为空，头指针均不为空。头指针是链表的必要元素

头结点

头结点是为了操作的统一和方便设立的，在第一个元素的结点之前，其数据域一般无意义（或存放链表长度）。
有了头结点，对在第一个元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了
头结点不一定是链表必须要素

链式存储结构：

typedef struct Node{   // 线性表的单链表存储结构
  ElemType data;  
  struct Node *next;  
}Node;

typedef struct Node *LinkList;  //  定义LinkList

这里讲一下，单链表的头插法和尾插法：

头插法：

 1 LinkList CreatList1(LinkList &L){
 2     //从表尾到表头逆向建立单链表L，每次均在头结点之后插入元素
 3     Node *s;int x;
 4     L=(LinkList)malloc(sizeof(Node));  //创建头结点
 5     L->next=NULL;  //初始为空链表
 6     scanf("%d", &x);  //输入结点的值
 7 
 8     while(x!=9999) {  //输入 9999 表示结束
 9         s=(Node*)malloc(sizeof(Node) );  //创建新结点
10         s->data=x;
11         s->next=L->next;
12         L->next=s;  //将新结点插入表中，L为头指针
13         scanf ("%d", &x);
14     }

头插法是逆序的，接着学习尾插法

代码如下：

 1 LinkList CreatListRear(LinkList &L){
 2     //从表头到表尾正向建立单链表L,每次均在表尾插入元素
 3     int x; // 设元素类型为整型
 4     L=(LinkList)malloc(sizeof(LNode));
 5     LNode *s, *r=L; //r 为表尾指针
 6     scanf ("%d", &x); //输入结点的值
 7      
 8     while (x!=9999) { //输入 9999 表示结束
 9         s=(LNode *)malloc(sizeof(LNode));
10         s->data=x;
11         r->next=s;
12         r=s; //r指向新的表尾结点
13         scanf ("%d", &x);
14     }
15      
16     r->next = NULL; //尾结点指针置空
17     return L;
18 }

尾插法最后的输出序列是正序的

单链表结构与顺序存储结构优缺点

2.2 静态链表（链表的游标实现）

用数组描述的链表就做静态链表。（这个就跟上一节讲解的模拟单链表很类似）

静态链表的优缺点：

总的说，静态链表是为了给没有指针的高级语言设计的一种实现单链表能力的方法。虽使用较少，但思考方式比较巧妙，思想值得借鉴。

3.3 双链表

双链表中的每个节点有两个子节点，一个指向它的前驱，一个指向它的后继。

采用尾插法建立双链表如下：

 1 void CreateDlistR (DLNode *&L, int a[], int n){ 
 2     DLNode*s,*r;
 3     inti;
 4     L = (DLNode*)malloc(sizeof(DLNode));
 5     L->next = NULL;
 6 
 7     //和单链表一样r始终指向终端结点，开始头结点也是尾结点
 8     r = L;
 9 
10     for(i = 1; i< = n; i++){ 
11         //创建新结点s->data = a[i];
12         s = (DLNode*)malloc(sizeof(DLNode));
13 
14         /*下边3句将s插入在L的尾部并且r指向s，s->prior = r;这一句是和建立单链表不同的地方。 */
15         r->next = s;
16         s->prior = r;
17         r = s;
18     }
19     r->next = NULL;
20 }

3.4 循环链表

3.4.1 循环单链表

只要将单链表的最后一个指针域（空指针）指向链表中第一个结点即可（这里之所以说第一个结点而不说是头结点是因为，如果循环单链表是带头结点的则最后一个结点的指针域要指向头结点；如果循环单链表不带头结点，则最后一个指针域要指向开始结点）。

带头结点的循环单链表当head等于head->next时链表为空；
不带头结点的循环单链表当head等于null时链表为空。

3.4.2 循环双链表

循环双链表的构造源自双链表，即将终端结点的nnext指针指向链表中第一个结点，将链表中第一个结点的prior指针指向终端结点。

带头结点的循环双链表当head->next和heaad->prior两个指针都等于head时链表为空。
不带头结点的循环双链表当head等于null的时候为空。

循环链表的算法操作

循环单链表和循环双链表由对应的单链表和双链表改造而来，秩序在终端节点和头节点间建立联系即可。

循环单链表终端结点的next结点指针指向表头结点；循环双链表终端结点的next指针指向表头结点，头结点的prior指针指向表尾结点。

如果p指针沿着循环链表行走，判断p走到表尾结点的条件是p->next == head。循环链表的各种操作均与非循环链表类似。