数据结构

前言

初习数据结构，有出错的地方请各位同仁斧正，并希望可以一起探讨交流。本人会持续更新该本教材的精讲和理解，并在不解的地方发起讨论，希望各位大佬能加以解答

一、绪论

1.数据（data）是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
2.数据元素（data element）是数据的基本单位。
3.一个数据元素可由若干个数据项组成，数据项是数据的不可分割的最小单位。
4.数据对象（data object）是性质相同的数据元素的集合，是数据的一个子集。
5.数据结构（data structure）是相互之间存在一种或多种特定关系的数据元素的集合。

思维导图：

6.存储结构是对数据元素内容和个数的体现。
存储实现是对数据元素位置的体现。
运算实现是对数据元素形式上的体现。
7.数据类型（data type）是一个值的集合和定义在这个值集合上的一组操作的总称。
8.抽象数据类型是应用问题的数学模型及定义在此模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和数据对象的基本操作的集合。
9.算法是对特定问题求解步骤的一种描述，是指令的有限序列
10. 存储密度： 结点数据本身所占存储量/整个结点结构所占的存储量
顺序表=1；单链<1（数据所占存储量+指针域所占空间）。
11.区分逻辑结构（数据元素间关系）和存储结构（存放数据元素的物理结构）
一种逻辑结构可用多种物理结构来实现。
物理结构影响逻辑结构上的各种操作的复杂度。
逻辑结构描述的是关系，与数据元素本身特点及计算机参数无关
12.算法5特性：有穷性、确定性、可行性、输入和输出性。
13.4个算法评价准则：正确性、可读性、健壮性、高效性。
14.复杂度（时间）、（空间）
时间复杂度：给定输入规模n，在最坏情况下需要多少时间一定能做完。
空间复杂度：给定输入规模n，在最坏情况下需要多少额外空间一定能做完。

大O表示法三规则O(数量级)

1.运行时间中所有的加减法常数用常数1代替。
2.只保留最高阶项。
3.去除最高项常数。

基础练习

一个算法理应接受的合法输入范围是[0，1000]，通过实验发现其在输入为0或1000时陷入死循环，
输入为其他合法值时能正常工作，说明该算法的_____有待提高.
A.效率 B.可行性 C.健壮性 D.有穷性

C
该算法的输入范围为[0，1000]，因此0和1000是该算法输入的边界情况，说明该算法在处理边界情况的时候不够仔细，导致出错，术语上称这种情况为不够健壮或不够鲁棒(robust).

顺序存储结构和链式存储结构在内存中都占用一块连续的区域（X）。

二、线性表（n个数据元素的有限序列）一对一的关系

线性表（逻辑结构）的顺序存储和链式存储（存储结构的物理结构）

顺序存储（按顺序在一起，相邻元素通过内存地址相邻产生联系）“随机读取元素”（清楚知晓每个元素的地址）时间复杂度O（1），不易插入元素

数组意味着所有数据在内存中都是相连的（紧靠在一起的）。
这便意味着我们想要插入数据就要在计算机中重新开空间，将原数据转移进去，这便造成了时间上的浪费。
或者为了不重开空间，往往会将原定计划的计算机内存空间额外请求扩大位置，若是额外请求的位置可能根本用不上，这将浪费内存，空间浪费。

链式存储（元素随机放置，每个元素保存相邻元素怒的内存地址来实现线性关系）“顺序读取”O（n），易插入元素

链表的每个元素都存储了下一个元素的地址。
所以链表不能直接访问最后一个数据，需要先访问第一个元素获取第二个元素位置，再不断往下访问递推，因此同时读取所有元素时，链表的效率很高，但如果你需要跳跃，链表的效率真的很低。

查找定位元素 （按值查找）O（n）

1.抽象数据类型线性表的定义

ADT List{
数据对象：D={ai|∈ElemSet，i=1,2,...,n,n>=0}
数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}
基本操作：
IntList(&L)
操作结果:构造一个空的线性表L。
DestroyList(&L)
初始条件：线性表L已存在。
操作结果：销毁线性表L。
ClearList(&L)
初始条件：线性表L已存在。
操作结果：将L重置为空表。
ListEmpty(L)
初始条件：线性表L已存在。
操作结果：若L为空表，则返回TRUE，否则返回FALSE。
ListLength(L)
初始条件：线性表L已存在。
操作结果：返回L中数据元素的个数。
GetElem（L，i，&e）
初始条件：线性表L已存在，1<=i<=ListLength(L)
操作结果：用e返回L中第i个数据元素的值。
LocateElem(L,e,compare())
初始条件：线性表L已存在，compare()是数据元素判定函数。
操作结果:返回L中第1个与e满足关系compare（）的数据元素的位序。若这样的数据元素不存在，则返回0。
PriorElem(L，cure_e,&pre_e)
初始条件：线性表L已存在。
操作结果：若cur_e是L的数据元素，且不是最后一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
NextElem(L，cur_e,&next_e)
初始条件：线性表L已存在。
若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的前驱，否则操作失败，next_e无定义
ListInsert(&L,i,e)
初始条件：线性表L已存在，1<=i<=LinstLength(L)+1。
操作结果：在L中第i个位置**之前**插入新的数据元素e，L的长度加1。
ListDelete(&L,i,&e)
初始条件：线性表L已存在且非空，1<=i<=ListLength(L)。
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。
ListTRaveerse(L,visit())
初始条件：线性表L已存在。
操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。
}ADT List

2.链表分类

1.线性链表

一组任意的存储单元存储线性表的数据元素数据域该数据元素存储其本身信息外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）指针域。

2.循环链表

表中最后一个结点的指针指向头结点，整个链表形成一个环。

3.双向链表

有两个指针域，分别指向直接前驱和直接后驱。

3.代码实现（线性表的插入和删除，合并）

1.插入（数组）

在第i（1<=i<=n）个元素之前插入一个元素时，需将第n至第i个（共n-i+1）个元素向后移动一个位置。

Status ListInsert_Sq(SqList &L,int i,ElemType e){
//在顺序线性表L中第i个位置之前插入新的元素e，
//i的合法值为1<=i<=ListLength_Sq(L)+1
if(i<1||i>L.length+1) return ERROR;//i值不合法
if(L.length>=L.listsize){ //当前存储空间已满，增加分配
  newbase=(ElemType*)realloc(L.elem,L.listsize+LISTINCREMENT)*sizeof(ElemType));
  if(!newbase)exit(OVERFLOW);//存储分配失败
  L.elem=newbase;//新基址
  L.listsize +=LISTINCREMENT;//增加存储容量
  }
  q=&(L.elem[i-1]);//q为插入位置
  for（p=&（L.elem[L.length-1]））;p>=q;--p)*(p+1)=*p;
  //插入位置及之后的元素右移
  *q=e;//插入e
  ++L.length;//表长增1
  return OK；
  }//ListInsert_Sq

2.删除（数组）

删除第i（1<=i<=n）个元素时需将从第i+1至第n个（共n-i）个元素依次向前移动一个位置。

Status ListDelete_Sq(SqList &L,int i,ElemType &e){
//在顺序线性表L中删除第i个元素，并用e值返回其值
i的合法值为1<=i<=ListLength_Sq(L)
if(i<1||i>L.length) return ERROR;//i值不合法
p=&(L.elem+L.length-1);//p为被删除元素的位置
e=*p;//将被删除元素的值赋给e
q=L.elem+L.length-1;//表尾元素的位置
for(++p;p<=q;++p)*(p-1)=*p//被删除元素之后的元素左移
--L.length;//表长减1
return OK;
}//ListDelete_Sq

3.顺序表的合并（数组）时间复杂度O(La.length+Lb.length)只合并不同元素，空间复杂度O（n）开辟额外空间存放

void MergeList_Sq(SqList La,SqList Lb,SqList &Lc){
//已知顺序线性表La和Lb的元素按值非递减排列
//归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列
pa=La.elem; pb=Lb.elem;
Lc.listsize=Lc.length=La.length+Lb.length;
pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));
if(!Lc.elem)exeit(OVERFLOW);//存储分配失败   //此三行生成C数组
pa_last=La.elem+La.length-1;
pb_last=Lb.elem+Lb.length-1;
while(pa<=pa_last&&pb<=pb_last){  //归并
if(*pa<=*pb)*pc++=*pa++;
else *pc++=*pb++;
}
while(pa<=pa_last)*pc++=*pa++;   //插入La的剩余元素
while(pb<=pb_last)*pc++=*pb++;   //插入Lb的剩余元素
}  //MergeList_Sq

4. 插入（单链表法）O（n）需先访问前驱结点，无需移动元素位置

Status ListInsert_L(LinkList &L,int i,ElemType e){
//在带头结点的单链线性表L中第i个位置之前插入元素e，
p=L; j=0;
while(p&& j<i-1){
p=p->next;++j;} //寻找第i-1个结点
if(!p||j>i-1) retturn ERROR; //i小于1或者大于表长加1
s=(LinkList)malloc(sizeof(LNode)); //生成新结点
s->data=e;s->next=p->next; //插入L中
p->next=s;
return OK;
} //ListInsert_L
  

图像文字解析如下：

data指的是数据，node指结点，指向下一个数据的地址。
关于s->data=e;s->next=p->next; p->next=s;
本题中S是新构建的结点，s->data=e 意思为构建连接1，使得s结点指向e，构成连接。
s->next=p->next 意思为原p指向的结点等同于s指向的结点，即连接1取代连接3，s结点指向了e结点。
p->next=s 意思则为s结点为p结点指向的下一个结点。即构成连接2。
本题通俗易懂版解析，将s结点插入链表中步骤生成s结点构建1连接，再构建2连接，切断3的图面意思。

5.删除（单链表法）

Status ListDelete_L(LinkList &L,int i,ElemType &e){
//在带头结点的单链线性表L中，删除第i个元素，并友e返回其值
p=L;j=0;
while(p->next&&j<j-1){ //寻找第i个结点，并令p指向其前驱
 p=p->next;++j;
 }
 if(!(p->next)||j>i-1)return ERROR; //删除位置不合理
 q=p->next;p->next=q->next; //删除并释放结点
 e=q->data; free(q);
return OK;
}//ListDelete_L

图像文字解析如下

q=p->next; q结点为p结点下一个指向的结点。
p->next=q->next 将q的下一个指向结点e的地址传给p，使p下一个连接的结点变成e，即生成连接3。
e=q->data 意思为 e为原q指向的下一个数据。
free(q) 清除q结点，则原链表无连接1和2。

6.删除（双向链表）

Status ListDelete_Dul(DuLinkList &L,int i,ElenType &e){
//删除带头结点的双链循环线性表L的第i个元素，i的合法值为1<=i<=表长
if(!(p=GetElemP_Dul(L,i))) //在L中确定第i个元素的位置指针p
 return ERROR;
 e=p->data;
 p->prior->next=p->next;
 p->next->prior=p->prior;
 free(p); return OK;
 }//ListDelete_Dul

图像分析如下（prior译为前驱）

关于p->prior->next=p->next;
p->next->prior=p->prior;的解析如下：

将p->next的位置信息赋予p->prior->next，即将2所指的位置信息给1，构成1号线。
将p->prior的位置信息赋予 p->next->prior，即将4所指的位置信息给予3，构成3号线
再通过free§,释放p结点。

插入（双链表法）

Status ListInsert_Dul(DuLinkList &L,int i,ElenType e){
//在带头结点的双链循环线性表中第i个位置之前插入元素e，
//i的合法值为1<=i<=表长+1。
if(!(p=GetElemP_Dul(L,i))) //在L中确定插入位置
return ERROR； //p=NULL，即插入位置不合法
if(!(s-(DuLinkList)malloc(sizeof(DuLNode)))) return ERROR;
s->data=e;
s->prior=p->prior; p->prior->next=s;
s->next=p; p->prior=s;
return OK;
}//LinkInsert_Dul

图像分析如下：

关于s->prior=p->prior; p->prior->next=s;
s->next=p; p->prior=s;
即分别是下图1至4号线的构造代码

基础练习

1.在内存中分配了一个Elemarray[10][20][30]的数组，单个Elem类型数据的大小为8字节，若array首元素地址为1024000，则元素array[5][7][9]的内存地址为().
A.1049000 B.1049680 C.1049072 D.1049752

先求array[5][0][0]地址:1024000+520308=1048000
再求array[5][7][0]地址:1048000+7308=1049680
最后求array[5][7][9]地址:1049680+98=1049752

2.在合并两个有序链表的算法中，如果使用了头结点
dummy，则该算法的空间复杂度和需要返回的（）
A.O(1);dummy B.O(mn);dummy->next C.取决于元素大小;dummy D.O(1);dummy->next

三、栈和队列

1.栈和队列的特性

栈：后进先出，（栈顶、栈底）
队列：先进先出

2.栈和递归

操作系统执行代码时，函数间的调用-返回关系正是通过调用栈来维护
函数递归调用本质也是一个栈型调用，因此可利用栈将一个递归函数改写为完全等价的非递归函数，避免操作系统层面的调用栈开销。

栈和队列的应用

1.栈的应用：括号匹配，表达式求值，进制转换，非递归的深度优先遍历（DFS）

2.队列的应用：循环队列

队首数据输入至队尾空间已满，弹出队首数据后，再输入数据至原队首的位置时实现循环利用已开的空间。

3.代码实现

1.顺序栈的实现

顺序栈的底层是一个数组，低地址为栈底，高地址为栈顶，只能从栈顶操作。

/*
(顺序)栈*/
//栈数据结构定义
#define MAX SIZE 10
typedef struct {
Student *data;
int size;
} Stack;

//往栈顶压入1个元素
bool Push(Stack &stk,const Student &s){
if (stk.size =MAX_SIZE){
return false;
}
int newTop =stk.size;
stk.data[newTop]=s;
stk.size++;
return true;
}

//弹出栈顶元素
bool Pop(Stack &stk){
if (stk.size =0){
return false;
}
stk.size--;
return true;
}

2.循环队列实现

/*循环队列*/
//循环队列数据结构
#define M 10
typedef struct {
Student data[M];
int front;
int back; //back表示队尾的下一个空位
}cQueue;
//C =Circulative

//求循环队列元素个数
int Getsize(CQueue &queue){
int size =(queue.back -queue.front M)%M;
return size;
}

//循环队列入队
bool Enqueue cQ(CQueue &queue,const Student &s){
int newBack (queue.back +1)%M;
if (newBack =queue.front){
return false;//头尾相接表示队列满了
}
queue.data[newBack]=s;
queue.back newBack;
return true;
}

//循环队列出队
bool Dequeue_CQ(CQueue &queue){
if (queue.front =queue.back){
return false;//头尾重合表示队列为空
}
queue.front= (queue.front +1)%M;
return true;
}

key1. 循环队列的容量是MAX—Size-1；

key2. 数组arry[M]中，循环队列当前元素数量计算（back-front+M）%M

key3.循环队列判满条件为（back+1）%MAX—Size==front下一尾等于当前头首尾相接
key4.循环队列判空条件为 back==front当前头等于当前尾首尾重合

四、树和二叉树

1.二叉树：每个结点至多为2个度；（所以二叉树可以是单支的）
2.森林：多棵树；
3.高度（深度 ）：最深的叶子结点所在的层数

4.二叉树性质：

二叉树第n层总计结点总数为2^n-1;
n个结点最多能构成多少种不同的二叉树：C(n，2n) / (n+1)；

5.两种特殊二叉树（满二叉树和完全二叉树的区别）：

满二叉树一定是完全二叉树，完全二叉树不是满二叉树；
完全二叉树只在最下层的最右边有空缺；

6.树/森林转换为二叉树

1.树转为二叉树：

每个结点只保留第一个孩子（老大）作为左孩子，剩下的孩子（老大的兄弟们）依次接到老大的右孩子链上。

2.森林转换为二叉树：

1.各树转换为二叉树；
2.各树根用右孩子链相连。
key1 森林向二叉树转换是确定且唯一的过程。

7. 二叉树存储实现

1.二叉树顺序存储实现（按各层从左至右数组排序）

1.顺序树中结点i的左右孩子分别是2i+1和2i+2（i从0开始计数）

2.二叉树链式实现

/*二叉树数据结构定义*/
typedef struct TreeNode{
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;

8.二叉树的遍历

1.先序遍历：根-左子树-右子树

2.中序遍历;左子树-根-右子树

3.后序遍历：左子树-右子树-根

key1：可以根据中序+先/后序来还原二叉树结构，先序+后序不行

9.哈夫曼树

权值最小的两根结点作为左右孩子，生成新的根结点，新结点权值为他们的权值之和

哈夫曼编码（左子树为0，右子树为1，默认小的权值放左边）

五、图 （多对多的逻辑结构）

1.在一个无向图中，所有顶点的度数之和为边数量的2倍
2.在一个有向图中，所有顶点的出度之和==所有顶点的入度之和
3.一个顶点可以连接除自己以外的点，则连n-1条边，n个顶点则n*（n-1）条边，无向图中一边连接两个结点，所以最大边数n*（n-1）/2
key1 不经中转：连通的，高速公路->双向的->无向图

图的存储结构：

1.邻接矩阵和邻接表