顺序表查找算法

东北石油大学计算机与信息技术学院李勇勇顺序表查找的算法：

最好情况下时间复杂度O(1),最坏情况下时间复杂度O(n),平均查找次数(n+1)/2

1

顺序查找法适用于存储结构为顺序或链接存储的线行表

一判断题 1．顺序查找法适用于存储结构为顺序或链接存储的线行表。 2．一个广义表可以为其他广义表所共享。 3．快速排序是选择排序的算法。 4．完全二叉树的某结点若无左子树，则它必是叶子结点。 5．最小代价生成树是唯一的。 6．哈希表的结点中只包含数据元素自身的信息，不包含任何指针。 7．存放在磁盘，磁带上的文件，即可意识顺序文件，也可以是索引文件。8．折半查找法的查找速度一定比顺序查找法快。 二选择题 1．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。 A. n B. 2n-1 C. 2n D. n-1 2.在文件"局部有序"或文件长度较小的情况下，最佳内部排序的方法是（）。 A. 直接插入排序 B.气泡排序 C. 简单选择排序 D. 快速排序 3.高度为K的二叉树最的结点数为（）。 A. 2 4.一个栈的输入序列是12345，则占的不可能的输出序列是（） A.54321 B. 45321 C.43512 D.12345 5.ISAM文件和V ASM文件属于（） A索引非顺序文件 B. 索引顺序文件 C. 顺序文件 D. 散列文件 6. 任何一棵二叉树的叶子结点在先序，中序和后序遍历序列中的相对次序（） A. 不发生变化 B. 发生变化 C. 不能确定 D. 以上都不对 7.已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（）。 A. acbed B. decab C. deabc D.cedba 三．填空题 1．将下图二叉树按中序线索化，结点的右指针指向（），Y的左指针指向（） B D C X E Y 2．一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四各度为4的结点和若干叶子结点，则T的叶结点数为（）

实现顺序表各种基本运算的算法

实现顺序表各种基本运算的算法 要求：编写一个程序（algo2_1.cpp）实现顺序表的各种基本操作，并在此基础上设计一个主程序（exp2_1.cpp）完成如下功能： （1）初始化顺序表L （2）依次采用尾插法插入a,b,c,d,e元素 （3）输出顺序表L （4）输出顺序表L的长度 （5）判断顺序表L是否为空 （6）输出顺序表L的第3个元素 （7）输出元素a的位置 （8）在第4个元素位置上插入f元素 （9）输出顺序表L （10）删除L的第3个元素 （11）输出顺序表L （12）释放顺序表L /*文件名:exp2-1.cpp*/ #include #include #define MaxSize 50 typedef char ElemType; typedef struct { ElemType elem[MaxSize]; int length; } SqList; extern void InitList(SqList *&L); extern void DestroyList(SqList *L); extern int ListEmpty(SqList *L); extern int ListLength(SqList *L); extern void DispList(SqList *L); extern int GetElem(SqList *L,int i,ElemType &e); extern int LocateElem(SqList *L, ElemType e); extern int ListInsert(SqList *&L,int i,ElemType e); extern int ListDelete(SqList *&L,int i,ElemType &e); void main() { SqList *L; ElemType e; printf("(1)初始化顺序表L\n"); InitList(L); printf("(2)依次采用尾插法插入a,b,c,d,e元素\n"); ListInsert(L,1,'a'); ListInsert(L,2,'b');

实验报告一顺序表的操作

《数据结构》实验报告一 系别：班级： 学号：姓名： 日期：指导教师： 一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 从键盘输入10个整数，产生顺序表，并输入结点值。 从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找不到，则显示“找不到”。 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出顺序表所有结点值，观察输出结果。 从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。二、程序设计的基本思想，原理和算法描述： （包括程序的结构，数据结构，输入/输出设计，符号名说明等） 三、源程序及注释：

#include <> /*顺序表的定义：*/ #define ListSize 100 /*表空间大小可根据实际需要而定，这里假设为100*/ typedef int DataType; /*DataType可以是任何相应的数据类型如int, float或char*/ typedef struct { DataType data[ListSize]; /*向量data用于存放表结点*/ int length; /*当前的表长度*/ }SeqList; /*子函数的声明*/ void CreateList(SeqList * L,int n); /*创建顺序表函数*/ int LocateList(SeqList L,DataType x); /*查找顺序表*/ void InsertList(SeqList * L,DataType x,int i); /*在顺序表中插入结点x*/ void DeleteList(SeqList * L,int i);/*在顺序表中删除第i个结点*/ void PrintList(SeqList L,int n); /*打印顺序表中前n个结点*/ void main() { SeqList L; int n=10,x,i; /*欲建立的顺序表长度*/ =0;

五种查找算法总结

五种查找算法总结 一、顺序查找 条件：无序或有序队列。 原理：按顺序比较每个元素，直到找到关键字为止。 时间复杂度：O(n) 二、二分查找（折半查找） 条件：有序数组 原理：查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束； 如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。 如果在某一步骤数组为空，则代表找不到。 这种搜索算法每一次比较都使搜索范围缩小一半。 时间复杂度：O(logn) 三、二叉排序树查找 条件：先创建二叉排序树： 1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 3. 它的左、右子树也分别为二叉排序树。 原理： 在二叉查找树b中查找x的过程为： 1. 若b是空树，则搜索失败，否则： 2. 若x等于b的根节点的数据域之值，则查找成功；否则： 3. 若x小于b的根节点的数据域之值，则搜索左子树；否则： 4. 查找右子树。 时间复杂度：

四、哈希表法（散列表） 条件：先创建哈希表（散列表） 原理：根据键值方式(Key value)进行查找，通过散列函数，定位数据元素。 时间复杂度：几乎是O(1)，取决于产生冲突的多少。 五、分块查找 原理：将n个数据元素"按块有序"划分为m块（m ≤ n）。 每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字； 而第2块中任一元素又都必须小于第3块中的任一元素，……。 然后使用二分查找及顺序查找。

编程基础之顺序查找

01:查找特定的值 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB 描述 在一个序列（下标从1开始）中查找一个给定的值，输出第一次出现的位置。 输入 第一行包含一个正整数n，表示序列中元素个数。1 <= n <= 10000。 第二行包含n个整数，依次给出序列的每个元素，相邻两个整数之间用单个空格隔开。元素的绝对值不超过10000。 第三行包含一个整数x，为需要查找的特定值。x的绝对值不超过10000。 输出 若序列中存在x，输出x第一次出现的下标；否则输出-1。 5 2 3 6 7 3 3 2

02:输出最高分数的学生姓名 查看 描述 输入学生的人数，然后再输入每位学生的分数和姓名，求获得最高分数的学生的姓名。 输入 第一行输入一个正整数N（N <= 100），表示学生人数。接着输入N行，每行格式如下： 分数姓名 分数是一个非负整数，且小于等于100； 姓名为一个连续的字符串，中间没有空格，长度不超过20。 数据保证最高分只有一位同学。 输出 获得最高分数同学的姓名。 5 87 lilei 99 hanmeimei 97 lily 96 lucy 77 jim hanmeimei 来源 习题(13-1)

03:不高兴的津津 查看 描述 津津上初中了。妈妈认为津津应该更加用功学习，所以津津除了上学之外，还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如果一天上课超过八个小时就会不高兴，而且上得越久就会越不高兴。假设津津不会因为其它事不高兴，并且她的不高兴不会持续到第二天。 请你帮忙检查一下津津下周的日程安排，看看下周她会不会不高兴；如果会的话，哪天最不高兴。 输入 包括七行数据，分别表示周一到周日的日程安排。每行包括两个小于10的非负整数，用空格隔开，分别表示津津在学校上课的时间和妈妈安排她上课的时间。 输出 包括一行，这一行只包含一个数字。如果不会不高兴则输出0，如果会则输出最不高兴的是周几（用1, 2, 3, 4, 5, 6, 7分别表示周一，周二，周三，周四，周五，周六，周日）。如果有两天或两天以上不高兴的程度相当，则输出时间最靠前的一天。 5 3 6 2 7 2 5 3 5 4 0 4 0 6 3

数据结构实现顺序表的各种基本运算(20210215233821)

实现顺序表的各种基本运算 一、实验目的 了解顺序表的结构特点及有关概念，掌握顺序表的各种基本操作算法思想及其实现。 二、实验内容 编写一个程序，实现顺序表的各种基本运算： 1、初始化顺序表； 2 、顺序表的插入； 3、顺序表的输出； 4 、求顺序表的长度 5 、判断顺序表是否为空； 6 、输出顺序表的第i位置的个元素； 7 、在顺序表中查找一个给定元素在表中的位置； 8、顺序表的删除； 9 、释放顺序表 三、算法思想与算法描述简图

主函数main

四、实验步骤与算法实现 #in clude #in clude #defi ne MaxSize 50 typedef char ElemType; typedef struct {ElemType data[MaxSize]; in t le ngth; void In itList(SqList*&L)〃 初始化顺序表 L {L=(SqList*)malloc(sizeof(SqList)); L->le ngth=0; for(i=0;ile ngth;i++) prin tf("%c ",L->data[i]); } void DestroyList(SqList*&L)〃 {free(L); } int ListEmpty(SqList*L)〃 {retur n( L->le ngth==O); } int Listle ngth(SqList*L)〃 {return(L->le ngth); } void DispList(SqList*L)〃 {int i; 释放顺序表 L

顺序查找

《数据结构》实验 题目：顺序查找班级：08计科 学号：10号姓名： #include #define MAX_SIZE 100 typedef struct{ int key; }element; element list[MAX_SIZE]; int seqsearch(element list[],int searchnum,int num); int main() { int i,num,searchnum,k; printf("请输入元素的个数："); scanf("%d",&num); printf("请输入元素：\n"); for(i=0;i

{ int j; list[num].key=searchnum; for(j=0;list[j].key!=searchnum;j++) ; return j #define MAX_SIZE 100 #define COMPARE(a,b) (a)>(b)?1:(a)==(b)?0:-1 typedef struct{ int key; }element; element list[MAX_SIZE]; int binsearch(element list[],int searchnum,int num); int main() { int i,num,searchnum,k; printf("请输入元素的个数："); scanf("%d",&num); printf("请输入元素：\n"); for(i=0;i

各种查找算法的性能比较测试(顺序查找、二分查找)

算法设计与分析各种查找算法的性能测试

目录 摘要 (3) 第一章：简介（Introduction） (4) 1.1 算法背景 (4) 第二章：算法定义（Algorithm Specification） (4) 2.1 数据结构 (4) 2.2顺序查找法的伪代码 (5) 2.3 二分查找（递归）法的伪代码 (5) 2.4 二分查找（非递归）法的伪代码 (6) 第三章：测试结果（Testing Results） (8) 3.1 测试案例表 (8) 3.2 散点图 (9) 第四章：分析和讨论 (11) 4.1 顺序查找 (11) 4.1.1 基本原理 (11) 4.2.2 时间复杂度分析 (11) 4.2.3优缺点 (11) 4.2.4该进的方法 (12) 4.2 二分查找（递归与非递归） (12) 4.2.1 基本原理 (12) 4.2.2 时间复杂度分析 (13) 4.2.3优缺点 (13) 4.2.4 改进的方法 (13) 附录：源代码（基于C语言的） (15) 声明 ................................................................................................................ 错误！未定义书签。

摘要 在计算机许多应用领域中，查找操作都是十分重要的研究技术。查找效率的好坏直接影响应用软件的性能，而查找算法又分静态查找和动态查找。 我们设置待查找表的元素为整数，用不同的测试数据做测试比较，长度取固定的三种，对象由随机数生成，无需人工干预来选择或者输入数据。比较的指标为关键字的查找次数。经过比较可以看到，当规模不断增加时，各种算法之间的差别是很大的。这三种查找方法中，顺序查找是一次从序列开始从头到尾逐个检查，是最简单的查找方法，但比较次数最多，虽说二分查找的效率比顺序查找高，但二分查找只适用于有序表，且限于顺序存储结构。 关键字：顺序查找、二分查找（递归与非递归）

顺序查找

顺序查找 #include #define MAXL 10 typedef int KeyType; typedef struct { KeyType key; }NodeType; typedef NodeType SeqList[MAXL]; int SeqSearch(SeqList R,int n,KeyType k) { int i=0; while(i=n) return -1; else { printf("%d",R[i].key); return i; } } void main(){ SeqList R; int n=10; KeyType k; int a[10],i; printf("输入数字:\n"); for(i=0;i

#include /* INT_MAX等*/ #include /* EOF(=^Z或F6),NULL */ #define OK 1 #define ERROR 0 #define N 5 /* 数据元素个数*/ typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等*/ typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */ typedef int KeyType; /* 设关键字域为整型*/ typedef struct /* 数据元素类型(以教科书图9.1高考成绩为例) */ { long number; /* 准考证号*/ char name[9]; /* 姓名(4个汉字加1个串结束标志) */ int politics; /* 政治*/ int Chinese; /* 语文*/ int English; /* 英语*/ int math; /* 数学*/ int physics; /* 物理*/ int chemistry; /* 化学*/ int biology; /* 生物*/ KeyType key; /* 关键字类型应为KeyType,域名应为key,与bo9-1.c中一致*/ } ElemType; ElemType r[N]={{179324,"何芳芳",85,89,98,100,93,80,47}, {179325,"陈红",85,86,88,100,92,90,45}, {179326,"陆华",78,75,90,80,95,88,37}, {179327,"张平",82,80,78,98,84,96,40}, {179328,"赵小怡",76,85,94,57,77,69,44}}; /* 全局变量*/ #define total key /* 定义总分(total)为关键字*/ #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)<=(b)) typedef struct { ElemType *elem; /* 数据元素存储空间基址，建表时按实际长度分配，0号单元留空*/ int length; /* 表长度*/ }SSTable; Status Creat_Seq(SSTable *ST,int n) { /* 操作结果: 构造一个含n个数据元素的静态顺序查找表ST(数据来自全局数组r) */ int i; (*ST).elem=(ElemType *)calloc(n+1,sizeof(ElemType)); /* 动态生成n个数据元素空间(0号单元不用) */ if(!(*ST).elem) return ERROR; for(i=1;i<=n;i++) *((*ST).elem+i)=r[i-1]; /* 将全局数组r的值依次赋给ST */

数据结构与算法基础知识总结

数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括：（1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构

算法与数据结构的顺序查找

#include"stdio.h" #include"stdlib.h" #include"string.h" #define MAX 31 typedef struct {int*k; int*elem; char*aa; int length; }SSTable; int lw_Search(SSTable ST,int key) { int i; ST.elem[0]=key; for(i=ST.length;ST.elem[i]!=ST.elem[0];--i); return i; } int lw_Search2(SSTable ST,int n,int key) { int low=1;int high=ST.length;int mid,a=0; while(low<=high) { mid=(low+high)/2; printf("第%d次查找:在[%d,%d]中找到元素 ST[%d]: %d\n",++a,low,high,mid,ST.k[mid]); if(ST.k[mid]==key) return mid; else if(ST.k[mid]>key) high=mid-1; else low=mid+1; } return 0; } int lw_bubble(SSTable ST,int n) {int i,j,temp;int*a; for(i=1;iST.k[j]) {

temp=ST.k[i]; ST.k[i]=ST.k[j]; ST.k[j]=temp; } } int lw_prit(SSTable ST,int n) { int i;int*a; for(i=1;ikey) high=mid-1; else low=mid+1; } return 0; } char lw_bubble2(SSTable ST,int n) {int i,j;char temp; for(i=1;i

数据结构与算法-实现顺序表的基本操作

实验报告 课程：数据结构与算法实验日期： 实验名称：实现顺序表的基本操作 一、实验目的 实现顺序表的熟练操作 二、实验内容 （1）先给出顺序表的类型定义 （2）给出顺序表的如下基本操作的算法函数定义 a) 构造一个空的线性表：InitList_Sq(SqList &L) b) 在顺序表L的第i个位置之前插入新的元素e：ListInsert_Sq(SqList &L, int i, ElemType e) c) 在顺序表L中删除第i个元素，并用e返回其值：ListDelete_Sq(SqList &L, int i, ElemType &e) （3）实现如下新操作的函数定义： a) 借助ListInsert_Sq操作创建一个顺序表：ListCreate_Sq(???) b) 计算线性表的长度：ListLength_Sq(???) c) 打印顺序表中的所有元素值：ListPrint_Sq(???) 其中???请自行考虑 （4）在主函数中分别调用ListCreate_Sq、ListPrint_Sq 、ListLength_Sq、ListInsert_Sq、ListDelete_Sq等函数，查看这些函数是否正常工作 三、实验步骤 （1）先给出顺序表的类型定义 （2）给出顺序表的如下基本操作的算法函数定义 a) 构造一个空的线性表：InitList_Sq(SqList &L)

b) 在顺序表L的第i个位置之前插入新的元素e：ListInsert_Sq(SqList &L, int i, ElemType e) c) 在顺序表L中删除第i个元素，并用e返回其值：ListDelete_Sq(SqList &L, int i, ElemType &e)

输出在顺序表{3,6,2,10,1,8,5,7,4,9},中采用顺序方法查找关键字5的过程。

/* 设计一个程序exp9-1.cpp， 输出在顺序表{3,6,2,10,1,8,5,7,4,9} 中采用顺序方法查找关键字5的过程。 */ #include #define MAXL 100 //定义表中最多记录个数 typedef int KeyType; typedef char InfoType[10]; typedef struct { KeyType key; //KeyType为关键字的数据类型InfoType data; //其他数据 } NodeType; typedef NodeType SeqList[MAXL]; //顺序表类型 int SeqSearch(SeqList R,int n,KeyType k) //顺序查找算法 { int i=0; while (i=n) return -1; else { printf("%d",R[i].key); return i; } } void main() { SeqList R; int n=10,i; KeyType k=5; int a[]={3,6,2,10,1,8,5,7,4,9}; for (i=0;i

printf("\n"); printf("查找%d所比较的关键字:\n\t",k); if ((i=SeqSearch(R,n,k))!=-1) printf("\n元素%d的位置是%d\n",k,i); else printf("\n元素%d不在表中\n",k); printf("\n"); }

散列查找顺序表的实现实验报告

题目：顺序表的实现 一、实验题目 顺序表的实现 二、实验目的 ⑴掌握线性表的顺序存储结构； ⑵验证顺序表及其基本操作的实现； ⑶理解算法与程序的关系，能够将顺序表算法转换为对应的程序。 三、实验内容与实现

⑴建立含有若干个元素的顺序表； ⑵对已建立的顺序表实现插入、删除、查找等基本操作。实验实现 #include #include int a[10000]; int arrlong() { int j; for(j=0;j<12;j++) if(a[j]==0) break; return j; } int Insect(int n,int s) ////插入 { int j; for(j=0;j<10000;j++) if(a[j]==0) break; printf("要操作的元素\n"); for(int i=0;in-1;i--) a[i+1]=a[i]; a[n]=s; for(int k=0;k

printf("%d ",a[k]); printf("\n"); } int Search(int p) //查找 { int j,h; for(j=0;j<12;j++) { if(a[j]==0) break; } for(h=0;h

实验一 顺序表的基本运算

实验一顺序表的基本运算 1、实验目的 掌握顺序表的基本操作，初始化、插入、删除以及显示等运算在顺序存储结构上的实现。 2、实验内容 （1）顺序表的初始化； （2）顺序表插入算法的实现； （3）顺序表删除算法的实现； （4）显示顺序表中各个元素； （5）顺序表清空算法的实现； （6）顺序表判空算法的实现； （7）求顺序表长度算法的实现； （8）求顺序表中一个元素前驱算法的实现； （9）求顺序表中一个元素后继算法的实现； （10）求顺序表第i个元素算法的实现。 3、实验要求 （1）能够熟练在Visual C++6.0环境中进行程序的编辑、编译和调试； （2）会书写类C语言的算法，并将算法转变为程序实现。 4、运行程序 #include #include #define MaxSize 100 #define LISTINCREMENT 10 typedef char ElemType; typedef struct{ ElemType *elem; int length; int listsize; }SqList; int InitList_Sq(SqList &L){ L.elem = (ElemType *)malloc(MaxSize*sizeof(ElemType)); if(!L.elem) return 0;

L.length = 0; L.listsize=MaxSize; return 1;} int ListInsert_Sq(SqList &L,int i,ElemType e){ if(i<1||i>L.length+1) return 0; ElemType *p; if(L.length>=L.listsize) { ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(! newbase) return 0; L.elem = newbase; L.listsize += LISTINCREMENT; } ElemType *q=&L.elem[i-1]; for(p=&L.elem[L.length-1];p>=q;--p) *(p+1)=*p; *q=e; ++L.length; return 1;} int ListDelete_Sq(SqList &L,int i,ElemType &e){ if(i<1||i>L.length) return 0; ElemType *p=&(L.elem[i-1]); e=*p; ElemType *q=L.elem+L.length-1; for(++p;p<=q;++p) *(p-1)=*p; --L.length; return 1;} void Disp_Sq(SqList L){ if(L.length==0) printf("此顺序表为空表！\n"); for(int i=0;i

顺序表查找算法的实现

算法与数据结构讲义实验五图的建立及遍历操作 一、实验目的 1.掌握图的存储结构和相关操作。 2.能够熟练用计算机来表示图和进行图处理。 二、实验环境 1.硬件：每个学生需配备计算机一台。操作系统：DOS或Windows; 2.软件：DOS或Windows操作系统+Turbo C; 三、实验要求 1．要求对于给定的图分别用邻接矩阵和邻接表示来存储。 2．对于存储好的图进行深度和广度优先遍历。 3．完成图的各种操作。 四、实验内容 1.现在某网络公司的光纤连接结点如下图所示，请分别用邻接矩阵和邻接表将图存储到计算机中方便进行处理。 2.现在某网络公司的光纤连接结点如下图所示，请分别用邻接矩阵和邻接表将图存储到计算机中方便进行处理。 五、代码如下 第一个实验 #include #include using namespace std; #define MAX 20 typedef int Adj[MAX][MAX]; typedef struct{ string vexs[MAX]; //顶点表 Adj arcs; //邻接矩阵 int vexnum,arcnum; //图的顶点和弧数}MGraph; int ylx_LocateVex(MGraph &G,string u); int ylx_CreateUDN(MGraph &G){ int i,k,j;string v1,v2; cout<<"请输入顶点数、弧数："; cin>>G.vexnum>>G.arcnum; cout<<"输入顶点:"; for(i=0;i>G.vexs[i]; //构造顶点数} for(i=0;i>v1>>v2; i=ylx_LocateVex(G,v1); j=ylx_LocateVex(G,v2); G.arcs[i][j]=1; G.arcs[j][i]=1; //置的对称弧 } return 0;} int ylx_LocateVex(MGraph &G,string u){ //确定u在G中序号 int i; for (i=0;i

实验十二 实现顺序和二分查找算法[管理资料]

实验十二实现顺序和二分查找算法[管理资料] 实验十二实现顺序和二分查找算法姓名:张就班级:09计算机一班学 号:2009111111 一、实验目的 掌握顺序和二分查找算法的基本思想及其实现方法。 二、实验内容 对给定的任意数组(设其长度为n)，分别用顺序和二分查找方法在此数组中查找与给定值k相等的元素。三、算法思想与算法描述 1、顺序查找，在顺序表R[0..n-1]中查找关键字为k的记录，成功时返回找到的记录位置，失败时返回-1，具体的算法如下所示: int SeqSearch(SeqList R,int n,KeyType k) { int i=0; while(i=n) return -1; else { printf("%d",R[i].key);

return i; } } 2、二分查找，在有序表R[0..n-1]中进行二分查找，成功时返回记录 的位置，失败时返回-1，具体的算法如下: int BinSearch(SeqList R,int n,KeyType k) { int low=0,high=n-1,mid,count=0; while(low<=high) { mid=(low+high)/2; printf("第%d次查找:在[ %d ,%d]中找到元素R[%d]:%d\n ",++count,low,high,mid,R[mid].key); if(R[mid].key==k) return mid; if(R[mid].key>k) high=mid-1; else low=mid+1; } return -1; } 四、实验步骤与算法实现 #include #define MAXL 100

数据结构顺序表

实验一顺序表的使用 一、实验目的 1、熟悉配书光盘和C++。 2、熟悉线性表的定义，理解顺序表的基本操作。 3、会使用顺序表的基本操作求解一些实际问题。 二、实验内容 1、上机运行在书中光盘所给程序并理解。 2、编写程序实现顺序表逆置算法。 3、创建2个单调递增的顺序表A，编写算法实现两个表的合并。 三、设计与编码 编写程序实现顺序表的逆置算法 算法设计：（1）定义一个新临时元素 （2）将i元素值赋予临时元素，将q-i元素值赋予首元素，将临时元素值赋予q-i元素。 编码：主函数 #include #include "SeqList.cpp" void Invert(int b[],int q); int main( ) { int i; int a[10]; cout<<"请输入十个数字"<>a[i]; } SeqList list(a,10); cout<<"顺序表的长度为："<

b[q-i-1]=temp; } SeqList list1(b,q); list1.PrintList(); } 四：运行与测试 运行结果： 请输入十个数字 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 顺序表的长度为：10 顺序表的逆置程序： 10 9 8 7 6 5 4 3 2 1 Press any key to continue

第9章 查找练习题及答案

第九章查找 单项选择题 1.顺序查找法适合于存储结构为的线性表。 A. 散列存储 B. 顺序存储或链接存储 C. 压缩存储 D. 索引存储 2.对线性表进行二分查找时，要求线性表必须。 A. 以顺序方式存储 B. 以顺序方式存储，且结点按关键字有序排列 C. 以链接方式存储 D. 以链接方式存储，且结点按关键字有序排列 3.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 4.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为。 A. O(n2) B. O(nlog2n) C. O(n) D. O (logn) 5.二分查找和二叉排序树的时间性能。 A. 相同 B. 不相同 6.有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当二分查找值为82的结点时，次比较后查找成功。 A. 1 B. 2 C. 4 D. 8 7.设哈希表长m=14，哈希函数H(key)=key%11。表中有4个结点： addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7 其余地址为空，如用二次探测再散列处理冲突，关键字为49的结点的地址是。 A. 8 B. 3 C. 5 D. 9 8.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为。 A. 35/12 B. 37/12 C. 39/12 D. 43/12 9.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分个结点最佳地。 A. 10 B. 25 C. 6 D. 625 10.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用查找方法。 A. 分块 B. 顺序 C. 二分 D. 散列 填空题 1.顺序查找法的平均查找长度为；二分查找法的平均查找长度为；分块查找法（以顺序查找确定块）的平均查找长度为；分块查找法（以二分查找确定块）的平均查找长度为；哈希表查找法采用链接法处理冲突时的平均查找长度为。 2.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。 3.二分查找的存储结构仅限于，且是。 4.在分块查找方法中，首先查找，然后再查找相应的。 5.长度为255的表，采用分块查找法，每块的最佳长度是。 6.在散列函数H(key)=key%p中，p应取。 7.假设在有序线性表A[1..20]上进行二分查找，则比较一次查找成功的结点数为，则