一、线性表的定义与抽象数据类型
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 0
typedef 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];//将指定位置的元素值赋给 *e
for (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; // 头结点指向NULL
return 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; // 位置不能小于1
Node* 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); // 输出：20
PrintList(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 替代 strcpy
if (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)
{ // 若新头节点存在，更新其前驱为NULL
head->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; // 初始化ID
strcpy_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) {
// 打印当前节点的书名、作者和ID
printf("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)
{ // 若新头节点存在，更新其前驱为NULL
head->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; // 空闲链表头指向索引0
for (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;
}
// 更新前驱节点的next
if (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;
}
四、存储结构对比与选择
顺序存储：适合频繁存取、元素变化少的场景（如固定长度的表格数据）。
链式存储：适合频繁插入删除、长度不确定的场景（如动态增长的链表）。
时间复杂度：顺序表存取 O(1)，插入删除 O(n)；链表存取 O(n)，插入删除 O(1)（定位后）。
五、核心思想与应用
线性表是基础数据结构，两种存储结构各有优劣，需根据实际需求（如操作频率、数据规模）选择。
链表通过指针灵活管理内存，避免顺序表的空间固定问题；静态链表则是指针的替代方案，体现了数据结构设计的灵活性。