資源簡介

(共31張PPT)
2.1　數據存儲的順序結構與鏈式結構
2 . 1 . 1 　數據存儲的順序結構
數據元素之間有一種常見的邏輯結構——線性結構，其數據元素中除第一個和最后一個數據元素之外，其他數據元素都是首尾相接的。就如生活中的一個隊伍一樣，隊伍中的每個人可以看作一個數據元素，除了第一個人和最后一個人之外，其他人都是跟在某一個人之后，且其后面又跟著另外一個人。如某數據結構中，數據元素的集合K和K上二元關系的集合R如下：
K＝{ a1，a2，…，ai-1，ai ，…，an-1，an }
R ={< a1，a2 > ，< a2，a3 >，…，< ai-1，ai > ，…，< an-1，an >}
其中，i為整數且1＜i≤n 。
我們說ai-1是ai的前驅，ai是ai-1的后繼。這種數據元素之間的線性關系指的是邏輯結構上的，而在物理存儲上則不一定。
2.2　數據的順序存儲與組織
數據在計算機中能夠以順序結構進行存儲。用計算機程序來實現對數據元素的順序存儲與組織，可以使用數組這種數據結構。
1．一維數組
在計算機程序設計中，可以通過數組（Array）這種數據結構來實現對具有相同數據類型且按一定邏輯順序排列的數據元素的存儲與組織，定義了一個數組就是定義了一塊可使用的連續存儲空間，數組的基本類型就是數據元素的類型，數組的長度就是數組元素的最大個數。在C++語言中，數組的一般定義方式為：
類型說明符 數組名[數組長度];
其中，“類型說明符”是任一種數據類型，“數組名”是用戶定義的數組標識符，“數組長度”必須為常量表達式。例如：
int a[6];
一維數組 int a[6]
a[0] a[1] a[2] a[3] a[4] a[5]
1 2 3 4 5 6
定義數組為整型，數組名為a，數組長度為6的一個數組。
a=[1,2,3,4,5,6]
2．二維數組
數組的下標可以是一個，也可以是多個。當數組有兩個下標時，就稱為二維數組。二維數組可以看成一維數組的嵌套，即首先把它看作一個一維數組，這個數組的每個元素又是一個一維數組。如一個二維數組b，可看成為某個一維數組共有n個元素，分別是b[0]，b[1]，…，b[n-1]，其中每個元素b[i]（0≤i＜n）又是一個有m個元素的一維數組，分別是b[i][0]， b[i][1]，…，b[i][m-1]。
從邏輯結構上，我們也可以把這個二維數組看成一個n行m列的矩陣，并把第一個下標稱為行下標，第二個下標稱為列下標。
int b[4][3];
int b[4]
雖然二維數組在邏輯結構上具有行與列兩個方向，但它作為一種順序結構，所有元素在計算機內存空間中的物理存儲地址仍是連續的。如在n行m列的二維數組b中，每個數據元素占用d個字節，假設b的第一個數據元素的計算機存儲地址為Loc(b[0][0])，那么b的存儲結構如圖2-5所示。
2 . 2 . 2 　數組的基本操作
對于一維數組，通常有遍歷（用于數組元素的賦值或查找）、插入元素、刪除元素這幾種操作。
通過對數組的操作，我們可以實現以數組為數據結構的數據的各種管理功能。
2 . 1 . 2 　數據存儲的鏈式結構
數據的鏈式結構與順序結構不同，它的特點是存儲各個數據元素的計算機存儲單元的地址不一定是連續的。因此，為了表示每個數據元素ai與其后繼數據元素ai+1之間的邏輯關系，對于數據元素ai來說，除了存儲其本身的信息，還需要存儲其后繼數據元素的存儲位置信息。
比如，人們到銀行、醫院辦理業務時，一般都是在叫號系統取號之后就在大廳中靜坐等候。此時的人們看似無序，但叫號系統為每個人分配的號碼無形中把等候的人們串成了一條鏈子。
當以鏈式結構存儲數據時，一種最簡單也最常用的方法是分別用兩個域存儲數據元素的兩部分信息：數據域存儲數據元素自身信息，指針域存儲后繼數據元素的存儲位置。
鏈式結構存儲學生信息表
指針不指向任何一個存儲單元，這種指針稱為空指針，最后一位同學由于沒有后記數據，所以指針域沒有指向任何一個存儲單元，用符號表示指針域為空指針賦值為null。
2 . 3 . 1 　指針與指針變量
采用鏈式結構存儲數據的特點是：每個數據元素除了要存儲數據本身的信息外，還需要存儲一個指示其后繼數據元素的信息（即后繼數據元素的存儲位置）。在C++語言中，通常使用指針（Pointer）來實現這種存儲位置的指示。
所謂指針，就是指某個內存單元的地址。在C++語言中，指針也是一種數據類型。與普通數據類型不同的是，定義指針變量（Pointer Variable）沒有專門的關鍵字，而是利用“*”（星號）來進行定義。
C++語言中定義指針變量的一般形式為：類型說明符 *變量名;
//指針變量的定義形式：類型說明符 *變量名；
int *pi; //定義一個整型指針
float *pf; //定義一個浮點型指針
string *ps; //定義一個字符串指針
struct WareInfo *pware; //定義一個結構類型指針
定義一個變量，其實就代表分配計算機內存中的一個存儲單元用于存儲數據，變量名通常就代表所存儲的數據。但是，如果我們在變量名前面使用“&”運算符（取地址運算符），則表示獲取變量對應存儲空間的地址。例如：
int a=42;
int *pi=&a;
在計算機程序中，我們通過鏈表（Linked Lists）這種數據結構來實現鏈式結構的數據存儲與組織，鏈表由一系列結點組成，結點可以動態生成。每個結點包括兩個部分：一個是存儲數據的數據域，另一個是存儲下一個結點物理地址的指針域。數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表有多種不同的類型，如單向鏈表、單向循環鏈表、雙向鏈表、雙向循環鏈表等，本節我們學習的是單向鏈表。
因為鏈表是由若干個結點鏈接而成的，每個結點都具有相同的結構，因此我們定義鏈表的結構時只需要定義鏈表結點的結構即可。以下是鏈表結點的類型定義：
typedef 類型聲明 類型別名;因為鏈表就像鐵鏈一樣，一環扣一環，只要記住第一環，那整個鏈表就被記住了。所以，只需要定義一個LinkList類型的變量L（即LinkNode的指針變量），就可以記錄和使用整個鏈表，L就稱為鏈表的頭指針，其定義如下：
LinkList L=NULL; //定義鏈表頭指針
在定義鏈表頭指針L時，可將其初始值設為NULL。這是因為，對于指針變量，如果沒有指向任何存儲單元，我們通常會把它賦值為NULL，NULL是一個常量值，表示指針不指向任何一個存儲單元。這樣的指針稱為空指針。
插入結點
刪除結點

展開更多......

收起↑