順序結構就是物理上的連續(在內存中使用連續一塊的地址)，其實就是陣列啦!! 不過這次要實現有基本操作的陣列:
如上圖表示，建立總容量為MaxSize的陣列，但目前只使用了N的空間，建立一個LAST代表矩陣使用的大小。LAST=N-1，表長為LAST+1，當表空時LAST=-1，資料存於Data[0]~Data[Last]之中。 結構如下:
#define MAXSIZE 1000;
typedef int Position; //下標位置
typedef struct LNode * PtrToNode;
struct LNode {
ElementType Data[MAXSIZE];
Position Last;
};
typedef PtrToNode List;1. 初始化 MakeEmpty :
List MakeEmpty(){
List L = (PtrToNode)malloc(sizeof(struct LNode));
L->Last = -1;
return L;
}2. 查找 Find (給定值，找出下標，沒找到返回 -1) :
Position Find(List L, ElementType X){
Position i=0;
while(i <= L->Last && L->Data[i]!=X) //兩種跳出方式: 1. 遍歷完 2. 找到
i++;
if(i > L->Last) return -1; // i 是遍歷完跳出來的
else return i;
}3. 插入 Insert (插入進 i) :
- 將 Ai~An 順序向後移動(下標 i-1 ~ L->Last-1)
- X置入第 i 位置
- 修改Last 位置，使之為最後一個數下標
//注意: 1. 不可滿、會溢出 2. 移動順序(應由後先動) 3. 搞清楚序號&下標差異
bool Insert (List L,ElementType x, int i){ // i 為序號
if(L->Last == MAXSIZE -1){ //檢查滿
printf("已滿");
return false;
}
if(i < 1 || i > L->Last +2){ //不能插入第0個
printf("插入序號錯誤");
return false;
}
for(int j=L->Last ; j>=i-1 ; j--)
L->Data[j+1]=L->Data[j]; //現在空出 i 了
L->Data[i-1]=x;
L->Last++;
return true;
}這題要仔細思考序號與下標的關係，知道下標從0開始，下標=序號-1。我要是不看書打肯定也會打錯!
4. 刪除 Delete (刪除序號 i ，沒數則返回false) :
這題恰好與插入相反，找到序號 i 後，由 i+1 開始覆蓋，直到L->Last。
bool Delete(List L , int i){
if(i<1 || i>L->Last+1){
printf("刪除位置不合法");
return false;
}
for(int j=i;j<=L->Last;j++)
L->Data[j-1]=L->Data[j];
L->Last--;
return true;
}完整程式碼:
參考資料 :
- 《数据结构》（第2版），陈越、何钦铭、徐镜春、魏宝刚、杨枨 编著，高等教育出版社，2016年6月
- https://www.icourse163.org/course/ZJU-93001
