单链表
定义:
单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。
单链表通过一组任意的存储单元来存储线性表中的数据元素,不需要使用地址连续的存储单元,因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。
特点:
- 单链表不要求逻辑上相邻的两个元素在物理位置上也相邻,因此不需要连续的存储空间。
- 单链表是非随机的存储结构,即不能直接找到表中某个特定的结点。查找某个特定的结点时,需要从表头开始遍历,依次查找。
对于每个链表结点,除了存放元素自身的信息外,还需要存放一个指向其后继的指针。
单链表中结点类型的描述:
typedef struct LNode
{ //定义单链表结点类型
int data; //数据域,可以是别的各种数据类型,本文统一用int类型
struct LNode *next; //指针域
}LNode, *LinkList;
单链表的读取
弊端:在单链表中,由于第 i i个元素到底在哪没办法一开始就知道,必须的从头开始找
代码:
//声明一个指针p指向链表的第一个结点
typedef struct Node
{
ElemType data; //结点的数据域
struct Node *next; //结点的指针域
}Node; //结构体的类型别名Node
typedef struct Node *LinkList; //LinkList为指向结构体Node的指针类型(结构体指针)
/* 初始条件:链式线性表L已存在,1≤i≤ListLength(L) */
/* 操作结果:用e返回L中第i个数据元素的值 */
Status GetElem(LinkList L,int i,ElemType *e)
{
int j; //初始化j从1开始
LinkList p; /* 声明头指针p */
p = L->next; /* 让p指向链表L的第一个结点 */
j = 1; /* j为计数器 */
while (p && j<i) /* p不为空或者计数器j还没有等于i时,循环继续 */
{
p = p->next; /* 让p指向下一个结点 */
++j; //最后一次加后,j=i,由此退出循环
}
if ( !p || j>i )
return ERROR; /* 第i个元素不存在 */
*e = p->data; //将获取到的数据元素赋值给解引用的指针e,由此返回给主调函数的实参e,一旦返回给主调函数,指针变量就不会随着被调函数的结束而销毁。
return OK;
}
说白了,就是从头开始找,直到第i个结点结束。
单链表的插入
插入链表表头
插入链表表尾
插入链表中任意位置:
//只需要让s->nexthep->next的指针做一点改变即可
s->next = p->next; //将p的后继结点赋值给s的后继
p->next = s; //将s赋值给p的后继
单链表第i个数据插入结点:
Status ListInsert(LinkList *L,int i,ElemType e)
{
int j;
LinkList p,s; //头指针p和新元素指针s
p = *L; //*L返回指定的地址内的变量的值,此值其实是头结点数据元素的存储位置
j = 1; //计数器
while (p && j < i) // 寻找第i个结点
{
//将指向下一元素的指针p->next赋值给p,以便下次循环使用
++j; //计数器累加
}
if (!p || j > i)
return ERROR; //第i个元素不存在
s = (LinkList)malloc(sizeof(Node)); // 为新结点分配内存空间,新指针s指向该新结点
//malloc函数的返回的是无类型指针,在使用时一定要强制转换为所需要的类型
s->data = e; //为新结点数据域赋值
s->next = p->next; // 将p的后继结点赋值给s的后继
p->next = s; //将s赋值给p的后继
return OK;
}
单链表的删除
单链表的删除直接绕过需要删除的结点即可。
q = p->next;
p->next = q->next; //将q的后继赋值给p的后继
单链表删除第i个数据删除结点的代码:
//操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1
Status ListDelete(LinkList *L,int i,ElemType *e)
{
int j;
LinkList p,q;
p = *L; //*L返回指定的地址内的变量的值,此值其实是头结点数据元素的存储位置
j = 1;
while (p->next && j < i) //遍历寻找第i个元素
{ //p->next保证下一个结点存在
p = p->next; //将前驱结点的指针域重新赋值为p,以便下次循环使用
++j;
}
if (!(p->next) || j > i)
return ERROR; //第i个元素不存在
p->next = q->next; // 将q的后继赋值给p的后继
*e = q->data; //将存储地址q对应的存储内容赋值给e
free(q); //让系统回收此结构体指针(结点),释放内存
return OK;
}
对于插入或删除数据越频繁的操作,单链表的效率优势更明显!