数据结构————顺序表

**数据结构——顺序表**

顺序表是一种线性数据结构，元素按照一定的顺序排列在内存中。它是最基本也是最常用的数据结构之一。在计算机科学中，顺序表经常被用来表示一组有序的数据。

**顺序表的定义和特点**

顺序表是一种线性数据结构，它由一系列元素组成，每个元素都有一个唯一的索引或下标。这些元素按照一定的顺序排列在内存中，通常是从低地址到高地址。顺序表的每个元素都可以通过其下标来访问。

顺序表的特点包括：

* 元素按一定顺序排列* 每个元素有一个唯一的索引或下标* 元素按照一定的顺序存储在内存中**顺序表的应用**

顺序表广泛应用于各种计算机系统和程序中，例如：

* 数组：顺序表是数组的基础结构。数组是一种特殊的顺序表，它的元素都有相同的类型。
* 链表：链表是一种非连续存储的顺序表，每个元素都有一个指向下一个元素的指针。
* 栈和队列：栈和队列都是基于顺序表的数据结构，用于实现后进先出(LIFO)和先进先出(FIFO)的访问顺序。

**顺序表的操作**

顺序表支持以下基本操作：

* **插入（Insert）**: 在指定位置插入一个新元素。
* **删除（Delete）**: 删除指定位置的元素。
* **查找（Search）**: 查找指定值的元素。
* **修改（Modify）**: 修改指定位置的元素。

**顺序表的实现**

顺序表可以使用以下数据结构来实现：

* 数组：使用一个数组来存储所有元素，通过下标访问每个元素。
* 链表：使用链表来存储所有元素，每个元素都有一个指向下一个元素的指针。

**示例代码**

c#include <stdio.h>
#include <stdlib.h>

// 定义顺序表结构体typedef struct {
 int *data;
 int size;
} SeqList;

// 初始化顺序表void init(SeqList *list, int capacity) {
 list->data = (int *)malloc(sizeof(int) * capacity);
 list->size =0;
}

// 插入元素void insert(SeqList *list, int index, int value) {
 if (index < 0 || index > list->size) {
 printf("Invalid index
");
 return;
 }

 // 扩容数组 int *newData = (int *)realloc(list->data, sizeof(int) * (list->size +1));
 for (int i = list->size; i >= index; --i) {
 newData[i] = list->data[i -1];
 }
 newData[index] = value;
 free(list->data);
 list->data = newData;
 list->size++;
}

// 删除元素void delete(SeqList *list, int index) {
 if (index < 0 || index >= list->size) {
 printf("Invalid index
");
 return;
 }

 // 缩容数组 int *newData = (int *)realloc(list->data, sizeof(int) * (list->size -1));
 for (int i = index; i < list->size -1; ++i) {
 newData[i] = list->data[i +1];
 }
 free(list->data);
 list->data = newData;
 list->size--;
}

// 查找元素int search(SeqList *list, int value) {
 for (int i =0; i < list->size; ++i) {
 if (list->data[i] == value) {
 return i;
 }
 }
 return -1;
}

// 修改元素void modify(SeqList *list, int index, int value) {
 if (index < 0 || index >= list->size) {
 printf("Invalid index
");
 return;
 }

 list->data[index] = value;
}

int main() {
 SeqList list;
 init(&list,10);

 insert(&list,2,5);
 insert(&list,4,10);
 delete(&list,1);
 modify(&list,0,20);

 printf("Size: %d
", list.size);
 for (int i =0; i < list.size; ++i) {
 printf("%d ", list.data[i]);
 }
 printf("
");

 return0;
}