首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


{ printf("nUnsuccess"); printf("nThe time of compare is %d",time); } printf("nContinue(y/n):n");/*是否继续,y 或 Y 继续查询,其它退出查询*/ ch=getch(); } while (ch=='y' || ch=='Y') ; } else /*表 ST 建立失败,输出内存溢出的信息*/

printf("noverflow"); } 【测试数据】

1.建立顺序表,根据运行提示输入表的长度和这些数据,建立一个顺序表,并可进行多次查找,注意观察运 行结果。 Please input the length of table:10 Please input 10 data:2 1 9 8 10 21 90 43 11 32 Input the key you want to search: 90 Success,the position is 7 The time of compare is 4 Continue(y/n):y Input the key you want to search: 7 Unsuccess The time of compare is 11 continue(y/n):n 2.读者自己可根据运行提示,自行输入数据建立顺序表,然后进行多次查询,注意观察运行结果,分析比 较次数。 【说明】 简单的算法分析:设顺序查找表的长度为 n,查找失败的比较次数为 n+1;在等概率情况下,查找成功时的平 均查找长度为 ; 【实验题】 1. 以上示例实现了无序顺序表的建立和查找算法,请读者完善以上程序,实现如下功能:编写函数计算如 上建立的顺序表在查找成功时的平均查找长度。 (可设定在等概率情况下,也可自行指定每个元素的查找概 率) 。 2. 参考以上程序,建立一个有序的顺序表,实现折半查找算法。要求能进行多次查找,对每次查找,要求输 出查找的结果和查找时需和表中关键字进行比较的次数,最后计算该表在等概率情况下的平均查找长度。 3. 建立一个索引顺序表,在索引表中采用折半查找方法确定待查关键字所在的块,而在块内采用顺序查找 方法进行查找,输出查找结果。 4. 编写一个学生成绩管理系统,每个学生的数据信息有准考证号(主关键字) 、姓名、政治、语文、英语、 数学、物理和总分等数据项,所有学生的信息构成一个学生成绩表。假设准考证号的头两位表示地区编号。 请设计一个管理系统达到如下基本要求: (1) 初始化:建立一个学生成绩表,输入准考证号、姓名、政治、语文、英语、数学、物理,然后计算 每个学生的总分,存入相应的数据项;注意:分析数据对象和它们之间的关系,并以合适的方式进行组织

(可选择无序的顺序表、有序的顺序表或索引顺序表来进行存储表示) ; (2) 查找:综合应用基本查找算法完成数据的基本查询工作,并输出查询的结果; (3) 输出:有选择性地输出满足一定条件的数据记录,如输出地区编号为"01",并且总分在 550 分以上 的学生的信息; (4) 计算:计算在等概率情况下该查找表的平均查找长度。

第三节 动态查找表
【问题描述】 动态查找表的特点是表结构本身在查找过程中动态生成,即对给定的关键字 key,若表中存在其关键字等于 key 的记录,则查找成功返回,否则插入关键字等于 key 的记录。设计一个有关动态查找表(以二叉排序树 为例)的建立、查找、插入和删除等基本操作的演示程序。 【数据描述】 动态查找表的抽象数据类型定义: ADT DynamicSearchTable{ D: 由具有相同特性的数据元素的集合。各元素含有类型相同,可唯一标识数据元素的关键字。 R:数据元素同属一个集合。 P:InitDSTable(&DT) 构造一个空的动态查找表 DT

DestroyDSTable(&DT) 销毁一个已存在的动态查找表 DT SearchDSTable(&DT,key) 在表 DT 中查找其关键字等于 key 的数据元素是否存在 InsertDSTable(&DT,e) 在表 DT 中插入一个表中没有的数据元素 e

DeleteDSTable(&DT,key) 在表 DT 中删除关键字为 key 的数据元素 TraverseDSTable(ST,visit()) 按某种次序对 DT 的每个元素进行访问 }ADT DynamicSearchTable;</P><P>【算法描述】 //动态查找表(二叉排序树)的链式存储结构定义 typedef struct BiTNode{ ElemType data; Struct BiTNode *lchild,*rchild; } BiTNode,*BiTree; // 二叉排序树的建立、查找、算法的实现和分析 BiTree SearchBST(BiTree bt,KeyType key){ if (bt==NULL) return NULL;//查找失败

else { if EQ(bt->data.key,key) return bt;//查找成功 else if LT(bt->data.key,key) return(SearchBST(bt->lchild,key)); else return(SearchBST(bt->lchild,key)); } } void InsertBST(BiTree &bt,BiTree s){ // 在二叉排序树 bt 中插入一个结点 s if (bt==NULL) bt=s; else if EQ(s->data.key,bt->data.key) return ();//不插入结点 else if LT(s->data.key,bt->data.key) InsertBST(bt->lchild,s);//不插入结点 else InsertBST(bt->rchild,s); } void CreateBST(Bitree &bt){ //建立一棵二叉排序树 ,bt 指向根结点 bt=NULL; do { scanf(&x); s=(BiTree)malloc(sizeof(BiTNode));s->data.key=x;s->lchild=s->rchild=NULL; InsertBST(bt,s);} While (x!=-1);//重复输入一系列值,直至输入的关键字等于-1 结束 }//CreateBST Status DeleteBST(BiTree &bt,KeyType key){ //若 bt 指向的二叉排序树中存在其关键字等于 key 的数据元素,则删除它。 if(bt==NULL) return FALSE; else{ if EQ(s->data.key,bt->data.key) Delete(bt);//不插入结点 else if LT(s->data.key,bt->data.key) DeleteBST(bt->lchild,key); else DeleteBST(bt->rchild,key); } 【C 源程序】

/*(二叉排序树的建立和查找算法实现示例)*/ #include <stdlib.h> #include <stdio.h> #define NULL 0 typedef int KeyType; typedef struct { KeyType key; </P><P>}ElemType; /*元素类型(其他数据项略,读者可根据实际情况加入)*/ typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTree searchBST(BiTree bt,KeyType key){ /*在二叉排序树 bt 中查找其关键字等于给定值的结点是否存在,并输出相应信息*/ if (bt==NULL) return NULL; else if (bt->data.key==key) return bt; else if (key<bt->data.key) return searchBST(bt->lchild,key); else return searchBST(bt->rchild,key); } void insertBST(BiTree *bt,BiTree s){ /*在二叉排序树中插入一个新结点*/ if (*bt==NULL) *bt=s; else if (s->data.key<(*bt)->data.key) insertBST(&((*bt)->lchild),s); else if (s->data.key>(*bt)->data.key) insertBST(&((*bt)->rchild),s); } void inorder(BiTree bt){ /*对已经建立好的二叉排序树进行中序遍历,将得到一个按关键字有序的元素序列*/ if (bt!=NULL){ inorder(bt->lchild); printf("%5d",(bt->data).key); inorder(bt->rchild);

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 

数据结构实验指导书 - 数据结构 实验指导书 院别 专业 班级 姓名 计算机学院编 实验一 线性表的顺序存储实验 一、实验目的及要求 1、掌握在TC环境下调试顺序表...

数据结构与算法实验指导书90969 - 数据结构与算法实验指导书 计算机与信息学院 实验一 【实验目的】 顺序表 熟练掌握线性表在顺序存储结构上的基本操作。 【实验...

数据结构实验指导书02 很好!很好!隐藏&gt;&gt; 实验二 2.1 实验目的: 线性表 (1)掌握线性表的顺序存储结构的定义及 C 语言实现。 (2)掌握线性表在顺序存储结构即...

数据结构实验说明书新版 - the principl e of simplified E IA of constr uction pr oject s in the regi on. In te...

数据结构实验指导书 - 数据结构实验指导(C语言版)... 数据结构实验指导书_IT/计算机_专业资料。数据结构实验指导(C语言版) 数据结构实验指导书 江西农业大学计算机与...

数据结构试验指导书V2[1].0 - V 2.0 数据结构与算法 实验指导书 编写: 编写:陆绍飞 校核: 校核:___ 湖南大学软件学院 2011 年 9 月 湖南大学软件学...

数据结构实验指导书(2012.9) - 1.2 实验报告(文档)书写规范 实验报告(文档)应包括以下 7 个方面的内容: 1、问题分析 根据对实验任务的理解, 以无歧义的陈述...

09级《数据结构》实验指导书 - 《数据结构实验指导书》 潘向辉/吴学毅编写 印包学院数字媒体技术专业 2011 年 3 月 实验说明 实验说明 【实验环境】 操作系统:...

空间数据结构基础实验指导书 隐藏&gt;&gt; 《空间数据结构基础》 课程实习指导书实习周数:2 周 学分数:2 一、实习目的 数据结构是一门重要的专业基础课,其特点是理论...

《数据结构(C 语言版) 》实验指导书(非计算机专业适用) 广州大学 2013.1 目 录 实验一 线性表的顺序存储及其操作... 1 实验二 线性表的链式存储及其操作......


 

热点推荐