數據結構---順序表

順序表：在連續的記憶體中，存入一系列結點的儲存單元。示意圖如下所示。

在很多的環境下無法使用官方庫，可以自己寫數據結構，進行使用。

上圖可以看到：儲存地址是連續的，表示可以通過（某一結點的地址+偏移量）直接存取其他結點。

順序表的特點：隨機存取（通過表頭元素地址和元素的標號，在O(1)的時間複雜度找到指定元素）
順序表的不足：刪除和插入都需要移動大量的元素

順序表基本操作：構造、插入、擴容、查詢、刪除、遍歷。以下是目錄：

• 順序表的構造
  • 順序表的建立
  • 表的初始化
• 結點插入
• 表的擴容
• 結點查詢
• 結點刪除
• 表的遍歷
• 釋放記憶體

順序表的構造

• 順序表的建立

1. 正如上圖中看到的，需要變數記錄，表的最大長度size和當前狀態下表內數據個數。
2. 其次，需要一個指針變數指向記憶體地址data。

typedef struct Vector {
	// 最大容量和當前順序表個數
    int size,length;
	// 用來指向儲存元素的數據
    int *data;
    
} Vector;

• 表的初始化

1. 分別爲表中的變數賦值
2. 爲順序表的數據儲存分配記憶體

void init(Vector *vector, int size) {
    vector->size = size;
    vector->length = 0;
	// 這裏分配的記憶體是存放數據陣列的記憶體
    vector->data = (int*)malloc(sizeof(int)*size);
}

結點插入

• 判斷插入位置是否合法
• 判斷順序表是否已滿，是否需要擴容（主要是因爲size一開始就固定了）。
• 將目標位置及之後的元素後移一位
• 將待插入的元素插入到目標位置

int insert(Vector *vector, int loc, int value) {
	// 判斷形參位置資訊是否符合
    if(loc < 0 || loc > vector->length){
        return ERROR;
    }
	// 判斷是否需要擴容
    if(vector->length >= vector->size){
//        return ERROR;
        expand(vector);
    }
	// 從表尾逐步向後移動
    for(int i = vector->length; i > loc; i--){
        vector->data[i] = vector->data[i-1];
    }
	// 新增新元素
    vector->data[loc] = value;
	// 長度加一
    vector->length++;
    return OK;
}

插入元素（複雜度分析）：

表的擴容

• 將原來的元素儲存到臨時儲存空間
• 擴大原來的儲存空間
• 將儲存空間裡的數據元素複製到新的儲存空間裡
• 釋放臨時儲存空間

void expand(Vector *vector){
    int  *old_data = vector->data;
    vector->size = vector->size * 2;
    vector->data = (int *)malloc(sizeof(int) * vector->size);
    for(int i = 0; i < vector->length; i++){
        vector->data[i] = old_data[i];
    }
    free(old_data);

}

結點查詢

• 從下標爲0的元素開始依次列舉所有元素
• 發現和value相同的值，則返回他的index
• 列舉沒找到目標元素則返回-1

int search(Vector *vector, int value) {
	for (int i = 0; i < vector->length; i++) {
		if (vector->data[i] == value) {
			return i;
		}
	}
	return -1;
}

查詢方法的時間複雜度：

 

結點刪除

• 判斷線標是否合法（if）
• 將目標下標之後的元素前移一位（for）
• 更新順序表的長度（length--）

int delete_node(Vector *vector, int index) {
	if (index < 0 || index >= vector->length) {
		return ERROR;
	}
	for (int i = index + 1; i < vector->length; ++i) {
		vector->data[i - 1] = vector->data[i];
	}
	vector->length = vector->length - 1;
	return OK;
}

刪除方法時間複雜度：

 

表的遍歷

• 從下標爲0的元素開始遍歷
• 輸出所有的元素值

void print(Vector *vector) {
	for (int i = 0; i < vector->length; i++) {
		if (i > 0) {
			printf(" ");

		}
		printf("%d", vector->data[i]);
	}
	printf("\n");
}

 

釋放記憶體

• 在建立鏈表指針的時候申請一部分需要釋放
• 在建立數據儲存單元的時候需要釋放一部分

void clear(Vector *vector) {
    free(vector->data);
    free(vector);
}

 

用順序表完成以下題目：

程式碼如下：

int main() {
    Vector *a = (Vector *)malloc(sizeof(Vector));
    init(a, 5);
    int n, col, data;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {

		scanf("%d%d", &col, &data);
		insert(a,col,data);

	}
	clear(a);

    return 0;
}

 

 

第二道題

int main() {
    Vector *a = (Vector *)malloc(sizeof(Vector));
    init(a, 20);
    int m, t,index,value,feiwu;
	scanf("%d", &m);
    for(int i = 0; i < m; i++){
        scanf("%d", &t);
        switch(t){
            case 1 :
                scanf("%d%d", &index, &value);
                feiwu = insert(a,index,value);
                break;
            case 2 :
                scanf("%d", &index);
                feiwu = delete_node(a,index);
                break;
            case 3 :
                scanf("%d", &value);
                feiwu = search(a,value);
                break;
            case 4 :
                print(a);
                break;
   }
    }
    free(a);

    return 0;
}