数据结构（王道）——线性表之静态链表&顺序表和链表的比较

**数据结构（王道）——线性表之静态链表&顺序表和链表的比较**

在计算机科学中，线性表是指一组元素按照一定的顺序排列起来的集合。线性表可以分为两大类：静态链表和动态链表（也就是我们常说的链表）。本文将重点讨论静态链表和顺序表与链表之间的比较。

**1. 静态链表**

静态链表是指在程序运行前就已经分配好了内存空间，且不能改变其大小的链表。也就是说，在程序编译时，静态链表的大小已经固定了，不会随着数据的增加而动态调整。

**1.1 静态链表的特点**

* 静态链表在程序运行前就已经分配好了内存空间。
* 静态链表不能改变其大小。
* 静态链表通常用于固定大小的数据集合。

**1.2 静态链表的实现**

静态链表可以使用数组来实现。每个元素都有一个指向下一个元素的指针，最后一个元素的指针指向 NULL 表示链表结束。

ctypedef struct Node {
 int data;
 struct Node* next;
} Node;

void init(Node** head) {
 *head = (Node*)malloc(sizeof(Node));
 (*head)->data =0;
 (*head)->next = NULL;
}

void add(Node** head, int data) {
 Node* newNode = (Node*)malloc(sizeof(Node));
 newNode->data = data;
 newNode->next = NULL;

 if (*head == NULL) {
 *head = newNode;
 } else {
 Node* current = *head;
 while (current->next != NULL) {
 current = current->next;
 }
 current->next = newNode;
 }
}

**2. 顺序表**

顺序表是指一组元素按照一定的顺序排列起来的集合，且所有元素都存储在一个连续的内存空间中。

**2.1 顺序表的特点**

* 顺序表中的所有元素都存储在一个连续的内存空间中。
* 顺序表可以使用数组来实现。
* 顺序表通常用于固定大小的数据集合。

**2.2 顺序表的实现**

顺序表可以使用数组来实现。每个元素都有一个索引，表示其在数组中的位置。

ctypedef struct {
 int data[10];
} OrderList;

void init(OrderList* list) {
 for (int i =0; i < 10; i++) {
 list->data[i] =0;
 }
}

void add(OrderList* list, int index, int data) {
 if (index >=0 && index <=9) {
 list->data[index] = data;
 } else {
 printf("Index out of range!
");
 }
}

**3. 链表**

链表是指一组元素按照一定的顺序排列起来的集合，且每个元素都有一个指向下一个元素的指针。

**3.1 链表的特点**

* 链表中的每个元素都有一个指向下一个元素的指针。
* 链表可以动态地增加或减少元素。
* 链表通常用于动态大小的数据集合。

**3.2 链表的实现**

链表可以使用结构体来实现。每个元素都有一个指向下一个元素的指针，最后一个元素的指针指向 NULL 表示链表结束。

ctypedef struct Node {
 int data;
 struct Node* next;
} Node;

void init(Node** head) {
 *head = (Node*)malloc(sizeof(Node));
 (*head)->data =0;
 (*head)->next = NULL;
}

void add(Node** head, int data) {
 Node* newNode = (Node*)malloc(sizeof(Node));
 newNode->data = data;
 newNode->next = NULL;

 if (*head == NULL) {
 *head = newNode;
 } else {
 Node* current = *head;
 while (current->next != NULL) {
 current = current->next;
 }
 current->next = newNode;
 }
}

**4. 静态链表与顺序表和链表的比较**

静态链表、顺序表和链表都是线性表的一种实现方式。下面是它们之间的主要区别：

* **内存分配**: 静态链表在程序运行前就已经分配好了内存空间，而顺序表和链表可以动态地增加或减少元素。
* **数据大小**: 静态链表通常用于固定大小的数据集合，而顺序表和链表可以用于动态大小的数据集合。
* **性能**: 静态链表由于其内存分配方式，通常比顺序表和链表更快。

综上所述，静态链表、顺序表和链表都是线性表的一种实现方式，每种实现方式都有其特点和应用场景。