【正文】 1 實驗一、順序表逆置和單鏈表逆置 問題的提出 設(shè)有一個線性表 E={e1, e2, … , e n1, en}，設(shè)計一個算法，將線性表逆置，即使元素排列次序顛倒過來，成為逆線性表 E’={ en , en1 , … , e 2 , e1 }，要求逆線性表占用原線性表空間，并且用順序表和單鏈表兩種方法表示，分別用兩個程序來完成。 ? 順序表逆置 算法分析 Step1： 將順序表位置 i的元素與位置 Llasti+1 的元素進行互換； Step2： 重復(fù) Step1，直到 i=Llast/2，結(jié)束 。 問題的程序代碼 //順序表逆置 void invert(sequenlist*L) { int i。 datatype temp。 //定義 i和 temp 的類型 for(i=1。i=Llast/2。i++)//for 循環(huán)語句，其中的 Llast/2 當 Llast 為奇數(shù)時，相當于向下取整 {temp=Ldata[i]。 Ldata[i]=Ldata[Llasti+1]。 Ldata[Llasti+1]=temp。//將位置 i和位置 Llasti+1 的元素進行互換 } } 運行結(jié)果 存在的問題 逆置表中的元素只能是單個元素，不能進行多位數(shù)的逆置，如下圖所示 2 ? 單鏈表逆置 算法分析 Step1： 將 p 指針指向頭結(jié)點， q 指針指向頭結(jié)點的下一個結(jié)點； Step2：將 p 和 q 逆置，并將它們分別后移一個結(jié)點； Step3：重復(fù) Step1~ Step2，直到指針 r 指向空域，結(jié)束。 問題的程序代碼 //單鏈表逆置 void invert(linklist *head) { linklist *p,*q,*r。 p=headnext。//p 指針指向頭結(jié)點 q=pnext。 //q 指針指向頭結(jié)點的下一個結(jié)點 while(q!=NULL)//當 q 指針非空時，進行 while 循環(huán) {r=qnext。 qnext=p。//將 r 指針指向 q 的下一個結(jié)點，而 q 指針指向 p p=q。 q=r。//將 p 指針指向 q， q 指針指向 r，實現(xiàn) p 和 q 的逆置 } headnextnext=NULL。//原鏈表的第一個結(jié)點指針置空，變?yōu)樾骆湵淼奈步Y(jié)點 headnext=p。// 原鏈表最后一個結(jié)點變?yōu)樾骆湵淼念^結(jié)點 } 運行結(jié)果 存在的問題 與順序表逆置一樣， 逆置表中的元素只能是單個元素，不能進行多位數(shù)的逆置，如下圖所示 3 實驗二、分解單鏈表 問題的提出 已知由不具有頭結(jié)點的單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素（字母、數(shù)字和其他字符），試編寫算法構(gòu)造三個以循環(huán)鏈表表示的線性表，使每個表中只含有同一類的字符，且利用原表中的結(jié)點空間， 頭結(jié)點可另辟空間。 算法分析 Step1： 將單鏈表中的頭結(jié)點與字母比較，判斷是否在 [A,Z]或者 [a,z]之間； Step2：在 [A,Z]或者 [a,z]之間，則將它寫入字母的單鏈表中 ,否則轉(zhuǎn) Step3； Step3： 將單鏈表中的頭結(jié)點與字母比較，判斷是否在 [0,9]之間； Step4：在 [0,9]之間，則將它寫入數(shù)字的單鏈表中否則轉(zhuǎn) Step5； Step5： 將它寫入其他字符的單鏈表中； Step6：取下一結(jié)點，重復(fù) Step1~ Step5，直到結(jié)點完全進入 3 個新的單鏈表，結(jié)束。 問題的程序代 碼 //按字母、數(shù)字、其它字符分解單鏈表 void resolve(linklist*head,linklist*letter,linklist*digit,linklist*other) { linklist *p。 while(headnext!=NULL) { p=headnext。//p 指針指向頭結(jié)點 headnext=headnextnext。 if((pdata=39。A39。amp。amp。pdata=39。Z39。)||(pdata=39。a39。amp。amp。pdata=39。z39。)) insert(letter,p)。 //判斷字符是否在 [A,Z]或者 [a,z]之間，是，插入第一個單鏈表中 else if(pdata=39。039。amp。amp。pdata=39。939。) insert(digit,p)。 else insert(other,p)。 //判斷字符是否在 [0,9]，是，插入第二個單鏈表中；否，插入第三個單鏈表中 } } 4 運行結(jié)果 存在的問題 此處的其他字符還包括了子母和數(shù)字以外的一切 字符，且此處的數(shù)字不能為多位數(shù)或者字符串，本程序不能識別 10 以上的數(shù)字及一個單詞的字符串，如下圖所示 實驗三、判斷字符串是否中心對稱 問題的提出 設(shè)單鏈表中存放有 n個字符，試編寫算法，判斷該字符串是否有中心對稱的關(guān)系，例如 xyzzyx 是中心對稱的字符串。（提示：將單鏈表中的一半字符先依次進棧，然后依次出棧與單鏈表中的另一半字符進行比較。） 算法分析 Step1： 將字符串中的前一半字符入 棧 ，并且將其與后一半的字符進行比較判定； Step2：當 字符串的長度為奇數(shù)時，將 p指針向后移一位，重復(fù) Step1，結(jié)束 。 問題的程序代碼 //判字符串是否中心對稱 int symmetry(linklist*head,stack*s) { int i,n。 linklist*p=headnext。 n=length(head)。//n 表示字符串的長度 datatype j。 for(i=1。in/2。i++) //當 p 非空時，將一半字符串入棧 {push(s,pdata)。 5 p=pnext。 } if(n%2==1) p=pnext。 //若字符串長度是奇 數(shù)，指針 p 從向后移一位 while(p!=NULL) //判斷字符串出棧與另外一半字符串比較是否相等，相等返回 1，否則返回 0 {j=pop(s)。 if(j!=pdata) //j 與 p 中的元素不相等時返回 1 return 1。 else p=pnext。 } return 0。 } 運行結(jié)果 ? 字符串不是中心對稱時結(jié)果 ? 字符串是中心對稱時結(jié)果 存在的問題 注意字符串長度為奇數(shù)時的判定即可。 實驗四、循環(huán)隊列 問題的提出 假設(shè)以數(shù)組 sequ[m]存放 循環(huán)隊列的元素，同時設(shè)變量 rear 和 quelen 分別指示循環(huán)隊列中隊尾元素的位置和內(nèi)含元素的個數(shù)。編寫實現(xiàn)該循環(huán)隊列的入隊和出隊操作的算法。提示：隊空的條件： sqquelen==0；隊滿的條件： sqquelen==m。 算法分析 Step1：先進行入隊操作，判斷是否隊滿，隊未滿時將 x 入隊尾； 6 Step2：再進行出隊操作，判斷是否隊空，隊列非空時將隊頭元素出隊 。 問題的程序代碼 //入隊 void enqueue(qu *sq, datatype x) { if(sqquelen==m) printf(queue is full\n)。//隊列上溢 else { sqquelen++。 sqrear=(sqrear+1)%m。 sqsequ[sqrear]=x。//隊列未滿時，將 x入隊尾 } } //出隊 datatype *dequeue(qu *sq) { datatype *temp。 if(sqquelen==0) { printf(queue is empty\n)。 return NULL。} //隊列 為空 else