二:鏈表

　　1、知識(shí)點(diǎn)

　　●邏輯次序與物理次序不一致存儲(chǔ)方法；
　　●單鏈表的定義：術(shù)語（頭結(jié)點(diǎn)、頭指針等）
　　●注意帶頭結(jié)點(diǎn)的單鏈表與不帶頭結(jié)點(diǎn)的單鏈表區(qū)別。（程序員考試一般不考帶頭結(jié)點(diǎn)，因?yàn)樯噪y理解）
　　●插入、刪除、遍歷（p==NULL表明操作完成）等操作
　　● 循環(huán)鏈表：定義，存儲(chǔ)表示，操作；
　　● 雙向鏈表：定義，存儲(chǔ)方法，操作；
　　單鏈表和循環(huán)鏈表區(qū)別在最后一個(gè)指針域值不同。

　　2、操作

　　●單鏈表：插入X，刪除X，查找X，計(jì)算結(jié)點(diǎn)個(gè)數(shù)
　　●單鏈表的逆置（中程曾考）
　　head->NULL/p->a1/p->a2/p->a3/p……an/NULL 注：p代表指針;NULL/p代表頭結(jié)點(diǎn)
　　＝》 head->NULL/p->an/p->an-1/p->an-2/p……a1/NULL 
　　●循環(huán)鏈表的操作：插入X，刪除X，查找X，計(jì)算結(jié)點(diǎn)個(gè)數(shù)；
　　　　用p=head->next來判斷一次計(jì)算結(jié)點(diǎn)個(gè)數(shù)完成；

　　程序段如下：
　　k=0;
　　do{
　　　k++;
　　　p=p->next;
　　}while(p!=head->next);
　　● 雙向鏈表
　　●多項(xiàng)式相加
　　● 有序鏈表合并

　　例程：已知兩個(gè)字符串S，T，求S和T的最長公子串；
　　1、邏輯結(jié)構(gòu)：字符串
　　2、存儲(chǔ)結(jié)構(gòu)：數(shù)組
　　3、算法：　精化（精細(xì)化工）**老頑童注：此處“精細(xì)化工”說明好像不對(duì)！
　　s="abaabcacb" 
　　t="abdcabcaabcda"
　　當(dāng)循環(huán)到s.len-1時(shí)，有兩種情況：s="abaabcacb"、s="abaabcacb" 
　　　　　　s.len-2時(shí)，有三種情況：s="abaabcacb"、s="abaabcacb"、s="abaabcacb" 
　　　　　　　.
　　　　　　　.
　　　　　　　.
　　　　　　1 s.len種情況
　　程序思路：
　　tag=0 //沒有找到
　　for(l=s.len;l>0&&!tag;l--) {
　　　判斷長度為l的s中的子串是否為t的子串;
　　　若是：tag=1;
　　}

　　長度為l的s的子串在s中有（s.len-l+1）個(gè)。
　　子串0:　0～l-1
　　　　1:　　　　1～l　　　　　　
　　　　2:　　　　2～l+1　　　　　　
　　　　3:　　　　3～l+2
　　　　　…… 
　　　　　……
　　　　s.len-l:　s.len-l～s.len-1
　　由上面可得：第j個(gè)子串為j～l+j-1。

　　判斷長度為l的s中的子串是否為t的子串:
　　for(j=0;j<s.len-l+1&&!tag;j++){
　　　判斷s中長度為l的第j個(gè)子串是否為t的子串;
　　　如果是：tag=1;
　　}

　　模式結(jié)構(gòu)：
　　tag=0;
　　for(l=s.len;l>0&&tag==0;l--) {
　　　for(j=0;j<s.len-l+1&&!tag;j++) {
　　　　?? 用模式匹配方法確定s[j]～s[l+j-1]這個(gè)字符串是否為t的子串； //好好想想
　　 　 若是，tag=1;
　　　}
　　}

上一頁  [1] [2] [3] [4] [5] [6] [7] [8] [9] 下一頁

轉(zhuǎn)帖于：軟件水平考試_考試吧