初识链表

• 用一组物理位置任意的存储单元来存放线性表的数据元素。
• 这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。
• 链表中元素的逻辑次序和物理次序不一定相同。

在存储自己内容的同时也存储下一个元素的地址。存储数据元素的域称为数据域，存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成ai的存储映象称为结点(Node)。n个结点(ai(1≤i≤n)的存储映象链结成一个链表，即为线性表。把链表中第1个结点的存储位置叫头指针。最后一个元素意味着没有直接后继规定最后一个结点指针为空(通常用NULL或^表示)

单链表由头指针唯一确定，因此单链表可用头指针名字来命名。

单链表、双向链表、循环链表 其他基础辨析

结点只有一个指针域的链表称为单链表或线性链表

结点有两个指针域的链表称为双链表

首尾相接的链表叫循环链表

为了更加方便对链表进行操作，会在单链表的第1个结点前附设一个头结点.头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，头结点的指针域存储指向线性表第1个元素的结点。

头指针：

指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针;

头指针具有标识作用，所以常用头指针冠以链表的名字;

无论链表是否为空，头指针均不为空。头指针是链表的必要元素

头结点：

头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）

有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了

头结点不一定是链表必须要素

首元结点：

是指链表中存储第一个数据元素a₁的结点

思考

如何表示空表

• 无头结点时，头指针为空时表示空表

• 有头结点时，当头结点的指针域为空时表示空表

有头结点有什么好处？

①有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了

②便于空表和非空表的统一处理
当链表不设头结点时，假设L为单链表的头指针，它应该指向首元结点，则当单链表为长度n为0的空表时，L指针为空（判定空表的条件可记为：L == NULL)。增加头结点后，无论链表是否为空，头指针都是指向头结点的非空指针。头指针指向头结点。若为空表，则头结点的指针域为空（判定空表的条件可记为：L ->next == NULL)

链表（链式存储结构）的特点

1. 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
2. 访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等

• 顺序表→随机存取

• 链表→顺序存取

单链表基本操作实现

单链表的初始化（带头结点的单链表）

• 即构造一个空表

步骤：

1. 生成新结点作头结点，用头指针L指向头结点

2. 将头结点的指针域置空

 Status InitList(LinkList &L) {	 //构造一个空的单链表LL = new LNode;        	 //生成新结点作为头结点，用头指针L指向头结点L->next = NULL;          //头结点的指针域置空return OK;}

补充单链表的几个常用简单算法

自我感觉除了判空都没啥用

判断链表是否为空

int ListEmpty(LinkList L)  //若L为空表，则返回1，否则返回0
{if(L->next) //非空return 0;else return 1;
}

单链表的销毁

链表销毁后不存在

• 从头指针开始依次释放所有结点

void DestoryList(Lnode* L)
{Lnode* p;while (L) {p = L;L = L->next;free(p);}return;
}

清空单链表

链表仍存在，但链表中无元素，成为空链表（头指针和头结点仍然在）

• 依次释放所有结点，并将头结点指针域设置为空

void ClearList(Lnode* L)
{Lnode* p, * q;p = L->next;while (p){q = p->next;free(p);p = q;}L->next = NULL;
}

求单链表的表长

• 从首元结点开始，依次计数

int ListLength(Lnode* L)
{int i = 0;Lnode* p = L->next;  //p指向第一个结点while (p){i++;p = p->next;}return i;
}

取值——取单链表第i个元素

• 从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构。

/*初识条件：顺序线性表L已存在，1 ≤ i ≤ListLength(L)操作结构：用e返回L中第i个数据元素的值。
*/
int GetElem(LinkList L, int i, int* e)
{int j;Lnode* p;    //声明一结点pp = L->next;    //让p指向链表L的第一个结点j = 1;          //j为计数器while (p && j < i )   //p不为空或者计数器j还没有等于i时循环继续{p = p->next;  //让p指向下一个结点j++;}if (!p || j > i){return -1;  //第i个元素不存在}*e = p->data;    //取第i个元素的数据return *e;
}

算法分析：

该算法的基本操作是比较 j 和 i 并后移指针 p，while循环体中的语句频度与位置 i 有关。若 1 ≤ i ≤ n ，则频度为 i - 1 ，一定能取值成功；若 i ＞ n，则频度为n，取值失败。因此取值算法的时间复杂度为O(n)。

假设每个位置上的元素取值概率相等，即：p_i = 1/n

则：

按值查找——根据特定数据获取该数据所在地址

1. 从第一个及诶点依次与e比较
2. 如果找到一个与e相等的元素，则返回在列表中的地址
3. 如果查边整个链表都没有找到和e相等的元素停止循环，并返回

Lnode* LocateElem(LinkList L, int e)
{// 在线性表L中查找值为e的数据元素//找到，则返回L中值为e的数据元素的地址，查找失败返回NULL（因为p最后指向了NULL）Lnode* p;p = L->next;while (p && p->data != e){p = p->next;}return p;
}

返回该数据位置序号

相当于多加了个计数器而已

int LocateElem2(LinkList L, int e)
{//返回L中值为e的数据元素的位置序号，查找失败返回0Lnode* p;p = L->next;int j = 1;while (p && p->data != e){p = p->next; j++;}if (p) return j;else return -1;
}

该算法的执行时间与待查找的值e相关， 其平均时间复杂度分析类似于算法2.7,也为O(n)。

单链表的插入

1. 首先找到a_i-1的存储结构p。
2. 生成一个数据域为e的新结点s。
3. 插入新结点：
   • 新结点的指针域指向结点a_i s->next = p->next
   • 结点a_i-1的指针域指向新结点 p->next = s;

/*i表示插入第几个元素之前
最后L要+1*/
void ListInsert(LinkList L,int i ,int e)
{int j;Lnode* p, * s;p = L;    //查找算法从首元素开始p=L->next;j=1【插入算法i=1它的前一个结点的头结点j=i-1不循环】j = 0;while (p && j < i - 1){p = p->next;j++;}if (!p || j > i - 1){printf("error");//插入错误，，，并提示return;}s = (Lnode*)malloc(sizeof(Lnode));s->data = e;s->next = p->next;   p->next = s;return;
}

单链表的删除

按位删除

1. 找到第i-1个结点，如果有必要的话保存a_i的值且将地址存于在q中以被释放
2. 找到a_i-1的位置赋值给a_i-1的next域
3. 释放a_i

p->next = p->next->next

/*删除L的第i个数据元素，并用e返回其值，L的长度减1*/
void Listdelete(LinkList L, int i, int* e)
{int j;Lnode* p, * q;p = L; //*i=1，p是头结点p=L;j = 0;while (p->next && j < i - 1)//遍历寻找第i-1个元素{p = p->next;j++;}if (!(p->next) || j > i - 1){/*  printf("")  */return;  //第i个元素不存在，并提示}q = p->next;p->next = p->next->next; //或者p->next=q->next *e = q->data;free(q);}

按值删除

/*按值删除*/
void ListdeleteElem(LinkList L, int e)
{//先查找   有才能删//需要另写一个定位函数int index = find(L, e);if (index == -1){//没找到}else {//定位到前一个元素Lnode* temp;temp = L;int i = 0;while (i < index)//定位置{temp = temp->next;i++;}Lnode* free_node = temp->next;temp->next = temp->next->next;free(free_node);}
}int find(LinkList L, int key)
{  //定位函数，定位到待删除元素的前一个Lnode* temp;int i = 0;temp = L->next;while (temp != NULL){if (temp->data == key){return i;}temp = temp->next;i++;}return -1;
}

头插法 &尾插法建立单链表

头插法 – 元素插入在链表头部 （前插法）

1. 从一个空表开始，重复读入数据；
2. 生成新结点，将读入数据存放到新结点的数据域中
3. 从最后一个结点开始，依次将各结点插入到链表的前端

/*头插法*/
void Linkinsert_head(LinkList L, int e)
{Lnode* temp = (Lnode*)malloc(sizeof(Lnode));// 创建新结点//if判断malloc是否分配成功temp->next = L->next;L->next = temp;temp->data = e;
}/*当然也可以考虑加个循环，连续插入*/

尾插法

1. 从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点。
2. 初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点。

/*尾插法*/
void Linkinsert_tail(LinkList L, int e)
{Lnode* temp = (Lnode*)malloc(sizeof(Lnode));// 创建新结点temp->next = NULL;Lnode* r, *p; r = L;p->data = e;p->next = NULL;r->next = p;// 插入到表尾r = p;  //r指向新尾结点
}

代码总结

#include<stdio.h>
#include<stdlib.h>typedef struct Lnode {    //声明结点的类型和指向结点的指针类型int data;             //结点数据域struct Lnode* next;   //结点指针域
}Lnode, *LinkList;        //LinkList为指向结构体Lnode的指针类型/*初始化  空链表
*/Lnode* InitList(LinkList L)
{L = (Lnode*)malloc(sizeof(Lnode);if (L == NULL){printf("分配失败");  //提示分配失败}else {L->next = NULL;}return L;
}void DestoryList(Lnode* L)
{Lnode* p;while (L) {p = L;L = L->next;free(p);}return;
}void ClearList(Lnode* L)
{Lnode* p, * q;p = L->next;while (p){q = p->next;free(p);p = q;}L->next = NULL;
}int ListLength(Lnode* L)
{int i = 0;Lnode* p = L->next;  //p指向第一个结点while (p){i++;p = p->next;}return i;
}/*初识条件：顺序线性表L已存在，1 ≤ i ≤ListLength(L)操作结构：用e返回L中第i个数据元素的值。
*/
int GetElem(LinkList L, int i, int* e)
{int j;Lnode* p;    //声明一结点pp = L->next;    //让p指向链表L的第一个结点j = 1;          //j为计数器while (p && j < i )   //p不为空或者计数器j还没有等于i时循环继续{p = p->next;  //让p指向下一个结点j++;}if (!p || j > i){return -1;  //第i个元素不存在}*e = p->data;    //取第i个元素的数据return *e;
}
/*按值查找*/
Lnode* LocateElem(LinkList L, int e)
{// 在线性表L中查找值为e的数据元素//找到，则返回L中值为e的数据元素的地址，查找失败返回NULL（因为p最后指向了NULL）Lnode* p;p = L->next;while (p && p->data != e){p = p->next;}return p;
}/*按值查找2   返回位置序号*/
int LocateElem2(LinkList L, int e)
{//返回L中值为e的数据元素的位置序号，查找失败返回0Lnode* p;p = L->next;int j = 1;while (p && p->data != e){p = p->next; j++;}if (p) return j;else return -1;
}/*i表示插入第几个元素之前
最后L要+1*/
void ListInsert(LinkList L,int i ,int e)
{int j;Lnode* p, * s;p = L;    //查找算法从首元素开始p=L->next;j=1【插入算法i=1它的前一个结点的头结点j=i-1不循环】j = 0;while (p && j < i - 1){p = p->next;j++;}if (!p || j > i - 1){printf("error");//插入错误，，，并提示return;}s = (Lnode*)malloc(sizeof(Lnode));s->data = e;s->next = p->next;   p->next = s;return;
}/*按位删除
删除L的第i个数据元素，并用e返回其值，L的长度减1*/
void Listdelete(LinkList L, int i, int* e)
{int j;Lnode* p, * q;p = L; //*i=1，p是头结点p=L;j = 0;while (p->next && j < i - 1)//遍历寻找第i-1个元素{p = p->next;j++;}if (!(p->next) || j > i - 1){/*  printf("")  */return;  //第i个元素不存在，并提示}q = p->next;p->next = p->next->next; //或者p->next=q->next *e = q->data;free(q);}/*按值删除*/
void ListdeleteElem(LinkList L, int e)
{//先查找   有才能删//需要另写一个定位函数int index = find(L, e);if (index == -1){//没找到}else {//定位到前一个元素Lnode* temp;temp = L;int i = 0;while (i < index)//定位置{temp = temp->next;i++;}Lnode* free_node = temp->next;temp->next = temp->next->next;free(free_node);}
}int find(LinkList L, int key)
{  //定位函数，定位到待删除元素的前一个Lnode* temp;int i = 0;temp = L->next;while (temp != NULL){if (temp->data == key){return i;}temp = temp->next;i++;}return -1;
}/*头插法*/
void Linkinsert_head(LinkList L, int e)
{Lnode* temp = (Lnode*)malloc(sizeof(Lnode));// 创建新结点//if判断malloc是否分配成功temp->next = L->next;L->next = temp;temp->data = e;
}/*尾插法*/
void Linkinsert_tail(LinkList L, int e)
{Lnode* temp = (Lnode*)malloc(sizeof(Lnode));// 创建新结点temp->next = NULL;Lnode* r, *p; r = L;p->data = e;p->next = NULL;r->next = p;// 插入到表尾r = p;  //r指向新尾结点
}