《数据结构（C语言版）第二版》第七章-查找（算法设计题）

2024-09-05 15:20
文章标签 算法 设计 数据结构 查找 第二 语言版 第七章

本文主要是介绍《数据结构（C语言版）第二版》第七章-查找（算法设计题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

习题1

试写出折半查找的递归算法。

#include <stdio.h>
#include <stdlib.h>#define Maxsize 100typedef int KeyType;
typedef char InfoType;typedef struct
{KeyType Key;InfoType OtherInfo;
}elem;typedef struct
{elem *R;int length;
}SSTable;void initSSTable(SSTable& ST);
int Search_Bin(SSTable ST, KeyType key, int low, int high);int main()
{SSTable ST = { NULL,0 };int i = 0;KeyType key = 0;int r = 0;char choice = '\0';initSSTable(ST);printf("请输入递增有序表中元素的个数：");scanf_s(" %d", &ST.length);for (i = 1; i <= ST.length; i++){printf("请输入第%d个元素的值：", i);scanf_s(" %d", &ST.R[i].Key);}while (1){printf("\n请输入要查找到数：");scanf_s(" %d", &key);r = Search_Bin(ST, key, 1, ST.length);if (r == -1){printf("%d查找失败。\n",key);}else{printf("%d的位置为：%d\n", key, r);}printf("是否继续？（y/Y）");scanf_s(" %c", &choice);if (choice != 'y' && choice != 'Y'){break;}}return 0;
}void initSSTable(SSTable& ST)
{ST.R = (elem*)malloc(sizeof(elem)* Maxsize);ST.length = 0;
}//折半查找 递归
int Search_Bin(SSTable ST, KeyType key, int low, int high)
{if (low > high){return -1;}int mid = (low + high) / 2;if (key == ST.R[mid].Key){return mid;}else if (key > ST.R[mid].Key){return Search_Bin(ST, key, mid + 1, high);}else{return Search_Bin(ST, key, low, mid - 1);}
}

在这里插入图片描述

习题2

试写一个判别给定二叉树是否为二叉排序树的算法。

#include <stdio.h>
#include <stdlib.h>typedef int KeyType;
typedef char InfoType;typedef struct 
{KeyType Key;InfoType OtherInfo;
}ElemType;typedef struct BTNode
{ElemType data;struct BTNode* lchild;struct BTNode* rchild;
}BTNode,* BTree;#define true 1
#define false 0bool flag = true; //全局变量，初值为true. 若非二叉排序树，则置flag为false.
BTree pre = NULL; void initTree(BTree& T);
void CreateTree(BTree& T);
void JudgeBSTree(BTree T, bool& flag);int main()
{BTree T = NULL;initTree(T);CreateTree(T);JudgeBSTree(T, flag);if (flag == 1){printf("该二叉树为排序二叉树。\n");}else{printf("该二叉树为非排序二叉树。\n");}return 0;
}void initTree(BTree& T)
{T = NULL;
}//创建普通二叉树
void CreateTree(BTree& T)
{ElemType e = { 0,'\0' };printf("请输入结点的关键字域值（结点不存在时，输入0）：");scanf_s(" %d", &e.Key);if (e.Key == 0){T = NULL;}else if (e.Key != 0){T = (BTree)malloc(sizeof(BTNode));T->data = e;CreateTree(T->lchild);CreateTree(T->rchild);}
}//中序遍历输入的二叉树，判断是否递增
void JudgeBSTree(BTree T, bool& flag)
{if (T && flag){JudgeBSTree(T->lchild, flag);//就是将原来中序遍历输出根结点的命令，替换为将该根结点值与其前一个值相比较if (pre == NULL){pre = T;   //pre只有在中序遍历到第一个结点时为空，后面的结点都不为空。而第一个结点不必判断。}else if (pre->data.Key < T->data.Key)  //每一个中序遍历的结点值T->data.Key都需要比前面一个结点值pre->data.Key大{pre = T;}else{flag = false;}JudgeBSTree(T->rchild, flag);}
}

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

//中序遍历输入的二叉树，判断是否递增
void JudgeBSTree(BTree T, bool &flag)
{if (T){printf("\n\n【a】T->data.Key = %d", T->data.Key);if (T->lchild){printf("\n【a】T->lchild->data.Key = %d", T->lchild->data.Key);}else{printf("\n【a】T->lchild->data.Key = #");}if (T->rchild){printf("\n【a】T->rchild->data.Key = %d", T->rchild->data.Key);}else{printf("\n【a】T->rchild->data.Key = #");}}else{printf("\n\n【a】T->data.Key = #");}if (T){printf("\n【1】开始 T = %d\n", T->data.Key);}else{printf("\n【1】开始 T = #\n");}if (T && flag){if (T->lchild){printf("\n【2】开始%d->lchild = %d \n", T->data.Key, T->lchild->data.Key);}else{printf("\n【2】开始%d->lchild = # \n ", T->data.Key);}JudgeBSTree(T->lchild,flag);if (T->lchild){printf("\n【3】%d->lchild = %d 结束\n", T->data.Key, T->lchild->data.Key);}else{printf("\n【3】%d->lchild = # 结束\n ", T->data.Key);}if (pre){printf("\n\n【b】pre->data.Key = %d \n", pre->data.Key);}else{printf("\n\n【b】pre->data.Key = # \n");}//就是将原来中序遍历输出根结点的命令，替换为将该根结点值与其前一个值相比较if (pre == NULL){pre = T;  //pre只有在中序遍历到第一个结点时为空，后面的结点都不为空。而第一个结点不必判断。}else if(pre->data.Key < T->data.Key)  //每一个中序遍历的结点值T->data.Key都需要比前面一个结点值pre->data.Key大{pre = T;}else {flag = false;}if (T->rchild){printf("\n【4】开始%d->rchild = %d \n", T->data.Key, T->rchild->data.Key);}else{printf("\n【4】开始%d->rchild = # \n ", T->data.Key);}JudgeBSTree(T->rchild, flag);if (T->rchild){printf("\n【5】%d->rchild = %d 结束\n", T->data.Key, T->rchild->data.Key);}else{printf("\n【5】%d->rchild = # 结束\n ", T->data.Key);}}if (T){printf("\n【6】T = %d 结束 \n", T->data.Key);}else{printf("\n【6】T = # 结束\n");}}

习题3

已知二叉排序树采用二叉链表存储结构，根结点的指针为 T, 链结点的结构为 (lchild,data, rchild) , 其中lchild、rchild分别指向该结点左、右孩子的指针，data域存放结点的数据信息。
请写出递归算法，从小到大输出二叉排序树中所有数据值 ≥ x 的结点的数据。要求先找到第一个满足条件的结点后，再依次输出其他满足条件的结点。

【在中序遍历时判断】

#include <stdio.h>
#include <stdlib.h>#define ENDFLAG -1 //自定义常量，作为输入结束标志typedef int KeyType;
typedef char InfoType;//二叉排序树的二叉链表存储表示
typedef struct
{KeyType Key;InfoType otherinfo;
}ElemType;typedef struct BSTNode
{ElemType data;struct BSTNode* lchild;struct BSTNode* rchild;
}BSTNode, * BSTree;void InitBiTree(BSTree& T);
void InsertBST(BSTree& T, ElemType e);
void CreateBST(BSTree& T);
void preOrderTraverse(BSTree T);
void InOrderTraverse(BSTree T);
void posOrderTraverse(BSTree T);
void Judge_x(BSTree T, int x);int main()
{BSTree T = NULL;InitBiTree(T);CreateBST(T);printf("\n二叉排序树链表的先序序列为： ");preOrderTraverse(T);printf("\n二叉排序树链表的中序序列为： ");InOrderTraverse(T);printf("\n二叉排序树链表的后序序列为： ");posOrderTraverse(T);printf("\n≥50的关键字为：");Judge_x(T, 50);return 0;
}//初始化二叉排序树
void InitBiTree(BSTree& T)
{T = NULL;
}//算法 7.5 二叉排序树的插入
//前提：当二叉排序树T中不存在关键字等于e.key的数据元素时， 则插入该元素
void InsertBST(BSTree& T, ElemType e)
{if (!T){BSTree S = (BSTree)malloc(sizeof(BSTNode));S->data = e;S->lchild = NULL;S->rchild = NULL;T = S; //把新结点*S链接到已找到的插入位置}else if (e.Key < T->data.Key){InsertBST(T->lchild, e);}else if (e.Key > T->data.Key){InsertBST(T->rchild, e);}else{printf("当二叉排序树T中存在关键字等于%d的结点，无法插入。\n", e.Key);return;}
}//算法7.6 二叉排序树的创建（在插入操作的基础上，且是从空的二叉排序树开始的）
//依次读人一个关键字为key的结点， 将此结点插人二叉排序树T中
void CreateBST(BSTree& T)
{InitBiTree(T);ElemType e = { 0,'\0' };printf("请输入新结点的关键字key值：");scanf_s(" %d", &e.Key);while (e.Key != ENDFLAG)  //ENDFLAG为自定义常量-1，作为输入结束标志{InsertBST(T, e);e = { 0,'\0' };printf("请输入新结点的关键字key值：");scanf_s(" %d", &e.Key);}
}//先序递归遍历二叉排序树
void preOrderTraverse(BSTree T)
{if (T)  //只有当T不为空时才访问它的成员{printf(" %d", T->data.Key);preOrderTraverse(T->lchild);preOrderTraverse(T->rchild);}
}//中序递归遍历二叉排序树
void InOrderTraverse(BSTree T)
{if (T){InOrderTraverse(T->lchild);printf(" %d", T->data.Key);InOrderTraverse(T->rchild);}
}//后序递归遍历二叉排序树
void posOrderTraverse(BSTree T)
{if (T){posOrderTraverse(T->lchild);posOrderTraverse(T->rchild);printf(" %d", T->data.Key);}
}//输出大于等于x的关键字
void Judge_x(BSTree T, int x)
{if (T){Judge_x(T->lchild, x);if (T->data.Key >= x){printf("%d ", T->data.Key);}Judge_x(T->rchild, x);}
}

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

习题4

已知二叉树T的结点形式为(llink,data, count, rlink), 在树中查找值为X的结点，若找到， 则记数(count)加1; 否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。

#include <stdio.h>
#include <stdlib.h>#define ENDFLAG -1 //自定义常量，作为输入结束标志typedef int KeyType;
typedef char InfoType;//二叉排序树的二叉链表存储表示
typedef struct
{KeyType Key;InfoType otherinfo;
}ElemType;typedef struct BSTNode
{ElemType data;int count;struct BSTNode* lchild;struct BSTNode* rchild;
}BSTNode, * BSTree;void InitBiTree(BSTree& T);
void InsertBST(BSTree& T, KeyType e);
void CreateBST(BSTree& T);
void preOrderTraverse(BSTree T);
void InOrderTraverse(BSTree T);
void posOrderTraverse(BSTree T);
void SearchBSTree(BSTree& T, KeyType e);int main()
{BSTree T = NULL;KeyType KEY = 0;char choice = '\0';InitBiTree(T);CreateBST(T);printf("\n二叉排序树链表的先序序列为： ");preOrderTraverse(T);printf("\n二叉排序树链表的中序序列为： ");InOrderTraverse(T);printf("\n二叉排序树链表的后序序列为： ");posOrderTraverse(T);while (1){printf("\n\n请输入要查找的关键字值：");scanf_s(" %d", &KEY);SearchBSTree(T, KEY);printf("\n二叉排序树链表的先序序列为： ");preOrderTraverse(T);printf("\n二叉排序树链表的中序序列为： ");InOrderTraverse(T);printf("\n二叉排序树链表的后序序列为： ");posOrderTraverse(T);printf("\n是否继续？（y/n）");scanf_s(" %c", &choice);if (choice != 'y' && choice != 'Y'){break;}}return 0;
}//初始化二叉排序树
void InitBiTree(BSTree& T)
{T = NULL;
}//二叉排序树的插入（非递归）
//二叉排序树T中不存在关键字等于key的数据元素时，插入该值.否则count++
void InsertBST(BSTree& T, KeyType e)
{BSTree f = NULL;BSTree q = T;BSTree S = (BSTree)malloc(sizeof(BSTNode));S->data.Key = e;S->count = 0;  //每查找成功了次数才加1，新建时次数为0S->lchild = NULL;S->rchild = NULL;if (!T) //T为空树{T = S;return;}//因为T可能为空树，所以不能把这种情况放在最前面if (T->data.Key == e){T->count++;free(S);S = NULL;return;}while (q && q->data.Key != e){f = q;if (q->data.Key > e){q = q->lchild;}else //if(q->data.Key < e){q = q->rchild;}}if (q){	q->count++;free(S);S = NULL;}else{q = S;//只知f是q的父节点，但是不清楚q是f的哪个子树if (f->data.Key > e){f->lchild = S;}else{f->rchild = S;}}
}//算法7.6 二叉排序树的创建（在插入操作的基础上，且是从空的二叉排序树开始的）
//依次读人一个关键字为key的结点， 将此结点插人二叉排序树T中
void CreateBST(BSTree& T)
{InitBiTree(T);KeyType Key = 0;printf("请输入新结点的关键字key值：");scanf_s(" %d", &Key);while (Key != ENDFLAG)  //ENDFLAG为自定义常量-1，作为输入结束标志{InsertBST(T, Key);printf("请输入新结点的关键字key值：");scanf_s(" %d", &Key);}
}//先序递归遍历二叉排序树
void preOrderTraverse(BSTree T)
{if (T)  //只有当T不为空时才访问它的成员{printf("\n Key = %d, count = %d ", T->data.Key, T->count);preOrderTraverse(T->lchild);preOrderTraverse(T->rchild);}
}//中序递归遍历二叉排序树
void InOrderTraverse(BSTree T)
{if (T){InOrderTraverse(T->lchild);printf("\n Key = %d, count = %d ", T->data.Key, T->count);InOrderTraverse(T->rchild);}
}//后序递归遍历二叉排序树
void posOrderTraverse(BSTree T)
{if (T){posOrderTraverse(T->lchild);posOrderTraverse(T->rchild);printf("\n Key = %d, count = %d ", T->data.Key, T->count);}
}//创建后的查找与插入(非递归)
void SearchBSTree(BSTree& T, KeyType e)
{if (!T){printf("二叉排序树为空，查找失败。\n");return;}BSTree p = T;BSTree f = NULL;if (T->data.Key == e){printf("%d查找成功。\n", e);T->count++;return;}while (p && p->data.Key != e){f = p;if (p->data.Key > e){p = p->lchild;}else{p = p->rchild;}}if (p) //说明找到了p->data.Key = e{p->count++;printf("%d查找成功。\n", e);}else{BSTree S = (BSTree)malloc(sizeof(BSTNode));S->data.Key = e;S->count = 0;S->lchild = NULL;S->rchild = NULL;p = S;if (e > f->data.Key){f->rchild = S;}else{f->lchild = S;}printf("%d查找失败，已插入。\n", e);}
}

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

习题5

假设一棵平衡二叉树的每个结点都标明了平衡因子b, 试设计一个算法，求平衡二叉树的高度。

#include <stdio.h>
#include <stdlib.h>#define ENDFLAG -1 //自定义常量，作为输入结束标志typedef int KeyType;
typedef char InfoType;//二叉排序树的二叉链表存储表示
typedef struct
{KeyType Key;InfoType otherinfo;
}ElemType;typedef struct BSTNode
{ElemType data;int bf;   //平衡因子(Balance Factor),struct BSTNode* lchild;struct BSTNode* rchild;
}BSTNode, * BSTree;void InitBiTree(BSTree& T);
void InsertBST(BSTree& T, KeyType e);
void CreateBST(BSTree& T);
void BF_BSTree(BSTree& T);
void preOrderTraverse(BSTree T);
void InOrderTraverse(BSTree T);
void posOrderTraverse(BSTree T);
int Height(BSTree T);
int Balance_Factor(BSTree T);
int Height_BF(BSTree T);int main()
{BSTree T = NULL;InitBiTree(T);CreateBST(T);BF_BSTree(T);printf("\n二叉排序树链表的先序序列为： ");preOrderTraverse(T);printf("\n二叉排序树链表的中序序列为： ");InOrderTraverse(T);printf("\n二叉排序树链表的后序序列为： ");posOrderTraverse(T);//假设已经平衡printf("\n\n该平衡二叉树的高度为：%d", Height_BF(T));return 0;
}//初始化二叉排序树
void InitBiTree(BSTree& T)
{T = NULL;
}//算法 7.5 二叉排序树的插入
//前提：当二叉排序树T中不存在关键字等于e.key的数据元素时， 则插入该元素
void InsertBST(BSTree& T, KeyType e)
{if (!T){BSTree S = (BSTree)malloc(sizeof(BSTNode));S->data.Key = e;S->bf = 0;S->lchild = NULL;S->rchild = NULL;T = S; //把新结点*S链接到已找到的插入位置}else if (e < T->data.Key){InsertBST(T->lchild, e);}else if (e > T->data.Key){InsertBST(T->rchild, e);}else{printf("当二叉排序树T中存在关键字等于%d的结点，无法插入。\n", e);return;}
}//算法7.6 二叉排序树的创建（在插入操作的基础上，且是从空的二叉排序树开始的）
//依次读人一个关键字为key的结点， 将此结点插人二叉排序树T中
void CreateBST(BSTree& T)
{InitBiTree(T);KeyType Key = 0;printf("请输入新结点的关键字key值：");scanf_s(" %d", &Key);while (Key != ENDFLAG)  //ENDFLAG为自定义常量-1，作为输入结束标志{InsertBST(T, Key);printf("请输入新结点的关键字key值：");scanf_s(" %d", &Key);}
}//全部创建完成后，根据中序遍历，求每个结点的平衡因子
void BF_BSTree(BSTree &T)
{if (T){BF_BSTree(T->lchild);T->bf = Balance_Factor(T);BF_BSTree(T->rchild);}
}//先序递归遍历二叉排序树
void preOrderTraverse(BSTree T)
{if (T)  //只有当T不为空时才访问它的成员{printf("\nKey = %d, bf = %d ", T->data.Key,T->bf);preOrderTraverse(T->lchild);preOrderTraverse(T->rchild);}
}//中序递归遍历二叉排序树
void InOrderTraverse(BSTree T)
{if (T){InOrderTraverse(T->lchild);printf("\nKey = %d, bf = %d ", T->data.Key, T->bf);InOrderTraverse(T->rchild);}
}//后序递归遍历二叉排序树
void posOrderTraverse(BSTree T)
{if (T){posOrderTraverse(T->lchild);posOrderTraverse(T->rchild);printf("\nKey = %d, bf = %d ", T->data.Key, T->bf);}
}//求高度
int Height(BSTree T)
{if (!T){return 0;}else{int m = Height(T->lchild);int n = Height(T->rchild);if (m > n){return m + 1;}else{return n + 1;}}
}//根据高度求平衡因子
int Balance_Factor(BSTree T)
{int left = Height(T->lchild);int right = Height(T->rchild);return left - right;
}//根据平衡二叉排序树的平衡因子求高度
//平衡二叉树，每个结点的平衡因子绝对值不超过1
int Height_BF(BSTree T)
{int level = 0;BSTree p = T;while (p){level++;if (p->bf < 0)  //p->bf == -1{p = p->rchild;}else //if(p->bf == 1 || p->bf == 0){p = p->lchild;}}return level;
}

在这里插入图片描述
在这里插入图片描述

习题6

分别写出在散列表中插入和删除关键字为K的一个记录的算法，设散列函数为H, 解决冲突的方法为链地址法。

//除留余数法构造散列函数，“链地址法”处理冲突#include <stdio.h>
#include <stdlib.h>
#include <math.h>#define m 13
#define NULLKEY 0typedef int KeyType;
typedef char InfoType;typedef struct KeyNode
{KeyType Key;InfoType OtherInfo;struct KeyNode* next;
}KeyNode;void CreateHash(KeyNode HT[]);
void Insert(KeyNode HT[], KeyType key);
int SearchHash(KeyNode HT[], KeyType key);
int H(KeyType key);
int maxPrimeNumber(int n);
int checkPrimeNumber(int n);
void Delete(KeyNode HT[], KeyType key);
void printHashTable(KeyNode HT[]);int main()
{KeyNode HT[m] = { 0 };KeyType k1 = 0;KeyType k2 = 0;char choice = '\0';CreateHash(HT);printHashTable(HT);while (1){printf("\n\n请输入要插入的数值：");scanf_s(" %d", &k1);Insert(HT, k1);printHashTable(HT);printf("\n\n请输入要删除的数值：");scanf_s(" %d", &k2);Delete(HT, k2);printHashTable(HT);printf("\n\n是否继续？（y/Y）");scanf_s(" %c", &choice);if (choice != 'y' && choice != 'Y'){break;}}return 0;
}//创建散列表
void CreateHash(KeyNode HT[])
{int i = 0;int KEY = 0;int flag = 0;for (i = 0; i < m; i++){HT[i].Key = NULLKEY;HT[i].next = NULL;}for (i = 1; i <= m; i++){printf("请输入第%d个关键字（结束时输入-1）：", i);scanf_s(" %d", &KEY);  //记录个数可以小于表长度if (KEY != -1){flag = SearchHash(HT, KEY);if (flag == -1){Insert(HT, KEY);}else{printf("该元素已存在，无法插入，请重新输入。\n");i--;}}else{break;}}if (i > m){printf("散列表已满。");return;}
}//散列表的查找
int SearchHash(KeyNode HT[], KeyType key)
{int	H0 = H(key);KeyNode* p = HT[H0].next;while (p != NULL){if (p->Key == key){return H0; //找见了}p = p->next;}return -1; //没找见
}//散列表的插入（链地址法处理冲突）
void Insert(KeyNode HT[], KeyType key)
{int H0 = H(key);KeyNode* p = HT[H0].next;while (p != NULL){if (p->Key == key){printf("该元素已存在，无法插入。\n");}p = p->next;}KeyNode* r = (KeyNode*)malloc(sizeof(KeyNode));r->Key = key;r->next = HT[H0].next;HT[H0].next = r;
}//散列函数
/* 采用除留余数法构造散列函数，选择p为小于表长m的最大质数 */
int H(KeyType key)
{int p = maxPrimeNumber(m);return key % p;
}//确定[0,n]范围内的最大质数
int maxPrimeNumber(int n)
{int i = 0;int status = checkPrimeNumber(0);int max = 0;for (i = 0; i <= n; i++){status = checkPrimeNumber(i);if (status){max = i;}}return max;
}//判断一个数是否是质数
int checkPrimeNumber(int n)
{int i = 0;int sq = floor(sqrt(n));if (n <= 1){return 0;}if (n == 2 || n == 3){return 1;}//只有6x-1和6x+1的数才有可能是质数（但不一定就是，如n=35，还需要继续判断）if (n % 6 != 1 && n % 6 != 5)   //n=4和n=6时，n%6满足该if条件，返回false，正好符合情况{return false;}/* 如果 i 是简单类型（int ，char)，在使用层面，i+=6 与 i=i+6 做的事是一样的，都是将 i 的值加了6，但生成的可执行代码不一样，且i+=6 与 i=i+6 运行的效率不同，i+=6 肯定更快。 *///只判断 该与6的倍数相邻的数n 能否被 其它不超过sq 且 也与6的倍数相邻的数i和i+2 整除// 同样因为“只有与6的倍数相邻的数才可能是质数”，所以用i和i+2来判断（i=5\11\17\23\29\35...  i+2=7\13\19\25\31\37...）。// 定理：如果一个数n不能整除 比它小的任何素数（比n小的全部素数一定都包含在i和i+2中），那么这个数n就是素数。for (i = 5; i <= sq; i+= 6){if (n % i == 0 || n % (i + 2) == 0)  {return 0;}}//此处for循环中，仍然找的是整数n的因数，所以仍然可以使用定理：如果一个数m不是质数，那么它必定有一个因子≤√m，另一个≥√m。所以i仍然判断到sq就可以。//真命题“如果数n存在一个大于√n的整数因数，那么它必定存在一个小于√n的整数因数。”的逆否命题也是真命题。// 即如果一个数n没有小于√n的整数因数，那么它也一定不会有大于√n的整数因数（除了它自己）。//n = 5 和 n=7 时，不会进入if判断语句，也不会进入for循环，而是直接返回true，此时也判断正确return true;
}void printHashTable(KeyNode HT[])
{int i = 0;KeyNode* p = NULL;printf("\n散列表中的元素为：");for (i = 0; i < m; i++){if (HT[i].next != NULL){printf("\n在%d个位置处，保存的关键字有：", i+1);for (p = HT[i].next; p; p = p->next){printf("%d ", p->Key);}}//空槽（链表不为空的）不输出，但是其它的元素还是要输出//链地址法中，散列表每个位置的HT[i].key成员并不存储任何数据，通常设置为 NULLKEY或者不使用}
}//散列表的删除
void Delete(KeyNode HT[],KeyType key)
{int	H0 = H(key);KeyNode* p = HT[H0].next;KeyNode* q = NULL;while (p != NULL){if (p->Key == key){break;}q = p;p = p->next;}if (!q){HT[H0].next = p->next;}else{q->next = p->next;}if (!p){printf("%d查找失败，无法删除。\n", key);}free(p);p = NULL;}

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

这篇关于《数据结构（C语言版）第二版》第七章-查找（算法设计题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1139329。

相关文章

闲置电脑也能活出第二春？鲁大师AiNAS让你动动手指就能轻松部署

闲置电脑也能活出第二春？鲁大师AiNAS让你动动手指就能轻松部署

对于大多数人而言，在这个“数据爆炸”的时代或多或少都遇到过存储告急的情况，这使得“存储焦虑”不再是个别现象，而将会是随着软件的不断臃肿而越来越普遍的情况。从不少手机厂商都开始将存储上限提升至1TB可以见得，我们似乎正处在互联网信息飞速增长的阶段，对于存储的需求也将会不断扩大。对于苹果用户而言，这一问题愈发严峻，毕竟512GB和1TB版本的iPhone可不是人人都消费得起的，因此成熟的外置存储方案开
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
怎么让1台电脑共享给7人同时流畅设计

怎么让1台电脑共享给7人同时流畅设计

在当今的创意设计与数字内容生产领域，图形工作站以其强大的计算能力、专业的图形处理能力和稳定的系统性能，成为了众多设计师、动画师、视频编辑师等创意工作者的必备工具。 设计团队面临资源有限，比如只有一台高性能电脑时，如何高效地让七人同时流畅地进行设计工作，便成为了一个亟待解决的问题。 一、硬件升级与配置 1.高性能处理器（CPU）：选择多核、高线程的处理器，例如Intel的至强系列或AMD的Ry
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2