順序表與鏈表-課件

軟件技術(shù)基礎(chǔ)自動化學院參考書籍1、數(shù)據(jù)結(jié)構(gòu)概念及順序表VC++工具使用1.1數(shù)據(jù)結(jié)構(gòu)基本概念1．數(shù)據(jù)（data）

數(shù)據(jù)是指能夠輸入到計算機中，并被計算機識別和處理的符號的集合。

2．數(shù)據(jù)元素（dataelement）

數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位。數(shù)據(jù)元素是一個數(shù)據(jù)整體中相對獨立的單位。但它還可以分割成若干個具有不同屬性的項（字段），故不是組成數(shù)據(jù)的最小單位數(shù)據(jù)結(jié)構(gòu)（datastructure）

是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素所組成的集合。數(shù)據(jù)結(jié)構(gòu)包含三個方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存貯結(jié)構(gòu)和對數(shù)據(jù)所施加的運算。

這三個方面的關(guān)系為：

數(shù)據(jù)的邏輯結(jié)構(gòu)獨立于計算機，是數(shù)據(jù)本身所固有的存貯結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機存貯器中的映像，必須依賴于計算機。運算是指所施加的一組操作總稱。運算的定義直接依賴于邏輯結(jié)構(gòu)，但運算的實現(xiàn)必依賴于存貯結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)基本類型

線性結(jié)構(gòu)——

通迅錄、成績單、花名冊樹形結(jié)構(gòu)——

電子字典、家譜、目錄圖狀結(jié)構(gòu)——

交通線路、通信網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)中常用的存貯結(jié)構(gòu)(1)順序存貯

所有元素存放在一片連續(xù)的存貯單元中，邏輯上相鄰的元素存放到計算機內(nèi)存仍然相鄰。(2)鏈式存貯

所有元素存放在可以不連續(xù)的存貯單元中，元素之間的關(guān)系通過地址確定，邏輯上相鄰的元素存放到計算機內(nèi)存后不一定是相鄰的。(3)索引存貯（略） (4)散列存貯（略）算法（algorithm）

通俗地講，算法就是一種解題的方法。更嚴格地說，算法是由若干條指令組成的有窮序列，它必須滿足下述條件（也稱為算法的五大特性）：（1）輸入：具有0個或多個輸入的外界量（算法開始前的初始量）（2）輸出：至少產(chǎn)生一個輸出，它們是算法執(zhí)行完后的結(jié)果。（3）有窮性：每條指令的執(zhí)行次數(shù)必須是有限的。（4）確定性：每條指令的含義都必須明確，無二義性。（5）可行性：每條指令的執(zhí)行時間都是有限的。1.2

線性數(shù)據(jù)結(jié)構(gòu)

線性表是由有限個同類型的數(shù)據(jù)元素組成的有序序列，一般記作（a1,a2,…,an）。除了a1和an之外，任意元素ai都有一個直接前趨ai-1和一個直接后繼ai+1。a1無前趨，an無后繼。

線性表的存儲結(jié)構(gòu)主要有順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)兩種。

順序表

采用順序存儲結(jié)構(gòu)的線性表稱為順序表，它的數(shù)據(jù)元素按照邏輯順序依次存放在一組連續(xù)的存儲單元中。邏輯上相鄰的數(shù)據(jù)元素，其存儲位置也彼此相鄰。

假定元素a1的物理地址是Loc(a1)，每個元素占d個存儲單元，則第i個元素的存儲位置為：Loc(ai)=Loc(a1)+(i-1)*d

length=nmaxsize01i-2i-1in-1a2…ai-1aiai+1a1…an順序表的主要算法

（1）在表中第i個位置插入新元素x

算法實現(xiàn)的主要步驟是： ①判斷插入位置的合理性以及表是否已滿。

②從最后一個元素開始依次向前，將每個元素向后移動一個位置，直到第i個元素為止。

③向空出的第i個位置存入新元素x。

④最后還要將線性表長度加一。（2）在表中刪除第i個元素

算法實現(xiàn)的主要步驟是： ①判斷刪除位置的合理性。

②從第i+1個元素開始，依次向后直到最后一個元素為止，將每個元素向前移動一個位置。這時第i個元素已經(jīng)被覆蓋刪除。 ③最后還要將線性表長度減一。（3）在表中查找某個元素

下面是根據(jù)數(shù)據(jù)元素本身的值進行查詢的算法，x為需要查找的元素，算法返回元素的實際位置。

intFind(ElemTypex) { for(inti=0;i<length;i++) {//查找成功，返回元素位置

if(data[i]==x)returni+1; } return0; //查找失敗，返回0 }1.3實驗內(nèi)容1、使用順序表實現(xiàn)學生名冊管理程序，名冊中的每條記錄包括學號、姓名、聯(lián)系電話等項。2、實現(xiàn)數(shù)字化菜單管理、學生名冊的建立、記錄的添加、查找、刪除和顯示等功能。2、鏈表的操作

線性鏈表的基本概念線性表的順序存儲存在以下幾個方面的缺點：1、插入或者刪除一個節(jié)點，需要涉及到大量元素的移動問題。2、容易出現(xiàn)上溢或者下溢現(xiàn)象，存儲空間不易擴展。3、多個線性表共享存儲空間時，存在存儲問題。因此在涉及到元素大量移動變動的表中，不宜采用線性表結(jié)構(gòu)。線性鏈表的基本概念鏈式存儲結(jié)構(gòu)：每個節(jié)點有兩部分組成：一個部分用存儲數(shù)據(jù)元素，稱為數(shù)據(jù)域；另外一部分存放指針，叫為指針域。鏈式存儲中元素之間的前后件關(guān)系可以通過指針來標識。鏈式存儲結(jié)構(gòu)既可以用于順序存儲，也可以用于較復雜的非線性存儲。線性鏈表的基本概念

線性鏈表鏈式的存儲結(jié)構(gòu)線性鏈表的邏輯結(jié)構(gòu)2.3.1線性鏈表的基本概念線性鏈表例2.3.1線性鏈表的基本概念相關(guān)操作首先定義一個線性鏈表類linked_Llist，具體如下：//文件名linked_Llist.h#include<iostream>usingnamespacestd;template<classT>//T為虛擬類型structnode{Td;node*next;};1.線性鏈表的插入線性鏈表的插入：在鏈式存儲結(jié)構(gòu)下的線性表中插入一個新元素。首先要給該元素分配一個新結(jié)點，以便用于存儲該元素的值；然后將存放新元素值的結(jié)點鏈接到線性鏈表中指定的位置。此外，在插入時，對于空表或者在第一個結(jié)點之前插入必須單獨考慮。

線性鏈表的插入運算插入（三種情況）

第一種情況：在第一個結(jié)點前插入

p->next

=head;

head=p;（插入前）（插入后）xheadppxhead第二種情況：在鏈表中間插入

p->next=q->next; q->next=p；x(插入前)(插入后)pxqpq第三種情況：在鏈表末尾插入p->next=q->next;//p->next=null;

q->next

=p；p(插入前)(插入后)pqq2.線性鏈表的刪除線性鏈表的刪除：在鏈式存儲結(jié)構(gòu)下的線性表中刪除包含指定元素的結(jié)點。首先要在線性鏈表中找到這個結(jié)點；然后將要刪除結(jié)點的存儲空間釋放回系統(tǒng)。線性鏈表的刪除運算刪除前刪除后ai-1xai+1qpqai-1ai+1xp=q->next;q->next=p->next;分析插入與刪除算法需要考慮的兩種特殊情況：在插入時，對于空表或者在第一個結(jié)點之前插入必須單獨考慮；在刪除時，對于空表及刪除第一個結(jié)點必須單獨考慮，并且還要考慮到鏈表中不存在被刪除元素的情況。2.3.3循環(huán)鏈表對于線性單鏈表，其插入與刪除操作雖然比較方便，但還存在一個問題：對于空表與對第一個結(jié)點的處理必須單獨考慮，使得空表與非空表的運算不統(tǒng)一。解決方法：循環(huán)鏈表（CircularLinkedList）。循環(huán)鏈表的兩個特點在循環(huán)鏈表中增加了一表頭結(jié)點，其數(shù)據(jù)域為任意或者根據(jù)需要來設(shè)置，指針域指向線性表的第一個元素的結(jié)點。循環(huán)鏈表的表頭指針HEAD指向表頭結(jié)點。循環(huán)鏈表中最后一個結(jié)點的指針域不是空，而是指向表頭結(jié)點。即在循環(huán)鏈表中，所有結(jié)點的指針構(gòu)造了一個環(huán)狀鏈。圖2.28循環(huán)鏈表的邏輯狀態(tài)循環(huán)鏈表與線性單鏈表的比較判斷線性單鏈表為空的條件：判斷循環(huán)鏈表為空的條件：head==NULLhead->next==heada1a2an-1an…….HEADa1a2an-1an∧…….HEADHEAD循環(huán)鏈表表頭結(jié)點首元結(jié)點線性單鏈表實驗要點設(shè)計接口函數(shù)鏈表成員插入函數(shù)

參數(shù)：插入位置；

插入成員