[算法討論] 算法中當查找失敗(即線性表中無元素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程序
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23339.html
