【笔记】数据结构笔记02

@toc

前话

算法学习网站：

itcharge
代码随想录
labuladong

参考严蔚敏数据结构

树与等价问题

typedef PTree MFSet;
	//查找算法

int find_mfset(MFSet S,int i){
	if(i<1||i>S.n) return -1;//i不属于任一集合
	for(j=i;S.nodes[j].parent>0;j=nodes[j].parents);
	return j;
}
//归并算法
Status merge_mfset(MFSet &S，int i,int j){
//S.node[i]和S.node[j]分别为S的互不相交的两个子集Si和Sj的根结点。
//求并集Si∪Sj
	if(i<1||i>S.n||j<1||j>S.n)return ERROR;
	S.node[i].parent=j;
	return OK;
}//merge_mfset

void mix_mfset(MFSet &S,int i,int j){
	if(i<1||i>S.n||j<1||j>S.n)return ERROR;
	if(S.nodes[i].parent>S.nodes[j].parent){
		S.nodes[j].parent+=S.nodes[i].parent;
		S.nodes[i].parent=j;
	}else{
		S[nodes[i].parent+=S.nodes[j].parent;
		S.nodes[j].parent=i;
	}
	return OK;
}
/
int fix_mfset(MFSet &S,int i){
	if(i<1||i>S.n)return -1;
	for(j=i;S.nodes[j].parent>0;j=S.nodes[j].parent);
	for(k=i;k!=j;k=t){
		t=S.nodes[k].parent;
		S.nodes[k].parent=j;
	}//进行路径压缩 将所有从根到元素i路径上元素都变成树根的孩子；
	return j;
}

赫夫曼树 p144

赫夫曼树没有度为1的结点，一棵有n个叶子结点的赫夫曼树共有2n-1个结点。可以存储在一个大小为2n-1的一维数组当中。
构成赫夫曼树后，
【求编码】：需从叶子结点出发走一条从叶子到根的路径。
【译码】：从根节点到叶子节点出发走
需知双亲信息和孩子信息

结构

typedef struct{
	unsigned int weight;//权值不能为负？
	unsigned int parent,lchild,rchild;
}HTNode,*HuffmanCode;//动态分配数组存储赫夫曼树；
typedef char ** HuffmanCode;//动态分配存储赫夫曼树编码表；

算法

void HuffmanCoding(HuffmanTree& HT,HuffmanCode& HC,int *w,int n){
//w存放n个字符的权值（均>0）,构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC
	if(n<=1)return ;
	int m=2*n-1;//哈夫曼树一共拥有的节点。
	HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));
	//0号单元未用
	
	for(p=HT,i=1;i<=n;++i，++p，++w)
		*p={*w,0,0,0};//先将每个权值存放进前n个
	
	for(;i<m;++i;++p)*p={0,0,0,0};//后面的结点全部赋值为0
	for(i=n+1;i<=m;++i){//遍历子节点。
		Select(HT,i-1,s1,s2);
		//在HT[1...i-1]选择parent为0且weight最小的两个结点，
		//其序号分别为s1,s2.
		HT[s1].parent=i;
		HT[s2].parent=i;
		
		HT[i].lchild=s1;
		HT[i].rchild=s2;
		
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
	//进行构建哈夫曼树
	
		HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
		//分配n个字符编码的头指针向量。
		cd=(char*) malloc(n*sizeof(char));
		//分配求编码的工作空间。
		cd[n-1]="\0";
		//编码结束符
		
		for(i=1;i<=n;++i){
		//逐个字符求赫夫曼编码
			start=n-1;//编码结束位置
				
			for(c=i，f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
			//求编码  从【叶子】到【根】逆向遍历
				if(HT[f].lchild==c)cd[--start]="0";
				else cd[--start]="1";
			
			HC[i]=(char*) malloc((n-start)*sizeof(char));
			//为第i个字符编码分配空间
			strcpy(HC[i],&cd[start]);
			//从cd复制编码（串）到HC
			
		}
		free(cd);//释放工作空间
}//HuffmanCoding

无栈非递归遍历赫夫曼树，求赫夫曼编码

HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
p=m,cdlen=0;
for(i=1;i<=m;++i)HT[i].weight=0;
//遍历赫夫曼树时用作结点状态标志；
while(p){
	if(HT[p].weight==0){//向左
		HT[p].weight=1;
		if(HT[p].lchild!=0){
			p=HT[p].lchild;
			cd[cdlen++]="0";
		}else if(HT[p].rchild==0){
			//登记叶子结点的字符编码；
			HC[p]=(char*)malloc((cdlen+1)*sizeof(char));
			cd[cdlen]="\0";
			strcpy(HC[p],cd);
			//复制编码（串）
		}
	}//endif
	else if{//向右
		HT[p].weight=2;
		if(HT[p].rchild!=0){
			p=HT[p].rchild;
			cd[cdlen++]="1";
		}
	}else{//HT[p].weight==2 退回
		HT[p].weight=0;
		p=HT[p].parent;
		--cdlen;//退到父结点，编码长度减一；
	}
}//while

求幂集元素过程

（1）集合
提示：集合的幂集就是集合A的所有子集所组成的集合。

题目：要求求n个元素的集合的幂集！
假设这里有三个元素：A={1,2,3}，那么集合A的幂集？
ρ（A）={{1，2,3}，{1,2}，{1,3}，{1}，{2,3}，{2}，{3}，Φ}
如下图所示：

参考
Keep_Trying_Go

求解集合的幂集

提示：求解ρ（A）集合的过程可以看成是依次对集合A中元素进行“取”或者“舍（弃）”的过程，通过上面也可以看到是一棵二叉树来表示幂集元素的状态变化状况。

过程：

• 树中的根节点表示幂集元素的初始状态（为空集）；
• 叶子节点表示它的终结状态中幂集ρ（A）的8个元素；
• 第i层（i=1,2,3,…,n）层的分支节点，则表示已对集合A中前i-1个元素进行了取/舍处理的当前状态（其中左分支表示“取”，右分支表示“舍”）；
• 将上述问题求解集合的幂集转换为先序遍历这棵状态树的过程。

//算法描述
void Powerset(int i,int n){
	//初始调用：Powerset(1,n)
	if(i>n){
		输出幂集的其中一个元素 
	}else{
		取第i个元素
		Powerset(i+1,n);
		舍第i个元素 
		Powerset(i+1,n);
	}
} 

void GetPowerSet(int i,List A,List &B){
	if(i>ListLength(A))	Output(B);
	else {
		GetElem(A,1,x);
 		int k=ListLength(B);
        ListInsert(B,k+1,x);
        GetPowerset(i+1,A,B);
 
        ListDelete(B,k+1,x);
        GetPowerset(i+1,A,B);

	}
}

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
 
#define maxn 10
 
//使用数组set表示集合
int set[maxn];
//使用辅助数组auxset表示取和舍的过程
int auxset[maxn];
 
void init(int n){
	for(int i=0;i<n;i++){
		set[i]=0;
		auxset[i]=0;
	} 
}
 
void Powerset(int i,int n){
//核心算法
	if(i>n){
		for(int j=0;j<i-1;j++){
			printf("%d  ",auxset[j]);
		}
		printf("\n");
	}else{
		auxset[i-1]=set[i-1];//进入左子树 取
		Powerset(i+1,n);
		auxset[i-1]=0;//进入右子树 舍
		Powerset(i+1,n);
	}
}
 
 
int main(){
	int n;
	printf("请输入集合的元素个数: ");
	scanf("%d",&n);
	init(n);
	printf("请输入元素: ");
	for(int i=0;i<n;i++){
		scanf("%d",&set[i]);
	}
	Powerset(1,n);
	return 0;
}
 

图

图没有顺序映像的存储结构，可以借助数组的数据类型表示元素之间的关系
用多重链表表示图是自然的事情。
两个数组分别存储数据元素（顶点）信息和数据元素的关系（边或弧）的信息

typedef enum{DG,DN,UDG,UDN}GraphKind;
//{有向图，有向网，无向图，无向网}
typedef struct ArcCell{
	VRType adj;
	//VRType 是顶点关系类型。对无权图，用1或0
	//表示相邻否，对带权图，则为权值类型
	InfoType *info;
	//该弧相关信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
	VertexType vexs[MAX_VERTEX_NUM];//顶点向量
	AdjMatrix arcs;//邻接矩阵
	int vexnum,arcnum;//图的当前顶点数和弧数
}MGraph

有向无环图

有向树，DAG图和有向图

检查有向图是否存在环比无向图复杂，
对于无向图来说，若深度优先遍历过程遇到回边（指向已访问过的顶点的边），则必定存在环。
对于有向图来说，这条回边有可能是指向深度优先生成森林中另一颗生成树上顶点的弧

有向图[关键路径和拓扑排序]

拓扑排序

集合上

偏序的定义：设R是集合A上的一个二元关系，若R满足：
Ⅰ 自反性：对任意x∈A，有xRx；
Ⅱ 反对称性（即反对称关系）：对任意x,y∈A，若xRy，且yRx，则x=y；
Ⅲ 传递性：对任意x, y,z∈A，若xRy，且yRz，则xRz。 则称R为A上的偏序关系。

全序：对每个x，y都有xRy或yRx，则可以称R是集合X上的全序关系。

全序：拓扑有序
偏序定义得到拓扑有序的操作是拓扑排序

动态存储管理

结构中的每个数据元素都占有一定的内存位置。数据元素的存取是通过对应的存储单元来进行的。

有了【高级语言】之后，程序员不需要直接和内存地址打交道，程序中使用的存储单元都由逻辑变量（标识符）表示。它们对应的内存地址都是由编译程序在【时期 ：编译或执行时】进行分配。

每个用户程序使用的内存由【操作对象：操作系统】进行分配，总的内存不够使用的时候可以采用自动覆盖技术。

编译程序中一个/几个字，在系统中几千，几万甚至是几十万。系统每次分配给用户的都是地址连续的内存区。

低地址：若干占用块
高地址：空闲块（堆）