Linux学习-数据结构（哈希表）

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