简介
线性表是数据结构中最基本的一种，它是由相同数据类型的一组元素组成的数据集合。线性表中的元素之间存在顺序关系，每个元素只有一个前驱和一个后继，除了第一个元素没有前驱，最后一个元素没有后继。线性表有两种常见的实现方式：顺序表和链表。
顺序表
顺序表是一种基于数组的线性表实现方式。它的特点是元素在内存中连续存储，可以通过索引访问元素，随机访问的时间复杂度为O(1)。顺序表的插入和删除操作比较耗时，平均时间复杂度为O(n)。
顺序表的定义如下：
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int length;
} SeqList;
顺序表的插入操作示例：
void insert(SeqList *list, int position, int value) {
// 检查插入位置的合法性
if (position < 0 || position > list->length) {
printf("Invalid position!\n");
return;
}
// 检查顺序表是否已满
if (list->length == MAX_SIZE) {
printf("List is full!\n");
return;
}
// 将position及其之后的元素后移
for (int i = list->length - 1; i >= position; i--) {
list->data[i + 1] = list->data[i];
}
// 插入新元素
list->data[position] = value;
list->length++;
}
链表
链表是一种基于指针的线性表实现方式。它的特点是元素在内存中不连续存储，通过指针相互连接。链表的插入和删除操作比较灵活，时间复杂度为O(1)。但是访问链表中的元素需要遍历，时间复杂度为O(n)。
链表的定义如下：
typedef struct Node {
int data;
struct Node *next;
} ListNode;
链表的插入操作示例：
void insert(ListNode *list, ListNode *position, int value) {
// 创建新节点
ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
newNode->data = value;
// 插入新节点
newNode->next = position->next;
position->next = newNode;
}
总结
线性表是数据结构中最基本且重要的一种。顺序表适用于元素数量固定且需要随机访问的场景，而链表适用于元素数量不确定且需要经常进行插入和删除操作的场景。在实际开发中，根据不同的需求选择合适的线性表实现方式是非常重要的。
