行业知识
数据结构——二叉树.顺序表结构及实现
1.树概念及结构
1.1树的结构
�� 树是一种非线性 的数据结构，它是由 n （ n>=0 ）个有限结点组成一个具有层次关系的集合。 把它叫做树是因 为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。 有一个特殊的结点，称为根结点 ，根节点没有前驱结点。 除根节点外，其余结点被分成M(M>0) 个互不相交的集合 T1 、 T2 、 …… 、 Tm ，其中每一个集合 Ti(1 27 , 15 , 19 , 18 , 28 , 34 , 65 , 49 , 25 , 37 }; set[pret]) //当父节点比子节点大时{ //就交换两者的值；
Sua(&set[cur], &set[pret]); //Sua为自己写的交换值的函数
cur = pret; //交换完后，使父节点变为子节点；
pret = pret * 2 + 1; //使子节点变为更小的字节点；
}
else
{
break;
}
} //当循环结束后，就完成调整了。
}
3.3.2建堆时间复杂度
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明( 时间复杂度本来看的 就是近似值，多几个节点不影响最终结果) ：3.3.3 堆的插入
先插入一个10 到数组的尾上，再进行向上调整算法，直到满足堆。 堆的插入数据时，我们写一个插入数据还需要再写一个 向上调整法；// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
//因为是顺序结构，所以我们要判断空间是否足够，不足时开辟新的空间进行插入操作
if (hp->size == hp->capacity)
{
if (hp->capacity == 0)
hp->capacity = 4;
else
hp->capacity = hp->capacity * 2;
int capy = hp->capacity;
HPDataType* set = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * capy);
if (set == NULL) //当set开辟空间失败时，返回。
{
printf("realloc error....");
exit(-1);
}
hp->a = set;
hp->capacity = capy;
}
hp->a[hp->size] = x;
hp->size++;
AdjustMake(hp->a, hp->size-1); //当插入数据后，为了保持堆的性质，我们需要把数 } // 据进行向上调整。
//向上调整
void AdjustMake(HPDataType* set, int size)
{ //size为插入数据的坐标大小
int mak = size; //mak为子节点
int cur = (size - 1) / 2; //cur为父节点
while (mak>0)
{
if (set[mak]
{
Sua(&set[mak], &set[cur]); //交换值
mak = cur; //把子节点变为父节点
cur = (cur - 1) / 2; //父节点也更新一下。
}
else
break;
}
}
3.3.4 堆的删除
删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。 // 堆的删除void HeapPop(Heap* hp)
{
assert(hp);
assert(hp->size>0); //hp->size也要断言一下
Sua(&hp->a[0], &hp->a[hp->size - 1]); //把堆顶的值与最后的值交换
hp->size-- ; //交换后别忘了要先把size-1再传参
AdjustDown(hp->a, hp->size ); //然后再向下调整一波，就完成了删除操作
}
3.3.5 堆的其余操作：
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
assert(hp);
assert(hp->size);
return hp->a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
assert(hp);
return hp->size;
}
// 堆的判空
bool HeapEmpty(Heap* hp)
{
assert(hp);
return hp->size == 0;
}
4.堆的代码：
typedef int HPDataType;typedef struct Heap{HPDataType* a;int size;int capacity;}Heap;//堆的初始化void HeapInit(Heap* hp);// 堆的销毁void HeapDestory(Heap* hp);// 堆的插入void HeapPush(Heap* hp, HPDataType x);// 堆的删除void HeapPop(Heap* hp);// 取堆顶的数据HPDataType HeapTop(Heap* hp);// 堆的数据个数int HeapSize(Heap* hp);// 堆的判空bool HeapEmpty(Heap* hp);//void Sua(HPDataType* pf, HPDataType* pt);void AdjustDown(HPDataType* set, int size);void AdjustMake(HPDataType* set, int size);//堆的初始化void HeapInit(Heap* hp){hp->a = NULL;hp->size = hp->capacity = 0;}// 堆的构建//void HeapCreate(Heap* hp, HPDataType* a, int n);//交换Suavoid Sua(HPDataType* pf, HPDataType* pt){HPDataType tmp = *pf;*pf = *pt;*pt = tmp;}// 堆的销毁void HeapDestory(Heap* hp){free(hp->a);hp->a = NULL;hp->capacity = hp->size = 0;}// 堆的插入void HeapPush(Heap* hp, HPDataType x){assert(hp);if (hp->size == hp->capacity){//hp->capacity == 0 ? 4 : hp->capacity * 2;//hp->capacity = 4;if (hp->capacity == 0)hp->capacity = 4;elsehp->capacity = hp->capacity * 2;int capy = hp->capacity;// a = sizeof(HPDataType) * capyHPDataType* set = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * capy);if (set == NULL){//perror(set);printf("realloc error....");exit(-1);}hp->a = set;hp->capacity = capy;}hp->a[hp->size] = x;hp->size++;AdjustMake(hp->a, hp->size - 1);}//向上调整void AdjustMake(HPDataType* set, int size){int mak = size;int cur = (size - 1) / 2;while (mak > 0){if (set[mak] size也要断言一下assert(hp->size > 0);Sua(&hp->a[0], &hp->a[hp->size - 1]);hp->size--;AdjustDown(hp->a, hp->size);}//想下调整void AdjustDown(HPDataType* set, int size){int cur = 0;int pret = cur * 2 + 1;while (pret set[pret + 1]){pret++;}if (set[cur] > set[pret]){Sua(&set[cur], &set[pret]);cur = pret;pret = pret * 2 + 1;}else{break;}}}// 取堆顶的数据HPDataType HeapTop(Heap* hp){assert(hp);assert(hp->size);return hp->a[0];}// 堆的数据个数int HeapSize(Heap* hp){assert(hp);return hp->size;}// 堆的判空bool HeapEmpty(Heap* hp){assert(hp);return hp->size == 0;}
上一篇：印度服务器在哪里？
下一篇：揭秘KC认证，真相大解密！
