数据结构详细笔记——线性表

---

线性表的三要素

逻辑结构（定义）

线性表是具有相同数据类型的n（n>=0）个数据元素的有限 序列，其中n为表长，当n=0时线性表是一个空表。

若用L命名线性表，则一般表示为 L= (a1,a2,…,ai,ai+1,…an)

总结一下：线性表的逻辑结构只需要掌握以下几点：
1、数据元素同类型、有限、有序
2、表长为0则是一个空表
3、数据元素的位序（从1开始），数组的位序（从0开始）

数据的运算（基本操作）

InitList(&L)
初始化表：构造一个空的线性表L，分配内存空间

DestroyList(&L)
销毁操作：销毁线性表，并释放线性表L所占用的内存空间

ListInsert(&L,i,e)
插入操作：在表L中的第i个位置上插入指定元素e

ListDelete(&L,i,&e)
删除操作：删除表L中的第i个位置的元素，并用e返回删除元素的值

LocateElem(L,e)
按值查找：在表L中查找具有给定关键字值的元素

GetElem(L,i)
按位查找：获取表L中第i个位置的元素的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

存储结构（物理结构）

顺序表（顺序存储）

顺序表的定义

顺序表——用顺序存储的方式实现线性表，把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中

顺序表的实现——静态分配

#define MaxSize 10
typedef stuct{
	int data[MaxSize];
	int length;
}SqList;
1
2
3
4
5

初始化静态分配顺序表

void InitList(SqList &L){
	for(int i=0; i < MaxSize; i++){
		L.data[i] = 0;
	}
	L.length = 0;
}
1
2
3
4
5
6

顺序表的实现——动态分配

#define InitSize 10
typedef struct{
	int *data;
	int MaxSize;
	int length;
}SeqList;
1
2
3
4
5
6

初始化动态分配顺序表

void InitList(SeqList &L){
	L.data = (int *) malloc(InitSize * (sizeof(int));
	L.Maxzise = InitSize;
	L.length = 0;
}
1
2
3
4
5

增加动态数组的长度

void IncreseSize(SeqList &L, int len){
	int *p = L.data;
	L.data = (int *) malloc((L.Maxsize + len) * sizeof(int));
	for(int i = 0; i< L.length; i++){
		L.data[i] = p[i];    // 将数据复制到新的区域
	}
	L.Maxsize = L.Maxsize + len;
    free(p);
 }
1
2
3
4
5
6
7
8
9

顺序表的特点

1、随机访问，即可以在O(1)时间内找到第i个元素。
2、存储密度高，每个节点只存储数据元素。
3、拓展容量不方便（即便采用动态分配方式实现，拓展长度的时间复杂度也比较高）。
4、插入、删除操作不方便，需要移动大量的元素。

顺序表的基本操作

插入操作—— 时间复杂度 O(n)

#define MaxSize 10
typedef struct{
	int data[MaxSize];
	int length;
}SqList;

void InitList(SqList &L){
	for(int i = 0; i < MaxSize; i++){
		L.data[i] = 0;
	}
	L.length = 0;
}

bool ListInsert(SqList &L, int i, int e){
	if(i < 1 || i > L.length+1 )   // 判断i是否有效
		return false;
	if(L.length >= MaxSize)        // 当前存储空间已满，不能插入
		return false;
	for(int j = L.length; j>=i; j--){  // 将第i个元素及之后的元素后移
		L.data[j] = L.data[j-1];
	}
	L.data[i-1] = e;    // 在位置i处放入e
	L.length ++;        // 长度加1
	return true;
}

int main(){
	SqList L;
	InitList(L);
	ListInsert(L,3,9);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

删除操作 —— 时间复杂度 O(n)

bool ListDelete(SqList &L, int i, &e){
	if(i < 1 || i > L.length)
		return false;
	e = L.data[i-1];
	for(int j = i; j < L.length; j++){
		L.data[j-1] = L.data[j];
	}
	L.length --;
	return true;
}
int main(){
	SqList L;
	InitList(L);
	...
	int e = -1;
	ListDelete(L,3,e);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

按位查找 —— 时间复杂度 O(1)

int GetElem(SqList L, int i){
	return L.data[i-1];
}
1
2
3

按值查找 —— 时间复杂度 O(n)

int LocateElem(SqList L, int e){
	for(let i = 0; i < L.length; i++){
		if(L.data[i] == e){
			return i+1;   // 返回的是位序，需要加一
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8

链表（链式存储）

单链表

单链表的定义

typedef struct LNode{
	ElmeType data;          // 每个节点存放一个数据元素
	struct LNode *next;     // 指针指向下一个节点
}LNode, *LinkList;
1
2
3
4

不带头结点的单链表

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;

// 初始化一个空的单链表
bool initList(LinkList &L){
	L = NULL;  // 空表，暂时还没有任何结点
	return true;
}

// 判断单链表是否为空
bool Empty(LinkList L){
	return (L == NULL)
}

void mian(){
	LinkList L;
	InitList(L);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

带头结点的单链表

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

bool InitList(LinkList &L){
	L = (LNode *) malloc(sizeof(LNode));  // 分配一个头结点
	if(L == NULL)      // 内存不足，分配失败
		return false;
	L->next = NULL;     // 头结点之后暂时还没有结点
	return true;
}

// 判断单链表是否为空
bool Empty(LinkList L){
	return (L->next == NULL)
}

void mian(){
	LinkList L;
	InitList(L);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

值得注意的点是：
LinkList 等价于 LNode *
LinkList 强调的是链表
LNode * 强调的是结点

单链表的基本操作

按位序插入（带头结点） —— 时间复杂度 O(n)

bool ListInsert(LinkList &L, int i, int e){
	if(i < 1)
		return false;
	LNode *p;  // 指针p指向当前扫描到的结点
	int j = 0;  // 当前p指向的是第几个结点
	p = L; // L指向头结点
	while(p != NULL && j < i-1){
		p = p->next;
		j++;
	}
	if(p == NUll)
		return false;
	LNode *s = (LNode *) malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

按位序插入（不带头结点） —— 时间复杂度 O(n)

bool ListInsert(LinkList &L, int i, int e){
	if(i < 1)
		return false;
	if(i == 1){
		LNode *s = (LNode *) malloc(sizeof(LNode));
		s->data = e;
		s->next=> L;
		s = L;
		return true;
	}
	LNode *p;  // 指针p指向当前扫描到的结点
	int j = 0;  // 当前p指向的是第几个结点
	p = L; // L指向头结点
	while(p != NULL && j < i-1){
		p = p->next;
		j++;
	}
	if(p == NUll)
		return false;
	LNode *s = (LNode *) malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

以上代码都有一段重复逻辑：在指定结点的后插操作，因此可以将重复逻辑封装起来
指定结点的后插操作 —— 时间复杂度 O(1)

bool InsertNextNode(LNode *p, int e){
	if(p == NUll)
		return false;
	LNode *s = (LNode *) malloc(sizeof(LNode));
	if(s == NULL)
	    return false;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11

指定结点的前插操作—— 时间复杂度 O(1)

bool InsertNextNode(LNode *p, int e){
	if(p == NUll)
		return false;
	LNode *s = (LNode *) malloc(sizeof(LNode));
	if(s == NULL)
	    return false;
	s->next = p->next；
	p->next = s;
	s->data = p->data;  // 同样是后插操作，改变数据的位置，完美实现前插操作
	p->data = e;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12

按位序删除（带头结点） —— 时间复杂度 O(n)

bool ListInsert(LinkList &L, int i, int e){
	if(i < 1)
		return false;
	LNode *p;  // 指针p指向当前扫描到的结点
	int j = 0;  // 当前p指向的是第几个结点
	p = L; // L指向头结点
	while(p != NULL && j < i-1){
		p = p->next;
		j++;
	}
	if(p == NUll)
		return false;
	if(p->next == NULL)
		return false; 
	LNode *q = p->next;  // 令q指向被删除结点
	e = q->data;
	p->next = q->next;
	free(q); 
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

按位序查找（带头结点） —— 时间复杂度 O(n)

LNode * GetElem(LinkList L, int i){
	if(i < 0)
		return false;
	LNode *p;
	int j = 0;
	p = L;
	while(p != NULL && j < i){
		p = p->next;
		j++;
	}
	return p;
}
1
2
3
4
5
6
7
8
9
10
11
12

按值查找（带头结点） —— 时间复杂度 O(n)

LNode * LocateElem(LinkList L, int e){
	LNode *p = L->next; // 从第一个结点开始寻找
	while(p != NULL && p->data != e){
		p = p->next;
	}
	return p;
}
1
2
3
4
5
6
7

尾插法建立单链表

LinkList List_TailInsert(LinkList &L){
	int x;
	L = (LNode *) malloc(sizeof(LNode));  // 建立头结点
	LNode *s,*r=L;  // r为表尾指针
	scanf("%d",&x);
	while(x!=9999){  // 表示结束
		s = (LNode *) malloc(sizeof(LNode));
		s=>data = x;
		r->next = s;
		r = s;    // r指向新的表尾结点
		scanf("%d",&x);
	}
	r->next = NULL;
	return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

头插法建立单链表

LinkList List_HeadInsert(LinkList &L){
    LNode *s;
	int x;
	L = (LNode *) malloc(sizeof(LNode));  // 建立头结点
	L->next = NULL;
	scanf("%d",&x);
	while(x!=9999){  // 表示结束
		s = (LNode *) malloc(sizeof(LNode));
		s=>data = x;
		s->next = L->next;
		L->next = s;
		scanf("%d",&x);
	}
	return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

双链表

双链表的定义

typedef struct DNode{
	int data;
	struct DNode *prior,*next;
}DNode,*DLinkList;
1
2
3
4

双链表的初始化（带头结点）

bool InitDLinkList(DLinkList &L){
	L = (DNode *) malloc(sizeof(DNode));
	if(L == NULL)
		return false;
	L->prior = NULL;   // 头结点的 prior 永远指向null
	L->next = NULL;
	return true;
}
1
2
3
4
5
6
7
8

双链表的插入

// 在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
	if(p == NULL || s == NULL)
		return false;
	s->next = p->next;
	if(p->next != NULL)
		p->next->prior = s;
	s->prior = p;
	p->next = s;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11

双链表的删除

// 删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
	if(p = NULL)
		return false;
	DNode *q = p->next;
	if(q == NULL)
		return false;
	p->next = q->next;
	if(q->next != NULL)
		q->next->prior = p;
	free(q);
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

双链表的销毁

void DestroyList(DLinkList &L){
	while(L->next != NULL){
		DeleteNextDNode(L);
	}
	free(L);
	L = NULL;
}
1
2
3
4
5
6
7

双链表的遍历 —— 时间复杂度 O(n)

// 后向遍历
while(p != NULL)
	p = p->next;

//前向遍历
while(p != NULL)
	p = p->prior;
	
//前向遍历(跳过头结点)
while(p->prior != NULL)
	p = p->prior;
1
2
3
4
5
6
7
8
9
10
11

循环链表

循环单链表

初始化循环单链表

typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

bool InitList(LinkList &L){
	L = (LNode *) malloc(sizeof(LNode));
	if(L == NULL)
		retun false;
	L->next = L;   // 头结点的next指向头结点
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12

判断循环单链表是否为空

bool Empty(LinkList L){
	if(L->next == L)
		return true;
	else
		return false;
}
1
2
3
4
5
6

判断结点p是否为循环单链表的表尾结点

bool isTail(LinkList L, LNode *p){
	if(p->next == L)
		return true;
	else
		return false;
}
1
2
3
4
5
6

循环双链表

初始化循环单链表

typedef struct DNode{
	int data;
	struct DNode *prior,*next;
}DNode,*DLinkList;

bool InitDLinkList(DLinkList &L){
	L = (DNode *) malloc(sizeof(DNode));
	if(L == NULL)
		return false;
	L->prior = L; 
	L->next = L;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

判断循环双链表是否为空

bool Empty(DLinkList L){
	if(L->next == L)
		return true;
	else
		return false;
}
1
2
3
4
5
6

判断结点p是否为循环双链表的表尾结点

bool isTail(DLinkList L, LNode *p){
	if(p->next == L)
		return true;
	else
		return false;
}
1
2
3
4
5
6

判断结点p是否为循环双链表的表尾结点

bool isTail(DLinkList L, LNode *p){
	if(p->next == L)
		return true;
	else
		return false;
}
1
2
3
4
5
6

双链表的插入

// 在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
	s->next = p->next;
	p->next->prior = s;
	s->prior = p;
	p->next = s;
}
1
2
3
4
5
6
7

静态链表

静态链表：分配一整片连续的内存空间，各个结点集中安置

定义静态链表

#define MaxSize 10
typedef struct{
	ElemType data;   // 存储数据元素
	int next;        // 下一个元素的数组下标
}SLinkList[MaxSize];
1
2
3
4
5

优点：增、删操作不需要大量移动元素
缺点：不能随机存取，只能从头结点开始依次往后查找，容量固定不变

顺序表与链表的区别

1、逻辑结构
都是属于线性表，都是线性结构

2、存储结构

顺序表：
优点：支持随机存取，存储密度高
缺点：大片连续空间分配不方便，改变容量不方便

链式表
优点：离散的小的空间分配方便，改变容量方便
缺点：不可以随机存取，存储密度低

用顺序表 or 链表？
表长难以预估、经常要增加、删除元素————链表
表长可预估，查询（搜索）操作比较多————顺序表