数据结构重点知识复习

数据结构

数据对象在计算机中的组织方式
逻辑结构（线性结构，树结构，图结构）
物理结构
数据对象必定与一系列加在其上的操作相关联
完成这些操作所用的方法就是算法

抽象数据类型（Abstract Data Type）

数据类型

数据对象集
数据集合相关联的操作集

抽象：描述数据类型的方法不依赖于具体实现

与存放的机器无关
与数据存储的物理结构无关
与实现操作的算法和编程语言无关

算法（Algorithm）

一个有限指令集
接受一些输入（或没有输入）
产生输出
在有限步骤之后终止
每一条指令必须

有充分明确的目标，不可有歧义
在计算机能处理的范围之内
描述应不依赖于任何一种计算机语言以及其具体的实现手段

什么是好算法？

空间复杂度S(n)——占用存储单元的长度
时间复杂度T(n)——耗费时间的长度

一般考虑最坏情况复杂度Tworst(n)和平均复杂度Tavg(n)，Ω(g(n)) <= T(n) <= O(f(n))

复杂度排序：常数<logn<n<nlogn<n2<n3<2n<n!

例子：给定N个整数的序列{A1, A2, …, AN}，求函数f(i, j) = max{0, ∑_(k=i)^j▒A_k }的最大值

T(n) = O(N3)

int MaxSubseqSum1(int A[], int N){

int ThisSum, MaxSum = 0;
int i, j, k;
for(i = 0; i < N; i++){
    for(j = i; j < N; j++){
        ThisSum = 0;
        for(k = i; k <= j; k++) ThisSum += A[k];
        if(ThisSum > MaxSum) MaxSum = ThisSum;
    }
}
return MaxSum;

}

T(n) = O(N2)

int MaxSubseqSum2(int A[], int N){

int ThisSum, MaxSum = 0;
int i, j;
for(i = 0; i < N; i++){
    ThisSum = 0;
    for(j = i; j < N; j++){
        ThisSum += A[j];
        if(ThisSum > MaxSum) MaxSum = ThisSum;
    }
}
return MaxSum;

}

T(n) = O(NlogN)

分而治之，算左边的最大、右边最大和跨左右最大。
这时候T(N) = 2T(N/2) + cN，其中T(1) = O(1)，将N/2代入：
T(N) = 2[2T(N/22) + cN/2] + cN

=2kO(1) + ckN

其中N/2k = 1
所以复杂度主导因子为ckN，即O(NlogN)

T(n) = O(N)，在线处理

int MaxSubseqSum4(int A[], int N){

int ThisSum, MaxSum = 0;
int i, j;
for(i = 0; i < N; i++){
    ThisSum += A[i];
    if(ThisSum > MaxSum) MaxSum = ThisSum;
    else if(ThisSum < 0) ThisSum = 0;
}
return MaxSum;

}

线性结构
一元多项式及其运算
F(x) = a0 + a1X + … + an-1Xn-1 + anXn 运算考虑加减乘

顺序存储结构直接表示

a[i]：项Xi的系数为ai
如f(x) = 4X5 – 3X2 + 1， 表示成{1, 0, -3, 0, 0, 4}

顺序存储结构表示非零项

f(x) = 9x12 + 15X8 + 3X2，表示成{{9, 12}, {15, 8}, {3, 2}}

链表结构存储非零项

coef expon link
typedef struct PolyNode *Polynomial;
struct PolyNode{

int coef;
int expon;
Polynomial link;

}

线性表(Linear List)：
由同类数据元素构成有序序列的线性结构

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

线性表的抽象数据类型描述：
类型名称：线性表
数据对象集：是n(n>=0)个元素构成的有序序列(a1, a2, …, an)
操作集：线性表L∈List，整数i表示位置，元素X∈ElementType

List MakeEmpty()
ElementType FindKth(int K, List L)
int Find(ElementType X, List L)
void Insert(ElementType X, int i, List L)
void Delete(int i, List L)
int Length(List L)
以数组方式实现：

typedef struct LNode *List;
struct LNode{

ElementType Data[MAXSIZE];
int Last

};
struct LNode L;
List PtrL;
访问下标为i的元素：L.Data[i]或PtrL -> Data[i]
线性表长度：L.Last + 1或PtrL -> Last + 1

初始化

List MakeEmpty(){

List PtrL;
PtrL = (List)malloc(sizeof(struct LNode));
PtrL->Last = -1;
return PtrL;

}

查找

int Find(ElementType X, List PtrL){

int i = 0;
while(i <= PtrL->Last && PtrL->Data[i] != X) i++;
if(i > PtrL->Last) return -1;
else return i;

}

插入

void Insert(ElementType X, int i, List PtrL){

int j;
if(PtrL->Last == MAXSIZE - 1){
    printf("表满");
    return;
}
if(i < 1 || i > PtrL->Last + 2){
    printf("位置不合法");
    return;
}
for(j = PtrL->Last; j >= i-1; j--) PtrL->Data[j+1] = PtrL->Data[j];
PtrL->Data[i-1] = X;
PtrL->Last++;
return;

}

删除

void Delete(int i, List PtrL){

int j;
if(i < 1 || i > PtrL->Last + 1){
    printf("不存在第%d个元素", i);
    return;
}
for(j = 1; j <= PtrL->Last; j++) PtrL->Data[j-1] = PtrL->Data[j];
PtrL->Last--;
return;

}

以链表方式实现：

typedef struct LNode *List;
struct LNode{

ElementType Data;
List Next;

};
struct LNode L;
List PtrL;

求表长

int Length(List PtrL){

List p = PtrL;
int j = 0;
while(p){
    p = p->Next;
    j++;
}
return j;

}

查找

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;

}
List Find(ElementType X, List PtrL){

List p = PtrL;
while(p != NULL && p->Data != X) p = p->Next;
return p;

}

插入

List Insert(ElementType X, int i, List PtrL){

List p, s;
if(i == 1){
    s = (List)malloc(sizeof(struct LNode));
    s->Data = X;
    s->Next = PtrL;
    return s;
}
p = FindKth(i - 1, PtrL);
if(p == NULL){
    printf("参数i错");
    return NULL;
} else{
    s = (List)malloc(sizeof(struct LNode));
    s->Data = X;
    s->Next = p->Next;
    p->Next = s;
    return PtrL;
}

}

删除

List Delete(int i, List PtrL){

List p, s;
if(i == 1){
    s = PtrL;
    if(PtrL != NULL) PtrL = PtrL->Next;
    else return NULL;
    free(s);
    return PtrL;
}
p = FindKth(i - 1, PtrL);
if(p == NULL){
    printf("第%d个结点不存在", i-1);
    return NULL;
}else if(p->Next == NULL){
    printf("第%d个结点不存在", i);
    return NULL;
}else{
    s = p->Next;
    p->Next = s->Next;
    free(s);
    return PtrL;
}

}

广义表：
二元多项式P(x, y) = 9x12y2 + 4x12 + 15x8y3 – x8y + 3x2
看成关于x的一元多项式：
P(x, y) = (9y2 + 4)x12 + (15y3 - y)x8 + 3x2
通过复杂链表表示
广义表（Generalized List）

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

typedef struct GNode *GList;
struct GNode{

int Tag; /*标志域，0表示节点是单元素，1表示节点是广义表*/
union{  /*子表指针域SubList与单元素数据域Data复用，即公用存储空间*/
    ElementType Data;
    GList SubList;
}URegion;
GList Next;

};
Tag Data Next

SubList

多重链表：链表中的节点可能同时隶属于多个链

多重链表中节点的指针域会有多个，如前面例子包含了Next和SubList两个指针域；
但包含两个指针域的链表并不一定是多重链表，比如双向链表不是多重链表

多重链表有广泛的用途，基本上如树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储。
矩阵可以用二维数组表示，但有两个缺陷，一是数组的大小需要事先确定，二是对于稀疏矩阵将造成大量的存储空间浪费。
可以采用一种典型的多重链表——十字链表来存储稀疏矩阵：

只存储矩阵非0元素项

节点的数据域：行坐标Row、列坐标Col、数值Value

每个节点通过两个指针域，把同行、同列串起来；

行指针Right
列指针Down

4行5列7个元素

用一个标识域Tag来区分头节点和非0元素节点；
头节点的标识值为“Head”，矩阵非0元素节点的标识值为“Term”。

Tag
Down URegion Right

节点的总体结构

Term
Down Row Col Right

Value    
矩阵非0元素节点

Head
Down Next Right

头节点

堆栈
计算机是如何进行表达式计算的？
首先将中缀表达式（a+bc-d/e）转换为后缀表达式（abc+de/-）
如62/3-42+=6/2-3+42=8：从左向右扫描，遇到运算数就记住，遇到运算符号就将最近记住的两个数进行计算，就需要先进后出，即堆栈。
定义：Stack，具有一定操作约束的线性表，只在一端（栈顶，Top）做入栈（Push）和出栈（Pop），遵循后入先出（Last In First Out，LIFO）
抽象数据类型描述
类型名称：堆栈
数据对象集：一个有0个或多个元素的有穷线性表。
操作集：长度为MaxSize的堆栈S∈Stack，堆栈元素item∈ElementType

生成空堆栈，最大长度为MaxSize
判断堆栈S是否已满
将元素item压入堆栈
判断堆栈S是否为空
删除并返回栈顶元素

栈的顺序存储实现
typedef ElementType;
typedef struct SNode *Stack;
struct SNode{

ElementType Data[MaxSize];
int Top;

}
入栈Push
void Push(Stack PtrS, ElementType item){

if(PtrS->Top == MaxSize-1){
    printf("fullstack");
    return;
} else{
    PtrS->Data[++(PtrS->Top)] = item;
    return;
}

}
出栈Pop
ElementType Pop(Stack PtrS){

if(PtrS->Top == -1){
    printf("emptystack");
    return ERROR;
} else{
    return PtrS->Data[PtrS->Top--];
}

}

栈的链式存储实现
typedef struct SNode *Stack;
struct SNode{

ElementType Data;
struct SNode *Next;

};
初始化
Stack CreateStack(){

Stack S;
S = (Stack)malloc(sizeof(struct SNode));
S->Next = NULL;
return S;

}
判空
int IsEmpty(Stack S){

return S->Next == NULL;

}
入栈
void Push(Stack S, ElementType item){

struct SNode *TempCell;
TempCell = (Stack)malloc(sizeof(struct SNode));
TempCell->Data = item;
TempCell->Next = S->Next;
S->Next = TempCell;

}
出栈
ElementType Pop(Stack S){

struct SNode *FirstCell;
ElementType TopElem;
if(IsEmpty(S)){
    printf("emptystack");
    return NULL;
}else{
    FirstCell = S->Next;
    S->Next = FirstCell->Next;
    TopElem = FirstCell->Data;
    free(FirstCell);
    return TopElem;
}

}

堆栈应用：表达式求值
中缀表达式转换为后缀表达式再求值

运算数相对顺序不变
运算符号顺序发生改变

需要存储“等待中”的运算符号
要将当前运算符号与“等待中”的最后一个运算符号比较
例子：a(b+c)/d=abc+d/
流程：从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理。

运算数：直接输出；
左括号：压入堆栈；
右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）；
运算符：
若优先级大于栈顶运算符时，则把它压栈；
若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈；
若各对象处理完毕，则把堆栈中存留的运算符一并输出。

例子：(2*(9+6/3-5)+4)
步骤 待处理表达式 堆栈状态
（底顶） 输出状态
1 2*(9+6/3-5)+4
2 *(9+6/3-5)+4 2
3 (9+6/3-5)+4 * 2
4 9+6/3-5)+4 *( 2
5 +6/3-5)+4 *( 29
6 6/3-5)+4 *(+ 29
7 /3-5)+4 *(+ 296
8 3-5)+4 *(+/ 296
9 -5)+4 *(+/ 2963
10 5)+4 *(- 2963/+
11 )+4 *(- 2963/+5
12 +4 * 2963/+5-
13 4 + 2963/+5-*
14 + 2963/+5-*4
15 2963/+5-*4+
堆栈其他应用：
函数调用及递归实现
深度优先搜索
回溯算法…

队列
遵循先入先出（First In First Out，FIFO）
队列的抽象数据类型描述
类型名称：队列
数据操作集：一个有0个或多个元素的有穷线性表。
操作集：长度为MaxSize的队列Q∈Queue，队列元素item∈ElementType

生成长度为MaxSize的空队列
判断队列Q是否已满
将数据元素item插入队列Q中
判断队列Q是否为空
将队头数据元素从队列中删除并返回

队列的顺序存储实现
typedef ElementType;
struct QNode{

ElementType Data[MaxSize];
int rear;
int front;

};
typedef struct QNode *Queue;
入队列
void AddQ(Queue PtrQ, ElementType item){

if((PtrQ->rear+1)%MaxSize == PtrQ->front){
    printf("fullqueue");
    return;
}
PtrQ->rear = (PtrQ->rear+1)%MaxSize;
PtrQ->Data[PtrQ->rear] = item;

}
出队列
ElementType DeleteQ(Queue PtrQ){

if(PtrQ->front == PtrQ->rear){
    printf("emptyqueue");
    return NULL;
}else{
    PtrQ->front = (PtrQ->front+1)%MaxSize;
    return PtrQ->Data[PtrQ->front];
}

}

队列的链式存储实现
typedef ElementType;
struct Node{

ElementType Data;
struct Node *Next;

};
struct QNode{

struct Node *rear;
struct Node *front;

};
typedef struct QNode *Queue;
Queue PtrQ;
出队
ElementType DeleteQ(Queue PtrQ){

struct Node *FrontCell;
ElementType FrontElem;

if(PtrQ->front == NULL){
    printf("emptyqueue");
    return ERROR;
}
FrontCell = PtrQ->front;
if(PtrQ->front == PtrQ->rear)
    PtrQ->front = PtrQ->rear = NULL;
else
    PtrQ->front = PtrQ->front->Next;
FrontElem = FrontCell->Data;
free(FrontCell);
return FrontElem;

}

应用实例：多项式加法运算