1、6-Sep-20,1,補充內(nèi)容,6-Sep-20,2,靜態(tài)鏈表,某些高級語言中可能不支持指針操作，在這種情況下可以用數(shù)組來實現(xiàn)鏈表結(jié)構(gòu)，這種鏈表稱為靜態(tài)鏈表 靜態(tài)鏈表中各個節(jié)點均是數(shù)組的元素，它的定義如下： #define MAXSIZE 1000 typedef struct ElemType data; int cur; component, SLinkListMAXSIZE; 在這種結(jié)構(gòu)中，除了一個數(shù)據(jù)域之外，還有一個游標域，它用來代替指針表示下一個節(jié)點在數(shù)組中的位置 在靜態(tài)鏈表中插入和刪除元素時只需要游標的值而不需要移動元素,6-Sep-20,3,靜態(tài)鏈表示例,假設線性表為ZHAO,Q

2、IAN,SUN,LI,ZHOU 則用靜態(tài)鏈表表示為： 刪除元素SUN之后的結(jié)構(gòu)為：,6-Sep-20,4,靜態(tài)鏈表的查找算法,int LocateElem_SL(SLinkList S, ElemType e) /在靜態(tài)鏈表中查找第1個值為e的元素 /若找到則返回其位置，否則返回0 i = S0.cur; while(!i ,6-Sep-20,5,靜態(tài)鏈表的空間分配與回收,由于靜態(tài)鏈表是用數(shù)組來實現(xiàn)的，因此 在插入元素時候，需要從數(shù)組的空余空間中找出一個單元給新插入的元素使用 當刪除元素后，該元素所占用的空間需要進行回收，以便該空間能被重新使用 為此可以采用下面的方法： 初始時，將數(shù)組所有空余

3、空間組成一個鏈式結(jié)構(gòu)，頭節(jié)點的cur域指向第一個空余的空間 當插入新元素的時候，將頭節(jié)點cur域指向的空間分給新插入的元素使用，同時修改cur指向下一個空余空間 當刪除一個元素時候，將該空間的插入空余空間鏈表的頭部,6-Sep-20,6,數(shù)組空間初始化,void InitSpace_SL(SLinkList ,初始化數(shù)組元素空間成為一個鏈表,6-Sep-20,7,分配空間給新元素,int Malloc_SL(SLinkList ,i=3,6-Sep-20,8,回收空間,void Free_SL(SLinkList ,k=3,5,3,下標,數(shù)組內(nèi)容,5,4,6-Sep-20,9,刪除節(jié)點算法,v

4、oid Delete_SL(SLinkList ,e=QIAN,5,3,4,ZHAO,3,QIAN,4,SUN,0,0,2,5,0,S,p,k,4,5,6-Sep-20,10,在表尾插入節(jié)點算法,void Insert_SL(SLinkList ,e,5,0,ZHAO,3,QIAN,4,SUN,0,0,2,0,0,S,p,k,r,i,e.data,6-Sep-20,11,用靜態(tài)鏈表實現(xiàn)(A-B)U(B-A),由終端輸入元素先建立集合A的靜態(tài)鏈表S，然后在輸入集合B的元素的同時查找S表，如果存在和B相同的元素，則從S表中刪除它，否則將該元素插入S表 void difference(SLinkLi

5、st ,6-Sep-20,12,(A-B)U(B-A)合并算法（續(xù)）,for(j=1;j=n;j+) scanf(“%d”,b); p=S; k=spaceS.cur; while(k!=spacer.cur /else /for /difference,6-Sep-20,13,隊列典型應用離散事件模擬,在日常生活中經(jīng)常會遇到排隊等待服務的情況 利用隊列和線性數(shù)據(jù)結(jié)構(gòu)可以建立起這類系統(tǒng)的計算機模擬程序以確定平均的服務時間 比如：銀行業(yè)務模擬 一個銀行業(yè)務單位有多個窗口 每時每刻均有用戶到達或離開 當用戶到達的時候，如果某個窗口空閑，則用戶可以直接上前辦理業(yè)務 如果所有窗口均不空閑，則用戶需要在

6、排在最短隊列的后面等待服務 每個用戶辦理的業(yè)務不同，因此服務所需要的時間可以不同 利用我們所學習的隊列知識，我們可以建立這樣一個模擬系統(tǒng)來統(tǒng)計一天中客戶在銀行中逗留的平均時間，從而為提高服務質(zhì)量提供依據(jù),6-Sep-20,14,模擬系統(tǒng)描述,為計算用戶的平均逗留時間，顯然需要記錄每個用戶到達銀行和離開銀行的時間，它們之差即為每個用戶的逗留時間 用所有用戶的逗留時間之和除以總的人數(shù)就可以得到平均逗留時間 用戶到達或離開銀行稱為事件 當用戶達到銀行應記錄其到達時間，同時根據(jù)銀行當前等待服務的情況加入隊列 當用戶離開時要記錄離開時間 整個系統(tǒng)應該以用戶到達或離開事件為基礎進行處理,6-Sep-20,

7、15,離散事件驅(qū)動程序,void Bank_Simulation(int CloseTime) OpenForDay; while(MoreEvent) do EventDrived(Occurtime, EventType); switch (EventType) case A: CustomArrived; break; case B: CustomDeparture;break; default: InValid; CloseForDay; ,6-Sep-20,16,模擬需要的數(shù)據(jù)結(jié)構(gòu)與操作,算法主要的處理對象是事件。用戶到達和用戶離開。 用戶到達的時刻是隨用戶到達自然產(chǎn)生的 用戶離開的

8、時間取決于排隊等候的時間和服務所需要的時間 任意時刻發(fā)生的事件只能有：用戶到達或離開某個窗口 所有的事件構(gòu)成一個有序線性鏈表（按事件發(fā)生的時間） 對于用戶排隊可以用隊列來描述，每個窗口對應一個隊列。 隊列中元素應記錄用戶到達的時間和服務所需要的時間 當用戶到達時候，她應該選擇排在最短隊列的后面 當用戶服務完備后，她要離開銀行，因此要產(chǎn)生一個客戶離開事件 因此模擬程序只需要兩種數(shù)據(jù)類型：有序鏈表和隊列,6-Sep-20,17,數(shù)據(jù)元素類型C描述,typedef struct int OccurTime; int NType; Event, ElemType; /事件類型 0 到達，1-4離開 t

9、ypedef LinkList EventList;/事件鏈表 typedef struct int ArrialTime; int Duration; QElemType; /隊列中各個客戶的信息,6-Sep-20,18,模擬用戶到達事件,在實際的銀行中，客戶達到的時間和要辦理的業(yè)務是隨機的，在模擬程序中可以用隨機數(shù)來模擬 假定第一用戶在時刻0到達，在這個用戶到達的時候需要產(chǎn)生兩個隨機數(shù)：intertime,durtime。前面一個數(shù)用來估計到下面一個客戶到達間隔，后一個數(shù)據(jù)用來估計用戶辦理業(yè)務需要多長時間 假定當前用戶到達的時間為curtime,因此用戶到達的時候需要產(chǎn)生一個新的用戶到達事

10、件，事件發(fā)生的時間為curtime+intertime。這個事件需要根據(jù)事件發(fā)生的時間插入到事件隊列的適當位置 剛到達的用戶還應該插入一個最短的隊列中去；若該隊列為空，則還應該產(chǎn)生一個客戶離開事件插入事件隊列?？蛻綦x開事件的時間應該為curtime+durtime。,6-Sep-20,19,模擬客戶離開事件,當客戶離開時首先要計算逗留時間 然后從隊列中刪除這個客戶，這個時候要檢查隊列是否為空，若不空則應該產(chǎn)生一個新的客戶離開事件 因為一個用戶離開后，后面的用戶就可以接受服務了，那么根據(jù)當前時間和用戶服務所需要的時間可以計算客戶離開的時間,6-Sep-20,20,模擬算法C描述全局變量,Even

11、List ev; /事件鏈表 Event en; /事件 LinkQueue q4; /假定4個隊列 QElemType customer; /客戶 int TotalTime,CustomerNum; /總時間和總客戶數(shù)目 int cmp(Event a, Event b); /比較兩個事件發(fā)生的時間，返回-1，0，1,6-Sep-20,21,模擬算法C描述初始化,void OpenForDay() TotalTime = 0; CustomerNum=0; InitList(ev); en.OccurTime = 0; en.NType=0; OrderInsert(ev,en,(*cmp

12、(); /根據(jù)發(fā)生時間將事件插入鏈表 for(i=0; i4;i+) InitQueue(qi); ,6-Sep-20,22,模擬算法C描述客戶到達,void CustomerArrived() +CustomerNum; Random(durtime,intertime); t = en.OccurTime + intertime; if (t CloseTime) OrderInsert(ev,(t,0),(*cmp(); /插入到達事件 i = Minimum(q); EnQueue(qi,(en.OccurTime,durtime); if (QueueLength(qi= 1) /隊

13、中只有一個人 t=en.OccurTime+durtime; OrderInsert(ev,(t,i), (*cmp(); ,6-Sep-20,23,模擬算法C描述客戶離開,void CustomerDeparture() i = en.NType; DelQueue(qi,customer); TotalTime += en.OccurTime customer.ArrivalTime; /累計客戶逗留時間 if (!QueueEmpty(qi) GetHead(qi,customer); /得到下一個客戶信息 t=en.OccurTime+customer.duration; /計算下一個

14、客戶離開的時間 OrderInsert(ev,(t,i), (*cmp(); /將給事件插入鏈表 ,6-Sep-20,24,完整的模擬算法C描述,void Bank_Simulation(int CloseTime) OpenForDay(); While(!EmptyEventList(ev) DelFirst(GetHead(ev),p); en = GetCurElem(p); if (en.NType = 0) CustomerArrived(); else CustomerDeparture(); printf(“The average time is %fn”, TotalTime

15、/CustomerNum); ,6-Sep-20,25,串的模式匹配,串操作中的子串定位Index(S,T,Pos)通常被稱為模式匹配，子串T被稱為模式串 最簡單的模式匹配方法如下： void Index(SString S, SString T,int pos) i = pos,j=1; while (i T0) return i-T0; else return 0; ,6-Sep-20,26,簡單模式匹配算法示例,S,T,第一趟匹配,i=3,j=3 i=i-j+2=2,回退1,S,T,第二趟匹配,i=2,j=1 i=i-j+2=3,前進,S,T,第三趟匹配,i=7,j=5 i=i-j+2=

16、4,回退3,6-Sep-20,27,簡單模式匹配算法的問題,當出現(xiàn)不匹配的時候，主串的指針需要回退，影響效率 極端情況下比較的次數(shù)與NM成正比 經(jīng)過人們的努力，發(fā)現(xiàn)了一種改進算法，它可以在N+M數(shù)量級上完成模式匹配。 這種算法稱為KMP算法，其改進之處在于：在每一趟比較中，當出現(xiàn)不匹配的情況時，不需要回退指針，而是根據(jù)已經(jīng)得到的“部分匹配”的結(jié)果，將指針后移一段距離后再進行比較,6-Sep-20,28,改進算法說明示例,S,T,第一趟匹配,S,T,第二趟匹配,S,T,第三趟匹配,因為主串i=2必然為b,而T(1)=a肯定不匹配,因為主串i=4,5必然為bc,T(1)=a肯定不匹配,主串6為a不

17、需要比較,6-Sep-20,29,討論一般情況,假設主串為s1s2sn而模式串為p1p2pm，當sipj時，模式串應該向右滑行多長的距離？換句話說，主串中第i個字符（i指針不回退）該與模式串中哪個字符比較呢 假設此時應該與模式串中的第k（kj）個字符比較,那么模式中的前k-1個字符必須滿足下列關(guān)系：,而已經(jīng)得到的部分匹配結(jié)果有：,6-Sep-20,30,k值的確定,根據(jù)上面的結(jié)論有：,對于模式abcac其值為：,6-Sep-20,31,改進后的算法,當當sipj時，讓主串中的第i個字符與模式中第j=next(j)個字符比較 如果相等則i,j均加1 否則j=next(next(j)，如果仍然不相

18、等，則這個過程一直進行下去直到 j=0。此時模式 右移一個位置，即從主 串的下一個位置(i+1)開始從新進行比較,6-Sep-20,32,KMP算法C描述,int Index_KMP(SString S, SString T, int pos) i = pos; j= 1; while(i T0) return i-T0; else return 0; 由此可見改進算法是以next(j)為基礎來運行的，對于給定的模式串，顯然根據(jù)定義我們可以手工推算出next(j)的值，但是右沒有更好的方法可以得到 它的值呢？,6-Sep-20,33,next(j)的計算,特別注意：從上面的分析可以知道，nex

19、t(j)的值完全取決于模式串，與主串沒有任何關(guān)系 首先，根據(jù)定義有：next1=0 假定nextj=k，這表明,6-Sep-20,34,next(j+1)與next(j)的關(guān)系,假定nextj=k，那么nextj+1有兩種可能： （1）pk=pj,這表明在模式串中存在：,于是有：nextj+1=k+1,6-Sep-20,35,next(j+1)計算,（2）pkpj,這相當于一個模式匹配問題，只不過主串和模式串是同一個串，這個時候應該將模式向右移動，使主串第j個字符和模式串中的第nextk=k個字符比較 如果pk=pj，則說明在主串第j+1個字符前面有k個字符的最大子串與模式中從首字符開始的長度

20、為k的子串相等，于是有nextj+1=nextk+1 pjpk,則繼續(xù)將模式串向右滑動nextk個字符，再比較，依次類推，直到找到某個匹配字符或不存在任何k，這個時候根據(jù)定義 nextj+1=1,6-Sep-20,36,第二種情況演示,k,子串,j,k,主串,相當于串比較,next(k)=k,相當于j+1前面由k個字符組成的串與子串頭k個字符組成的子串相同，因此next(j+1)=k+1=next(k)+1,假定next(j)=k,6-Sep-20,37,next(j)計算示例,當j=7時，next(6)=3,需要比較p6和p3,由于p6p3,所以需要繼續(xù)比較;由于next(3)=1,故需比較

21、p6和p1,由于p6p1,所以需要繼續(xù)比較,由于next(1)=0,所以next(7)=1; 當j=8時，next(7)=1,需要比較p7和p1,由于p7=p1,所以next8=next7+1=2,6-Sep-20,38,next(j)函數(shù)C描述,void get_next(SString T,int ,6-Sep-20,39,Huffman編碼存儲C描述,typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; typedef char *HuffmanCode;,6-Sep-20,40,Huffman編碼算法(初始化）,void HuffmanCoding(HuffmanTree ,6-Sep-20,41,Huffman編碼算法(建樹）,for(i=n+1;i=m;i+) Select(HT,i-1,s1,s2); /從前面i-1元素中選兩個最小的值 HTs1.parent = i; HTs2.parent=i; HTi.lchild=s1;HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; ,6-Sep-20,42,Huffman編