线性表

线性表是最简单，前后排的数据结构

线性表基本概念

具有相同特性的数据元素的有限的序列

线性表特点

• 元素个数有限
• 元素具有逻辑上的顺序性
• 元素是数据元素
• 元素具有抽象性

线性表是逻辑结构，表示元素之间一对一的相邻关系
顺序表和单链表是存储结构

顺序表

存储方式

• 除第一个元素与最后一个元素，其他每个元素都有一个直接前驱和一个直接后继
• 存储地址连续，逻辑顺序与物理顺序相同
• 顺序表中每个元素占$k$个存储单元，第1个元素存储地址为$m$，则第$i$个元素的存储地址是$mk(i-1)$

代码

定义

静态分配

typedef struct{  // 顺序表定义 
	ElemType data[MaxSize];  // 顺序表的元素
	int length;  // 当前长度 
}SeqList;

动态分配

typedef struct{  // 顺序表定义 
	ElemType *data;  // 数据表元素基址
	int MaxSize;  // 数据最大容量 
	int length;  // 数据的当前个数 
}SeqList;

时间复杂度：$O(n)$

初始化

Status Init(SeqList L){  // 初始化顺序表 
	L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize); // 分配存储空间
	if(! L.data)  // 分配空间失败 
		return false; 
	L.length = 0;  // 空表长度为0
	L.MaxSize = InitSize;  // 初始存储容量	
    return true;
}

插入元素

/* 插入元素
L：顺序表
i：插入位置  1 <= i <= L.length + 1 
x：插入元素
返回：成功 1
      失败 0
*/ 
bool ListInsert(SeqList &L, int i, ElemType x){  
	if(i < 1 || i > L.length + 1)
		return false;
	if(L.length >= L.MaxSize)  // 存储空间已满
		return false;
	for(int j = L.length ; j > i ; j--)  // i元素及之后的元素后移
		L.data[j] = L.data[j-1];
	L.data[i-1] = x;  // 赋值 
	L.length++;  // 表长+1
	return true; 
}

最好情况：$\text{O}(1)$
最坏情况：$\text{O}(n)$
平均情况：$\text{O} (n)$

• 插入$i$位置移动$n-i$个元素
• 平均移动个数$\dfrac{n}{2}$

删除元素

/*删除元素
L：顺序表
i：删除位置  1 <= i <= L.length
x：删除元素
返回：成功 1
      失败 0
*/
bool ListDelete(SeqList &L, int i, ElemType &x){
	if(i < 1 || i > L.length)  // 判断i是否符合范围 
		return false;
	x = L.data[i-1];  // 删除元素赋值
	for(int j = i ; j < L.length ; j++)  // 将i位置后的元素前移
		L.data[j-1] = L.data[j];
	L.length--;  // 表长-1
	return true; 
}

最好情况：$\text{O}(1)$
最坏情况：$\text{O}(n)$
平均情况：$\text{O} (n)$

• 在$i$位置删除元素需要移动$n-i-1$个元素
• 平均移动：$\dfrac{n-1}{2}$

元素查找

/*查找素
L：顺序表
x：查找元素
返回：成功 1
      失败 0
*/
ElemType LocateElem(SeqList L, ElemType x){
	for(int i = 0 ; i < L.length ; i++)
		if(L.data[i] == x)
			return i+1;  // 下标为i，位置i+1
	return  false;
}

最好情况：$\text{O}(1)$
最坏情况：$\text{O}(n)$
平均情况：$\text{O} (n)$

逆置

/*
逆置顺序表
left：左起始
right：右起始
i<j：i和j互换或者i和j相等都停止
*/
for(int i=left, j=right ; i < j ; ++i, --j){  
	temp = L.data[i];
	L.data[i] = L.data[j];
	L.data[j] = temp;
}

---

单链表

存储方式

代码

定义

typedef struct LNode{  // 定义单链表结点 
	ElemType data;  // 数据域
	struct LNode *next;  // 指针域 
}LNode, *LinkList;

带表头单链表

• 空表——head->link == NULL

初始化

头插法

/*
逆向建立单链表
L：链表
返回L 
*/
LinkList List_HeadInsert(LinkList &L){
	LNode *node;  // 结点
	ElemType x;  // 每个结点的数据
	L = (LinkList)malloc(sizeof(LNode));  // 创建头结点
	L->next = NULL;  //初始为空链表
	scanf("%d", &x);  // 输入结点的值
	while(x != 9999){  // 输入9999表示结束 
		node = (LNode*)malloc(sizeof(LNode));  // 创建新结点
		node->data = x;  // x赋值 
		L->next = node;  // 头指针指向node结点
		scanf("%d", &x); 
	} 
	return L;
}

时间复杂度：$\text{O}(n)$

尾插法

/*尾插法
正向建立单链表
L：链表头结点 
返回L 
*/
LinkList List_TailInsert(LinkList &L){
	ElemType x;  // 插入元素
	LNode *node;  // 结点指针
	LNode *rear = L;  // r为尾指针；初始尾指针与头指针一起
	scanf("%d", &x);  // 输入结点值 
	while(x != 9999){  // 输入9999表示结束 
		 node = (LNode*)malloc(sizeof(LNode));  // 创建头结点
		 node->data = x;  // x赋值 
		 rear->next = node;  // 尾指针指向结点
		 rear = node;  // 该结点成为新的尾结点
		scanf("%d", &x); 
	} 
	rear->next = NULL;  // 尾结点置空
	return L; 
} 

时间复杂度：$\text{O}(n)$

查找

按序号查找

/*按序号查找结点 
L：链表头结点 
i：查询位置
返回：第i个元素的指针 
*/
LNode* GetElem(LinkList L, int i){
	int j = 1;  // 计数，初始为1
	LNode *node = L->next;  // 头结点指向结点
	if(i < 0)  // 若i无效，则返回NULL
		return NULL; 
	if(i==0)  // 若i==0，则返回头结点 
		return L;
	while(node && j<i){ // 从第一个结点开始，查找第i个结点
		node = node->next;  // 指向下一个结点
		j++;  // 计数+1 
	}
	return node;  // 找到后返回该指针，否则返回NULL 
} 

时间复杂度：$\text{O}(n)$

按值查找

/*按序值找结点 
L：链表头结点 
x：查询元素 
返回：元素结点指针 
*/
LNode* LocateElem(LinkList L, ElemType x){
	LNode *node = L->next;  // 结点为头结点所指向
	while(node != NULL  && node->data == x)  // 结点不为空且结点数据为x 
		node = node->next;  // 结点指向下一个 
	return node;  // 找到后返回该指针，否则返回NULL 
}

时间复杂度：$\text{O}(n)$

插入

按位置插入结点

p = GetElem(L, i-1);  // 插入位置的前驱结点
node->next = p->next;  // 待插入结点指向前驱结点所指向的后结点
p->next = node;  //前驱结点指向插入节点

时间复杂度：$\text{O}(n)$
已知结点后插：$\text{O}(1)$

某一结点前插

node->next = p->next;
p->next = node;  // 先执行后插

temp = p->data;
p->data = node->data;
node->data = temp;  // 交换node和p的数据值

时间复杂度：$\text{O}(1)$

删除

按位置删除结点

p = GetElem(L, i-1);  // 插入位置的前驱结点
node = p->next;  // node指向被删除结点
p->next = node->next;  // 前驱直接指向后结点
free(node);  // 释放结点存储空间

时间复杂度：$\text{O}(n)$

删除指定结点*p

node = p->next;  // node指向p后继
p->data = p->next->data;  // 交换数据域
p->next = node->next;  // node断开
free(node);  // 释放存储空间

时间复杂度：$\text{O}(1)$

求表长

时间复杂度：$\text{O}(n)$

逆置

p = L;  // p为头结点
q = rear;  // q为尾结点
do{
    temp = p->next;  // 临时指针取p后继结点
    p->next = temp->next;  // temp结点断开
    temp->next = q->next;  
    q->next = temp;  // temp结点移动q之后
}while(p->next == q)  // p q相遇停止

双向链表

存储方式

代码

定义

typedef struct DNode
{
    ElemType data; // 数据域
    struct DNode *prior; //左指针域
    struct DNode *next; //右指针域
}DNode,DLinkList;

插入

q->llink = p->llink; // q左指针指向p左指针指向的结点
q->rlink = p; // q右指针指向p结点
p->llink->rlink = q; // p左指针指向的结点(即p原左结点)右指针指向q结点
p->llink = q; // p左指针指向q

删除

p->llink->rlink = p->rlink; // p的左结点直接指向p的右结点
p->rlink->llink = p->llink; // p的右结点直接指向p的左结点
free(p); // 释放p

循环链表

存储方式

• p指针指向尾结点条件p->link = first
• 链表为空的条件first == NULL

静态链表

存储方式

用数组描述线性表的链式存储

下标

data

next的下标

结束标志：next==-1

代码

定义

typedef struct{  // 定义静态链表 
	ElemType data;  // 数据域 
	int next;  // 下一个元素的下标 
}SLinkList[MaxSize];

int p = index_0;  // 定义一个指针
SL[p].data;  // p指针数据域
SL.next;  // p指针指针域

线性表优劣比较

各线性结构比较

	顺序表	单链表	带表头的链表	循环链表	双向链表
优	查找速度$O(1)$	查找速度$O(n)$ 不需要估计存储长度	方便插入和删除操作的实现	从表中任意结点出发都能扫描整个链表	可快速访问直接前驱
劣	增删速度$O(n)$ 需要先估计存储空间	增删速度$O(1)$ 增删中头结点需要单独考虑

顺序表 & 链表

	顺序表	链表
存取方式	可顺序存储，也可随机存储	只能表头顺序存储
逻辑结构 & 物理结构	逻辑上相邻物理存储也相邻	逻辑上相邻物理上不一定相邻
CURD操作	按值查找： 无序：$O(n)$ 有序：$O(n\log n)$ 按序号查找：$O(1)$	查找：$O(n)$
空间分配	存储密度大 要预分配空间	存储密度小 只要又空间就可以分配，更灵活高效

选择存储结构

	顺序表	链表
基于存储的考虑		难以预测存储规模时，不宜采用顺序表
基于运算考虑	按序号访问元素较多	增删较多
基于环境考虑	实现较为简单