当前位置：文档之家 › 数据结构之顺序表元素查找

数据结构之顺序表元素查找

  • 格式：docx
  • 大小：17.76 KB
  • 文档页数：5

下载文档原格式

  / 5

合集下载

数据结构顺序表的查找插入与删除

数据结构顺序表的查找插入与删除
void InsertList(SeqList *L,DataType x,int i);
void DeleteList(SeqList *L,int i);
CreateList(&L,n);/*建立顺序表*/
PrintList(L,n);/*打印顺序表*/
prinnf("%d",&x);
scanf("%d",&i);
DeleteList(&L,i);/*顺序表删除*/
PrintList(L,n);/*打印顺序表*/
}
/*顺序表的建立：*/
void CreateList(SeqList *L,int n)
{
int i;
for(i=0;i<n;i++)
scanf ("%d",&L->data[i]);
{
int i=0;
while (i<L.length && L.data [i]!=x)
++i;
if (i<L.length)
return i+ 1;
else return 0;
}
/*顺序表的插入：*/
void InsertList(SeqList *L,DataType x,int i)
{
int j;
4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。
二、源程序及注释：
#include <stdio.h>
#include <stdlib.h>
/*顺序表的定义：*/
#include<iostream.h>

数据结构——查找,顺序查找,折半查找

数据结构——查找,顺序查找,折半查找

实验五查找的应用一、实验目的：1、掌握各种查找方法及适用场合，并能在解决实际问题时灵活应用。

2、增强上机编程调试能力。

二、问题描述1.分别利用顺序查找和折半查找方法完成查找。

有序表（3,4,5,7,24,30,42,54,63,72,87,95）输入示例：请输入查找元素：52输出示例：顺序查找：第一次比较元素95第二次比较元素87 ……..查找成功，i=**/查找失败折半查找：第一次比较元素30第二次比较元素63 …..2.利用序列（12,7,17,11,16,2,13,9,21,4）建立二叉排序树，并完成指定元素的查询。

输入输出示例同题1的要求。

三、数据结构设计（选用的数据逻辑结构和存储结构实现形式说明）（1）逻辑结构设计顺序查找和折半查找采用线性表的结构，二叉排序树的查找则是建立一棵二叉树，采用的非线性逻辑结构。

（2）存储结构设计采用顺序存储的结构，开辟一块空间用于存放元素。

（3）存储结构形式说明分别建立查找关键字，顺序表数据和二叉树数据的结构体进行存储数据四、算法设计（1）算法列表（说明各个函数的名称，作用，完成什么操作）序号 名称 函数表示符 操作说明1 顺序查找 Search_Seq 在顺序表中顺序查找关键字的数据元素2 折半查找 Search_Bin 在顺序表中折半查找关键字的数据元素3 初始化 Init 对顺序表进行初始化，并输入元素4 树初始化 CreateBST 创建一棵二叉排序树5 插入 InsertBST 将输入元素插入到二叉排序树中6 查找 SearchBST在根指针所指二叉排序树中递归查找关键字数据元素 （2）各函数间调用关系（画出函数之间调用关系）typedef struct { ElemType *R; int length;}SSTable;typedef struct BSTNode{Elem data; //结点数据域 BSTNode *lchild,*rchild; //左右孩子指针}BSTNode,*BSTree; typedef struct Elem{ int key; }Elem;typedef struct {int key;//关键字域}ElemType;（3）算法描述int Search_Seq(SSTable ST, int key){//在顺序表ST中顺序查找其关键字等于key的数据元素。

数据结构_查找原理及典型的查找算法

数据结构_查找原理及典型的查找算法
无法实现！因全部元素的定位只能从头指针head开 始，是一种非随机存取结构。
3.对非线性(树)结构如何进行折半查找？ 可借助二叉排序树来查找（属动态查找表形式）。
9.1.2 有序表的查找
折半查找过程可以描述为一棵二叉树
折半查找的判定树 如：（a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11）
总之：
二叉排序树既有类似于折半查找的特性，又采用了链 表存储，它是动态查找表的一种适宜表示。
一、二叉排序树
（3）构造过程: 例：输入序列{45，12，37，3，53，100，24}
45
12
53
3
37
100
24
一、二叉排序树
（2）非递归查找过程 BiTree SearchBST(BiTree T,KeyType key){
CH9 查找
查找的基本概念 9.1 静态查找表
9.1.1 顺序查找 9.1.2 有序表的查找 9.1.3 索引顺序表的查找
9.2 动态查找表
9.2.1 二叉排序树和平衡二叉树 9.2.2 B－和B＋树
9.3 哈希表
查找的基本概念
1.查找表 2.查找
关键字 主关键字 次关键字
}
9.2.1 二叉排序树和平衡二叉树
一、二叉排序树 二、平衡二叉树
一、二叉排序树
1.定义、特点、构造过程
（1）定义 二叉排序树或者是一棵空树，或是具有下列性质的二叉树：
若左子树非空，则左子树上所有结点的值均小于它的 根结点的值。
若右子树非空，则右子树上所有结点的值均大于它的 根结点的值。
有序/无序表 有序表
顺序/链式存 储
顺序存储
分块查找 介于二者之间 表中元素逐段有序 顺序/链式存储

大学数据结构课件--第9章 查找

大学数据结构课件--第9章 查找
——这种既查找又插入的过程称为动态查找。
二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态 查找表的一种适宜表示。
注：若数据元素的输入顺序不同，则得到的二叉排序树形态 也不同！
17
二、二叉树的插入和删除操作
1、二叉排序树的插入和查找操作
例：输入待查找的关键字序列=（45，24，53，12，90）
折半查找举例：
已知如下11个元素的有序表：
（05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为21和85的数据元素。
Low指向待查元 素所在区间的下 界
mid指向待查元素所在 high指向待查元素所
区间的中间位置
在区间的上界
8
9.1.2 折半查找（又称二分查找或对分查找）
balance。这样，可以得到AVL树的其它性质：
❖ 任一结点的平衡因子只能取：-1、0 或 1；如果树中任 意一个结点的平衡因子的绝对值大于1，则这棵二叉树 就失去平衡，不再是AVL树；
24
三、平衡二叉树
例：判断下列二叉树是否AVL树？
-1
1
-1
0
0
1
0
(a) 平衡树
2
-1
0
0
1
0
(b) 不是平衡树
（1）p为叶子结点，只需修改p双亲f的指针f->lchild=NULL或 f->rchild=NULL
（2）P只有左子树或右子树 ❖ P只有左子树，用P的左孩子代替P ❖ P只有右子树，用P的右孩子代替P
（3）P左、右子树均非空 （P左子树的根C的右子树分支找到S，S的右子树为空） ❖ P的左子树成为双亲f的左子树，P的右子树成为S的右子树 ❖ S的左子树成为S的双亲Q的右子树，用S取代p； 若C无右子树，用C取代p

数据结构：顺序表单元测试与答案

数据结构：顺序表单元测试与答案

一、单选题1、对有14个元素的有序表A[14]作二分查找，查找元素A[3]时，将会与元素依次比较。

A.A[0]，A[1]，A[2]，A[3]B.A[6]，A[2]，A[4]，A[3]C.A[6]，A[4]，A[2]，A[3]D. A[0]，A[13]，A[6]，A[3]正确答案：B2、如果线性表最常用的操作是取第i个结点及其前驱，则采用_____存储方式最节省时间。

A.顺序表B.单向链表C.单向循环链表D.双向链表正确答案：A3、对于顺序存储的长度为n的线性表，在第i个位置插入一个元素需要移动____个元素。

其中，0≤i＜n。

A.n-i+1B.n-iC.iD.n-i-1正确答案：B4、对线性表进行二分查找时，要求线性表必须采用 _____。

A.链式存储，且结点有序排序B.顺序存储，且结点有序排序C.链式存储D.顺序存储正确答案：B5、有一个长度为12的有序表，按二分找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为_____。

A.37/12B.35/12C.39/12D.43/12正确答案：A6、有序数组a[18]进行二分查找时，查找到a[5]的查找路径（下标序列）为_____。

A.8，4，5B.1，3，5C.8，2，5D.8，3，5正确答案：D7、用二分法对数组a[13]进行查找，若待查元素为x，且a[7]<x<a[8]，那么查找路径为____________A.6，9，7B.7，9，8C.6，9，7，8D.6，9，8正确答案：C8、对于顺序存储的长度为n的线性表，删除第i个元素需要移动____个元素。

其中，0≤i＜n。

A.iB.n-i-1C.n-i+1D.n-i正确答案：B9、用二分法对数组a[13]进行查找，在等概率的情况下，查找不成功的平均查找长度为________。

A.49/13B.49/14C.27/7D.54/13正确答案：C10、对a[12]进行二分查找，查找下标为_____的元素时，查找长度最大。

数据结构(八)查找

数据结构(八)查找
122
99
250
110
300
280
类C程序实现： void InsertBST(*&t，key) //在二叉排序树中插入查找关键字key { if(t= = NULL){ t=new BiTree; t->lchild=t->rchild=NULL; t->data=key; return; } if(key<t->data ) InsertBST(t->lchild,key); else InsertBST (t->rchild, key ); } void CreateBiTree(tree,d[ ],n） //n个数据在数组d中，tree为二叉排序树根 { tree=NULL; for(i=0;i<n;i++) InsertBST(tree,d[i]); }
p q
void delete(*&p) { if(p->rchild = = NULL) { q=p; p=p->lchild; delete q; } else if(p->lchild= =NULL) { q=p; p=p->rchild; delete q; } else { q=p; s=p->lchild; while(s->rchild!=NULL) {q=s; s=s->rchild;} p->data=s->data; if(q!=p) q->rchild=s->lchild; else q->lchild=s->lchild; } delete s; }
在xL中选值最大的代替x，该数据按二叉排序树的性质应在 最右边。
f x f s c

数据结构实验一顺序表

数据结构实验一1、实验目的∙掌握线性表的逻辑特征∙掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算2、实验内容：建立顺序表，完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、查找元素、判线性表是否为空；1．问题描述：利用顺序表,设计一组输入数据（假定为一组整数），能够对顺序表进行如下操作：∙创建一个新的顺序表，实现动态空间分配的初始化；∙根据顺序表结点的位置插入一个新结点(位置插入)，也可以根据给定的值进行插入(值插入)，形成有序顺序表；∙根据顺序表结点的位置删除一个结点(位置删除)，也可以根据给定的值删除对应的第一个结点，或者删除指定值的所有结点(值删除)；∙利用最少的空间实现顺序表元素的逆转；∙实现顺序表的各个元素的输出；∙彻底销毁顺序线性表，回收所分配的空间；∙对顺序线性表的所有元素删除，置为空表；∙返回其数据元素个数；∙按序号查找，根据顺序表的特点，可以随机存取，直接可以定位于第i 个结点，查找该元素的值，对查找结果进行返回；∙按值查找，根据给定数据元素的值，只能顺序比较，查找该元素的位置，对查找结果进行返回；∙判断顺序表中是否有元素存在，对判断结果进行返回；.编写主程序，实现对各不同的算法调用。

2．实现要求：∙“初始化算法”的操作结果：构造一个空的顺序线性表。

对顺序表的空间进行动态管理，实现动态分配、回收和增加存储空间；∙“位置插入算法”的初始条件：顺序线性表L 已存在，给定的元素位置为i，且1≤i≤ListLength(L)+1 ；操作结果：在L 中第i 个位置之前插入新的数据元素e，L 的长度加1；∙“位置删除算法”的初始条件：顺序线性表L 已存在，1≤i≤ListLength(L) ；操作结果：删除L 的第i 个数据元素，并用e 返回其值，L 的长度减1 ；∙“逆转算法”的初始条件：顺序线性表L 已存在；操作结果：依次对L 的每个数据元素进行交换，为了使用最少的额外空间，对顺序表的元素进行交换；∙“输出算法”的初始条件：顺序线性表L 已存在；操作结果：依次对L 的每个数据元素进行输出；∙“销毁算法”初始条件：顺序线性表L 已存在；操作结果：销毁顺序线性表L；∙“置空表算法”初始条件：顺序线性表L 已存在；操作结果：将L 重置为空表；∙“求表长算法”初始条件：顺序线性表L 已存在；操作结果：返回L 中数据元素个数；∙“按序号查找算法”初始条件：顺序线性表L 已存在，元素位置为i，且1≤i≤ListLength(L)操作结果：返回L 中第i 个数据元素的值∙“按值查找算法”初始条件：顺序线性表L 已存在，元素值为e；操作结果：返回L 中数据元素值为e 的元素位置；∙“判表空算法”初始条件：顺序线性表L 已存在；操作结果：若L 为空表，则返回TRUE，否则返回FALSE；分析: 修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。

数据结构顺序查找与折半查找

数据结构顺序查找与折半查找1，顺序查找顺序查找⼜称线性查找，它对顺序表和链表都适⽤。

（1）以下给出相关函数1 typedef struct{2 ElemType *elem; //元素存储空间地址，建表时按实际长度分配，0号单元留空3int TableLen; //表的长度4 }SSTable;5int Search_Seq(SSTable ST,ElemType key)6 {7 ST.elem[0]=key; //把要查找的关键字放在0号位置，称“哨兵”8for(int i=ST.TableLen;ST.elem!=key;i--) //从后往前找9 {10return i; //若表中不存在关键字为key的元素，将查找i=0时退出循环11 }12 }在上述算法中，将ST.elem[0]称为“哨兵”。

引⼊它的⽬的是使得Search_Seq内的循环不必判断数组是否会越界。

因为满⾜i=0时，循环⼀定会跳出。

除此之外，引⼊“哨兵”可以避免很多不必要的判断语句，从⽽提⾼算法的执⾏效率。

（2）算法效率分析当每个元素查找概率相同时，平均查找长度ASL=（n+1)/2, 查找不成功时，需要⽐较整个顺序表，所以⽐较次数时（n+1)次，从⽽顺序查找不成功的平均查找长度为(n+1)。

2.有序表的顺序查找（假设从⼩到⼤排列）有序表的顺序查找成功的平均查找长度与⼀般的线性表⼀样，即（n+1)/2.当查找失败时，待查找的元素为key,当查找第i个元素时，发现第i个元素的对应的关键字⼩于key,但第i+1个元素对应的关键字⼤于key,这时就可以返回查找失败的信息。

查找失败的平均查找长度为ASL=n/2+n/(n+1).3.折半查找前提：折半查找仅适⽤于有序的顺序表。

折半查找原理：将给定的key与中间元素⽐较，直到查到要找的元素。

以下是相关函数1int Binary_Search(SeqList L,ElemType key){2int low=0,high=L.TableLen-1,mid;//low指向表头，high指向表尾，mid中间值3while(low<=high)4 {5 mid=(low+high)/2;6if(L.elem[mid]==key) //中间值等于要查找元素7return mid;8else if(L.elem[mid]<key) //要查找元素在中间值右边9 low=mid+1;10else11 hign=mid-1; //要查找元素在中间值左边12 }13 }查找成功的时间复杂度为log2n，平均情况下⽐顺序查找效率⾼⼀些。

数据结构中顺序表的基本操作

数据结构中顺序表的基本操作
顺序表是一种线性表的存储结构，使用一组连续的存储单元来存储元素，其基本操作包括：
1. 初始化：创建一个空顺序表，设置其长度为0。

2. 插入元素：在顺序表的指定位置插入一个元素，需要将插入位置之后的元素依次向后移动，然后将新元素放入插入位置，并更新顺序表的长度。

3. 删除元素：删除顺序表中的指定位置的元素，需要将删除位置之后的元素依次向前移动，然后更新顺序表的长度。

4. 查找元素：根据元素的值，查找顺序表中第一个与该值相等的元素，并返回其位置。

如果不存在，则返回-1。

5. 获取元素：根据位置，返回顺序表中指定位置的元素。

6. 修改元素：根据位置，修改顺序表中指定位置的元素。

7. 清空顺序表：将顺序表的长度设置为0，即清空元素。

这些基本操作可以根据具体需求进行使用和扩展。

数据结构的实验报告

一、实验目的本次实验旨在让学生掌握数据结构的基本概念、逻辑结构、存储结构以及各种基本操作，并通过实际编程操作，加深对数据结构理论知识的理解，提高编程能力和算法设计能力。

二、实验内容1. 线性表（1）顺序表1）初始化顺序表2）向顺序表插入元素3）从顺序表删除元素4）查找顺序表中的元素5）顺序表的逆序操作（2）链表1）创建链表2）在链表中插入元素3）在链表中删除元素4）查找链表中的元素5）链表的逆序操作2. 栈与队列（1）栈1）栈的初始化2）入栈操作3）出栈操作4）获取栈顶元素5）判断栈是否为空（2）队列1）队列的初始化2）入队操作3）出队操作4）获取队首元素5）判断队列是否为空3. 树与图（1）二叉树1）创建二叉树2）遍历二叉树（前序、中序、后序）3）求二叉树的深度4）求二叉树的宽度5）二叉树的镜像（2）图1）创建图2）图的深度优先遍历3）图的广度优先遍历4）最小生成树5）最短路径三、实验过程1. 线性表（1）顺序表1）初始化顺序表：创建一个长度为10的顺序表，初始化为空。

2）向顺序表插入元素：在顺序表的第i个位置插入元素x。

3）从顺序表删除元素：从顺序表中删除第i个位置的元素。

4）查找顺序表中的元素：在顺序表中查找元素x。

5）顺序表的逆序操作：将顺序表中的元素逆序排列。

（2）链表1）创建链表：创建一个带头结点的循环链表。

2）在链表中插入元素：在链表的第i个位置插入元素x。

3）在链表中删除元素：从链表中删除第i个位置的元素。

4）查找链表中的元素：在链表中查找元素x。

5）链表的逆序操作：将链表中的元素逆序排列。

2. 栈与队列（1）栈1）栈的初始化：创建一个栈，初始化为空。

2）入栈操作：将元素x压入栈中。

3）出栈操作：从栈中弹出元素。

4）获取栈顶元素：获取栈顶元素。

5）判断栈是否为空：判断栈是否为空。

（2）队列1）队列的初始化：创建一个队列，初始化为空。

2）入队操作：将元素x入队。

3）出队操作：从队列中出队元素。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

数据结构--顺序表查找#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
int data[MAXSIZE];
int len;
typedef struct
{
int data[MAXSIZE];
int len;
} SeqList;
SeqList *Init_SeqList( )
{
SeqList *L;
L=(SeqList*)malloc(sizeof(SeqList));
L->len= -1;
return L;
}
//顺序查找
int SearchSeq(SeqList *S,int t)
{
int i;
for(i=0;i<S->len;i++)
if(t==S->data[i])
{
return i;
break;
}
if(i==S->len)
return -1;
}
//对顺序表进行排序
SeqList *Sort(SeqList *S)
{
int temp,i,j;
for (i=0;i<s->len;i++)
{
for (j=i+1;j<s->len;j++)
if(S->data[j]>S->data[j+1])
{
temp=S->data[j];S->data[j]=S->data[j+1];S->data[j+1]=temp;
}
}
for(int k=0;k<S->len;k++)
{
printf("%d ",S->data[k]);
}
return S;
}
//折半查找
int SearchBin(SeqList *S ,int t)
{
int mid,low=0,high=S->len-1;
while(low<=high)
{
mid=(low+high)/2;
if(t==S->data[mid])
return mid;
else if(t>S->data[mid]) low=mid+1;
else high=mid-1;
}
return -1;
}
int main()
{
SeqList *L=Init_SeqList();
int t1,t2,len,e;
printf("请输入顺序表的长度");
scanf("%d",&L->len);
printf("请输入顺序表中各元素:\n");
getchar();
for(int k=0;k<L->len;k++)
{
scanf("%d",&e);
L->data[k]=e;
}
printf("请输入要查找的数:\n");
scanf("%d",&t1);
int m=SearchSeq(L,t1);
if(m>-1)
printf("该查找的数顺序查找后在顺序表中的位置为%d:\n",m+1); else printf("该数没有找到\n");
printf("排序之后的顺序表");
SeqList*S=Sort(L);
printf("请输入要查找的数:\n");
scanf("%d",&t2);
int s=SearchBin(S ,t2);
if(s>-1)
printf("该查找的数折半查找后在顺序表中的位置为%d:\n",s+1); else printf("该数没有找到\n");
return 0;
}。