数据结构6

一、哈希散列--通讯录查找

#include "hash.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>//int *a[10];int hash_function(char key)
{if (key >= 'a' && key <= 'z'){return key - 'a';}else if (key >= 'A' && key <= 'Z'){return key - 'A';}else{return HASH_TABLE_MAX_SIZE-1;}
}int insert_hash_table(Hash_node **hash_table, Data_type data)
{int addr = hash_function(data.name[0]);	Hash_node *pnode = malloc(sizeof(Hash_node));if (NULL == pnode){printf("fail malloc\n");return -1;}pnode->data = data;pnode->pnext = NULL;
/*pnode->pnext = hash_table[addr]; //pheadhash_table[addr] = pnode;
*/if (NULL == hash_table[addr]){hash_table[addr] = pnode;}else if (strcmp(hash_table[addr]->data.name, data.name) >= 0){pnode->pnext = hash_table[addr];hash_table[addr] = pnode;}else{Hash_node *p = hash_table[addr];while (p->pnext != NULL && strcmp(p->pnext->data.name, pnode->data.name) < 0){p = p->pnext;}pnode->pnext = p->pnext;p->pnext = pnode;}return 0;
}void hash_table_for_each(Hash_node **hash_table)
{for (int i = 0; i < HASH_TABLE_MAX_SIZE; i++){Hash_node *p = hash_table[i];while (p != NULL){printf("%s: %s\n", p->data.name, p->data.tel);p = p->pnext;}printf("\n");}
}Hash_node *find_hash_by_name(Hash_node **hash_table, char *name)
{int addr = hash_function(name[0]);Hash_node *p = hash_table[addr];while (p){if (0 == strcmp(p->data.name, name)){return p;}p = p->pnext;}return NULL;
}void destroy_hash_table(Hash_node **hash_table)
{for (int i = 0; i < HASH_TABLE_MAX_SIZE; i++){Hash_node *p = hash_table[i];while (p != NULL){hash_table[i] = p->pnext;free(p);p = hash_table[i];}}
}

二、前情回顾

顺序表：	数组
链式表：	单向链表双向链表循环链表内核链表
栈：	顺序栈链式栈
队列：	顺序队列、循环队列链式队列
散列结构：	哈希表：

三、树型结构

        1.定义(一对多)：

        树:由n个节点组成的有限集有一个根节点;其他节点只有一个前驱节点，但可以有多个后继节点。

        根：无前驱，有后继n=0，空树

                叶子结点（终端结点）：有前驱结点、无后继结点

                分支结点（非终端结点）：有前驱结点，有后继结点

        度：

                深度：树的层数

                广度：树中最大结点的度就是树的广度

                        结点的度：当前结点的后继结点个数

二叉树：树的度为二，且左右子树不可交换位置

满二叉树：在不增加层数的前提下，无法再增加一个结点

满二叉树第K层结点个数:2^(K-1)

                      K层满二叉树结点总个数:2^K-1

完全二叉树：在满二叉树的前提下，增加数据只能从上到下、从左至右；

删除数据只能从下至上，从右向左。

满二叉树->完全二叉树

完全二叉树 !-> 满二叉树

2.遍历

（广度优先遍历算法）

                前序遍历：根左右

中序遍历：左根右

后序遍历：左右根

（深度优先遍历算法）

                 层遍历：从上到下，从左到右，逐层遍历

*已知前序+中序才能还原出唯一的二叉树

#include "tree.h"
#include <stdio.h>
#include <stdlib.h>#include "queue.h"BTData_type tree[] = {"ABEH##M##F##DI#C##G##"};int idx = 0;
Tree_node *create_bintree()
{BTData_type data = tree[idx++];if ('#' == data){return NULL;}Tree_node *pnode = malloc(sizeof(Tree_node));if (NULL == pnode){printf("fail malloc\n");return NULL;}pnode->data = data;pnode->pl = create_bintree();pnode->pr = create_bintree();return pnode;
}void pre_order(Tree_node *proot)
{if (NULL == proot){return;}printf("%c", proot->data);pre_order(proot->pl);pre_order(proot->pr);
}void mid_order(Tree_node *proot)
{if (NULL == proot){return ;}mid_order(proot->pl);printf("%c", proot->data);mid_order(proot->pr);
}void pos_order(Tree_node *proot)
{if (NULL == proot){return ;}pos_order(proot->pl);pos_order(proot->pr);printf("%c", proot->data);
}int get_tree_node_cnt(Tree_node *proot)
{if (NULL == proot){return 0;}return 1 + get_tree_node_cnt(proot->pl)+get_tree_node_cnt(proot->pr);
}int get_tree_layer_cnt(Tree_node *proot)
{if (NULL == proot){return 0;}int cntl = get_tree_layer_cnt(proot->pl);int cntr = get_tree_layer_cnt(proot->pr);return cntl > cntr ? cntl+1 : cntr+1;}void destroy_tree(Tree_node **pproot)
{if (NULL == *pproot){return ;}destroy_tree(&((*pproot)->pl));destroy_tree(&((*pproot)->pr));free(*pproot);*pproot = NULL;
}void layer_order(Tree_node *proot)
{Queue *pque = create_queue();if (NULL == pque){return ;}Data_type outdata;enter_queue(pque, proot);while (!is_empty_queue(pque)){out_queue(pque, &outdata);printf("%c", outdata->data);if (outdata->pl != NULL){enter_queue(pque, outdata->pl);}if (outdata->pr != NULL){enter_queue(pque, outdata->pr);}}destroy_queue(&pque);
}

四、算法：解决特定问题的求解步骤

衡量算法：
算法的设计，
1.正确性.
        语法正确
        合法的输入能得到合理的结果。
        对非法的输入，给出满足要求的规格说明
        对精心选择，甚至习难的测试都能正常运行，结果正确

2.可读性，便于交流，阅读，理解高内聚低耦合

3.健壮性，输入非法数据，能进行相应的处理，而不是产生异常
4.高效率(时间复杂度)

时间复杂度：数据增长量与处理时间的关系

时间复杂度的计算规则
1，用常数1 取代运行时间中的所有加法常数

2、在修改后的运行医数中，只保留最高阶项

3、如果最高阶存在且系数不是1，则去除这个项相乘的常/数。

排序算法：
1. 思想
2. 代码
3. 时间复杂度
4. 排序算法的稳定性:对于两个相同的数据，经过排序，两个相同数据的相对位置没有
发生变化，这就是一个稳定的排序算法。

冒泡排序：相邻两两比较，优先排好最大值
for(i=len-1;i>0;--i)
{for(j=0;j<i;++j){if(a[i]>a[j]){swap(a[i],a[j]);   }}
}
时间复杂度：O（n^2）
稳定性：稳定

选择排序：将待排位置的数据和后续的数据依次进行比较，将小的存放在待排位置，
经过一趟，优先排好最小值。
              for(int i = 0; i < len-1; i++){for (int j = i+1,; j < len; j++){if (a[i] > a[j])swap(a[i], a[j]);}}
时间复杂度：O（n^2）
稳定性：不稳定

插入排序：将待排的元素，依次插入到一个有序序列中，确保插入后任然有序。
                       for (int i = 1; i < len; i++){j = i;int temp = a[i];while (j > 0 && a[j-1] > temp){a[j] = a[j-1];--j;}  a[j] = temp;}
时间复杂度：O（n^2）
稳定性：稳定

快速排序：选定基准值，从两头分别和基准值比较，比基准值大的向后，比基准值小的向前，优先排好基准值。
void Qsort(int *begin, int *end)
{int *p = begin;int *q = end;if(begin >= end){return ;}int t = *begin;while(p < q){while(p < q && *q >= t){--q;}while(p < q && *p <= t){++p;}swap(p, q);}swap(begin, p);Qsort(begin, p - 1);Qsort(p + 1, end);}
时间复杂度：O（nlogn）
稳定性：不稳定

希尔排序：将待排的序列，按照增量分成若干个子系列，对子序列进行插入排序。
void shell_sort(int *a, int len)
{int j = 0;for (int inc = len/2; inc > 0; inc /=2){for (int i = inc; i < len; i++){j = i;int tmp = a[i];while (j >= inc && a[j-inc] > tmp){a[j] = a[j-inc];j = j-inc;}a[j] = tmp;}}
}
时间复杂度：O（nlogn）-O（n^2）
稳定性：不稳定
二分查找：
前提：有序的序列
int BinaryFind(int a[],int len,int n){int begin=0;int end=len-1;int mid;while(begin<=end){mid=(begin+end)/2;if(n<a[mid]){end=mid-1;}else if(n>a[mid]){begin=mid+1;}else{break;}     }if(begin<=end){return mid;}else{return -1;}                                                                       }
时间复杂度：O（logn）