資源簡介

(共29張PPT)
線性數據的組織和存儲
線性表（Linear List）
是最簡單且最常用的一種數據結構，是由若干個具有相同屬性的數據元素組成的有限序列。比如，英文字母表（A，B，C，…，Z）就是一個長度為26的線性表，表中的每一個英文字母為一個數據元素。
線性表具有如下的結構特點：
1．均勻性
雖然不同數據表的數據元素可以是各種各樣的，但同一線性表的各數據元素必定具有相同的數據類型和長度。
2．有序性
各數據元素在線性表中的位置只取決于它們的序號，數據元素之間的相對位置是線性的，即存在唯一的“第一個”和“最后一個”數據元素，除了第一個和最后一個，其他元素前面均只有一個數據元素（直接前趨），后面也只有一個數據元素（直接后繼）。
對于線性表，常見的基本運算有：
（1）置空表setnull(L)，這是一個過程，其結果是將線性表L置為空表。
（2）求長度length(L)，這是一個函數，返回值為線性表L的長度。
（3）取得表中第i個元素get(L,i)，這是一個函數，當1≤i≤length(L)時，返回第i個數據元素。
（4）取直接前趨prior(L,ai)，這是一個函數，當2≤i≤length(L)時，返回ai的直接前趨ai-1。
（5）取直接后繼next(L,ai)，這是一個函數，當1≤i≤length(L)-1時，返回ai的直接后繼ai+1。
（6）根據特定值查找線性表locate(L,x)，這是一個函數，若線性表中存在值為x的數據元素ai時，則返回i值，即ai在線性表中的序號；若存在多個值為x的數據元素ai時，則i為其序號最小的值；若不存在值為x的數據元素，則返回值零。
（7）插入數據元素insert(L,x,i)，這是一個過程，是將新數據元素x插入到數據元素ai之前，因此當1≤i≤length(L)+1時有意義，運算的結果使長度為n的線性表變為長度為n+1的線性表。
（8）刪除操作delete(L,i)，這是一個過程，當1≤i≤length(L)時，將線性表L中第i個數據元素刪除，使長度為n的線性表變為長度為n-1的線性表。
3.2　用字符串存儲數據
3 . 2 . 1 　字符串及其存儲
字符串（String）一般簡稱為串，可以將它看作一種特殊的線性表，它的每個數據元素僅由一個字符組成。與一般線性表相比，字符串有以下特點：
（1）字符串的數據元素的類型限定為字符型。
（2）字符串操作的對象，多數情況下是字符串整體或其中一部分，當然也可以是單個的數據元素。
隨著計算機技術的發展，字符串成為非數值計算問題中的主要操作對象，如信息檢索、文本編輯、問答系統、音樂分析程序等。
1．字符串的描述
字符串是由零個或有限個字符構成的有序序列。一般記作：
s="c0c1c2…cn-1" (n≥0)
其中：s為串名，用雙引號引起來的字符序列稱為串值；ci（0≤i≤n-1）可以是字母、數字或其他字符。下標i表示字符ci在串中的位置。雙引號是串值的定界符，不是串的一部分。
字符串中字符的個數n稱為串的長度。長度為0的字符串稱為空串，此時串中沒有任何字符。
注意：空格在字符串中也算一個字符；長度為1的字符串與單個字符的意義及可執行的操作是不同的。
例如，字符串“20180105”，長度為8，其中字符“8”的位置是3。
為了支持字符串的處理，在高級語言中引入了串的數據類型。并且，字符串變量與其他變量（如整型、實型等）一樣，可以進行各種運算，字符串運算的基本函數和過程也可以同時建立。在C++語言中，字符串被定義為結構數據類型，可以直接用string來定義字符串變量：
string s;
一個字符串中任意個連續的字符組成的子序列稱為該串的子串，包含這個子串的字符串就稱為主串。一個子串在主串中的位置是用這個子串的第一個字符在主串中的位置來表示的。
例如，s1="20180105"，s2="01"，則稱s2是s1的子串，子串s2在s1中的位置是1。
2．字符串的存儲結構
字符串是一種特殊的線性表。因此，字符串的存儲結構也有兩種：靜態的順序存儲結構，動態的鏈式存儲結構或堆存儲結構。
（1）串的順序存儲結構。
串的順序存儲結構與一維數組的類似，用一組地址連續的存儲單元存儲串值的符序列，如圖3-6所示。字符串的字符依次存放在這些存儲單元中。因此，串可以用數組表示。
此外，存儲串的連續的存儲單元一般要求先定義好最大長度，這也使得串的操作受限。兩個字符串連接的結果，很可能超出這個最大長度。
（2）串的動態存儲結構
用順序存儲結構來存儲字符串，因為其規模在定義的時候就已定下，容易造成存儲空間的浪費；同時，線性表的插入和刪除操作效率很低。因此，有些時候也采用動態存儲方式。動態存儲方式包括鏈式存儲結構和堆存儲結構。
3 . 2 . 2 　字符串的基本操作
字符串的基本操作有賦值、連接、求串長、求子串、插入子串、刪除子串、查找子串、判斷兩個串是否相等。目前，字符串在很多程序設計語言中被定義為結構數據類型，有關字符串的操作也被設計成系統函數，可以直接引用。
以C++語言為例，通常有以下幾種基本操作：
（1）字符串賦值：直接賦值s="20180105"。
（2）字符串連接s1.append(s2)：把字符串s2接在s1的后面，返回連接后的新串。
（3）求字符串長度s.length( )：返回字符串s中當前所含字符個數。
（4）求子串操作s1.substr(pos1,len1)：從字符串s1中復制指定位置pos1開始、指定長度len1的子串。
（5）插入操作s1.insert(pos,s2)：將一個子串s2插入到s1的指定位置pos，返回這個新的主串。
（6）刪除操作s.erase(pos,len)：刪除位置pos開始的長度為len的一個子串。
3 . 2 . 2 　字符串的基本操作
字符串的基本操作有賦值、連接、求串長、求子串、插入子串、刪除子串、查找子串、判斷兩個串是否相等。目前，字符串在很多程序設計語言中被定義為結構數據類型，有關字符串的操作也被設計成系統函數，可以直接引用。
（7）查找子串操作s1.find(s2)：找出主串s1中是否包含子串s2，包含則返回該子串位
置，不包含則返回空值。
（8）判斷兩個字符串是否相等s1.compare(s2)：比較s1、s2兩個字符串是否相等，相等返回true，否則返回false。字符串相等，是指兩個字符串長度相等且對應位置的元素一一相等。例如，字符串s1="693450213"，s2="693450213"，s3="693550213"，其中串s2與s1相等，s3與s1不等。
顧客若要求查詢編號為“693450213”的商品銷量，則需將此字符串與銷售記錄中的商品編號逐一比較，找到該字符串第一次出現的記錄。
3.3　用隊列組織先進先出數據（先進先出）
隊列（Queue）是一種特殊的線性表，它只允許在表的一端進行插入，在表的另一端進行刪除。在隊列中，可以插入的一端稱為隊尾，可以刪除的一端稱為隊頭。把一個數據元素插入隊列中的操作叫作進隊，從隊列中刪除一個數據元素的操作叫作出隊。隊列中沒有元素時，稱為空隊列。
在日常生活中，售票窗外或服務臺前，顧客按到達的先后次序排成一隊。排在隊頭的首先得到服務，然后離隊。所有顧客一律平等，嚴格遵守秩序，不允許插隊現象。也就是說，隊列中總是排在最前面的對象首先離隊。因此，隊列符合這個規律：先放入隊列中的數據元素首先取出。故隊列又被稱為先進先出（FIFO：First In First Out）線性表。
3 . 3 . 2 　隊列的基本操作
3 . 3 . 3 　隊列的實現
1．順序隊列
在隊列的程序定義中，可以利用數組這種具有一定容量的順序存儲結構來存儲隊列元素，并用隊頭標志front指示即將出隊的元素的位置，用隊尾標志rear指示即將入隊的元素的位置，它們的初始值在隊列初始化時均為0。
同時我們約定：當入隊或出隊時，隊尾標志rear或隊頭標志front只能往后移動一位，且其最大值為隊列的最大長度maxsize（數組的量），我們把這種隊列稱為順序隊列。假設已定義隊列q，隊頭front，隊尾rear，數組容量為6，其順序隊列存儲方式如圖3-12所示。
基于以上約定，在編程實現隊列操作時，隊頭標志和隊尾標志會有幾種不同的變化，
還可以利用隊頭標志和隊尾標志來求得隊列的當前長度：
（1）初始化隊列：front = rear = 0
（2）入隊操作：rear = rear+1
（3）出隊操作：front = front+1
（4）隊空判斷：front == rear
（5）隊滿判斷：rear == maxsize
（6）求隊列長度：rear - front
2．循環隊列
當我們對順序隊列不斷執行入隊操作時，隊列就有可能出現溢出現象。如已定義順序隊列q，隊頭front，隊尾rear，數組容量為6，當有元素入隊時，有下面兩種情況：
（1）真溢出。
當隊列中的實際元素個數達到隊列最大長度maxsize時，隊列滿，這時做入隊操作將產生空間溢出的現象，如圖3-13所示。真溢出是一種出錯狀態，應設法避免。
循環隊列
為充分利用隊列的存儲空間，克服“假溢出”現象，可以將數組存儲區想象為一個首尾相接的圓環，并稱存儲在其中的隊列為循環隊列。同時，為了區別隊滿和隊空，我們約定：當數組中只剩下一個元素為空時，即若隊尾標志繼續后移一位將與隊頭標志重疊，就判為隊滿，此時不能再做入隊操作。
循環隊列
為充分利用隊列的存儲空間，克服“假溢出”現象，可以將數組存儲區想象為一個首尾相接的圓環，并稱存儲在其中的隊列為循環隊列。同時，為了區別隊滿和隊空，我們約定：當數組中只剩下一個元素為空時，即若隊尾標志繼續后移一位將與隊頭標志重疊，就判為隊滿，此時不能再做入隊操作。
不難發現，循環隊列中的元素被刪除后，其原來的空間仍然可以使用，因而循環隊列能實現對空間更大限度的利用。
3.4　用棧組織后進先出數據（后進先出）
隊列對應了生活中的排隊現象，但還有另一種現象，如對一疊碗的取放：每次把洗凈的碗放好時總是放在這疊碗的最上面，而每次取用的時候也總是取最上面的。在這種現象中，事物的進出順序都有共同的特征，那就是后進先出。
棧（Stack）是限制只能在一端進行插入和刪除的特殊線性表。棧中能進行插入和刪除的一端稱為棧頂（Top），而另一固定端稱為棧底（Bottom）。把一個數據元素放入棧中的操作叫作進棧或壓棧（Push），從棧中取出一個數據元素的操作稱為出棧或彈出Pop）。棧中沒有元素時，稱為空棧。
3 . 4 . 3 　順序棧的實現
棧的存儲也可采用順序存儲結構的方法來實現，采用順序存儲結構的棧稱為順序棧，是指利用一組連續的存儲單元依次存放自棧底到棧頂的數據元素，同時設置指針top來動態地指示棧頂元素的當前位置。
3 . 4 . 2 　棧的基本操作
棧的常用基本操作有以下幾種：
（1）初始化棧：構造一個空棧，初始化棧頂標志。
（2）元素入棧：若棧非滿，棧頂標志上移一位，插入一個元素到棧頂標志指向的位
置，該元素成為新的棧頂元素。
（3）元素出棧：刪除棧頂標志指向的棧頂元素，棧頂標志下移一位，若此時棧非
空，則棧頂標志指向的元素成為新的棧頂元素。
（4）棧空判斷：判斷棧是否為空。
（5）棧滿判斷：判斷棧是否為滿。
（6）棧的長度：求棧的元素個數。
由于棧是一個動態結構，而數組是一個靜態結構，所以在順序棧的操作過程中會有“溢出”情況的出現。當棧滿時，如果再有元素入棧，將會產生“上溢（Overflow）”；當棧空時，如果再執行出棧操作，將會產生“下溢（Underflow）”。為了避免發生棧溢出情況，在進行入棧和出棧操作前應先檢測棧是否已滿或已空。順序棧的程序定義如下：
其中，maxsize為棧中允許存放元素個數的最大值，top是棧頂標志，指示存放數組的
下標，不是真正的指針，當top= -1時表示空棧，當top= maxsize -1時表示滿棧。
棧來存儲數學運算表達式
日常生活中，我們所遇見的數學表達式都是類似于a+b-xy這樣的中綴表達式。但在計算機中，是如何翻譯這個表達式并對其求值呢？
例如，x+y*(a-b)-d/e所對應的后綴表達式是xyab-*+de/。計算機運用該方法進行計算的原理在于，從左向右掃描時，當遇到操作數，則將操作數進棧；當遇到操作符時，彈出兩個操作數，進行運算后，將新的結果壓入棧中。循環如此，直到棧內不含操作符，彈出結果。
該算法的特點在于，操作數與操作符使用同一個棧，但是要將算術表達式先轉換為后綴表達式。
實踐：一個是存放操作數的data棧，一個是存放操作符op棧。利用事先定義好的運算符優先級，將操作符壓棧或退棧。
1.操作符站初始化，將#壓入op棧內，從表達式中讀取字符ch。
2.若ch是操作數，則直接壓入data棧內。
3.若ch是操作符，則判斷instack(op)與outstack(ch)的優先級。
汽車輪渡口
假設數組q的最大下標為10，恰好是每次載渡的最大量。假設客車的隊列是q1，貨車的隊列為q2。若q1充足，則每取4個q1元素后再取一個q2元素，直到q的長度為10。若q1不充足，則直接用q2補齊。

展開更多......

收起↑