c语言线性表

### C语言中线性表的实现与操作 #### 1. 线性表的概念 线性表是一种基本的数据结构，其特点是数据元素之间具有一对一的关系。在线性表中，除了第一个和最后一个元素外，其他每个元素都有唯一的一个前驱和后继[^2]。 #### 2. 线性表的实现方式 线性表可以通过两种主要的方式实现：顺序表和链表。 ##### (1) **顺序表** 顺序表是通过一段连续的内存空间来存储线性表中的元素。以下是基于数组的顺序表示例： ```c #define MAXSIZE 100 typedef int ElemType; // 定义顺序表结构体 typedef struct { ElemType data[MAXSIZE]; int length; } SeqList; ``` - `data` 数组用于存储线性表中的元素。 - `length` 表示当前线性表的实际长度。 ###### 基本操作函数原型 以下是一些常见的顺序表操作函数声明： ```c void InitSeqList(SeqList *L); // 初始化顺序表 bool InsertSeqList(SeqList *L, int pos, ElemType e); // 插入元素 ElemType DeleteSeqList(SeqList *L, int pos); // 删除指定位置的元素 int LocateSeqList(SeqList L, ElemType e); // 查找元素的位置 void PrintSeqList(SeqList L); // 打印顺序表 ``` ###### 示例代码 初始化并打印顺序表的操作如下所示： ```c #include <stdio.h> #include <stdlib.h> void InitSeqList(SeqList *L) { L->length = 0; // 初始为空表 } bool InsertSeqList(SeqList *L, int pos, ElemType e) { if (pos < 1 || pos > L->length + 1) { // 检查插入位置合法性 printf("Insert position error!\n"); return false; } if (L->length >= MAXSIZE) { // 检查容量是否已满 printf("Table is full!\n"); return false; } for (int i = L->length; i >= pos; --i) { // 后移元素 L->data[i] = L->data[i - 1]; } L->data[pos - 1] = e; // 插入新元素 ++(L->length); return true; } void PrintSeqList(SeqList L) { for (int i = 0; i < L.length; ++i) { printf("%d ", L.data[i]); } printf("\n"); } ``` ##### (2) **单链表** 单链表是由一系列节点组成，每个节点包含两个部分：数据域 (`data`) 和指针域 (`next`)。以下是单链表的基本定义： ```c typedef struct Node { ElemType data; struct Node *next; } LinkNode; typedef struct { LinkNode *head; } LinkedList; ``` - `LinkNode` 是链表的节点结构，其中 `data` 存储实际数据，`next` 指向下一个节点。 - `LinkedList` 结构用来管理整个链表，通常只保存头结点地址。 ###### 单链表常见操作 一些常用的单链表操作包括： ```c void CreateLinkedListHead(LinkedList *L); // 头插法创建链表 void CreateLinkedListTail(LinkedList *L); // 尾插法创建链表 bool InsertLinkedList(LinkNode *p, ElemType e); // 在某个节点之后插入新节点 ElemType DeleteLinkedList(LinkNode *p); // 删除某节点后的节点 void PrintLinkedList(LinkNode *head); // 遍历并打印链表 ``` ###### 创建单链表的例子 以下是一个简单的尾插法创建单链表的代码片段： ```c void CreateLinkedListTail(LinkedList *L) { L->head = (LinkNode *)malloc(sizeof(LinkNode)); // 创建头结点 L->head->next = NULL; LinkNode *tail = L->head; // 记录尾部 ElemType value; printf("Enter elements (-1 to end):\n"); while (scanf("%d", &value), value != -1) { LinkNode *newNode = (LinkNode *)malloc(sizeof(LinkNode)); newNode->data = value; newNode->next = NULL; tail->next = newNode; // 新节点接在尾部 tail = newNode; // 更新尾部指针 } } ``` #### 3. 总结 无论是顺序表还是单链表，它们都提供了灵活的方式来管理和操作一组具有线性关系的数据。具体选择哪种实现取决于应用场景的需求。如果需要频繁随机访问，则优先考虑顺序表；而如果更关注动态增删操作效率，则更适合采用单链表[^1]。