当前位置：首页 > web >正文

数据结构之线性表

web 2025/5/8 9:42:18

一、线性表的定义与抽象数据类型

1.定义：线性表是零个或多个数据元素的有限序列，元素具有相同类型且存在唯一前驱和后继（除首尾元素），如排队的小朋友序列。

2.抽象数据类型：包含初始化、清空、判空、获取元素、查找、插入、删除、求长度等操作，例如根据位序获取元素、查找元素位置等。

二、顺序存储结构

1.存储方式：用地址连续的数组存储，通过数组下标实现随机访问，数据元素逻辑顺序与物理顺序一致。

2.结构定义：包含数据数组data和当前长度length，如typedef struct { ElemType data[MAXSIZE]; int length; } SqList;。

3.操作特点：

获取元素：时间复杂度为 O(1)，直接通过下标访问。
插入 / 删除：需移动后续元素，最坏时间复杂度为 O(n)。例如插入时从最后一个元素向前移动，直到目标位置。

4.优缺点：

优点：无需额外空间存储逻辑关系，存取高效。
缺点：插入删除效率低，需预分配固定容量，可能导致空间浪费或溢出。

5.代码示例：

①顺序表的基本操作

#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 20
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0typedef int ElemType;
typedef struct 
{ElemType data[MAXSIZE];int length;
} SqList;// 初始化
int InitList(SqList* L) 
{L->length = 0;return OK;
}// 插入操作
int ListInsert(SqList* L, int i, ElemType e) 
{if (i < 1 || i > L->length + 1 || L->length == MAXSIZE) return ERROR;for (int k = L->length - 1; k >= i - 1; k--) //从顺序表的最后一个元素开始，将从插入位置开始的所有元素依次向后移动一位，为新元素腾出位置{L->data[k + 1] = L->data[k];}L->data[i - 1] = e;//将指定元素放入指定位置L->length++;return OK;
}// 删除操作
int ListDelete(SqList* L, int i, ElemType* e) 
{if (i < 1 || i > L->length) return ERROR;*e = L->data[i - 1];//将指定位置的元素值赋给 *efor (int k = i; k < L->length; k++) //从删除位置的下一个元素开始，将后面的元素依次向前移动一位，覆盖掉被删除的元素。{L->data[k - 1] = L->data[k];}L->length--;return OK;
}// 查找元素
//遍历顺序表中的所有元素，若找到与 e 相等的元素，则返回该元素在顺序表中的位置（位置从 1 开始计数）
int LocateElem(SqList* L, ElemType e) 
{for (int i = 0; i < L->length; i++) {if (L->data[i] == e) {return i + 1;}}return 0;
}// 显示顺序表元素
void DisplayList(SqList* L) {if (L->length == 0) {printf("顺序表为空。\n");return;}printf("顺序表元素为：");for (int i = 0; i < L->length; i++) {printf("%d ", L->data[i]);}printf("\n");
}int main() {SqList L;InitList(&L);// 测试插入操作ListInsert(&L, 1, 10);ListInsert(&L, 2, 20);ListInsert(&L, 3, 30);DisplayList(&L);// 测试查找操作int pos = LocateElem(&L, 20);if (pos) {printf("元素 20 在顺序表中的位置是：%d\n", pos);}else {printf("未找到元素 20。\n");}// 测试删除操作ElemType deleted;if (ListDelete(&L, 2, &deleted)) {printf("已删除位置 2 的元素，删除的元素是：%d\n", deleted);}else {printf("删除操作失败。\n");}DisplayList(&L);return 0;
}

②使用顺序表实现学生成绩管理系统

#include <stdio.h>
#include <stdlib.h>//提供通用工具函数，例如动态内存分配和进程控制函数。
#include <string.h>#define MAX_STUDENTS 100 //定义了顺序表所能容纳的最大学生数量// 定义学生结构体 
//用于存储单个学生的信息，包含学生姓名、学号和成绩
typedef struct 
{char name[50];int id;float score;
} Student;// 定义顺序表结构体
//用于表示顺序表，包含一个 Student 类型的数组 students 和一个表示当前顺序表长度的整数 length
typedef struct {Student students[MAX_STUDENTS];int length;
} SeqList;// 初始化顺序表
void initList(SeqList* list) 
{list->length = 0; //将顺序表的长度初始化为 0，表示顺序表为空
}// 添加学生信息
void addStudent(SeqList* list, int id, const char* name, float score) 
{if (list->length >= MAX_STUDENTS) {printf("顺序表已满，无法添加新学生！\n");return;}Student newStudent;newStudent.id = id;strcpy_s(newStudent.name, name);newStudent.score = score;list->students[list->length] = newStudent;list->length++;//将新学生对象添加到顺序表的末尾，并将顺序表的长度加 1
}// 根据学生 ID 删除学生信息
void deleteStudent(SeqList* list, int id) {int i, j;for (i = 0; i < list->length; i++) {if (list->students[i].id == id) //遍历顺序表，查找学号与传入的 id 相等的学生{for (j = i; j < list->length - 1; j++) {list->students[j] = list->students[j + 1];}list->length--;printf("ID 为 %d 的学生信息已删除！\n", id);return;}}printf("未找到 ID 为 %d 的学生！\n", id);
}// 根据学生 ID 查找学生信息
void findStudent(SeqList* list, int id) 
{int i;//遍历顺序表，查找学号与传入的 id 相等的学生for (i = 0; i < list->length; i++) {if (list->students[i].id == id) {printf("找到学生：ID: %d, 姓名: %s, 成绩: %.2f\n", list->students[i].id, list->students[i].name, list->students[i].score);return;}}printf("未找到 ID 为 %d 的学生！\n", id);
}// 显示所有学生信息
void displayStudents(SeqList* list) 
{if (list->length == 0) {printf("学生列表为空！\n");return;}int i;printf("所有学生信息如下：\n");for (i = 0; i < list->length; i++) {printf("ID: %d, 姓名: %s, 成绩: %.2f\n", list->students[i].id, list->students[i].name, list->students[i].score);}
}int main() {SeqList studentList;initList(&studentList);// 添加学生信息addStudent(&studentList, 1, "张三", 85.5);addStudent(&studentList, 2, "李四", 90.0);addStudent(&studentList, 3, "王五", 78.2);// 显示所有学生信息displayStudents(&studentList);// 查找学生信息findStudent(&studentList, 2);// 删除学生信息deleteStudent(&studentList, 3);// 再次显示所有学生信息displayStudents(&studentList);return 0;
}

三、链式存储结构

单链表：

结点结构：包含数据域data和指向下一结点的指针域next，通过头指针访问链表。
操作特点：
插入 / 删除：只需修改指针，无需移动元素，时间复杂度为 O(1)（找到位置后），但查找需遍历，时间复杂度为 O(n)。
创建方式：头插法（新结点插在头部）和尾插法（新结点接在尾部）。
代码示例：
①单链表的基本操作：

#include <stdio.h>
#include <stdlib.h>// 定义状态码
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0// 定义结点结构
typedef int ElemType;
typedef struct Node 
{ElemType data;          // 数据域struct Node* next;      // 指针域，指向下一个结点
} Node, * LinkList;       // LinkList为指向结点的指针类型// 1. 初始化链表（带头结点）
int InitList(LinkList* L) 
{*L = (Node*)malloc(sizeof(Node));  // 创建头结点if (*L == NULL) return ERROR;       // 内存分配失败(*L)->next = NULL;                  // 头结点初始时不指向任何结点return OK;
}// 2. 销毁链表（释放所有内存）
int DestroyList(LinkList* L) 
{Node* p, * q;p = (*L)->next;                     // 从第一个结点开始while (p != NULL) {q = p;p = p->next;free(q);                        // 释放当前结点内存}free(*L);                           // 释放头结点内存*L = NULL;                          // 头指针置空return OK;
}// 3. 清空链表（保留头结点，清空数据结点）
int ClearList(LinkList L) 
{Node* p, * q;p = L->next;while (p != NULL) {q = p;p = p->next;free(q);}L->next = NULL;                     // 头结点指向NULLreturn OK;
}// 4. 判断链表是否为空
int ListEmpty(LinkList L) 
{return (L->next == NULL) ? TRUE : FALSE;
}// 5. 获取链表长度
int ListLength(LinkList L) 
{int len = 0;Node* p = L->next;                  // 从第一个结点开始遍历while (p != NULL) {len++;p = p->next;}return len;
}// 6. 按位置插入结点（第i个位置，从1开始）
int ListInsert(LinkList L, int i, ElemType e) 
{if (i < 1) return ERROR;            // 位置不能小于1Node* p = L;                        // p指向头结点，用于定位前驱结点int j = 0;                          // 当前位置（头结点位置为0）while (p != NULL && j < i - 1) {    // 找到第i-1个结点p = p->next;j++;}if (p == NULL) return ERROR;         // i超过链表长度Node* s = (Node*)malloc(sizeof(Node));s->data = e;s->next = p->next;                  // 新结点指向原后继结点p->next = s;                        // 前驱结点指向新结点return OK;
}// 7. 按位置删除结点（删除第i个位置的结点）
int ListDelete(LinkList L, int i, ElemType* e) 
{if (i < 1) return ERROR;Node* p = L;                        // p指向头结点int j = 0;while (p != NULL && j < i - 1) {    // 找到第i-1个结点p = p->next;j++;}if (p == NULL || p->next == NULL) return ERROR; // 位置非法或链表为空Node* q = p->next;                  // q指向要删除的结点*e = q->data;                       // 返回删除的结点值p->next = q->next;                  // 前驱结点指向后继结点free(q);                            // 释放删除结点的内存return OK;
}// 8. 按值查找结点（返回第一个匹配的位置，从1开始）
int LocateElem(LinkList L, ElemType e) 
{int i = 1;                          // 位置从1开始Node* p = L->next;                  // p指向第一个结点while (p != NULL) {if (p->data == e) return i;      // 找到匹配值，返回位置p = p->next;i++;}return 0;                           // 未找到
}// 9. 按位置获取结点值
int GetElem(LinkList L, int i, ElemType* e) 
{if (i < 1) return ERROR;Node* p = L->next;                  // p指向第一个结点int j = 1;while (p != NULL && j < i) {        // 遍历到第i个结点p = p->next;j++;}if (p == NULL) return ERROR;        // 位置非法*e = p->data;                       // 返回结点值return OK;
}// 10. 打印链表
void PrintList(LinkList L) 
{Node* p = L->next;                  // 从第一个结点开始printf("LinkList: ");while (p != NULL) {printf("%d ", p->data);p = p->next;}printf("\n");
}// 主函数（测试用例）
int main() {LinkList L;ElemType e;// 1. 初始化链表if (InitList(&L) == OK) {printf("链表初始化成功\n");}else {printf("链表初始化失败\n");return ERROR;}// 2. 插入结点（在第1、2、3位置插入10、20、30）ListInsert(L, 1, 10);ListInsert(L, 2, 20);ListInsert(L, 3, 30);PrintList(L);  // 输出：LinkList: 10 20 30// 3. 按位置插入（在第2位置插入15）ListInsert(L, 2, 15);PrintList(L);  // 输出：LinkList: 10 15 20 30// 4. 按值查找（查找20的位置）int pos = LocateElem(L, 20);printf("值20的位置是：%d\n", pos);  // 输出：2// 5. 按位置删除（删除第3个结点）ListDelete(L, 3, &e);printf("删除的值是：%d\n", e);      // 输出：20PrintList(L);  // 输出：LinkList: 10 15 30// 6. 获取第2个结点的值GetElem(L, 2, &e);printf("第2个结点的值是：%d\n", e);  // 输出：15// 7. 清空链表ClearList(L);printf("链表已清空，当前长度：%d\n", ListLength(L));  // 输出：0// 8. 销毁链表DestroyList(&L);if (L == NULL) {printf("链表销毁成功\n");}return 0;
}

②应用实例：学生成绩管理系统

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义学生结构体
typedef struct Student {char name[50];int score;struct Student* next;
} Student;// 创建新学生节点
Student* createStudent(const char* name, int score) {Student* newStudent = (Student*)malloc(sizeof(Student));if (newStudent == NULL) {printf("内存分配失败！\n");return NULL;}// 使用 strcpy_s 替代 strcpyif (strcpy_s(newStudent->name, sizeof(newStudent->name), name) != 0) {printf("字符串复制失败！\n");free(newStudent);return NULL;}newStudent->score = score;newStudent->next = NULL;return newStudent;
}// 添加学生信息到链表
void addStudent(Student** head, const char* name, int score) {Student* newStudent = createStudent(name, score);if (*head == NULL) {*head = newStudent;}else {Student* temp = *head;while (temp->next != NULL) {temp = temp->next;}temp->next = newStudent;}
}// 删除指定姓名的学生信息
void deleteStudent(Student** head, const char* name) {Student* current = *head;Student* previous = NULL;while (current != NULL && strcmp(current->name, name) != 0) {previous = current;current = current->next;}if (current == NULL) {printf("未找到该学生！\n");return;}if (previous == NULL) {*head = current->next;}else {previous->next = current->next;}free(current);printf("已删除学生：%s\n", name);
}// 查找指定姓名的学生成绩
void findStudent(Student* head, const char* name) {Student* current = head;while (current != NULL) {if (strcmp(current->name, name) == 0) {printf("学生 %s 的成绩是：%d\n", current->name, current->score);return;}current = current->next;}printf("未找到该学生！\n");
}// 显示所有学生信息
void displayAllStudents(Student* head) {Student* current = head;if (current == NULL) {printf("暂无学生信息！\n");return;}printf("所有学生信息如下：\n");while (current != NULL) {printf("姓名：%s，成绩：%d\n", current->name, current->score);current = current->next;}
}// 释放链表内存
void freeList(Student** head) {Student* current = *head;Student* next;while (current != NULL) {next = current->next;free(current);current = next;}*head = NULL;
}int main() {Student* head = NULL;// 添加学生信息addStudent(&head, "张三", 85);addStudent(&head, "李四", 90);addStudent(&head, "王五", 78);// 显示所有学生信息displayAllStudents(head);// 查找学生成绩findStudent(head, "李四");// 删除学生信息deleteStudent(&head, "王五");// 再次显示所有学生信息displayAllStudents(head);// 释放链表内存freeList(&head);return 0;
}

循环链表：尾结点指针指向头结点，形成环，便于从任意结点遍历全表。

代码示例：

①基本操作

#include <stdio.h>
#include <stdlib.h>// 定义循环链表节点结构
typedef struct Node {int data;struct Node* next;
} Node;// 创建新节点
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {printf("内存分配失败\n");return NULL;}newNode->data = data;newNode->next = NULL;return newNode;
}// 初始化循环链表
Node* initCircularList() {return NULL;
}// 在链表头部插入节点
Node* insertAtHead(Node* head, int data) 
{Node* newNode = createNode(data);if (head == NULL) //若链表为空，新节点的 next 指向自己，形成循环{newNode->next = newNode;return newNode;}Node* temp = head;while (temp->next != head) //若链表不为空{temp = temp->next; //找到尾节点（遍历直到 temp->next == head）}temp->next = newNode;//尾节点的 next 指向新节点newNode->next = head;//新节点的 next 指向原头节点，形成循环return newNode;
}// 在链表尾部插入节点
Node* insertAtTail(Node* head, int data) //类似在链表头部插入节点
{Node* newNode = createNode(data);if (head == NULL) {newNode->next = newNode;return newNode;}Node* temp = head;while (temp->next != head) {temp = temp->next;}temp->next = newNode;newNode->next = head;return head;
}// 删除指定值的节点
Node* deleteNode(Node* head, int key) 
{if (head == NULL) return NULL;  // 空链表直接返回Node* current = head;Node* prev = NULL;// 情况1：删除头节点if (current->data == key) {if (current->next == head) {  // 链表只有一个节点free(current);return NULL;}// 找到尾节点（用于更新尾节点的next）Node* temp = head;while (temp->next != head) {temp = temp->next;}Node* newHead = current->next;  // 新头节点是原头节点的下一个节点temp->next = newHead;  // 尾节点的next指向新头节点free(current);  // 释放原头节点内存return newHead;  // 返回新头节点}// 情况2：删除非头节点do {prev = current;current = current->next;if (current->data == key){prev->next = current->next;  // 前驱节点跳过当前节点free(current);  // 释放内存return head;  // 头节点不变，返回原头节点}} while (current != head);  // 遍历直到回到头节点（避免死循环）printf("未找到要删除的节点\n");return head;
}// 查找指定值的节点
Node* searchNode(Node* head, int key) 
{if (head == NULL) return NULL;Node* current = head;do {if (current->data == key) {return current;  // 找到节点，返回指针}current = current->next;} while (current != head);  // 遍历整个链表return NULL;  // 未找到
}// 打印循环链表
void printList(Node* head) 
{if (head == NULL) {printf("链表为空\n");return;}Node* current = head;do {printf("%d ", current->data);current = current->next;} while (current != head);  // 回到头节点时停止printf("\n");
}// 释放循环链表的内存
void freeList(Node* head) 
{if (head == NULL) return;Node* current = head;Node* next;do {next = current->next;  // 保存下一个节点指针free(current);         // 释放当前节点内存current = next;        // 移动到下一个节点} while (current != head);  // 直到回到头节点（此时头节点已被释放，循环终止）
}int main() {Node* head = initCircularList();// 插入节点head = insertAtTail(head, 1);head = insertAtTail(head, 2);head = insertAtTail(head, 3);head = insertAtHead(head, 0);printf("插入节点后的链表: ");printList(head);// 查找节点Node* found = searchNode(head, 2);if (found != NULL) {printf("找到节点: %d\n", found->data);}else {printf("未找到节点\n");}// 删除节点head = deleteNode(head, 2);printf("删除节点后的链表: ");printList(head);// 释放链表内存freeList(head);return 0;
}

②约瑟夫问题

/*约瑟夫环问题。约瑟夫环问题描述的是：
有 n 个人围成一圈，从第 k 个人开始报数，
报到第 m 的人出列，然后从出列的下一个人重新开始报数，
直到所有人都出列为止。我们可以使用循环链表来模拟这个过程。*/
#include <stdio.h>
#include <stdlib.h>// 定义循环链表节点结构
typedef struct Node {int data;struct Node* next;
} Node;// 创建新节点
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {printf("内存分配失败\n");return NULL;}newNode->data = data;newNode->next = NULL;return newNode;
}// 创建循环链表
Node* createCircularList(int n) {if (n <= 0) return NULL;Node* head = createNode(1);Node* current = head;for (int i = 2; i <= n; i++) {current->next = createNode(i);current = current->next;}// 使链表成为循环链表current->next = head;return head;
}// 解决约瑟夫环问题
void josephusProblem(int n, int k, int m) 
{if (n <= 0 || k <= 0 || m <= 0) return;Node* head = createCircularList(n);Node* prev = NULL;Node* current = head;// 移动到第 k 个人for (int i = 1; i < k; i++) {prev = current;current = current->next;}printf("出列顺序为：");while (current->next != current) {// 找到第 m 个人for (int i = 1; i < m; i++) {prev = current;current = current->next;}printf("%d ", current->data);// 删除当前节点prev->next = current->next;Node* temp = current;current = current->next;free(temp);}printf("%d\n", current->data);free(current);
}int main() {int n = 10; // 总人数int k = 1;  // 从第 k 个人开始报数int m = 3;  // 报到第 m 的人出列josephusProblem(n, k, m);return 0;
}

双向链表：每个结点含前驱和后继指针，支持双向遍历，插入删除需修改两个指针。

示例代码：

①基本操作

//实现双向链表的基本操作（插入、删除、查找）
#include <stdio.h>
#include <stdlib.h>// 定义双向链表节点结构
typedef struct Node 
{int data;                // 存储节点数据struct Node* prev;       // 指向前驱节点的指针struct Node* next;       // 指向后继节点的指针
} Node;// 创建新节点
Node* createNode(int data) 
{Node* newNode = (Node*)malloc(sizeof(Node));  // 分配节点内存if (newNode == NULL) {printf("内存分配失败\n");return NULL;  // 分配失败时返回NULL}newNode->data = data;          // 初始化数据域newNode->prev = NULL;          // 新节点初始时无前驱和后继newNode->next = NULL;return newNode;                // 返回新节点指针
}// 在链表头部插入节点
Node* insertAtHead(Node* head, int data) 
{Node* newNode = createNode(data);  // 创建新节点if (head == NULL) {                // 空链表情况：新节点成为头节点return newNode;}// 双向链表头插逻辑：newNode->next = head;              // 新节点的后继指向原头节点head->prev = newNode;              // 原头节点的前驱指向新节点return newNode;                    // 新节点成为新的头节点
}// 在链表尾部插入节点
Node* insertAtTail(Node* head, int data) 
{Node* newNode = createNode(data);  // 创建新节点if (head == NULL) {                // 空链表情况：新节点成为头节点return newNode;}Node* temp = head;                 // 从头部开始遍历// 找到链表的最后一个节点（next为NULL的节点）while (temp->next != NULL) {temp = temp->next;}// 双向链表尾插逻辑：temp->next = newNode;              // 原尾节点的后继指向新节点newNode->prev = temp;              // 新节点的前驱指向原尾节点return head;                       // 头节点不变，返回原头节点
}// 删除指定值的节点
Node* deleteNode(Node* head, int key) 
{if (head == NULL) return NULL;     // 空链表直接返回Node* current = head;              // 从头部开始查找目标节点// 遍历链表，找到值为key的节点while (current != NULL && current->data != key) {current = current->next;}if (current == NULL) {             // 未找到目标节点printf("未找到要删除的节点\n");return head;}// 处理三种删除情况：// 情况1：删除头节点（current->prev == NULL）if (current->prev == NULL) {head = current->next;          // 新头节点为原头节点的后继if (head != NULL) {            // 若新头节点存在，更新其前驱为NULLhead->prev = NULL;}}// 情况2：删除中间节点或尾节点（非头节点）else {current->prev->next = current->next;  // 前驱节点的后继指向目标节点的后继}// 情况3：删除尾节点或中间节点（处理后继节点的前驱）if (current->next != NULL) {current->next->prev = current->prev;  // 后继节点的前驱指向目标节点的前驱}free(current);                       // 释放目标节点内存return head;                         // 返回更新后的头节点
}// 查找指定值的节点
Node* searchNode(Node* head, int key) {Node* current = head;              // 从头部开始遍历while (current != NULL) {if (current->data == key) {     // 找到匹配节点，返回其指针return current;}current = current->next;        // 移动到下一个节点}return NULL;                        // 未找到时返回NULL
}// 打印双向链表
void printList(Node* head) 
{Node* current = head;              // 从头部开始遍历while (current != NULL) {printf("%d ", current->data);  // 打印当前节点数据current = current->next;        // 移动到下一个节点}printf("\n");
}// 释放双向链表的内存
void freeList(Node* head) 
{Node* current = head;              // 从头部开始Node* next;                         // 临时保存下一个节点的指针while (current != NULL) {next = current->next;           // 保存下一个节点，避免丢失free(current);                  // 释放当前节点内存current = next;                 // 移动到下一个节点}
}int main() {Node* head = NULL;// 插入节点head = insertAtTail(head, 1);head = insertAtTail(head, 2);head = insertAtTail(head, 3);head = insertAtHead(head, 0);printf("插入节点后的链表: ");printList(head);// 查找节点Node* found = searchNode(head, 2);if (found != NULL) {printf("找到节点: %d\n", found->data);}else {printf("未找到节点\n");}// 删除节点head = deleteNode(head, 2);printf("删除节点后的链表: ");printList(head);// 释放链表内存freeList(head);return 0;
}

②应用实例：图书管理系统

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义图书结构体（双向链表节点）
typedef struct Book {char title[100];       // 书名（最大长度100）char author[100];      // 作者（最大长度100）int id;                // 图书ID（唯一标识）struct Book* prev;     // 指向前一个节点的指针（双向链表特性）struct Book* next;     // 指向后一个节点的指针（双向链表特性）
} Book;// 创建新的图书节点
Book* createBook(int id, const char* title, const char* author) {Book* newBook = (Book*)malloc(sizeof(Book));  // 分配节点内存if (newBook == NULL) {printf("内存分配失败！\n");return NULL;  // 分配失败时返回NULL}newBook->id = id;                              // 初始化IDstrcpy_s(newBook->title, title);               // 复制书名（安全版本的strcpy）strcpy_s(newBook->author, author);             // 复制作者名newBook->prev = NULL;                          // 新节点初始时无前驱和后继newBook->next = NULL;return newBook;                                // 返回新节点指针
}// 在链表尾部添加图书
void addBook(Book** head, int id, const char* title, const char* author) 
{Book* newBook = createBook(id, title, author);  // 创建新节点if (*head == NULL) {                            // 空链表情况：新节点成为头节点*head = newBook;return;}Book* current = *head;                          // 从头部开始遍历// 找到链表的最后一个节点（next为NULL的节点）while (current->next != NULL) {current = current->next;}// 连接新节点到链表尾部：current->next = newBook;       // 原尾节点的next指向新节点newBook->prev = current;       // 新节点的prev指向原尾节点（双向链表关键步骤）
}// 根据图书 ID 删除图书
void deleteBook(Book** head, int id) {if (*head == NULL) {                            // 空链表处理printf("图书列表为空，无法删除！\n");return;}Book* current = *head;                          // 从头部开始查找目标节点// 遍历链表，找到ID匹配的节点while (current != NULL && current->id != id) {current = current->next;}if (current == NULL) {                           // 未找到目标节点printf("未找到 ID 为 %d 的图书！\n", id);return;}// 调整前后节点的指针：if (current->prev != NULL) {                    // 目标节点不是头节点current->prev->next = current->next;         // 前驱节点的next指向后继节点}else {                                        // 目标节点是头节点，更新头指针*head = current->next;}if (current->next != NULL) {                    // 目标节点不是尾节点current->next->prev = current->prev;         // 后继节点的prev指向前驱节点}free(current);                                   // 释放目标节点内存printf("ID 为 %d 的图书已删除！\n", id);
}// 根据图书 ID 查找图书
Book* findBook(Book* head, int id) {Book* current = head;                            // 从头部开始遍历while (current != NULL) {if (current->id == id) {                     // 找到匹配ID的节点return current;                          // 返回节点指针}current = current->next;                     // 移动到下一个节点}return NULL;                                     // 未找到时返回NULL
}// 显示所有图书信息
void displayBooks(Book* head) {if (head == NULL) {                              // 空链表处理printf("图书列表为空！\n");return;}Book* current = head;                            // 从头部开始遍历printf("所有图书信息如下：\n");while (current != NULL) {// 打印当前节点的书名、作者和IDprintf("ID: %d, 书名: %s, 作者: %s\n", current->id, current->title, current->author);current = current->next;                     // 移动到下一个节点}
}//使用双向链表实现的图书管理系统
// 释放链表内存
void freeBooks(Book** head) {Book* current = *head;                           // 从头部开始Book* next;                                      // 临时保存下一个节点的指针while (current != NULL) {next = current->next;                        // 保存下一个节点，避免丢失free(current);                               // 释放当前节点内存current = next;                              // 移动到下一个节点}*head = NULL;                                    // 最后将头指针置为NULL，避免野指针
}int main() {Book* library = NULL;// 添加图书addBook(&library, 1, "C 语言入门", "张三");addBook(&library, 2, "数据结构与算法", "李四");addBook(&library, 3, "操作系统原理", "王五");// 显示所有图书信息displayBooks(library);// 查找图书Book* foundBook = findBook(library, 2);if (foundBook != NULL) {printf("找到图书：ID: %d, 书名: %s, 作者: %s\n", foundBook->id, foundBook->title, foundBook->author);}else {printf("未找到 ID 为 2 的图书！\n");}// 删除图书deleteBook(&library, 3);// 再次显示所有图书信息displayBooks(library);// 释放链表内存freeBooks(&library);return 0;
}

静态链表：用数组模拟指针，通过游标cur表示后继位置，适合无指针语言，插入删除无需移动元素，但失去随机访问特性。

代码示例：

①基本操作

//实现双向链表的基本操作（插入、删除、查找）
#include <stdio.h>
#include <stdlib.h>// 定义双向链表节点结构
typedef struct Node
{int data;                // 存储节点数据struct Node* prev;       // 指向前驱节点的指针struct Node* next;       // 指向后继节点的指针
} Node;// 创建新节点
Node* createNode(int data)
{Node* newNode = (Node*)malloc(sizeof(Node));  // 分配节点内存if (newNode == NULL){printf("内存分配失败\n");return NULL;  // 分配失败时返回NULL}newNode->data = data;          // 初始化数据域newNode->prev = NULL;          // 新节点初始时无前驱和后继newNode->next = NULL;return newNode;                // 返回新节点指针
}// 在链表头部插入节点
Node* insertAtHead(Node* head, int data)
{Node* newNode = createNode(data);  // 创建新节点if (head == NULL) {                // 空链表情况：新节点成为头节点return newNode;}// 双向链表头插逻辑：newNode->next = head;              // 新节点的后继指向原头节点head->prev = newNode;              // 原头节点的前驱指向新节点return newNode;                    // 新节点成为新的头节点
}// 在链表尾部插入节点
Node* insertAtTail(Node* head, int data)
{Node* newNode = createNode(data);  // 创建新节点if (head == NULL) {                // 空链表情况：新节点成为头节点return newNode;}Node* temp = head;                 // 从头部开始遍历// 找到链表的最后一个节点（next为NULL的节点）while (temp->next != NULL){temp = temp->next;}// 双向链表尾插逻辑：temp->next = newNode;              // 原尾节点的后继指向新节点newNode->prev = temp;              // 新节点的前驱指向原尾节点return head;                       // 头节点不变，返回原头节点
}// 删除指定值的节点
Node* deleteNode(Node* head, int key)
{if (head == NULL) return NULL;     // 空链表直接返回Node* current = head;              // 从头部开始查找目标节点// 遍历链表，找到值为key的节点while (current != NULL && current->data != key){current = current->next;}if (current == NULL) {             // 未找到目标节点printf("未找到要删除的节点\n");return head;}// 处理三种删除情况：// 情况1：删除头节点（current->prev == NULL）if (current->prev == NULL){head = current->next;          // 新头节点为原头节点的后继if (head != NULL){            // 若新头节点存在，更新其前驱为NULLhead->prev = NULL;}}// 情况2：删除中间节点或尾节点（非头节点）else {current->prev->next = current->next;  // 前驱节点的后继指向目标节点的后继}// 情况3：删除尾节点或中间节点（处理后继节点的前驱）if (current->next != NULL){current->next->prev = current->prev;  // 后继节点的前驱指向目标节点的前驱}free(current);                       // 释放目标节点内存return head;                         // 返回更新后的头节点
}// 查找指定值的节点
Node* searchNode(Node* head, int key) {Node* current = head;              // 从头部开始遍历while (current != NULL) {if (current->data == key) {     // 找到匹配节点，返回其指针return current;}current = current->next;        // 移动到下一个节点}return NULL;                        // 未找到时返回NULL
}// 打印双向链表
void printList(Node* head)
{Node* current = head;              // 从头部开始遍历while (current != NULL){printf("%d ", current->data);  // 打印当前节点数据current = current->next;        // 移动到下一个节点}printf("\n");
}// 释放双向链表的内存
void freeList(Node* head)
{Node* current = head;              // 从头部开始Node* next;                         // 临时保存下一个节点的指针while (current != NULL){next = current->next;           // 保存下一个节点，避免丢失free(current);                  // 释放当前节点内存current = next;                 // 移动到下一个节点}
}int main() {Node* head = NULL;// 插入节点head = insertAtTail(head, 1);head = insertAtTail(head, 2);head = insertAtTail(head, 3);head = insertAtHead(head, 0);printf("插入节点后的链表: ");printList(head);// 查找节点Node* found = searchNode(head, 2);if (found != NULL) {printf("找到节点: %d\n", found->data);}else {printf("未找到节点\n");}// 删除节点head = deleteNode(head, 2);printf("删除节点后的链表: ");printList(head);// 释放链表内存freeList(head);return 0;
}

②应用实例

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_SIZE 100       // 静态链表最大节点数（可根据需求调整）
#define NULL_INDEX -1     // 表示空节点（无下一个节点）
#define NAME_MAX_LEN 20   // 姓名最大长度// 定义节点结构（存储学生信息）
typedef struct {int id;           // 学生学号（唯一标识）char name[NAME_MAX_LEN];  // 学生姓名int next;         // 下一个节点的数组索引（静态指针）
} Node;// 静态链表结构体（包含节点数组、头节点索引、空闲链表头）
typedef struct {Node nodes[MAX_SIZE];  // 节点数组int head;              // 头节点索引（初始为 NULL_INDEX）int freeList;          // 空闲节点链表头索引
} StaticLinkedList;// 函数声明
void initStaticList(StaticLinkedList* list);
int allocateNode(StaticLinkedList* list);
void freeNode(StaticLinkedList* list, int index);
int insertAtHead(StaticLinkedList* list, int id, const char* name);
int insertAtTail(StaticLinkedList* list, int id, const char* name);
int deleteByID(StaticLinkedList* list, int targetID);
int searchByID(StaticLinkedList* list, int targetID);
void updateNameByID(StaticLinkedList* list, int targetID, const char* newName);
void traverseList(StaticLinkedList* list);
void clearList(StaticLinkedList* list);
void printMenu();
int getValidInput(int min, int max);// 初始化静态链表（包括空闲链表）
void initStaticList(StaticLinkedList* list) {list->head = NULL_INDEX;list->freeList = 0;  // 空闲链表头指向索引0for (int i = 0; i < MAX_SIZE - 1; i++) {list->nodes[i].next = i + 1;  // 空闲节点依次连接list->nodes[i].id = 0;       // 初始学号为0（无效值）strcpy_s(list->nodes[i].name, "");  // 初始姓名为空}list->nodes[MAX_SIZE - 1].next = NULL_INDEX;  // 最后一个节点的next为NULL
}// 申请空闲节点（从空闲链表获取）
int allocateNode(StaticLinkedList* list) {if (list->freeList == NULL_INDEX) {printf("错误：学生数量达到上限（%d人）！\n", MAX_SIZE);return NULL_INDEX;}int newNodeIndex = list->freeList;list->freeList = list->nodes[newNodeIndex].next;  // 更新空闲链表头return newNodeIndex;
}// 释放节点到空闲链表
void freeNode(StaticLinkedList* list, int index) {if (index < 0 || index >= MAX_SIZE) return;list->nodes[index].id = 0;          // 重置学号为无效值strcpy_s(list->nodes[index].name, ""); // 清空姓名list->nodes[index].next = list->freeList;  // 新释放节点指向原空闲头list->freeList = index;              // 空闲头更新为当前节点
}// 头插法插入学生
int insertAtHead(StaticLinkedList* list, int id, const char* name) {int newNodeIndex = allocateNode(list);if (newNodeIndex == NULL_INDEX) return 0;list->nodes[newNodeIndex].id = id;strncpy_s(list->nodes[newNodeIndex].name, name, NAME_MAX_LEN);  // 安全复制姓名list->nodes[newNodeIndex].next = list->head;list->head = newNodeIndex;printf("成功在头部插入学生（学号：%d）\n", id);return 1;
}// 尾插法插入学生
int insertAtTail(StaticLinkedList* list, int id, const char* name) {int newNodeIndex = allocateNode(list);if (newNodeIndex == NULL_INDEX) return 0;list->nodes[newNodeIndex].id = id;strncpy_s(list->nodes[newNodeIndex].name, name, NAME_MAX_LEN);if (list->head == NULL_INDEX) {  // 空链表直接作为头节点list->head = newNodeIndex;}else {int current = list->head;// 找到尾节点（next为NULL_INDEX的节点）while (list->nodes[current].next != NULL_INDEX) {current = list->nodes[current].next;}list->nodes[current].next = newNodeIndex;}list->nodes[newNodeIndex].next = NULL_INDEX;printf("成功在尾部插入学生（学号：%d）\n", id);return 1;
}// 按学号删除学生
int deleteByID(StaticLinkedList* list, int targetID) {int current = list->head;int prev = NULL_INDEX;while (current != NULL_INDEX && list->nodes[current].id != targetID) {prev = current;current = list->nodes[current].next;}if (current == NULL_INDEX) {printf("错误：未找到学号为%d的学生！\n", targetID);return 0;}// 更新前驱节点的nextif (prev == NULL_INDEX) {  // 删除头节点list->head = list->nodes[current].next;}else {list->nodes[prev].next = list->nodes[current].next;}freeNode(list, current);  // 释放节点到空闲链表printf("成功删除学号为%d的学生！\n", targetID);return 1;
}// 按学号查找学生（返回节点索引，未找到返回NULL_INDEX）
int searchByID(StaticLinkedList* list, int targetID) {int current = list->head;while (current != NULL_INDEX) {if (list->nodes[current].id == targetID) {return current;}current = list->nodes[current].next;}return NULL_INDEX;
}// 按学号更新学生姓名
void updateNameByID(StaticLinkedList* list, int targetID, const char* newName) {int index = searchByID(list, targetID);if (index == NULL_INDEX) {printf("错误：未找到学号为%d的学生！\n", targetID);return;}strncpy_s(list->nodes[index].name, newName, NAME_MAX_LEN);printf("成功更新学号为%d的学生姓名为：%s\n", targetID, newName);
}// 遍历并打印所有学生信息
void traverseList(StaticLinkedList* list) {int current = list->head;if (current == NULL_INDEX) {printf("提示：学生列表为空！\n");return;}printf("\n------------------- 学生信息列表 -------------------\n");printf("学号\t\t姓名\n");printf("--------------------------------------------\n");while (current != NULL_INDEX) {printf("%-12d%s\n", list->nodes[current].id, list->nodes[current].name);current = list->nodes[current].next;}printf("------------------------------------------------\n\n");
}// 清空链表（释放所有节点到空闲链表）
void clearList(StaticLinkedList* list) {int current = list->head;int nextNode;while (current != NULL_INDEX) {nextNode = list->nodes[current].next;freeNode(list, current);current = nextNode;}list->head = NULL_INDEX;printf("成功清空学生列表！\n");
}// 打印操作菜单
void printMenu() {printf("================== 学生信息管理系统 ==================\n");printf("1. 头部插入学生（头插法）\n");printf("2. 尾部插入学生（尾插法）\n");printf("3. 按学号删除学生\n");printf("4. 按学号查找学生\n");printf("5. 按学号更新学生姓名\n");printf("6. 显示所有学生信息\n");printf("7. 清空学生列表\n");printf("0. 退出系统\n");printf("请选择操作（0-7）：");
}// 获取有效输入（限制范围[min, max]）
int getValidInput(int min, int max) {int choice;while (scanf_s("%d", &choice) != 1 || choice < min || choice > max) {printf("输入无效！请重新选择（%d-%d）：", min, max);while (getchar() != '\n');  // 清空输入缓冲区}while (getchar() != '\n');  // 消耗剩余换行符return choice;
}// 主函数（菜单驱动界面）
int main() {StaticLinkedList studentList;initStaticList(&studentList);int choice;do {printMenu();choice = getValidInput(0, 7);switch (choice) {case 1: {  // 头插法插入int id;char name[NAME_MAX_LEN];printf("请输入学生学号：");scanf_s("%d", &id);printf("请输入学生姓名：");scanf_s("%s", name);insertAtHead(&studentList, id, name);break;}case 2: {  // 尾插法插入int id;char name[NAME_MAX_LEN];printf("请输入学生学号：");scanf_s("%d", &id);printf("请输入学生姓名：");scanf_s("%s", name);insertAtTail(&studentList, id, name);break;}case 3: {  // 删除学生int targetID;printf("请输入要删除的学生学号：");scanf_s("%d", &targetID);deleteByID(&studentList, targetID);break;}case 4: {  // 查找学生int targetID = searchByID(&studentList, getValidInput(1, MAX_SIZE * 10));  // 示例输入处理if (targetID != NULL_INDEX) {printf("找到学生：学号 %d，姓名 %s\n",studentList.nodes[targetID].id,studentList.nodes[targetID].name);}break;}case 5: {  // 更新姓名int targetID;char newName[NAME_MAX_LEN];printf("请输入要更新的学生学号：");scanf_s("%d", &targetID);printf("请输入新姓名：");scanf_s("%s", newName);updateNameByID(&studentList, targetID, newName);break;}case 6: {  // 显示所有学生traverseList(&studentList);break;}case 7: {  // 清空列表clearList(&studentList);break;}case 0: {  // 退出printf("感谢使用！系统已退出。\n");break;}}} while (choice != 0);return 0;
}