数据结构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]; //phead hash_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）

5.低存储(空间复杂度)