熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第二章 答案[35]

2013-11-15 15:23:30  來源: 數據結構 

  [算法討論] 算法中當查找失敗(即線性表中無元素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
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.