計算機軟件基礎(chǔ)習(xí)題

數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作等等的學(xué)科。

數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運算：查詢、排序、插入、刪除、修改等

線性結(jié)構(gòu)

非線性結(jié)構(gòu)

順序存儲

鏈式存儲線性表棧隊樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面：計算機軟件基礎(chǔ)習(xí)題共16頁，您現(xiàn)在瀏覽的是第1頁!1.回文是指正讀和反讀都相同的字符序列，如“abba”,“abdba”均是回文，“good”不是回文。編寫一個算法判定給定的字符串是否為回文。計算機軟件基礎(chǔ)習(xí)題共16頁，您現(xiàn)在瀏覽的是第2頁!算法描述1將字符串的一半字符壓入棧中，再將其依次彈出與字符串的另一半字符做比較，如果相同則為回文，不相同則不是。這里要考慮串長是奇偶兩種情況。計算機軟件基礎(chǔ)習(xí)題共16頁，您現(xiàn)在瀏覽的是第3頁!算法描述2先將整串字符壓入棧，后將倒序方法用已知字符串的每個字符依次與出棧字符相比。計算機軟件基礎(chǔ)習(xí)題共16頁，您現(xiàn)在瀏覽的是第4頁!算法描述3將已知字符串倒序賦值給另外一個字符串，比較它們整個字符串是否相等。計算機軟件基礎(chǔ)習(xí)題共16頁，您現(xiàn)在瀏覽的是第5頁!2.參考課件P36前序遍歷二叉樹的算法和程序?qū)懗龊笮虮闅v二叉樹的算法及程序(非遞歸)計算機軟件基礎(chǔ)習(xí)題共16頁，您現(xiàn)在瀏覽的是第6頁!VoidPreorder(structnode*t){structnode*p；

structnode*s[max];inttop;top=-1;p=t;do{WHILE(p!=null){printf(“%d”,p->data)；

IF(p->rlink!=null) { top=top+1; s[top]=p->rlink; }p=p->llink;}IF(top！=-1){p=s[top];top=top-1;}}while((p！=null)||(top！=-1))}VoidPostorder(structnode*t){structnode*p，*pre；//pre保存剛訪問過節(jié)點

structnode*s[max];inttop=-1;p=t;pre=null;While(p||top>-1){//沿著左子樹走到最底端while(p!=null) {top=top+1;s[top]=p;p=p->llink; }p=s[top];If((p->rlink==null)||(p->rlink==pre)) {//如果沒有右子樹或者右子樹剛被訪問過

printf(“%d”,p->data)；top=top-1;pre=p;p=null; }Elsep=p->rlink;}}計算機軟件基礎(chǔ)習(xí)題共16頁，您現(xiàn)在瀏覽的是第7頁!思考習(xí)題如何對二叉樹線索化

遍歷二叉樹是以一定規(guī)則將二叉樹的節(jié)點排成一個線性序列，得到二叉樹中節(jié)點的特定序列（前序，中序，后序）。實質(zhì)上是對一個非線性結(jié)構(gòu)進行線性化操作，使每個節(jié)點（除個和最后一個）在這些線性序列中僅有一個直接前驅(qū)和直接后繼。

計算機軟件基礎(chǔ)習(xí)題共16頁，您現(xiàn)在瀏覽的是第8頁!思考習(xí)題解決方法增加兩個標(biāo)志域LTAG=0,Lchild域指向節(jié)點的左子樹LTAG=1,Lchild域指向節(jié)點的前驅(qū)RTAG=0,Rchild域指向節(jié)點的右子樹RTAG=1,Rchild域指向節(jié)點的后繼DATALTAGRTAGRchildLchild計算機軟件基礎(chǔ)習(xí)題共16頁，您現(xiàn)在瀏覽的是第9頁!IntText(char*s){intlenth=strlen(s);//計算字符串長度Inti,j,k;If(lenth%2==0)//長度為偶數(shù){i=lenth/2;for(j=0;j<=i-1;j++)//將前半串字符依次壓棧push(s[j]);for(j=i-1;j>=0;j--)//依次彈出與后半串比較{k=pop(s[j]);if(k!=s[i++])break;}if(j<0)return1;//是回文return0;}else//長度為奇數(shù){i=lenth/2;for(j=0;j<=i-1;j++)//將前半串入棧push(s[j]);i++;//越過串中間字符for(j=i-1;j>=0;j--){k=pop(s[j]);//依次彈出if(k!=s[i++])//進行比較break;}if(j<0)return1;//是回文return0;}}計算機軟件基礎(chǔ)習(xí)題共16頁，您現(xiàn)在瀏覽的是第10頁!inttext(char*s1){charstack[max],k;Inttop=-1;inti;for(i=0;i<strlen(s1);i++) {top=top+1;

stack[top]=s1[i];//入棧 }for(i=strlen(s1)-1;i>=0;i--) { k=stack[top]; top=top-1; if(s1[i]!=k) { break; return0; } else return1; }}計算機軟件基礎(chǔ)習(xí)題共16頁，您現(xiàn)在瀏覽的是第11頁!inttext(char*s1){char*s2=newchar[strlen(s1)];inti;for(i=0;i<strlen(s1);i++)//將字符串倒序賦值 s2[strlen(s1)-1-i]=s1[i]; if(strcmp(s1,s2)) return1; else return0;delete[]s2;}計算機軟件基礎(chǔ)習(xí)題共16頁，您現(xiàn)在瀏覽的是第12頁!算法比較前序遍歷算法1.訪問根節(jié)點2.遍歷左子樹3.遍歷右子樹4.返回后序遍歷算法1.遍歷左子樹2.遍歷右子樹3.訪問根節(jié)點4.返回計算機軟件基礎(chǔ)習(xí)題共16頁，您現(xiàn)在瀏覽的是第13頁!VoidInorder(structnode*t){structnode*p；

structnode*s[max];inttop;top=-1;p=t;do{WHILE(p!=null)/*掃描左節(jié)點*/{top=top+1;s[top]=p;

p=p->llink;}IF(top>=0){p=s[top];/*p所指的節(jié)點為無左子樹或其左子樹已經(jīng)遍歷過*/top=top-1;printf(“%d”,p->data)；/*訪問節(jié)點*/P=p->rlink/*掃描右子樹*/}

while((p！=null)||(top！=-1))}計算機軟件基礎(chǔ)習(xí)題共16頁，您現(xiàn)在瀏覽的是第14頁!思考習(xí)題問題但是二叉樹作為鏈式的存儲結(jié)構(gòu)，只能找到節(jié)點的左右子樹，不能得到節(jié)點在任一序列中的前趨后繼，這種信息只有在遍歷的動態(tài)過程中才能等到。計算機軟件基礎(chǔ)習(xí)題共16頁，您現(xiàn)在瀏覽的是第15頁!思考習(xí)題提示：

if(p->llink!=NULL) p->ltag=0; else { p->ltag=1; p->llink=pre; }//建立P節(jié)點的左線索，指向前趨節(jié)點Pre if(pre!=NULL