试分别画出在线性表(a,b,c,d,e,f,g)中进行折半查找,查找关键字e,和g的过程。

发布网友 发布时间：2022-05-18 19:49

我来回答

共3个回答

热心网友 时间：2023-10-28 07:00

解题如下：

(1)查e

Step1: a b c d e f g

↑ ↑ ↑

low mid high d<e low=mid + 1;

Step2: a b c d e f g

↑ ↑ ↑

low mid high f>e high=mid – 1;

Step 3: a b c d e f g

↑

low/high

mid e==e return mid ;

(2)查f

Step 1: a b c d e f g

↑ ↑ ↑

low mid high d<f low=mid + 1;

Step 2: a b c d e f g

↑ ↑ ↑

low mid high f==f return mid;

(3)查g

Step 1: a b c d e f g

↑ ↑ ↑

low mid high d<g low=mid + 1;

Step 2: a b c d e f g

↑ ↑ ↑

low mid high f<g low=mid + 1;

Step 3: a b c d e f g

↑

low/high

mid g==g return(mid);

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。

线性表是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。

在稍复杂的线性表中，一个数据元素可由多个数据项（item）组成，此种情况下常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。

线性表中的个数n定义为线性表的长度，n=0时称为空表。在非空表中每个数据元素都有一个确定的位置，如用ai表示数据元素，则i称为数据元素ai在线性表中的位序。

线性表的相邻元素之间存在着序偶关系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一个顺序表，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2，…，n-1时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱 。

扩展资料：

线代表存储结构

线性表主要由顺序表示或链式表示。在实际应用中，常以栈、队列、字符串等特殊形式使用。

顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，称为线性表的顺序存储结构或顺序映像。它以“物理位置相邻”来表示线性表中数据元素间的逻辑关系，可随机存取表中任一元素。

链式表示指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。它的存储单元可以是连续的，也可以是不连续的。

在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置），这两部分信息组成数据元素的存储映像，称为结点。它包括两个域；存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链

参考资料：百度百科-线代表

热心网友 时间：2023-10-28 07:01

热心网友 时间：2023-10-28 07:01