线性表的链式存储结构
前言：
采用链式存储结构的线性表称为链表，由n个结点链接而成
特点：
- 对于顺序表的使用，我们一般是根据最大需求来定义，然而这样常常会造成一定的存储空间的浪费，而链式存储结构可以根据需要来进行动态的调整
- 链表中逻辑上相邻的数据元素其物理存储位置不要求紧邻，即链表中结点的逻辑次序和物理次序不一定相同
- 比起顺序存储结构除了要存储其本身的信息外，还要存储一个指向其直接后继元素的存储位置的信息
链表是一种复杂的数据结构，其数据之间的相互关系可以分为三种：单链表，双向链表，循环链表
单链表：
一个线性表的链式存储结构当中每个结点如果只包含一个指针域，则这种线性表为单链表
结点：
每个结点的构成方式如下所示：
- 数据域：存储数据元素信息（该结点的值）的域称为数据域
- 指针域：存放结点的直接后继元素的地址（位置）的指针域（链域）
这两部分信息（即当前元素和指向后继元素的存储位置的指针）组成数据元素称为存储映像，称为结点（Node）
对于整个单链表的构成形式是，每个结点的存储地址是存放在其前驱结点的指针域（next）中的，由于第一个元素结点无前驱元素，所以为了使单链表中的第一个结点与其余各点的基本运算统一，通常在单链表前另加一个表头结点，表头结点的链域指针指向第一个结点。
因为头结点出现是为了规范操作，所以对于一个链表来说，头结点不一定是链表的必须元素。
单链表的描述：
typedef int Elemtype; //存储的数据类型
typedef struct node //结点类型定义
{
Elemtype data; //数据域
struct node* next; //指针域
}Node;
typedef Node* LinkList;
- Node* 和LinkList是同一类型的指针变量，命名不同是为了便于区分概念
- Linklist类型的指针变量表示它是单链表的头指针
- Node* 类型变量表示它是指向某一结点的指针
单链表的运算：
建立单链表
动态建立单链表的的常用方法一般有两种：头插法，尾插法
- 头插法建单链表
算法思路：
顾名思义，也就是不断的生成一个新的结点来存储输入的 数据元素，然后把这个新的结点插入到当前链表的表头上， 直到遇到输入结束的标志就停止建表，不过这样生成的表中 结点次序，与输入数据次序相反代码实现
LinkList CreatList(int end) { LinkList head; //头指针 Node* p; //工作指针 int x; head = NULL; //头指针初始化为空 scanf("%d",&x); //输入数据元素 while(x!=end) //读入的元素为end时，建表停止 { p = (Node*)malloc(sizeof(Node*));//生成新的结点 p->data = x; //将读入的数据存入新结点的数据域中 p->next = head; //新结点的链域指向头指针之前指向的结点 head = p; //头指针指向新的结点 scanf("%d",&x); } return head; //返回生成的单链表的头指针 } - 尾插法建立单链表
算法思路：
同理，只不过是把生成的新结点插入到当前链表的表尾上，所以这样生成的单链表结点次序是和输入的结点次序是一样的代码实现
//第一种方法，不采用头结点 LinkList CreatList(int end) { int x; LinkList head; //多用了一个尾指针，始终指向当前链表的尾结点 Node *s,*r; head = NULL; r = NULL; //初始化为空 scanf("%d",&x); while(x!=end) { p = (Node*)malloc(sizeof(Node*)); p->data = x; //如果是第一个结点，则让头指针指向他 if(head!=NULL) head=s; else r->next = p;//否则则直接将新结点插入到*r的后面 r=p; //尾指针指向新表尾 scanf("%d",&x); } r->next = NULL; return head; } //第二种方法，采用头结点 LinkList CreatList(int end) { int x; //生成头结点 LinkList head = (Node*)malloc(sizeof(Node*)); Node *p,*r; r = head; //尾指针初始化指向头结点 scanf("%d",&x); while(x!=end) { p = (Node*)malloc(sizeof(Node*)); p->data = x; r->next = p; r = p; } r->next = NULL; return head; }
单链表的基本操作
</br>
//在建表方式不同的情况下，操作会略有改变
//因为头结点是否存在会影响其代码的实现，不过思路大体相同
//状态码
#define OK 1
#define ERROR 0
typedef int Status;
//初始化单链表
Status InitList(LinkList L)
{
L->next = NULL; //头结点指针域置为空
return OK;
}
//清空单链表
//即把除头结点之外的所有结点空间释放，并把头结点的指针与置为NULL
Status ClearList(LinkList L)
{
Node *q,*p; //工作指针
p = L->next; //p指向第一个结点
while(p)
{
q = p;
p = p->next; //p指向下一个结点
free(q); //释放q（即上一个结点）的空间
}
L->next = NULL;
return OK;
}
//判断链表是否为空
int ListEmpty(LinkList L)
{
return (L->next == NULL)//只需要判断头指针是否指向空即可
}
//计算链表长度
int ListLength(LinkList L)
{
int count = 1;
Node *p;
p = L->next; //从第一个结点开始计数，来计算元素个数
while(p)
{
count++;
p = p->next;
}
return count; //返回元素个数
}
//GetElem的具体操作
Status GetElem(LinkList L,int i,Elemtype *e)
{
int j = 1;
Node *p;
p = L;
while(p && j<i)
{
p = p->next;
j++;
}
if(!p || j>i) //找不到此位置，返回错误
return ERROR;
*e = p->data; //通过e来返回第i个位置的元素
return OK;
}
//LocateElem操作
int LocateElem(LinkList L,Elemtype e)
{
int i = 1; //记录该元素的位置
Node *p;
p = L;
while(p && p->data !=e)
{
p = p->next;
i++;
}
if(!p)
return ERROR; //查找失败
else return i; //返回该元素的位置
}
//ListInsert操作
Status ListInsert(LinkList L,int i,Elemtype e)
{
Node *p,*s;
int k = 1;
p = L; //指向头指针
while(k<i && p) //将指针移向第i个元素的前驱元素
{
k++;
p = p->next;
}
if(k>i || !p) //插入的位置不合理
return ERROR;
s = (Node*)malloc(sizeof(Node*));//生成新结点
if(!s) //内存分配失败
return ERROR;
s->data = e; //将e赋给新结点的数据域
s->next = p->next; //新结点的指针域指向第i个结点
p->next = s; //第i-1个结点指向新结点
return OK;
}
//ListDelete操作
Status ListDelete(LinkList L,int i,Elemtype *e)
{
Node *p,*q;
int k = 1;
p = L;
while(k<i && p)
{
k++;
p = p->next;
}
if(k>i || !p) //删除的位置不合理
return ERROR;
q = p->next; //q指向第i个结点
p->next = q->next; //p指向q的下一个结点
*e = q->data; //将删除结点的数据元素保存在e
free(q); //释放结点q
return OK;
}
//销毁链表操作
Status DestroyList(LinkList L)
{
Node *p; //用来指向当前要释放的结点
while(L)
{
p = L; //p指向当前要释放的结点
L = L->next; //L指向下一个要释放的结点
free(p); //释放结点p
}
return OK;
}
顺序表与单链表的对比
- 存储分配方式
+ 顺序表存储结构采用一段连续的存储单元依次存储线性表的元素
+ 单链表则用一组任意的存储单元来存放线性表元素
- 时间性能
- 查找
- 顺序表O(1)
- 单链表O(n)
- 插入和删除
- 顺序表O(n)
- 单链表本身的插入和删除操作是O(1)，但由于要确定插入和删除的位置，所以是O(n)
- 查找
- 空间性能
- 顺序表容易造成存储空间的浪费
- 单链表不需要提前分配好空间，只有需要就给分配，元素个数也不受限制
