数据结构（5）

一、队列

        我们把可以从一端进行数据的插入，另一端进行数据的删除的线性存储结构叫做队列。

        我们把插入数据操作叫做入队，插入端为队尾，把删除操作叫做出队，在队头。

        队列的最大存储特点就是先入先出即：FIFO，可以应用在数据的缓存。

（1）顺序队列

使用顺序表排列的队列为顺序队列。

        顺序队列存在假溢出问题：即当数据的头不在队列的两端，存储数据会发生空间不足的情况，事实上队列空间被没有被完全利用。解决上述问题的办法为：使用顺序队列，即存储数据到一端时，会折返至另一端继续存储，存储至队列空间-1个时结束。这是因为循环队列为了区分队列的判空和判满。

  pbase 为首元素地址（基地址），head 为头角标， tail 为为角标；

        判空时：队头和队尾在同一位置时：

        判满时：当队尾数据+1跟上队头数据时；

顺序队列的行为：

1.创建

Seqque_t *create_seqque()
{Seqque_t *psq = malloc(sizeof(Seqque_t));if (NULL == psq){printf("malloc error\n");return NULL;}psq->head = 0;psq->tail = 0;psq->pbase = malloc(sizeof(Data_type_t) * SEQQUE_MAX_LEN);if (NULL == psq->pbase){printf("malloc error\n");return NULL;}return psq;
}

2.判空、判满和遍历

int is_full_seqque(Seqque_t *psq)
{if ((psq->tail+1)%SEQQUE_MAX_LEN == psq->head){return 1;}return 0;
}int is_empty_seqque(Seqque_t *psq)
{if (psq->head == psq->tail){return 1;}return 0;
}void seqque_for_each(Seqque_t *psq)
{for (int i = psq->head; i != psq->tail; i = (i+1)%SEQQUE_MAX_LEN){printf("%d ", psq->pbase[i]);}printf("\n");
}

3.入队

int push_seqque(Seqque_t *psq, Data_type_t data)
{if (is_full_seqque(psq)){printf("seqque is full\n");return -1;}psq->pbase[psq->tail] = data;psq->tail = (psq->tail+1) % SEQQUE_MAX_LEN;return 0;
}

4.出队

int pop_seqque(Seqque_t *psq, Data_type_t *data)
{if(is_empty_seqque(psq) || NULL == data) {printf("error!");return -1;}*data = psq->pbase[psq->head];printf("\n");psq->head = (psq->head + 1) % SEQQUE_MAX_LEN;  return *data;
}

5.查找

int find_seqque(Seqque_t *psq, Data_type_t *data)
{if(is_empty_seqque(psq)){printf("error!");return -1;}if(data != NULL){*data = psq->pbase[psq->head];}return *data;
}

6.销毁

void destory_seqque(Seqque_t **psq)
{free((*psq)->pbase);free(*psq);*psq = NULL;
}

（2）链式队列

        链式队列与顺序队列类似，只不过队列其中元素不是连续的，上一个元素保留着下一个元素的地址；

        pfront 为首元素地址，prear为尾元素地址，clen为元素个数；data为链表存储的数据，pnext为下一结点的地址。

链式对列的行为：

1.创建

LQueue_t *create_queue()
{LQueue_t *ptmp = malloc(sizeof(LQueue_t));if(NULL == ptmp){printf("malloc error!\n");return NULL;}ptmp->phead = NULL;ptmp->ptail = NULL;ptmp->clen = 0;return ptmp;
}

2.判空和遍历

3.入队

​int insert_lqlink(LQueue_t *pqlink, Data_type_t data)
{if(NULL == pqlink){printf("error\n");return -1;}LQNode_t *ptmp = malloc(sizeof(LQNode_t));if(NULL == ptmp){printf("malloc error\n");return -1;}ptmp->data = data;ptmp->pnext = NULL;if(NULL == pqlink->phead){pqlink->phead = ptmp;  pqlink->ptail = ptmp;pqlink->clen++;return 0;}else{pqlink->ptail->pnext = ptmp;pqlink->ptail = ptmp;pqlink->clen++;}return 0;
}

4.出队

int delete_pqlink(LQueue_t *pqlink, Data_type_t *data)
{if(data != NULL){if(is_empty_pqlink(pqlink)){return -1;}LQNode_t *pdel = pqlink->phead;pqlink->phead = pdel->pnext;if (data != NULL){*data = pdel->data;}free(pdel);if (NULL == pqlink->phead){pqlink->ptail = NULL;}pqlink->clen--;}return 0;
}

5.查找

int find_pqlink(LQueue_t *pqlink, Data_type_t *data)
{if(is_empty_pqlink(pqlink)){printf("error!\n");return -1;}else{if(data != NULL){*data = pqlink->phead->data;}return *data;}}

6.销毁

void destroy_pqlink(LQueue_t **pqlink)
{if(is_empty_pqlink(*pqlink)){printf("error\n");return ;}while(!is_empty_pqlink(*pqlink)){Data_type_t data;delete_pqlink(*pqlink, &data);}free(*pqlink);*pqlink = NULL;      }

二、哈希表

        哈希表（Hash Table），也称为散列表，是一种高效的数据结构，它通过哈希函数将键（Key）映射到对应的值（Value）的存储位置，从而实现快速的插入、删除和查找操作，平均时间复杂度接近 O (1)。

        哈希函数：将要存储的数据的关键字和存储位置之间建立起对应关系，这个关系称之为哈希函数。存储数据时，通过对应的哈希函数可以将数据映射到指定位置，查找时，仍可以将根据数据找到存储位置。

        哈希冲突（哈希矛盾）：当两个不同的键通过哈希函数计算得到相同的哈希值时，就会发生哈希冲突。即 key1 ！= key 2  ，f（key1） ==  f（key2） 由于哈希表的底层存储通常是固定大小的数组，冲突无法完全避免。解决办法有：

        （1）开放地址法：找到指定位置，顺位向下存储至下一空位；

        （2）链地址法：哈希表内不存储数据，申请结点存储进去（保存该链表首地址）；

哈希表的行为：

1.创建

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_TABLE_MAX_SIZE-1;}
}

2.插入

int insert_hash_table(HSNode_t **hash_table, Data_type_t data)
{int addr = hash_function(data.name[0]);if(addr < 0 || addr > 27){return -1;}HSNode_t *pnode =  malloc(sizeof(HSNode_t));if( NULL == pnode){printf("malloc error!\n");return -1;}if(hash_table[addr] == NULL){pnode->data =data;hash_table[addr] = pnode;pnode->pnext = NULL;}else{pnode->data =data;pnode->pnext = hash_table[addr];hash_table[addr] = pnode;}return 0;
}

3.查找首元素

HSNode_t *find_hash(HSNode_t **hash_table, char *name)
{int addr = hash_function(name[0]);HSNode_t *ptmp = hash_table[addr];while(ptmp){if(0 == strcmp(name, ptmp->data.name)){return ptmp;}ptmp = ptmp->pnext;}return NULL;
}

4.销毁

void destroy_hash_table(HSNode_t **hash_table)
{for(int i = 0; i < HASH_TABLE_MAX_SIZE; ++i){HSNode_t *pdel = hash_table[i];while(hash_table[i] != NULL){hash_table[i] = pdel->pnext;free(pdel);pdel = hash_table[i];}}
}

5.遍历

void go_for_each_hash(HSNode_t *hash_table[HASH_TABLE_MAX_SIZE])
{int i = 0;for(; i < HASH_TABLE_MAX_SIZE; ++i){if(hash_table != NULL){HSNode_t *ptmp = hash_table[i];while(ptmp != NULL){printf("%s\n %s\n",ptmp->data.name, ptmp->data.tel);ptmp = ptmp->pnext;}}}
}