数据结构笔记Data Structure

抽象

行为抽象

• 通俗地说便是将一个行为序列归并 (抽象)为一个行为的过程

例如： 将 “取碗筷、盛饭、盛菜，扒一口饭、夹一筷菜、再扒一口饭、再夹一筷菜” 的若干重复，然后放下碗筷的过程归并为吃饭。

数据抽象

• 通俗地说，就是将事物归类，或者说，将事物看成是一定型号、规格的数据，然后将性质接近的数据归纳(抽象)为一类.

例如：将圆、三角形、长方形归为形状类.

数据结构Data Structure

数据结构：

• 数据对象在计算机中的组织方式
  逻辑结构（线性、树、图）
• 数据对象必定与一系列加在其上的操作相关联
• 完成这些操作所用的方法就是算法
• 一系列性质相同的数据, 组织成一定的逻辑结构, 并带有自身的一系列操作
• 常见两种存储方式：数组、链表

抽象数据类型ADT（Abstract Data Type）

数据类型：

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

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

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

只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题

例：“矩阵”的抽象数据类型定义
类型名称：矩阵（Matrix）
数据对象集：一个MxN的矩阵A_MxN=（a_ij）（i=1,…,M;
j=1,…,N）由MxN个三元组<a,i,j>构成，其中a是矩阵元素的值，i是元素所在的行号，j是元素所在的列号。
操作集：对于任意矩阵A、B、C ∈ \in ∈ Matrix，以及整数i、j、M、N
Matrix Create(int M, int N):返回一个MxN的空矩阵；
int GetMaxRow（Matrix A）：返回矩阵A的总行数；
int GetMaxCol（Matrix A）： 返回矩阵A的总列数；
ElementType GetEntry（Matrix A， int i，int j）：返回矩阵A的第i行、第j列的元素；
Matrix Add（Matrix A，Matrix B）；如果A和B的行、列数一致，则返回矩阵C=A+B，否则返回错误标志；
Matrix Multiply（Matrix A，Matrix B）：如果A的列数等于B的行数，则返回矩阵C=AB，否则返回错误标志；

线性结构

多项式存储

方法1：顺序存储结构直接表示

• 数组各分量对应多项式各项，下标对应项的幂次

a[i]: 项xⁱ的系数a_i

• 两个多项式相加：两个数组对应分量相加

方法2：顺序存储结构表示非零项（结构数组）

• 每个非零项a_ixⁱ涉及两个信息：系数a_i和指数i
• 可以将一个多项式看成是一个（a_i，i）二元组的集合
• 用结构数组表示：数组分类是由系数a_i、指数i组成的结构，对应一个非零项

方法3：链表结构存储非零项

• 链表中每个结点存储多项式中的一个非零项，包括系数和指数两个数据域以及一个指针域

结构表示

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

多项式加法运算

采用不带头结点的单向链表，按照指数递减的顺序排列各项

struct PolyNode {
	int coef; //系数
	int expon; //指数
	struct PolyNode *link; //指向下一个结点的指针
};
typedef struct PolyNode *Polynomial;
Polynomial P1,P2;

算法思路：两个指针P1和P2分别指向这两个多项式第一个结点，不断循环；
P1->expon==P2->expon：系数相加，若结果不为0，则作为结果多项式对应项的系数。同时，P1和P2都分别指向下一项；
P1->expon>P2->expon：将P1的当前项存入结果多项式，并使P1指向下一项；
P1->exponexpon：将P2的当前项存入结果多项式，并使P2指向下一项；
当某一多项式处理完时，将另一个多项式的所有结点依次复制到结果多项式中去。

Polynomial PolyAdd(Polynomial P1, Polynomial P2)
{
	Polynomial front,rear,temp;
	int sum;
	rear=(Polynomial)malloc(sizeof(struct PolyNode));
	front=rear; //由front记录结果多项式链表头结点
	while(P1 && P2) //当两个多项式都有非零项待处理时
	{
		switch(Compare(P1->expon,P2->expon))
		{
			case 1:
				Attach(P1->coef,P1->expon,&rear);
				P1=P1->link;
				break;
			case -1:
				Attach(P2->coef,P2->expon,&rear);
				P2=P2->link;
				break;
			case 0:
				sum=P1->coef + P2->coef;
				if(sum)
				{
					Attach(sum,P1->expon,&rear);
				}
				P1=P1->link;
				P2=P2->link;
				break;
		}
	}
	//将未处理完的另一个多项式的所有结点依次复制到结果多项式中去
	for(;P1;P1=P1->link)
	{
		Attach(P1->coef,P1->expon,&rear);
	}
	for(;P2;P2=P2->link)
	{
		Attach(P2->coef,P2->expon,&rear);
	}
	rear->link=NULL;
	temp=front;
	front=front->link; //令front指向结果多项式第一个非零项
	free(temp); //释放临时空表头结点
	return front;
}

添加函数

void Attach(int c, int e, Polynomial *pRear)
{
	Polynomial P;
	P=(Polynomial)malloc(sizeof(struct PolyNode));
	P->coef=c; //对新节点赋值
	P->expon=e;
	P->link = NULL;
	(*pRear)->link = P;
	*pRear = P; //修改pRear值
}

多项式的表示（相乘和相加）

仅表示非零项

struct PolyNode {
	int coef; //系数
	int expon; //指数
	struct PolyNode *link; //指向下一个结点的指针
};

int main()
{
	Polynomial P1,P2,PP,PS;
	P1=ReadPoly();
	P2=ReadPoly();
	PP=Mult(P1,P2);
	PrintPoly(PP);
	PS=Add(P1,P2);
	PrintPoly(PS);
	
	return 0;
}

读入函数

Polynomial ReadPoly()
{
	Polynomial P, Rear,t;
	int c,e,N;
	scanf("%d",&N);
	P=(Polynomial)malloc(sizeof(struct PolyNode)); //链表头空结点
	P->link = NULL;
	Rear = p;
	while(N--)
	{
		scanf("%d %d",&c,&e);
		Attach(c,e,&Rear); //将当前多项式插入尾部
	}
	.t=P;
	P=P->link;
	free(t); //删除临时生成的头结点
	return P;
}

void Attach(int c, int e, Polynomial *pRear)
{
	Polynomial P;
	P=(Polynomial)malloc(sizeof(struct PolyNode));
	P->coef=c; //对新节点赋值
	P->expon=e;
	P->link = NULL;
	(*pRear)->link = P;
	*pRear = P; //修改pRear值
}

相乘函数（乘法转化为加法）

Polynomial Mult(Polynomial P1, Polynomial P2)
{
	Polynomial P, Rear, t1,t2,t;
	int c,e;
	if(!P1 || !P2)  //由一个多项式为0，返回NULL
	{
		return NULL;
	}
	t1=P1;
	t2=P2;
	P=(Polynomial)malloc(sizeof(struct PolyNode));
	P->link = NULL;
	Rear=P;
	while(t2) //先用P1的第1项乘以P2，得到P
	{
		Attach(t1->coef*t2->coef, t1->expon+t2->expon, &Rear);
		t2=t2->link;
	}
	t1=t1->link;
	while(t1) // 依次用P1余下的项乘以P2的每一项，并及时添加到P中
	{
		t2=P2;
		Rear = P;
		while(t2)
		{
			e=t1->expon + t2->expon;
			c = t1->coef*t2->coef;
			while(Rear->link && Rear->link->expon>e)
			{
				Rear=Rear->link;
			}
			if(Rear->link && Rear->link->expon== e)
			{
				if(Rear->link->coef+c)  //系数相加结果为不为0，更新系数
				{
					Rear->link->coef += c;
				}
				else    //系数相加结果为0，清除该项
				{
					t=Rear->link;
					Rear->link = t->link;
					free(t);
				}
			}
			else
			{
				t=(Polynomial)malloc(sizeof(struct PolyNode));
				t->coef = c;
				t->expon = e;
				t->link = Rear->link;
				Rear->link = t;
				Rear = Rear->link;
			}
			t2=t2->link;
		}
		t1=t1->link;
	}
	t2=P;
	P=P->link;
	free(t2);
	return P;
}

输出函数
void PrintPoly(Polynomial P)
{
int flag = 0; //辅助调整输出格式用
if(!P) //如果P为空，输出0
{
printf(“0 0\n”);
return;
}
while§
{
if(!flag) //第一项不打印空格
{
flag = 1;
}
else
{
printf(" “);
}
printf(”%d %d", P->coef, P->expon);
P=P->link; //移到下一项
}
}

线性表Linear List

多项式表示问题的启示：

1. 同一个问题可以有不同的表示（存储）方法
2. 有一类共性问题：有序线性序列的组织和管理

线性表：由同类型数据元素构成有序序列的线性结构

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

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

1. 类型名称：线性表（List）
2. 数据对象集：线性表是n(>=0)个元素构成的有序序列（a₁，a₂，…，a_n）
3. 操作集：线性表L∈List，整数i表示位置，元素X∈ElementType，线性表基本操作主要有：

地方

1. List Make Empty(): 初始化一个空线性表L；
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。

线性表的顺序存储实现

利用数组的连续存储空间顺序存放线性表的各元素

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

主要操作实现
1,初始化（建立空的顺序表）

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

2，查找

int Find(ElementType X, List PtrL)
{
	int i=0;
	while(i <= PtrL->Last && PtrL->Data[i] != X)
	{
		i++;
	}
	if(i>PtrL->Last)
	{
		return -1; //如果每找到，返回-1
	}
	else
	{
		return i;   //找到后返回的是存储位置
	}
}

3，插入（第i(1<=i<=n+1)个位置上插入一个值为X的新元素）

• 先移动再插入

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++;  //Last仍指向最后元素
	return;
}

4，删除（删除表的第i(1<=i<=n)个位置上的元素）

• 后面的元素依次前移

void Delete(int i, List PtrL)
{
	int j;
	if(i<1 || i>Ptrl->Last+1) //检查空表及删除位置的合法性
	{
		printf("不存在第%d个元素"，i);
		return;
	}
	for(j=i; j<=PtrL->Last;j++)
	{
		PtrL->Data[j-1] = PtrL->Data[j]; //将a(i+1)~a(n)顺序向前移动
	}
	PtrL->Last--; //Last仍指向最后元素
	return;
}

线性表的链式存储实现

不要求逻辑上相邻的两个元素物理上也相邻；通过“链”建立起数据元素之间的逻辑关系

插入、删除不需要移动数据元素，只需要修改“链”

typedef struct LNode *List;
struct LNode {
	ElementType Data;
	List Next;
} ;
struct LNode L;
List PtrL;

主要操作实现
1，求表长

int Length(List PtrL)
{
	List p = PtrL; //p指向表的第一个结点
	int j=0;
	while(p)
	{
		p=p->Next;
		j++; //当前p指向的是第j个结点
	}
	return j;
}

2，查找
（1）按序号查找：FindKth;

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; //找到第K个，则返回指针
	}
	else
	{
		return NULL； //否则返回空
	}
}

（2）按值查找Find

List Find(ElementType X,List PtrL)
{
	List p=PtrL;
	while(p!=NULL && p->Data!= X)
	{
		p=p->Next;
	}
	return p;
}

3，插入（在第i-1(1<=i<=n+1)个结点后插入一个值为X的新结点）
（1）先构造一个新结点，用s指向
（2）再找到链表的第i-1个结点，用p指向；
（3）然后修改指针，插入结点（p之后插入新结点时s）

先让s指向p的下一个结点，然后让p指向s

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;
		returns;
	}
	p=FindKth(i-1, PtrL); //查找第i-1个结点
	if(p==NULL)
	{
		printf("参数i错"); //第i-1个不存在，不能插入
		return NULL;
	}
	else
	{
		s=(List)malloc(sizeof(struct LNode)); //申请、填装结点
		s->Data= X;
		s->Next=p->Next; //新结点插入在第i-1个结点的后面
		p->Next=s;
		return PtrL;
	}
}

4，删除（删除链表的第i(1<=i<=n)个位置上的结点）
（1）先找到链表的第i-1个结点，用p指向；
（2）再用指针s指向要被删除的结点（p的下一个结点）s=p->Next；
（3）然后修改指针(s->Next=p->Next)，删除s所指结点；
（4）最后释放s所指结点的空间(free(s))。

List Delete(int i, List PtrL)
{
	List p, s;
	if(i==1) //若要删除的时表的第一个结点
	{
		s=PtrL; //s指向表的第一个结点
		if(PtrL!=NULL)
		{
			PtrL=PtrL->Next; //从链表中删除
		}
		else
		{
			return NULL;
		}
		free(s); //释放被删除结点
		return PtrL;
	}
	p=FindKth(i-1,PtrL); //查找第i-1个结点
	if(p==NULL)
	{
		printf("第%d个结点不存在", i-1);
		return NULL;
	}
	else if(p->Next==NULL)
	{
		printf("第%d个结点不存在", i);
		return NULL;
	}
	else
	{
		s=p->next; //s指向第i个结点
		p->Next=s->Next; //从链表中删除
		free(s); //释放被删除结点
		return PtrL;
	}
}

链表的逆转算法

抽象的链表

单链表的逆转

测试数据（边界测试）

广义表（Generalized List)

Union的应用

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

typedef struct GNode *GList;
struct GNode {
	int Tag;  //标志域：0表示结点时单元素，1表示结点时广义表
	union {  //子表指针域Sublist与单元素数据域Data复用，即共用存储空间
		ElementType Data;
		GList SubList;
	} URegion;
	GList Next; //指向后继结点
};

多重链表

链表中的结点可能同时隶属于多个链

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

多重链表有广泛的用途：
基本上如树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储

矩阵A的多重链表图

堆栈

堆栈的抽象数据类型描述

堆栈（Stack）：具有一定操作约束的线性表
只在一端（栈顶，Top）做插入、删除

• 插入数据：入栈（Push）
• 删除数据：出栈（Pop）
• 后入先出：Last In First Out（LIFO）

栈的顺序存储实现

• 栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成

#define MaxSize <存储数据元素的最大个数>
typedef struct SNode *Stack;
struct SNode {
	ElementType Data[MaxSize];
	int Top;
};

(1)入栈

void Push(Stack PtrS, ElementType item)
{
	if(PtrS->Top==MaxSize-1)
	{
		printf("堆栈满");
		return;
	}
	else
	{
		PtrS->Data[++(PtrS->Top)] = item;
		return;
	}
}

(2)出栈

ElementType Pop(Stack PtrS)
{
	if(PtrS->Top == -1)
	{
		printf("堆栈空");
		return ERROR; //ERROR是ElementType的特殊值，标志错误
	}
	else
	{
		return(PtrS->Data[(PtrS->Top)--]);
	}
}

一个数组实现两个堆栈

要求最大地利用数组空间，使数组只要有空间入栈操作就可以成功。

解析：使这两个栈分别从数组的两头开始向中间生长；当两个栈的栈顶指针相遇时，表示两个栈都满了。

#define MaxSize <存储数据元素的最大个数>
struct DStack {
	ElementType Data[MaxSize];
	int Top1; //堆栈1的栈顶指针
	int Top2; //堆栈2的栈顶指针
}S;
S.Top1=-1;
S.Top2=MaxSize;

Push操作

void Push(struct DStack *PtrS, ElementType item, int Tag)
{
	//Tag作为区分两个堆栈的标志，取值为1和2
	if(PtrS->Top2 - PtrS->Top1 == 1) //堆栈满
	{
		printf("堆栈满");
		return;
	}
	if(Tag==1) //对第一个堆栈操作
	{
		PtrS->Data[++(PtrS->Top1)] = item;
	}
	else //对第二个堆栈操作
	{
		PtrS->Data[--(PtrS->Top2)] = item;
	}
}

Pop操作

ElementType Pop(struct DStack *PtrS, int Tag)
{
	//Tag作为区分两个堆栈的标志，取值1和2
	if(Tag==1) //对第一个堆栈操作
	{
		if(PtrS->Top1 == -1) //堆栈1空
		{
			printf("堆栈1空"); 
			return NULL;
		}
		else
		{
			return PtrS->Data[(PtrS->Top1)--];
		}
	}
	else //对第二个堆栈操作
	{
		if(PtrS->Top2 ==MaxSize) //堆栈2空
		{
			printf("堆栈2空");
			return NULL;
		}
		else
		{
			return PtrS->Data[(PtrS->Top2)++];
		}
	}
}

堆栈的链式存储实现

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

typedef struct SNode *Stack;
struct SNode {
	ElementType Data;
	struct SNode *Next;
};

(1)堆栈初始化（建立空栈）
(2)判断堆栈S是否为空

Stack CreateStack()
{
	//构建一个堆栈的头结点，返回指针
	Stack S;
	S=(Stack)malloc(sizeof(struct SNode));
	S->Next = NULL;
	return S;
}

int IsEmpty(Stack S)
{
	//判断堆栈S是否为空，若为空函数返回整数1，否则返回0
	return (S->Next == NULL);
}

入栈操作

void push(ElementType item, Stack S)
{
	//将元素item压入堆栈
	struct SNode *TmpCell;
	TmpCell=(struct SNode *) malloc(sizeof(struct SNode));
	TmpCell->ElementType = item;
	TmpCell->Next = S->Next;
	S->Next = TmpCell;
}

出栈操作

ElementType Pop(Stack S)
{
	//删除并返回堆栈S的栈顶元素
	struct SNode *FirstCell;
	if(IsEmpty(S))
	{
		printf("堆栈空");
		return NULL;
	}
	else
	{
		FirstCell=S->Next;
		S->Next = FirstCell->Next;
		TopElem = FirstCell->Element;
		free(FirstCell);
		return TopElem;
	}
}

堆栈应用：表达式求值

• 应用堆栈实现后缀表达式求值的基本过程：
  从左到右读入后缀表达式的各项（运算符或运算数）
  1，运算数：入栈；
  2，运算符：从堆栈中弹出适当数量的运算数，计算并将结果入栈；
  3，最后堆栈顶上的元素就是表达式的结果值

中缀表达式求值

• 基本策略：将中缀表达式转换为后缀表达式，然后求值
  1，运算数相对顺序不变
  2，运算符号顺序发生改变
  需要存储“等待中”的运算符号
  要将当前运算符号与“等待中”的最后一个运算符号比较
  
  中缀表达式转换为后缀表达式

• 从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理。
  ①运算数：直接输出；
  ②左括号：压入堆栈；
  ③右括号；将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）；
  ④运算符：
  若优先级大于栈顶运算符时则把它压栈；
  若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈；
  ⑤若各对象处理完毕，则把堆栈中留存的运算符一并输出。

堆栈的其他应用：

• 函数调用及递归实现
• 深度优先搜索
• 回溯算法

队列

队列：具有一定操作约束的线性表
插入和删除操作：只能在一端插入，而在另一端删除。
数据插入：入队列（AddQ）
数据删除：出队列（DeleteQ）
先进先出：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组成。

#define MaxSize <存储数据元素的最大个数>
struct QNode {
	ElementType Data[MaxSize];
	int rear;
	int front;
};
typedef struct QNode *Queue;

顺环队列

• 问题：
  堆栈空和满的判断条件是什么？
  为什么会出现空、满无法区分？根本原因是什么？
• 解决方案：
  使用额外标记：Size(0~n)或者tag(0/1)域
  仅使用n-1个数组空间

(1)入队列

void AddQ(Queue PtrQ, ElementType item)
{
	if((PtrQ->rear+1)%MaxSize==PtrQ->front)//求余
	{
		printf("队列满");
		return;
	}
	PtrQ->rear=(PtrQ->rear+1)%MaxSize;
	PtrQ->Data[PtrQ->rear] = item;
}

(2)出队列

ElementType DeleteQ(Queue PtrQ)
{
	if(PtrQ->front==PtrQ->rear)
	{
		printf("队列空");
		return ERROR;
	}
	else
	{
		PtrQ->front=(PtrQ->front+1)%MaxSize;
		return PtrQ->Data[PtrQ->front];
	}
}

队列的链式存储实现

队列的链式存储结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行；队列指针front指向表头，rear指向表尾。

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("队列空");
		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;
}

树

引子

数据管理的基本的三个操作：查找，插入，删除

查找（Searching）

查找：根据某个给定关键字K，从集合R中找出关键字与K相同的记录

• 静态查找：集合中记录是固定的
  没有插入和删除操作，只能查找
• 动态查找：集合中记录时动态变化的
  除查找，还可能发生插入和删除

静态查找

• 方法1：顺序查找

①哨兵模式：

int SequentialSearch(List Tbl, ElementType K)
{/*在Element[1]~Element[n]中查找关键字为K的数据元素*/
	int i;
	Tbl->Element[0] = K; /*建立哨兵*/
	for(i= Tbl->Length; Tbl->Element[i]!=K; i--)
	{
		;
	}
	return i;/*查找成功返回所在单元下标；不成功返回0*/
}
typedef struct LNode *List;
struct LNode{
	ElementType Element[MAXSIZE];
	int Length;
};

②无哨兵：

int SequentialSearch(List Tbl, ElementType K)
{/*在Element[1]~Element[n]中查找关键字为K的数据元素*/
	int i;
	
	for(i= Tbl->Length; i>0 && Tbl->Element[i]!=K; i--)
	{
		;
	}
	return i;/*查找成功返回所在单元下标；不成功返回0*/
}

• 方法2：二分查找（Binary Search）

假设n个数据元素的关键字满足有序（比如：小到大）
k1 < k2 < … < kn
并且时连续存放（数组），那么可以进行二分查找。

【例】假设有13个数据元素，按关键字由小到大顺序存放。
二分查找关键字为444的数据元素过程如下：

int BinarySearch(List Tbl, ElementType K)
{/*在表Tbl中查找关键字为K的数据元素*/
	int left,right,mid,NoFound=-1;
	left=1; //初始左边界
	right = Tbl->Length; //初始右边界
	while(left<=right)
	{
		mid =(left+right)/2; //计算中间元素坐标
		if(K<Tbl->Element[mid])
		{
			right = mid-1; //调整右边界
		}
		else if(K>Tbl->Element[mid])
		{
			left = mid+1; //调整左边界
		}
		else
		{
			return mid; //查找成功，返回数据元素的下标
		}
	}
	return NotFound; //查找不成功，返回-1
}

什么是树

• 客观世界中许多事物存在层次关系

人类社会家谱
社会组织结构
图书信息管理

• 分层次组织在管理上具有更高的效率！

树（Tree）：n（n>=0）个结点构成的有限集合。

• 当n=0时，称为空树；
• 对于任一棵非空树（n>0），它具备以下性质：
  树中有一个称为“根（Root）”的特殊结点，用r表示；
  其余结点可分为m（m>0）个互不相交的有限集T1，T2，…，Tm，其中每个集合本身又是一棵树，称为原来树的“子树（SubTree）”
• 子树是不相交的；
• 除了根结点外，每个结点有且仅有一个父节点
• 一颗N个结点的树有N-1条边

树的基本术语

1，结点的度（Degree）：结点的子树个数
2，树的度：树的所有结点中最大的度数
3，叶结点（Leaf）：度为0的结点
4，父结点（Parent）：有子树的结点是其子树的根结点的父结点
5，子结点（Child）：若A结点时B结点的父结点，则称B结点是A结点的子结点：子结点也称孩子结点
6，兄弟结点（Sibling）：具有同一父结点的各结点彼此是兄弟结点
7，路径和路径长度：从结点n₁到n_k的路径为一个结点序列，n_i是n_i+1的父结点。路径所包含边的个数为路径的长度。
8，祖先结点（Ancestor）：沿树根到某一结点路劲上的所有结点都是这个结点
9，子孙结点（Descendant）：某一结点的子树中的所有结点时这个结点的子孙
10，结点的层次（Level）：规定根结点在1层，其它任一结点的层数是其父结点的层数加1
11，树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度。

二叉树

定义

二叉树T:一个有穷的结点集合

• 这个集合可以为空
• 若不为空，则它是由根结点和称为其左子树T_L和右子树T_R的两个不相交的二叉树组成

二叉树五种基本形态

特殊二叉树

斜二叉树

完美二叉树

完全二叉树

二叉树几个重要性质

• 一个二叉树第i层的最大结点数为：2^i-1， i >=1
• 深度为k的二叉树有最大结点总数为：2^k-1, k>=1
• 对任何非空二叉树T，若n₀表示叶结点的个数、n₂是度为2的非叶结点个数，那么两者满足关系n₀=n₂+1

二叉树的抽象数据类型定义

类型名称：二叉树
数据对象集：一个有穷的结点集合。若不为空，则由根结点和其左、右二叉子树组成。
操作集：BT∈BinTree，Item∈ElementType，重要操作有：
1，Boolean IsEmpty(BinTree BT)：判别BT是否为空；
2，void Traversal(BinTree BT)：遍历，按某顺序访问每个结点；
3，BinTree CreatBinTree()：创建一个二叉树。

常用遍历方法：

代码表示

typedef struct TNode Position;
typedef Position BinTree; / 二叉树类型 /
struct TNode{ / 树结点定义 /
ElementType Data; / 结点数据 /
BinTree Left; / 指向左子树 /
BinTree Right; / 指向右子树 */
};

二叉树的存储结构

1，顺序存储结构


2，链表存储

二叉树的遍历

先序遍历

中序遍历

后序遍历

二叉树的非递归遍历

后序非递归遍历

方法一：

voidPostOrderTraversal(BinTreeBT)
{
	BinTreeT=BT;
	BinTreeExist=NULL;
	StackS=CreatStack(MaxSize);//初始化堆
	while(T||!IsEmpty(S))
	{
		while(T&&T->Left!=Exist&&T->Right!=Exist)
		{
			//是否遍历完，左孩子或右孩子是否已入栈
			Push(S,T);//从(子)树根向左将结点入栈
			T=T->Left;
		}
		if(!IsEmpty(S))
		{
			T=GetTop(S);//获取栈顶元素
			if(T->Right&&T->Right!=Exist)
			{
				//右孩子存在且未入过栈
				T=T->Right;//如果左边最后的结点有右子树,继续上述入栈操作
			}
			else
			{
				T=Pop(S);//没有右子树了，就出栈
				printf("%5d",T->Data);//读根
				Exist=T;//存放已读根的左孩子
				T=GetTop(S);//获取栈顶元素，即返回已读根的父结点
			}
		}
	}
}

难点在于对根的左右孩子是否曾经入过栈的判定，以及栈顶元素的返回时机

方法二：

使用两个栈，s和s2。使用 【根->右->左】 的方式，在第一次遇到结点时，就将结点的值压入栈s2中，那么最后遍历完了，根据栈的性质，s2依次弹出的就是【左->右->根】的后续遍历了

void PostorderTraversal2( BinTree BT ){

    BinTree T = BT;

    stack<BinTree> s;

    stack<ElementType> s2;

    while (T || !s.empty()){

        while (T){

            s.push(T);

            s2.push(T->Data);

            T = T->Right;

        }

        if (!s.empty()){

            T = s.top();

            s.pop();

            T = T->Left;

        }

    }

    while (!sr.empty()){

        printf("%5d", s2.top());

        s2.pop();

    }

}

层序遍历

二叉树遍历例子

题意理解及二叉树表示

程序框架搭建（判别同构）

二叉搜索树

中序遍历是正序的（由小到大排列）

搜索树特别函数

查找Find

查找最大值和查找最小值

插入

删除

平衡二叉树

平衡二叉树的调整(RR、LL、LR、RL旋转）

判断是否是同一棵二叉搜索树

题意理解

解题方法

求解思路

flag标记是否被访问过

程序框架搭建

建搜索树

判别

堆

优先队列

堆的特性

堆的抽象数据类型描述

最大堆

创建

插入

删除

应用：堆排序

把最后一个节点和它的父节点（左兄弟）先排序成一个堆，依次往前、往上逐步完成从小堆到大堆的调整。

堆中的路径（例）

哈夫曼树与哈夫曼编码

例引

哈夫曼树定义（最优二叉树）

哈夫曼树构造

哈夫曼树特点

哈夫曼编码

集合

集合的表示

集合运算

集合实例File Transfer（并查集）

TSSN实现

按秩归并（对union函数改进）

路径压缩（对find函数改进）

时间复杂度（引理Tarjan）

图

什么是图

抽象数据类型

常见术语

无向图：所有边不分方向
有向图：边有单向或双向
网络：带权重的图
……

在程序中表示一个图

邻接矩阵