《2022年数据结构:查找子系统 .pdf》由会员分享,可在线阅读,更多相关《2022年数据结构:查找子系统 .pdf(10页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、/* *题目:编写循序查找程序* 编写二分查找程序* 编写建立二叉排序树的程序* 编写在二叉排序树上的查找、输入、删除结点的程序* 编写二叉排序树的中序输出的程序* 设计一个选择式菜单,一级菜单形式如下:* 查找子系统* * * * 1-顺序查找* * * 2-二分查找* * * 3-二叉排序树* * * 0-返回* * * * 请选择菜单号(0-3) :* 二叉排序树的二级菜单如下:* 二叉排序树* * * * 1-更新二叉排序树* * * 2-查找结点* * * 3-插入结点* * * 4-删除结点* * * 5-中序输出排序树* * * 0-返回* * * * 请选择菜单号(0-5) :
2、*/ #include #include #include #define SEARCHMAX 30 typedef struct node int trData; / 根节点struct node *lchild; / 左子树struct node *rchild; / 右子树BtNode, *pBtNode; void seqSearch(); void binSearch(); void btSearch(); pBtNode createBT(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -
3、 - - - - 第 1 页,共 10 页 - - - - - - - - - void searchBT(pBtNode T, int k); void insBT(pBtNode *T, int k); void delBT(pBtNode *T, int k); void inorderBT(pBtNode T); void main() int choice, k = 1; while (k) printf(n 查找子系统 n); printf(*n); printf(* 1-顺序查找*n); printf(* 2-二分查找*n); printf(* 3-二叉排序树*n); print
4、f(* 0-返回*n); printf(*n); printf( 请选择菜单号(0-3) :); fflush(stdin); scanf(%d, &choice); switch(choice) case 1: seqSearch(); break; case 2: binSearch(); break; case 3: btSearch(); break; case 0: k = 0; break; default: printf( 输入错误,请重新输入。); getchar(); k = 1; break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - -
5、 - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 10 页 - - - - - - - - - void seqSearch() / 顺序查找 int aSEARCHMAX, x, y, i; char ch; printf( 建立一个整数的顺序表(以-1 结束) :); for (i = 0; iSEARCHMAX; i+) scanf(%d, &ai); getchar(); if (ai = -1) / 记录结束位置,结束循环 y = i; break; printf( 是否需要查找(Y/N) :); scanf(%c, &ch); while
6、(ch = y|ch = Y) printf( 请输入要查找的数据:n); scanf(%d, &x); getchar(); i = 0; / 找到数组的结束位置。while (i y-1&ai != x) / 找到要查找的数据的位置 i+; if (i = -1) / 没找到 printf( 对不起,没有找到。n); else printf( 该数据在第 %d 个位置上。 n, i+1); printf( 是否继续查找(Y/N) :); scanf(%c, &ch); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心
7、整理 - - - - - - - 第 3 页,共 10 页 - - - - - - - - - void binSearch() / 二分查找 int bSEARCHMAX, i, y, x, low, mid, high, n; char ch; printf( 建立递增有序的查找顺序表(以-1 结束) :n); for (i = 0; iSEARCHMAX; i+) scanf(%d, &bi); getchar(); if (bi = -1) / 记录结束位置,结束循环 y = i; break; printf( 是否需要查找(Y/N) :); scanf(%c, &ch); while
8、 (ch = y|ch = Y) printf( 请输入要查找的数据:); scanf(%d, &x); getchar(); low = 0; / 低high = y-1; / 高n = 0; / 记录次数while (low x) / 在左边 high = mid-1; else if (bmid high) printf( 对不起,没有找到该数据。n); printf( 共进行 %d 次比较。 n, n); if (bmid trData = k) / 判断是否找到该数据 printf( 已找到数据。 n); return; f = (k trData )?f-lchild:f-rchi
9、ld; / 判断下一个查找的位置 printf( 没有找到数据。n); void insBT(pBtNode *T, int k) / 插入二叉树结点 pBtNode f, p; p = (*T); / 指向指针的指针while (p) / 当结点不为空 if (p-trData = k) printf( 树中已有 %d,不需要插入。, k); return; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页,共 10 页 - - - - - - - - - else f =
10、p; p = (k trData)?p-lchild:p-rchild; / 判断插入的数据的位置 p = (BtNode *)malloc(sizeof(BtNode); / 分配空间p-trData = k; p-lchild = p-rchild = NULL; if (*T) = NULL) (*T) = p; else if (ktrData) f-lchild = p; else f-rchild =p; void delBT(pBtNode *T, int k) / 删除二叉树结点 pBtNode p, q, child, parent = NULL; p = *T; while
11、 (p) / 找到输入的数据的位置 if (p-trData = k) break; parent = p; / 记录上一个结点p = (k trData)?p-lchild:p-rchild; if (!p) / 没有找到位置 printf( 没有找到你要删除的数据结点。n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页,共 10 页 - - - - - - - - - return; q = p; if (q-lchild&q-rchild) for (parent
12、= q, p = q-rchild; p-lchild; parent = p, p=p-lchild) ; child = (p-lchild)?p-lchild:p-rchild; / 下一个指针的指向if (!parent) *T = child; else if (p = parent-lchild) parent-lchild = child; else parent-rchild = child; if (p != q) q-trData = p-trData; free(p); void inorderBT(pBtNode T) / 中序遍历二叉树 if (T != NULL) inorderBT(T-lchild); printf(%5d, T-trData); inorderBT(T-rchild); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页,共 10 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页,共 10 页 - - - - - - - - -