数据结构 | 每日一练（66）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1．在输入数据无序的情况下，建立一个数据值为整型的递增有序的顺序存储线性表 L，且要求当输入相同数据值时，线性表中不能存在数据值相同的数据元素，试写出其算法。

顺序存储结构的线性表描述为：

CONST maxlen={线性表可能达到的最大长度}；

TYPE sqlisttp=RECORD

elem:array[1..maxlen] of integer;

last :0..maxlen

END;

VAR L: sqlisttp;

正确答案

ps：||代表注释

[题目分析] 建立递增有序的顺序表，对每个输入数据，应首先查找该数据在顺序表中的位置，若表中没有该元素则插入之，如已有该元素，则不再插入，为此采用折半查找方法。

FUNC BinSearch（ VAR a：sqlisttp；x：integer）：integer；∥在顺序表a中查找值为x的元素，如查找成功，返回0值，如x不在a中，则返回查找失败时的较大下标值。

low:=1；high:=a.last；found:=false；

WHILE（low<=high） AND NOT found DO

[mid:=（low+high） DIV 2；

IF a.elem[mid]=x THEN found:=true

ELSE IF a.elem[mid]>x THEN high:=mid-1 ELSE low:=mid+1；

]

IF found=true THEN return（0）

ELSE return（low）；∥当查找失败时，low=high+1。

ENDF；∥结束对分查找函数。

PROC create（ VAR L：sqlisttp）∥本过程生成顺序表L。

L.last:=0； ∥顺序表L初始化。

read（x）；

WHILE x<>9999 DO ∥设x=9999时退出输入

[k:=binsearch（L，x）；∥去查找x元素。

IF k<>0 ∥不同元素才插入

THEN [ FOR i:=L.last DOWN TO k DO L.elem[i+1]:=L.elem[i]；

L.elem[k]=x；L.last:= L.last+1；∥插入元素x，线性表长度增1

]

read（x）；

]

ENDP；∥结束过程creat