數(shù)據(jù)機構(gòu)棧和隊列

1、第2章 線性表本章主要內(nèi)容2.1 線性表的定義和基本操作n線性表的定義n線性表是由n（n0）個類型相同的數(shù)據(jù)元素組成的有限序列。nL=( a1, a2,.,ai-1,ai,ai+1,.,an)；其中：L為表名，習慣用大寫書寫；ai為該線性表的數(shù)據(jù)元素，習慣用小寫書寫；n線性表中數(shù)據(jù)元素的個數(shù)被稱為線性表的長度，當n=0時，稱為空線性表。 線性表特點n特點n除第一個和最后一個元素外，其他元素都存在唯一的前驅(qū)、后繼關(guān)系n舉例 n La=（34，89，765，12，90，-34，22） 數(shù)據(jù)元素類型為int。n Ls=(Hello,World, China, Welcome) 數(shù)據(jù)元素類型為stri

2、ng。 n舉例n Lb=(book1,book2,.,book100) 數(shù)據(jù)元素類型為下列所示的結(jié)構(gòu)類型： struct bookinfo int No; /圖書編號 char *name; /圖書名稱 char *auther; /作者名稱 .; 在現(xiàn)實中，這種類型的數(shù)據(jù)結(jié)構(gòu)很多很多，如學生檔案學籍系統(tǒng)、圖書管理系統(tǒng)、倉庫管理系統(tǒng)、設(shè)備管理系統(tǒng)等線性表的基本操作n1. 初始化線性表L InitList(L) n2. 銷毀線性表L DestoryList(L) n3. 清空線性表L ClearList(L) n4. 求線性表L的長度 ListLength(L)n5. 判斷線性表L是否為空 Is

3、Empty(L) n6. 獲取線性表L中的某個數(shù)據(jù)元素 內(nèi)容GetElem(L,i,e) n7. 檢索值為e的數(shù)據(jù)元素 LocateELem(L,e)了解，算法了解，算法有待學習有待學習n8. 返回線性表L中e的直接前驅(qū)元素 PriorElem(L,e) n9. 返回線性表L中e的直接后繼 元素NextElem(L,e) n10.在線性表L中插入一個數(shù)據(jù) 元素ListInsert(L,i,e)n11. 刪除線性表L中第i個數(shù)據(jù) 元素ListDelete(L,i,e) 注意：這些操作都是定義在邏輯層面上注意：這些操作都是定義在邏輯層面上理解，算法理解，算法有待學習有待學習返回返回線性表的基本操作

4、2.2 線性表的順序存儲結(jié)構(gòu)存儲地址內(nèi)存單元.da1d+La2d+2La3.d+(i-1)Lai.d+(n-1)Lan.n順序存儲結(jié)構(gòu)n指用一組連續(xù)的存儲單元依次存儲線性表中的每個數(shù)據(jù)元素。如右圖所示：說明：說明：L為每個數(shù)據(jù)元素所占據(jù)的存儲單元數(shù)目。為每個數(shù)據(jù)元素所占據(jù)的存儲單元數(shù)目。順序表元素在內(nèi)存的存儲地址 n相鄰兩個數(shù)據(jù)元素的存儲位置計算公式 LOC(ai+1)=LOC(ai)+Ln線性表中任意一個數(shù)據(jù)元素的存儲位置的計算 公式為：LOC(ai+1)=LOC(a1)+(i-1)*L 順序存儲結(jié)構(gòu)的特點n邏輯與物理一致： 邏輯上相鄰，物理上也相鄰利用數(shù)據(jù)元素的存儲位置表示線性表中相鄰數(shù)據(jù)

5、元素之間的前后關(guān)系n隨機存?。?可以利用上述給出的數(shù)學公式，快速地計算出任何一個數(shù)據(jù)元素的存儲地址順序存儲結(jié)構(gòu)的類型定義n在C語言中，實現(xiàn)線性表的順序存儲結(jié)構(gòu)的類型定義如下 #define MAXSIZE 100 typedef struct node DataType dataMAXSIZE； int length； SeqList, *PseqList；n定義一個順序表：SeqList L；初始化一個線性表nPSeqList是指向SeqList 類型變量的指針類型；n定義：PSeqlist PL ； n則如下初始化PL=( PSeqList )malloc(sizeof(SeqList)n

6、 或者 PL=&L建立的內(nèi)存存儲映象如下頁所示線性表的存儲圖 典型操作的算法實現(xiàn)1. 初始化線性表LPSeqList Init_SeqList(void ) /*創(chuàng)建一順序表，入口參數(shù)無，返回一個指向順序表的指針，指針值為零表示分配空間失敗*/ PSeqList PL; PL=( PSeqList )malloc(sizeof(SeqList); if (PL) /*若SL=0表示分配失敗*/ PL - length =0; return (PL); 典型操作的算法實現(xiàn)2.銷毀線性表void Destroy_SeqList(PSeqList *PL) /*銷毀順序表，入口參數(shù)：為要銷毀

7、的順序表指針地址，無返回值*/ if (*PL) free (*PL) ; *PL=NULL; return ; 典型操作的算法實現(xiàn)3. 求順序表的長度n定義：求順序表中元素的個數(shù)。首先判斷順序表是否存在，若存在返回length ，若不存在返回-1。算法如下：nint Length_SeqList (PSeqlist PL)n /*求順序表的長度，入口參數(shù)：為順序表指針，返回表長，-1表示表不存在*/n if (PL)n return (PL- length) ;n return (-1);n 典型操作的算法實現(xiàn)4. 順序表的檢索操作（值查找）n定義：在順序表表存在的情況下，查找值為x的數(shù)據(jù)元

8、素，成功:返回值為x的那個元素的序號；未找到返回0。n方法:從第一個元素e1 起依次和x比較，直到找到一個與x相等的數(shù)據(jù)元素，返回它在順序表中的data數(shù)組的下標1（第一個元素存放data0）；或者查遍整個表都沒有找到與x相等的元素，返回0。順序表查詢算法int Location_SeqList (PSeqList PL, DataType x) /*順序表檢索，入口參數(shù)：為順序表指針，檢索元素，順序表檢索，入口參數(shù)：為順序表指針，檢索元素， 返回元素位置，返回元素位置，-1表示表不存在，表示表不存在，0表示查找失敗表示查找失敗*/ int i=0; if (!PL) printf(表不存在表

9、不存在); return(-1); /*表不存在，不能檢索表不存在，不能檢索*/ while (i length & PL-datai!= x) i+; if (i=PL- length) return 0; else return (i +1); 典型操作的算法實現(xiàn)5. 順序表的插入運算n定義： 順序表的插入是指在表的第i個位置上插入一個值為x的新元素，即在第i元素之前插入 x，使原表長為n的表：(e1，e2，. ，ei-1，ei，ei+1，. ，en) 變?yōu)楸黹L為 n+1 表：(e1，e2，.，ei-1，x，ei，ei+1，.，en) 。其中i：1in+1。 n(1)檢查待插入的表

10、是否存在，若不存在退出；n(2)判斷順序表是否滿(即表長length是否大于等于MAXSIZE)？若滿，退出；否則執(zhí)行(3)；n(3)檢查插入位置的合法性( i 滿足1=i length = MAXSIZE) printf(“表溢出表溢出”); return(-1); /*表空間已滿，不能插入表空間已滿，不能插入*/ if (i PL- length +1) /*檢查插入位置的合法性檢查插入位置的合法性*/ printf(“插入位置不合法插入位置不合法”); return(0); for(j= PL - length -1; j=i-1; j-) PL -dataj+1= PL -dataj;

11、 /* 移動元素移動元素 */ PL-datai-1=x; /*新元素插入新元素插入*/ PL- length +; /*表長加表長加 1*/ return (1); /*插入成功，返回插入成功，返回*/ n設(shè)插入的位置為i ，則把ei到en元素向后移動一個位置共需要移動 ni1個元素。n設(shè)在第i個位置上作插入的概率為Pi，n由于 1 i n+1，共有 n1個位置可以插入，即在情況下pi=1/ (n+1)，則：n算法的時間復雜度為(n)11111E(1 )(1 )12nniniiinp n in in 順序表插入運算的效率分析刪除的存儲示意如下頁所示典型操作的算法實現(xiàn)6. 順序表的刪除運算是指

12、將表中第 i 個元素從線性表中去掉 刪除前：表長n (e1，e2，. ，ei-1，ei，ei+1，.，en) 刪除后：表長 n -1 (e1，e2，. ，ei-1， ei+1，. ，en) 其中i：1 i n。刪除前刪除后下頁給出刪除的算法刪除的操作步驟:n（1）檢查表是否存在，若不存在退出n（2）檢查刪除位置的合法性（ i 是否為1ilength）若不滿足，退出n（3）將ei+1en 順序向上移動一位，ei+1占據(jù)ei 位置，（注意數(shù)據(jù)的移動方向）n（4）修改表長下頁給出算法C語言描述順序表刪除算法int Delete_SeqList(PSeqList PL，int i) /*順序表刪除，入

13、口參數(shù)：順序表指針，刪除元素位置，順序表刪除，入口參數(shù)：順序表指針，刪除元素位置，返回標志返回標志1表示成功，表示成功，0表示刪除位置不合法，表示刪除位置不合法，-1表示表不存在表示表不存在*/ int j; if (!PL) printf(表不存在表不存在); return(-1); /*表不存在，不能刪除元素表不存在，不能刪除元素*/ if(i PL - length) /*檢查刪除位置的合法性檢查刪除位置的合法性*/ printf (刪除位置不合法刪除位置不合法); return(0); for(j=i; j length; j+) PL -dataj-1= PL-dataj; /*向上

14、移動向上移動*/ PL- length -; return (1); /*刪除成功刪除成功*/ 刪除算法的效率分析n在進行刪除操作時，若假定刪除每個元素的可能性均等，則平均移動元素的個數(shù)為： n1idl21ni)(nn1E結(jié)論n順序存儲結(jié)構(gòu)表示的線性表，在做插入或刪除操作時，平均需要移動大約一半的數(shù)據(jù)元素n當線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對其做插入或刪除操作時，消耗的時間代價較大返回返回2.3 線性表的鏈式存儲結(jié)構(gòu)n線性表順序存儲結(jié)構(gòu)的優(yōu)點：n邏輯上相鄰、物理上相鄰，結(jié)構(gòu)簡單n可以根據(jù)元素的下標存取，速度便捷 n線性表順序存儲結(jié)構(gòu)的缺點：n在做插入或刪除元素的操作時，會產(chǎn)生大量的數(shù)據(jù)元素移

15、動n對于長度變化較大的線性表，要一次性地分配足夠的存儲空間，但這些空間常常又得不到充分的利用n線性表的容量難以擴充為此我們引入線性表的鏈式存儲線性表的鏈式存儲n邏輯上相鄰的元素之間的物理位置是通過指針的指向來實現(xiàn)的，這種指向一般是通過的動態(tài)的地址指針來實現(xiàn)的（也可以通過靜態(tài)的偽地址指針來實現(xiàn)）n每個數(shù)據(jù)元素不僅要表示它的具體內(nèi)容，還要附加一個表示它的直接后繼元素存儲位置的信息下頁給出鏈式存儲的內(nèi)存示意圖：下頁給出鏈式存儲的內(nèi)存示意圖：headd cba存儲地址內(nèi)容直接后繼存儲地址100b120.120c160.144a100.160dNULL.首元素位置線性表鏈式存儲結(jié)構(gòu)示意圖線性表鏈式存儲結(jié)

16、構(gòu)示意圖鏈式存儲n表示每個數(shù)據(jù)元素的兩部分信息組合在一起被稱為結(jié)點, 其中表示數(shù)據(jù)元素內(nèi)容的部分被稱為數(shù)據(jù)域data；表示直接后繼元素存儲地址的部分被稱為指針或指針域next n單鏈表中最后一個結(jié)點沒有直接后繼結(jié)點，它的指針域放入一個特殊的值NULLn為了簡化對鏈表的操作，人們經(jīng)常在鏈表的第一個結(jié)點之前附加一個結(jié)點，并稱為頭結(jié)點headd cba帶頭結(jié)點的單鏈表結(jié)構(gòu)示意圖帶頭結(jié)點的單鏈表結(jié)構(gòu)示意圖n鏈式存儲結(jié)構(gòu)的特點n線性表中的數(shù)據(jù)元素在存儲單元中的存放順序與邏輯順序不一定一致n通過頭指針進入鏈表，通過結(jié)點的指針域訪問后繼結(jié)點，尋找第一個結(jié)點和尋找最后一個結(jié)點所花費的時間不等，存取方式被為順序

17、存取方式對比順序存儲為對比順序存儲為隨即存取方式隨即存取方式鏈式存儲鏈式存儲的幾種形式n單鏈表n循環(huán)鏈表n雙向鏈表n靜態(tài)鏈表 首先介紹單鏈表首先介紹單鏈表鏈表的每個元素構(gòu)成一個結(jié)點，定義如下：Typedef struct node DataType data; /*每個元素數(shù)據(jù)信息*/ struct node *next; /*存放后繼元素的地址*/ LNode，*LinkList；定義頭指針變量：LinkList H； 單鏈表的定義單鏈表的邏輯結(jié)構(gòu)示意圖單鏈表的幾種形態(tài)單鏈表的基本操作n1. 創(chuàng)建空單鏈表n鏈表是一種動態(tài)管理的存儲結(jié)構(gòu)，鏈表中的每個結(jié)點占用的存儲空間是運行時動態(tài)分配的n創(chuàng)建空

18、單鏈表就是建立一個帶頭結(jié)點的空表n算法主要是為單鏈表申請頭結(jié)點下頁給出相應(yīng)的C語言描述LinkList Creat_LinkList(void ) /*創(chuàng)建空單鏈表，入口參數(shù)：無；返回值：單鏈表的頭指針，0代表創(chuàng)建失敗，非0表成功*/ LinkList H； H=(LinkList )malloc(sizeof(LNode); if (H) /*確認創(chuàng)建頭結(jié)點創(chuàng)建是否成功，若成功，修改單鏈表頭結(jié)點的指針域為0表空表*/ H-next=NULL; return H; 創(chuàng)建單鏈表算法n2. 銷毀鏈表Ln單鏈表不需要使用時，必須要銷毀，以釋放空間n單鏈表的銷毀操作是創(chuàng)建操作的逆運算n通過頭指針逐個釋

19、放每個數(shù)據(jù)節(jié)點（如果數(shù)據(jù)節(jié)點存在的話，包括釋放頭節(jié)點）下頁給出相應(yīng)的C語言描述銷毀鏈表銷毀單鏈表算法void Destroy_LinkList(LinkList *H) /*入口參數(shù)：單鏈表頭指針的地址，出口參數(shù)：無*/ LinkList p,q; p=*H; while ( p!=NULL) /*釋放單鏈表的所有結(jié)點*/ q=p; p=p-next; free(q); /*while */ *H=NULL; /*將頭指針變?yōu)榱惚硎締捂湵聿淮嬖?/主程序中的調(diào)用方式 main( ) LinkList H; H =Creat_LinkList(); Destroy_LinkList(&H

20、);n3. 求單鏈表表長n單鏈表采用鏈接的存儲方式并且沒有顯示表長的存儲信息，求單鏈表的表長須將單鏈表遍歷一遍int Length_LinkList (LinkList H) /* 求單鏈表表長，入口參數(shù)：單鏈表頭指針，出口參數(shù)：表長，-1表示 單鏈表不存在。*/ LinkList p=H; /* p指向頭結(jié)點*/ int count= -1; /*H帶頭結(jié)點所以從1開始*/ while ( p) /* p所指的是第 count + 1 個結(jié)點*/ p=p-next; count+; /*while */ return (count); 算法的時間復雜度為算法的時間復雜度為O(n),其中其中n

21、為單鏈表為單鏈表的結(jié)點數(shù)的結(jié)點數(shù) 求鏈表長度算法n4. 查找操作n按序號查找n按指定的值查找n（1）按序號查找n從單鏈表的第一個元素結(jié)點起， 判斷當前結(jié)點是 否是第i個，若是，則返回該結(jié)點的指針，否則繼 續(xù)下一個結(jié)點的查找，直到表結(jié)束為止。 若沒有 第個結(jié)點則返回空。如果i=0返回頭指針。 下頁給出相應(yīng)的C語言描述鏈表查找序號查找算法 LinkList Locate_LinkList( LinkList H, int i) LinkList p; int j; p=H; j=0; while (p & jnext; j+; /*while*/ if ( j != i | !p) pri

22、ntf(參數(shù)參數(shù) i 錯或單鏈表不存在錯或單鏈表不存在); return (NULL); /*第第i個結(jié)點不存在個結(jié)點不存在*/ return （p）; n(2) 在單鏈表中按指定的值查找元素 n單鏈表的按值查找是在線性表存在的情況下， 查找值為的數(shù)據(jù)元素n若成功，返回首次出現(xiàn)的值為的那個元素 所在結(jié)點的指針n否則，未找到值為的數(shù)據(jù)元素，返回NULL 表示查找失敗下頁給出相應(yīng)的C語言描述鏈表查找值查找算法LinkList Locate_LinkList( LinkList H, DataType x)/*在單鏈表中查找值為在單鏈表中查找值為x的結(jié)點，入口參數(shù)：單鏈表指針，檢的結(jié)點，入口參數(shù)：單

23、鏈表指針，檢索元素索元素,出口參數(shù)：找到后返回其指針，否則返回出口參數(shù)：找到后返回其指針，否則返回NULL*/ LinkList p=H-next; while ( p & p-data != x) p=p-next; return (p); 效率分析：兩種算法的時間復雜度均為效率分析：兩種算法的時間復雜度均為O(n)n5.單鏈表的插入運算n在單鏈表的第i個位置前插入一個值為 x 的新結(jié)點n設(shè)指針為 p指向第i-1結(jié)點，q指向待插入的值為x的新結(jié)點n 插入操作如下圖所示鏈表插入單鏈表插入算法int Insert_LinkList( LinkList H, int i, DataType

24、 x) /*返回參數(shù)：成功標志，返回參數(shù)：成功標志，0不成功，不成功，1成功成功*/ LinkList p, q; p= Locate_LinkList( H, i-1); /*找第找第i-1個結(jié)點地址個結(jié)點地址*/ if (!p) printf(i有誤有誤); return (0); q=(LinkList) malloc(sizeof(LNode); if (!q) printf(”申請空間失敗申請空間失敗”); return (0); /*申請空間失敗，不能插入申請空間失敗，不能插入*/ q-data=x; q-next=p-next; /*新結(jié)點插入在第新結(jié)點插入在第i-1個結(jié)點的后面

25、個結(jié)點的后面*/ p-next=q; return 1; /*插入成功，則返回插入成功，則返回*/ 問題：該算法的時間效率是多少？問題：該算法的時間效率是多少？n6. 刪除 n刪除單鏈表的第 i 個結(jié)點， 通過將第 i-1 個元素結(jié) 點的指針域指向第 i+1 個元素結(jié)點。n設(shè)單鏈表第 i-1 個元素結(jié)點指針為p，要刪除第 i 個 元素結(jié)點（指針為q），操作如下圖所示:p-next=q-next; free(q);下頁給出相應(yīng)的C語言描述鏈表刪除單鏈表刪除算法int Del_LinkList(LinkList H，int i) /*刪除單鏈表刪除單鏈表H上的第上的第i個結(jié)點個結(jié)點;返回參數(shù)：返回

26、參數(shù)：0不成功，不成功，1成功成功*/ LinkList p, q; if (H=null | H-next=null) printf(空表不能刪除空表不能刪除); return (0); p= Locate_LinkList( H, i-1); /*找第找第i-1個結(jié)點地址，見算法個結(jié)點地址，見算法2.10*/ if (p=null | p-next=null ) printf(參數(shù)參數(shù) i 錯錯); return (0); /*第第i個結(jié)點不存在個結(jié)點不存在*/ q=p-next; /*q指向第指向第i個結(jié)點個結(jié)點*/ p-next=q-next; /*從鏈表中刪除從鏈表中刪除*/ fre

27、e(q); /*釋放釋放*s */ return (1); 和插入算法一樣，時間消耗在查找第和插入算法一樣，時間消耗在查找第i-1個元素結(jié)點上個元素結(jié)點上,時間復雜度為時間復雜度為O(n) 循環(huán)鏈表循環(huán)鏈表為循環(huán)鏈表為空的情形空的情形特點：特點： 1.可以通過鏈表中任意節(jié)點遍歷整個鏈表 2.可以通過尾指針訪問到頭節(jié)點 3.循環(huán)鏈表的操作基本上和單鏈表相同 請自行閱讀教材上兩個循環(huán)鏈表合并的例子雙向鏈表如何定義雙向鏈表的節(jié)點，請看下頁雙向鏈表的節(jié)點定義typedef struct node DataType data; struct node *prior, *next;DuNode,*DLin

28、kList;在此定義基礎(chǔ)之上，雙向鏈表的插入、刪除運算是如何實現(xiàn)的呢？雙向鏈表的節(jié)點插入n設(shè)p指向雙向鏈表中某結(jié)點，s指向待插入的值為x的新結(jié)點，將*s插入到*p的前面，n步驟如下：s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;雙向鏈表的節(jié)點刪除n設(shè)p指向雙向鏈表中某結(jié)點，刪除*p。n操作示意圖如圖2-17所示。n操作步驟如下：p-prior-next=p-next;p-next-prior=p-prior; free(p) 1、2的順序可以調(diào)換 靜態(tài)鏈表n是一種以數(shù)組模擬的鏈表形式，在后面的完全二叉樹以及堆排序中會有應(yīng)用n其具體實現(xiàn)是以數(shù)

29、組元素的值來記錄邏輯上相鄰的元素的在數(shù)組中的下標其類型定義如下頁所示靜態(tài)鏈表的類型定義typedef struct DataType data; /*元素*/ int next；/*相對指針*/ SNode; /*結(jié)點類型*/再定義一個靜態(tài)鏈表#define MAXSIZE 100 /*鏈表可能的最大長度*/ typedef struct SNode spMAXSIZE; int SL; /*靜態(tài)鏈表頭指針*/ StList, *PStList;靜態(tài)鏈表的實例返回返回 2.4 線性表的應(yīng)用舉例n順序表逆置n單鏈表逆置n順序表合并n約瑟夫問題（基于順序表的實現(xiàn)和單鏈表的實現(xiàn)）順序表逆置n有一線性

30、表的順序表 (a1，a2， ，an) ，設(shè)計一算法將該線性表逆置成逆線性表(an，an-1， ，a1)，要求用最少的輔助空間a1a2a3ananan-1an-2a1順序表逆置void Reverse_SeqList (PSeqList PL) int i; DataType x; for (i=1; i length /2;i+) x = PL-datai -1; /*完成元素ai與an - i+1交換*/ PL-datai -1=PL-dataPL -length i ; PL-dataPL -length i =x； /* for */ 循環(huán)次數(shù)為 n/2 次時間復雜度為(n) 單鏈表逆置

31、n有一線性表的單鏈表表示 (a1，a2， ，an) ，設(shè)計一算法將該單鏈表逆置成逆線性表(an，an-1， ，a1)。 逆置為逆置的思想n算法思路：n 首先將單鏈表拆開成一個空表H和一個不帶頭結(jié)點的單鏈表n將不帶頭結(jié)點的單鏈表從第一個結(jié)點開始依次取出每個結(jié)點，將其插入到H單鏈表的第一個位置逆置算法void reverse_LinkList (Linklist H) LinkList p,q; p=H-next; /*p指向第一個數(shù)據(jù)結(jié)點*/ H-next=NULL; /*將原鏈表置為空表H*/ while (p) q=p; p=p-next; q-next=H-next; /*將當前結(jié)點插到頭

32、結(jié)點的后面*/ H-next=q; /*while*/可以畫圖演示順序表合并n 有順序表A和B，其元素值均按從小到大的 升序排列，要求將它們合并成一個順序 表C，且C的元素也是從小到大的升序排列n算法思想： 依次掃描A和B的元素，比較線性表A和B當前元素的值，將較小值的元素賦給C，如此直到一個線性表掃描完畢，然后將未完的那個順序表中余下部分賦給C即可 下頁給出算法的C語言描述注意：線性表C的容量要大于線性表A和B長度之和 參考順序表的定義合并算法A+B=Cint merge_SeqList (PSeqList A, PSeqList B, PSeqList *C) /*入口參數(shù)：指向三個順序表

33、的指針，返回值：0表示失敗，1表示成功*/ int i,j,k; i=0;j=0;k=0; *C=Init_SeqList(); /* 建立新表并初始化 */ if(!*C) printf(“C表不存在”); return(0)； if (A-length+B-length=MAXSIZE) printf(“C表空間不足”); return(0)； while ( ilength & jlength ) if (A-dataidataj) (*C) -datak+=A-datai+; else *C-datak+=B-dataj+; /*while */ while (ilength ) (*C)-datak+= A-datai+; /復制剩余部分 while (jlength ) (*C)-datak+= B-dataj+; /復制剩余部分 (*C)-length=k; return(1); /*合并成功*/約瑟夫問題n設(shè)由n個人圍坐在一個圓桌周圍，現(xiàn)從第s個人開始從1報數(shù)，數(shù)到m的人出列，然后從出列的下一個人重新開始從1報數(shù)，數(shù)到m的人再出列如此反復，直到所