本文介绍: 【代码】数据结构与算法 – 查找。
文章目录
第1关:实现折半查找
代码如下:
/*************************************************************
date: April 2009
copyright: Zhu En
DO NOT distribute this code.
**************************************************************/
//折半查找的顺序表 实现文件
//每个结点的数据是关键码
//
#include <stdio.h>
#include <stdlib.h>
#include "BSlist.h"
BSeqList* BSL_Create(int size)
//创建一个顺序表
//与BSL_Free()配对
{
BSeqList* blist=(BSeqList*)malloc(sizeof(BSeqList));
blist->pkey = (int*)malloc(sizeof(int)*size);
blist->max=size;
blist->len=0;
return blist;
}
void BSL_Free(BSeqList* blist)
//释放/删除顺序表
//与BSL_Create()配对
{
free(blist->pkey);
free(blist);
}
int BSL_FindKey(BSeqList* blist, int key)
//在排序的顺序表中查找关键码值为key的结点,返回结点的编号
//返回值大于等于0时表示找到值为key的结点的编号,-1表示没有找到
{
/*请在BEGIN和END之间实现你的代码*/
/*****BEGIN*****/
int k = 0;
int r = blist->len - 1;
while (k <= r) {
int m = (k + r) / 2;
if (key == blist->pkey[m]) {
return m;
} else if (key < blist->pkey[m]) {
r = m - 1;
} else {
k = m + 1;
}
}
return -1;
/******END******/
/*请不要修改[BEGIN,END]区域外的代码*/
}
int BSL_InsKey(BSeqList* blist, int key)
//在排序的顺序表中插入一个值为key的结点
//返回值大于等于0时表示插入的位置, -1表示表满(无法插入)
{
if (blist->len>=blist->max) return -1;
int k, r, m;
k=0; r=blist->len-1;
//寻找插入位置
while (k<=r) {
m=(k+r)>>1; //m=(k+r)/2
if (key == blist->pkey[m]) return -2;若不允许插入已存在的值,则需要此行
if (key<blist->pkey[m]) r=m-1;
else k=m+1;
}
//插入位置为k, 腾出k号位置
for (r=blist->len; r>k; r--)
blist->pkey[r]=blist->pkey[r-1];
//key放入k号位置
blist->pkey[k]=key;
blist->len++;
return k;
}
int BSL_DelKey(BSeqList* blist, int key)
//在排序的顺序表中删除值为key的结点,
//存在值为x的结点则返回结点编号, 未找到返回-1
{
int k=BSL_FindKey(blist, key);
if (k<0) return -1;
int i=k;
while(i < blist->len-1) {
blist->pkey[i] = blist->pkey[i+1];
i++;
}
blist->len --;
return k;
}
void BSL_Print(BSeqList* blist)
//打印整个顺序表
{
if (blist->len==0) {
printf("The list is empty.n");
return;
}
printf("The list contains: ");
for (int i=0; i<blist->len; i++) {
printf("%d ", blist->pkey[i]);
}
printf("n");
}
第2关:实现散列查找
代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "indLnkHash.h"
LHTable* ILH_Create(int n)
//创建散列表, n为表长度,最佳取值:n取小于等于数据个数的最大质数
{
HNode* pn=(HNode*)malloc(sizeof(HNode)*n);
for (int i=0; i<n; i++) {
pn[i].key=0;
pn[i].next=NULL;
}
LHTable* pt=(LHTable*)malloc(sizeof(LHTable));
pt-> pn=pn;
pt->n=n;
return pt;
}
void ILH_Free(LHTable* pt)
//释放散列表
{
if (pt==NULL) return;
for (int i=0; i<pt->n; i++) {
HNode* curr=pt->pn[i].next;
while (curr) {
HNode* next=curr->next;
free(curr);
curr=next;
}
}
free(pt->pn);
free(pt);
}
bool ILH_InsKey(LHTable* pt, int x)
//插入关键码x
//返回true,表示插入成功
//返回false,表示插入失败(关键码已经存在)
{
/*请在BEGIN和END之间实现你的代码*/
/*****BEGIN*****/
int d=x%pt->n;
if (pt->pn[d].key==0) {
pt->pn[d].key=x;
return true;
}
else if (pt->pn[d].key==x)
return false;
HNode* prev=&(pt->pn[d]);
HNode* curr=pt->pn[d].next;
while (curr && curr->key!=x) {prev=curr; curr=curr->next;}
if (curr) return false;
HNode* pnode=(HNode*)malloc(sizeof(HNode));
pnode->key=x;
pnode->next=NULL;//pt->pn[d].next;
prev->next=pnode;
return true;
/******END******/
/*请不要修改[BEGIN,END]区域外的代码*/
}
bool ILH_FindKey(LHTable* pt, int x)
//查找关键码x
//返回true表示找到
//返回false表示没找到
{
int d=x%pt->n;
if (pt->pn[d].key==0) {
return false;
}
else if (pt->pn[d].key==x)
return true;
HNode* curr=pt->pn[d].next;
while (curr && curr->key!=x) curr=curr->next;
if (curr) return true;
else return false;
}
bool ILH_DelKey(LHTable* pt, int x)
//删除关键码
//返回true表示该关键码存在,且成功删除
//返回false表示该关键码不存在
{
/*请在BEGIN和END之间实现你的代码*/
/*****BEGIN*****/
int d=x%pt->n;//关键码x的散列值d
if (pt->pn[d].key==0) {
return false;
}
else if (pt->pn[d].key==x) {
if (pt->pn[d].next ==NULL)
pt->pn[d].key=0;
else {
HNode* first=pt->pn[d].next;
pt->pn[d].key=first->key;
pt->pn[d].next=first->next;
free(first);
}
return true;
}
HNode* prev=&(pt->pn[d]);
HNode* curr=pt->pn[d].next;
while (curr && curr->key!=x) {prev=curr; curr=curr->next;}
if (curr==NULL) return false;
prev->next=curr->next;
free(curr);
return true;
/******END******/
/*请不要修改[BEGIN,END]区域外的代码*/
}
void ILH_Print(LHTable *pt)
{
for (int i=0; i<pt->n; i++) {
printf("%5d:", i);
if (pt->pn[i].key) {
printf("%d", pt->pn[i].key);
HNode* curr=pt->pn[i].next;
while (curr) {
printf("->%d", curr->key);
curr=curr->next;
}
printf("n");
}
else
printf("-n");
}
}
原文地址:https://blog.csdn.net/2301_77225918/article/details/135302244
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_52628.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。