bachzart's Blog
0%

ZJU_DS_02-线性结构

Posted on Edited on In ,

什么是线性结构？如何表示和实现？有哪些线性结构？对应的有什么样性质？常见的应用有哪些？

Linear List

在介绍线性表之前，何老师先介绍了线性表的一个应用实例 —— 一元多项式及其运算。
而关于一元多项式的表示方法，老师介绍了三种方法：

  • 数组（顺序存储结构）直接表示，数组下标对应未知数 x 的指数，数组元素的值对应各项的系数，但对于某些特殊的多项式，此法会有较多的空间浪费。
  • 结构数组（顺序存储结构）表示非零项，将一个多项式看成是一个指数与系数的二元组的集合，多项式的每一项需按照指数大小有序存储。
  • 链表存储非零项，链表中每个结点存储多项式中的一个非零项，包括系数和指数两个数据域和一个指针域。

上述三种方法中，利用数组表示是易于实现的，但是不易设计与多项式相关的加减操作。而使用链表来表示十分灵活，且易于实现对应操作。从这可以看出，同一个问题可以有不同的表示（存储）方法；存在一类共性问题，即：有序线性序列的组织和管理。
由此可以引出线性表的概念：由同类型数据元素构成有序序列的线性结构，具备以下三个特点：

  1. 表中元素个数称为线性表的长度
  2. 线性表没有元素时，称为空表
  3. 表起始位置称表头，表结束位置称表尾

线性表的抽象数据类型描述

类型名称：线性表（List）
数据对象集：线性表是$n(≥0)$个元素构成的有序序列
操作集：线性表$L ∈ List$，整数$i$表示位置，元素$X ∈ ElementType$，主要操作：

  1. List MakeEmpty()，初始化一个空线性表
  2. ElementType FindKth(int K, List L)，根据位序K，返回相应元素
  3. int Find(ElementType X, List L)，在线性表L中查找X的第一次出现为止
  4. void Insert(ElementType X, int i, List L)，在位序i前插入一个新元素X
  5. void Delete(int i, List L)，删除指定位序i的元素
  6. int Length(List L)，返回线性表L的长度n

线性表的顺序存储实现

顺序表的顺序存储实现利用数组来连续存储空间顺序存放线性表的各元素，C 语言版本的定义（后文的代码都是 C 语言的）如下：

1
2
3
4
5
6
7
typedef int ElementType;
typedef int Position;	/*note here! */
typedef struct LNode* List;	/* struct LNode * = List */
struct LNode{
	ElementType Data[MAXSIZE];	/* #define MAXSIZE 100 */
	Position Last; /* the length of list */
};

初始化（建立空表）

按照上面的定义，我们可以写出建立空表的操作。

1
2
3
4
5
6
List MakeEmpty() {
	List L;
	L = (List)malloc(sizeof(struct LNode));
	L->Last = -1;	/*use -1 to represent that the list is blank */
	return L;
}

查找

前面一讲中，我们已经学会了二分查找，那么二分查找是否能在此处应用呢？要注意的是，二分查找的前提条件有两个： 顺序存储和数据有序。

这里我们采用按照顺序从前往后查找的方法来编写这个操作，需要将被查找的数据元素和所查找的线性表交给函数。当然，如果线性表是全局变量，那么可以不用传入线性表，这里假设线性表是在main函数中声明的。

1
2
3
4
5
6
7
8
Position Find(ElementType X, List L) {
	Position i = 0;
	while(i <= L->Last && L->Data[i] != X) {
		i++;
	}
	if(i > L->Last) return -1; /*can't find the element*/
	else return i;	/*return the index of this element*/
}

那么该如何计算查找成功的平均比较次数呢？假设有 n 个元素，如果第一个元素就是我们要查找的元素，那么此时查找成功的比较次数就是 1 次；继而可知当第二个元素就是我们要查找的元素时，查找成功的比较次数就是 2 次；从而我们可以知道对于 n 个元素的线性表查找成功的比较次数就是：$(1 + 2 + ... + n) / n = (1 + n) / 2$。这说明这种思路的查找算法的平均时间性能是$O(n)$。

插入

在直接上手写插入操作之前需要想一想插入操作的几种情况：表头、表中和表尾。针对这三种不同的情况，我们可以发现只有当在表尾插入的时候才不需要将元素移动；同时，在每一次插入操作时，由于线性表可能已经满了，那么插入操作就会失败了，这也是需要考虑的情况，接着，我们来写一下代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Insert(ElementType X, int i, List PtrL) {
	int j;
	if(PtrL->Last == MAXSIZE - 1) {
		printf("The list is full.\n");
		return;
	}
	if(i < 1 || i > PtrL->Last + 2) {
		printf("The position of the insertion is not valid.\n");
		return;
	}
	for(j = PtrL->Last; j >= i - 1; j--) {
		PtrL->Data[j + 1] = PtrL->Data[j];
	}
	PtrL->Data[i - 1] = X;
	PtrL->Last++;
}

从上述代码可以看出：

  1. 由于线性表的顺序存储结构借助了数组，所以当数组下标为$MAXSIZE - 1$时，表示线性表已满。
  2. 当插入位置 i 小于 1 或者大于PtrL->Last + 2时，插入位置就是不合法的。之所以大于PtrL->Last + 2不合法是因为，当PtrL->Last == MAXSIZE - 2时，PtrL->Last + 2 == MAXSIZE，那么 i 就大于了MAXSIZE，那就超出范围了。这里要区分好两个概念：插入位置和存储位置。插入位置是人为规定且从 1 开始的（符合人的思考习惯），而存储位置是从 0 开始的，因为数组下标是从 0 开始的。后面的移动操作也是基于这个前提来编写的。
  3. 所插入位置后的全部元素需要向后移动。

删除

有了插入操作的基础，删除操作就比较容易了，因为我们只需先找到要删除的元素，然后将此元素后的所有元素向前移动一个位置即可，但是要注意表为空的情况，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
void Delete(int P, List PtrL) {
	Position i;
	if(P < 1 || P > L->Last) {
		printf("The deleting position is illegal!\n");
		return false;
	}
	for(i = P + 1; i <= L->Last; i++) {
		L->Data[i - 1] = L->Data[i];
	}
	L->Last--;
	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
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
71
72
73
74
75
76
77
78
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXSIZE 10
#define ERROR -1
typedef int ElementType;
typedef int Position;
typedef struct LNode* List;
struct LNode{
	ElementType Data[MAXSIZE];
	Position Last; 
};
List MakeEmpty() {
	List L;
	L = (List)malloc(sizeof(struct LNode));
	L->Last = -1;
	return L;
}
Position Find(List L, ElementType X) {
	Position i = 0;
	while(i <= L->Last && L->Data[i] != X) {
		i++;
	}
	if(i > L->Last) return ERROR;
	else return i;
}
bool Insert(List L, ElementType X, Position P) {
	Position i;
	if(L->Last == MAXSIZE - 1) {
		printf("Sequence List is full!\n");
		return false;
	}
	if(P < 1 || P > L->Last + 2) {
		printf("The inserting position is illegal!\n");
		return false;
	}
	for(i = L->Last; i >= P - 1; i--) {
		L->Data[i + 1] = L->Data[i];
	}
	L->Data[P - 1] = X;
	L->Last++;
	return true;
}
bool Delete(List L, Position P) {
	Position i;
	if(P < 0 || P > L->Last) {
		printf("The deleting position is illegal!\n");
		return false;
	}
	for(i = P + 1; i <= L->Last; i++) {
		L->Data[i - 1] = L->Data[i];
	}
	L->Last--;
	return true;
}
void Print(List L) {
	if(L->Last == -1) printf("The Sequence List is empty!\n");
	else {
		int i = 0;
		while(i < L->Last) {
			printf("%d, ", L->Data[i]);
			i++; 
		} 
		printf("%d\n", L->Data[i]);
	}
}
int main() {
	List Sqlist = MakeEmpty();
	bool flag = Insert(Sqlist, 11, 0);
	printf("flag = %d\n", flag);
	Insert(Sqlist, 22, 1);
	Insert(Sqlist, 33, 2);
	Insert(Sqlist, 44, 3);
	Print(Sqlist);
	bool del_flag = Delete(Sqlist, 2);
	printf("del_flag = %d\n", del_flag);
	Print(Sqlist); 
}

线性表的链式存储实现

线性表的链式存储实现就是大家熟知的链表了，学过 C 语言的同学可能已经学会了如何构造、使用链表等。相比顺序表而言，链表的最突出的一个特点就是不再要求顺序存储了，也就是说，链表中的各个元素在内存中的位置是不一定相邻的。先看一下链表的定义：

1
2
3
4
5
6
7
8
9
#define ERROR NULL
typedef int ElementType;
typedef struct LNode* PtrToLNode;
struct LNode{
	ElementType Data;
	PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

这里使用不同的关键词来表示指向链表的指针，这样在后面的各种操作中可以区分各个指针的作用，让读代码的人更加易于从单词意思来理解代码。

初始化（建立空表）

链表建立空表的基本方法有头插法和尾插法，使用不同的方法建立链表可以得到不同的效果，可以方便我们解决问题，以下代码以带头结点的单链表为说明对象。

求表长

链表不同于顺序表，顺序表的表厂是限定的，但是链表的长度是无限的（假设内存无限），所以自然就会有求链表表长的问题产生。解决这个问题的最直观的思路也就是将链表遍历（从头结点访问到尾结点）一遍即可，代码如下：

1
2
3
4
5
6
7
8
9
int GetLength(List L) {
	List p = L->Next;	/*Let's say the linked list has head node. */
	int length = 0;
	while(p) {
		p = p->Next;
		length++;
	}
	return length;
}

查找

链表的查找有两种情况，分别是：按序号查找和按值查找。这两种查找方法思路比较简单，本质上都是对链表进行遍历。

按序号查找

1
2
3
4
5
6
7
8
9
10
List FindKth(int K, List PtrL) {
	List p = PtrL;
	int i = 1;
	while(p != NULL && i < K) {
		p = p->Next;
		i++;
	}
	if(i == K) return p;
	else return NULL;
}

按值查找

1
2
3
4
5
6
Position Find(ElementType X, List L) {
	Position p = L;
	while(p && p->Data != X) p = p->Next;
	if(p) return p;
	else return ERROR;
}

插入

往链表中插入一个结点，那么就需要先构造一个新的结点，然后再将这个新的结点插入到链表中。那么，如何进行插入呢？

假如要插入到第 i 个位置，那么就必须先要找到第 i - 1 个位置，然后再将这个新结点插入到第 i - 1 个结点的后面。另外，此处链式结构的指针应用一直是让初学者头疼的问题。但实际上，分析这类问题时，都有一个原则：必须要先让新结点指向后面的结点，才能再让前面的结点指向新结点。这点其实也不难理解，假如让前面的结点先指向新结点，那么后面的结点就丢失了，因为指向后面的结点的唯一指针（即前面结点的指针）已经指向了新结点。话说起来是很拗口且不那么直观，建议用笔在纸上画一画。

按照不同的查找方法，也可以给出不同的插入方法。

按序号插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool Insert_2(List L, ElementType X, int k) {
	List pre, tmp;
	if(k == 1) {
		tmp = (PtrToLNode)malloc(sizeof(struct LNode));
		tmp->Data = X;
		tmp->Next = L->Next;
		L->Next = tmp;
	}
	pre = FindKth(L, k);
	if(pre == NULL) {
		printf("The inserting position is illegal!\n");
		return false;
	} else {
		tmp = (PtrToLNode)malloc(sizeof(struct LNode));
		tmp->Data = X;
		tmp->Next = pre->Next;
		pre->Next = tmp;
		return true;
	}
}

按值插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool Insert_1(List L, ElementType X, Position P) {
	if(P == NULL) {
		printf("The inserting position is illegal!\n");
		return false;
	}
	Position tmp, pre;
	for(pre = L; pre && pre->Next != P; pre = pre->Next);
	if(pre == NULL) {
		printf("The inserting position is illegal!\n");
		return false;
	} else {
		tmp = CreateLNode(X);
		tmp->Next = P;
		pre->Next = tmp;
		return true;
	}
}

删除

由于我们已经明确了查找的方式，所以删除操作可以简化一些了，只要确保指向被删除元素的指针正确传给删除函数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool Delete(List L, Position P) {
	if(P == NULL) {
		printf("The deleting position is illegal!\n");
		return false;
	}
	Position tmp, pre;
	for(pre = L; pre && pre->Next != P; pre = pre->Next);
	if(pre == NULL) {
		printf("The deleting position is illegal!\n");
		return false;
	} else {
		pre->Next = P->Next;
		free(P);
		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
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ERROR NULL
#define MAXSIZE 10
typedef int ElementType;
typedef struct LNode* PtrToLNode;
struct LNode{
	ElementType Data;
	PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
Position Find(List L, ElementType X) {
	Position p = L;
	while(p && p->Data != X) p = p->Next;
	if(p) return p;
	else return ERROR;
}
Position FindKth(List L, int k) {
	PtrToLNode p = L;
	int i = 0;
	while(p && i < k) {
		i++;
		p = p->Next;
	}
	if(i == k) return p;
	else return NULL;
}
List MakeEmpty() {
	List L = (List)malloc(sizeof(struct LNode));
	L->Next = NULL;
	return L;
}
PtrToLNode CreateLNode(int value) {
	PtrToLNode t = (PtrToLNode)malloc(sizeof(struct LNode));
	t->Next = NULL;
	t->Data = value;
	return t;
}
bool Insert_1(List L, ElementType X, Position P) {
	if(P == NULL) {
		printf("The inserting position is illegal!\n");
		return false;
	}
	Position tmp, pre;
	for(pre = L; pre && pre->Next != P; pre = pre->Next);
	if(pre == NULL) {
		printf("The inserting position is illegal!\n");
		return false;
	} else {
		tmp = CreateLNode(X);
		tmp->Next = P;
		pre->Next = tmp;
		return true;
	}
}
bool Insert_2(List L, ElementType X, int k) {
	List pre, tmp;
	if(k == 1) {
		tmp = (PtrToLNode)malloc(sizeof(struct LNode));
		tmp->Data = X;
		tmp->Next = L->Next;
		L->Next = tmp;
	}
	pre = FindKth(L, k);
	if(pre == NULL) {
		printf("The inserting position is illegal!\n");
		return false;
	} else {
		tmp = (PtrToLNode)malloc(sizeof(struct LNode));
		tmp->Data = X;
		tmp->Next = pre->Next;
		pre->Next = tmp;
		return true;
	}
}
bool Delete(List L, Position P) {
	if(P == NULL) {
		printf("The deleting position is illegal!\n");
		return false;
	}
	Position tmp, pre;
	for(pre = L; pre && pre->Next != P; pre = pre->Next);
	if(pre == NULL) {
		printf("The deleting position is illegal!\n");
		return false;
	} else {
		pre->Next = P->Next;
		free(P);
		return true;
	}
}
void Print(List L) {
	if(L->Next == NULL) printf("The link list is empty!\n");
	else {
		L = L->Next;
		while(L->Next != NULL) {
			printf("%d, ", L->Data);
			L = L->Next;
		}
		printf("%d\n", L->Data);
	}
}
int main() {
	List L = MakeEmpty();
	PtrToLNode t = CreateLNode(11);
	L->Next = t;
	Print(L);
	int ins_flag = Insert_1(L, 22, Find(L, 11));
	printf("ins_flag = %d\n", ins_flag);
	Print(L);
	Insert_1(L, 33, Find(L, 22));
	Insert_1(L, 44, Find(L, 33));
	Print(L);
	int del_flag = Delete(L, Find(L, 33));
	printf("del_flag = %d\n", del_flag);
	Print(L);
	
	printf("/*--------------------*/\n");
	Insert_2(L, 55, 3);
	Print(L);
	Insert_2(L, 8, 2);
	Print(L);
	printf("%d\n", Insert_2(L, 9, 10));
	Print(L);
	return 0;
}

Generalized List

关于广义表的含义，何老师的 PPT 里面说的比较清楚了，即:

  1. 广义表是线性表的推广
  2. 对于广义表而言，n 个元素都是基本的单元素
  3. 广义表中，这些元素不仅可以是单元素也可以是另一个广义表

其实说白了，广义表是个大集合，囊括了线性表这个小集合。

关于多重链表，其实是广义表的一种应用，也即线性表中的每一个“结点”，又是一个线性表。多重链表多应用与于树（线索二叉树等）和图（十字链表等）这类复杂的数据结构，当然，树和图也可以不采用多重链表来存储。

Stack

堆栈（Stack），具有一定操作约束的线性表，只在一端（栈顶，Top）做插入、删除操作。
插入数据：入栈（Push）
删除数据：出栈（Pop）
后入先出：Last In First Out（LIFO）

堆栈的抽象数据类型描述

类型名称：堆栈（Stack）
数据对象集：一个有0个或多个元素的有穷线性表
操作集：长度为MaxSize的堆栈S ∈ Stack，堆栈元素item ∈ ElementType，主要操作：

  1. Stack CreateStack(int MaxSize)，生成空堆栈，其最大长度为MaxSize
  2. int IsFull(Stack S, int MaxSize)，判断堆栈S是否已满
  3. void Push(Stack S, ElementType item)，将元素item压入堆栈
  4. int IsEmpty(Stack S)，判断堆栈S是否为空
  5. ElementType Pop(Stack S)，删除并返回栈顶元素

栈的顺序存储实现

栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成，C 语言版本的定义如下：

1
2
3
4
5
6
7
8
9
10
#define MAXSIZE 10 /*store the maximum number of data*/
#define ERROR -1
typedef int ElementType;
typedef int Position;
typedef struct LNode* List;
struct LNode{
	ElementType Data[MAXSIZE];
	Position Last; 
};
typedef struct SNode *Stack;

初始化（建立空栈）

1
2
3
4
5
6
7
Stack Createstack(int MaxSize) {
	Stack S = (Stack)malloc(sizeof(struct SNode));
	S->Data = (ElementType*)malloc(MaxSize * sizeof(ElementType));
	S->Top = -1;
	S->MaxSize = MaxSize;
	return S; 
}

判断栈满

1
2
3
bool Isfull(Stack S) {
	return S->Top == S->MaxSize - 1;
}

判断栈空

1
2
3
bool Isempty(Stack S) {
	return S->Top == -1;
}

入栈

由于顺序栈是由数组存储，而数组有大小，当数组没有空间的时候就无法进行入栈操作，所以在入栈操作之前就必须要判断栈是否满了。

1
2
3
4
5
6
7
8
9
bool Push(Stack S, ElementType X) {
	if(Isfull(S)) {
		printf("The stack is full!\n");
		return false;
	} else {
		S->Data[++S->Top] = X;
		return true;
	}
}

出栈

与入栈操作类似，当栈为空时，显然无法进行出栈操作。

1
2
3
4
5
6
7
8
ElementType Pop(Stack S) {
	if(Isempty(S)) {
		printf("The stack is empty!\n");
		return false;
	} else {
		return S->Data[S->Top--];
	}
}

求栈内元素个数

1
2
3
int Getsize(Stack S) {
	return S->Top + 1;
}

测试代码

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
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int ElementType;
typedef int Position;
struct SNode{
	ElementType *Data;
	Position Top;
	int MaxSize;
};
typedef struct SNode *Stack;

Stack Createstack(int MaxSize) {
	Stack S = (Stack)malloc(sizeof(struct SNode));
	S->Data = (ElementType*)malloc(MaxSize * sizeof(ElementType));
	S->Top = -1;
	S->MaxSize = MaxSize;
	return S; 
}
bool Isfull(Stack S) {
	return S->Top == S->MaxSize - 1;
}
bool Push(Stack S, ElementType X) {
	if(Isfull(S)) {
		printf("The stack is full!\n");
		return false;
	} else {
		S->Data[++S->Top] = X;
		return true;
	}
}
bool Isempty(Stack S) {
	return S->Top == -1;
}
ElementType Pop(Stack S) {
	if(Isempty(S)) {
		printf("The stack is empty!\n");
		return false;
	} else {
		return S->Data[S->Top--];
	}
}
int Getsize(Stack S) {
	return S->Top + 1;
}
int main() {
	Stack S = Createstack(5);
	Pop(S);
	printf("S.size = %d\n", Getsize(S));
	int push_flag = Push(S, 11);
	Push(S, 22);
	Push(S, 33);
	int x = Pop(S);
	printf("push_flag = %d, x = %d\n", push_flag, x);
	printf("S.size = %d\n", Getsize(S));
	Push(S, 33);
	Push(S, 44);
	Push(S, 55);
	Push(S, 66);
	printf("S.size = %d\n", Getsize(S));
	return 0;
}

栈的链式存储结构实现

栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行，注意栈顶指针 top 只能在链表的表头。

1
2
3
4
5
6
7
typedef int ElementType;
typedef struct SNode* PtrToSNode;
struct SNode{
	ElementType Data;
	struct SNode *Next;
};
typedef PtrToSNode Stack;

初始化（建立空栈）

1
2
3
4
5
6
Stack Createstack() {
	Stack S;
	S = (Stack)malloc(sizeof(struct SNode));
	S->Next = NULL;
	return S;
}

入栈

由于链栈是通过申请内存构造结点的，所以理论上不存在栈满的情况（内存满了就不能分配空间了）。

1
2
3
4
5
6
7
bool Push(Stack S, ElementType X) {
	PtrToSNode tmpcell = (PtrToSNode)malloc(sizeof(struct SNode));
	tmpcell->Data = X;
	tmpcell->Next = S->Next;
	S->Next = tmpcell;
	return true;
}

判断栈空

尽管链栈不用判断栈满，但是在进行出栈操作时需要判断栈是否为空。

1
2
3
bool Isempty(Stack S) {
	return S->Next == NULL; 
}

出栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ElementType Pop(Stack S) {
	PtrToSNode firstcell;
	ElementType topelem;
	if(Isempty(S)) {
		printf("The stack is empty!\n");
		return false;
	} else {
		firstcell = S->Next;
		topelem = firstcell->Data;
		S->Next = firstcell->Next;
		free(firstcell);
		return topelem;
	}
}

求栈内元素个数

1
2
3
4
5
6
7
8
int Getsize(Stack S) {
	int size = 0;
	while(S->Next != NULL) {
		S = S->Next;
		size++;
	} 
	return size;
}

测试代码

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
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int ElementType;
typedef struct SNode* PtrToSNode;
struct SNode{
	ElementType Data;
	struct SNode *Next;
};
typedef PtrToSNode Stack;
Stack Createstack() {
	Stack S;
	S = (Stack)malloc(sizeof(struct SNode));
	S->Next = NULL;
	return S;
}
bool Isempty(Stack S) {
	return S->Next == NULL; 
}
bool Push(Stack S, ElementType X) {
	PtrToSNode tmpcell = (PtrToSNode)malloc(sizeof(struct SNode));
	tmpcell->Data = X;
	tmpcell->Next = S->Next;
	S->Next = tmpcell;
	return true;
}
ElementType Pop(Stack S) {
	PtrToSNode firstcell;
	ElementType topelem;
	if(Isempty(S)) {
		printf("The stack is empty!\n");
		return false;
	} else {
		firstcell = S->Next;
		topelem = firstcell->Data;
		S->Next = firstcell->Next;
		free(firstcell);
		return topelem;
	}
}
int Getsize(Stack S) {
	int size = 0;
	while(S->Next != NULL) {
		S = S->Next;
		size++;
	} 
	return size;
}
int main() {
	Stack S = Createstack();
	Pop(S);
	printf("S.size = %d\n", Getsize(S));
	Push(S, 11);
	Push(S, 22);
	Push(S, 33);
	printf("S.top = %d\n", Pop(S));
	Push(S, 33);
	Push(S, 44);
	Push(S, 55);
	printf("S.size = %d\n", Getsize(S)); 
	return 0;
}

Queue

队列也是具有一定操作约束的线性表（与堆栈类似），只能在一端插入，而在另一端删除。
数据插入：入队列（AddQ）
数据删除：出队列（DeleteQ）
先来先服务，先进先出，First In First Out，FIFO

队列的抽象数据类型描述

类型名称：队列（Queue）
数据对象集：一个有0个或多个元素的有穷线性表
操作集：长度为MaxSize的队列Q ∈ Queue，队列元素item ∈ ElementType，主要操作：

  1. Queue CreatQueue(int MaxSize)，生成长度为MaxSize的空队列
  2. int IsFullQ(Queue Q, int MaxSize)，判断队列Q是否已满
  3. void AddQ(Queue Q, ElementType item)，将数据元素item插入队列Q中
  4. int IsEmptyQ(Queue Q)，判断队列Q是否为空
  5. ElementType DeleteQ(Queue Q)，将对头数据元素从队列中删除并返回

队列的顺序存储实现

队列的顺序存储实现与顺序栈的实现方式相同，还是需要借助一个数组来存储元素。但与栈不同的是队列需要有队头（front）指针和队尾（rear）指针，定义如下：

1
2
3
4
5
6
7
8
typedef int ElementType;
typedef int Position;
struct QNode{
	ElementType *Data;
	Position Front, Rear;
	int MaxSize;
};
typedef struct QNode* Queue;

初始化（建立空队列）

1
2
3
4
5
6
7
Queue Createqueue(int MaxSize) {
	Queue Q = (Queue)malloc(sizeof(struct QNode));
	Q->Data = (ElementType*)malloc(sizeof(MaxSize * sizeof(ElementType)));
	Q->Front = Q->Rear = 0;
	Q->MaxSize = MaxSize;
	return Q;
}

判断队空

1
2
3
bool Isempty(Queue Q) {
	return Q->Front == Q->Rear;
}

判断队满

1
2
3
bool Isfull(Queue Q) {
	return (Q->Rear + 1) % Q->MaxSize == Q->Front;
}

入队

为了更好的利用数组，采取循环队列的设计方法，借助取余运算刚好可以满足要求，出队时同理。

1
2
3
4
5
6
7
8
9
10
bool Addq(Queue Q, ElementType X) {
	if(Isfull(Q)) {
		printf("The queue is full!\n");
		return false;
	} else {
		Q->Rear = (Q->Rear + 1) % Q->MaxSize;
		Q->Data[Q->Rear] = X;
		return true;
	}
}

出队

1
2
3
4
5
6
7
8
9
ElementType Deleteq(Queue Q) {
	if(Isempty(Q)) {
		printf("The queue is empty!\n");
		return false;
	} else {
		Q->Front = (Q->Front + 1) % Q->MaxSize;
		return Q->Data[Q->Front];
	}
}

求队列中元素个数

1
2
3
int Getsize(Queue Q) {
	return (Q->Rear + Q->MaxSize - Q->Front) % Q->MaxSize; 
}

测试代码

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
71
72
73
74
75
76
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int ElementType;
typedef int Position;
struct QNode{
	ElementType *Data;
	Position Front, Rear;
	int MaxSize;
};
typedef struct QNode* Queue;
Queue Createqueue(int MaxSize) {
	Queue Q = (Queue)malloc(sizeof(struct QNode));
	Q->Data = (ElementType*)malloc(sizeof(MaxSize * sizeof(ElementType)));
	Q->Front = Q->Rear = 0;
	Q->MaxSize = MaxSize;
	return Q;
}
bool Isfull(Queue Q) {
	return (Q->Rear + 1) % Q->MaxSize == Q->Front;
}
bool Addq(Queue Q, ElementType X) {
	if(Isfull(Q)) {
		printf("The queue is full!\n");
		return false;
	} else {
		Q->Rear = (Q->Rear + 1) % Q->MaxSize;
		Q->Data[Q->Rear] = X;
		return true;
	}
}
bool Isempty(Queue Q) {
	return Q->Front == Q->Rear;
}
ElementType Deleteq(Queue Q) {
	if(Isempty(Q)) {
		printf("The queue is empty!\n");
		return false;
	} else {
		Q->Front = (Q->Front + 1) % Q->MaxSize;
		return Q->Data[Q->Front];
	}
}
int Getsize(Queue Q) {
	return (Q->Rear + Q->MaxSize - Q->Front) % Q->MaxSize; 
}
void print(Queue q) {
	int i;
	for(i = 0; i < 5; i++) {
		printf("%d ", q->Data[i]);
	}
	putchar('\n');
}
int main() {
	Queue q = Createqueue(5);
	int x = Deleteq(q);
	printf("x = %d\n", x); 
	Addq(q, 11);
	printf("%d\n", Getsize(q)); 
	Addq(q, 22);
	x = Deleteq(q);
	printf("x = %d\n", x);
	Addq(q, 33);
	Addq(q, 44);
	Addq(q, 55);
	print(q);
	printf("q->front = %d, q->rear = %d\n", q->Front, q->Rear);
	printf("q.size = %d\n", Getsize(q));
	Addq(q, 66);
	x = Deleteq(q);
	x = Deleteq(q);
	Addq(q, 66);
	printf("q->front = %d, q->rear = %d\n", q->Front, q->Rear);
	printf("q.size = %d\n", Getsize(q));
	return 0;
}

队列的链式存储实现

队列的链式存储实现要比链栈的实现稍微复杂一点，需要有一个单独的队列结构（包含队头指针和队尾指针）来指向队列，定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
typedef int ElementType;
typedef struct Node* PtrToNode;
struct Node {
	ElementType Data;
	PtrToNode Next;
};
typedef PtrToNode Position;
struct QNode {
	Position Front, Rear;
	int MaxSize;
};
typedef struct QNode* Queue;

初始化（建立空队列）

1
2
3
4
5
6
Queue Createqueue(int MaxSize) {
	Queue q = (Queue)malloc(sizeof(struct QNode));
	q->Front = q->Rear = NULL;
	q->MaxSize = MaxSize;
	return q;
}

求队列中元素个数

1
2
3
4
5
6
7
8
9
int Getsize(Queue Q) {
	int count = 0;
	PtrToNode p = Q->Front;
	while(p) {
		count++;
		p = p->Next;
	}
	return count;
}

判断队空

1
2
3
bool Isempty(Queue Q) {
	return Q->Front == NULL;
}

判断队满

由于上述定义设置的有MaxSize，默认链队列是有最大空间的，所以需要判断队列是否为满。

1
2
3
4
bool Isfull(Queue Q) {
	if(Getsize(Q) >= Q->MaxSize) return true;
	else return false;
}

入队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool Addq(Queue Q, ElementType X) {
	if(Isfull(Q)) {
		printf("The queue is full!\n");
		return false;
	} else {
		PtrToNode t = (PtrToNode)malloc(sizeof(struct Node));
		t->Data = X;
		t->Next = NULL;
		if(Isempty(Q)) Q->Front = Q->Rear = t;
		else {
			Q->Rear->Next = t;
			Q->Rear = t;
		}
		return true;
	}
}

出队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ElementType Deleteq(Queue Q) {
	Position Frontcell;
	ElementType Frontelem;
	if(Isempty(Q)) {
		printf("The queue is empty!\n");
		return false;
	} else {
		Frontcell = Q->Front;
		if(Q->Front == Q->Rear) Q->Front = Q->Rear = NULL;
		else Q->Front = Q->Front->Next;
		Frontelem = Frontcell->Data;
		free(Frontcell);
		return Frontelem;
	}
}

测试代码

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int ElementType;
typedef struct Node* PtrToNode;
struct Node {
	ElementType Data;
	PtrToNode Next;
};
typedef PtrToNode Position;
struct QNode {
	Position Front, Rear;
	int MaxSize;
};
typedef struct QNode* Queue;
Queue Createqueue(int MaxSize) {
	Queue q = (Queue)malloc(sizeof(struct QNode));
	q->Front = q->Rear = NULL;
	q->MaxSize = MaxSize;
	return q;
}
bool Isempty(Queue Q) {
	return Q->Front == NULL;
}
ElementType Deleteq(Queue Q) {
	Position Frontcell;
	ElementType Frontelem;
	if(Isempty(Q)) {
		printf("The queue is empty!\n");
		return false;
	} else {
		Frontcell = Q->Front;
		if(Q->Front == Q->Rear) Q->Front = Q->Rear = NULL;
		else Q->Front = Q->Front->Next;
		Frontelem = Frontcell->Data;
		free(Frontcell);
		return Frontelem;
	}
}
int Getsize(Queue Q) {
	int count = 0;
	PtrToNode p = Q->Front;
	while(p) {
		count++;
		p = p->Next;
	}
	return count;
}
bool Isfull(Queue Q) {
	if(Getsize(Q) >= Q->MaxSize) return true;
	else return false;
}
bool Addq(Queue Q, ElementType X) {
	if(Isfull(Q)) {
		printf("The queue is full!\n");
		return false;
	} else {
		PtrToNode t = (PtrToNode)malloc(sizeof(struct Node));
		t->Data = X;
		t->Next = NULL;
		if(Isempty(Q)) Q->Front = Q->Rear = t;
		else {
			Q->Rear->Next = t;
			Q->Rear = t;
		}
		return true;
	}
}
int main() {
	Queue q = Createqueue(5);
	int x = Deleteq(q);
	Addq(q, 11);
	printf("q.size = %d\n", Getsize(q));
	x = Deleteq(q);
	printf("x = %d\n", x);
	Addq(q, 11);
	Addq(q, 22);
	Addq(q, 33);
	Addq(q, 44);
	Addq(q, 55);
	Addq(q, 66);
	printf("q.size = %d\n", Getsize(q));
	x = Deleteq(q);
	printf("x = %d, q.size = %d\n", x, Getsize(q));
	x = Deleteq(q);
	printf("x = %d, q.size = %d\n", x, Getsize(q));
	return 0;
}

Homework

02-1 两个有序链表序列的合并

此题考察链表的合并操作，注意链表有序且给定链表带头结点，要求合并后链表为非递减序列，所以需要对每一个结点值进行比较，代码如下（其中函数体为需要提交的代码）：

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
71
72
73
74
75
76
77
78
79
80
#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read();
void Print( List L );

List Merge( List L1, List L2 );

int main()
{
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    Print(L1);
    Print(L2);
    return 0;
}

List Read() {
	int i, n, temp;
	scanf("%d", &n);
	List L, p;
	L = (List)malloc(sizeof(struct Node));
	L->Next = NULL;
	p = L;
	for(i = 0; i < n; i++) {
		scanf("%d", &temp);
		PtrToNode t = (PtrToNode)malloc(sizeof(struct Node));
		t->Data = temp;
		t->Next = NULL;
		p->Next = t;
		p = t;
	}
	return L;
}

void Print( List L ) {
	PtrToNode p = L->Next;
	if(!p) {
		printf("NULL\n");
		return;
	}
	while(p->Next != NULL) {
		printf("%d ", p->Data);
		p = p->Next;
	}
	printf("%d\n", p->Data);
}

List Merge( List L1, List L2 ) {
	PtrToNode p, p1 = L1->Next, p2 = L2->Next;
	L1->Next = L2->Next = NULL;
	List L = (List)malloc(sizeof(struct Node));
	L->Next = NULL;
	p = L;
	while(p1 && p2) {
		if(p1->Data < p2->Data) {
			p->Next = p1;
			p = p1;
			p1 = p1->Next;
		} else {
			p->Next = p2;
			p = p2;
			p2 = p2->Next;
		}
	}
	if(p1) p->Next = p1;
	if(p2) p->Next = p2;
	return L;
}

02-2 一元多项式的乘法与加法运算

这道题的何老师已经讲过了，按照何老师给的思路，补全所有代码即可（最底下提供了几组测试用例）。

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#include <stdio.h>
#include <stdlib.h>
typedef struct PolyNode* Polynomial;
typedef struct PolyNode* PtrToPolyNode;
struct PolyNode {
	int coef, expon;
	struct PolyNode *link;
};
PtrToPolyNode CreateNode(int c, int e) {
	PtrToPolyNode t = (PtrToPolyNode)malloc(sizeof(struct PolyNode));
	t->coef = c, t->expon = e;
	t->link = NULL;
	return t;
}
Polynomial ReadPoly() {
	int n, c, e;
	scanf("%d", &n);
	Polynomial P, p;
	P = (Polynomial)malloc(sizeof(struct PolyNode));
	P->link = NULL;
	p = P;
	if(n == 0) {
		PtrToPolyNode t = CreateNode(0, 0);
		p->link = t;
	} else {
		while(n--) {
			scanf("%d %d", &c, &e);
			PtrToPolyNode t = CreateNode(c, e);
			p->link = t;
			p = t;
		}
	}
	return P;
}
void Print(Polynomial P) {
	if(P->link == NULL) {
		printf("0 0\n");
		return;
	} else {
		P = P->link;
		while(P->link != NULL) {
			printf("%d %d ", P->coef, P->expon);
			P = P->link;
		}
		printf("%d %d\n", P->coef, P->expon);
	}
}
Polynomial Add(Polynomial P1, Polynomial P2) {
	Polynomial P, p, p1 = P1->link, p2 = P2->link;
	P = (Polynomial)malloc(sizeof(struct PolyNode));
	P->link = NULL;
	p = P;
	while(p1 && p2) {
		if(p1->expon == p2->expon) {
			int e = p1->expon, c = p1->coef + p2->coef;
			if(c != 0) {
				PtrToPolyNode t = CreateNode(c, e);
				p->link = t;
				p = t;
			}
			p1 = p1->link;
			p2 = p2->link;
		} else if(p1->expon > p2->expon) {
			PtrToPolyNode t = CreateNode(p1->coef, p1->expon);
			p->link = t;
			p = t;
			p1 = p1->link;
		} else {
			PtrToPolyNode t = CreateNode(p2->coef, p2->expon);
			p->link = t;
			p = t;
			p2 = p2->link;
		}
	}
	while(p1 && p1->coef != 0) {
		PtrToPolyNode t = CreateNode(p1->coef, p1->expon);
		p->link = t;
		p = t;
		p1 = p1->link;
	}
	while(p2 && p1->coef != 0) {
		PtrToPolyNode t = CreateNode(p2->coef, p2->expon);
		p->link = t;
		p = t;
		p2 = p2->link;
	}
	return P;
}
Polynomial Multi(Polynomial P1, Polynomial P2) {
	Polynomial P, p, p1 = P1->link, p2;
	P = (Polynomial)malloc(sizeof(struct PolyNode));
	P->link = NULL;
	while(p1) {
		p2 = P2->link;
		while(p2) {
			int c = p1->coef * p2->coef;
			int e = p1->expon + p2->expon;
			p = P;
			while(p->link != NULL && p->link->expon > e) p = p->link;
			if(p->link != NULL) {
				if(p->link->expon == e) {
					int ctmp = p->link->coef + c;
					if(ctmp == 0) {
						PtrToPolyNode tmp = p->link;
						p->link = tmp->link;
						free(tmp);
					} else {
						p->link->coef = ctmp;
					}
				} else {
					if(c != 0) {
						PtrToPolyNode t = CreateNode(c, e);
						t->link = p->link;
						p->link = t;
					}
				}
			} else {
				if(c != 0) {
					PtrToPolyNode t = CreateNode(c, e);
					t->link = p->link;
					p->link = t;
				}
			}
			p2 = p2->link;
		}
		p1 = p1->link;
	}
	return P;
}
int main() {
	Polynomial P1, P2, PP, PS;
	P1 = ReadPoly();
	P2 = ReadPoly();
	PS = Add(P1, P2);
	PP = Multi(P1, P2);
	Print(PP);
	Print(PS);
	return 0;
}

/*
some samples:
in:
1 -1 1
1 1 1
out:
-1 2
0 0

in:
2 -1 1 2 0
1 1 1
out:
-1 2 2 1
2 0

in:
2 1 1 1 0
2 1 1 -1 0
out:
1 2 -1 0
2 1

in:
4 3 4 -5 2  6 1  -2 0
3 5 20  -7 4  3 1
out:
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0

in:
1 0 0
3 1 3 1 2 1 1
out:
0 0
1 3 1 2 1 1

in:
2 2 0 0 0
3 3 2 2 1 1 0
out:
6 2 4 1 2 0
3 2 2 1 3 0

in:
0
1 10 0
out:
0 0
10 0
*/

02-3 Reversing Linked List

此题题意比较直接，但是测试点比较多，要考虑全面。推荐使用静态链表的方法解题，这样耗时较少。

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <stdio.h>
#define maxn 100005
int addr[maxn], address[maxn], data[maxn], next[maxn];
void reverse(int A[], int left, int right) {
	for(; left < right; left++, right--) {
		int temp = A[left];
		A[left] = A[right];
		A[right] = temp;
	}
}
int main() {
	int src, n, k, m;
	scanf("%d %d %d", &src, &n, &k);
	m = n;
	int tmp_add, tmp_data, tmp_next;
	while(m--) {
		scanf("%d %d %d", &tmp_add, &tmp_data, &tmp_next);
		address[tmp_add] = tmp_add;
		next[tmp_add] = tmp_next;
		data[tmp_add] = tmp_data;
	}
	int len = 1, i, j, tmp = src;
	addr[0] = src;
	while(src != -1) {
		addr[len++] = next[src];
		src = next[src];
	}
	for(i = 0, j = k; j <= len - 1; i = j, j += k) {
		reverse(addr, i, j - 1);
	}
	for(i = 0; i < len - 2; i++) {
		src = addr[i];
		printf("%05d %d %05d\n", src, data[src], addr[i + 1]);
	}
	printf("%05d %d -1\n", address[addr[i]], data[addr[i]]);
	return 0;
}

/*
some samples:
in:
00100 6 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
out:
68237 6 99999
99999 5 00000
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 -1

in:
00100 6 3
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
out:
33218 3 12309
12309 2 00100
00100 1 68237
68237 6 99999
99999 5 00000
00000 4 -1

in:
00100 6 1
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
out:
00100 1 12309
12309 2 33218
33218 3 00000
00000 4 99999
99999 5 68237
68237 6 -1

in:
00100 5 3
00000 4 99999
00100 1 12309
33218 3 00000
99999 5 -1
12309 2 33218
out:
33218 3 12309
12309 2 00100
00100 1 00000
00000 4 99999
99999 5 -1

in:
00100 9 2
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
33333 7 22222
44444 8 11111
03333 9 02222
out:
12309 2 00100
00100 1 00000
00000 4 33218
33218 3 68237
68237 6 99999
99999 5 -1

in:
00100 3 2
00100 1 -1
11111 2 22222
33333 3 44444
out:
00100 1 -1
*/

02-4 Pop Sequence

本题考察栈的相关知识，本质上是模拟栈的相关操作，推荐使用 C++ 自带的 STL 模板里面的 Stack ，可以直接拿来使用，但需要先了解一下用法。

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
#include <iostream>
#include <stack>
using namespace std;
const int maxn = 1000 + 10;
int seq[maxn];
int main() {
	int m, n, k;
	cin >> m >> n >> k;
	bool flag = true;
	while(k--) {
		stack<int> st;
		for(int i = 1; i <= n; i++) {
			cin >> seq[i];
		}
		bool flag = true;
		int i = 1, j = 1;
		while(j <= n + 1) {
			if(st.size() > m) {
				flag = false;
				break;
			}
			if(!st.empty()) {
				if(st.top() == seq[i]) {
					st.pop();
					i++;
				} else st.push(j++);
			} else st.push(j++);
		}
		if(flag && st.size() == 1) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
} 
/*
some samples:
in:
5 7 1
5 6 4 3 7 2 1
out:
YES

some sample:
in:
2 4 4
1 2 3 4
2 1 3 4
1 2 4 3
3 1 2 4
out:
YES
YES
YES
NO
*/