数据结构与算法——线性表

**数据结构与算法——线性表**

线性表是最基本的线性数据结构之一，它是一种有序集合，元素之间存在前后关系。线性表可以看作是一个一维数组，每个元素都有一个唯一的索引。

### 线性表的定义线性表由以下几个组成部分：

* **元素（Element）**：线性表中的每个数据项称为元素。
* **位置（Position）**：线性表中每个元素的索引，通常用整数表示。
* **长度（Length）**：线性表中元素的数量。

### 线性表的基本操作线性表支持以下基本操作：

* **插入（Insert）**：在指定位置插入一个新元素。
* **删除（Delete）**：从指定位置删除一个元素。
* **查找（Search）**：找到指定元素的位置。
* **遍历（Traversal）**：访问线性表中的所有元素。

### 线性表的实现线性表可以使用数组或链式结构来实现。下面我们将分别介绍这两种实现方式。

#### 数组实现在数组实现中，线性表中的元素存储在一个连续的内存空间中，每个元素都有一个唯一的索引。

ctypedef struct {
 int data[10]; // 元素数组 int length; // 元素数量} ArrayList;

支持基本操作的函数：

* `insert(int index, int value)`：在指定位置插入新元素。
* `delete(int index)`：从指定位置删除元素。
* `search(int value)`：找到指定元素的位置。
* `traversal()`：访问线性表中的所有元素。

cvoid insert(ArrayList *list, int index, int value) {
 if (index < 0 || index > list->length) {
 printf("Invalid index!
");
 return;
 }
 for (int i = list->length; i > index; --i) {
 list->data[i] = list->data[i -1];
 }
 list->data[index] = value;
 ++list->length;
}

void delete(ArrayList *list, int index) {
 if (index < 0 || index >= list->length) {
 printf("Invalid index!
");
 return;
 }
 for (int i = index; i < list->length -1; ++i) {
 list->data[i] = list->data[i +1];
 }
 --list->length;
}

int search(ArrayList *list, int value) {
 for (int i =0; i < list->length; ++i) {
 if (list->data[i] == value) {
 return i;
 }
 }
 return -1; // 未找到}

void traversal(ArrayList *list) {
 printf("线性表中的元素：
");
 for (int i =0; i < list->length; ++i) {
 printf("%d ", list->data[i]);
 }
 printf("
");
}

#### 链式结构实现在链式结构实现中，线性表中的元素存储在一个个的结点中，每个结点都有一个指向下一个结点的指针。

ctypedef struct Node {
 int data; // 元素值 struct Node *next; // 下一个结点指针} Node;

typedef struct {
 Node *head; // 头结点指针 int length; // 元素数量} LinkedList;

支持基本操作的函数：

* `insert(int value)`：在链表尾部插入新元素。
* `delete(int index)`：从指定位置删除元素。
* `search(int value)`：找到指定元素的位置。
* `traversal()`：访问链表中的所有元素。

cvoid insert(LinkedList *list, int value) {
 Node *newNode = (Node *)malloc(sizeof(Node));
 newNode->data = value;
 newNode->next = NULL;
 if (list->head == NULL) {
 list->head = newNode;
 } else {
 Node *current = list->head;
 while (current->next != NULL) {
 current = current->next;
 }
 current->next = newNode;
 }
 ++list->length;
}

void delete(LinkedList *list, int index) {
 if (index < 0 || index >= list->length) {
 printf("Invalid index!
");
 return;
 }
 Node *current = list->head;
 for (int i =0; i < index -1; ++i) {
 current = current->next;
 }
 if (index ==0) {
 list->head = current->next;
 } else {
 current->next = current->next->next;
 }
 --list->length;
}

int search(LinkedList *list, int value) {
 Node *current = list->head;
 while (current != NULL) {
 if (current->data == value) {
 return0; // 找到 }
 current = current->next;
 }
 return -1; // 未找到}

void traversal(LinkedList *list) {
 printf("链表中的元素：
");
 Node *current = list->head;
 while (current != NULL) {
 printf("%d ", current->data);
 current = current->next;
 }
 printf("
");
}

### 总结线性表是最基本的线性数据结构之一，它是一种有序集合，元素之间存在前后关系。线性表可以使用数组或链式结构来实现，支持基本操作如插入、删除、查找和遍历。

在本文中，我们分别介绍了数组实现和链式结构实现的代码示例和注释。这些示例代码展示了如何在 C语言中实现线性表的基本操作，并提供了一些使用说明和注意事项。

希望这篇文章能够帮助你理解线性表的概念、实现方式以及相关的基本操作。