哈希表

1哈希算法

將數據通過哈希算法映射成一個鍵值，存取都在同一個位置實現數據的高效存儲和查找，將時間復雜度盡可能降低至O(1)

2哈希碰撞

多個數據通過哈希算法得到的鍵值相同，成為產生哈希碰撞

3哈希表：

• 構建哈希表存放0-100之間的數據
• 哈希算法選擇：
  • 將0-100之間的數據的各位作為鍵值

4. 哈希表的實現

????????1. 哈希表插入

????????

linknode *phashtable[INDEX];
// 一個名為phashtable的指針型數組,一共INDEX個元素 每個元素的值都是linknode*型 指向鏈表的頭節點指針
// phashtable是二級指針哦 指向數組頭元素的地址常量(數組內元素都為地址 指向指針的指針則是二級指針)
int insert_hashtable(int tmpdata)
{int key = 0;linknode **pptmpnode = NULL;linknode *pnewnode = NULL;key = tmpdata % INDEX;//*pptmpnode != NULL說明哈希表當前這個元素后面有鏈表// 注意:你要操作循環的是 存放哈希表的元素指針值(這里變化的i是 二級指針)// pptmpnode等于哈希表里存的元素的地址// 先1 若2 再3(把指針往后挪一個)若2 再3 直到找到存放大于輸入的數據的鏈表位置退出循環for (pptmpnode = &phashtable[key]; *pptmpnode != NULL && (*pptmpnode)->data < tmpdata; pptmpnode = &((*pptmpnode)->pnext)){}// 新建鏈式空間pnewnode = malloc(sizeof(linknode));if (pnewnode == NULL){perror("fail to malloc");return -1;}pnewnode->data = tmpdata;pnewnode->pnext = *pptmpnode; // 若你插入的數字是62 *pptmpnode則是指向72節點的地址*pptmpnode = pnewnode;        //**ptmpnode 同時也是指向52節點里面pnext的值 改這個值return 0;
}

2. 哈希表遍歷

 int show_hashtable(void){int i = 0;linknode *ptmpnode = NULL;for (i = 0; i < INDEX; i++){printf("%d:", i);ptmpnode = phashtable[i];while (ptmpnode != NULL){printf("%2d ", ptmpnode->data);ptmpnode = ptmpnode->pnext;}printf("\n");}return 0;}

排序和查找算法：

1.冒泡排序

• 1. 時間復雜度為O()
• 2. 穩定的排序算法
• 3. 排序方法：
  • 相鄰的兩個元素比較，大的向后走，小的向前走
  • 循環找len-1個大的值

int bubble_sort(int *parray, int len){int i = 0;int j = 0;int tmp = 0;for (j = 0; j < len-1; j++){for (i = 0; i < len-1-j; i++){if (parray[i] > parray[i+1]){tmp = parray[i];parray[i] = parray[i+1];parray[i+1] = tmp;}}}return 0;}

2. 選擇排序

• 1. 時間復雜度O()
• 2. 不穩定排序算法
• 3. 排序方法：
  • 從前到后找最小值與前面的元素交換
  • 找到len-1個最小值嗎，最后一個最大值即排序完成

 int select_sort(int *parray, int len){int i = 0;int j = 0;int tmp = 0;int min = 0;for (j = 0; j < len-1; j++){min = j;for (i = j+1; i < len; i++){if (parray[i] < parray[min]){min = i;}}if (min != j){tmp = parray[min];parray[min] = parray[j];parray[j] = tmp;}}return 0;}

3.插入排序

• 1. 時間復雜度O()，如果是組有序時間復雜度降低至O(n)
• 2. 穩定的排序算法
• 3. 排序方法：
  • 將數組中的每個元素插入到有序數列中
  • 先將要插入的元素取出O()
  • 依次和前面元素比較，比元素大的向后走，直到前一個元素比要插入的元素小，或者到 達有序數列開頭停止
  • 插入元素即可

 int insert_sort(int *parray, int len){int tmp = 0;int i = 0;int j = 0;for (j = 1; j < len; j++){tmp = parray[j];for (i = j; i > 0 && tmp < parray[i-1]; i--){parray[i] = parray[i-1];}parray[i] = tmp;}return 0;
}

4.希爾排序

• 時間復雜度O(nlogn)
• 不穩定的排序算法
  • ?通過選擇不同的步長，將數組拆分成若干個小的數組實現插入排序
  • 若干個小的數組稱為有序數列后，使得數組中的數據大致有序
  • ?最后再對整體完成一個插入排序

????????

/* 耗時: 5 - 10ms*/int shell_sort(int *parray, int len){int step = 0;int j = 0;int i = 0;int tmp = 0;for (step = len/2; step > 0; step /= 2){for (j = step; j < len; j++){tmp = parray[j];for (i = j; i >= step && tmp < parray[i-step]; i -= 
step){parray[i] = parray[i-step];}parray[i] = tmp;}}return 0;}

5.快速排序

????????1. 時間復雜度為O(nlogn)

????????2. 不穩定的排序算法

????????3. 選擇左邊的作為鍵值，從后面找一個比鍵值小的放前面，從前面找一個比鍵值大的放后面，鍵 值放中間

????????4. 左右兩邊有元素則遞歸調用快速排序

int quick_sort(int *parray, int low, int high){int key = 0;int j = 0;int i = 0;key = parray[low];j = high;i = low;while (i < j){while (i < j && parray[j] >= key){j--;}if (i < j){parray[i] = parray[j];}while (i < j && parray[i] <= key){i++;}if (i < j){parray[j] = parray[i];}    }parray[i] = key;if (i-1 > low){quick_sort(parray, low, i-1);}if (i+1 < high){quick_sort(parray, i+1, high);}return 0;}

6.折半查找(二分查找)

????????時間復雜度O(logn)

 int mid_search(int *parray, int low, int high, int tmpdata){int mid = 0;if (low > high){return -1;}mid = (low + high) / 2;if (tmpdata == parray[mid]){return mid;}else if (tmpdata > parray[mid]){return mid_search(parray, mid+1, high, tmpdata);}else if (tmpdata < parray[mid]){return mid_search(parray, low, mid-1, tmpdata);}}

7順序查找

時間復雜度為O(n)