数据结构（5） 循环列表，哈希表

顺序队列会假溢出故移入循环队列循环队列与顺序队列思想相同都是顺序存储预先分配数组空间循环队列1. 空队列队头和队尾在同一位置为了与队空的判别条件进行区分数据存储时会故意留下一格不存数据2. 满队列队列少存储一个数据当队尾1跟上队头sysqueue.h#ifndef __SYSQUEUE_H__ #define __SYSQUEUE_H__ typedef int DataType_t; typedef struct sque { DataType_t *pbase; int head; int tail; } SQueue_t; #define MAX_QUEUE_LEN 10 extern SQueue_t *create_sysqueue(); extern int is_full_sysqueue(SQueue_t *psque); extern int is_empty_sysqueue(SQueue_t *psque); extern int push_sysqueue(SQueue_t *psque,DataType_t data); extern void show_sysqueue(SQueue_t *psque); extern int pop_sysqueue(SQueue_t *psque,DataType_t *pdata); extern void clear_sysqueue(SQueue_t *psque); extern void destiry_sysqueue(SQueue_t **ppsque); #endifsysqueue.c#include sysqueue.h #include stdio.h #include stdlib.h //创建循环队列 SQueue_t *create_sysqueue() { SQueue_t *psque malloc(sizeof(SQueue_t)); if(NULLpsque) { printf(malloc error\n); return NULL; } psque-pbasemalloc(sizeof(DataType_t)*MAX_QUEUE_LEN); if(NULLpsque-pbase) { printf(malloc error\n); return NULL; } psque-head0; psque-tail0; return psque; } //判满 int is_full_sysqueue(SQueue_t *psque) { if(((psque-tail1)%MAX_QUEUE_LEN)psque-head) { return 1; } return 0; } //判空 int is_empty_sysqueue(SQueue_t *psque) { if(psque-headpsque-tail) { return 1; } return 0; } //入队 int push_sysqueue(SQueue_t *psque,DataType_t data) { if(is_full_sysqueue(psque)) { return -1; } // *(psque-pbasepsque-tail)data; psque-pbase[psque-tail]data; // if(psque-tailMAX_QUEUE_LEN) // { // psque-tail0; // } // else // { // psque-tail; // } psque-tail((psque-tail1)%MAX_QUEUE_LEN); return 0; } //遍历 void show_sysqueue(SQueue_t *psque) { for(int ipsque-head;i!psque-tail;i(i1)%MAX_QUEUE_LEN) { printf(%d ,psque-pbase[i]); } printf(\n); } //出队 int pop_sysqueue(SQueue_t *psque,DataType_t *pdata) { if(is_empty_sysqueue(psque)) { return -1; } if(pdata!NULL) { *pdatapsque-pbase[psque-head]; } psque-head(psque-head1)%MAX_QUEUE_LEN; return 0; } //置空循环队列 void clear_sysqueue(SQueue_t *psque) { psque-headpsque-tail0; } //销毁 void destiry_sysqueue(SQueue_t **ppsque) { free((*ppsque)-pbase); free(*ppsque); *ppsqueNULL; }main.c#include sysqueue.h #include stdio.h int main(int argc, char **argv) { SQueue_t *psquecreate_sysqueue(); DataType_t data; if(NULLpsque) { return -1; } push_sysqueue(psque, 1); push_sysqueue(psque, 2); push_sysqueue(psque, 3); push_sysqueue(psque, 4); push_sysqueue(psque, 5); show_sysqueue(psque); int retpop_sysqueue(psque, data); if(!ret) { printf(pop_data %d\n,data); } push_sysqueue(psque, 6); show_sysqueue(psque); clear_sysqueue(psque); destiry_sysqueue(psque); return 0; }哈希表哈希存储散列存储将要存储数据的关键字和数据存储位置值之间建立起对应的函数关系当数据存储时根据该关系映射数据的存储位置查找数据时利用该函数关系运算出数据的存储位置。目的为了快速检索数据哈希冲突/哈希矛盾解决哈希冲突的方法:1. 开放定址法闭散列冲突后在表内另找空闲位置不额外开辟空间。线性探测往后逐个找空位缺点易产生聚集。二次探测按二次步长寻址缓解聚集。随机探测随机选下一个地址。2. 链地址法开散列 / 拉链法哈希表每个位置存链表冲突元素直接挂在对应链表尾部。优点实现简单、无聚集、删除方便。工程最常用Java HashMap、Redis 字典均使用。hash.h#ifndef __HASH_H__ #define __HASH_H__ typedef struct info { char name[32]; char tel[16]; }DataType_t; typedef struct node { DataType_t data; struct node *pnext; }HSnode_t; #define HASH_MAX_SIZE 27 extern int insert_hash_table(HSnode_t *hash_table[],DataType_t data); extern void show_hash_table(HSnode_t *hash_table[]); extern HSnode_t *find_hash_table(HSnode_t **hash_table,char *name); extern void destory_hash(HSnode_t **hash_table); #endifhash.c#include hash.h #include stdio.h #include stdlib.h #include string.h //哈希函数 int hash_function(char key) { if(keyakeyz) { return key-a; } else if(keyAkeyZ) { return key-A; } else { return HASH_MAX_SIZE-1; } } //创建哈希表 int insert_hash_table(HSnode_t *hash_table[],DataType_t data) { HSnode_t *pnodemalloc(sizeof(HSnode_t)); if(NULLpnode) { printf(malloc error\n); return -1; } pnode-datadata; pnode-pnextNULL; int addrhash_function(data.name[0]); pnode-pnexthash_table[addr]; hash_table[addr]pnode; return 0; } //遍历 void show_hash_table(HSnode_t *hash_table[]) { for(int i0;iHASH_MAX_SIZE;i) { HSnode_t *phash_table[i]; while(p!NULL) { printf(%s : %s\n,p-data.name,p-data.tel); pp-pnext; } printf(\n); } } //查找 //*hash_table[] 等价于 **hash_table HSnode_t *find_hash_table(HSnode_t **hash_table,char *name) { int addrhash_function(name[0]); HSnode_t *phash_table[addr]; while(p!NULL) { if(0strcmp(p-data.name,name)) { return p; } pp-pnext; } return NULL; } //销毁 void destory_hash(HSnode_t **hash_table) { for(int i0;iHASH_MAX_SIZE;i) { HSnode_t *phash_table[i]; while(p!NULL) { hash_table[i]p-pnext; free(p); phash_table[i]; } } }main.c#include hash.h #include stdio.h int main(int argc, char **argv) { HSnode_t *hash_table[HASH_MAX_SIZE]{NULL}; DataType_t pers[]{{zhangsan,110},{lisi,112}, {wanger,120},{zhaowu,119},{maliu,10086}}; insert_hash_table(hash_table,pers[0]); insert_hash_table(hash_table,pers[1]); insert_hash_table(hash_table,pers[2]); insert_hash_table(hash_table,pers[3]); insert_hash_table(hash_table,pers[4]); show_hash_table(hash_table); HSnode_t *pfind_hash_table(hash_table, maliu); printf(find:%s ,%s\n,p-data.name,p-data.tel); destory_hash(hash_table); return 0; }