單鏈表的查找運算

（）按序號查找
① 鏈表不是隨機存取結構
　在鏈表中即使知道被訪問結點的序號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&&j<i){//順指針向後掃描直到p>next為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/23269.html