【正文】 p=pnext。 if(p==NULL) printf(空表 )。 } void disp(nodetype *h)/*輸出由 h 指向的單鏈表的所有 data 域之值 */ { nodetype *p=h。/*始終指向生成的單鏈表的最后一個(gè)節(jié)點(diǎn) */ } i++。tnext=s。 sdata=d。t=h。 hdata=d。 if(d==0) break。 scanf(%d,amp。 peintf(建立一個(gè)單鏈表 \n)。 nodetype *h=NULL,*s,*t。 }nodetype。/*定義數(shù)據(jù)域的類型 */ typedef struct linknode/*定義節(jié)點(diǎn)類型 */ { elemtype data。 disp(C,nc)。 disp(B,nb)。 disp(A,na)。 int na,nb,nc。 return k。inb。j++) C[k++]=A[j]。 } if(ina)/*A 還有元素 */ for(j=i。 i++。 else if(A[i]B[j]) C[k++]=B[j++]。amp。 } /*習(xí)題 */ /*假設(shè)以兩個(gè)元素依值遞增有序排列的線性表 A和 B分別表示兩個(gè)集合 (即同一表中的元素值各不相同 ),現(xiàn)要求另開辟空間構(gòu)成一個(gè)線性表 C,其元素為 A 和 B 中元素的交集 ,且表 C 中的元素也依值遞增有序排列 .試對(duì)順序表編寫求 C 的算法 */ include int unions(sqlist A,int na,sqlist B,int nb,sqlist C) { int i=0,j=0,k=0。 nc=intersect(A,na,B,nb,C)。 nb=create(B)。 na=create(A)。 } void main() { sqlist A,B,C。j。 8 else/*A[i1]=B[j1]*/ { C[k++]=A[i1]。j=0) if(A[i1]B[j1]) i。 while(i=0amp。 disp(A,n)。 disp(A,n)。 int n。A[ni1]=temp。i++)/*將 A[i]與 A[ni1]進(jìn)行交換 */ { temp=A[i]。 for(i=0。 } /*運(yùn)行結(jié)果： 創(chuàng)建一個(gè)順序表 輸入元素個(gè)數(shù)： 5 輸入第 1 個(gè)元素值： 1 輸入第 1 個(gè)元素值： 2 輸入第 1 個(gè)元素值： 3 輸入第 1 個(gè)元素值： 4 輸入第 1 個(gè)元素值： 5 輸出一個(gè)順序表 1 2 3 4 5 輸入 I,k:2 2 輸出一個(gè)順序表 1 4 5 */ 練習(xí) /*試寫一算法 ,實(shí)現(xiàn)順序表的就地逆置 ,即利用原表的存儲(chǔ)空間將線性表 (a1,a2,...,an)逆置為 (an,an1,...,a1).*/ include 7 void invert(sqlist A,int n) { int m=n/2,i。n,i,k)==1) disp(A,n)。k)。 scanf(%d %d,amp。 disp(A,n)。 int n,i,k。 return 1。j++) A[jk]=A[j]。 } else { for(j=i+k1。 6 if(i0||i+k1*n) { printf(i,k 參數(shù)不正確 \n)。 } getch()。 case 1:printf(AB\n)。 case 1:printf(AB\n)。 switch(n) { case 0:printf(A=B\n)。 nb=create(B)。 int na,nb,n。 else return 1。j==nb) return 1。/*ab*/ if(i!=naamp。amp。j==nb) return 0。 if(i==naamp。/*比較相同部分 */ 5 i。amp。amp。試寫一個(gè)比較 A,B 大小的算法（請(qǐng)注意：在算法中，不要破壞原表 A 和 B，并且，也不一定先求得 A’和 B’才能進(jìn)行比較） */ include int p(sqlist A,int na,sqlist B,int nb) { int i=0,j=0。若 A’=B’=空表，則 A=B。 getch()。 n=insert(A,n,10)。 n=create(A)。/*順序表長(zhǎng)度增 1*/ } void main() { sqlist A。 /*移出插入 x 的位置 */ A[i]=x。j=i。 while(xA[i]) i++。 if(x=A[n1]) A[n]=x。 } 練習(xí) : /*設(shè)順序表 va中的數(shù)據(jù)元素遞增有序。 if(in) return 1。amp。 } int find(sqlist A,int n,elemtype x) /*在一個(gè)有 n 個(gè)元素的順序表 A中查找元素值為 x 的元素 */ { int i=0。 /*將第 i 個(gè)元素之后的元素前移覆蓋 A[i]*/ n。jn。 if(i=0||in) printf(i值下溢或上溢 \n)。/*順序表長(zhǎng)度加 1*/ } return n。 /*將第 i 個(gè)元素及其后的元素后移 */ A[i]=x。j=i。 if(i0||in) printf(i值下溢或上溢 \n)。 printf(\n)。in。 if(n==0) printf(空表 )。 } void disp(sqlist A,int n)/*輸出一個(gè)順序表 */ { int i。A[i])。i++) { printf(輸入第 %d個(gè)元素值 :,i+1)。 for(i=0。 scanf(%d,amp。 printf(創(chuàng)建一個(gè)順序表： \n)。 typedef elemtype sqlist[MaxLen]。 printf(%d %d %d,a,b,c)。b,amp。 swap(amp。b,amp。 scanf(%d,%d,%d,amp。*y=t。 if(*x*y) t=*x。*y=*z。*y=t。 if(*x*y) t=*x。 1 數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) 的的 語語 言言 算算 法法 作者：林慶達(dá) 班級(jí)：計(jì)算機(jī)（ 7）班 學(xué)號(hào)： 80 號(hào) 2 以下數(shù)據(jù)結(jié)構(gòu)算法由 C 語言編譯，并在 TC 上運(yùn)行通過，其中，擴(kuò)展名為 ”.CPP”的為頭文件，運(yùn)行時(shí)只需將頭文件與相應(yīng)算法連接即可。 第一章 緒論（預(yù)備知識(shí)） 練習(xí) /*試寫一算法 ,自大至小輸出順序讀入的三個(gè)整數(shù) X,Y 和 Z的值 */ include void swap(int *x,int *y,int *z) { int t。*x=*y。 if(*y*z) t=*y。*z=t。*x=*y。 } main() {int a,b,c。a,amp。c)。a,amp。c)。 } 第二章 線性表 1．順序表 實(shí)現(xiàn)順序表基本算法的頭文件 為：include define MaxLen 50/*順序表中最多元素個(gè)數(shù) */ typedef int elemtype。 int create(sqlist A)/*創(chuàng)建線形表 */ { int i,n。 printf(輸入元素個(gè)數(shù)： )。n)。in。 scanf(%d,amp。 } return n。 printf(輸出一個(gè)順序表 : \n)。 for(i=0。i++) 3 printf(%d ,A[i])。 } int ins(sqlist A,int n,int i,elemtype x) /*在順序表第 i 個(gè)元素前插入一個(gè)元素 x,若 i=0,則新元素作為 第一個(gè)元素 ,若 i=1,則插入在最后 */ { int j。 else { for(j=n1。j) A[j+1]=A[j]。n++。 } int del(sqlist A,int n,int i) /*在順序表中刪除第 i 個(gè)元素 */ { int j。 else { for(j=i1。j++) A[j]=A[j+1]。 /*順序表長(zhǎng)度減 1*/ } return n。 while(i=namp。A[i]!=x) i++。 else return 0。試寫一算法，將 x 插入到順序表的適當(dāng)位置上，以保持該表的有序性 */ include int insert(sqlist A,int n,elemtype x)/*順序表 A 的長(zhǎng)度為 n*/ { 4 int i,j。 /*若 x 大于最后的元素，則將其插入到最后 */ else { i=0。/*查找插入位置 i*/ for(j=n。j) A[j+1]=A[j]。 } return (n+1)。 int n。 disp(A,n)。/*插入元素 10*/ disp(A,n)。 } /*運(yùn)行結(jié)果： 創(chuàng)建一個(gè)順序表 輸入元素個(gè)數(shù)： 3 輸入第 1 個(gè)元素值： 6 輸入第 1 個(gè)元素值： 9 輸入第 1 個(gè)元素值： 14 輸出一個(gè)順序表 6 9 14 輸出一個(gè)順序表 6 9 10 14 */ 練習(xí) /*設(shè) A=（ a1,… ,am）和 B=(b1,… ,bm)均為順序表， A’和 B’分別為 A和 B 中除去最大共同前綴后的子表（例如， A=（ x,y,y,z,x,z） ,B=(x,y,y,z,y,x,x,z),則兩者中最大的共同前綴為（ x,y,y,z），在兩表中除去最大的共同前綴后的子表分別為 A’=(x,z)和 B’=(y,x,x,z)。若 A’=空表， B’!=空表，或者兩者均不為空表，且 A’的首元小于 B’的首元，則 AB；否則 AB。 while(inaamp。jnbamp。A[i++]==B[j++])。j。amp。/*a=b*/ if(i==naamp。j!=nb) return 1。amp。/*ab*/ if(A[i]B[j]) return 1。 } void main() { sqlist A,B。 na=create(A)。 n=p(A,na,B,nb)。 break。 break。 break。 } /*運(yùn)行結(jié)果 創(chuàng)建一個(gè)順序表 輸入元素個(gè)數(shù)： 3 輸入第 1 個(gè)元素值： 2 輸入第 1 個(gè)元素值： 3 輸入第 1 個(gè)元素值： 5 創(chuàng)建一個(gè)順序表 輸入元素個(gè)數(shù)： 4 輸入第 1 個(gè)元素值： 2 輸入第 1 個(gè)元素值： 3 輸入第 1 個(gè)元素值： 4 輸入第 1 個(gè)元素值： 5 比較結(jié)果： AB */ 練習(xí) /*刪除 A 中第 i 個(gè)元素起的 k 個(gè)元素 */ include int delk(sqlist A,int *n,int i,int k) { int j。 return 0。j*n。 (*n)=k。 } } void main() { sqlist A。 n=create(A)。 printf(輸入 i,k:)。i,amp。 if(delk(A,amp。 getch()。 /*m 為長(zhǎng)度的一半即 [n\2]*/ elemtype temp。im。A[i]=A[ni1]。 } } void main() { sqlist A。 n=create(A)。 invert(A,n)。 } /*運(yùn)行結(jié)果 ： 創(chuàng)建一個(gè)順序表 輸入元素個(gè)數(shù)： 4 輸入第 1 個(gè)元素值： 2 輸入第 1 個(gè)元素值： 6 輸入第 1 個(gè)元素值： 3 輸入第 1 個(gè)元素值： 1 輸出一個(gè)順序表 2 6 3 1 輸出一個(gè)順序表 1 3 6 2 */ 練習(xí) /*假設(shè)有兩個(gè)按元素值遞增有序排列的線性表 A和 B，均以單鏈表做存儲(chǔ)結(jié)構(gòu)，請(qǐng)編寫算法將 A表和 B 表歸并成一個(gè)按元素值遞