数据结构

发表于 更新于 分类于 阅读次数：
本文为西电计科院数据结构科目的复习小结，内容来自于课本、PPT、习题。仅在默认掌握所有内容的情况下记录一些重要的、“应对西电考试特有的”的知识点。

1.线性表

暂略

2.栈与队列

2.1 顺序栈

后进先出结构（LIFO）

2.1.1 栈定义：

动态：

1
2
3
4
5
typedef struct Node{
	SElemType *base;
	SElemType *top;
	int stacksize; //已分配的空间大小(字节)
}SqStack;

栈结构不存在：

S.base = NULL;

空栈：

S.base = S.top;

栈满：

S.top - S.base >= S.stacksize;

静态：

1
2
3
4
typedef struct Node{
	SElemType data[MAXSIZE]; //逻辑大小
	int top;
}SqStack;

空栈：

top = -1;

栈满：
top = MAXSIZE - 1;

注意：top指向栈顶元素的下一个位置，而不是栈顶。所以后续操作中对top都是先用后加。

2.1.2基本运算：

  • InitStack(&S) 初始化，创建一个空栈
  • Push(&S, e) 插入e为新的栈顶元素
  • Pop(&S, &e) 删除栈顶元素，返回e
  • GetTop(S, &e) 用e返回栈顶元素
  • StackEmpty(S) 判断是否存在

（详见代码复习文档）

2.2 链栈

指针指向： 从 n -> 1，栈底元素是 a1；无头节点，头指针就是栈顶指针，栈空 S = NULL

2.2.1 链栈定义

1
2
3
4
typedef struct STNode{
	SElemType data;
	struct STNode *next;
} STNode, *LinkStack;

链栈的优势：不会出现栈满的情况

2.3 链队列

先进先出结构（FIFO）

2.3.1 类型定义

1
2
3
4
5
6
7
8
9
typedef struct QNode{
	QElemType data;
	struct QNode *next;
} QNode, *QueuePtr;

typedef struct Queue{
	QueuePtr front; //队头指针
	QueuePtr rear; //队尾指针                            
} LinkQueue;

对于非空队列，rear指针始终指向队尾的下一位置。

2.3.2 基本运算

  • InitQueue(&Q) 初始化，设置一个空队列
  • EnQueue(&Q, e) 插入e
  • DeQueue(&Q, &e) 删除队头
  • GetHead(Q, &e) 读取队头
  • QueueEmpty(S) 判空

（详见代码复习文档）

2.3.3 循环队列

  • 尾指针增1：Q.rear = (Q.rear + 1) % SIZE;
  • 头指针增1：Q.front = (Q.front + 1) % SIZE;
  • 队列空：Q.raer = Q.front;
  • 队列满：(Q.rear + 1) % SIZE = Q.front;
  • 元素个数：(Q.rear - Q.front + SIZE) % SIZE;

3. 串

空串是任意串的子串，任意串是其自身的子串。

对于字符串的考察应该只局限在概念层面，顶多也就求个next值完事了。

3.1 串的存储

3.1.1 顺序存储

1
2
3
4
5
6
7
8
9
typedef struct{
	char ch[LEN];
	int length;
} Sqstring;

typedef struct{
	char *ch;
	int length;
} Hstring;

3.2 基本运算

  • StrAssign(&S, chars) 串赋值
  • StrCompare(S, T) 串比较
  • StrLength(S) 求串长
  • Concat(&T, S1, S2) 串连接：将S1和S2连接到新串T上
  • SubString(&Sub, S, pos, len) 求子串（起始位置 + 长度）
  • StrCopy(&T, S) 串复制
  • Index(S, T, pos) 子串定位

3.3 KMP

学校教的next数组的值为：

对于next[j]，它的值等于前 j-1 位数字真前缀的值 - 1

逆天！

4. 数组与广义表

4.1 数组

$Loc(a_{ij}) = Loc(a_{11}) + [(j-1)*(m或n) + i - 1] * d$ ，d为字节数

乘m或n取决于行优先还是列优先

4.2 矩阵

特殊矩阵的压缩存储：

（公式）

稀疏矩阵的压缩存储：

存储的是一个三元组(i,j,v)，表示行，列，值

存储顺序是先行优先再列优先

转置的两种方式：第一种是直接swap(i,j)后再按行优先列优先sort；第二种是计算行列元素个数提前预判元素的位置，省去排序的过程

4.3 广义表