数据结构合集

这篇文章主要记录各种数据结构的基本操作以及一些相关题目。

队列

队尾插入,队头删除。

基本操作

顺序队列

队列的类型定义:

1
2
3
4
5
#define MAXLEN 1000
struct SeqQueue{
int front, rear;
int data[MAXLEN];
};

队列的初始化:

1
2
3
void init(SeqQueue &q){
q.front = q.rear = 0;
}

判断队列是否为空:

1
2
3
bool isEmpty(SeqQueue q){
return q.front == q.rear;
}

判断是否队满:

1
2
3
bool isFull(SeqQueue q){
return q.rear == MAXLEN;
}

入队操作:

1
2
3
4
5
bool Push(SeqQueue &q, int t){
if(isFull(q)) return false;
q.data[q.rear++] = t;
return true;
}

出队操作:

1
2
3
4
5
bool Pop(SeqQueue &q, int &dt){
if(isEmpty(q)) return false;
dt = q.data[q.front++];
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
#define MAXLEN 100
struct CycleQueue{
int data[MAXLEN];
int front, rear;
};
void init(CycleQueue &q){
q.front = q.rear = 0;
}
bool isEmpty(CycleQueue q){
return q.rear == q.front;
}
bool isFull(CycleQueue &q){
return (q.rear + 1) % MAXLEN == q.front;
}
bool Push(CycleQueue &q, int t){
if(isFull(q)) return false;
q.data[q.rear++] = t;
return true;
}
bool Pop(CycleQueue &q, int &dt){
if(isEmpty(q)) return false;
dt = q.data[q.front];
q.front = (q.front + 1) % MAXLEN;
return true;
}

HDU1276

方法一:(没用队列)

注意:这里是说不超过3,也就是可以小于3,所以不是只剩下3个时就停止报数,而是把那一趟报完,剩下几个就输出几个。

典型的如:输入4,输出1 3

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
using namespace std;

int n;
int d[5005];

void init(){
for(int i = 1; i <= n; i++)
d[i] = i;
}

int main(){
int N;
while(cin >> N){
while(N--){
cin >> n;
init();
int c = 0, cnt = n;
while(cnt > 3){
if(!c){
int f = 0;
for(int i = 1; i <= n; i++){
if(d[i]){
if(f){
d[i] = 0;
cnt--;
}
f ^= 1;
}
}
c ^= 1;
}
else{
int f = 2;
for(int i = 1; i <= n; i++){
if(d[i]){
if(f){
f--;
}
else{
d[i] = 0;
cnt--;
f = 2;
}
}
}
c ^= 1;
}
}
int j = 0;
for(int i = 1; i <= n; i++){
if(d[i]){
j = i;
cout << d[i];
break;
}
}
if(j){
for(int i = j + 1; i <= n; i++){
if(d[i]){
cout << " " << d[i];
}
}
}
cout << endl;
}
}
return 0;
}

方法二:(队列)

利用两个队列来模拟整个报数方式,一个队列存放初始士兵,另一个存放一次报数后剩下的士兵,两个队列循环,直到最后队列中人数小于4人时,停止报数。

1

顺序栈的基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define MAXLEN 100
struct Stack{
int data[MAXLEN];
int top;
};
bool isEmpty(Stack s){
return s.top == 0;
}
bool isFull(Stack s){
return s.top == MAXLEN; //栈顶指针s.top指向的是栈顶元素位置的上一个
}
bool Push(Stack &s, int t){
if(isFull(s)) return false;
s.data[s.top++] = t;
return true;
}
bool Pop(Stack &s, int &dt){ //或者干脆写个GetTop(int &dt)
if(isEmpty(s)) return false;
dt = s.data[s.top--];
return true;
}

栈的应用

表达式求值

数制转换

数据结构复习 查找

查找表是由同一类型的数据元素(或记录)组成的集合。

查找表的分类:

1.静态查找表:仅作查询和检索操作的查找表

2.动态查找表:在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除某个已存在的数据元素

关键字:是数据元素(或记录)中某个数据项的值,用以标识(识别)一个数据元素(或记录)。若此关键字可以识别唯一的一个记录,则称之为“主关键字”。若此关键字能识别若干记录,则称之为“次关键字”。

查找:根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素或记录。

若查找表中存在这样的一个记录,则”查找成功“,查找结果:给出整个记录的信息,或指示该记录在查找表中的位置。否则”查找不成功“,查找结果:给出“空记录”或“空指针”。

查找的方法取决于查找表的结构。由于查找表的数据元素之间不存在明显的组织规律,因此不便于查找。为了提高查找的效率,需要在查找表的元素之间人为地附加某种确定的关系。也就是说,用另外一种结构来表示查找表。

查找方法评价:查找速度、占用存储空间多少、算法本身复杂程度、平均查找长度ASL(Average Search Length,为确定记录在表中的位置,需和给定值进行比较的关键字的个数的期望值)

img

img

静态查找表:

1.顺序表的查找:

查找过程:从表的一端开始,逐个进行记录的关键字与给定值的比较。

例如,有n个数,则构造一个长度为n+1的数组arr,其中arr[0]为监视哨,存放要查找的元素,剩下的1~n位存放n个数。从arr[n]开始向arr[1]查找,则比较次数:

若查找第n个元素,则比较1次(第一次就找到);

若查找第n-1个元素,则比较2次(第一次比较之后,又比较了一次);

若查找第i个元素,则比较(n+1-i)次;

查找失败:比较了n+1次。

1
2
3
4
5
6
7
int Search_Seq(int &a[], int key){
a[0] = key;
for(int i = n; i >= 1; --i)
if(a[i] == key)
return i;
return 0;
}

对于顺序表,等概率情况下:=img

若不等概率,或查找概率无法事先确定,则采取的改进方法是:在每次查找之后,将刚刚查找过的记录移至表尾位置上。

2.有序表的查找:

顺序表的查找算法简单,但是ASL较大,不适用于表长较大的查找表。

若以有序表表示静态查找表,则查找过程可以“折半”进行。

折半查找:

查找过程:每次将待查记录所在区间减小一半。

适用条件:采用顺序存储结构的有序表。

折半查找算法的实现:

img

若k == mid,查找成功;

若k < mid,high = mid - 1;

若k > mid,low = mid + 1;

重复上述操作,直至条件low <= high不再满足为止。

1
2
3
4
5
6
7
8
9
10
int Search_Bin(int &a[], int k){
int low = 1, high = n;
while(low <= high){
int mid = (low + high) / 2;
if(k == a[mid]) return mid;
else if(k > a[mid]) low = mid + 1;
else high = mid - 1;
}
return 0;
}

性能分析:

判定树:描述查找过程的二叉树。

img

img

img

img

img

由此可见,

  • 折半查找效率比顺序查找高。
  • 折半查找只适用于有序表,并且以顺序存储结构存储。

顺序表和有序表的比较:

顺序表 有序表
表的特性 无序 有序
存储结构 顺序 或 链式 顺序
插删操作 易于进行 需要移动元素
ASL

3.索引顺序表(=索引+顺序表)

在建立顺序表的同时,建立一个索引项,包括:关键字项和指针项。索引表按关键字有序,表则为分块有序。

顺序表:

15 95 42 37 65 16

索引表:

95 0 65 3 85 6

(索引表中包含:第一块:0-2,最大关键字是95,起始是0;…)

索引顺序查找,又称分块查找。

查找过程:将表分为几块,块内无序,块间有序;先确定待查记录所在块,再在块内查找。

适用条件:分块有序表

算法实现:用数组存放待查记录,每个数据元素至少含有关键字域;建立索引表,每个索引表结点含有最大关键字域和指向本块第一个结点的指针。

img

img

查找方法比较:

顺序 折半 分块
ASL 两者之间
表结构 无序 或 有序 有序 分块有序表
存储结构 顺序 或 链式 顺序 顺序 或 链式

从查找性能来看,最好情况能达到O(logn),此时要求表有序;

从插入和删除的性能来看,最好情况能达到O(1),此时要求存储结构是链表。

动态查找表:

特点:表结构本身是在查找过程中动态生成。若表中存在其关键字等于给定值的记录,则查找成功,否则插入关键字等于key的记录。

高度为h的AVL树的最少节点数

设高度为h的AVL树最少的节点数为f(h)
可以算出f(0)=0,f(1)=1,f(2)=2.
设左子树的高度为h-1,则右子树的高度为h-2.
因此得到递推公式:f(h) = f(h-1) + f(h-2) + 1.

Hash