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

線性表 - 鏈式存儲結構- 單鏈表的運算(四)

2013-11-15 15:22:10  來源: 數據結構 

  單鏈表的查找運算

  ()按序號查找

  ① 鏈表不是隨機存取結構

  在鏈表中即使知道被訪問結點的序號i也不能像順序表中那樣直接按序號i訪問結點而只能從鏈表的頭指針出發順鏈域

  next逐個結點往下搜索直至搜索到第i個結點為止因此鏈表不是隨機存取結構

  ② 查找的思想方法

  計數器j置為掃描指針p指針從鏈表的頭結點開始順著鏈掃描當p掃描下一個結點時計數器j相應地加當j=i時指針

  p所指的結點就是要找的第i個結點而當p指針指為null且j≠i時則表示找不到第i個結點

  注意

  頭結點可看做是第個結點

  ③具體算法實現

  ListNode* GetNode(LinkList headint i)

  {//在帶頭結點的單鏈表head中查找第i個結點若找到(≤i≤n)

  //則返回該結點的存儲位置否則返回NULL

  int j;

  ListNode *p;

  p=head;j=;//從頭結點開始掃描

  while(p>next&&jnext為NULL或i=j為止

  p=p>next;

  j++;

  }

  if(i==j)

  return p;//找到了第i個結點

  else return NULL;//當i<或i>找不到第i個結點

  }

  ④算法分析

  算法中while語句的終止條件是搜索到表尾或者滿足j≥i其頻度最多為i它和被尋找的位置有關在等概率假設下平均時間復雜度為

  () 按值查找

  ①思想方法

  從開始結點出發順著鏈逐個將結點的值和給定值key作比較若有結點的值與key相等則返回首次找到的其值為key的結點的存儲

  位置;否則返回NULL

  ②具體算法實現

  ListNode* LocateNode (LinkList headDataType key)

  {//在帶頭結點的單鏈表head中查找其值為key的結點

  ListNode *p=head>next;//從開始結點比較表非空p初始值指向開始結點

  while(p&&p>data!=key)//直到p為NULL或p>data為key為止

  p=p>next;//掃描下一結點

  return p;//若p=NULL則查找失敗否則p指向值為key的結點

  }

  ③算法分析

  該算法的執行時間亦與輸入實例中key的取值相關其平均時間復雜度分析類似於按序號查找為O(n)


From:http://tw.wingwit.com/Article/program/sjjg/201311/23307.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.