數(shù)據(jù)結構考研課程總結課件

1、數(shù)據(jù)結構 主講 劉鐵銘單位工院一系二教Tel: 319468/22/20221數(shù)據(jù)結構講課安排：串講全書內(nèi)容典型習題分析前年、去年考題分析 8/22/20222數(shù)據(jù)結構第一章 概 論數(shù)據(jù)結構及其概念 如何評價一個算法8/22/20223數(shù)據(jù)結構第一章 概 論1.1 數(shù)據(jù)結構的概念一、術語1.數(shù)據(jù)(Data): 是信息的載體，能被計算機識別、存儲、加工處理。2.數(shù)據(jù)元素(Data Element): 數(shù)據(jù)的基本單位, 即數(shù)據(jù)集合中的一個個體。也稱元素、結點、頂點、記錄數(shù)據(jù)項:是具有獨立含義的最小標識單位關鍵字（key)：唯一能識別一個數(shù)據(jù)元素的數(shù)據(jù)項。數(shù)據(jù)元素由數(shù)據(jù)項(data item)組成8

2、/22/20224數(shù)據(jù)結構 3、數(shù)據(jù)類型(Data Type): 是具有相同性質(zhì)的計算機數(shù)據(jù)的集合及在這個集合上的一組操作。原子數(shù)據(jù)類型(atomic data type)結構數(shù)據(jù)類型(aggregate data type)4、數(shù)據(jù)結構 數(shù)據(jù)的邏輯結構 數(shù)據(jù)的存儲結構 數(shù)據(jù)的運算：既對數(shù)據(jù)施加的操作8/22/20225數(shù)據(jù)結構邏輯結構：(有時直接稱為數(shù)據(jù)結構）線性結構：線性表、棧、隊列、串(最多只有一個直接前趨和一個直接后繼)非線性結構：樹 、圖、多維數(shù)組、廣義表說明：1、邏輯結構與數(shù)據(jù)元素本身的形式、內(nèi)容無關2、邏輯結構與數(shù)據(jù)元素的相對位置無關3、邏輯結構與所含結點個數(shù)無關8/22/202

3、26數(shù)據(jù)結構存儲結構：順序存儲方法：數(shù)據(jù)元素在內(nèi)存中按序連續(xù)存儲， 結點間的邏輯關系由存儲單元的鄰接關系來體現(xiàn)鏈接存儲方法：用指針指出其直接后繼結點的存儲位置， 結點間的邏輯關系由存儲單元的鄰接關系來體現(xiàn)索引存儲方法：數(shù)據(jù)元素連續(xù)存放，再設一個索引表（有序），索引表由索引項組成，每個索引項由關鍵字和地址構成 分為稠密索引和稀疏索引散列存儲方法：確定散列函數(shù)后，根據(jù)結點的關鍵字直接 計算出該結點的存儲地址。8/22/20227數(shù)據(jù)結構關系：邏輯結構是從邏輯關系上描述數(shù)據(jù)，與存儲無關，是獨立于計算機的。邏輯結構是從具體問題抽象出來的數(shù)學模型存儲結構是邏輯結構用計算機語言的實現(xiàn)（亦稱映象）數(shù)據(jù)的運算

4、是定義在數(shù)據(jù)的邏輯結構上的一個運算的集合運算的實現(xiàn)與存儲結構密切相關邏輯結構與存儲結構是多對多的關系8/22/20228數(shù)據(jù)結構例：一個學生成績表：是一個數(shù)據(jù)結構每行是一個結點（或記錄），由學號、姓名、各科成績 及平均成績等數(shù)據(jù)項組成。邏輯關系：線性結構存儲結構：表的運算：8/22/20229數(shù)據(jù)結構 邏輯結構上定義的基本運算在存儲結構上的實現(xiàn)是通過算法來描述的。一、算法定義 算法是對特定問題求解步驟的一種描述，由有限的指令序列構成，其中每一條指令表示一個或多個操作。第一章 概 論1.3 算法描述8/22/202210數(shù)據(jù)結構 二、算法應具有的五個特性：（1）輸入 一個算法有零個或多個的輸入，

5、它們是算法開始前給出的最初量（2）輸出 一個算法至少有一個輸出，它們是同輸入 有某種關系的量（3）有窮性 每一條指令的執(zhí)行次數(shù)必須是有限的（4）確定性 每一條指令必須有確切的含義，無二義性（5）可行性 每條指令的執(zhí)行時間都是有限的。8/22/202211數(shù)據(jù)結構第一章 概 論一、算法評價五要素 （1）正確性（2）執(zhí)行算法所耗費的時間（3）執(zhí)行算法所耗費的空間（4）可讀性（5）健壯性1.4 算法分析8/22/202212數(shù)據(jù)結構第一章 概 論二、算法的時間復雜度 一個算法所耗費的時間:該算法中每條語句的執(zhí)行時間之和。每條語句的執(zhí)行時間：該語句的執(zhí)行次數(shù)乘以該語句執(zhí)行一次所需時間。頻度：語句重復執(zhí)

6、行的次數(shù)算法的時間耗費T(n)=每條語句的執(zhí)行的時間=（語句頻度語句執(zhí)行一次所需時間） =語句頻度算法的時間復雜度：就是算法的時間耗費T(n)8/22/202213數(shù)據(jù)結構第一章 概 論三、（漸進）時間復雜度(O(f(n)當問題的規(guī)模n趨向無窮大時，時間復雜度T(n)的數(shù)量級（階）稱為算法的漸近時間復雜度，簡稱時間復雜度四、最壞時間復雜度依據(jù)數(shù)據(jù)集中可能出現(xiàn)的最壞情況估算出的時間復雜度稱為最壞時間復雜度。五、平均時間復雜度在假設數(shù)據(jù)集的分布是等概率的條件下，估算出的時間復雜度稱為平均時間復雜度。例：順序查找8/22/202214數(shù)據(jù)結構五、空間復雜度S(n)： 算法所耗費的存儲空間，仍是問題規(guī)

7、模n的函數(shù)。第一章 概 論8/22/202215數(shù)據(jù)結構第一章 概 論本章要求:1、掌握數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結構等基本概念。2、掌握數(shù)據(jù)邏輯結構和物理結構的分類。3、學會算法分析的基本方法。8/22/202216數(shù)據(jù)結構第二章 線性表本章要學習的主要內(nèi)容1、線性表的邏輯結構及基本運算2、線性表的順序存儲結構3、線性表的鏈式存儲結構：單鏈表、循環(huán)鏈表、雙鏈表、靜態(tài)鏈表4、順序表和鏈表的比較8/22/202217數(shù)據(jù)結構2.1 線性表的概念及運算1.描述: 線性表是由n (n=0)個數(shù)據(jù)元素(點)a1,a2,.,ai,.,an組成的有限序列。其中，數(shù)據(jù)元素的個數(shù)n定義為表長。當n=0時稱為空表，非

8、空的線性表(n0)記為： (a1,a2,.,ai,.,an)一、邏輯結構 注意: 1.數(shù)據(jù)元素ai是一個抽象的符號 2. ai可取各種數(shù)據(jù)類型 3. 一般情況下,同一線性表中的元素具有相同的數(shù)據(jù)類型 4. i是元素的序號 (1=i=n) 2.邏輯特征：僅有一個開始結點和一個終端結點，并且所有結點都最多只有一個直接前趨和一個直接后繼8/22/202218數(shù)據(jù)結構線性表的常見基本運算包括： （1）置空表SETNULL(L) （2）建表CREATLIST(L)二、線性表的運算 （4）取結點GET(L,i) （5）定位LOCATE(L,x) （6）插入INSERT(L,x,i) （7）刪除DELETE

9、(L,i) （3）求表長LENGTH(L)復雜的運算可以由這些基本運算組合來實現(xiàn)8/22/202219數(shù)據(jù)結構2.2 線性表的順序存儲1、順序存儲：將線性表的結點按邏輯次序依次存放在一組地址連續(xù)的存儲單元里。 3、存儲地址的計算： LOC(ai)=LOC(a1)+(i-1)*c 1=idata=ch; s-next=head; head=s; ch=getchar( );return head;8/22/202228數(shù)據(jù)結構2.3.2 單鏈表上的基本運算（實現(xiàn)）尾插法建表：將新結點插入到當前鏈表的表尾（需引入r）dsrabcHeadr不帶頭結點的尾插法：插入時，第一個結點的處理與其它結點的處理

10、有區(qū)別。 結束時，空表和非空表的處理有區(qū)別。8/22/202229數(shù)據(jù)結構Linklist *CREATLISTR( ) char ch; linklist *head,*s,*r; head=NULL; r=NULL; ch=getchar( ); while (ch!=$) s=malloc(sizeof(linklist) ; s-data=ch; if(head=NULL) head=s else r-next=s; r=s; ch=getchar( ); if (r!=NULL) r-next=NULL; return head;8/22/202230數(shù)據(jù)結構2.3.2 單鏈表上的基

11、本運算（實現(xiàn)）尾插法建表：將新結點插入到當前鏈表的表尾（需引入r）dsrabcHeadr不帶頭結點的尾插法：插入時，第一個結點的處理與其它結點的處理有區(qū)別。結束時，空表和非空表的處理有區(qū)別。帶頭結點的尾插法：1）鏈表第一個位置上的操作與其它位置上的操作相一致。2）空表和非空表的處理相一致。8/22/202231數(shù)據(jù)結構2.3.2 單鏈表上的基本運算（實現(xiàn)）Linklist *CREATLISTR1() char ch; linklist *head,*s,*r; head=malloc(sizeof(linklist); r=head; ch=getchar(); while(ch!=“$”)

12、 s=malloc(sizeof(linklist); s-data=ch; r-next=s; r=s; ch=getchar(); r-next=NULL; return head; dsrcHeadr8/22/202232數(shù)據(jù)結構2.3.2 單鏈表上的基本運算（實現(xiàn)） 二、查找運算（1）按序號查找 GET（L，i） 給定一個序號，在單鏈表中查找該序號對應的結點， 若結點存在，則返回該結點的指針，否則返回空指針。方法：非隨機存儲結構的鏈表，決定了上述查找運算只能通過掃描單鏈表來完成。設置一個計數(shù)器j一個p，初始指向頭結點P向后每移動一個位置j+當j=i時返回8/22/202233數(shù)據(jù)結構按

13、值查找即在鏈表中查找是否有值等于給定值key的結點。若有則返回首次找到的其值為key的結點的指針，否則返回NULL。算法描述如下： linklist *locate(head,key) linklist *head; datatye key; linklist *p; p=head next;在等概率的情況下，該算法的平均時間復雜度亦為O(n)（2）按值查找 LOCATE（head，key）2.3.2 單鏈表上的基本運算（實現(xiàn)）while (p!=NULL) if (p data!=key) p=p next; else break ; return p; 8/22/202234數(shù)據(jù)結構 3.

14、插入運算 （1）后插操作: 在指針p所指結點之后插入xs （2）前插操作: 在指針p所指結點之前插入Headp時間復雜度度O(1)xs平均時間復雜度 O(n)先從頭指針起, 順鏈找到*p的前趨結點*q.Headpq8/22/202235數(shù)據(jù)結構Headpax 3.插入運算:將前插操作轉變?yōu)楹蟛宀僮鱴sxsaINSERTBEFORE(p,x)linklist *p;datatype x;linklist *s;s=malloc(sizeof(linklist);s-data=p-data;s-next=p-next;p-data=x;p-next=s;時間復雜度 O(1)應盡量將單鏈表上的插入操

15、作轉化為后插操作！8/22/202236數(shù)據(jù)結構 4.刪除運算時間復雜度 O(1)刪除指定結點的直接后繼Headprr=p-next;p-next=r-next;free(r);刪除指定結點時間復雜度O(n)鏈表的優(yōu)點:在鏈表上實現(xiàn)插入、刪除運算無須移動結點，僅須修改指針改進?8/22/202237數(shù)據(jù)結構2.單循環(huán)鏈表的特點：鏈表尾結點的next域不為空，而是指向頭結點或開始結點。（優(yōu)點：從任一結點開始，均可找到其前趨和后繼結點。）3、引入單循環(huán)鏈表的目的在于方便一些運算的實現(xiàn)。實用中常采用尾指針單循環(huán)鏈表,而不是頭指針單循環(huán)鏈表。4、單循環(huán)鏈表上的操作與單鏈表基本一致 差別僅在于：循環(huán)控制

16、條件不是判空，而是判斷是否等于頭指針或尾指針。2.3.3 單循環(huán)鏈表1.循環(huán)鏈表:是一種首尾相接的鏈表單循環(huán)鏈表雙循環(huán)鏈表8/22/202238數(shù)據(jù)結構 1. 雙鏈表的特點：每個結點有兩個指針域，分別指向其直接 前趨和后繼。2.雙鏈表存儲結構描述如下： typedef struct dnode datatype data; struct dnode *prior,*next; dlinklist; dlinklist *head; 對于雙向鏈表，當將頭、尾結點鏈起來時，便成了雙向循環(huán)鏈表。2.3.4 雙鏈表 priornextdata為了指示雙鏈表，也須引入一個頭指針head，指向其開始結點。

17、8/22/202239數(shù)據(jù)結構3.雙向鏈表基本運算的實現(xiàn)：（1）刪除運算（2）插入運算插入和刪除都非常方便p-prior-next=p=p-next-prior刪除運算DELETENODE（p） /*刪除雙鏈表結點*p */dlinklist *p; p-prior-next=p-next; p-next-prior= p -prior; free(p);Headp8/22/202240數(shù)據(jù)結構插入運算DINSERTBEFORE(p,x)dlinklist *p;datatype x;dlinklist *s;Pxss=malloc(sizeof(dlinklist);s-data=x;s-p

18、rior=p -prior;s-next=p;p -prior -next=s;p -prior=s;8/22/202241數(shù)據(jù)結構2.3.5 靜態(tài)鏈表 實現(xiàn)方法 存儲空間 分配和釋放 靜態(tài)鏈表 游 標 預分配的一個連續(xù)空間 用戶定義 動態(tài)鏈表 指 針 內(nèi)存所有可用空間 系統(tǒng)提供 靜態(tài)鏈表與動態(tài)鏈表的區(qū)別8/22/202242數(shù)據(jù)結構 2、靜態(tài)鏈表存儲結構描述如下：define maxsize 1024typedef int datatype;typedef int cursor ; typedef struct datatype data; 數(shù)據(jù)域 cursor next; 游標 node;

19、 node nodepoolmaxsize; 存儲池 cursor av; 游標變量 2.3.5 靜態(tài)鏈表1、用數(shù)組和“游標”實現(xiàn)鏈式存儲的方法是： 事先定義一個規(guī)模較大的結構數(shù)組作為備用結點空間（即存儲池），當申請結點空間時，從存儲池中取出結點，當釋放結點空間時，將其歸還于存儲池內(nèi)。采用這種方法實現(xiàn)的鏈表稱為靜態(tài)鏈表。12Maxsize-13NULL012Maxsize-1av0nodepoolmaxsize8/22/202243數(shù)據(jù)結構說明:靜態(tài)鏈表也可以用頭指針L唯一指示 ,L為cursor類型 3、可用空間表:將存儲池中所有空閑結點鏈成一個頭指針為av的單鏈表,構成一個可用空間表8/2

20、2/202244數(shù)據(jù)結構2.3.5 靜態(tài)鏈表12Maxsize-13NULL012Maxsize-1av1nodepoolmaxsize初始化：INITALIZE() int i; for (i=0;idata=x; p-next=top; return p;8/22/202256數(shù)據(jù)結構Linkstack *POPLSTACK(top,datap)linkstack *top;datatype *datap; linkstack *p; if(top=NULL) printf(“underflow”); return NULL; else *datap=top-data; p=top; to

21、p=top-next; free(p); return top; 2） 退棧 *POPLSTACK(top,datap)8/22/202257數(shù)據(jù)結構3.2 棧的應用舉例1. 文字編輯器2. 函數(shù)的遞歸調(diào)用（p47)8/22/202258數(shù)據(jù)結構3.3 隊 列1定義：隊列(queue) 是一端進行刪除另一端進行插入的線性表。允許插入的一端稱為隊尾(rear) ，允許刪除的一端稱為隊頭(front)。2特點： 先入隊(即插入隊尾）的元素必將被先刪除(即出隊）。因此，隊列是一種先進先出(First In First Out)的線性表。3.3.1 隊列的概念及運算出隊入隊隊頭隊尾a1 a2 an8/

22、22/202259數(shù)據(jù)結構 3隊列的基本運算： （1）SETNULL（Q）置隊空 （2）EMPTY（Q）判隊空 （3）FRONT（Q）取隊頭元素,隊中元素保持不變 （4）ENQUEUE（Q,x) 將元素x入隊 （5）DEQUEUE（Q）出隊,函數(shù)返回原隊頭元素8/22/202260數(shù)據(jù)結構3.3.2 順 序 隊 列1 定義：采用順序存儲結構的隊列稱為順序隊列。 規(guī)定：front總是指向當前隊頭元素的前一個位置 rear指向當前隊尾元素的位置2 順序隊列存儲結構描述如下： typedef struct datatype datamaxsize; int front,rear; sequeue;

23、sequeue *sq;8/22/202261數(shù)據(jù)結構4 3 2 1 0sq-rearsq-front sq-rear4 3 2 1 0DCBA4 3 2 1 0DC 空隊列 ABCD入隊 AB出棧sq-front sq-front sq-rear3 順序隊列指針圖示4 順序隊列基本運算初始時，sqrear=sq front=-1,在不考慮溢出的情況下，入隊和出隊的運算如下： 入隊： sq rear+; sq datasq rear=x;出隊： sq front+;8/22/202262數(shù)據(jù)結構隊空： sq rear=sq front隊滿： sq rear sq front=maxsize下溢

24、： 隊空時，若要進行出隊操作時發(fā)生上溢： 隊滿時，進行入隊操作時出現(xiàn)?！凹偕弦纭保寒?sq-rear=maxsize-1但隊列并不滿時進行入隊操作.sqrear=4sqfront=143210edcba這種情況（即sq-rear=maxsize-1)下若要進行入隊運算,sqrear的值將超出下標范圍，故不能進行這種運算，但此時整個隊列空間并沒用完。 4 幾種特殊情況8/22/202263數(shù)據(jù)結構解決“假上溢”的方法有兩種： （1）當元素出隊或出現(xiàn)假上溢時，移動隊列元素。 sqrear=4sqfront=143210edcbaedc43210sqrear=2sqfront= -1移動元素后（2）

25、采用循環(huán)隊列：即sq-data0 接在sq-datamaxsize-1之后循環(huán)隊列的示意圖054321sqrear=0sqfront=48/22/202264數(shù)據(jù)結構采用循環(huán)隊列后，進行入隊和出隊運算時，頭、尾指針加1操作應如下進行： 出隊： sq front=(sq front+1)% maxsize; 入隊： sq rear=(sq rear+1)% maxsize;循環(huán)隊列如何判斷隊空和隊滿? 方法一：引入標志flag 若 (sq front=sq rear)&(flag=0),則隊空,不能出棧。 若 (sq front=sq rear)&(flag=1),則隊滿,不能入棧。054321

26、sqrear=5sqfront=5054321sqfront=5sqrear=48/22/202265數(shù)據(jù)結構 方法二：犧牲一個元素的空間（sq-datasq-front)，避免隊滿時頭、尾指針指向同一位置。 若 sq front=sq rear，則隊空。 若 (sq rear+1)%maxsize= sq front，則隊滿。054321sqrear=1sqfront=1054321sqfront=5sqrear=48/22/202266數(shù)據(jù)結構3.3.3 鏈 隊 列1 、定義：采用鏈式存儲結構的隊列稱為鏈隊列。（是限制在表頭刪除在表尾插入的單鏈表）2 、鏈隊列存儲結構描述 typedef

27、struct linklist *front,*rear; linkqueue; linkqueue *q; 為了運算實現(xiàn)的方便，在隊頭結點前引入一個頭結點。初始時（即隊空）鏈隊的頭、尾指針均指向頭結點。 front rear q頭結點qrearfront rear q頭結點 qfront隊頭結點q-front=q-rear8/22/202267數(shù)據(jù)結構1）入隊ENQUEUE（q,x)類似于單鏈表的尾插法8/22/202268數(shù)據(jù)結構2）出隊qrearfront rear q頭結點 qfront隊頭結點*sfront rear q頭結點a1*s front rear q頭結點S=q-front

28、-next; q-front-next=s-next; free(s);隊列長度等于1時，不但修改頭結點的指針域，還需尾指針。隊列長度大于1時，只需修改頭結點的指針域，尾指針不變。8/22/202269數(shù)據(jù)結構解決方法：出隊時只修改頭指針，刪除頭結點，使鏈隊列上的隊頭結點成為新的鏈表的頭結點，隊列上的第2個結點成為隊頭結點。即物理上刪除頭結點，邏輯上刪除對頭結點。即使當前隊列長度為1，也不用修改尾指針。qrearfront rear q頭結點 隊頭結點*s8/22/202270數(shù)據(jù)結構串(即字符串）是一種特殊的線性表，其每個結點僅由一個字符組成。4.1 串及其運算4.1.1 串的基本概念 1.

29、串(string):是由零個或多個字符組成的有限序列。 一般記為S=“a1a2.an”, 其中：S為串名，a1a2an為串值；ai(1=i=n)可 以是字母、數(shù)字和其它字符； 注意：僅含一個空格的串（“”）和空串（“ ”）是不同的兩個串。2.串長度：串中所含的字符個數(shù) 空串：長度為零的串（不含任何字符，和空格串嚴格區(qū)分）第四章 串8/22/202271數(shù)據(jù)結構4.子串在主串中的序號：子串在主串中第一次出現(xiàn)時其第一個字符在主串中的序號。S1=“Iamastudent.”S2=“student”S2在S1中的序號為83.子串： 串中任意個連續(xù)的字符組成的子序列,該串相應稱為主串?？沾疄槿我獯淖哟?/p>

30、，任意串為其自身的子串。兩串相等當且僅當兩串長度相等且對應位置上的字符相同。5. 在程序中使用的串可分為串常量和串變量S2=“student”將串常量命名為S2char object=“datastructure”第四章 串8/22/202272數(shù)據(jù)結構4.1.2 串的基本運算 串的基本運算有九種，具體如下（p61）（1）賦值：=（2）聯(lián)接： strcat(ST1,ST2) （3）求串長：strlen(S) （4）求子串：substr(S,i,j) （5）比較串的大?。簊trcmp(S,T) （6）插入：insert(S1,i,S2) （7）刪除：delete(S,i,j) （9）置換：rep

31、lace(S1,i,j,S2)， repl(S,T,V) 8/22/202273數(shù)據(jù)結構4.2 串的存儲結構 串可以分別采用順序、鏈式和索引存儲結構實現(xiàn)存儲。1）用字符數(shù)組描述1、順序存儲 串中的字符被順序地存儲在內(nèi)存中相鄰的存儲單元中。采用順序存儲結構的串稱為順序串。 H o w a r e y o u ? . 串S的順序存儲示意圖S=“How are you?”#define maxsize 32char smaxsize;8/22/202274數(shù)據(jù)結構 ） 順序串存儲結構描述： #define maxsize 128;typedef struct char chmaxsize; int

32、curlen; seqstring;串字符存儲空間串長度 缺點： 順序串上插入、刪除運算不方便。8/22/202275數(shù)據(jù)結構 2. 鏈式存儲 采用鏈式存儲結構的串稱為鏈串，鏈串中結點的數(shù)據(jù)域既可存儲單個字符，也可存儲多個字符，結點數(shù)據(jù)域存儲字符的個數(shù)稱為結點的大小。 顯然，結點大小大于1的鏈串，其結點的存儲密度提高了，但同時也帶來了問題： (1) 如何處理鏈串的最后一個結點，因為串所含字符數(shù)不一定是結點大小的整數(shù)倍。 (2) 插入、刪除運算實現(xiàn)起來不方便。(p64)8/22/202276數(shù)據(jù)結構 typedef struct linknode char data; struct linkno

33、de *next; linkstring; linkstring *s;如果結點大小不為1，則此處應說明一個字符數(shù)組。 鏈串存儲結構描述如下： 8/22/202277數(shù)據(jù)結構 1）帶長度的名字表 2）帶末指針的名字表 3）帶特征位的名字表 4）帶位移量的名字表 3. 索引存儲特點：將串的串名作為關鍵字組織名字表(即索引表)，名字表中的每一項記錄了串名和串值存放單元的起址及確定串長的有關數(shù)據(jù)。 名字表一般采用順序存儲方式存儲。其組織形式主要有如下幾種：(p65)8/22/202278數(shù)據(jù)結構 本節(jié)討論子串定位運算(也稱模式匹配)在順序串上的實現(xiàn),及在鏈串上的實現(xiàn)子串定位運算的含意：4.3 串運算

34、的實現(xiàn)設有兩個順序串S和T，且： S=“s0s1s2.sn-1” 目標 T=“t0t1t2.tm-1” 模式 匹配有兩種結果：若在S中找到了模式為T的子串（若有多個模式為T的子串，只需找出第一個）時，則返回該子串在S中的位置，這種情況稱為匹配成功；否則稱為匹配失敗。8/22/202279數(shù)據(jù)結構 1. 樸素的匹配算法基本思想：初始時，從S的第一個字符開始將T的第一個字符與其進行比較，若相等，則繼續(xù)逐個比較后續(xù)字符，如匹配成功，則返回子串在S中的位置，否則，將T向右移動一個字符位置，從T的第一個字符開始與S中第二個字符進行比較，并在相等的情況下逐個比較后續(xù)字符，進行第二趟匹配，成功則返回子串在S

35、中的位置，否則，T再向右移動一個字符位置，進行第三趟匹配，如此反復，或匹配成功，或當T右移到無法與S繼續(xù)進行比較時，匹配失敗。 a b a b c a b c a c b a b a b c a c8/22/202280數(shù)據(jù)結構 1. 樸素的匹配算法基本思想：初始時，從S的第一個字符開始將T的第一個字符與其進行比較，若相等，則繼續(xù)逐個比較后續(xù)字符，如匹配成功，則返回子串在S中的位置，否則，將T向右移動一個字符位置，從T的第一個字符開始與S中第二個字符進行比較，并在相等的情況下逐個比較后續(xù)字符，進行第二趟匹配，成功則返回子串在S中的位置，否則，T再向右移動一個字符位置，進行第三趟匹配，如此反復，

36、或匹配成功，或當T右移到無法與S繼續(xù)進行比較時，匹配失敗。 a b a b c a b c a c b a b a b c a c8/22/202281數(shù)據(jù)結構 a b a b c a b c a c b a b 設S=“ababcabcacbab” T=“abcac” a b c a ci=0j=0i=1j=1i=2j=2i指針回溯的位置為：i=i-j+1（i的值為1） 1. 樸素的匹配算法8/22/202282數(shù)據(jù)結構 a b a b c a b c a c b a b 設S=“ababcabcacbab” T=“abcac” a b c a ci=1j=0i指針回溯的位置為：i=i-j+

37、1（i的值為2）8/22/202283數(shù)據(jù)結構設S=“ababcabcacbab” T=“abcac” a b a b c a b c a c b a b a b c a ci=2j=0i=3j=1i=4j=2i=5j=3i=6j=4i指針回溯的位置為：i=i-j+1（i的值為3）8/22/202284數(shù)據(jù)結構 a b a b c a b c a c b a b 設S=“ababcabcacbab” T=“abcac” a b c a ci=3j=0i指針回溯的位置為：i=i-j+1（i的值為4）8/22/202285數(shù)據(jù)結構 a b a b c a b c a c b a b 設S=“aba

38、bcabcacbab” T=“abcac” a b c a ci=4j=0i指針回溯的位置為：i=i-j+1（i的值為5）8/22/202286數(shù)據(jù)結構 a b a b c a b c a c b a b 設S=“ababcabcacbab” T=“abcac” a b c a ci=5j=0i=6j=1i=7j=2i=8j=3i=9j=4i=10j=5返回子串的位置為：i-j+1=6（串的起始位置從1開始算起）8/22/202287數(shù)據(jù)結構 int index(s,t) seqstring *s,*t; int i=0,j=0;while (iscurlen)&(jt curlen) if

39、(s chi=t chj i+;j+; else i=i-j+1;j=0; if (j=t curlen) return (i-j+1) else return (-1); 樸素的模式匹配算法描述如下：8/22/202288數(shù)據(jù)結構5.1 多 維 數(shù) 組一、多維數(shù)組的概念多維數(shù)組可以看成是向量（一維數(shù)組）的擴展1、二維數(shù)組： 可以看成是m個行向量和n個列向量組成的向量邏輯特征： 除邊界外，每個元素aij恰好有兩個直接前趨和兩個直接后繼。ai-1,jai,jai+1,jai,j-1ai,j+1Amn=a11 a12 a1na21 a22 a2n am1 am2 amn8/22/202289數(shù)據(jù)結

40、構2.三維及多維數(shù)組三維數(shù)組Amnp: 可看成有p個二維數(shù)組（m*n)所組成的向量每個元素aijk同屬于三個向量（二維數(shù)組）最多有3個直接前趨和直接后繼（除角、邊、面上的結點）推廣：多維數(shù)組An1n2nm可看成nm個（m-1）維數(shù)組所構成的向量任一元素ai1i2im都屬于m個向量，最多有m個直接前趨和m個直接后繼8/22/202290數(shù)據(jù)結構對于數(shù)組，通常只有兩種操作： (1)取值：給定一組下標，存取相應的數(shù)據(jù)元素； (2)修改：給定一組下標，修改相應數(shù)據(jù)元素中的某一個或幾個數(shù)據(jù)項的值。二、多維數(shù)組的運算說明：對于數(shù)組，通常只進行讀、寫操作，不進行元素的插入和刪除操作。因此，一般采用順序存儲結

41、構表示數(shù)組。8/22/202291數(shù)據(jù)結構1、兩種順序存儲方法： (1) 行優(yōu)先順序(row major order) (c,pascal語言采用） 特點：將數(shù)組元素按行向量排列 (以二維數(shù)組為例）(2) 列優(yōu)先順序(column major order) (fortran語言采用） 特點：將數(shù)組元素按列向量排列 (以二維數(shù)組為例）a11 a12 . a1n a21 a22 a2n am1 am2 amn 第1行 第2行 第m行a11 a21 . am1 a12 a22 am2 a1n a2n amn 第1列 第2列 第n列三、順序存儲方法8/22/202292數(shù)據(jù)結構2、特點 順序存儲的數(shù)組

42、是一個隨機存取結構，即只要知道開始元素的存儲起址、維數(shù)和每一維的上、下界及單個元素所占單元數(shù)，便可將數(shù)組元素的存儲地址表示為其下標的線性函數(shù)。 (以二維數(shù)組為例,且數(shù)組采用行優(yōu)先順序） LOC(aij)=LOC(a11)+(i-1)*n+j-1*dd為單個元素所占單元數(shù)開始元素的存儲起址n為列數(shù)c語言中因數(shù)組下標從0開始，因此上面的式子應改為： LOC(aij)=LOC(a00)+(i*n+j)*d8/22/202293數(shù)據(jù)結構5.2 矩陣的壓縮存儲壓縮存儲: 前提：非零元素呈某種規(guī)律分布或矩陣中有大量零元素 定義：多個值相同的元素只分配一個存儲空間，值為0的 元素不分配空間采用壓縮存儲的矩陣

43、分為兩類：特殊矩陣和稀疏矩陣。 5.2.1 特 殊 矩 陣特殊矩陣：指的是非零元素或零元素的分布有一定規(guī)律的矩陣。對特殊矩陣常采用一維數(shù)組存儲。需解決的問題：如何將二維數(shù)組元素下標轉換成一維數(shù)組元素下標。8/22/202294數(shù)據(jù)結構 1.對稱矩陣 1）定義: 已知n階方陣A，若其元素滿足如下性質(zhì)： aij=aji 0=i,j=j 則 k=i*(i+1)/2+j b: 若 ij 則 k=j*(j+1)/2+i(這是由對稱性質(zhì)決定的） 注意：進行壓縮存儲后，沒有改變原采用二維數(shù)組存儲時能進行隨機訪問的特性。綜合a、b，令I=max(i,j), J=min(i,j)，則k=I*(I+1)/2+Jl

44、oc(aij)=loc(sak)=loc(sa0)+k*d =loc(sa0)+(I*(I+1)/2+J)*da00a10 a11a20 a21 a22 aij a n-1,0 a n-1,1 an-1,2 a n-1,n-18/22/202296數(shù)據(jù)結構2.三角矩陣（方陣） 1）分類：三角矩陣以主對角線劃分，可分為上三角矩陣和下三角矩陣。a00 c c ca10 a11 c a20 a21 c a n-1,0 a n-1,1 an-1,2 a n-1,n-18/22/202297數(shù)據(jù)結構2.三角矩陣（方陣） 2）存儲方法： 只需存儲非常數(shù)三角中的所有元素，另外再加一個存儲單元存儲常數(shù)C。 非

45、常數(shù)三角中的所有元素個數(shù)為n(n+1)/2,外加一個常數(shù),總共有n(n+1)/2+1個元素，可用一維數(shù)組sn*(n+1)/2+1存儲，常數(shù)存于最后一個存儲單元。 1）分類：三角矩陣以主對角線劃分，可分為上三角矩陣和下三角矩陣。8/22/202298數(shù)據(jù)結構上三角矩陣中aij與sk的對應關系：下三角矩陣中aij與sk的對應關系： i*(2n-i+1)/2+j-i ij i*(i+1)/2+j i=j k= n*(n+1)/2 ija00 a01 a0,n-1 c a11 a1,n-1 aii aij c c an-1,n-13)存儲地址的計算i*n-(i-1) *i /28/22/202299數(shù)

46、據(jù)結構3.對角矩陣特點：所有的非零元素都集中在以對角線為中心的帶狀區(qū)域中。帶狀區(qū)域外的所有元素均為零。以三對角矩陣為例（p75)三對角矩陣中所有非零元素為3*n-2,可用一維數(shù)組s3*n-2存儲.再次強調(diào)：特殊矩陣的壓縮存儲沒有改變原采用二維數(shù)組存儲時所具有的隨機存取特性。 8/22/2022100數(shù)據(jù)結構5.2.2 稀 疏 矩 陣稀疏矩陣的壓縮存儲通常有兩種方式：三元組表和十字鏈表。稀疏矩陣：非零元素的個數(shù)遠遠少于矩陣元素的總數(shù)的矩陣（sm=3; a-n=5; a-t=4; a- data16 8/22/2022105數(shù)據(jù)結構傳統(tǒng)轉置方法介紹基本思想：由于A的列是B的行，因此按a-data的

47、列序轉置，所得到的轉置矩陣B的三元組表b-data必定是按行優(yōu)先順序存放的。為了找到A的每一列中的所有非零元素，需要對三元組表a-data從第一行起掃描一遍，由于a-data是按A的行優(yōu)先順序存放的，因此得到的恰是b-data應有的順序。時間復雜度：O(n*t)O(m*n) 0 1 2 1 3 1 2 0 -3 2 3 2 i j vA的三元組表 i j v 0 2 -3 1 0 2 3 1 1 3 2 2 B 的三元組表轉置后8/22/2022106數(shù)據(jù)結構 3、十字鏈表1) 十字鏈表中結點的結構： i j v/next cptr rptr存儲行號存儲列號存儲元素值或指向下一個表頭結點列指針

48、域，指向本列下一個非零元素行指針域，指向本行下一個非零元素4)三元組表的優(yōu)點：結構簡單，易于實現(xiàn)，存儲密度高。 缺點：不具有隨機存儲特性；矩陣中非零元素發(fā)生變化時，將會引起三元組表中大量元素的移動。8/22/2022107數(shù)據(jù)結構十字鏈表h0 0 0 0 0 0 0 0 0 0 1 2 2 2 4 1 3 1 -3 3 4 2 0 0 0 0 0 0 3 5 H1H1H4H2H3H2H5H3 A= 0 2 0 0 0 0 0 0 1 0 -3 0 0 2 0 i j v/next cptr rptr8/22/2022108數(shù)據(jù)結構2) 十字鏈表存儲結構描述： typedef struct ln

49、ode int i,j; struct lnode *cptr,*rptr; union struct lnode *next; datatype v ; uval; link; 3)建立十字鏈表 i j v/next cptr rptr8/22/2022109數(shù)據(jù)結構建立十字鏈表的算法分為兩步： 1.建立表頭結點的循環(huán)鏈表 2.依次讀入非零元素的三元組，每讀入一個三元組，生成一個表結點，并將其插入相應行、列鏈表中的正確位置上。8/22/2022110數(shù)據(jù)結構5.3 廣義表的概念廣義表(Lists)是n（n=0)個元素a1,a2,an的有限序列，其中ai或者是原子或者是一個廣義表，通常記為LS

50、=(a1,a2,an)1、定義：8/22/2022111數(shù)據(jù)結構補充說明：對于LS=(a1,a2,an)LS:廣義表的名字n: 廣義表的長度。E=(a,E )如果ai是廣義表， 則稱它為LS的子表書寫時，用大寫字母表示廣義表，小寫字母表示原子若LS非空(n=1)，則a1是LS的表頭，（a2,a3,an)構成的表稱為LS的表尾表是遞歸定義的，一個表的深度定義為表展開后所含括號的層數(shù).D=(A,B,C )如果規(guī)定任何表都是有名字的，為了即表明每個表的名字，又說明它的組成，則可以在每個表的前面冠以該表的名稱。 D (A( ),B ( b,c,d), C (a, B(b,c,d) ) )； 8/22/

51、2022112數(shù)據(jù)結構2、廣義表的表示方法圖示法：用分支結點表示廣義表，非分支結點表示原子。特殊的，空表對應的也是非分支結點。A=( )AB=( b,c,d)BbcdC=(a,(b,c,d) )bcdBCaD=(A,B,C )DABbcdCaE=(a,E )Ea純表：樹對應的廣義表，限制了成分的共享與遞歸 A,B,C再入表：允許結點間共享的表 D 遞歸表：允許遞歸的表 E 8/22/2022113數(shù)據(jù)結構3、廣義表的兩個特殊的運算取表頭head(LS): 任何一個非空廣義表的表頭是表中第一個元素。取表尾tail(LS)：據(jù)表尾定義，必定是子表。例: head(B)=btail(B)=(c,d)

52、head(D)=Atail(D)=（B,C)head( )=( )tail( )=( )線性表純表 再入表 遞歸表所以，廣義表不僅是線性表的推廣，還是樹的推廣8/22/2022114數(shù)據(jù)結構5.3 廣義表的存儲p831、單鏈表示法（模仿單鏈表結構）2、雙鏈表示法（類似于第六章的二叉鏈表）8/22/2022115數(shù)據(jù)結構第六章 樹 樹形結構是一種重要的非線性結構，在我們的客觀世界和現(xiàn)實生活中大量存在。 樹形結構：結點之間有分支，并且具有層次關系的結構8/22/2022116數(shù)據(jù)結構6.1 樹的概念1、樹的定義：樹(Tree)是n(n0)個結點的有限集合T，它滿足如下條件： (1) 有且僅有一個稱

53、為根(Root)的結點。 (2) 其余結點可分為m(m=0)個互不相交的有限集合,T1,T2,Tm,其中每個集合又是一棵樹，并稱其為根的子樹（Subtree） 。這是一個遞歸定義。 有時n=0也稱為空樹。ABCDEFG集合1集合2集合3一、樹的基本概念8/22/2022117數(shù)據(jù)結構2、樹的表示方法1）樹形圖法2）嵌套集合法3）廣義表形式4）凹入表示法(A(B),C(E,F),D(G)ABCDEFGABCEFDGABDGEFC8/22/2022118數(shù)據(jù)結構1）結點的度(Degree)：為該結點的子樹的個數(shù)。2）樹的度：為該樹中結點的最大度數(shù)。3）終端結點(葉子)：度為零的結點。4）非終端結點

54、(分支結點)：度不為零的結點。5）內(nèi)部結點：除根結點之外的分支結點。ACDEFGB3、 樹結構的基本術語8/22/2022119數(shù)據(jù)結構6）孩子(child)：結點的子樹之根 雙親（parent):該結點稱為孩子的雙親 兄弟(sibling):同一雙親的孩子 堂兄弟（cousin):雙親不同但其雙親處于同一層的結點7）路徑(Path)：若樹中存在一個結點序列k1,k2,kj,使得ki是ki+1的雙親(1=i=0)棵互不相交的樹的集合稱為森林。關系：樹森林刪去一個樹根加上一個樹根ACDEFGB8/22/2022122數(shù)據(jù)結構6.2 二 叉 樹6.2.1 二叉樹的概念一、二叉樹的定義： 二叉樹(B

55、inary Tree)是n(n=0)個結點的有限集，它或者是空集(n=0)或者由一個根結點和兩棵互不相交的，分別稱為根的左子樹和右子樹的二叉樹組成。 可以看出，二叉樹的定義和樹的定義一樣，均為遞歸定義。8/22/2022123數(shù)據(jù)結構二、二叉樹的五種基本形態(tài)：空二叉樹只有一個根結點的二叉樹右子樹為空的二叉樹左子樹為空的二叉樹左、右子樹均非空的二叉樹注意：二叉樹中子樹是有左右之分的，即使只有一棵子樹，或為左子樹，或為右子樹，這一點與度為2的有序樹不同。這不是二叉樹這是二叉樹8/22/2022124數(shù)據(jù)結構6.2.2 二叉樹的性質(zhì)性質(zhì)1：二叉樹第i層上的結點數(shù)目最多為2i-1 (i=1)性質(zhì)2：深

56、度為k的二叉樹至多有2k-1個結點(k=1)性質(zhì)3：任意二叉樹中，若葉結點的個數(shù)為n0,度為2的結點數(shù)為n2，則n0=n2+1。8/22/2022125數(shù)據(jù)結構兩種特殊形態(tài)的二叉樹：滿二叉樹和完全二叉樹 深度為k且有2 k-1個結點的二叉樹稱為滿二叉樹。 若一棵二叉樹至多只有最下面的兩層上結點的度數(shù)可以小于2，并且最下一層上的結點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。滿二叉樹1234567非完全二叉樹123456完全二叉樹234518/22/2022126數(shù)據(jù)結構兩種特殊形態(tài)的二叉樹：滿二叉樹和完全二叉樹 深度為k且有2 k-1個結點的二叉樹稱為滿二叉樹。 對滿二叉樹的結點

57、進行編號，約定編號從根結點起，自上而下，自左至 右。 深度為k的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應，則稱之為完全二叉樹。滿二叉樹1234567非完全二叉樹123456完全二叉樹234518/22/2022127數(shù)據(jù)結構根據(jù)定義:(1)滿二叉樹是完全二叉樹,反之不成立; (2)對于完全二叉樹,若某結點無左孩子,則必無右孩子,該結點為葉結點;性質(zhì)4：具有n個結點的完全二叉樹的深度為 log2n +1( log2(n+1) )8/22/2022128數(shù)據(jù)結構性質(zhì)5：如果對一棵有n個結點的完全二叉樹的結點按層次編號(即自上而下，自左至右)，則對

58、任一結點i(1=i1,則其雙親是編號為 i/2 的結點。 (2) 如果2*in,則結點i無左孩子；否則其左孩子是編號為2*i的結點。 (3) 如果2*i+1n,則結點i無右孩子；否則其右孩子是編號為2*i+1的結點。 (4)若i為奇數(shù)且不為1,則結點i的左兄弟的編號是i-1;否則,結點i無左兄弟。 (5)若 i為偶數(shù)且小于n,則結點i的右兄弟的編號是i+1;否則,結點i無右兄弟。234518/22/2022129數(shù)據(jù)結構6.2.3 二叉樹的存儲1. 順序存儲結構1）對于完全二叉樹可以采用順序存儲結構(即一維數(shù)組)進行存儲，編號為i的結點存放在第i個數(shù)組元素所分配的存儲單元中，完全二叉樹結點之間

59、的邏輯關系通過數(shù)組元素的下標體現(xiàn)。完全二叉樹abcde非完全二叉樹abcdef 0 1 2 3 4 5 a b c d e 下標元素 0 1 2 3 4 5 6 7 a b c * d e f 下標元素“虛結點”占據(jù)的空間補設的“虛結點”8/22/2022130數(shù)據(jù)結構2）對于非完全二叉樹，通過補設一些“虛結點”，使得二叉樹的結點的編號與完全二叉樹相同，再進行順序存儲。每個“虛結點”都將占據(jù)一個數(shù)組元素存儲單元。結論：非完全二叉樹采用順序存儲結構會造成存儲空間的浪費。8/22/2022131數(shù)據(jù)結構二叉樹除了可以采用順序存儲結構實現(xiàn)存儲外,還可以采用鏈式存儲結構進行存儲,與采用順序存儲結構相比

60、,采用鏈式存儲結構實現(xiàn)二叉樹的存儲顯得更自然.1）鏈式存儲結構中結點的結構: lchild data rchild指向左孩子的指針域指向右孩子的指針域存放數(shù)據(jù) 2、鏈式存儲結構8/22/2022132數(shù)據(jù)結構2）結點的存儲描述:typedef struct nodedatatype data; struct node *lchild,*rchild; bitree;bitree *root;所有類型為node的結點，再加上一個指向根結點的頭指針root，就構成了二叉樹的存儲結構，稱為二叉鏈表。 lchild data rchild指向左孩子的指針域指向右孩子的指針域存放數(shù)據(jù)8/22/20221