实验一 ADT描述及其实现
上机实验要求及规范
数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。在上机实验是一个重要的教学环节。一般情况下学生能够重视实验环节，对于编写程序上机练习具有一定的积极性。但是容易忽略实验的总结，忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目，一般不要急于编程。按照面向过程的程序设计思路（关于面向对象的训练将在其它后继课程中进行），正确的方法是：首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。具体实习步骤如下：
1.问题分析与系统结构设计
充分地分析和理解问题本身，弄清要求做什么（而不是怎么做），限制条件是什么。按照以数据结构为中心的原则划分模块，搞清数据的逻辑结构（是线性表还是树、图？），确定数据的存储结构（是顺序结构还是链表结构？）。然后设计有关操作的函数。在每个函数模块中，要综合考虑系统功能，使系统结构清晰、合理、简单和易于调试。最后写出每个模块的算法头和规格说明，列出模块之间的调用关系（可以用图表示），便完成了系统结构设计。
2.详细设计和编码
详细设计是对函数（模块）的进一步求精，用伪高级语言（如类C语言）或自然语言写出算法框架，这时不必确定很多结构和变量。
编码，即程序设计，是对详细设计结果的进一步求精，即用某种高级语言（如C/C++语言）表达出来。尽量多设一些注释语句，清晰易懂。尽量临时增加一些输出语句，便于差错矫正，在程序成功后再删去它们。
3.上机准备
熟悉高级语言用法，如C语言。熟悉机器（即操作系统），基本的常用命令。静态检查主要有两条路径，一是用一组测试数据手工执行程序（或分模块进行）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注释和断言。如果程序中逻辑概念清楚，后者将比前者有效。
4.上机调试程序
调试最好分块进行，自底向上，即先调试底层函数，必要时可以另写一个调用驱动程序，表面上的麻烦工作可以大大降低调试时所面临的复杂性，提高工作效率。
5.整理实习报告
在上机实开始之前要充分准备实验数据，在上机实践过程中要及时记录实验数据，在上机实践完成之后必须及时总结分析。写出实验报告。
一、实验报告的基本要求：
一般性、较小规模的上机实验题，必须遵循下列要求。养成良好的习惯。
（1）姓名班级学号日期
（2）题目：内容叙述
（3）程序清单（带有必要的注释）
（4）调试报告：
实验者必须重视这一环节，否则等同于没有完成实验任务。这里可以体现个人特色、或创造性思维。具体内容包括：测试数据与运行记录；调试中遇到的主要问题，自己是如何解决的；经验和体会等。
二、实验习报告的提高要求：
阶段性、较大规模的上机实验题，应该遵循下列要求。养成科学的习惯。
（1）需求和规格说明
描述问题，简述题目要解决的问题是什么。规定软件做什么。原题条件不足时补全。
（2）设计
a.设计思想：存储结构（题目中限定的要描述）；主要算法基本思想。
b.设计表示：每个函数的头和规格说明；列出每个函数所调用和被调用的函数，也可以通过调用关系图表
达。
c.实现注释：各项功能的实现程度、在完成基本要求的基础上还有什么功能。
（3）用户手册：即使用说明。
（4）调试报告：调试过程中遇到的主要问题是如何解决的；设计的回顾、讨论和分析；时间复杂度、空间复杂度分析；改进设想；经验和体会等。
实验一ADT描述及其实现
一、实验目的
1. 了解抽象数据类型（ADT）的基本概念，及描述方法。
2. 通过对抽象数据类型ADT的实现，熟悉C++语言语法及程序设计。为以后章节的学习打下基础。
二、实例
矩形抽象数据类型ADT的描述及实现。
[矩形ADT的描述]
ADT RECtangle{
数据对象：D={ length,width length,width∈FloatSet }
数据关系：R={ < length,width > }
基本操作：
初始化一个矩形
Void InitRectangle(struct Rectangle &r,float len,float wid);
计算矩形的周长
Float Circumference(struct Rectangle &r) ;
计算矩形的面积
Float Area(struct Rectangle &r) ;
} ADT RECtangle;
[矩形ADT的实现]
1.用c++的一般实现
Struct RECtangle{
Float length,width;
};
Void InitRectangle(struct Rectangle &r,float len,float wid){
r.length=len;
r.width=wid;
}
Float Circumference(struct Rectangle &r){
Return 2*(r.length+r.width);
}
Float Area(struct Rectangle &r){
Return r.lenght*r.width;
}
2.用c++类的实现
Class Rectangle{
Private:
Float length,width;
Public:
RECtangle(float len,float wid){
Length=len;width=wid;
}
Float Circumference(void){
Return 2*(r.length+r.width);
}
Float Area(void){
Return r.lenght*r.width;
}
};
[矩形ADT实现c++完整程序]
1. 用c++的一般实现
#include
Struct RECtangle{
Float length,width;
};
Void InitRectangle(struct Rectangle &r,float len,float wid); Float Circumference(struct Rectangle &r) ;
Float Area(struct Rectangle &r) ;
Void main(){
Float x,y;
Float p,s;
Rectangle a;
Cout<<”please input length and width of a rectangle:”< Cin>>x>>y; InitRectangle(a,x,y); P=Circumference(a) ; S=Area(a) ; Cout< Cout<<” Circumference of the rectangle:”< Cout<<” area of the rectangle:”< } Void InitRectangle(struct Rectangle &r,float len,float wid){ r.length=len; r.width=wid; } Float Circumference(struct Rectangle &r){ Return 2*(r.length+r.width); } Float Area(struct Rectangle &r){ Return r.lenght*r.width; } 2.用c++类的实现 略。 三、实验内容及要求 1．阅读实例，理解抽象数据类型的描述与实现方法与步骤，然后将上面源程序输入计算机，进行调试。运行程序，输入下列一个矩形的长和宽，记录输出结果。原始数据：2.0，3.5；3.0，6.3。 2．设计复数的抽象数据类型的描述与实现，只要求实现复数的初始化和和复数的加和减。 要求： 先给出复数的抽象数据类型的描述，然后分别用c++的一般形式和类的形式实现，再分别用c++的一般形式和类的形式写出完整的源代码，最后调试运行程序，输入数据，记录结果，完成实验报告。 附1： C语言基本知识 结构体及运用 数据结构课程所研究的问题均运用到“结构体”。在C语言中结构体的定义、输入/输出是数据结构程序设计的重要语法基础。定义结构体的一般格式： struct 结构体类型名 { 类型名1 变量名1； //数据子域 类型名2 变量名2；…… 类型名n 变量名n； }； 其中struct是保留字。结构体类型名由用户自己命名。在使用时必须声明一个具体的结构体类型的变量，声明创建一个结构体变量的方法是： struct 结构体类型名结构体变量名； 例如： struct ElemType /* 定义结构体 */ { int num; char name[10]; } ; struct ElemType x； /* 声明结构体变量x */ 另外有一种方法使用typedef 语句定义结构体，在声明结构体变量时可以不写struct，使得书写更加简便。例如： typedef struct { int num; char name[10]; } ElemType； ElemType就是一个新的类型名，并且是结构体类型名。声明变量x的语句是： ElemType x; 一个结构体中可以包含多个数据子域。数据子域的类型名一般指基本数据类型（int char 等），也可是已经定义的另一结构体名。数据子域变量名可以是简单变量，也可以是数组。它们也可以称为结构体的数据成员。 通过“结构体变量名.数据子域”可以访问数据子域。 例设计Student结构体，在主程序中运用。 #include #include typedef struct /* 定义结构体Student */ { long num; /* 学号*/ int x; /* 成绩*/ char name[10]; /* 姓名*/ } Student; void main( ) { Student s1; /* 声明创建一个结构体变量s1 */ s1.num=1001 ; /* 为s1的数据子域提供数据*/ s1. x=83; strcpy( https://www.wendangku.net/doc/6412835304.html,, “李明”)； printf( “\n 姓名：%s”, https://www.wendangku.net/doc/6412835304.html,); /* 输出结构体变量s1 的内容*/ printf( “\n 学号：%d”, s1.num); printf( “\n 成绩：%d”, s1.x); } 或者使用键盘输入: { scanf(“%d”, s1.num); scanf(“%d”, s1.x); scanf(“%s”, https://www.wendangku.net/doc/6412835304.html,); } 还可以通过“结构体指针->数据子域”来访问数据域。在实际问题中还会使用到指向结构体的指针，通过以下语句段可以说明结构体指针的一般用法。 { Student *p; /*声明指针变量p */ p=( Student *)malloc(sizeof( Student));/* 分配存储单元，首地址赋给p指针*/ p->num=101; p->x=83; strcpy( p->name, “李明”); printf(“\n %10s%6d%6d”,p->name,p->num,p->x); } 设计一个一维数组，每个数组元素是Student结构体类型，通过以下语句段可以说明结构体数组 的一般用法。可以通过“结构体数组名[下标].数据子域”访问数据域。 { Student a[5]; /* 声明创建一个结构体数组a */ int i ; for( i=0, i<5, i++){ printf(“\n 学号：%d”,a[i].num) ; printf(“\n 姓名：%s”,a[i].name) ； printf(“\n 成绩：%d”,a[i].x) ; } } 以上是关于结构体的基本概念和简单运用。 河北科技大学 实验报告 16级计算机科学与技术专业班学号 2019年5月21日姓名教师白云飞 实验名称查找表操作成绩 实验类型设计型实验批阅教师白云飞 一、实验目的 1．掌握查找表的基本概念。 2．掌握静态查找表（顺序查找、折半查找）的存储和算法实现。 3．掌握动态查找表（二叉排序树）的存储和算法实现。 二、实验内容 1．给出静态查找表的顺序存储结构描述。 2．实现顺序查找和折半查找操作。 3．给出二叉排序树的二叉链式存储结构描述。 4．实现二叉排序树的初始化、插入、删除、查找、清空等操作。 5．编写主程序实现对这些运算的测试。 三、实验环境 硬件：CPU I 5 内存4GB，硬盘512GB 操作系统：Windows XP 软件编程环境：VC++6.0 四、实验步骤 1．用VC建立一个控制台应用程序，命名为Search。 2．新建一个头文件，命名为datastru.h，包含标示符常量的定义和Status类型定义。 3．新建一个头文件，命名为Search.h，包含查找表的存储类型描述和基本运算的声明。4．新建一个程序文件，命名为Search.cpp，包含查找表基本运算的实现和复杂运算的实现。5．新建一个主程序文件，命名为SearchMain.cpp，包含对这些运算的测试。 五、程序源代码（对复杂的设计思想描述要有较详细的注释） 1．头文件datastru.h内容。 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status ; 2．头文件Search.h内容。 …… 3．程序文件Search.cpp内容。 ……. 4．主程序文件SearchMain.cpp实现。 //设计测试程序 …… 六、实验数据、结果分析 （描述最终得到的结果，并进行分析说明） 既要有正确数据的测试也要有异常数据的测试。 七、结论体会 （说明实验过程中遇到的问题及解决办法；个人的收获；未解决的问题等） 实验目的: 观察.研究”递归表查询”的用法. 所有路由表项不必一定指向下一跳路由器. 实验说明: 如上图,所有路由器都配的是静态路由,所以每个路由器上的路由表项都是比较大的.刚开始是经由R2去往R4和R5右边的网络的,现在想要改由经过R3去往那边的网络. 如果用一般的方法,配置静态路由会比较麻烦.因此在这儿用”递归表查询”只需改动一条静态路由,便可以实现要求! ************************************************************** 基本配置: 各个路由器上的静态路由已经配好. R1:(配置递归表项) R1(config)#ip route 10.45.2.0 255.255.255.0 10.87.14.4 R1(config)#ip route 10.10.3.0 255.255.255.0 10.87.14.4 R1(config)#ip route 192.168.200.0 255.255.255.0 10.87.14.5 R1(config)#ip route 192.168.150.0 255.255.255.0 10.87.14.5 R1(config)#ip route 10.87.14.0 255.255.255.0 10.23.5.20 ************************ 此时R1上的路由表: R1(config)#do sh ip rou Codes: C - connected, S - static, R - RIP, M - mobile, B - BGP D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area N1 - OSPF NSSA external type 1, N2 - OSPF NSSA external type 2 E1 - OSPF external type 1, E2 - OSPF external type 2 i - IS-IS, su - IS-IS summary, L1 - IS-IS level-1, L2 - IS-IS level-2 ia - IS-IS inter area, * - candidate default, U - per-user static route o - ODR, P - periodic downloaded static route Gateway of last resort is not set S 192.168.150.0/24 [1/0] via 10.87.14.5 S 192.168.200.0/24 [1/0] via 10.87.14.5 10.0.0.0/24 is subnetted, 4 subnets S 10.10.3.0 [1/0] via 10.87.14.4 C 10.23.5.0 is directly connected, FastEthernet0/0 S 10.45.2.0 [1/0] via 10.87.14.4 S 10.87.14.0 [1/0] via 10.23.5.20 *********************************** 通过路由跟踪,可以看到刚开始数据包是经由R2 被转发的: R1#traceroute 192.168.200.1 Type escape sequence to abort. Tracing the route to 192.168.200.1 1 10.23.5.20 140 msec 4 msec 80 msec 2 10.23.5.95 104 msec 80 msec 48 msec 3 10.87.14.5 152 msec * 256 msec *************************** 现在在R1上用以下命令让数据包改由R3转发: R1(config)#no ip route 10.87.14.0 255.255.255.0 10.23.5.20 R1(config)#ip route 10.87.14.0 255.255.255.0 10.23.5.95 ******************************** 此时再看R1的上路由表: 9.1静态查找表 关键字类型说明： typedef float KeyType； //实型。 typedef int KeyType； //整型。 typedef char *KeyType; //字符串型。 数据元素类型定义： typedef struct{ KeyType key; //关键字域。 ... //其它域。 }ElemType; 对两个关键字的比较： //--对数值型关键字--- #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)>=(b)) //--对字符串型关键字--- #define EQ(a,b) (!strcmp((a),(b))) #define LT(a,b) (strcmp((a),(b))<0) #define LQ(a,b) (strcmp((a),(b))>=0) ... 9.1.1顺序表的查找 //---静态查找表的顺序存储结构------- typedef struct { ElemType *elem; //数据元素存储空间基址，建表时按实际长度分配，0号单元留空。 int length; //表长度。 }SSTable; 程序： int Search_Seq(SSTable ST,KeyType key) //在顺序表ST中顺序查找其关键字等于key的数据元素，若找到，则函数值为 //该元素在表中的位置，否则为0。 { ST.elem[0].key=key; for(i=ST.length;!EQ(ST.elem[i].key,key);--i);//从后往前找。 return i; //找不到时,i为0。 }//Search_Seq 9.1.2有序表的查找。 ①折半查找实例： （05,13,19,21,37,56,64,75,80,88,92）查找21和85. （1）找21. low=1,high=11 ,mid=(low+high)/2=6,ST.elem[mid]=56>21; low=1,high=mid-1=5,mid=(low+high)/2=3,ST.elem[mid]=19<21; low=mid+1=4,high=5,mid=(low+high)/2=4,ST.elem[mid]=21=21; 实验B06: 静态表的查找操作实验 一、实验名称和性质 二、实验目的 1．掌握顺序查找操作的算法实现。 2．掌握二分查找操作的算法实现及实现该查找的前提。 3．掌握索引查找操作的算法实现。 三、实验内容 1．建立顺序查找表，并在此查找表上实现顺序查找操作（验证性内容）。 2．建立有序顺序查找表，并在此查找表上实现二分查找操作（验证性内容）。 3．建立索引查找表，并在此查找表上实现索引查找操作（设计性内容）。 四、实验的软硬件环境要求 硬件环境要求： PC机（单机） 使用的软件名称、版本号以及模块： Windows环境下的TurboC2.0以上或VC++ 五、知识准备 前期要求掌握查找的含义和顺序查找、二分查找及索引查找操作的方法。 六、验证性实验 1．实验要求 编程实现如下功能： （1）根据输入的查找表的表长n和n个关键字值，建立顺序查找表，并在此查找表中用顺序查找方法查找给定关键值的记录，最后输出查找结果。 （2）根据输入的查找表的表长n和n个按升排列的关键字值，建立有序顺序查找表，并在此查找表中用二分查找方法查找给定关键值的记录，最后输出查找结果。 （3）主程序中要求设计一个菜单，允许用户通过菜单来多次选择执行哪一种查找操作。 2. 实验相关原理： 查找表分别静态查找表和动态查找表两种，其中只能做引用操作的查找表称为静态查找表。 静态查找表采用顺序存储结构的数据描述为： #define MAXSIZE 100 /*顺序查找表的最大长度*/ typedef int keytype; typedef struct {keytype key; }redtype; typedef struct {redtype elem[MAXSIZE]; int length; }Sstable; 【核心算法提示】 查找操作是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或记录的过程。若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；若在查找表中不存在这样的记录，则称“查找不成功”。查找结果给出“空记录”或“空指针”。 （1）顺序查找操作的基本步骤：从表中最后一个记录开始，逆序扫描查找表，依次将扫描到的结点关键字值与给定值key进行比较，若当前扫描到的结点关键字值与key相等，则查找成功；若扫描到第一个记录，仍未找到关键字值等于key的记录，则查找失败。在程序设计中为了减少执行的循环次数使用了监视哨。监视哨可设置在表头，也可设置在表尾。在此设置在表头。 （2）二分查找也叫折半查找，这种查找要求查找表必须是有序顺序表。其查找操作的基本步骤：首先取出表中的中间元素，若其关键字值等于给定值key，则查找成功，操作结束；否则以中间元素为分界点，将查找表分成两个子表，并判断所查的key值所在的子表是前部分，还是后部分，再重复上述步骤直到找到关键字值为key的元素或子表长度为0。【核心算法描述】 int sxsearch(Sstable ST, keytype key) /*在顺序查找表ST中，用顺序查找的方法查找其关键字等于key的数据元素。若找到，则函数返回 数据结构实验报告 题目：静态查找表的实现 成绩____________________ 2014年6月10号 静态查找表抽象数据类型的实现 一、设计任务、要求及所用的软件环境或工具： 1.设计任务及要求：用C语言实现静态查找表的抽象数据类型 2.软件环境：win7 3.开发工具：C-Free 二、抽象数据类型的实现 1. 题目 采用顺序存储和链式存储为存储结构，实现抽象数据类型StaticSearchTable。 ADT StaticSearchTable{ 数据对象D：D是具有相同特性的数据元素的集合。各个数据元素 含有类型相同的关键字，可唯一标识元素的关键字。 数据关系R：数据元素同属一个集合。 基本操作P： Create(&ST,n); 操作结果：构造一个含n个数据元素的静态查找表ST。 Destroy(&ST); 初始条件：静态查找表ST存在。 操作结果：销毁表ST。 Search(ST,key); 初始条件：静态查找表ST存在，key 为和关键字类型相同的 给定值。 操作结果：若 ST 中存在其关键字等于key的数据元素，则 函数值为其值或在表中的位置，否则为“空”。 Traverse(ST,Visit()); 初始条件：静态查找表ST存在，Visit是对元素操作的应用 函数。 操作结果：按某种次序对ST的每个元素调用函数Visit()一 次且仅一次。一旦Visit()失败，则操作失败。 }ADT StaticSearchTable 2．存储结构定义 *公用头文件DS0.h: #include 数据结构实验 实验一静态查找表中的查找 一、实验目的： 1、理解静态查找表的概念 2、掌握顺序查找和折半查找算法及其实现方法 3、理解顺序查找和折半查找的特点，学会分析算法的性能 二、实验内容： 1、按关键字从小到大顺序输入一组记录构造查找表，并且输出该查找表； 2、给定一个关键字值，对所构造的查找表分别进行顺序查找和折半查找，输出查找的结果以及查找过程中“比较”操作的执行次数。 三、实验要求： 1、查找表的长度、查找表中的记录和待查找的关键字值要从终端输入； 2、具体的输入和输出格式不限； 3、算法要具有较好的健壮性，对错误操作要做适当处理； 4、输出信息中要标明所采用的查找方法类型。 实验二基于二叉排序树的查找 一、实验目的： 1、理解动态查找表和二叉排序树的概念 2、掌握二叉排序树的构造算法及其实现方法 3、掌握二叉排序树的查找算法及其实现方法 二、实验内容： 1、输入一组记录构造一颗二叉排序树，并且输出这棵二叉排序树的中序序列； 2、给定一个关键字值，对所构造的二叉排序树进行查找，并输出查找的结果。 三、实验要求： 1、二叉排序树中的记录和待查找的关键字值要从终端输入； 2、输入的记录格式为(整数，序号)，例如(3, 2)表示关键字值为3，输入序号为2的记录； 3、算法要具有较好的健壮性，对错误操作要做适当处理。 四、程序实现： (1)实现顺序查找表和折半查找表： #include /* 静态查找表(顺序结构) 实现 Create(&ST,n)构造含有n个元素的静态查找表ST Destroy(&ST)销毁表 Search(ST,key)返回表中位置,若无,返回空 Traverse(ST,Visit())遍历-->函数作为参数暂时不会 */ #include for(i=1;i<=ST->length;i++){ printf("%d ",ST->elem[i]); } printf("\n\n"); } void Destroy(stable *ST){ free(ST->elem); ST->elem=NULL; ST->length=0; } void main(){ stable ST; int n; elemtype key; printf("\n请输入元素个数:"); scanf("%d",&n); Create(&ST,n); printf("\n请输入要查找的数:"); scanf("%d",&key); printf("\n要找的元素在第%d位\n",Search(&ST,key)); Traverse(&ST); Destroy(&ST); } 实验一、静态查找表中的查找 一、实验目的： 1、理解静态查找表的概念 2、掌握顺序查找和折半查找算法及其实现方法 3、理解顺序查找和折半查找的特点，学会分析算法的性能 二、实验仪器 PC、VC++6.0 三、简要原理 【实验内容】 1、按关键字从小到大顺序输入一组记录构造查找表，并且输出该查找表； 2、给定一个关键字值，对所构造的查找表分别进行顺序查找和折半查找，输出查找的结果以及查找过程中“比较”操作的执行次数。 【实验要求】 1、查找表的长度、查找表中的记录和待查找的关键字值要从终端输入； 2、具体的输入和输出格式不限； 3、算法要具有较好的健壮性，对错误操作要做适当处理； 4、输出信息中要标明所采用的查找方法类型。 四、实验数据及计量结果 <头文件static.h> #include 上海环球雅思老师于君星今天为大家带来的是雅思小作文中静态图表必备考点解析。雅思A 类小作文的图标题其实是非常有用的，对考生之后出国留学过程中，大家写论文的时候是经常会碰到的。所以说能写得一手好图标解析的小作文是有很大的作用的。 一、何为静态图 静态图表可以为所呈现的信息，只有不同数据之间的对比，无时间变化的图表。主要常见的静态图可以分为：柱状图，饼状图，表格以及对比式的地图题。 二、静态图表的例题解析 （一）图表 You may spend about 20 minutes on this task. The chart below shows the different levels of post-school qualification in Australia and the proportion of men and women who held them in 1999. Summarise the information by selecting and reporting the main features, and make comparisons if necessary. You should write about 150 words. （二）范文分析 1、Part 1: Introduction The bar chart here reflects 5 different levels of post-school qualifications as well as the proportion of qualification-holders according to gender in Australia in 1999. （1）表示开头段介绍句的句型 The bar chart here reflects 5 different levels of post-school qualifications as well as the proportion of qualification-holders according to gender in Australia in 1999. （2）该句可以做成句型： The 图表名称+（given/here/provided）+describe/demonstrate/depict/ details/ display/ illustrate/ indicate/ represent/reflect............ （3）该句可以改写成： Given in the 图表名称is the information/are figures regarding/concerning/about/on............ A glance at the + 图表名称+provided/here/given + reveals/indicates......... 2、Part 2: Main Body Main Body 1: Apparently, there is a striking/remarkable contrast/gap in the proportion of both genders who attained skilled vocational diploma. More precisely, men in this level reached/accounted for 90%, + ,which is nine times as much as their female counterparts. , and women’s percentage was only 10%. , nine times as much as females. + What should be emphasized is that both data ranked the most and the least among five level. （1）主体段落开头必备 副词 总结与提高——教学讲义 【主要知识点】 1．查找表的检索机制 查找表是由同一类型元素构成的集合。本章给出了三种类型的查找表： 第一类主要基于线性结构，记录关键字一般按序排列，以提高检索速度，主要采用基于比较的顺序检索或折半检索方法。由于这一类查找表主要用于查找，一般不对表做插入和删除操作，通常称为静态查找表。 第二类主要基于树形结构，包括二叉树和m 叉树，主要采用基于比较的分支检索方法，即从树根开始，根据比较结果，沿着特定的分支进行检索，其检索的时间复杂度与树的深度同级别为对数函数。由于这一类查找表不仅用于查找，还需要对表做插入和删除操作，通常称为动态查找表。 第三类是散列（哈希）结构，根据数据的关键字“计算”数据的存储地址。散列（哈希）法既是建立表的方法，也是查找表的方法，其对应的检索方法是“计算式”的检索。 2．平均查找长度 为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。由于查找算法的基本运算是关键字之间的比较操作，所以平均查找长度是衡量查找算法的性能的重要指标。 计算平均查找长度的基本公式： 对于长度为n 的列表，查找成功时的平均查找长度为： ASL=P 1C 1+P 2C 2+…+P n C n =∑=n i i i c p 1其中P i 为查找列表中第i 个数据元素的概率，C i 为找到列表中第i 个数据元素时，已经进行过的关键字比较次数。 计算方法： 针对具体的查找问题，一般直接根据上述定义计算平均查找长度，通常称为手工计算方式。也可采用预先推导出的理论公式进行计算，理论公式一般基于合理的假设，通用但有一定误差。虽然两种方式在计算相同问题时得到的具体结果有一定差异，但都是基于相同的平均查找长度定义，故应当掌握这些方法原则并能应用。 3．折半查找 折半查找法要求待查找表应采用顺序存储结构且按关键字有序排列。 折半查找过程借助于折半判定树加以描述。判定树中每一结点对应表中一个记录在表中的位置序号。 折半查找算法的性能：在等概率时查找成功的平均查找长度与折半判定树的深度相关， 1 )1(log 2-+≈n ASL bs 折半查找算法查找速度快，平均性能好；插入删除较困难。 4．二叉排序树 二叉排序树的定义：树中左子树上所有结点的值均小于根结点的值，树中右子树上所有结点的值均大于根结点的值。 二叉排序树的构建过程：从空树开始，每次都从根开始比较插入（小于插入左子树，大于插入其右子树），逐一往树中插入序列中所有结点。 二叉排序树的构建形态：含有n 个相同结点的二叉排序树形态各异，其构造形态与数列的输入顺序有关。 查找表 一、选择题： 1．若查找每个元素的概率相等，则长度为n的顺序表上查找任一元素的平均查找长度为（） A．n B．n+1 C．(n-1)/2 D．(n+1)/2 2．顺序查找法适合于（）存储结构的查找表。 A．压缩B．散列C．索引D．顺序或链式 3．对线性表采用二分查找法，该线性表必须（）。 A．采用顺序存储结构 B．采用链式存储结构 C．采用顺序存储结构，且元素按值有序 D．采用链式存储结构，且元素按值有序 4．对长度为n的单链有序表，若查找每个元素的概率相等，则查找任一元素的平均查找长度为（）。 A．n/4 B．n+1 C．(n-1)/2 D．(n+1)/2 5．设有序表的关键字序列为{10，14，16，20，28，35，42，53，67，71，78，84，92，99}，当用二分查找法查找键值为84的节点时，经（）次比较后查找成功。 A．2 B．3 C．4 D．12 7．静态查找表与动态查找表两者的根本差别在于（）。 A．逻辑结构不同 B．存储实现不同 C．施加的操作不同 D．数据元素的类型不同 8．判断：采用二分法查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。（错） 9．对于静态顺序查表算法，若在表头设置岗哨，则正确的查找方式为（）。 A．从第0个元素开始往后查找该数据元素 B．从第1个元素开始往后查找该数据元素 C．从第n个元素开始往前查找该数据元素 D．与查找顺序无关 11．采用顺序查找法，若在表尾设置岗哨，则正确的查找方式通常为（）。 A．从第0个元素开始往后查找该数据元素 B．从第1个元素开始往后查找该数据元素 C．从第n个元素开始往前查找该数据元素 D．从第n+1个元素开始往前查找该数据元素 12．在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入至集合中。这种方式主要适合（） A．静态查找表 B.动态查找表 C.静态查找表与动态查找表 C.两种表都不适合 实验B06: 静态表得查找操作实验 一、实验名称与性质 二、实验目得 1.掌握顺序查找操作得算法实现。 2.掌握二分查找操作得算法实现及实现该查找得前提。 3.掌握索引查找操作得算法实现。 三、实验内容 1.建立顺序查找表,并在此查找表上实现顺序查找操作(验证性内容)。 2.建立有序顺序查找表,并在此查找表上实现二分查找操作(验证性内容)。 3.建立索引查找表,并在此查找表上实现索引查找操作(设计性内容)。 四、实验得软硬件环境要求 硬件环境要求: PC机(单机) 使用得软件名称、版本号以及模块: Windows环境下得TurboC2、0以上或VC++ 五、知识准备 前期要求掌握查找得含义与顺序查找、二分查找及索引查找操作得方法。 六、验证性实验 1.实验要求 编程实现如下功能: (1)根据输入得查找表得表长n与n个关键字值,建立顺序查找表,并在此查找表中用顺序查找方法查找给定关键值得记录,最后输出查找结果。 (2)根据输入得查找表得表长n与n个按升排列得关键字值,建立有序顺序查找表,并在此查找表中用二分查找方法查找给定关键值得记录,最后输出查找结果。 (3)主程序中要求设计一个菜单,允许用户通过菜单来多次选择执行哪一种查找操作。 2、实验相关原理: 查找表分别静态查找表与动态查找表两种,其中只能做引用操作得查找表称为静态查找表。 静态查找表采用顺序存储结构得数据描述为: #define MAXSIZE 100 /*顺序查找表得最大长度*/ typedef int keytype; typedef struct {keytype key; }redtype; typedef struct查找表实验报告
递归表查询法配置静态路由
9.1静态查找表
静态表的查找操作实验
数据结构实验报告之静态查找表
数据结构实验报告-静态查找表中的查找
静态查找表-C基本操作
静态查找
雅思小作文静态图表必备
数据结构：查找表
查找表复习
静态表的查找操作实验