數(shù)據(jù)結構之線性表和樹

1、1065865姓名姓名 學號學號 成績成績 班級班級 李紅李紅 9761059 95 機機97.6 ABCDEFG2022-5-152 1數(shù)據(jù)的邏輯結構 2、數(shù)據(jù)的存儲結構 3、數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等。 A線性結構 B非線性結構A 順序存儲 B 鏈式存儲 線性表棧隊樹形結構圖形結構數(shù)據(jù)結構的三個主要問題 2022-5-153線性結構線性結構 A , B , C , ，X ,Y , Z學 生 成 績 表86胡孝臣986110395劉忠賞9861107100張卓9861109成績姓名學號線性表線性表結點間是以線性關系聯(lián)結結點間是以線性關系聯(lián)結2022-5-154 1數(shù)據(jù)的邏輯結

2、構 2、數(shù)據(jù)的存儲結構 3、數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等。 A線性結構 B非線性結構A 順序存儲 B 鏈式存儲 線性表棧隊樹形結構圖形結構數(shù)據(jù)結構的三個方面 2022-5-155樹形結構樹形結構全校學生檔案管理的組織方式全校學生檔案管理的組織方式2022-5-156ABCDEFGH樹形結構 結點間具有分層次的連接關系HBCDEFGA2022-5-1572.5 樹樹2.5.1 樹的定義：由一個或多個結點組成的有限集合樹的定義：由一個或多個結點組成的有限集合。僅有僅有一個根結點，結點間有明顯的層次結構關系。一個根結點，結點間有明顯的層次結構關系。 A C G T2D H I T3J

3、M B E L KT1 F現(xiàn)實世界中，能用樹的結構表示的例子：現(xiàn)實世界中，能用樹的結構表示的例子：學校的行政關系、書的層次結構、人類的家族血緣關學校的行政關系、書的層次結構、人類的家族血緣關系等。系等。2022-5-158介紹幾個概念：介紹幾個概念：結點（結點（Node）：樹中的元素，包含數(shù)據(jù)項及若干指向其）：樹中的元素，包含數(shù)據(jù)項及若干指向其子樹的分支。子樹的分支。結點的度（結點的度（Degree）：結點擁有的子樹數(shù)。）：結點擁有的子樹數(shù)。結點的層次：從根結點開始算起，根為第一層。結點的層次：從根結點開始算起，根為第一層。葉子（葉子（Leaf）：度為零的結點，也稱端結點。）：度為零的結點，也

4、稱端結點。孩子（孩子（Child）：結點子樹的根稱為該結點的孩子結點。）：結點子樹的根稱為該結點的孩子結點。兄弟（兄弟（Sibling）：同一雙親的孩子。）：同一雙親的孩子。雙親（雙親（Parent）：孩子結點的上層結點，稱為這些結點的）：孩子結點的上層結點，稱為這些結點的雙親。雙親。深度（深度（Depth)： 樹中結點的最大層次數(shù)。樹中結點的最大層次數(shù)。森林（森林（Forest）：）：M棵互不相交的樹的集合?？没ゲ幌嘟坏臉涞募稀?A C G T2D H I T3J M B E L KT1 F2022-5-1592.5.2 二叉樹二叉樹 （Binary Tree）1 、二叉樹的定義及其性質、

5、二叉樹的定義及其性質 (1) 二叉樹的定義二叉樹的定義二叉樹的五種基本形態(tài)二叉樹的五種基本形態(tài)二叉樹一種特殊的樹型結構，特點是樹中每個結點只有兩棵二叉樹一種特殊的樹型結構，特點是樹中每個結點只有兩棵子樹，且子樹有左右之分，次序不能顛倒。子樹，且子樹有左右之分，次序不能顛倒。 空二叉樹空二叉樹 僅有僅有根結點根結點 右子樹右子樹為空為空 左子樹左子樹為空為空左右子樹左右子樹均非空均非空因為樹的每個結點的度不同，存儲困難，使對樹的處理算法因為樹的每個結點的度不同，存儲困難，使對樹的處理算法很復雜。所以引出二叉樹的討論。很復雜。所以引出二叉樹的討論。2022-5-1510 二叉數(shù)是二叉數(shù)是n(nn(

6、n 0)0)個結點的有限集合。它或為空個結點的有限集合。它或為空數(shù)數(shù)(n=0),(n=0),或由一個根結點和兩棵分別稱為根的左子或由一個根結點和兩棵分別稱為根的左子樹和右子樹的互不相交的二叉數(shù)組成。樹和右子樹的互不相交的二叉數(shù)組成。 特別要注意：特別要注意：二叉數(shù)不是二叉數(shù)不是樹的特殊情況。樹的特殊情況。a aa ab bb b兩棵不同的二叉數(shù)兩棵不同的二叉數(shù)2022-5-1511A、 二叉樹的第i層上至多有2 i-1（i 1）個結點。(2) 二叉樹的基本性質二叉樹的基本性質423167891011121314155第三層上第三層上( (i=3)i=3)，有，有2 23-13-1=4=4個節(jié)點

7、。個節(jié)點。第四層上第四層上( (i=4)i=4)，有，有2 24-14-1=8=8個節(jié)點。個節(jié)點。2022-5-1512A、 二叉樹的第i層上至多有2 i-1（i 1）個結點。 B、 深度為h的二叉樹中至多含有2h-1個結點。(2) 二叉樹的基本性質二叉樹的基本性質423167891011121314155此樹的深度此樹的深度h=4h=4，共有，共有2 24 4-1=15-1=15個節(jié)點。個節(jié)點。2022-5-1513A、 二叉樹的第i層上至多有2 i-1（i 1）個結點。B、 深度為h的二叉樹中至多含有2h-1個結點。C、 若在任意一棵二叉樹中，有n0個葉子結點， 有n2個度為2的結點，則：

8、n0=n2+1(2) 二叉樹的基本性質二叉樹的基本性質423167891011121314155n n0 0=8=8n n2 2=7=72022-5-1514（3）滿二叉樹）滿二叉樹423167891011121314155特點：每一層上都含有最大結點數(shù)。特點：每一層上都含有最大結點數(shù)。2022-5-15154231678910 11125 非完全二叉樹非完全二叉樹（4）完全二叉樹4231678910 11125 完全二叉樹完全二叉樹特點：除最后一層外，每一層都取最大結點數(shù)，特點：除最后一層外，每一層都取最大結點數(shù)，最后一層結點都集中在該層最左邊的若干位置。最后一層結點都集中在該層最左邊的若干

9、位置。2022-5-1516（5）樹與二叉樹的區(qū)別）樹與二叉樹的區(qū)別A樹的結點個數(shù)至少為樹的結點個數(shù)至少為1，而二叉樹的結點個數(shù)可以為，而二叉樹的結點個數(shù)可以為0。B樹中結點的最大度數(shù)沒有限制，二叉樹結點最大度數(shù)為樹中結點的最大度數(shù)沒有限制，二叉樹結點最大度數(shù)為2。C樹的結點無左、右之分，二叉樹的結點子樹有明確的左、右之分。樹的結點無左、右之分，二叉樹的結點子樹有明確的左、右之分。 樹 二叉樹2022-5-1517性質性質1：二叉樹的第二叉樹的第i層上至多有層上至多有2 i-1（i 1）個結點。個結點。證明：根據(jù)二叉樹的特點，結論是顯然的。證明：根據(jù)二叉樹的特點，結論是顯然的。性質性質2：深度

10、為深度為h的二叉樹中至多含有的二叉樹中至多含有2h-1個結點。個結點。證明：深度為證明：深度為m的二叉樹最多有的二叉樹最多有m層，根據(jù)性質層，根據(jù)性質1，只要將第，只要將第1層到第層到第m層的最大結點數(shù)相加，就可得到整個二叉樹中結點的層的最大結點數(shù)相加，就可得到整個二叉樹中結點的最大值。最大值。21-1 + 2 2-1+ 2 m-1 = 2 m-1 性質性質3：度為：度為0的結點總比度為的結點總比度為2的結點多一個。的結點多一個。設：有設：有n0個葉子結點，有個葉子結點，有n1個度為個度為1的結點，有的結點，有n2個度為個度為2的結點，的結點， 則二叉樹中結點總數(shù)為則二叉樹中結點總數(shù)為：n=n

11、0+n1+ n2 設所有進入分支的總數(shù)為設所有進入分支的總數(shù)為m,則總的結點個數(shù)為：則總的結點個數(shù)為：n=m+1總的射出分支與總的進入分支數(shù)相等：總的射出分支與總的進入分支數(shù)相等：m= n1+2 n2 因此：因此： n0+n1+ n2 = n1+2 n2 +1 所以：所以： n0= n2+1 2022-5-1518（5）樹與二叉樹的區(qū)別）樹與二叉樹的區(qū)別A 樹的結點個數(shù)至少為樹的結點個數(shù)至少為1，而二叉樹的結點個數(shù)可以為而二叉樹的結點個數(shù)可以為0。B樹中結點的最大度數(shù)沒有限制，二叉樹結點最大度數(shù)為樹中結點的最大度數(shù)沒有限制，二叉樹結點最大度數(shù)為2。C樹的結點子樹無左、右之分，二叉樹的結點子樹有

12、明確的左、樹的結點子樹無左、右之分，二叉樹的結點子樹有明確的左、 右之分。右之分。 二叉樹二叉樹樹樹2022-5-15192、二叉樹的存儲結構、二叉樹的存儲結構 (2) 鏈式存儲結構鏈式存儲結構T16若父結點在數(shù)組中若父結點在數(shù)組中i下標處，其左孩子在下標處，其左孩子在2*i處，右孩子在處，右孩子在2*i+1處。處。11 A B c F E D 1 2 4 8 910 5 6 3 712131415(1) 順序存儲結構順序存儲結構(1) 順序存儲結構順序存儲結構2h-1= 24-1 = 15用一組連續(xù)的存儲單元存放二叉樹用一組連續(xù)的存儲單元存放二叉樹的數(shù)據(jù)元素。結點在數(shù)組中的相對的數(shù)據(jù)元素。結

13、點在數(shù)組中的相對位置蘊含著結點之間的關系。位置蘊含著結點之間的關系。0000FE000DC0BA15141312111098765432100一般二叉樹必須按完全二叉樹的形式存儲，將造成存儲的浪費。一般二叉樹必須按完全二叉樹的形式存儲，將造成存儲的浪費。2022-5-1520(2) 鏈式存儲結構鏈式存儲結構lchildDatarchildADBCEF圖為一般二叉圖為一般二叉樹的二叉鏈表樹的二叉鏈表結構結構AECBDF每個結點由數(shù)據(jù)域、左指針域和右指針域組成。每個結點由數(shù)據(jù)域、左指針域和右指針域組成。2022-5-1521鏈式存儲結構的描述：鏈式存儲結構的描述：Typedef struct Bi

14、TNode int data; Struct BiTNode *lchild, *rchild; BiTNode, * BiTree;lchildDatarchildlchildDatarchildlchildDatarchild2022-5-15223、將樹和森林轉換為二叉樹、將樹和森林轉換為二叉樹 由于二叉樹可以用二叉鏈表表示，為了使一般樹也能由于二叉樹可以用二叉鏈表表示，為了使一般樹也能用二叉鏈表表示，必須找出樹與二叉樹之間的關系。用二叉鏈表表示，必須找出樹與二叉樹之間的關系。 這樣，給定一棵樹，可以找到唯一的一棵二叉樹與之這樣，給定一棵樹，可以找到唯一的一棵二叉樹與之對應。對應。（1）

15、樹轉換為二叉樹）樹轉換為二叉樹方法：方法： 對每個孩子進行從左到右的排序；對每個孩子進行從左到右的排序； 在兄弟之間加一條連線；在兄弟之間加一條連線； 對每個結點，除了左孩子外，去除其與其余孩子對每個結點，除了左孩子外，去除其與其余孩子之間的聯(lián)系；之間的聯(lián)系； 以根結點為軸心，將整個樹順時針轉以根結點為軸心，將整個樹順時針轉45度。度。2022-5-1523 I A B C DE F G H(b) A B CD E G H FI(a)樹轉換為二叉樹樹轉換為二叉樹ABEFCDGHI(d)ABCDEFGHI(c)2022-5-1524 （2） 森林轉換為二叉樹森林轉換為二叉樹ADCBEFHIGJE

16、FADCBHIGJADCBEFHIGJADCBEFHIGJ方法：方法： 將各棵樹分別轉成二叉樹；將各棵樹分別轉成二叉樹； 把每棵樹的根結點用線連起來；把每棵樹的根結點用線連起來； 以第一棵樹的根結點作為二叉樹以第一棵樹的根結點作為二叉樹的根結點，按順時針方向旋轉。的根結點，按順時針方向旋轉。2022-5-15254、 二叉樹的遍歷二叉樹的遍歷 查找某個結點，或對二叉樹中全部結點進行某種處理，就需要遍查找某個結點，或對二叉樹中全部結點進行某種處理，就需要遍歷。歷。（1）遍歷定義及遍歷算法）遍歷定義及遍歷算法 遍歷是指按某條搜索路線尋訪樹中每個結點，且每個結點只被訪遍歷是指按某條搜索路線尋訪樹中每

17、個結點，且每個結點只被訪問一次。問一次。 按先左后右的原則，一般使用三種遍歷：按先左后右的原則，一般使用三種遍歷：先序遍歷先序遍歷(D L R): 訪問根結點，按先序遍歷左子樹，按先序遍歷右子樹。訪問根結點，按先序遍歷左子樹，按先序遍歷右子樹。中序遍歷中序遍歷(L D R): 按中序遍歷左子樹，訪問根結點，按中序遍歷右子樹。按中序遍歷左子樹，訪問根結點，按中序遍歷右子樹。后序遍歷后序遍歷(L R D): 按后序遍歷左子樹，按后序遍歷右子樹，訪問根結點。按后序遍歷左子樹，按后序遍歷右子樹，訪問根結點。 二叉樹為空時，執(zhí)行空操作，即空二叉樹已遍歷完。二叉樹為空時，執(zhí)行空操作，即空二叉樹已遍歷完。2

18、022-5-1526 （2）遍歷算法遍歷算法先序遍歷：先序遍歷：D L R中序遍歷：中序遍歷：L D R后序遍歷：后序遍歷：L R DADBCT1T2T3D L RAD L RD L RBDCD L R以先序遍歷以先序遍歷D L RD L R為例演示遍歷過程為例演示遍歷過程 ABDCBDAC DBCA2022-5-1527Void PreOderTraverse(BiTree T)if(T! =NULL) printf (T-data); PreOrderTraverse(T-lchild); PreOrderTraverser(T-rchild); /*先序遍歷先序遍歷*/主程序主程序Pre

19、( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回左是空返回pre(T R);T左是空返回左是空返回T右是空返回右是空返回T左是空返回左是空返回T右是空返回右是空返回pre(T R);2022-5-1528中序遍歷二叉樹的遞歸算法：中序遍歷二叉樹的遞歸算法： void inOrderTraverse(BiTree T) if(T!=NULL) inOrderTraverse(T-lch

20、ild); printf(T-data); inOrderTraverse(T-rchild); 后序遍歷二叉樹的遞歸算法：后序遍歷二叉樹的遞歸算法： void PostOrderTraverse(BiTree T) if(T!=NULL) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); printf(T-data); 2022-5-1529 （3）遍歷二叉樹的應用）遍歷二叉樹的應用 1) 建立一棵二叉樹建立一棵二叉樹 (在遍歷過程生成結點，建立二叉在遍歷過程生成結點，建立二叉樹的存儲結構，用鏈式存儲結構）樹的存儲結構，用鏈式

21、存儲結構）BiTree CreatBiTree() BiTree T; scanf(&ch); if(ch= = ) T=NULL; else T=(BiTNode )malloc(sizeof(BiTNode); T-data=ch; /*生成根結點生成根結點*/ T-lchild= CreatBiTree( ); /*構造左子樹構造左子樹*/ T-rchild= CreatBiTree(); /*構造右子樹構造右子樹*/ return (T) ;ADBCA B D CA B D C 按先序遍歷按先序遍歷2022-5-1530ch=ATTAcreat(T L)T= , Creat(T) 返回

22、creat(T R)Tch=D|=返回creat(T R)D=Tch=返回ch=DTTDcreat(T L)=|creat(T R)ch=CTTCcreat(T L)+ch=BTTBcreat(T L)Tch=BTCch=+返回creat(T R)TCch=+返回ATABABD|=ABDABDC+BAABDC2022-5-1531（2）統(tǒng)計二叉樹中葉子結點的個數(shù)）統(tǒng)計二叉樹中葉子結點的個數(shù) 方法：對二叉樹進行遍歷，判斷被訪問的結點是否葉方法：對二叉樹進行遍歷，判斷被訪問的結點是否葉子結點，若是葉子結點，則將計數(shù)器加子結點，若是葉子結點，則將計數(shù)器加1。實現(xiàn)算法：實現(xiàn)算法：int countle

23、af(BiTree) int n1,n2; if (T= =NULL) return(0); else if (T-lchild= =NULL) & (T-rchild= =NULL) return(1); else n1=countleaf (T-lchild); n2=countleaf (T-rchild); return( n1+n2); 2022-5-1532作業(yè)：作業(yè)：P77第第2925題題第第27題、第題、第29題題2022-5-1533 A C G D H I J M B E L K F作業(yè)作業(yè)20解解AK、L、F、G、M、I、J CE、FE、F、G、H、I、J42022-5-

24、1534ABCDEFKLGHIJM2022-5-1535 void change(NODE *T)NODE *m; if(T!=NULL) m=T-L T-L=T-R; T-R=m; change(T-L); change(T-R);typedef struct nodeint data；struct node *L，*R；NODE；ABCDACBDACBD21.試以二叉鏈表作為存儲結構，將二試以二叉鏈表作為存儲結構，將二叉樹中所有結點的左右子樹進行交換。叉樹中所有結點的左右子樹進行交換。2022-5-153623. n24. 12 i-125. CDBFGEA27. 82022-5-1537

25、第第2525題題: :先序遍歷中的第一個元素必為二叉樹的根結點。先序遍歷中的第一個元素必為二叉樹的根結點。中序遍歷中的根結點恰為左、右子樹的分界點。中序遍歷中的根結點恰為左、右子樹的分界點。先序遍歷先序遍歷:ABCDEFG :ABCDEFG 中序遍歷中序遍歷: :CBDAFEGCBDAFEGC D B F G E AC D B F G E A2022-5-1538int AA（R，e） P=R；int n=1； while（P-data!=e | p-next=NULL) p=p-next; n=n+1; if(p-next=NULL & P-data!=e) printf(“ERRORn”)

26、; return(n);關系運算符：關系運算符： = = = !=邏輯運算符：邏輯運算符： & | !錯在哪？錯在哪？2022-5-1539 閱讀程序并回答問題：（1） 程序執(zhí)行了什么功能？（2） 針對右面的圖，寫出程序的運行結果。 typedef struct BiTNode int data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree; int preprn(BiTtree T) if(T-lchild!=NULL)&（T-rchild!=NULL）) printf(T-data);preprn(T-lchild);preprn(T-rc

27、hild); else return OK;abdecgfhia b c g2022-5-154011月月20日上機作業(yè)：日上機作業(yè)：作業(yè)作業(yè)1： 用用C語言編寫遞歸和非遞歸語言編寫遞歸和非遞歸計算計算n!程序。程序。2022-5-1541遞歸算法遞歸算法 ：int F(int n) int m; if(n=0) m=1; else m=n*F(n-1); return (m);非遞歸算法：非遞歸算法：int F(int n) int f1=1,s=1; if(n=0) return 1; while(sdata data)-data data) q-data = pbq-data = pb-

28、data;-data;p pq qai-1a1aianPab2b1Pb2022-5-1547合并算法如下：合并算法如下：JD JD * * comlink(JD comlink(JD * *pa,JD pa,JD * *pbpb) ) JD JD * *p,p,* *q,q,* *pc;pc; pc=(JD pc=(JD* *)malloc(sizeof)malloc(sizeof(JD);(JD);pcpcp=pc;p=pc;While(pa!=NULL & pbWhile(pa!=NULL & pb!=NULL)!=NULL) q=(JDq=(JD* *)malloc(sizeof)mal

29、loc(sizeof(JD);(JD);if (pbif (pb-data data)-data data) q-data = pbq-data = pb-data;-data;p pq qai-1a1aianPab2b1Pbb12022-5-1548合并算法如下：合并算法如下：JD JD * * comlink(JD comlink(JD * *pa,JD pa,JD * *pbpb) ) JD JD * *p,p,* *q,q,* *pc;pc; pc=(JD pc=(JD* *)malloc(sizeof)malloc(sizeof(JD);(JD);pcpcp=pc;p=pc;Whil

30、e(pa!=NULL & pbWhile(pa!=NULL & pb!=NULL)!=NULL) q=(JDq=(JD* *)malloc(sizeof)malloc(sizeof(JD);(JD);if (pbif (pb-data data)-data data) q-data = pbq-data = pb-data;-data;p pq qb1pb=pbpb=pb-link;-link;ai-1a1aianPab2b1Pb2022-5-1549合并算法如下：合并算法如下：JD JD * * comlink(JD comlink(JD * *pa,JD pa,JD * *pbpb) )

31、JD JD * *p,p,* *q,q,* *pc;pc; pc=(JD pc=(JD* *)malloc(sizeof)malloc(sizeof(JD);(JD);pcpcp=pc;p=pc;While(pa!=NULL & pbWhile(pa!=NULL & pb!=NULL)!=NULL) q=(JDq=(JD* *)malloc(sizeof)malloc(sizeof(JD);(JD);if (pbif (pb-data data)-data data) q-data = pbq-data = pb-data;-data;p pq qb1pb=pbpb=pb-link;-link

32、;ai-1a1aianPab2b1Pb2022-5-1550pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p pq qai-1a1aianPab2b1Pba12022-5-1551pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;if (pa-data= =pbif (pa-data= =pb-data)-data)pb = pbpb = pb-link;-link;p pq qai-1a1aianPab2b1P

33、ba12022-5-1552pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p-link=q;p-link=q;if (pa-data= =pbif (pa-data= =pb-data)-data)pb = pbpb = pb-link;-link;p pq qai-1a1aianPab2b1Pba12022-5-1553pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p-link=q;p-link=q;if

34、(pa-data= =pbif (pa-data= =pb-data)-data)pb = pbpb = pb-link;-link;p pq qai-1a1aianPab2b1Pba1p=q;p=q; 2022-5-1554pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p-link=q;p-link=q;if (pa-data= =pbif (pa-data= =pb-data)-data)pb = pbpb = pb-link;-link;p pq qai-1a1aianPab2b1Pba1p=q

35、;p=q; 2022-5-1555pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p-link=q;p-link=q;if (pa-data= =pbif (pa-data= =pb-data)-data)pb = pbpb = pb-link;-link;p pq qai-1a1aianPab2b1Pba1p=q;p=q; 2022-5-1556pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p-link=q;

36、p-link=q;if (pa-data= =pbif (pa-data= =pb-data)-data)pb = pbpb = pb-link;-link;p pq qai-1a1aianPab2b1Pba1p=q;p=q; a22022-5-1557pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p-link=q;p-link=q;if (pa-data= =pbif (pa-data= =pb-data)-data)pb = pbpb = pb-link;-link;p pq qai-1a1aia

37、nPab2b1Pba1p=q;p=q; a22022-5-1558pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p-link=q;p-link=q;if (pa-data= =pbif (pa-data= =pb-data)-data)pb = pbpb = pb-link;-link;p pq qai-1a1aianPab2b1Pba1p=q;p=q; a22022-5-1559pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa

38、=pa-link;p-link=q;p-link=q;if (pa-data= =pbif (pa-data= =pb-data)-data)pb = pbpb = pb-link;-link;p pq qai-1a1aianPab2b1Pba1p=q;p=q; a22022-5-1560pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p-link=q;p-link=q;if (pa-data= =pbif (pa-data= =pb-data)-data)pb = pbpb = pb-link;-li

39、nk;p pq qai-1a1aianPab2b1Pba1p=q;p=q; a22022-5-1561pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p-link=q;p-link=q;if (pa-data= =pbif (pa-data= =pb-data)-data)pb = pbpb = pb-link;-link;p pq qai-1a1aianPab2b1Pba1p=q;p=q; a2b12022-5-1562pcpcElse q-data = pa-data;Else q-data = p

40、a-data;pa=pa-link;pa=pa-link;p-link=q;p-link=q;if (pa-data= =pbif (pa-data= =pb-data)-data)pb = pbpb = pb-link;-link;p pq qai-1a1aianPab2b1Pba1p=q;p=q; a2b12022-5-1563pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p-link=q;p-link=q;if (pa-data= =pbif (pa-data= =pb-data)-data)p

41、b = pbpb = pb-link;-link;p pq qai-1a1aianPab2b1Pba1p=q;p=q; a2b12022-5-1564While (pa!=nNULLWhile (pa!=nNULL)/)/* *如果如果papa鏈表還未到表尾，復制剩余部分鏈表還未到表尾，復制剩余部分* */ /q=(JD q=(JD * *)malloc(sizeof)malloc(sizeof(JD);(JD); q-data = pa-data; q-data = pa-data; pa=pa-link; pa=pa-link; p-link=q; p-link=q; p=q; p=q;

42、2022-5-1565While (pb!=nNULLWhile (pb!=nNULL)/)/* *如果如果pbpb鏈表還未到表尾，復制剩余部分鏈表還未到表尾，復制剩余部分* */ /q=(JD q=(JD * *)malloc(sizeof)malloc(sizeof(JD);(JD); q-data = pb q-data = pb-data;-data; pb=pb pb=pb-link;-link; p-link=q; p-link=q; p=q; p=q; 2022-5-1566pcpcp-link=NULL;p-link=NULL;p pq qa1a2b12022-5-1567pc

43、pcp-link=NULL;p-link=NULL;p=pc;p=pc;p pq qa1a2b12022-5-1568pcpcp-link=NULL;p-link=NULL;p=pc;p=pc;pc=p-link;pc=p-link;p pq qa1a2b12022-5-1569pcpcp-link=NULL;p-link=NULL;p=pc;p=pc;pc=p-link;pc=p-link;free(p);free(p);p pq qa1a2b12022-5-1570pcpcp-link=NULL;p-link=NULL;p=pc;p=pc;return(pc);return(pc); pc

44、=p-link;pc=p-link;free(p);free(p);q qa1a2b12022-5-1571合并算法程序如下：合并算法程序如下：JD JD * * comlink(JD comlink(JD * *pa,JD pa,JD * *pbpb) ) JD JD * *p p，* *q q，* *pcpc； pc=(JDpc=(JD* *)malloc(sizeof)malloc(sizeof(JD)(JD)；p=pcp=pc；While(pa!=NULL & pbWhile(pa!=NULL & pb!=NULL)!=NULL) q=(JDq=(JD* *)malloc(sizeof

45、)malloc(sizeof(JD)(JD)；if (pbif (pb-data data)-data data) q-data = pb-dataq-data = pb-data； pb = pbpb = pb-link-link； Else q-data = paElse q-data = pa-data-data；pa=pa-linkpa=pa-link；p-link=qp-link=q；if (pa-data= =pb-data) pb = pbif (pa-data= =pb-data) pb = pb-link-link； p=qp=q； 2022-5-1572While (pa!

46、=nNULLWhile (pa!=nNULL)/)/* *如果如果papa鏈表還未到表尾，復制剩余部分鏈表還未到表尾，復制剩余部分* */ /q=(JD q=(JD * *)malloc(sizeof)malloc(sizeof(JD);(JD); q-data = pa-data; q-data = pa-data; pa=pa-link; pa=pa-link; p-link=q; p-link=q; p=q; p=q; 2022-5-1573While (pb!=nNULLWhile (pb!=nNULL)/)/* *如果如果pbpb鏈表還未到表尾，復制剩余部分鏈表還未到表尾，復制剩余部

47、分* */ /q=(JD q=(JD * *)malloc(sizeof)malloc(sizeof(JD);(JD); q-data = pb q-data = pb-data;-data; pb=pb pb=pb-link;-link; p-link=q; p-link=q; p=q; p=q; 2022-5-1574p-link=NULL;p-link=NULL;p=pc;p=pc;return(pc);return(pc); pc=p-link;pc=p-link;free(p);free(p);2022-5-1575下面介紹鏈表的創(chuàng)建。下面介紹鏈表的創(chuàng)建。2022-5-1576Lin

48、klist creatLinklist creat()()linklist linklist head,p1,p2;head,p1,p2;n=0n=0；p1=p2=(struct lnodep1=p2=(struct lnode* *)malloc)malloc(LEN)(LEN)；scanfscanf(“%d”,&p1-data)(“%d”,&p1-data)；head-next=NULL;head-next=NULL;while(p1-data!0)while(p1-data!0) n=n+1 n=n+1； if(n=1) head-next=p1if(n=1) head-next=p1；

49、 else p2-next=p1else p2-next=p1； p2=p1p2=p1；p1=(struct lnodep1=(struct lnode* *)malloc)malloc(LEN)(LEN)； scanfscanf(%d”,&p1-data)(%d”,&p1-data)；p2-next=NULLp2-next=NULL； return(head)return(head)； 創(chuàng)立具有頭指針的鏈表創(chuàng)立具有頭指針的鏈表2022-5-1577Linklist creatLinklist creat()() linklist linklist head,p1,p2head,p1,p2;

50、;n=0n=0；p1=p2=(struct lnodep1=p2=(struct lnode* *)malloc)malloc(LEN)(LEN)；scanfscanf(“%d”,&p1-data)(“%d”,&p1-data)；head-next=NULL;head-next=NULL;while(p1-data!0)while(p1-data!0) n=n+1 n=n+1； if(n=1) head-next=p1if(n=1) head-next=p1； else p2-next=p1else p2-next=p1； p2=p1p2=p1；p1=(struct lnodep1=(stru

51、ct lnode* *)malloc)malloc(LEN)(LEN)； scanfscanf(%d”,&p1-data)(%d”,&p1-data)；p2-next=NULLp2-next=NULL； return(head)return(head)； HeadHeadp1p1p2p22022-5-1578Linklist creatLinklist creat()() linklist linklist head,p1,p2head,p1,p2; ;n=0n=0；p1=p2=(struct lnodep1=p2=(struct lnode* *)malloc)malloc(LEN)(LEN

52、)；scanfscanf(“%d”,&p1-data)(“%d”,&p1-data)；head-next=NULL;head-next=NULL;while(p1-data!0)while(p1-data!0) n=n+1 n=n+1； if(n=1) head-next=p1if(n=1) head-next=p1； else p2-next=p1else p2-next=p1； p2=p1p2=p1；p1=(struct lnodep1=(struct lnode* *)malloc)malloc(LEN)(LEN)； scanfscanf(%d”,&p1-data)(%d”,&p1-da

53、ta)；p2-next=NULLp2-next=NULL； return(head)return(head)； HeadHeadp1p1p2p2n=0n=02022-5-1579Linklist creatLinklist creat()() linklist linklist head,p1,p2head,p1,p2; ;n=0n=0；p1=p2=(struct lnodep1=p2=(struct lnode* *)malloc)malloc(LEN)(LEN)；scanfscanf(“%d”,&p1-data)(“%d”,&p1-data)；head-next=NULL;head-nex

54、t=NULL;while(p1-data!0)while(p1-data!0) n=n+1 n=n+1； if(n=1) head-next=p1if(n=1) head-next=p1； else p2-next=p1else p2-next=p1； p2=p1p2=p1；p1=(struct lnodep1=(struct lnode* *)malloc)malloc(LEN)(LEN)； scanfscanf(%d”,&p1-data)(%d”,&p1-data)；p2-next=NULLp2-next=NULL； return(head)return(head)； HeadHeadp1

55、p1p2p2n=0n=02022-5-1580Linklist creatLinklist creat()() linklist linklist head,p1,p2head,p1,p2; ;n=0n=0；p1=p2=(struct lnodep1=p2=(struct lnode* *)malloc)malloc(LEN)(LEN)；scanfscanf(“%d”,&p1-data)(“%d”,&p1-data)；head-next=NULL;head-next=NULL;while(p1-data!0)while(p1-data!0) n=n+1 n=n+1； if(n=1) head-

56、next=p1if(n=1) head-next=p1； else p2-next=p1else p2-next=p1； p2=p1p2=p1；p1=(struct lnodep1=(struct lnode* *)malloc)malloc(LEN)(LEN)； scanfscanf(%d”,&p1-data)(%d”,&p1-data)；p2-next=NULLp2-next=NULL； return(head)return(head)； HeadHeadp1p1p2p2n=0n=015152022-5-1581Linklist creatLinklist creat()() linkli

57、st linklist head,p1,p2head,p1,p2; ;n=0n=0；p1=p2=(struct lnodep1=p2=(struct lnode* *)malloc)malloc(LEN)(LEN)；scanfscanf(“%d”,&p1-data)(“%d”,&p1-data)；head-next=NULLhead-next=NULL; ;while(p1-data!0)while(p1-data!0) n=n+1 n=n+1； if(n=1) head-next=p1if(n=1) head-next=p1； else p2-next=p1else p2-next=p1；

58、p2=p1p2=p1；p1=(struct lnodep1=(struct lnode* *)malloc)malloc(LEN)(LEN)； scanfscanf(%d”,&p1-data)(%d”,&p1-data)；p2-next=NULLp2-next=NULL； return(head)return(head)； HeadHeadp1p1p2p215n=0n=02022-5-1582Linklist creatLinklist creat()() linklist linklist head,p1,p2head,p1,p2; ;n=0n=0；p1=p2=(struct lnodep1

59、=p2=(struct lnode* *)malloc)malloc(LEN)(LEN)；scanfscanf(“%d”,&p1-data)(“%d”,&p1-data)；head-next=NULLhead-next=NULL; ;while(p1-data!0)while(p1-data!0) n=n+1n=n+1； if(n=1) head-next=p1if(n=1) head-next=p1； else p2-next=p1else p2-next=p1； p2=p1p2=p1；p1=(struct lnodep1=(struct lnode* *)malloc)malloc(LEN

60、)(LEN)； scanfscanf(%d”,&p1-data)(%d”,&p1-data)；p2-next=NULLp2-next=NULL； return(head)return(head)； HeadHeadp1p1p2p215n=1n=12022-5-1583Linklist creatLinklist creat()() linklist linklist head,p1,p2head,p1,p2; ;n=0n=0；p1=p2=(struct lnodep1=p2=(struct lnode* *)malloc)malloc(LEN)(LEN)；scanfscanf(“%d”,&p1