---

順序存儲線性表是一種基本的數據結構，它將線性表的元素按照一定的順序存放在一組地址連續的存儲單元中。在這篇博客中，我們將詳細介紹順序存儲線性表的實現，并以C、C#和C++三種編程語言為例，展示如何實現一個順序存儲線性表。

一、順序存儲線性表的基本概念

順序存儲線性表是一種線性表的實現方式，它具有以下特點：

元素類型相同：順序存儲線性表中的元素類型相同，每個元素占用一定的存儲空間。
元素有序：順序存儲線性表中的元素按照一定的順序排列，通常為非遞減順序。
隨機訪問：順序存儲線性表支持隨機訪問，即可以通過索引直接訪問表中的任意元素。
動態擴展：順序存儲線性表可以根據需要動態地擴展存儲空間，以容納更多元素。

二、順序存儲線性表的實現

1、數據結構定義

首先，我們需要為順序存儲線性表定義一個數據結構。以C語言為例，可以使用結構體（struct）來定義：

#include <stdio.h>
#include <stdlib.h>typedef struct {int *data; // 指向動態分配的數組int size;  // 線性表的當前長度int capacity; // 線性表的容量
} SequenceList;

2、初始化

初始化順序存儲線性表，為其分配初始容量。在C語言中，我們可以使用malloc函數動態分配內存：

void initSequenceList(SequenceList *list, int capacity) {list->data = (int *)malloc(capacity * sizeof(int));if (list->data == NULL) {exit(-1); // 內存分配失敗，退出程序}list->size = 0;list->capacity = capacity;
}

3、添加元素

向順序存儲線性表中添加元素。如果當前容量不足以容納新元素，需要先擴展容量：

void appendSequenceList(SequenceList *list, int value) {if (list->size == list->capacity) {// 擴展容量int newCapacity = list->capacity * 2;int *newData = (int *)malloc(newCapacity * sizeof(int));if (newData == NULL) {exit(-1); // 內存分配失敗，退出程序}for (int i = 0; i < list->size; i++) {newData[i] = list->data[i];}free(list->data);list->data = newData;list->capacity = newCapacity;}list->data[list->size++] = value;
}

4、訪問元素

訪問順序存儲線性表中的指定元素：

int getSequenceList(const SequenceList *list, int index) {if (index < 0 || index >= list->size) {return -1; // 索引無效，返回-1}return list->data[index];
}

5、修改元素

修改順序存儲線性表中的指定元素：

void setSequenceList(SequenceList *list, int index, int value) {if (index < 0 || index >= list->size) {return; // 索引無效，不進行操作}list->data[index] = value;
}

6、刪除元素

刪除順序存儲線性表中的指定元素：

void removeSequenceList(SequenceList *list, int index) {if (index < 0 || index >= list->size) {return; // 索引無效，不進行操作}for (int i = index + 1; i < list->size; i++) {list->data[i - 1] = list->data[i];}list->size--;
}

7、銷毀

銷毀順序存儲線性表，釋放分配的內存：

void destroySequenceList(SequenceList *list) {free(list->data);list->data = NULL;list->size = 0;list->capacity = 0;
}

三、示例

下面我們使用C、C#和C++三種編程語言，分別實現一個順序存儲線性表，并添加、刪除、訪問和打印線性表中的元素。

C語言示例

#include <stdio.h>
#include <stdlib.h>typedef struct {int *data;int size;int capacity;
} SequenceList;void initSequenceList(SequenceList *list, int capacity) {list->data = (int *)malloc(capacity * sizeof(int));if (list->data == NULL) {exit(-1);}list->size = 0;list->capacity = capacity;
}void appendSequenceList(SequenceList *list, int value) {if (list->size == list->capacity) {int newCapacity = list->capacity * 2;int *newData = (int *)malloc(newCapacity * sizeof(int));if (newData == NULL) {exit(-1);}for (int i = 0; i < list->size; i++) {newData[i] = list->data[i];}free(list->data);list->data = newData;list->capacity = newCapacity;}list->data[list->size++] = value;
}int getSequenceList(const SequenceList *list, int index) {if (index < 0 || index >= list->size) {return -1;}return list->data[index];
}void setSequenceList(SequenceList *list, int index, int value) {if (index < 0 || index >= list->size) {return;}list->data[index] = value;
}void removeSequenceList(SequenceList *list, int index) {if (index < 0 || index >= list->size) {return;}for (int i = index + 1; i < list->size; i++) {list->data[i - 1] = list->data[i];}list->size--;
}void destroySequenceList(SequenceList *list) {free(list->data);list->data = NULL;list->size = 0;list->capacity = 0;
}int main() {SequenceList list;initSequenceList(&list, 10);appendSequenceList(&list, 1);appendSequenceList(&list, 2);appendSequenceList(&list, 3);printf("Get element at index 1: %d\n", getSequenceList(&list, 1));setSequenceList(&list, 1, 4);printf("Get element at index 1 after modification: %d\n", getSequenceList(&list, 1));removeSequenceList(&list, 0);printf("Get element at index 0 after removal: %d\n", getSequenceList(&list, 0));destroySequenceList(&list);return 0;
}

C#語言示例

using System;public class SequenceList
{private int[] data;private int size;private int capacity;public SequenceList(int capacity){this.data = new int[capacity];this.size = 0;this.capacity = capacity;}public void Append(int value){if (size == capacity){int newCapacity = capacity * 2;int[] newData = new int[newCapacity];for (int i = 0; i < size; i++){newData[i] = data[i];}data = newData;capacity = newCapacity;}data[size++] = value;}public int Get(int index){if (index < 0 || index >= size){return -1;}return data[index];}public void Set(int index, int value){if (index < 0 || index >= size){return;}data[index] = value;}public void RemoveAt(int index){if (index < 0 || index >= size){return;}for (int i = index + 1; i < size; i++){data[i - 1] = data[i];}size--;}public void Clear(){size = 0;}
}class Program
{static void Main(string[] args){SequenceList list = new SequenceList(10);list.Append(1);list.Append(2);list.Append(3);Console.WriteLine("Get element at index 1: " + list.Get(1));list.Set(1, 4);Console.WriteLine("Get element at index 1 after modification: " + list.Get(1));list.RemoveAt(0);Console.WriteLine("Get element at index 0 after removal: " + list.Get(0));list.Clear();}
}

C++語言示例

#include <iostream>class SequenceList {
private:int *data;int size;int capacity;public:SequenceList(int capacity) {data = new int[capacity];size = 0;capacity = capacity;}void Append(int value) {if (size == capacity) {int newCapacity = capacity * 2;int *newData = new int[newCapacity];for (int i = 0; i < size; i++) {newData[i] = data[i];}delete[] data;data = newData;capacity = newCapacity;}data[size++] = value;}int Get(int index) {if (index < 0 || index >= size) {return -1;}return data[index];}void Set(int index, int value) {if (index < 0 || index >= size) {return;}data[index] = value;}void RemoveAt(int index) {if (index < 0 || index >= size) {return;}for (int i = index + 1; i < size; i++) {data[i - 1] = data[i];}size--;}void Clear() {size = 0;}
};int main() {SequenceList list(10);list.Append(1);list.Append(2);list.Append(3);std::cout << "Get element at index 1: " << list.Get(1) << std::endl;list.Set(1, 4);std::cout << "Get element at index 1 after modification: " << list.Get(1) << std::endl;list.RemoveAt(0);std::cout << "Get element at index 0 after removal: " << list.Get(0) << std::endl;list.Clear();return 0;
}

在這三個示例中，我們定義了一個順序存儲線性表類，并提供了一系列基本操作，如添加、刪除、訪問和打印元素。通過這些示例，您可以了解如何在不同的編程語言中實現順序存儲線性表。