數(shù)據結構第7講

1、數(shù)據結構數(shù)據結構第第3章章 復習：復習： 棧：是后進先出的線性表。棧：是后進先出的線性表。 棧頂指針：棧頂指針：toptop 棧底指針：棧底指針：basebase 棧采用順序存儲結構棧采用順序存儲結構-順序棧。順序棧。低低高高地址地址topbase空?？諚Ｈ霔Ｈ霔３鰲３鰲1a3topa2a4toptoptopa4a4top數(shù)據結構數(shù)據結構第第3章章 3.4 3.4隊列隊列 1. 1. 抽象數(shù)據類型隊列的定義抽象數(shù)據類型隊列的定義 隊列隊列是一種先進先出的線性表。是一種先進先出的線性表。 它只允許在表的一端進行插入，而在另一端刪它只允許在表的一端進行插入，而在另一端刪除元素。在隊列中，允許插入

2、的一端叫除元素。在隊列中，允許插入的一端叫隊尾隊尾，往隊往隊尾插入一個元素的操作叫尾插入一個元素的操作叫入隊入隊允許刪除的一端則稱允許刪除的一端則稱為為隊頭，隊頭，在隊頭端刪除一個元素的操作叫在隊頭端刪除一個元素的操作叫出隊出隊。 排隊排隊打印隊列打印隊列 想一想想一想：生活中有哪些例子類似于隊列？：生活中有哪些例子類似于隊列？ 計算機中有哪些問題應用隊列？計算機中有哪些問題應用隊列？ a1 a2 a3 a4 .an 隊頭隊頭隊尾隊尾出隊出隊入隊入隊數(shù)據結構數(shù)據結構第第3章章 隊列的抽象數(shù)據類型的定義隊列的抽象數(shù)據類型的定義 ：ADTQueue 數(shù)據對象：數(shù)據對象：Dai|ai ElemSet

3、,i=1,2,.,n, n0 數(shù)據關系：數(shù)據關系： R1 | ai-1, aiD, i=2,.,n 約定約定a1端為隊列頭端為隊列頭， an端為隊列尾。端為隊列尾。 基本操作：基本操作： InitQueue(&Q) DestroyQueue(&Q)QueueLength(Q) QueueEmpty(Q)GetHead(Q, &e) ClearQueue(&Q) EnQueue(&Q, e) DeQueue(&Q , &e) QueueTravers(Q, visit() 數(shù)據結構數(shù)據結構第第3章章 2.2.隊列的順序表示與實現(xiàn)隊列的順序表

4、示與實現(xiàn)-循環(huán)隊列循環(huán)隊列 隊列有兩種存儲表示：隊列有兩種存儲表示：鏈隊列鏈隊列和和循環(huán)隊列循環(huán)隊列。 在隊列的順序存儲結構中，除了用一組地址連在隊列的順序存儲結構中，除了用一組地址連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素之續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素之外，尚需附設兩個指針外，尚需附設兩個指針 frontfront和和 rearrear分別指示隊列分別指示隊列頭元素和隊列尾元素的位置。頭元素和隊列尾元素的位置。 約定：約定：初始化建空隊列時，令初始化建空隊列時，令front=rear=0front=rear=0，每當插入新的隊列尾元素時，每當插入新的隊列尾元素時，“尾指針增尾

5、指針增1 1”，每當，每當刪除隊列頭元素時，刪除隊列頭元素時，“頭指針增頭指針增1 1”。因此，在非空。因此，在非空隊列中，頭指針始終指向隊列的頭元素，而尾指針隊列中，頭指針始終指向隊列的頭元素，而尾指針始終指向隊列尾元素的下一個位置。始終指向隊列尾元素的下一個位置。數(shù)據結構數(shù)據結構第第3章章 假設：隊列分配的最大空間為假設：隊列分配的最大空間為6 6。012345Q.frontQ.rearJ1012345Q.frontQ.rear空隊列空隊列Q.rearJ1J2J3012345J3012345Q.frontQ.rearJ3J4J5J6012345Q.frontQ.rear假溢出假溢出為解決假

6、溢出為解決假溢出現(xiàn)象，可采用現(xiàn)象，可采用循環(huán)隊列循環(huán)隊列Q.rearJ7Q.rearJ8Q.rear數(shù)據結構數(shù)據結構第第3章章注意：注意：循環(huán)隊列，隊空時，循環(huán)隊列，隊空時，front=rearfront=rear，隊滿時，隊滿時，front=rearfront=rear，因此只憑因此只憑front=rear front=rear 是無法判別隊列是是無法判別隊列是“空空”還是還是“滿滿”。 可以可以有兩種處理方法有兩種處理方法：其一是另設一個：其一是另設一個標志位以區(qū)別隊列是標志位以區(qū)別隊列是“空空”還是還是“滿滿”；其；其二是少用一個元素的空間，約定以二是少用一個元素的空間，約定以“隊列頭隊

7、列頭指針在隊列尾指針的下一位置上指針在隊列尾指針的下一位置上”作為隊列作為隊列呈呈“滿滿”狀態(tài)標志。狀態(tài)標志。數(shù)據結構數(shù)據結構第第3章章 #define MAXQSIZE 100 /最大隊列長度最大隊列長度 typedef struct QElemType *base; / 動態(tài)分配存儲空間動態(tài)分配存儲空間 int front; / 頭指針，若隊列不空，頭指針，若隊列不空， / 指向隊列頭元素指向隊列頭元素 int rear; / 尾指針，若隊列不空，指向尾指針，若隊列不空，指向 / 隊列尾元素隊列尾元素 的下一個位置的下一個位置 SqQueue; 數(shù)據結構數(shù)據結構第第3章章 Status I

8、nitQueue (SqQueue &Q) / 構造一個空隊列構造一個空隊列Q Q.base = (ElemType *) malloc (MAXQSIZE *sizeof (ElemType); if (!Q.base) exit (OVERFLOW); / 存儲分配失敗存儲分配失敗 Q.front = Q.rear = 0; return OK; 數(shù)據結構數(shù)據結構第第3章章 Status EnQueue(SqQueue &Q, ElemType e) / 插入元素插入元素e為為Q的新的隊尾元素的新的隊尾元素 if (Q.rear+1) % MAXQSIZE = Q.fron

9、t) return ERROR; /隊列滿隊列滿 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK;數(shù)據結構數(shù)據結構第第3章章 Status DeQueue (SqQueue &Q, ElemType &e) / 若隊列不空，則刪除若隊列不空，則刪除Q的隊頭元素，用的隊頭元素，用e返回其值返回其值 if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK; Status

10、GetHead (SqQueue Q, ElemType &e) / 若隊列不空，則用若隊列不空，則用e返回返回Q的隊頭元素。的隊頭元素。 if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; return OK; 數(shù)據結構數(shù)據結構第第3章章 第第4 4章章 串串一、串的類型定義一、串的類型定義1 1、串的基本概念、串的基本概念串串是由零個或多個字符組成的有限序列。串中字符是由零個或多個字符組成的有限序列。串中字符的數(shù)目的數(shù)目n n稱為稱為串的長度串的長度。零個字符的串稱為。零個字符的串稱為空串空串。 串中任意個連續(xù)的字符組成的子

11、序列稱為串中任意個連續(xù)的字符組成的子序列稱為子串子串；包含子串的串相應地稱為包含子串的串相應地稱為主串主串。字符在序列中的序號為該字符在串中的字符在序列中的序號為該字符在串中的位置位置。何為兩串相等？何為兩串相等？只有兩串的長度相同，并且各個對應位置的字符都只有兩串的長度相同，并且各個對應位置的字符都相等時，兩串相等。相等時，兩串相等。數(shù)據結構數(shù)據結構第第3章章空串與空格串的區(qū)別？空串與空格串的區(qū)別？注意：串與線性表的區(qū)別？注意：串與線性表的區(qū)別？串的邏輯結構與線性表極為相似，區(qū)別在于：串的邏輯結構與線性表極為相似，區(qū)別在于：（1 1）串的數(shù)據對象僅限于是字符集，而線性表不限；）串的數(shù)據對象僅

12、限于是字符集，而線性表不限；（2 2）串的基本操作中通常是以）串的基本操作中通常是以“串的整體串的整體”為操作對象，如為操作對象，如在串中查找子串、求子串、在主串中插入或刪除一個子串在串中查找子串、求子串、在主串中插入或刪除一個子串；而線性表基本操作中，大多以而線性表基本操作中，大多以“單個元素單個元素”作為操作對象作為操作對象，如在線性表中查找某個元素、在某個位置插入或刪除一，如在線性表中查找某個元素、在某個位置插入或刪除一個元素等。個元素等。 空串空串,空串的長度為空串的長度為0 空格串，空格串的長度為空格的個數(shù)空格串，空格串的長度為空格的個數(shù)數(shù)據結構數(shù)據結構第第3章章 2、串的抽象數(shù)據類

13、型串的抽象數(shù)據類型ADT String 數(shù)據對象：數(shù)據對象：D ai |aiCharacterSet, i=1,2,.,n, n0 數(shù)據關系：數(shù)據關系：R1 | ai-1, ai D, i=2,.,n 基本操作基本操作：StrAssign (&T, chars)StrLength(S) StrCompare (S, T) Concat (&T, S1, S2) SubString (&Sub, S, pos, len) 這五個操這五個操作構成串作構成串類型的最類型的最小操作子小操作子集。集。這些操作這些操作不可能利不可能利用其它串用其它串操作來實操作來實現(xiàn)?，F(xiàn)。數(shù)據結構

14、數(shù)據結構第第3章章 StrCopy (&T, S) StrEmpty (S) DestroyString(&S) ClearString (&S) Index (S, T, pos) Replace (&S, T, V) StrInsert (&S, pos, T) StrDelete (&S, pos, len) ADT String其中：其中：StrCompare(S,T)初始條件：串初始條件：串 S 和和 T 存在。存在。操作結果：若操作結果：若S T，則返回值則返回值 0； 若若S T，則返回值則返回值 0； 若若S T，則返回值則返回值

15、 0。 例如：例如：StrCompare( data , state ) ？ StrCompare( cat , case ) ？ 0next=p-next-next; p-next=p-next-next; B B、p-next=p-next;p-next=p-next;C C、p=p-next-next; p=p-next-next; D D、p=p-next; p-next=p-next-next;p=p-next; p-next=p-next-next;CA+BBA數(shù)據結構數(shù)據結構第第3章章7. 7. 設棧設棧S和隊列和隊列Q的初始狀態(tài)為空，元素的初始狀態(tài)為空，元素e1、e2、e3、e

16、4、e5、e6依次通過棧依次通過棧S，一個元素，一個元素出棧后即進入隊列出棧后即進入隊列Q，若，若6個元素出隊的順序是個元素出隊的順序是e2、e4、e3、e6、e5、e1，則棧，則棧S的容量至少的容量至少應該是（應該是（ ）。）。 A 6 B 4 C 3 D 2CAB8. 8. 用單鏈表表示的隊列長度為用單鏈表表示的隊列長度為n，若只設頭指，若只設頭指針，則出隊和入隊的時間復雜度分別是（針，則出隊和入隊的時間復雜度分別是（ ）和（和（ ）A (1) B (n) C (n2) D (n3) 數(shù)據結構數(shù)據結構第第3章章 （二）填空題（二）填空題1. 在線性結構中，第一個結點在線性結構中，第一個結點

17、_前驅結點，其余每個前驅結點，其余每個結點有且只有結點有且只有_個前驅結點；最后一個結點個前驅結點；最后一個結點_后續(xù)后續(xù)結點，其余每個結點有且只有結點，其余每個結點有且只有_個后續(xù)結點。個后續(xù)結點。2. 設設n為整數(shù)，分析下列程序中用為整數(shù)，分析下列程序中用#標明的語句的語句頻度及標明的語句的語句頻度及時間復雜度時間復雜度_。 for (i=1; in; i+ ) for (j=1; jn; j+) cij=0; for ( k=1; knext=_next=_；(2)p(2)pnext=snext=s； (3)t=p(3)t=pdatadata； (4)p(4)pdata=_data=_；

18、 (5)s(5)sdata=_data=_；5.5.對于一個具有對于一個具有n n個結點的單鏈表，在已知個結點的單鏈表，在已知p p所指結點后插入所指結點后插入一個新結點的時間復雜度是一個新結點的時間復雜度是_；在給定值為；在給定值為x x的結的結點后插入一個新結點的時間復雜度是點后插入一個新結點的時間復雜度是_。ni+lP-nexts-datatO(1)O(n)數(shù)據結構數(shù)據結構第第3章章 6. 6.需要分配較大空間，插入和刪除不需要移動元需要分配較大空間，插入和刪除不需要移動元 素的線性表，其存儲結構是：素的線性表，其存儲結構是： 。 7. 7.如果最常用的操作是取第如果最常用的操作是取第i

19、個元素及其前驅，個元素及其前驅， 則采用則采用 存儲方式最節(jié)省時間。存儲方式最節(jié)省時間。 8 8. .在一個單鏈表中刪除在一個單鏈表中刪除p所指結點時，應執(zhí)行以所指結點時，應執(zhí)行以 下操作：下操作： q=p-next; p-data=p-next-data; p-next=_; free(q);靜態(tài)鏈表靜態(tài)鏈表順序表順序表q-next數(shù)據結構數(shù)據結構第第3章章 （三）簡答（三）簡答 1. 1. 描述單鏈表中以下二個概念的區(qū)別：描述單鏈表中以下二個概念的區(qū)別： 頭指針，頭結點頭指針，頭結點 頭指針：在單鏈表中是指向起始結點的指針。頭指針：在單鏈表中是指向起始結點的指針。頭結點：在單鏈表中，我們將

20、在第一個結點頭結點：在單鏈表中，我們將在第一個結點 前附設的一個結點叫頭結點。前附設的一個結點叫頭結點。數(shù)據結構數(shù)據結構第第3章章 2. 2. 在操作序列在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，棧頂之后，棧頂元素和棧底元素分別是什么？（元素和棧底元素分別是什么？（push(k)表示整表示整數(shù)數(shù)k入棧，入棧，pop表示棧頂元素出棧。）表示棧頂元素出棧。） 棧頂元素為棧頂元素為6，棧底元素為，棧底元素為1。數(shù)據結構數(shù)據結構第第3章章 算法設計題算法設計題1 1. .有一個單鏈表有一個單鏈表L（至少有一個結點），其頭至少有一個結點

21、），其頭結點指針為結點指針為head，編寫一個函數(shù)將編寫一個函數(shù)將L逆置，即逆置，即最后一個結點變成第一個結點，原來倒數(shù)第二最后一個結點變成第一個結點，原來倒數(shù)第二個結點變成第二個結點，如此等等。個結點變成第二個結點，如此等等。數(shù)據結構數(shù)據結構第第3章章 本題采用的算法是：從頭到尾掃描單鏈本題采用的算法是：從頭到尾掃描單鏈表表L L，將第一個結點的將第一個結點的nextnext域置為域置為NULLNULL，將將第二個結點的第二個結點的nextnext域指向第一個結點，將第域指向第一個結點，將第三個結點的三個結點的nextnext域指向第二個結點，如此等域指向第二個結點，如此等等，直到最后一個結點，便用等，直到最后一個結點，便用headhead指向它，指向它，這樣達到了本題的要求。這樣達到了本題的要求。實現(xiàn)本題功能的函數(shù)如下：實現(xiàn)本題功能的函數(shù)如下：typedef struct LNodetypedef struct LNode int data; int data; Struct LNode Struct LNode * *next;next; LNode, LNode, * *LinkListLinkList數(shù)據結構數(shù)據結構第第3章章 void invert ( LinkList &head) LNode *p, *q, *r; /*q指向正處理