为了表示每个数据元素ai 与其后继数据元素ai+1 之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息外，还需存储一个指示其直接后继的信息；
存储数据元素信息的域称为数据域，把存储直接后继的位置域称为指针域，指针域存储的信息叫指针或链。这两部分信息组成数据元素ai 的存储映像，称为结点（Node)
n个结点结成一个链表---线性表（a1....ai)的链式存储结构，链表的每个结点中只包含一个指针域，叫单链表。单链表通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。
把链表的第一个结点的存储位置叫做头指针，第一个结点称为头节点，头节点的数据域可以不存储任何信息
头指针：
指链表指向第一个结点的指针，若链表有头结点，则时指向头节点的指针。
头指针具有标识的作用，所以常用头指针冠以链表的名称
无论链表是否为空，头指针均不为空，头指针时链表的必要元素
线性表如果为空表，则头结点的指针域为空
/*线性表的单链表存储结构*/
typedef struct Node
{
ElemType data;
struct Node * next;
} *LinkList;
结点有存放数据元素的数据域存放后继结点地址的指针域组成。
假设p 是指向线性表第i 个元素指针，ai 的数据域 p->data(数据元素) 表示，ai 的指针域可以哟个p->next（指针） 来表示，p->next 指向i+1 的元素。
单链表的读取
思路：
1、声明一个结点p指向链表第一个结点，初始化j从1开始；
2、当j<i就遍历链表，让p 的指针向后移动，不断指向下一个结点，j++;
3、当链表末尾p为空,则说明第i元素不存在；
4、查找成功，返回结点 p 的数据；
Status GetElem(LinkList L, int i, ElemType *e)
{
int j;
LinkList p;
p = L->next;//让p 指向第一个结点
j = 1;//计数器
while (p && j < i)
{
p = p->next;
++j;
}
if (!p || j > i)return ERROR;//元素不存在
*e = p->data;
return OK;
}
插入试图：
插入算法思路：
1、声明一结点p指向链表第一个结点，初始化j从1开始
2、当j<i 时，就遍历链表，让p 的指针移动，不断指，向下一个结点，j++;
3、若到链表尾p为空，则说第i 个元素不存在；
4、否则查找成功，在系统中，生成一个空结点s;
5、将数据元素e赋值给s->data;
6、单链表插入标准语句s->next= p->next ;p->next =s
7、返回成功。
代码：
Status ListInsert(LinkList *L, int i, ElemType e)
{
int j;
LinkList p, s;
p = *L;
j = 1;
while (j < i && p)
{
p = p->next;
j++;
}
if (!p || j>i) return ERROR;
//查找成功，申请内存
s = (LinkList )malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
}
单链表的删除
设存储元素ai 的结点为q，要实现把结点q 删除单链表操作，其实就是将他的前继结点的指针绕过，
指向他的后继结点即可
实际上就一步：p->next = p->next->next,用q 来取代p->next，
q=p->next ; p->next =q-next;
思路：
1、声明一结点p 指向链表第一个结点，初始化j从1开始；
2、当j<i时，就遍历链表，让p 的指针向后移动，不断指向下一个结点，j ++；
3、若到链表末尾p 为空，则说明第i 个元素不存在；
4、否则查找成功，将欲删除的结点p->next 赋值给q;
5、单链表删除的标准语句； p-.next =q->next;
6、将q 的结点中的数据赋值给e，作为返回。
7、释放q 结点；
8、反回成功；
Status ListDelete(LinkList *L, int i, ElemType e)
{
int j;
LinkList p, q;
while (j < i && p)
{
p = p->next;
j++;
}
if (!p|| j > i) return ERROR;
q = p->next;
p->next = q->next;
e= q->data;
free(q);
return OK;
}
单链表的插入跟删除主要有两部分组成： 遍历查找第i 个元素；插入和删除元素。
对于插入或删除数据越频繁，单链表的效率优势就越明显
创建单链表的过程就时一个动态生成链表的过程，即从“空表”的初始状态起，依次建立各元素结点，并逐个插入。
单链表创建：
1、声明一结点p ,和计数器i；
2、初始化一个空链表L；
3、让L的头结点的指针指向NULL，即建立一个带头结点的单链表
4、循环：
生成一新结点赋值给p;
随机生成一数字赋值给P ,的数据域p->data;
将p 插入到头结点与前一个新结点之间。
//头插法
void CreateListHead(LinkList *L, int n)
{
LinkList p;
int j;
srand(time(0));//初始化随机数种子
*L = (LinkList)malloc(sizeof(Node));//初始化L
(*L)->next = NULL;//先建立一个带2头结点的单链表
for (int i = 0; i < n; i++)
{
p = (LinkList)malloc(sizeof(Node)); //生成新结点
p->data = rand() % 100 + 1;//随机生成100以内的数字
p->next = (*L)->next;
(*L)->next = p;
}
}
//尾插法
void CreateListTail(LinkList *L, int n)
{
LinkList p, r;
int i;
srand(time(0));
*L = (LinkList )malloc(sizeof(Node));
r = *L;//r指向尾部的结点
for (i = 0; i < n; i++)
{
p = (LinkList)malloc(sizeof(Node));
p->data = rand() % 100 + 1;
r->next = p;//将尾部终端结点的指针指向新结点
r = p;//将当前新结点定义为尾部终端结点
}
r->next = NULL; //表示当前链表结束
}
单链表的整表删除
算法思路：
1、声明一个结点p,q ；
2、将第一个结点赋值给p；
3、循环：
将下一个结点赋值给q;
释放p;
将q 赋值给p;
//删除单链表
Status CrearList(LinkList *L)
{
LinkList p, q;
p = (*L)->next;
while (p)
{
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL;
return OK;
}
注意： 遍历p 的作用，它使得下一个结点是谁得到了记录，以便于等当前结点释放后，把下一结点拿回来补充。
单链表结构与顺序存储结构的优缺点
存储分配方式：
a,顺序存储结构用一段连续的存储单元依次存储线性表的数据元素 b.单链表采用链式存储解雇，用一组任意的存储单元存放线性表的元素
时间性能：
查找：顺序存储结构O(1) ，单链表O(1)
插入和删除：顺序存储结构需要平均移动表长一半元素，时间为O（n); 表在找出某位置的指针后，插入删除时间O(1)；
空间性能：
顺序存储结构需要预分配存储空间，大了浪费，小了易发生溢出
单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。
网友评论