數(shù)據(jù)結構與算法--線性表1

1、數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法 2/42第二講第二講 順序表順序表本講知識點：本講知識點： (1)熟悉順序表的優(yōu)缺點熟悉順序表的優(yōu)缺點 (2)通過應用加深順序表的操作通過應用加深順序表的操作 (3)簡單了解鏈表的結點簡單了解鏈表的結點重點：重點：順序表的應用順序表的應用難點：難點：順序表應用中算法的改進順序表應用中算法的改進3/42一、順序表的優(yōu)缺點一、順序表的優(yōu)缺點 優(yōu)點：優(yōu)點： 無須為表示節(jié)點間的邏輯關系而增加額外的存儲空間無須為表示節(jié)點間的邏輯關系而增加額外的存儲空間 邏輯相鄰，物理相鄰邏輯相鄰，物理相鄰; ;可隨機存取任一元素可隨機存取任一元素 缺點缺點: : 插入、刪除操作需要移動大量

2、的元素插入、刪除操作需要移動大量的元素 要求占用連續(xù)的存儲空間，存儲分配只能預先進行要求占用連續(xù)的存儲空間，存儲分配只能預先進行 預先分配空間需按最大空間分配，利用不充分預先分配空間需按最大空間分配，利用不充分4/42提出問題提出問題設計順序表存儲的兩個集合求差集的算法。設計順序表存儲的兩個集合求差集的算法。25 33 57 50 16 48 09 63 1 2 3 4 5 6 7 8la12 50 23 79 04 34 25 13 lblc程序實現(xiàn)見文件夾s2_15/4225 33 57 50 16 48 09 63 1 2 3 4 5 6 7 8la12 50 23 79 04 34 2

3、5 13 lblc下標下標aPositionbPosition分析問題分析問題6/42分析問題分析問題第一步，取第一步，取lala的數(shù)據(jù)的數(shù)據(jù)第二步，到第二步，到lblb順序查找，查看是否存在順序查找，查看是否存在第三部，判斷第三部，判斷不存在，則插入不存在，則插入lclc；存在，則繼續(xù)循環(huán)轉第一步存在，則繼續(xù)循環(huán)轉第一步程序實現(xiàn)見文件夾s2_17/42/ 文件路徑名文件路徑名:s2_1alg.h template void Difference(const SqList &la, const SqList &lb, SqList &lc)/ 操作結果操作結果: 用用l

4、c返回返回la和和lb表示的集合的差集表示的集合的差集/ 方法方法: 在在la中取出元素中取出元素,在在lb中進行查找中進行查找,如果未在如果未在lb中中/出現(xiàn)了出現(xiàn)了,將其插入到將其插入到lcElemType aItem, bItem;lc.Clear();/ 清空清空lc解決問題解決問題8/42for (int aPosition = 1; aPosition = la.Length(); aPosition+)la.GetElem(aPosition, aItem);/ 取出取出la的一個元素的一個元素aItembool isExist = false;/ 表示表示aItem是否在是否在

5、lb中出現(xiàn)中出現(xiàn)for (int bPosition = 1; bPosition = lb.Length(); bPosition+)lb.GetElem(bPosition, bItem);/ 取出取出lb的一個元素的一個元素bItem解決問題解決問題9/42if (aItem = bItem)isExist = true;/ aItem同時在同時在la和和lb中中/ 出現(xiàn)出現(xiàn),置置isExist為為truebreak;/ 退出內(nèi)層循環(huán)退出內(nèi)層循環(huán) if (!isExist) / aItem在在la中出現(xiàn)中出現(xiàn),而未在而未在lb中未出現(xiàn)中未出現(xiàn),/將其插入到將其插入到lc中中l(wèi)c.Inse

6、rt(lc.Length() + 1, aItem); 解決問題解決問題10/42思考：思考：若數(shù)據(jù)量龐大，這個效率？若數(shù)據(jù)量龐大，這個效率？11/42課堂實戰(zhàn)課堂實戰(zhàn)問題描述：問題描述：已知順序表已知順序表la的元素類型為的元素類型為int，設計，設計算法將其調(diào)整為左右兩部分，左邊的所有元素算法將其調(diào)整為左右兩部分，左邊的所有元素為奇數(shù)，右邊的為偶數(shù)。為奇數(shù)，右邊的為偶數(shù)。要求：要求：T(n)=O(n)輸入說明：輸入說明：數(shù)據(jù)個數(shù)數(shù)據(jù)個數(shù)n和和n個個int型數(shù)據(jù)型數(shù)據(jù)輸出說明：輸出說明：調(diào)整后的調(diào)整后的n個個int型數(shù)據(jù)型數(shù)據(jù)程序實現(xiàn)見文件夾s2_212/421 2 3 4 5 6 7 8l

7、aleftPositionrightPosition25 34 57 50 16 48 09 6225 34 57 50 16 48 09 62laleftPositionrightPosition25 34 57 50 16 48 09 62laleftPositionrightPosition13/4225 34 57 50 16 48 09 62laleftPositionrightPosition0934交換交換25 09 57 50 16 48 34 62laleftPositionrightPositionleftPositionrightPosition25 09 57 50 1

8、6 48 34 62laleftPositionrightPositionrightPositionleftPosition14/42算法實現(xiàn)算法實現(xiàn)15/42算法實現(xiàn)算法實現(xiàn)16/42類似考研題類似考研題17/42 經(jīng)典問題：約瑟夫環(huán)經(jīng)典問題：約瑟夫環(huán) n n個人圍成一圈，從第個人圍成一圈，從第s s個人開始報數(shù)，報到個人開始報數(shù)，報到m m的人出列，從下一個人再重新報數(shù)，報到的人出列，從下一個人再重新報數(shù)，報到m m的的人出列，如此下去，直至所有人都出列。試編人出列，如此下去，直至所有人都出列。試編寫算法，輸出出列人的編號。寫算法，輸出出列人的編號。程序實現(xiàn)見文件夾s2_Joseph二、順

9、序表的應用二、順序表的應用18/42（1 1）把）把n n個人看成一個環(huán)。個人看成一個環(huán)。（2 2）設當前有）設當前有 i i 個人，下一出列的人為個人，下一出列的人為s s。 s=s=（s + m - 1s + m - 1）% i% i（3 3）將出列的人刪除。）將出列的人刪除。123456789則：則： i=9 s=1 m=4舉例：舉例：9 9個人，從個人，從1 1號開始報數(shù)，密碼號開始報數(shù)，密碼4 4算法思想算法思想19/42123456789s=1據(jù)公式據(jù)公式s=(s+m-1)%i i=9 m=4for( j=s; j=i-1; j+) L.elemj = L.elemj+1;4pri

10、nt20/42123456789第一輪第一輪123456789m=44print123567894計算出計算出s=4s=41 2 3 4 5 6 7 8 921/4212356789123567894m=4計算出計算出s=7s=78123567941235679841 2 3 4 5 6 7 8 922/42123567984m=41256798431256793841 2 3 4 5 6 7 8 923/42125679384m=4計算出計算出s=0125673849125679384則則 s=i 即即s=61 2 3 4 5 6 7 8 924/42125679384m=4計算出計算出s=

11、41257938461257693841 2 3 4 5 6 7 8 925/421257693841 2 3 4 5 6 7 8 9m=4計算出計算出s=3127569384m=4計算出計算出s=0則則 s=i 即即s=3127569384m=4計算出計算出s=0則則 s=i 即即s=212756938426/42算法思路算法思路第一，共需要循環(huán)多少趟？第一，共需要循環(huán)多少趟？第二，每趟重復做什么動作？第二，每趟重復做什么動作？第一，據(jù)公式求第一，據(jù)公式求s s值值第二，暫存第二，暫存s s處值到處值到t t里里第三，后面的數(shù)前移第三，后面的數(shù)前移第四，放數(shù)第四，放數(shù)t t到到i i位置位置

12、有遺漏的動作嗎？有遺漏的動作嗎？27/42/ 文件路徑名文件路徑名:s2_Josephalg.h void Joseph(SqList &la)/ 約瑟夫環(huán)問題約瑟夫環(huán)問題int Start=1; / 從從1號開始報數(shù)號開始報數(shù)int Mima=4; /密碼是密碼是4int tmp, tmp2;int i, j;算法實現(xiàn)算法實現(xiàn)28/42for (i=la.Length();i1;i-)Start=(Start+Mima-1)%i;if (Start = 0)/ 余數(shù)為余數(shù)為0Start=i;la.GetElem(Start,tmp);for(j=Start;j=i-1;j+)la.G

13、etElem(j+1,tmp2);la.SetElem(j,tmp2);la.SetElem(i,tmp);算法實現(xiàn)算法實現(xiàn)29/42課堂實戰(zhàn)課堂實戰(zhàn)-程序填空程序填空問題描述：問題描述：已知已知la、lb和和lc為為3個元素值遞增有序個元素值遞增有序的順序表，請對表的順序表，請對表la作如下運算：刪去那些既作如下運算：刪去那些既在在lb中出現(xiàn)又在中出現(xiàn)又在lc中出現(xiàn)的元素。中出現(xiàn)的元素。30/42template void ADelBC(SqList &la, const SqList &lb, const SqList &lc)/ 操作結果操作結果: la,lb,l

14、c遞增有序，刪除遞增有序，刪除la中，同時在中，同時在lb和和lc里出現(xiàn)的里出現(xiàn)的數(shù)據(jù)數(shù)據(jù)ElemType aItem, bItem, cItem;for (int aPosition = 1; aPosition = la.Length(); aPosition+)bool IsDelete = false;la.GetElem(aPosition, aItem);程序填空程序填空31/42for (int bPosition = 1; bPosition=lb.Length(); bPosition+) lb.GetElem( , bItem); if (bItem = aItem) fo

15、r (int cPosition =1; cPosition=lc.Length(); cPosition+) lc.GetElem(cPosition, ); if(cItem = ) la.Delete(aPosition, aItem);IsDelete= ;break; if(IsDelete = true) break; /* end of for aPosition */ /*end of ADelBC */程序填空程序填空32/42三、單鏈表三、單鏈表 用一組用一組任意的任意的存儲單元存儲線性表的數(shù)據(jù)元素；存儲單元存儲線性表的數(shù)據(jù)元素； 利用利用指針指針實現(xiàn)了用不相鄰的存儲單元存

16、放邏輯上相鄰的實現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素；元素； 每個數(shù)據(jù)元素每個數(shù)據(jù)元素a ai i，除存儲本身信息外，還需存儲其直接除存儲本身信息外，還需存儲其直接后繼的信息。后繼的信息。33/42例如：例如： 姓氏線性表姓氏線性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)頭指針頭指針 31head存儲地址1713192531374343131NULL3719257數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU三、單鏈表三、單鏈表34/42ZHAOQIANSUNLIZHOUWUZHENGWANGH邏輯上的示意圖：邏輯上的示意圖： 三

17、、單鏈表三、單鏈表35/42結點如何實現(xiàn)？結點如何實現(xiàn)？ (*p)表示表示p所指所指向的結點向的結點(*p).data表示表示p指向結指向結點的數(shù)據(jù)域點的數(shù)據(jù)域(*p).next表示表示p指向結指向結點的指針域點的指針域三、單鏈表三、單鏈表36/42在單鏈表第一個結點前附設一個結點叫在單鏈表第一個結點前附設一個結點叫 。頭結點指針域為空表示線性表為頭結點指針域為空表示線性表為空?？?。ha1a2頭結點頭結點an .h空表空表頭結點：頭結點： 37/42結點類結點類參見文件夾參見文件夾S2_3里的文件里的文件node.h38/42簡單線性鏈表類簡單線性鏈表類參見文件夾參見文件夾S2_3里的文件里的文件simple_lk_list.h39/42簡單線性鏈表類簡單線性鏈表類(續(xù)續(xù))40/4241/42本講小結本講小結（1）復習鞏固）復習鞏固C+程序編寫的細節(jié)知識程序編寫的細節(jié)知識（2）熟練掌