链表与顺序表的比较：
（1）顺序表便于访问查询，具有随机存取特性，链表便于插入删除。
（2）顺序表的存储密度为1，链表的存储密度小于1。
存储密度=节点中数据元素所占的存储量 / 节点所占存储量
初始定义结构体
typedef struct LNode
{
int data;
struct LNode* next;
}LinkNode;
一.建立单链表
void CreateListF(LinkNode*& L, int a[], int n)
{
LinkNode* s;
L = (LinkNode*)malloc(sizeof(LinkNode));
L->next = NULL; //创建头节点，将其next域置为NULL
for (int i = 0; i < n; i++) //循环创建数据节点s，并将其插入到L中
{
s = (LinkNode*)malloc(sizeof(LinkNode)); //创建数据节点s
s->data = a[i];
//将s节点插入原首节点前，头节点后
s->next = L->next;
L->next = s;
}
}
关键：建立一个节点r，r开始时指向头节点，插入数据后一直指向尾节点。
void CreateListR(LinkNode*& L, int a[], int n)
{
LinkNode* s, * r;
L = (LinkNode*)malloc(sizeof(LinkNode)); //创建头节点
r = L; //r始终指向尾节点，开始时指向头节点
for (int i = 0; i < n; i++) //循环建立数据节点s，并将其插入到L中
{
s = (LinkNode*)malloc(sizeof(LinkNode));//创建数据节点s
s->data = a[i]; //为s赋予数据
r->next = s; //在L尾端插入s
r = s; //更新L尾端指针
}
r->next = NULL; //将尾节点的next域置为NULL
}
二.单链表的基本运算
void InitList(LinkNode*& L)
{
L = (LinkNode *)malloc(sizeof(LinkNode));
L->next = NULL; //创建头节点，将其next域置为NULL
}
void DestroyList(LinkNode*& L)
{
LinkNode* pre = L, * p = L->next; //pre指向节点p的前驱节点
while (p != NULL) //遍历单链表
{
free(pre); //释放pre节点
pre = p; //pre、p同步后移一个节点
p = pre->next;
}
free(pre); //循环结束时p为NULL，pre指向尾节点，释放它
}
bool ListEmpty(LinkNode* L)
{
return(L->next == NULL);
}
int ListLength(LinkNode* L)
{
int n = 0;
LinkNode* p = L; //p指向头节点，n置为0（即头结点的序号为0）
while (p->next != NULL)
{
n++;
p = p->next;
}
return n; //循环结束时，p指向尾节点，其序号n为节点的个数
}
void DisplayList(LinkNode* L)
{
LinkNode* p = L->next; //p指向首节点
while (p != NULL)
{
printf("%d", p->data); //p不为NULL，就输出p节点的data域
p = p->next;
}
printf("\n");
}
注意：
LinkNode* p=L 为p指向头节点
LinkNode* p=L->next 为p指向首节点
bool GetElem(LinkNode* L, int i, int& e)
{
int j = 0;
LinkNode* p = L; //p指向头节点，j置为0（即头结点的序号为零）
if (i next;
} //找到第i个节点，循环结束后p可能指向第i个节点，也可能指向NULL
if (p == NULL)
{
return false;
}
else
{
e = p->data;
return true;
}
}
int LocateElem(LinkNode* L, int e)
{
int i = 1;
LinkNode* p = L->next; //p指向首节点，i置为1（即首节点的序号为1）
while (p != NULL && p->data != e) //查找data值为e的节点，当p的data为e或为查找到时时循环结束
{
p = p->next;
i++;
}
if (p == NULL)
{
return (0);
}
else
{
return i;
}
}
bool ListInsert(LinkNode*& L, int i, int e)
{
int j = 0;
LinkNode* p = L, * s; //p指向头节点，j置为0（即头节点的序号为0），s为创建要被插入元素做准备
//p的作用是标记第i-1个节点的地址，j是标记元素下标，p根据j找到第i-1个节点地址。
if (i < 0)return false; //i错误返回false
while (j < i - 1 && p != NULL)
{
j++;
p = p->next;
} //查找到第i-1个节点，查找第i-1个结点的好处是便于插入操作
//如若查找的是第i个节点，则需在其前面插入，单链表无法指向其前方的元素
if (p == NULL) //未找到第i-1个节点p，返回false
{
return false;
}
else
{
s = (LinkNode*)malloc(sizeof(LinkNode));
s->data = e; //创建新节点s，将其data域置为e
s->next = p->next;
p->next = s; //将s节点插入到p之后
return true;
}
}
bool ListDelete(LinkNode*& L, int i)
{
int j = 0;
LinkNode* p = L, * q; //p指向头节点，j置为0（头结点的序号为0）
if (i next;
} //查到到第i-1个节点，用p指向该节点,查找到第i-1个节点的好处是便于下面的删除操作
q = p->next; //用q指向p的下一个节点
if (p == NULL || q == NULL) //如果p=NULL，则证明未找到i-1个节点如果q==NULL，则证明要删除的节点为NULL（不存在）
{
return false;
}
else
{
p->next = q->next;
free(q); //删除第i个节点
return true;
}
}
三.单链表的应用示例
1.有一个带头结点的单链表L=(a1,b1,a2,b2,······，an,bn),设计一个算法将其拆分成两个带头结点的单链表L1与L2,其中L1=(a1,a2,a3,·······an),L2=(bn,bn-1,······b1),要求L1使用L的头节点。
思路：整体建表法。利用原单链表L中的所有节点通过改变其指针域重组成两个单链表L1和L2。由于L1中节点的相对顺序与L中的相同，所以采用尾插法建立单链表L1；由于L2中的节点相对顺序与L中的相反，所以采用头插法建立单链表L2。
时间复杂度：O(n)
//L1使用尾插法，L2使用头插法
void split(LinkNode*& L, LinkNode*& L1, LinkNode*& L2)
{
LinkNode* p = L->next, * q, * r1; //p指向第一个数据节点
L1 = L; //L1利用原来的L的头节点
r1 = L1; //r1始终指向L1尾节点
L2 = (LinkNode*)malloc(sizeof(LinkNode)); //创建L2的头节点
L2->next = NULL; //置L2的指针域为NULL
while (p != NULL)
{
r1->next = p;
r1 = p; //采用尾插法将p插入L1
p = p->next; //p移动到下一个节点
q = p->next; //q用来记录p的下一个节点
p->next = L2->next;
L2->next = p; //将p连接到L2中
p = q; //p移动到其原来下一个节点位置
}
r1->next = NULL; //L1尾节点的next域置为空
}
2.设计一个算法，删除单链表L中元素值最大的节点
思路：双指针法。在单链表中删除一个节点首先要找到它的前驱节点，用指针p遍历整个单链表，pre指向p的前驱节点，在遍历时用maxp指向data域值最大的节点，maxpre指向max节点的前驱节点，当单链表遍历完成后，通过maxpre节点删除其后继节点。
时间复杂度：O(n)
void delmaxnode(LinkNode*& L)
{
LinkNode* p = L->next, * pre = L, * maxp = p, * maxpre = pre;
//建立四个节点，p用来遍历，pre用来记录p的前一个节点位置，maxp记录元素值最大的节点位置，maxpre用来记录maxp前一节点位置
while (p != NULL)//遍历整个单链表
{
if (maxp->data < p->data)
{
maxp = p; //标记元素最大值的位置
maxpre = pre;
}
pre = p; //推进遍历过程
p = p->next;
}
//删除该元素
maxpre->next = maxp->next;
free(maxp);
}
3.有一个带头结点的单链表L（至少有一个数据节点），设计一个算法实现所有数据节点按data域递增排序。
思路：直接插入法。由于单链表L中有一个以上的数据节点，首先构造一个只含头节点和首节点的有序单链表（只含一个数据节点的单链表一定是有序的）。然后遍历单链表L余下的节点（由p指向），在有序单链表中通过比较找插入节点p的前驱节点（由pre指向它），在pre结点之后插入p节点，直到p==NULL为止。
时间复杂度：O(n*n)
void sort(LinkNode*& L)
{
LinkNode* p, * pre, * q;
p = L->next->next;
L->next->next = NULL;
while (p != NULL)
{
q = p->next; //用q记录p下一个结点的位置
pre = L; //pre找寻L中比p的data域值小的节点的前驱地址
while (pre->next != NULL && pre->next->data < p->data)//寻找过程
{
pre = pre->next;
}
//找到后插入
p->next = pre->next;
pre->next = p;
//p回到其下一个位置
p = q;
}
}
Original: https://blog.csdn.net/qq_64585761/article/details/127098097
Author: zjx…
Title: 单链表
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/654941/
转载文章受原作者版权保护。转载请注明原作者出处！