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

数据结构

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

——老子

1

每日一练

1．设线性表存于 A[1..size]的前 num 各分量中，且递增有序。请设计一个算法，将 x 插入到线性表的适当位置上，以保持线性表的有序性，并在设计前说明设计思想，最后说明所设计算法的时间复杂度。

类似本题的另外叙述有：

(1) 试编制在线性表 L={12,13,21,24,28,30,42,}中插入数据元素 26 的程序。（要求该程序用 turbo Pascal 语言编制并能在计算机上运行，结点类型为链式结构）

正确答案

ps：||代表注释

1.[题目分析] 在递增有序的顺序表中插入一个元素x，首先应查找待插入元素的位置。因顺序表元素递增有序，采用折半查找法比顺序查找效率要高。查到插入位置后，从此位置直到线性表尾依次向后移动一个元素位置，之后将元素x插入即可。

void Insert（ElemType A[]， int size, ElemType x）∥ A是有size个元素空间目前仅有num（num<size）个元素的线性表。本算法将元素x插入到线性表中，并保持线性表的有序性。

{low=1；high=num； //题目要求下标从1开始

while（low<=high）∥对分查找元素x的插入位置。

{mid=（low+high）/2；

if（A[mid]==x）{low=mid+1； break；}

else if（A[mid]>x）high=mid-1 ； else low=mid+1 ；

}

for（i=num；i>=low；i--） A[i+1]=A[i]；∥元素后移。

A[i+1]=x； ∥将元素x插入。

}算法结束。

[算法讨论] 算法中当查找失败（即线性表中无元素x）时，变量low在变量high的右面（low=high+1）。移动元素从low开始，直到num为止。特别注意不能写成 for（i=low；i<=num；i++）A[i+1]=A[i]，这是一些学生容易犯的错误。另外，题中未说明若表中已有值为x的元素时不再插入，故安排在A[mid]= =x时，用low（=mid+1）记住位置，以便后面统一处理。查找算法时间复杂度为O（logn），而插入时的移动操作时间复杂度为O（n），若用顺序查找，则查找的时间复杂度亦为O（n）。

类似本题的其它题的解答：

（1）[题目分析] 本题与上面15题类似，不同之处是给出具体元素值，且让编写turbo pascal程序，程序如

下：

PROGRAM example（input，output）；

TYPE pointer=^node；

node= RECORD

data：integer；

next：pointer；

END；

VAR head，q：pointer；

PROCEDURE create（ VAR la：pointer）；

VAR x：integer；

p,q：pointer；

BEGIN

new（la）；la^.next:=NIL；{建立头结点。}

read（x）；q:=la；{q用以指向表尾。}

WHILE NOT EOF DO {建立链表}

BEGIN

new（p）；p^.data:=x；p^.next:=q^.next；q^.next:=p；q:=p; read(x);

END；

END；

PROCEDURE insert（ VAR la：pointer；s：pointer）；

VAR p,q：pointer；found：boolean；

BEGIN

p:= la^.next；{p为工作指针。}

q:=la；{q为p的前驱指针。}

found:=false；

WHILE（p<>NIL） AND NOT found

IF（p^.data<x） THEN BEGIN q:=p；p:= p^.next； END

ELSE found:=true；

s^.next:=p；{将s结点插入链表}

q^.next:=s；

END；

BEGIN {main}

writeln（“请按顺序输入数据，建立链表”）

create（head）；

writeln（“请输入插入数据”）

new（q）；

readln（q^.data）；

insert（head，q）；

END.{程序结束}

[程序讨论] 在建立链表时，输入数据依次为12，13，21，24，28，30，42，键入CTRL-Z，输入结束。“插入数据”输26即可。本题编写的是完整的pascal程序。

转发朋友圈，点下“在看”就是对小编的最大帮助！

-end-