数据结构---哈西表、算法

一、哈希表

哈希算法：
    在记录的存储位置和它的关键字之间建立一种去特定的对应关系，使得每个关键字key对应一个存储位置；
    查找时，根据确定的对应关系，找到给定的key的映射。
    
        记录的存储位置 = f（关键字）

我们把这种关系f称为哈希函数（散列函数）；
    采用这种散列技术将记录存储在一块连续的存储空间，这块连续存储开空间称为哈希表或散列表。
    
    存储时，通过散列函数计算出记录的散列地址；
    查找时，根据同样的散列函数计算记录的散列地址，并按此散列地址访问记录。
     

#include<head.h>
#include"hash.h"HSNode_t *hashtable[HASH_SIZE]={NULL};                //以全局表量形式表示哈希表/*哈希函数*/
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_SIZE - 1;}
}
/*插入链表*/
int insert_hashtable(HSDataTYpe data)
{int addr = hash_function(data.name[0]);HSNode_t *pnode = malloc(sizeof(HSNode_t));if(NULL == pnode){perror("malloc fail");return -1;}pnode->data = data;pnode->pnext = NULL;pnode->pnext = hashtable[addr];hashtable[addr] = pnode;return 0;
}
/*遍历*/
void printf_hash()
{for(int i= 0;i < 26;++i){HSNode_t *p = hashtable[i];while(p != NULL){printf("%s %s\n",p->data.name,p->data.tel);p = p->pnext;}}
}
/*查找*/
HSNode_t *find_hash(char *name)
{int addr = hash_function(name[0]);HSNode_t *p = hashtable[addr];while(p != NULL){if(strncmp(name,p->data.name,strlen(name)) == 0){return p;}p=p->pnext;}
}/*删除*/ 
int  pop_hash(int i)
{HSNode_t *pdel = hashtable[i];if(NULL == pdel){return 0;}hashtable[i] = pdel->pnext;free(pdel);return 1;
}
/*销毁*/
void destory()
{for(int i=0;i<HASH_SIZE;++i){while(hashtable[i] != NULL){pop_hash(i);}}
}
/********************************************************************/
#ifndef _HASH_H
#define _HASH_H#define HASH_SIZE 27typedef struct per
{char name[64];char tel[32];
}HSDataTYpe;typedef struct hsnode
{HSDataTYpe data;struct hsnode *pnext;
}HSNode_t;extern int insert_hashtable(HSDataTYpe data);
extern void printf_hash();
extern HSNode_t *find_hash(char *name);extern int pop_hash();extern void destory();
#endif

二、算法

1、算法的设计
  

1.正确性，
        语法正确
        合法的输入能得到合理的结果。
        对非法的输入，给出满足要求的规格说明
        对精心选择，甚至刁难的测试都能正常运行，结果正确
    2. 可读性，便于交流，阅读，理解    高内聚 低耦合
    3. 健壮性，输入非法数据，能进行相应的处理，而不是产生异常
    4. 高效率(时间复杂度)
    5. 低存储（空间复杂度）

2、算法时间复杂度
      

 执行这个算法所花时间的度量
  将数据量增长和时间增长用函数表示出来，这个函数就叫做时间复杂度。
        一般用大O表示法：O（n）-----时间复杂度是关于数据n的一个函数
        随着n的增加，时间复杂度增长较慢的算法时间复杂度低
    时间复杂度的计算规则
        1，用常数1 取代运行时间中的所有加法常数
        2，在修改后的运行函数中，只保留最高阶项。
        3，如果最高阶存在且系数不是1，则去除这个项相乘的常数。

3、排序算法

1、插入排序

思想：将数组分为已排序区间和未排序区间，初始已排序区间只有一个元素，就是数组的第一个元素。然后，每次从未排序区间中取出第一个元素，在已排序区间中找到相应的位置并插入。

特点：

• 在小规模数据集上，插入排序的性能接近线性排序。
• 时间复杂度在最好情况下为O(n)，最坏情况下为O(n^2)。
• 插入排序是稳定的排序算法。
• 不需要额外的存储空间，也是原地排序

   void InsertionSort(int *a,int len)
  {int i,j;for(i=1;i<len;++i){j= i;int t = *(a+i);while(j>0 && (*(a+j-1))>t){*(a+j) = *(a+j-1);--j;}*(a+j) = t;}}
  

   

2、选择排序

思想：遍历数组，每次从未排序的部分找到最小（或最大）的元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

特点：

• 时间复杂度为O(n^2)，其中n是数组的长度。
• 不稳定排序（即相等的元素可能在排序后的序列中改变相对位置）。
• 不需要额外的存储空间，原地排序。

• void choiceSort(int *a, int len)
  {int i,j; for(i=0;i<len;++i){for(j=i+1;j<len;++j){if(*(a+i) >*(a+j)){swap(a+i,a+j);}}}
  }
  

                               

3、冒泡排序

思想：通过重复遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的，直到没有再需要交换的元素为止，这表示该数列已经排序完成。

特点：

• 时间复杂度也是O(n^2)。
• 也是一种原地排序，且是稳定的排序算法

• void BubbleSort(int *a,int len)
  {int i,j;for(j=len-1;j>0;--j){for(i=0;i<j;++i){if(*(a+i) > *(a+i+1)){swap(a+i,a+i+1);}}}
  }

                                                                                                                                                                    

4、快速排序

基本思想为：任取待排序元素序列中的某元素作为基准值（pivot），按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。快速排序采用了分治的思想，将一个大问题转化为若干个小问题，然后逐个解决每个小问题，最终达到解决问题的目的。

void qSort(int *begin , int *end)
{if(begin >= end){return ;}int t = *begin;int *p = begin;int *q = end;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);
}

5、二分查找

• 优点：
  • 效率高：二分查找的时间复杂度为O(log n)，在处理大数据集时非常高效。
  • 适用范围广：只要数组（或类似的数据结构）是有序的，就可以使用二分查找算法来快速定位元素。
  • 稳定性好：二分查找的性能不会受到输入数据分布的影响。
  • 空间复杂度低：不需要额外的存储空间。
• 缺点：
  • 要求有序数组：如果数组无序，则需要先进行排序操作，这可能会增加额外的时间开销。
  • 插入和删除操作效率低：二分查找在查找操作上非常高效，但如果需要在数组中频繁地进行插入和删除操作，则二分查找可能不是最佳选择。
  • 不适用于非数组数据结构：二分查找主要适用于数组或类似数组的数据结构。
  • 边界条件处理复杂：在实现二分查找时，需要正确处理各种边界条件，这可能会使代码变得复杂且容易出错。

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(*(a+mid) < n){begin = mid +1;}else if(*(a+mid) > n){end = mid -1;}else{return a+mid;}}return NULL;
}