数据结构与算法 --1. 线性表

發表於 更新於 分類於

存储结构：顺序，链接，索引，哈希

一、顺序表

线性表的寻顺序存储又称为顺序表

1. 随机存储

相同数据类型，所以可以用公式 LOC (A) + (i-1) xsize (ElemType)

2. 类型描述

1
2
3
4
5
6
7
8
9
#define InitSize 100
typedef struct
{
	ElemType *data;
	int MaxSize, length;
} SeqList;

SeqList L;
L.data = new ElemType [InitSize];

3. 操作与实现

删除，插入，按值查找

4. 例题

若长度为 n 的非空线性表釆用顺序存储结构，在表的第 i 个位置插入一个数据元素，i 的合法值应该是？
A. 1<=i<=n B. 1<=i<=n+l C. 0<=i<=n-1 D. 0<=i<=n
答案：B 表元素序号从 1 开始，而在第 n+1 个位置插入相当于在表尾追加

求两个升序序列 A 和 B 的合并序列 C：
分别用游标 i 和 j 指向序列 A 和 B 的序列头，
依次比较 A [i] 和 B [j]，比较小的就放入序列 C

方法 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int search_median (int A [], int B [], int n)
{
	int i=0, j=0, cnt=0;
	while (true)
	{
		cnt++;
		if (cnt == n)
		{
			return A [i]<B [j]?A [i]:B [j];
		}

		if (A [i] < B [j]) i++;
		else j++;
	}
}

方法 2：分治

1

二、单链表

1. 实现

线性表的链式存储又称为单链表

1
2
3
4
5
6
typedef struct LNode
{
	ElemType data;
	struct LNode* next;
} LNode, *LinkList;
// 指向节点的指针就是链表

2. 操作

(1) 建立表
1
2
3
4
5
6
7
(a) 采用头插法建立单链表（插入 S）
s->next = L->next;
L->next = s;
(b) 采用头插法建立单链表（插入 S）
 需要有一个尾指针 r
r->next = s;
r = s;
(2) 按序号查找节点值（遍历 + 计数器）
1
2
3
4
5
6
7
int cnt = 0, LNode* p = NULL;
for (p = L->next; p != NULL; p = p->next)
{
	cnt++;
	if (cnt == i)
		return p;
}
(3) 按值查找表节点
1
2
3
4
5
6
7
LNode* p = NULL;
for (p=L->next; p!=NULL; p=p->next)
{
	if (p->data == e)
		return p;
}
return NULL;
(4) 插入节点

先检查插入位置的合法性，找到待插入位置的前驱节点 p，再在其后插入新节点（i 前插）

1
2
3
4
5
s->next = p->next;
p->next = s;
//p->next 一定是在最后一步修改
i 前插 = (i-1) 后插 = i 后插，交换 i 和 i+1 的 data
(在有了指向 i 节点的指针，且是单链表的情况下，可以用这个技巧降低时间复杂度)

(5) 删除节点

先检查删除位置 q 的合法性，找到待删除位置的前驱节点

1
2
p->next = q->next;
free (q);// 没有释放会导致内存泄漏

(6) 求表长（遍历 + 计数器）

int cnt=0, LNode* p;
for (p=L->next; p!=NULL; p=p->next)
{
cnt++;
}
return cnt;

三、双链表

ex：单链表的插入算法，要先找到欲插入位置的前驱，就要花费 O (n) 的时间

1. 实现

1
2
3
4
5
typedef struct DNode
{
	ElemType data;
	struct DNode *prior, *next;
} DNode, *DLinklist;

2. 操作

(1) 插入节点
1
2
3
4
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
(2) 删除节点

删除双链表中节点 p 和后继节点 q

1
2
3
p->next = q->next;
q->next->prior = p;
free (q);

四、循环链表（分为循环单链表和循环双链表）

1. 循环单链表

L 是头指针，r 是尾指针
r->next = L->next;
判空条件：L->next == L;

2. 循环双链表

判空条件：L->next==L && L->prior==L;

五、静态链表

移动 -> 使用链表
查找 -> 使用顺序表
移动又查找 -> 使用静态链表
既有前向操作又有后向操作 -> 选择双向链表

数据结构与算法系列

数据结构与算法 —1. 线性表
数据结构与算法 —2. 树
数据结构与算法 —3. 图
数据结构与算法 —4. 查找
数据结构与算法 —5. 排序