单链表的定义和表示
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。
链表中的数据是以结点来表示的，每个结点的构成包括两个域：其中存储数据元素信息的域成为数据域（data）；存储直接后继存储位置的域称为指针域（next）。
单链表是由头指针唯一确定的，因此单链表可以用头指针的名字来命名。若头指针名是 L ，则简称该链表为表L。
单链表可由头指针唯一确定，在c语言中可用结构指针来描述：
//单链表的存储结构
typedef struct LNode
{
ElemType data; //结点的数据域
struct LNode *next; //结点的指针域
}LNode,*LinkList; //LinkList为指向结构体LNode的指针类型
区别首元结点、头结点、头指针：
-
首元结点
-
头结点
-
头指针
线性表-单链表的基本操作
链表增加头节点的作用：
- 便于首元结点的处理
- 便于空表和非空表的统一处理
单链表基本操作的实现
①单链表的初始化（构造空表）
【算法步骤】
- 生成新结点作头节点，用头指针 L 指向头节点
- 将头节点的指针域置空
【算法描述】
Status InitList(LinkList &L)
{
L=new LNode; //生成一个新结点作为头节点，用头指针L指向头节点
L->next NULL; //头节点指针域置空
return OK;
}
注：
L=new LNode;（c++)也可写成
L=(LinkList)malloc(sizeof(LNode));©
malloc函数用法（ c ）：
- malloc是动态内存分配函数，用于申请一块连续的指定大小的内存块区域以void类型返回分配的内存区域地址（void为不确定类型指针）
- 在使用malloc开辟空间时，使用完成后要用
free函数释放
- malloc函数必须在其前面加上指针类型
强制转换
- 头文件是
stdlib.h
-
指针自身 = (指针类型*）malloc（sizeof（指针类型）*数据数量）
#include<stdio.h>
#include<stdlib.h>
int main()
{
int *p=NULL;
int n =5;
p=(int*)malloc(sizeof(int)*n);
}
free函数用法( c )：
- 用于释放malloc(或calloc、realloc)函数给指针变量分配的内存空间。
- 使用后该指针变量需要重新
指向NULL
#include<stio.h>
#include<stdlib.h>
int main()
{
int *p=( int*)malloc(sizeof(int)) ;
*p=5;
free(p);
p=NULL;
}
②单链表的销毁（头节点、头指针、所有元素均销毁）
【算法思路】
从头指针开始，依次释放所有结点
【算法描述】
Status DestoryList_L(LinkList &L)
{
LinkList p; //或Lnode *p;p为指针变量
while(L) //L非空
{
p=L; //p、L指向同一结点
L=L->next; //L指针指向下一个结点
delete p; //删除结点p
}
}
③清空单链表 （头指针、头节点仍在）
【算法思路】
依次释放所有结点，并将头节点指针域设置为空
【算法描述】
Status ClearList(LinkList &L)
{
Lnode *p,*q; //或LinkList p,q;
p=L->next;
while(p) //非空，没到表尾
{
q=p->next; //q指向p的下一个结点
delete p; //销毁p
p=q; //使p、q指向同一结点
}
L->next=NULL; //将头节点指针域置为空
return OK;
④求单链表的表长
【算法思路】
从首元结点开始，依次计数所有结点
【算法描述】
int ListLength_L(LinkList L)
{
Linklist p; //或Lnode *p;
p=L->next; //p指向第一个结点
i=0; //计数器i
whilw(p) //遍历单链表，统计结点数
{
i++;
p=p->next; //p指向下一个结点
}
}
⑤取第i个元素值 O(n)
【算法思路】
从首元结点出发，顺着链域next逐个结点向下访问
【算法描述】
Status GetElem(LinkList L,int i,ELemType &e)
{
p=L->next;j=1; //p指向首元结点，计数器j=1
while(p&&j<i)
{
p=p->next; //p指向下一个结点
++j;
}
if(!p||j>i) return ERROR; //i不合法i>n或i≤0
e=p->data; //取第i个结点的数据域
return OK;
}
⑥按值查找 O(n)
【算法思路】
从首元结点出发，依次顺着链域next向下查，直到查到与e相等或为空
【算法描述】
LNode *LocateElem(LinkList L,ElemType e)
{
p=L->next; //p指向首元结点
while(p&&p->data!=e) //顺链向后扫描，直到p为空或p所指数据域=e
p=p->next; //p指向下一个结点
return p; //若查找成功返回e的结点地址p，查找失败p为NULL
}
⑦插入结点 O(n)
【算法思路】
将值为e的新结点插入到表的第i个结点的位置上，即插入到a(i-1)与a(i)之间,使a(i-1)的指针域指向数据域为e的那个新结点，使数据域为e的这个结点的指针域指向a(i)
【算法描述】
Status ListInsert(LinkList &L,int i,ElemType e)
{
p=L;j=0; //p指向头结点
while(p&&(j<i-1))
{
p=p->next;++j; //查找第i-1个结点，p指向该结点
}
if(!p||j>i-1) return ERROR; //i>n+1或i<1
s=new LNode; //生成新结点*s
s->data=e; //将结点*s的数据域置为e
s->next=p->next; //将结点*s的指针域指向结点a(i)
p->next=s; //将结点*p的指针域指向结点*s
return OK;
}
⑧删除结点 O(n)
【算法思路】
删除单链表第i个结点a(i)并释放a(i)的空间,使a(i-1)的指针域指向a(i+1)
【算法描述】
Status ListDelete(LinkList &L,int i)
{
p=L;j=0; //p指向头结点
while((p->next)&&(j<i-1))
{
p=p->next;
++j; //查找第i-1个结点，p指向该结点
}
if(!(p->next)||(j>i-1)) return ERROR; //i>n或i<1时，删除位置不合理
q=p->next; //临时保存被删除结点的地址以备释放
p->next=q->next; //改变删除结点前驱结点的指针域
delete q; //释放删除结点的空间
return OK;
}
⑨前插法创建单链表 O(n)
【算法思路】
逆序输入n个元素的值，建立带表头结点的单链表L
【算法描述】
void CreateList_H(LinkList &L,int n)
{
L=new LNode;
L->next=NULL; //先建立一个带头节点的空链表
for(i=0;i<n;++i)
{
p=new LNode; //生成新结点*p
cin >> p-data; //输入元素值赋给新结点*p的数据域
p->next=L-next; L->next=p; //将新结点*p插入到头节点之后
}
}
⑩后插法创建单链表 O(n)
【算法思路】
正序输入n个元素的值，建立带表头结点的单链表L
【算法描述】
void CreatList_R(LinkList &L,int n)
{
L=new LNode;
L->next=NULL; //先建立一个带头节点的空链表
r=L; //尾指针r指向头节点
for(i=0;i<n;++i)
{
p=new LNode; //生成新结点
cin >> p->data; //输入元素值赋给新结点*p的数据域
p->next=NULL;r->nextp; //将新结点*p插入尾结点*r之后
r=p; //r指向新的尾结点*p
}
}
借鉴：《数据结构》严蔚敏