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

数据结构(二) 线性表

news 2025/5/20 5:39:54

一. 线性表

        1.定义

                线性表是由n(n>=0)个具有相同数据类型的数据元素构成的有限序列。其中，元素之间通过顺序关系排列，每个元素有且只有一个直接前驱和一个直接后继(除首尾元素外)

二.线性表的顺序表示(顺序表)

        1.存储方式

                使用连续的内存空间(数组)存储元素，逻辑相邻的元素在物理位置上也相邻

        2.特点

                优点：支持随机访问，时间复杂度为O(1)

                缺点：进行插入/删除操作时，需要移动元素，平均时间复杂度为O(n)

        3.动态扩容

                当数组空间不足时，可以重新分配更大的空间，并复制数据

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAXSIZE 100  // 顺序表初始最大容量// 顺序表结构体定义
typedef struct SeqList{int *data;       // 指向动态分配数组的指针int length;      // 当前表长（有效元素个数）int capacity;    // 当前分配的存储容量
}SeqList;/* 初始化顺序表* 参数：L - 指向顺序表结构的指针* 流程：* 1. 申请MAXSIZE大小的连续内存空间* 2. 初始化长度为0* 3. 设置当前容量为MAXSIZE*/
void InitList(SeqList *L){L->data = (int *)malloc(sizeof(int) * MAXSIZE);  // 分配初始内存L->length = 0;               // 初始空表L->capacity = MAXSIZE;       // 记录最大容量
}/* 插入元素函数* 参数：L - 顺序表指针，index - 插入位置（从1开始），value - 插入值* 返回值：bool - 是否插入成功* 流程：* 1. 位置有效性检查（1<=index<=length+1）* 2. 空间不足时自动扩容（2倍扩容策略）* 3. 元素后移操作（从最后一个元素开始到目标位置）* 4. 插入新元素并更新表长*/
bool InsertList(SeqList *L, int index, int value){// 位置合法性校验（包括空表情况下的校验）if(index < 1 || index > L->length + 1){return false;  // 插入位置非法}// 空间扩容机制（当表满时自动扩容）if(L->length >= L->capacity){// 尝试扩容为当前容量的2倍int *NewData = (int *)realloc(L->data, sizeof(int) * L->capacity * 2);if(!NewData){  // 内存分配失败return false;} L->data = NewData;     // 更新数据指针L->capacity *= 2;      // 更新容量记录}// 元素后移操作（从后往前移动防止覆盖）for(int i = L->length; i >= index; i--){L->data[i] = L->data[i-1];  // 将index-1位置后的元素依次后移}// 插入新元素并更新表长L->data[index-1] = value;  // 数组下标从0开始，故减1L->length++;               // 表长增加return true;
}/* 打印顺序表* 参数：L - 顺序表指针* 流程：* 1. 遍历有效元素* 2. 空格分隔元素* 3. 末尾换行*/
void PrintList(SeqList *L){for(int i = 0; i < L->length; i++){printf("%d ", L->data[i]);  // 逐个输出元素}printf("\n");  // 换行保持输出格式
}/* 主函数测试流程* 测试策略：* 1. 初始化测试* 2. 正常插入（头部、中间、尾部）* 3. 边界测试（尾部追加）* 4. 异常测试（非法位置插入）*/
int main() {SeqList L;InitList(&L);// 初始状态验证printf("初始顺序表：");PrintList(&L);  // 应输出 []// 正常插入测试（验证不同位置的插入逻辑）InsertList(&L, 1, 10);  // 首部插入（空表插入）InsertList(&L, 2, 30);  // 尾部插入（容量足够时）InsertList(&L, 2, 20);  // 中间插入（触发元素移动）printf("插入3个元素后：");PrintList(&L);  // 应输出 [10 20 30]// 边界测试（验证最大容量的插入）InsertList(&L, 4, 40);  // 尾部追加（验证边界条件）printf("尾部追加后：");PrintList(&L);  // 应输出 [10 20 30 40]// 异常测试（验证错误处理能力）bool result = InsertList(&L, 6, 50);  // 非法位置（当前长度4，只能插入到位置5）printf("非法插入结果：%s\n", result ? "成功" : "失败");  // 应输出失败return 0;
}

 三.线性表的链式表示和实现(链表)

        1.存储方式

               通过节点(包含数据域和指针域)动态分配内存，逻辑相邻的元素在物理位置上不一定相邻

        2.类型

                单链表：     每个节点指向下一个结点

                双链表：     节点包含前驱和后继指针

                循环链表：  尾节点指向头节点

        3.特点

                优点： 进行插入/删除操作时高效，时间复杂度为O(1)

                缺点： 无法随机访问节点值，必须从头遍历，时间复杂度为O(n)  

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>/* 链表节点结构体* Data: 节点存储的数据（整型）* Next: 指向下一个节点的指针 */
typedef struct Node{int Data;struct Node *Next;
}Node;/* 初始化链表头节点* 返回值：已分配内存的头节点指针* 注意：头节点不存储有效数据，仅作为链表入口 */
Node* InitList(){Node* Head = (Node*)malloc(sizeof(Node));Head->Next = NULL;return Head;
}/* 头插法插入节点* Head: 链表头节点指针* Value: 要插入的整型数据* 流程：1.创建新节点 2.调整指针指向 */
void InsertHead(Node* Head, int Value){Node* NewNode = (Node*)malloc(sizeof(Node));NewNode->Data = Value;NewNode->Next = Head->Next;Head->Next = NewNode;
}/* 尾插法插入节点* Head: 链表头节点指针* Value: 要插入的整型数据* 流程：1.遍历到最后一个节点 2.在末尾插入新节点 */
void InsertTail(Node* Head, int Value){Node* Current = Head;while(Current->Next != NULL){Current = Current->Next;}Node* NewNode = (Node*)malloc(sizeof(Node));NewNode->Data = Value;NewNode->Next = NULL;Current->Next = NewNode;
}/* 删除指定值的节点* Head: 链表头节点指针* Value: 要删除的整型数据* 返回值：true删除成功，false未找到数据* 流程：双指针法遍历，找到后调整指针并释放内存 */
bool DeleteNode(Node* Head, int Value){Node* Previous = Head;Node* Current = Head->Next;while(Current!=NULL){if(Current->Data == Value){Previous->Next = Current->Next;free(Current);return true;}Previous = Current;Current = Current->Next;}return false;
}/* 修改指定位置节点的值* Head: 链表头节点指针* pos: 要修改的位置（从0开始计数）* NewValue: 新的整型数据值* 注意：如果位置超出链表长度，不会修改任何节点 */
void ModifyNode(Node* Head, int pos, int NewValue){Node* Current = Head->Next;int count = 0;while(Current!=NULL && count<pos){Current = Current->Next;count++;}if(Current!=NULL){Current->Data = NewValue;}
}/* 搜索节点位置* Head: 链表头节点指针* Value: 要查找的整型数据* 返回值：找到返回位置索引（从0开始），未找到返回-1 */
int SearchNode(Node* Head, int Value){Node* Current = Head->Next;int pos = 0;while(Current!=NULL){if(Current->Data == Value){return pos;}Current = Current->Next;pos++;}return -1;
}/* 打印整个链表* Head: 链表头节点指针* 输出格式：数据->数据->...->NULL */
void PrintList(Node* Head){Node* Current = Head->Next;while(Current!=NULL){printf("%d->", Current->Data);Current = Current->Next;}printf("NULL \n"); 
}/* 反转链表* Head: 链表头节点指针* 实现方式：三指针法原地反转* 流程：1.逐个节点反转指向 2.最后更新头节点指针 */
void ReverseList(Node* Head){Node* Previous = NULL;Node* Current = Head->Next;Node* Next = NULL; while(Current!=NULL){Next = Current->Next;Current->Next = Previous;Previous = Current;Current = Next; }Head->Next = Previous;
}/* 清空链表（保留头节点）* Head: 链表头节点指针* 流程：逐个释放所有节点内存，最后重置头节点指针 */
void ClearList(Node* Head){Node* Current = Head->Next;Node* Next = NULL;while(Current!=NULL){Next = Current->Next;free(Current);Current = Next;}Head->Next = NULL; 
}
int main(){Node* Head = InitList();InsertHead(Head, 1);InsertHead(Head, 2);InsertHead(Head, 3);InsertTail(Head, 4);InsertTail(Head, 5);PrintList(Head);DeleteNode(Head, 3);PrintList(Head);ModifyNode(Head, 1, 6);PrintList(Head);printf("Position of 6: %d\n", SearchNode(Head, 6));ReverseList(Head);PrintList(Head);ClearList(Head);PrintList(Head);return 0; 
}
        4.部分函数解析

                (1)链表逆置(ReverseList):

/* 三指针法实现链表逆置* 时间复杂度：O(n) 空间复杂度：O(1) * 执行过程：* 1. 初始化三个指针：Previous(前驱)、Current(当前)、Next(后继)* 2. 遍历链表，逐个反转节点指向* 3. 最后更新头节点指针 */
void ReverseList(Node* Head){Node* Previous = NULL;       // 前驱指针初始化为空Node* Current = Head->Next; // 当前指针指向第一个有效节点Node* Next = NULL;           // 后继指针用于临时存储while(Current != NULL){Next = Current->Next;    // 保存下一个节点Current->Next = Previous;// 反转指针方向Previous = Current;      // 前驱指针前移Current = Next;          // 当前指针前移}Head->Next = Previous;       // 更新头节点指向新的首节点
}

                (2) 头插法(InsertHead)

/* 头插法特点：* 1. 新节点总是插入在链表头部* 2. 插入顺序与最终链表顺序相反* 3. 时间复杂度：O(1) */
void InsertHead(Node* Head, int Value){Node* NewNode = (Node*)malloc(sizeof(Node));NewNode->Data = Value;NewNode->Next = Head->Next;  // 新节点指向原首节点Head->Next = NewNode;        // 头节点指向新节点
}

                 (3)尾插法(InsertTail)

/* 尾插法特点：* 1. 新节点总是追加在链表末尾* 2. 插入顺序与最终链表顺序一致* 3. 时间复杂度：O(n) */
void InsertTail(Node* Head, int Value){Node* Current = Head;while(Current->Next != NULL){ // 遍历到最后一个节点Current = Current->Next;}Node* NewNode = (Node*)malloc(sizeof(Node));NewNode->Data = Value;NewNode->Next = NULL;         // 新节点作为末节点Current->Next = NewNode;      // 原末节点指向新节点
}

http://www.xdnf.cn/news/526591.html

相关文章：

  • java中的Servlet4.x详解
  • 湖北理元理律师事务所观察：债务服务中的“倾听者价值”
  • 深入解析Spring Boot与Kafka集成：构建高效消息驱动微服务
  • APP小程序抓包和下游代理
  • 云原生攻防2（Docker基础补充）
  • 2.微服务-配置
  • Fines for Parking vs. Free News
  • 云计算与大数据进阶 | 26、解锁云架构核心：深度解析可扩展数据库的5大策略与挑战（下）
  • Kotlin 协程
  • MySQL故障排查
  • 高效掌握二分查找：从基础到进阶
  • LED太阳光模拟器与氙灯太阳光模拟器的性能区别
  • Protobuf协议生成和使用
  • 5G金融互联：迈向未来金融服务的极速与智能新时代
  • 判断三方库是64位还是32位
  • CVE-2015-3934 Fiyo CMS SQL注入
  • 代码随想录算法训练营Day37 | 完全背包基础理论 518. 零钱兑换II 377. 组合总和Ⅳ 57. 爬楼梯（第八期模拟笔试）
  • 网络协议之一根网线就能连接两台电脑？
  • Spring boot 学习笔记2
  • 易境通海外仓系统：一件代发全场景数字化解决方案
  • MySQL函数触发：函数处理与触发器自动化应用
  • 【Web渗透】DVWA搭建详细教程
  • NLP学习路线图（一）： 线性代数（矩阵运算、特征值分解等）
  • MATLAB中islogical函数用法
  • wpf DataGrid 行选择事件
  • kafka 问与答
  • Cursor日常配置指南
  • CSS的padding属性设置探讨
  • uniapp vue 开发微信小程序 分包梳理经验总结
  • Java迭代器知识点详解