【數據結構（二）】線性表|順序表|C/C++|順序表的動靜態實現及基本操作|2021王道數據結構筆記整理及測試
2020-08-12 10:46:03
線性表的物理/儲存結構之——順序表
【寫在前面】本部落格是筆者按照2021王道數據結構考研複習指導的視訊課程整理的筆記，均已用編譯器測試過可行，部分函數按照老師的提示做了一些程式碼健壯性的提升，可以放心使用。
目錄導航（點選跳轉）
一、順序表的相關知識
1、順序儲存的概念
順序儲存：是指把邏輯上相鄰的元素儲存在物理位置上也相鄰的儲存單元中，元素之間的關係由儲存單元的鄰接關係來體現。
2、如何知道一個數據元素的大小
C語言中爲sizeof(ElemType)
ElemType就是你的順序表中存放的數據元素型別。
eg：
sizeof(int)=4B;
sizeof(Customer)=8B;//Customer爲包含兩個整型元素的結構體
二、順序表的實現：靜態儲存
1、靜態分配
使用陣列的方式來存放順序表，陣列的長度大小一旦確定了之後就不可以改變，這是靜態陣列的特點。分配一整片連續的儲存空間，大小爲MaxSize*sizeof(ElemType)。
#define Maxsize 10 //宏定義一個常數，定義最大長度
typedef struct{
ElemType data[MaxSize]; //定義了一個靜態陣列，大小爲Maxsize，用來存放數據元素
int length; //順序表的當前長度
}SqList; //Sq表示sequence（順序、序列）
//自己寫程式碼的時候ElemType是什麼型別吧ElemType替換掉就可以了。
2、定義一個存放整型數據的順序表，初始化順序表，並輸出
#include<stdio.h>
#define Maxsize 10 //定義最大長度
typedef struct {
int data[Maxsize]; //定義一個長度爲Maxsize的陣列用來存放數據元素
int length; //順序表的當前長度
}SqList;
//基本操作——初始化一個順序表
void InitList(SqList &L) {
for (int i = 0;i < Maxsize;i++) {
L.data[i] = 0; //將所有數據元素設定爲預設初始值0
}
L.length = 0;
}
void PrintList(SqList L) {
for (int i = 0;i < Maxsize;i++) {
printf("%d ",L.data[i]);
}
printf("\n%d ", L.length);
}
int main() {
SqList L; //宣告一個順序表
InitList(L); //初始化順序表
PrintList(L);
return 0;
}
列印輸出內容：
3、【注】如果不給data[i]賦初值，則會輸出記憶體中遺留的髒數據。
測試如下。將上一個程式碼中的初始化函數改爲如下內容，編譯測試，輸出如下。
//基本操作——初始化一個順序表
void InitList(SqList &L) {
//for (int i = 0;i < Maxsize;i++) {
// L.data[i] = 0; //將所有數據元素設定爲預設初始值0
//}
L.length = 0;
}
列印輸出內容：
【注】而實際上上面的用i<Maxsize來存取陣列的寫法是違規的，而應該用i<length來存取，因爲不應該從第一個元素存取到最後一個元素而是應該存取到當前儲存的實際長度的最後一個元素。
4、其他筆記
1. 給各個數據元素設定預設值的步驟可以省略，因爲按正常的存取方式的話，其實不應該存取超過順序表實際長度的數據元素。這種存取方式也不夠好，更好的做法是使用基本操作來存取各個數據元素。
2. Q：C語言不是會自動給int型的變數設定初始值爲0嗎？
A：設定初始值是編譯器做的事情，換一個C語言的編譯器可能不會幫你做初始化的工作。
所以當我們宣告一個順序表的時候，把它的length值設定爲0這一步是必須做的。
3. Q：如果陣列存滿了怎麼辦？
A：直接放棄治療，順序表的表長一旦確定了就無法更改。（儲存空間是靜態的）
4. Q：如果剛開始就宣告一塊很大的儲存空間，存在什麼問題？
A：很浪費。