线性表的链式存储与删除
1.头指针和头结点的区别：
头指针：
a.头指针是指链表指向第⼀个结点的指针，若链表有头结点，则是指向头结点的指针
b.头指针具有标识作⽤，所以头指针冠以链表的名字（指针变量的名字）
c.⽆论链表是否为空，头指针均不为空
d.头指针是链表的必要元素
头结点：
a.头结点是为了操作的统⼀和⽅便⽽设⽴的，放在第⼀个元素的结点之前，其数据域⼀般⽆意义（但也可以⽤来存放链表的长度）
b.有了头结点，对在第⼀元素结点前插⼊结点和删除第⼀结点起操作与其它结点的操作就统⼀了
c.头结点不⼀定是链表的必要元素
2.单链表的读取
在线性表的顺序存储结构中，我们要计算任意⼀个元素的存储位置是很容易的。但在单链表中，由于第i个元素到底在哪？没办法⼀开始就知道，必须得从头开始。因此，对于单链表实现获取第i个元素的数据的操作GetElem，在算法上，相对要⿇烦⼀些。
获得链表第i个数据的算法思路：
a.声明⼀个指针p指向链表第⼀个结点，初始化j从1开始；
b.当j<i时，就遍历链表，让p的指针向后移动，不断指向下⼀结点，j累加1；
c.若到链表末尾p为空，则说明第i个结点不存在；
d.否则查成功，返回结点p的数据。
实现代码算法如下：
/* 初始条件：顺序线性表L已存在，1≤i≤
ListLength(L) */
/* 操作结果：⽤e返回L中第i个数据元素的值 */
Status GetElem(LinkList L, int i, ElemType *e)
{
int j;
LinkList p;            /* 声明⼀指针p */
p = L->next;        /* 让p指向链表L的第个结点 */
j = 1;                /* j为计数器 */
/* p不为空且计数器j还没有等于i时，循环继续 */
while (p && j < i)
{
p = p->next;    /* 让p指向下⼀个结点 */
++j;
}
if (!p || j > i)
return ERROR;      /* 第i个结点不存在 */
*e = p->data;      /* 取第i个结点的数据 */
return OK;
}
说⽩了，就是从头开始，直到第i个结点为⽌。由于这个算法的时间复杂度取决于i的位置，当i=1时，则不需遍历，第⼀个就取出数据了，⽽当i=n时则遍历n-1次才可以。因此最坏情况的时间复杂度是O(n)。
由于单链表的结构中没有定义表长，所以不能事先知道要循环多少次，因此也就不⽅便使⽤for来控制循环。其主要核⼼思想就是“⼯作指针后移”，这其实也是很多算法的常⽤技术。
3.单链表的插⼊
先来看单链表的插⼊。假设存储元素e的结点为s，要实现结点p、p->next和s之间逻辑关系的变化，只需将结点s插⼊到结点p和p-
>next之间即可。
根本⽤不着惊动其他结点，只需要让s->next和p->next的指针做⼀点改变即可。
s->next = p->next; p->next = s;
解读这两句代码，也就是说让p的后继结点改成s的后继结点，再把结点s变成p的后继结点
如果先p->next=s；再s->next=p->next；会怎么样？因为此时第⼀句会使得将p->next给覆盖成s的地址了。那么s->next=p->next，其实就等于s->next=s。这样的插⼊操作就是失败的，造成了临场掉链⼦的尴尬局⾯。所以这两句是⽆论如何不能反的，这点初学者⼀定要注意。
单链表第i个数据插⼊结点的算法思路： 1.声明⼀指针p指向链表头结点，初始化j从1开始； 2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下⼀结点，j累加1； 3.若到链表末尾p为空，则说明第i个结点不存在； 4.否则查成功，在系统中⽣成⼀个空结点s； 5.将数据元素e赋值给s->data； 6.单链表的插⼊标准语句s->next=p->next;p->next=s； 7.返回成功。
实现代码算法如下：
/* 初始条件：顺序线性表L已存在，1≤i≤
ListLength(L)， */
/* 操作结果：在L中第i个结点位置之前插⼊新的数
据元素e，L的长度加1 */
Status ListInsert(LinkList *L, int i, ElemType e)
{
int j;
LinkList p, s;
p = *L;
j = 1;
/
* 寻第i-1个结点 */
while (p && j < i)
{
p = p->next;
++j;
}
/* 第i个结点不存在 */
if (!p || j > i)
return ERROR;
/* ⽣成新结点（C标准函数） */
s = (LinkList)malloc(sizeof(Node));
s->data = e;
/* 将p的后继结点赋值给s的后继 */
s->next = p->next;
/* 将s赋值给p的后继 */
p->next = s;
return OK;
}
在这段算法代码中，我们⽤到了C语⾔的mal-loc标准函数，它的作⽤就是⽣成⼀个新的结点，其类型与Node是⼀样的，其实质就是在内存中了⼀⼩块空地，准备⽤来存放数据e的s结点。
4.单链表的删除
单链表第i个数据删除结点的算法思路：
a.声明⼀指针p指向链表头结点，初始化j从1开始；
b.当j<i时，就遍历链表，让p的指针向后移动，不断指向下⼀个结点，j累加1；
c.若到链表末尾p为空，则说明第i个结点不存在；
d.否则查成功，将欲删除的结点p->next赋值给q；
e.单链表的删除标准语句p->next=q->next；
f.将q结点中的数据赋值给e，作为返回；
g.释放q结点；
h.返回成功。
实现代码算法如下：
/* 初始条件：顺序线性表L已存在，1≤i≤
ListLength(L) */
/* 操作结果：删除L的第i个结点，并⽤e返回其
值，L的长度减1 */
Status ListDelete(LinkList *L, int i, ElemType *e)
{
int j;
LinkList p, q;
p = *L;
j = 1;
/* 遍历寻第i-1个结点 */
while (p->next && j < i)
{
p = p->next;
++j;
}
/* 第i个结点不存在 */
if (!(p->next) || j > i)
return ERROR;
q = p->next;
/* 将q的后继赋值给p的后继 */
p->next = q->next;
/* 将q结点中的数据给e */
*e = q->data;
/* 让系统回收此结点，释放内存 */
free(q);
return OK;
c语言listinsert函数}
这段算法代码⾥，我们⼜⽤到了另⼀个C语⾔的标准函数free。它的作⽤就是让系统回收⼀个Node结点，释放内存。
分析⼀下刚才我们讲解的单链表插⼊和删除算法，我们发现，它们其实都是由两部分组成：第⼀部分就是遍历查第i个结点；第⼆部分就是插⼊和删除结点。
从整个算法来说，我们很容易推导出：它们的时间复杂度都是O(n)。如果在我们不知道第i个结点的指针位置，单链表数据结构在插⼊和删除操作上，与线性表的顺序存储结构是没有太⼤优势的。但如果，我们希望从第i个位置，插⼊10个结点，对于顺序存储结构意味着，每⼀次插⼊都需要移动n-i个结点，每次都是O(n)。⽽单链表，我们只需要在第⼀次时，到第i个位置的指针，此时为O(n)，接下来只是简单地通过赋值移动指针⽽已，时间复杂度都是O(1)。显然，对于插⼊或删除数据越频繁的操作，单链表的效率优势就越是明显。
5.单链表的整表创建
单链表整表创建的算法思路：
a.声明⼀指针p和计数器变量i；
b.初始化⼀空链表L；
c.让L的头结点的指针指向NULL，即建⽴⼀个带头结点的单链表；
d.循环：
⽣成⼀新结点赋值给p；
随机⽣成⼀数字赋值给p的数据域p->data；
将p插⼊到头结点与前⼀新结点之间。
实现代码算法如下：
/* 随机产⽣n个元素的值，建⽴带表头结点的单链
线性表L（头插法） */
void CreateListHead(LinkList *L, int n)
{
LinkList p;
int i;
/* 初始化随机数种⼦ */
srand(time(0));
*L = (LinkList)malloc(sizeof(Node));
/* 先建⽴⼀个带头结点的单链表 */
(*L)->next = NULL;
for (i = 0; i < n; i++)
{
/
* ⽣成新结点 */
p = (LinkList)malloc(sizeof(Node));
/* 随机⽣成100以内的数字 */
p->data = rand() % 100 + 1;
p->next = (*L)->next;
/* 插⼊到表头 */
(*L)->next = p;
}
}
这段算法代码⾥，我们其实⽤的是插队的办法，就是始终让新结点在第⼀的位置。我也可以把这种算法简称为头插法.
可事实上，我们还是可以不这样⼲，为什么不把新结点都放到最后呢，这才是排队时的正常思维，所谓的先来后到。我们把每次新结点都插在终端结点的后⾯，这种算法称之为尾插法。
实现代码算法如下：
/* 随机产⽣n个元素的值，建⽴带表头结点的单链
线性表L（尾插法） */
void CreateListTail(LinkList *L, int n)
{
LinkList p,r;
int i;
/* 初始化随机数种⼦ */
srand(time(0));
/* 为整个线性表 */
*L = (LinkList)malloc(sizeof(Node));
/* r为指向尾部的结点 */
r = *L;
for (i = 0; i < n; i++)
{
/* ⽣成新结点 */
p = (Node *)malloc(sizeof(Node));
/* 随机⽣成100以内的数字 */
p->data = rand() % 100 + 1;
/* 将表尾终端结点的指针指向新结点 */
r->next = p;
/
* 将当前的新结点定义为表尾终端结点 */
r = p;
}
/* 表⽰当前链表结束 */
r->next = NULL;
}
注意L与r的关系，L是指整个单链表，⽽r是指向尾结点的变量，r会随着循环不断地变化结点，⽽L则是随着循环增长为⼀个多结点的链表。这⾥需解释⼀下，r->next=p；的意思，其实就是将刚才的表尾终端结点r的指针指向新结点p.
6.单链表的整表删除
当我们不打算使⽤这个单链表时，我们需要把它销毁，其实也就是在内存中将它释放掉，以便于留出空间给其他程序或软件使⽤。
单链表整表删除的算法思路如下：
a.声明⼀指针p和q；
b.将第⼀个结点赋值给p；
c.循环：
将下⼀结点赋值给q；
释放p；
将q赋值给p。
实现代码算法如下：
/* 初始条件：顺序线性表L已存在，操作结果：将L
重置为空表 */
Status ClearList(LinkList *L)
{
LinkList p, q;
/* p指向第⼀个结点 */
p = (*L)->next;
/* 没到表尾 */
while (p)
{
q = p->next;
free(p);
p=q;
}
/
* 头结点指针域为空 */
(*L)->next = NULL;
return OK;
}
这段算法代码⾥，常见的错误就是有同学会觉得q变量没有存在的必要。在循环体内直接写free(p); p = p->next；即可。可这样会带来什么问题？
要知道p指向⼀个结点，它除了有数据域，还有指针域。你在做free(p)；时，其实是在对它整个结点进⾏删除和内存释放的⼯作。这就好⽐皇帝快要病死了，却还没有册封太⼦，他⼉⼦五六个，你说要是你脚⼀蹬倒是解脱了，这国家咋办，你那⼏个⼉⼦咋办？这要是为了皇位，什么亲兄弟⾎⾁情都成了浮云，⼀定会打起来。所以不⾏，皇帝不能马上死，得先把遗嘱写好，说清楚，哪个⼉⼦做太⼦才⾏。⽽这个遗嘱就是变量q的作⽤，它使得下⼀个结点是谁得到了记录，以便于等当前结点释放后，把下⼀结点拿回来补充。
7.静态链表
其实C语⾔真是好东西，它具有的指针能⼒，使得它可以⾮常容易地操作内存中的地址和数据，这⽐其他⾼级语⾔更加灵活⽅便。后来的⾯向对象语⾔，如Java、C#等，虽不使⽤指针，但因为启⽤了对象引⽤机制，从某种⾓度也间接实现了指针的某些作⽤。但对于⼀些语⾔，如Basic、Fortran等早期的编程⾼级语⾔，由于没有指针，链表结构按照前⾯我们的讲法，它就没法实现了。怎么办呢？
有⼈就想出来⽤数组来代替指针，来描述单链表。真是不得不佩服他们的智慧，我们来看看他是怎么做到的。
⾸先我们让数组的元素都是由两个数据域组成，data和cur。也就是说，数组的每个下标都对应⼀个data和⼀个cur。数据域data，⽤来存放数据元素，也就是通常我们要处理的数据；⽽cur相当于单链表中的next指针，存放该元素的后继在数组中的下标，我们把cur叫做游标。
我们把这种⽤数组描述的链表叫做静态链表，这种描述⽅法还有起名叫做游标实现法。
为了我们⽅便插⼊数据，我们通常会把数组建⽴得⼤⼀些，以便有⼀些空闲空间可以便于插⼊时不⾄于溢出。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。