数据结构
合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下
——老子
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
