1.哈希表

1.哈希算法

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

2.哈希碰撞

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

3.哈希表

• 構建哈希表存放0-100之間的數據
• 哈希算法選擇：

1.將0-100之間的數據的個位作為鍵值

4.哈希表的實現

1.元素插入

int insert_data_hashtable(int tmpdata)
{hashnode **pptmpnode = NULL;hashnode *pnewnode = NULL;int key = 0;key = tmpdata % INDEX;for(pptmpnode = &(phashtable[key]); *pptmpnode != NULL && (*pptmpnode)->data < tmpdata; pptmpnode = &(*pptmpnode)->pnext){}pnewnode = malloc(sizeof(hashnode));if(pnewnode == NULL){perror("fail to malloc");return -1;}pnewnode->data = tmpdata;pnewnode->pnext = *pptmpnode;*pptmpnode = pnewnode;return 0;
}

2.遍歷

int show_data_hashtable(void)
{int i = 0;hashnode *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;
}

3.元素查找

hashnode *find_data_hashtable(int tmpdata)
{int key = 0;hashnode *ptmpnode = NULL;key = tmpdata % INDEX;ptmpnode = phashtable[key];while(ptmpnode != NULL && ptmpnode->data <= tmpdata){if(ptmpnode->data == tmpdata){return ptmpnode;}ptmpnode = ptmpnode->pnext;}

4.銷毀

int destroy_hashtable(void)
{int i = 0;hashnode *ptmpnode = NULL;hashnode *pfreenode = NULL;for(i = 0; i < INDEX; i++){ptmpnode = phashtable[i];pfreenode = phashtable[i];while(ptmpnode != NULL){ptmpnode = ptmpnode->pnext;free(pfreenode);pfreenode = ptmpnode;}phashtable[i] = NULL;}return 0;
}

2.排序和查找算法

1.冒泡排序

• 時間復雜度o(n^2)
• 相鄰兩個元素比較，大的向后走，小的向前走

2.選擇排序

• 時間復雜度o(n^2)
• 從前到后找最小值與前面的元素交換
• 找到 len-1個最小值，最后一個最大值即排序完成

3.插入排序

• 時間復雜度o(n^2)，如果數組有序時間復雜度降低至o(n)
• 將數組中的每個元素插入到有序數列中
• 先將要插入的元素取出，依次和前面元素比較，比元素大的向后走，直到前一個元素比要插入的元素小，或者到達有序數列開頭為止

4.希爾排序

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

5.快速排序

• 時間復雜度o(nlogn)
• 選擇左邊的作為鍵值，從后面找一個比鍵值小的放前面，從前面找一個比鍵值的放后面，鍵值放中間
• 左右兩邊有元素則遞歸調用

6.折半查找（二分查找）

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);}
}