線性表 - 鏈式存儲結構- 單鏈表的運算（四）

　　單鏈表的查找運算

　　()按序號查找

　　① 鏈表不是隨機存取結構

　　在鏈表中即使知道被訪問結點的序號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