怎么买域名做企业网站,做服装在哪个网站找,响应式网站多少钱,网站别人做的上面有方正字体1.树的概念及结构
1.1树的概念
树是一种非线性的数据结构#xff0c;它是由n#xff08;n0#xff09;个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树#xff0c;也就是说它是根朝上#xff0c;而叶朝下的。 有一个特殊的结点…1.树的概念及结构
1.1树的概念
树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 有一个特殊的结点称为根结点根结点没有前驱结点除根结点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继 结构图 注意树形结构中子树之间不能有交集否则就不是树形结构
1.2树的相关概念 1.结点的度一个结点含有的子树的个数称为该结点的度 如上图A的为6 2.叶结点或终端结点度为0的结点称为叶结点 如上图B、C、H、I…等结点为叶结点 3.非终端结点或分支结点度不为0的结点 如上图D、E、F、G…等结点为分支结点 4.双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点 如上图A是B的父结点 5.孩子结点或子结点 一个结点含有的子树的根结点称为该结点的子结点 如上图B是A的孩子结点 6.兄弟结点具有相同父结点的结点互称为兄弟结点 如上图B、C是兄弟结点 7.树的度一棵树中最大的结点的度称为树的度 如上图树的度为6 8.结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推 9.树的高度或深度树中结点的最大层次 如上图树的高度为4 10.堂兄弟结点双亲在同一层的结点互为堂兄弟如上图H、I互为兄弟结点 11.结点的祖先从根到该结点所经分支上的所有结点如上图A是所有结点的祖先 12.孩子结点或子结点以某结点为根的子树中任一结点都称为该结点的子孙。如上图所有结点都是A的子孙 13.森林由mm0棵互不相交的树的集合称为森林
2.二叉树的概念及结构
2.1二叉树的概念
与树不同二叉树根结点的子节点有且不超过两个。 以下几个都是二叉树
2.2特殊的二叉树
满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且结点总数是 则它就是满二叉树。 完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。 ##2.3 二叉树的性质
若规定根结点的层数为h则一棵非空二叉树的第h层上最多有2^(h-1)个结点若规定根结点的层数为h则深度为h的二叉树的最大结点数是 2^h-1对任何一棵二叉树, 如果度为0其叶结点个数为n1, 度为2的分支结点个数为n2,则有n1n21假设在顺序表中父亲节点parent的下标是i则孩子节点child的下标分别是i * 2 1和i * 2 2分别对应左右孩子假设在顺序表中孩子节点child的下标是i,不管其是左孩子还是有孩子其父亲节点的下标都是(i - 1) / 2
2.4二叉树的存储形式
二叉树分为完全二叉树和不完全二叉树对于完全二叉树我们可以采用顺序表进行存储对于不完全二叉树我们则需采用链式存储
3.堆的顺序结构及实现
3.1堆的概念
堆是一种特别的完全二叉树堆分为大堆和小堆。 对于大堆堆中任意某个节点的值总是大于其子节点的值。 对于小堆堆中任意某个节点的值总是小于其父节点的值。
3.2堆的实现
堆结构的定义
对于堆我们是采用顺序表进行存储因此定义了一个指向数组的指针a和存储数据个数和申请的空间大小的两个变量。
typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;//数据个数int capacity;//空间大小
}HP;堆的初始化
堆的初始化就是顺序表的初始化我们先不申请空间后续插入数据的时候我们再申请。
//堆的初始化
void HPInit(HP* php)
{php-a NULL;php-size php-capacity 0;
}堆的插入
我们先判断空间是否足够当前空间大小为0的话申请4个字节大小的空间不为空的话就进行扩容两倍。
//堆的插入
void HPPush(HP* php, HPDataType x)
{assert(php);//判断空间是否足够if (php-size php-capacity){HPDataType newCapacity php-capacity 0 ? 4 : 2 * php-capacity;HPDataType* tmp (HPDataType*)realloc(php-a,sizeof(HPDataType) * newCapacity);if (tmp NULL){perror(HPPush():realloc);return;}php-a tmp;php-capacity newCapacity;}//先把数据插入数组尾部php-a[php-size] x;//然后向上调整AdjustUp(php-a, php-size - 1);
}向上调整这个函数传的两个参数分别表示要调整的数组和要调整的孩子节点child在数组中的下标。 有了孩子节点的下标我们就可以计算其父亲节点的下标int parent (child - 1) / 2; 因为我们要实现的是小堆所以如果父亲节点比孩子节点大我们则将父子节点进行交换交换完后我们得到新的父子节点的下标最坏的情况是孩子节点向上不断交换最后孩子节点的下标0说明其所在位置已经是根节点了是最小的数了比较也就停止。
//向上比较交换
void AdjustUp(HPDataType* a, int child)
{//将数组和最后一个数据下标传过去//求这个孩子节点的父亲节点int parent (child - 1) / 2;//这个孩子节点最终成为根节点则不再比较while (child 0){//我们要实现的是小堆父亲节点得比孩子节点小//如果孩子节点比父亲节点小则交换if (a[child] a[parent]){Swap(a[child], a[parent]);//孩子节点成为父亲节点继续和祖宗节点比较child parent;parent (child - 1) / 2;}//a[child] a[parent],符合小堆逻辑不用交换了else{break;}}
}里面对父子节点进行交换我们也单独写一个函数方便后续我们要使用的时候直接调用
//交换父子节点
void Swap(HPDataType* child, HPDataType* parent)
{HPDataType tmp *child;*child *parent;*parent tmp;
}堆的删除
我们要删除的是堆的根我们怎么删除他呢直接删除吗不行因为直接删除的话剩下的节点直接的关系就全乱了假如直接删除根节点后顺序表中的第二个数据就成为了根而其兄弟节点成为了他的孩子这时候二者就有了大小关系但我们知道兄弟节点之间是没有大小关系的因此这时候顺序表的剩下的数据还是一个堆吗不是了他们直接的关系全乱了。 所以我们要删除根节点的办法是先将根节点个顺序表中的最后一个数据进行交换然后这时候删除最后一个节点就相当于删除了原本的根节点。删除完后我们就需要对这时候的根节点进行调整了。
//堆的删除删除的是根
void HPPop(HP* php)
{assert(php);assert(php-size);//先将根和数组最后一个数据进行交换Swap((php-a[0]), (php-a[php-size - 1]));//然后删除数组最后一个数据即是删除原本小堆的根数据php-size--;//然后向下比较交换父子节点AdjustDown(php-a, php-size, 0);
}如何调整呢我们传三个参数一个是要操作的顺序表一个是顺序表中元素的个数因为我们前面删除了最后一个数(也就是原本的根节点)所以我们传数据个数的时候需要减去原本的那个根节点。第三个参数是需要调整的这个节点的下标因为我们是向下调整需要这个节点与其孩子节点进行比较所以我们命名这个节点为parent。 怎么比较呢这里我们是要保持我们的堆依旧是小堆所以我们要让大的元素与其孩子进行交换但一般父亲节点都有两个孩子我们要与谁进行交换呢我们要与两个孩子中较小的那个孩子进行交换因为如果我们是与较大的那个孩子进行交换的话我们还记得小堆的性质小堆中任意一个父亲节点的值都小于其孩子节点。 所以如果我们与较大的那个孩子节点交换后这个孩子节点就成为了父亲节点他需要比他的孩子节点小但是他是两个孩子中大的那个呀他成为父亲节点后他原本的兄弟节点就成为了他的孩子但他比他孩子大这就不构成小堆了。所以我们要与较小的那个孩子进行比较。 我们用假设法先假设左孩子较小如果右孩子比左孩子小那child就变成右孩子。 后续就是如果父亲节点比孩子节点大就交换然后确认出新的孩子节点和父亲节点。
//向下比较交换父子节点
void AdjustDown(HPDataType* a, int n, int parent)
{//n是数据个数parent是父亲节点的下标//假设法先假设左孩子是比较小的那个int child parent * 2 1;//当这个父亲节点变成叶子节点的时候就结束了//当他是叶子节点那他就没孩子了他孩子的下标就越界了while (child n){ //如果只有左孩子child1最后可能越界if (child 1 n a[child 1] a[child]){//那较小的那个就是右孩子child;}//父子节点进行比较父亲节点大于孩子节点则进行交换if (a[parent] a[child]){Swap(a[parent], a[child]);//这个节点变成孩子节点了继续找他的孩子节点parent child;child parent * 2 1;}//a[parent] a[child]满足小堆逻辑else{break;}}
}返回堆的根
判断不为空后直接返回顺序表第一个元素即可。
//返回堆的根
HPDataType HPTop(HP* php)
{assert(php);assert(php-size);return php-a[0];
}堆的判空
size 0为真返回1为假返回0
//堆的判空
bool HPEmpty(HP* php)
{assert(php);return php-size 0;
}堆的销毁
堆的销毁就是将顺序表动态申请的空间进行释放。
//堆的销毁
void HPDestroy(HP* php)
{free(php-a);php-a NULL;php-size php-capacity 0;
}4.堆排序
堆排序的思路是降序建小堆升序建大堆。 以升序为例我们先建大堆建完后我们的根节点是不是就是这个堆中最大的那个元素我们将根节点和数组中的最后一个元素进行交换然后将除最后一个元素(被交换的那个根节点)之外剩下的元素进行向下调整再次形成一个大堆这时候这个大堆的根节点是不是就是这个堆中最大的元素也就是数组中第二大的元素然后我们继续向下调整一直这个样重复我们就能得到一个升序的序列了。 参考代码如下
#define _CRT_SECURE_NO_WARNINGS 1#includestdio.h
#includeassret.hvoid Swap(int* child, int* parent)
{int temp *child;*child *parent;*parent temp;
}//向下调整父亲与孩子比较交换
void AdjustDown(int* a, int n, int parent)
{assert(a);//假设法先假设左孩子是较大的那个int child parent * 2 1;//孩子下标超过剩余元素个数说明父亲节点已经变成叶子节点了while (child n){if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}void HeapSort(int* a, int n)
{assert(a);//升序建大堆//从最后一个非叶子节点开始向下调整建堆//最后一个非叶子节点的下标是(n - 1 - 1) / 2这个下标作为父亲节点的下标for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}//建堆完后我们交换第一个和最后一个元素然后将根元素向下调整int end n - 1;while (end){Swap(a[0], a[end]);//end是最后一个元素的下标AdjustDown(a, end, 0);//end是除最后一个元素外剩余元素的个数--end;}
}int main()
{int a[] { 9,5,6,3,7,8,1,2,0,4 };//排个升序HeapSort(a, sizeof(a) / sizeof(a[0]));for (int i 0; i sizeof(a) / sizeof(a[0]); i){printf(%d , a[i]);}return 0;
}5.文件中的TopK问题
文件中的TopK问题就是我们有一个文件里面有很多数据我们要找出这些数据中最大的前k个元素。 思路是: 我们先创建一个k个元素的小堆(向下调整建堆)这k个元素是文件中的前k个元素。因为是小堆所以根节点位置的元素是k个元素中最小的那个元素然后我们将文件中剩下的n-k个元素依次与根节点进行比较如果比根节点位置的数据大我们就将根节点的数据进行覆盖然后我们将这个节点进行向下调整成新的小堆这样我们确保了根节点永远是k个元素中最小的那个这样子最后比较完后我们这个小堆中的k个元素就是文件里的n个元素中最大的k个元素了。 参考代码如下
#define _CRT_SECURE_NO_WARNINGS 1#includestdio.h
#includeassret.h
#includestdlib.h
#includetime.h//空间复杂度:O(k)
//时间复杂度:O((N-K)*logK),即O(N)void Swap(int* child, int* parent)
{int temp *child;*child *parent;*parent temp;
}//向下调整父亲与孩子比较交换
void AdjustDown(int* a, int n, int parent)
{assert(a);//假设法先假设左孩子是较小的那个int child parent * 2 1;//孩子下标超过剩余元素个数说明父亲节点已经变成叶子节点了while (child n){if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}void CreateNData()
{int n 100000;srand((unsigned int)time(NULL));FILE* fp fopen(test.txt, w);if (fp NULL){perror(CreateNData():fopen);return;}for (int i 0; i n; i){int x rand() % 10000000;fprintf(fp, %d\n, x);}fclose(fp);fp NULL;
}void PrintTopK()
{printf(请输入要查找最大的前多少个数:);int k 0;scanf(%d, k);//为数组申请k个空间int* kminHeap (int*)malloc(sizeof(int) * k);FILE* pf fopen(test.txt, r);if (pf NULL){perror(PrintTopK():fopen);return;}//读取文件前k个数据for (int i 0; i k; i){fscanf(pf, %d, kminHeap[i]);}//建小堆for (int i (k - 1 - 1) / 2; i 0; i--){AdjustDown(kminHeap, k, i);}int x 0;//返回的是读取成功的个数读取失败返回-1while (fscanf(pf, %d, x) 0){if (x kminHeap[0]){kminHeap[0] x;AdjustDown(kminHeap, k, 0);}}for (int i 0; i k; i){printf(%d , kminHeap[i]);}
}int main()
{//先先文件中放些数据//CreateNData();PrintTopK();return 0;
}
