数据结构考研分类复习真题 第二章 答案[35]

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

类似本题的其它题的解答

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

PROGRAM example(inputoutput);

TYPE pointer=^node;

node=RECORD

datainteger;

nextpointer;

END;

VAR headqpointer;

PROCEDURE create(VAR lapointer);

VAR xinteger;

pqpointer;

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 lapointer;spointer);

VAR pqpointer;foundboolean;

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(headq);

END{程序结束}

[程序讨论] 在建立链表时输入数据依次为键入CTRLZ输入结束插入数据输即可本题编写的是完整的pascal程序

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []