创新优典网站建设免费策划方案平台

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

创新优典网站建设,免费策划方案平台,本地生活服务平台app,wordpress change language1线性表的定义与操作 1.1线性表的定义 线性表是一种基础的数据结构#xff0c;其主要特点是#xff1a;数据元素之间存在一种线性关系#xff08;一对一#xff09;。线性表的每一个数据元素都有一个唯一的前驱和后继#xff0c;除了第一个元素没有前驱#xff0c;最后…1线性表的定义与操作 1.1线性表的定义 线性表是一种基础的数据结构其主要特点是数据元素之间存在一种线性关系一对一。线性表的每一个数据元素都有一个唯一的前驱和后继除了第一个元素没有前驱最后一个元素没有后继 有限性线性表中数据元素的个数是有限的。序列性数据元素之间存在着先后顺序即线性表中的数据元素是有顺序的。相同数据类型线性表中的数据元素具有相同的数据类型。 线性表Linear List是由n个数据元素组成的有限序列可以用以下形式表示 顺序线性表数据元素在内存中占据连续的存储空间。链式线性表数据元素在内存中不必连续但每个元素都包含指向下一个元素的地址指针 1.2线性表的基本操作 初始化操作 功能创建一个空的线性表为后续的操作做好准备。实现通常分配一定的存储空间并将线性表的长度设置为 0。 插入操作 功能在指定位置插入一个新的数据元素。实现首先要判断插入位置是否合法如果合法则从插入位置开始将后面的元素依次向后移动一位然后在指定位置插入新元素并更新线性表的长度。例如在线性表 [1, 2, 3] 中在位置 2 插入元素 4结果为 [1, 2, 4, 3]。 删除操作 功能删除指定位置的数据元素。实现首先判断删除位置是否合法如果合法则将删除位置后面的元素依次向前移动一位覆盖被删除的元素并更新线性表的长度。例如在线性表 [1, 2, 3, 4] 中删除位置 2 的元素结果为 [1, 2, 4]。 查找操作 功能在线性表中查找指定的数据元素并返回其位置。实现从线性表的第一个元素开始依次比较每个元素与目标元素是否相等直到找到目标元素或遍历完整个线性表。例如在线性表 [1, 2, 3, 4] 中查找元素 3返回位置 2。 遍历操作 功能依次访问线性表中的每个数据元素。实现使用循环从线性表的第一个元素开始依次访问每个元素直到遍历完整个线性表。例如对于线性表 [1, 2, 3, 4]遍历输出为 “1 2 3 4”。 获取长度操作 功能返回线性表中数据元素的个数。实现直接返回存储线性表长度的变量值。 判断空操作 功能判断线性表是否为空。实现如果线性表的长度为 0则为空返回 true否则返回 false。 2线性表的顺序存储 2.1顺序表的定义与初始化 一、顺序表的定义 顺序表又称线性表的顺序存储结构是用一组地址连续的存储单元依次存储线性表中的数据元素从而使得逻辑上相邻的两个元素在物理位置上也相邻。在顺序表中各个表项的逻辑顺序与其存放的物理顺序一致即第i个表项存储于第i个物理位置1≤i≤n。 顺序表具有以下特点 随机访问可通过首地址和元素序号在单位时间O(1)内找到指定的元素。存储密度高因为每个结点存储空间只用来存储数据元素没有额外的开销。物理位置相邻逻辑上相邻的元素在物理位置上也相邻因此插入和删除元素需要移动大量元素比较耗时。 二、顺序表的初始化 确定顺序表的存储结构 通常可以使用数组来实现顺序表。定义一个数组来存储数据元素并记录顺序表的当前长度。 分配存储空间 根据实际需求确定数组的大小并在内存中分配相应的空间。可以在程序运行时动态分配空间也可以使用固定大小的数组。 设置初始状态 将顺序表的长度初始化为 0表示当前没有数据元素。同时可以将数组的所有元素初始化为特定的值如 0 或 null。 以下是用 C 语言实现顺序表初始化的示例代码 方式一静态数组定义和初始化 这是最简单的定义和初始化方式适用于固定大小的顺序表。 #include stdio.h#define MAXSIZE 100 // 定义顺序表的最大容量 typedef int ElemType; // 定义顺序表中元素的类型typedef struct {ElemType data[MAXSIZE]; // 存储数据的静态数组int length; // 当前表长 } SqList; // 定义顺序表的结构体类型// 初始化顺序表 void InitList(SqList *L) {L-length 0; // 初始化表长为0 }int main() {SqList L; // 声明一个顺序表变量InitList(L); // 初始化顺序表// … 其他操作return 0; } 方式二动态数组定义和初始化 这种方式允许在运行时动态分配内存适用于不确定顺序表大小的情况。 #include stdio.h #include stdlib.htypedef int ElemType; // 定义顺序表中元素的类型typedef struct {ElemType *data; // 存储数据的动态数组int length; // 当前表长int maxSize; // 数组的最大容量 } SqList; // 定义顺序表的结构体类型// 初始化顺序表 void InitList(SqList *L, int maxSize) {L-data (ElemType *)malloc(maxSize * sizeof(ElemType)); // 动态分配内存if (L-data NULL) {printf(内存分配失败\n);exit(1);}L-length 0; // 初始化表长为0L-maxSize maxSize; // 设置最大容量 }// 释放顺序表的内存 void FreeList(SqList *L) {free(L-data);L-data NULL;L-length 0;L-maxSize 0; }int main() {SqList L; // 声明一个顺序表变量InitList(L, 100); // 初始化顺序表最大容量为100// … 其他操作FreeList(L); // 释放顺序表的内存return 0; } 方式三内存分配与初始化函数结合 这种方式将内存分配和初始化结合在一起适用于需要初始化默认值的情况。 #include stdio.h #include stdlib.htypedef int ElemType; // 定义顺序表中元素的类型typedef struct {ElemType data; // 存储数据的动态数组int length; // 当前表长int maxSize; // 数组的最大容量 } SqList; // 定义顺序表的结构体类型// 初始化顺序表并分配内存 SqList CreateList(int maxSize) {SqList *L (SqList *)malloc(sizeof(SqList)); // 动态分配顺序表结构体内存if (L NULL) {printf(内存分配失败\n);exit(1);}L-data (ElemType *)malloc(maxSize * sizeof(ElemType)); // 动态分配数组内存if (L-data NULL) {printf(内存分配失败\n);free(L);exit(1);}L-length 0; // 初始化表长为0L-maxSize maxSize; // 设置最大容量return L; }// 释放顺序表的内存 void DestroyList(SqList *L) {free(L-data);free(L); }int main() {SqList *L CreateList(100); // 创建顺序表最大容量为100// … 其他操作DestroyList(L); // 释放顺序表的内存return 0; } 2.2顺序表的基本操作 1插入运算 插入运算的步骤 检查位置合法性 确保插入位置 pos 在有效范围内即 1 ≤ pos ≤ length 1其中 length 是顺序表的当前长度。如果 pos 小于 1 或大于 length 1则插入位置非法通常返回错误或抛出异常。检查容量 确保顺序表的容量即数组的大小足够容纳新元素。如果当前容量不足需要进行扩容操作通常是分配一个更大的数组并将原数组的内容复制到新数组中。插入元素 从插入位置 pos 开始将顺序表中该位置及其后的所有元素向后移动一个位置以腾出空间插入新元素。将新元素插入到 pos - 1 的位置因为数组索引从 0 开始。更新长度 将顺序表的长度 length 增加 1。 以下是一个简单的 c语言实现展示了如何在顺序表中插入元素 #include stdio.h #include stdlib.h#define MAXSIZE 100 // 定义顺序表的最大容量 typedef int ElemType; // 定义顺序表中元素的类型typedef struct {ElemType data[MAXSIZE]; // 存储数据的数组int length; // 当前表长 } SqList; // 定义顺序表的结构体类型// 初始化顺序表 void InitList(SqList *L) {L-length 0; // 初始化表长为0 }// 插入元素到顺序表的指定位置 int InsertList(SqList *L, int pos, ElemType e) {if (L-length MAXSIZE) {printf(顺序表已满无法插入元素 %d\n, e);return 0; // 插入失败}if (pos 1 || pos L-length 1) {printf(插入位置 %d 不合法\n, pos);return 0; // 插入失败}// 从后向前移动元素为新元素腾出位置for (int i L-length; i pos; i–) {L-data[i] L-data[i - 1];}L-data[pos - 1] e; // 插入新元素L-length; // 更新当前表长return 1; // 插入成功 }// 打印顺序表中的所有元素 void DisplayList(const SqList *L) {for (int i 0; i L-length; i) {printf(%d , L-data[i]);}printf(\n); }int main() {SqList L; // 声明一个顺序表变量InitList(L); // 初始化顺序表// 插入1到10的数字到顺序表中for (int i 1; i 10; i) {InsertList(L, i, i);}// 打印顺序表中的所有元素printf(顺序表中的元素);DisplayList(L);// 在位置3插入一个新元素 99if (InsertList(L, 3, 99)) {printf(插入元素后的顺序表);DisplayList(L);}return 0; } 2删除运算 删除运算的步骤 检查位置合法性 确保删除位置 pos 在有效范围内即 1 ≤ pos ≤ length其中 length 是顺序表的当前长度。如果 pos 小于 1 或大于 length则删除位置非法通常返回错误或抛出异常。删除元素 从删除位置 pos 开始将顺序表中该位置之后的所有元素向前移动一个位置以填补被删除元素留下的空位。注意不需要为被删除元素分配新的存储空间或进行其他特殊处理因为顺序表的内存是连续的只需调整后续元素的位置即可。更新长度 将顺序表的长度 length 减少 1。 // 删除顺序表中指定位置的元素 int deleteElem(SeqList *L, int pos) {if (L-length 0) {return 0; // 顺序表为空删除失败}if (pos 1 || pos L-length) {return 0; // 位置不合法删除失败}for (int i pos; i L-length; i) {L-data[i - 1] L-data[i];}L-length–;return 1; // 删除成功 } 以下是一个完整的 C 代码示例包括顺序表的定义、初始化、删除运算以及显示顺序表内容的功能。 #include stdio.h #include stdlib.h#define MAXSIZE 100 // 定义顺序表的最大容量 typedef int ElemType; // 定义顺序表中元素的类型typedef struct {ElemType data[MAXSIZE]; // 存储数据的数组int length; // 当前表长 } SqList; // 定义顺序表的结构体类型// 初始化顺序表 void InitList(SqList *L) {L-length 0; // 初始化表长为0 }// 插入元素到顺序表的指定位置 int InsertList(SqList *L, int pos, ElemType e) {if (L-length MAXSIZE) {printf(顺序表已满无法插入元素 %d\n, e);return 0; // 插入失败}if (pos 1 || pos L-length 1) {printf(插入位置 %d 不合法\n, pos);return 0; // 插入失败}// 从后向前移动元素为新元素腾出位置for (int i L-length; i pos; i–) {L-data[i] L-data[i - 1];}L-data[pos - 1] e; // 插入新元素L-length; // 更新当前表长return 1; // 插入成功 }// 删除顺序表中指定位置的元素 int DeleteList(SqList *L, int pos, ElemType *e) {if (L-length 0) {printf(顺序表为空无法删除元素\n);return 0; // 删除失败}if (pos 1 || pos L-length) {printf(删除位置 %d 不合法\n, pos);return 0; // 删除失败}*e L-data[pos - 1]; // 保存被删除的元素// 从前向后移动元素覆盖被删除的元素for (int i pos - 1; i L-length - 1; i) {L-data[i] L-data[i 1];}L-length–; // 更新当前表长return 1; // 删除成功 }// 打印顺序表中的所有元素 void DisplayList(const SqList *L) {for (int i 0; i L-length; i) {printf(%d , L-data[i]);}printf(\n); }int main() {SqList L; // 声明一个顺序表变量InitList(L); // 初始化顺序表// 插入1到10的数字到顺序表中for (int i 1; i 10; i) {InsertList(L, i, i);}// 打印顺序表中的所有元素printf(顺序表中的元素);DisplayList(L);// 从顺序表中删除位置3的元素ElemType deletedElem;if (DeleteList(L, 3, deletedElem)) {printf(删除了元素 %d\n, deletedElem);printf(删除元素后的顺序表);DisplayList(L);}return 0; } 3按值查找 按值查找的步骤 遍历顺序表从顺序表的第一个元素开始逐个检查每个元素的值是否等于指定的值。 记录位置如果找到了与指定值相等的元素则记录该元素的位置索引。注意根据具体实现位置可能是从0开始还是从1开始的索引。 返回结果如果遍历完整个顺序表后找到了元素则返回记录的位置如果未找到则返回一个表示失败的值。
// 按值查找元素在顺序表中的位置 int searchElem(SeqList *L, int elem) {for (int i 0; i L-length; i) {if (L-data[i] elem) {return i 1;}}return -1; // 未找到元素 } 以下是一个简单的 c语言实现展示了如何在顺序表中找到具体元素 #include stdio.h #include stdlib.h#define MAXSIZE 100 // 定义顺序表的最大容量 typedef int ElemType; // 定义顺序表中元素的类型typedef struct {ElemType data[MAXSIZE]; // 存储数据的数组int length; // 当前表长 } SqList; // 定义顺序表的结构体类型// 初始化顺序表 void InitList(SqList *L) {L-length 0; // 初始化表长为0 }// 插入元素到顺序表的指定位置 int InsertList(SqList *L, int pos, ElemType e) {if (L-length MAXSIZE) {printf(顺序表已满无法插入元素 %d\n, e);return 0; // 插入失败}if (pos 1 || pos L-length 1) {printf(插入位置 %d 不合法\n, pos);return 0; // 插入失败}// 从后向前移动元素为新元素腾出位置for (int i L-length; i pos; i–) {L-data[i] L-data[i - 1];}L-data[pos - 1] e; // 插入新元素L-length; // 更新当前表长return 1; // 插入成功 }// 按值查找顺序表中的元素 int LocateElem(const SqList *L, ElemType e) {for (int i 0; i L-length; i) {if (L-data[i] e) {return i 1; // 返回元素位置从1开始}}return 0; // 未找到元素 }// 打印顺序表中的所有元素 void DisplayList(const SqList L) {for (int i 0; i L-length; i) {printf(%d , L-data[i]);}printf(\n); }int main() {SqList L; // 声明一个顺序表变量InitList(L); // 初始化顺序表// 插入1到10的数字到顺序表中for (int i 1; i 10; i) {InsertList(L, i, i);}// 打印顺序表中的所有元素printf(顺序表中的元素);DisplayList(L);// 按值查找元素 5int pos LocateElem(L, 5);if (pos) {printf(元素 5 的位置是 %d\n, pos);} else {printf(未找到元素 5\n);}// 按值查找元素 20pos LocateElem(L, 20);if (pos) {printf(元素 20 的位置是 %d\n, pos);} else {printf(未找到元素 20\n);}return 0; } 3线性表的链式存储 优点 动态大小 链表不需要在创建时指定大小它可以根据需要动态地增长和缩小。高效插入和删除 在链表中插入和删除操作特别是在已知节点位置的情况下通常可以在O(1)时间复杂度内完成因为只需要调整相邻节点的指针。无需连续内存 链表节点可以分散在内存中的任何位置这有助于减少内存碎片问题。灵活性 链表可以通过各种方式如双向链表、循环链表等进行扩展以满足不同的需求。 缺点 访问速度慢 链表不支持随机访问因此查找特定位置的元素需要从头节点开始顺序遍历时间复杂度为O(n)。额外空间开销 每个链表节点都需要额外的空间来存储指针这增加了内存的使用量。内存管理复杂 链表节点的动态分配和释放需要仔细管理以避免内存泄漏和碎片化。缓存性能较差 由于链表节点在内存中通常不是连续存储的因此可能无法充分利用CPU缓存导致访问速度下降。 应用场景 链表适用于需要频繁进行插入和删除操作但对随机访问要求不高的场景。双向链表和循环链表等扩展形式可以用于需要双向遍历或循环遍历的场景。在实现某些数据结构如栈、队列、哈希表等时链表也可以作为底层存储结构。 3.1单向链表的结构 一、结构特点 节点组成 单向链表由一系列节点Node组成每个节点包含两个部分数据域Data和指针域Next。数据域用于存储节点的数据可以是任意类型由编程者自行指定。指针域用于存储下一个节点的地址或指针指向链表中的下一个节点。链接方向 单向链表的链接方向是单向的即只能从头节点开始通过指针域依次访问后续节点。头节点与头指针 头节点是为了操作方便而设立的通常放在第一个元素节点之前其数据域一般无实际意义但也可以用来存放链表长度等信息。头指针是指向链表头节点的指针无论链表是否为空头指针均不为空是链表的必要元素。无头与有头链表 无头链表不设立头节点头指针直接指向第一个元素节点如果存在。有头链表设立头节点头指针指向头节点头节点的指针域指向第一个元素节点。 二单链表的定义与初始化 一、单链表的定义 typedef struct ListNode {int data;struct ListNode next; } ListNode; 二、单链表的初始化 ListNode* initList() {// 创建一个空的头节点ListNode* head (ListNode*)malloc(sizeof(ListNode));head-data 0; // 头节点的数据域可以存储一些特殊信息这里初始化为 0head-next NULL;return head; } 以下是一个用C语言初始化单链表的示例包含头节点 #include stdio.h #include stdlib.h// 定义链表节点 typedef int ElemType; // 定义链表中元素的类型typedef struct Node {ElemType data; // 数据域struct Node *next; // 指针域指向下一个节点 } Node, *LinkedList;// 初始化链表 LinkedList InitList() {LinkedList L (LinkedList)malloc(sizeof(Node)); // 申请头节点空间if (!L) {printf(内存分配失败\n);exit(1); // 内存分配失败退出程序}L-next NULL; // 初始化头节点指针域为空return L; // 返回初始化后的链表 }// 测试初始化链表 int main() {LinkedList L InitList(); // 初始化链表if (L-next NULL) {printf(链表初始化成功头节点指向 NULL\n);}// 这里可以继续对链表进行插入、删除等操作free(L); // 释放头节点的内存return 0; } 3.2单链表的基本操作 1插入结点建立单链表 在单链表中插入节点是一个常见的操作它允许我们在链表的特定位置添加一个新的节点。 在链表头部插入节点新节点成为链表的新头节点。在链表尾部插入节点新节点成为链表的最后一个节点。在链表中间插入节点在指定位置插入新节点新节点位于指定位置的节点之前。 单链表的定义 #include stdio.h #include stdlib.h// 定义链表节点的类型 typedef int ElemType; // 定义链表中元素的类型typedef struct Node {ElemType data; // 数据域struct Node *next; // 指针域指向下一个节点 } Node, *LinkedList; 初始化单链表 // 初始化链表 LinkedList InitList() {LinkedList L (LinkedList)malloc(sizeof(Node)); // 申请头节点空间if (!L) {printf(内存分配失败\n);exit(1); // 内存分配失败退出程序}L-next NULL; // 初始化头节点指针域为空return L; // 返回初始化后的链表 } 在链表头部插入节点 // 在链表头部插入节点 void InsertHead(LinkedList L, ElemType e) {Node *s (Node *)malloc(sizeof(Node)); // 申请新节点空间if (!s) {printf(内存分配失败\n);exit(1); // 内存分配失败退出程序}s-data e; // 新节点数据域赋值s-next L-next; // 新节点的指针域指向原头节点的下一个节点L-next s; // 头节点的指针域指向新节点 } 在链表尾部插入节点 // 在链表尾部插入节点 void InsertTail(LinkedList L, ElemType e) {Node *p L;// 找到链表的最后一个节点while (p-next) {p p-next;}Node *s (Node *)malloc(sizeof(Node)); // 申请新节点空间if (!s) {printf(内存分配失败\n);exit(1); // 内存分配失败退出程序}s-data e; // 新节点数据域赋值s-next NULL; // 新节点的指针域指向NULLp-next s; // 原最后一个节点的指针域指向新节点 } 在指定位置插入节点 // 在链表的第pos个位置插入节点 int InsertAtPosition(LinkedList L, int pos, ElemType e) {Node *p L;int i 0;// 找到插入位置的前一个节点while (p i pos - 1) {p p-next;i;}if (!p || i pos - 1) {printf(插入位置不合法\n);return 0; // 插入失败}// 创建新节点Node *s (Node *)malloc(sizeof(Node));if (!s) {printf(内存分配失败\n);exit(1); // 内存分配失败退出程序}s-data e; // 新节点数据域赋值s-next p-next; // 新节点的指针域指向插入位置的下一个节点p-next s; // 插入位置前一个节点的指针域指向新节点return 1; // 插入成功 } 打印链表 // 打印链表中的所有元素 void DisplayList(LinkedList L) {Node p L-next;while (p) {printf(%d , p-data);p p-next;}printf(\n); } 主函数 int main() {LinkedList L InitList(); // 初始化链表// 在链表头部插入节点InsertHead(L, 1);InsertHead(L, 2);// 在链表尾部插入节点InsertTail(L, 3);InsertTail(L, 4);// 在指定位置插入节点InsertAtPosition(L, 3, 5); // 在第3个位置插入元素5// 打印链表中的所有元素printf(链表中的元素);DisplayList(L);return 0; } 2有头节点的单链表 在有头节点的单链表中链表包含一个额外的节点称为头节点或哑节点、哨兵节点。头节点不存储实际的数据而是作为链表的起点其next指针指向链表的第一个实际数据节点。头节点的存在可以简化链表的操作特别是在插入和删除节点时因为它允许我们在链表头部进行这些操作而无需检查是否为空链表。 定义 在C语言中有头节点的单链表可以通过定义一个结构体来表示链表节点其中包含一个数据域和一个指向下一个节点的指针域。头节点也是这个结构体的一个实例但其数据域通常不会被使用。 typedef struct Node { int data; // 数据域可以存储任意类型的数据这里以int为例 struct Node next; // 指针域指向下一个节点
} Node; 初始化 初始化有头节点的单链表时需要为头节点分配内存并将其next指针设置为NULL表示链表当前为空。以下是一个初始化有头节点的单链表的函数示例 Node* initLinkedList() { Node* head (Node*)malloc(sizeof(Node)); // 为头节点分配内存 if (head NULL) { // 内存分配失败可以打印错误信息或进行其他错误处理 printf(内存分配失败\n); return NULL; // 返回NULL表示初始化失败 } head-next NULL; // 初始化头节点的next指针为NULL表示链表为空 return head; // 返回头节点的指针
} 3求单链表的长度 #include stdio.h #include stdlib.h// 定义链表节点的类型 typedef int ElemType;typedef struct Node {ElemType data; // 数据域struct Node *next; // 指针域指向下一个节点 } Node, *LinkedList;// 初始化有头节点的单链表 LinkedList InitList() {LinkedList L (LinkedList)malloc(sizeof(Node)); // 申请头节点空间if (!L) {printf(内存分配失败\n);exit(1);}L-next NULL; // 初始化头节点的下一个节点为空return L; }// 在链表尾部插入节点 void InsertTail(LinkedList L, ElemType e) {Node *p L;while (p-next) {p p-next;}Node *s (Node *)malloc(sizeof(Node)); // 申请新节点空间if (!s) {printf(内存分配失败\n);exit(1);}s-data e; // 新节点数据域赋值s-next NULL; // 新节点的指针域指向NULLp-next s; // 原最后一个节点的指针域指向新节点 }// 求链表的长度 int GetLength(LinkedList L) {int length 0; // 初始化长度为0Node *p L-next; // 从头节点的下一个节点开始遍历while (p) {length; // 计数p p-next; // 移动到下一个节点}return length; // 返回链表的长度 }// 打印链表中的所有元素 void DisplayList(LinkedList L) {Node *p L-next;while (p) {printf(%d , p-data);p p-next;}printf(\n); }// 主函数 int main() {LinkedList L InitList(); // 初始化链表// 插入一些元素到链表中InsertTail(L, 10);InsertTail(L, 20);InsertTail(L, 30);InsertTail(L, 40);// 打印链表printf(链表中的元素);DisplayList(L);// 求链表的长度int length GetLength(L);printf(链表的长度是%d\n, length);return 0; } 4输出表中所有元素 #include stdio.h #include stdlib.h// 定义链表节点的类型 typedef int ElemType;typedef struct Node {ElemType data; // 数据域struct Node *next; // 指针域指向下一个节点 } Node, *LinkedList;// 初始化有头节点的单链表 LinkedList InitList() {LinkedList L (LinkedList)malloc(sizeof(Node)); // 申请头节点空间if (!L) {printf(内存分配失败\n);exit(1);}L-next NULL; // 初始化头节点的下一个节点为空return L; }// 在链表尾部插入节点 void InsertTail(LinkedList L, ElemType e) {Node *p L;while (p-next) {p p-next;}Node *s (Node *)malloc(sizeof(Node)); // 申请新节点空间if (!s) {printf(内存分配失败\n);exit(1);}s-data e; // 新节点数据域赋值s-next NULL; // 新节点的指针域指向NULLp-next s; // 原最后一个节点的指针域指向新节点 }// 打印链表中的所有元素 void DisplayList(LinkedList L) {Node *p L-next; // 从头节点的下一个节点开始遍历while (p) {printf(%d , p-data); // 输出当前节点的数据域p p-next; // 移动到下一个节点}printf(\n); }// 主函数 int main() {LinkedList L InitList(); // 初始化链表// 插入一些元素到链表中InsertTail(L, 10);InsertTail(L, 20);InsertTail(L, 30);InsertTail(L, 40);// 打印链表中的所有元素printf(链表中的元素);DisplayList(L);return 0; } 5删除指定元素 #include stdio.h #include stdlib.h// 定义链表节点的类型 typedef int ElemType;typedef struct Node {ElemType data; // 数据域struct Node *next; // 指针域指向下一个节点 } Node, *LinkedList;// 初始化有头节点的单链表 LinkedList InitList() {LinkedList L (LinkedList)malloc(sizeof(Node)); // 申请头节点空间if (!L) {printf(内存分配失败\n);exit(1);}L-next NULL; // 初始化头节点的下一个节点为空return L; }// 在链表尾部插入节点 void InsertTail(LinkedList L, ElemType e) {Node *p L;while (p-next) {p p-next;}Node *s (Node *)malloc(sizeof(Node)); // 申请新节点空间if (!s) {printf(内存分配失败\n);exit(1);}s-data e; // 新节点数据域赋值s-next NULL; // 新节点的指针域指向NULLp-next s; // 原最后一个节点的指针域指向新节点 }// 删除链表中指定的元素 void DeleteElement(LinkedList L, ElemType e) {Node *p L; // p 指向头节点Node *q; // q 用于指向要删除的节点// 遍历链表找到目标元素的前一个节点while (p-next p-next-data ! e) {p p-next;}// 如果找到了目标元素if (p-next) {q p-next; // q 指向要删除的节点p-next q-next; // 修改前一个节点的指针域跳过目标节点free(q); // 释放目标节点的内存空间printf(元素 %d 已删除\n, e);} else {printf(链表中不存在元素 %d\n, e);} }// 打印链表中的所有元素 void DisplayList(LinkedList L) {Node *p L-next; // 从头节点的下一个节点开始遍历while (p) {printf(%d , p-data); // 输出当前节点的数据域p p-next; // 移动到下一个节点}printf(\n); }// 主函数 int main() {LinkedList L InitList(); // 初始化链表// 插入一些元素到链表中InsertTail(L, 10);InsertTail(L, 20);InsertTail(L, 30);InsertTail(L, 40);// 打印链表中的所有元素printf(删除前的链表);DisplayList(L);// 删除指定元素DeleteElement(L, 30);// 打印删除后的链表printf(删除后的链表);DisplayList(L);return 0; } 6查找特定元素

1. 无头结点的单链表查找代码 struct ListNode {int value; // 节点的值struct ListNode* next; // 指向下一个节点的指针 };// 查找特定元素的函数 struct ListNode* search_element(struct ListNode* head, int target) {struct ListNode* current head; // 从头节点开始查找while (current ! NULL) { // 遍历链表直到结束if (current-value target) { // 如果当前节点的值等于目标值return current; // 找到元素返回当前节点}current current-next; // 移动到下一个节点}return NULL; // 未找到元素返回 NULL } 2有头结点的单链表查找代码 struct ListNode {int value; // 节点的值struct ListNode* next; // 指向下一个节点的指针 };// 查找特定元素的函数 struct ListNode* search_element(struct ListNode* head, int target) {struct ListNode* current head-next; // 从头节点的下一个节点开始查找while (current ! NULL) { // 遍历链表直到结束if (current-value target) { // 如果当前节点的值等于目标值return current; // 找到元素返回当前节点}current current-next; // 移动到下一个节点}return NULL; // 未找到元素返回 NULL } 3完整代码 #include stdio.h #include stdlib.h// 定义链表节点的类型 typedef int ElemType;typedef struct Node {ElemType data; // 数据域struct Node *next; // 指针域指向下一个节点 } Node, *LinkedList;// 初始化有头节点的单链表 LinkedList InitList() {LinkedList L (LinkedList)malloc(sizeof(Node)); // 申请头节点空间if (!L) {printf(内存分配失败\n);exit(1);}L-next NULL; // 初始化头节点的下一个节点为空return L; }// 在链表尾部插入节点 void InsertTail(LinkedList L, ElemType e) {Node *p L;while (p-next) {p p-next;}Node *s (Node *)malloc(sizeof(Node)); // 申请新节点空间if (!s) {printf(内存分配失败\n);exit(1);}s-data e; // 新节点数据域赋值s-next NULL; // 新节点的指针域指向NULLp-next s; // 原最后一个节点的指针域指向新节点 }// 查找链表中指定的元素 int FindElement(LinkedList L, ElemType e) {Node *p L-next; // 从头节点的下一个节点开始遍历int index 1; // 记录元素的索引位置// 遍历链表查找目标元素while (p) {if (p-data e) {return index; // 返回元素的索引位置}p p-next; // 移动到下一个节点index; // 索引位置加1}return -1; // 如果未找到返回-1 }// 打印链表中的所有元素 void DisplayList(LinkedList L) {Node *p L-next; // 从头节点的下一个节点开始遍历while (p) {printf(%d , p-data); // 输出当前节点的数据域p p-next; // 移动到下一个节点}printf(\n); }// 主函数 int main() {LinkedList L InitList(); // 初始化链表// 插入一些元素到链表中InsertTail(L, 10);InsertTail(L, 20);InsertTail(L, 30);InsertTail(L, 40);// 打印链表中的所有元素printf(链表中的元素);DisplayList(L);// 查找指定元素ElemType target 30;int index FindElement(L, target);if (index ! -1) {printf(元素 %d 在链表中的位置是 %d\n, target, index);} else {printf(链表中不存在元素 %d\n, target);}return 0; } 7判断单链表是否为空
2. 无头结点的单链表判断是否为空 struct ListNode {int value; // 节点的值struct ListNode* next; // 指向下一个节点的指针 };// 判断无头结点单链表是否为空 int is_empty(struct ListNode* head) {return head NULL; // 头节点为 NULL 则链表为空 }
3. 有头结点的单链表判断是否为空 struct ListNode {int value; // 节点的值struct ListNode* next; // 指向下一个节点的指针 };// 判断有头结点单链表是否为空 int is_empty(struct ListNode* head) {return head-next NULL; // 如果头节点的下一个节点为 NULL则链表为空 } 8销毁单链表
4. 无头结点的单链表销毁 #include stdlib.hstruct ListNode {int value; // 节点的值struct ListNode* next; // 指向下一个节点的指针 };// 销毁无头结点单链表的函数 void destroy_list(struct ListNode* head) {struct ListNode* current head;struct ListNode* next_node;while (current ! NULL) { // 遍历链表直到结束next_node current-next; // 保存下一个节点free(current); // 释放当前节点current next_node; // 移动到下一个节点} } 2. 有头结点的单链表销毁 #include stdlib.hstruct ListNode {int value; // 节点的值struct ListNode* next; // 指向下一个节点的指针 };// 销毁有头结点单链表的函数 void destroy_list(struct ListNode* head) {struct ListNode* current head;struct ListNode* next_node;while (current ! NULL) { // 遍历链表直到结束next_node current-next; // 保存下一个节点free(current); // 释放当前节点current next_node; // 移动到下一个节点}head NULL; // 销毁后将头节点指针置为 NULL避免野指针 } 9清空单链表
5. 无头结点的单链表清空 #include stdlib.hstruct ListNode {int value; // 节点的值struct ListNode* next; // 指向下一个节点的指针 };// 清空无头结点单链表的函数 void clear_list(struct ListNode** head) {struct ListNode* current head;struct ListNode next_node;while (current ! NULL) { // 遍历链表直到结束next_node current-next; // 保存下一个节点free(current); // 释放当前节点current next_node; // 移动到下一个节点}head NULL; // 清空后将头节点指针置为 NULL表示链表为空 } 2. 有头结点的单链表清空 #include stdlib.hstruct ListNode {int value; // 节点的值struct ListNode next; // 指向下一个节点的指针 };// 清空有头结点单链表的函数 void clear_list(struct ListNode* head) {struct ListNode* current head-next;struct ListNode* next_node;while (current ! NULL) { // 遍历链表直到结束next_node current-next; // 保存下一个节点free(current); // 释放当前节点current next_node; // 移动到下一个节点}head-next NULL; // 清空后将头节点的 next 指针置为 NULL表示链表为空 } 3.3循环链表 循环链表是一种特殊的链表结构其特点是链表中的最后一个节点指向头节点形成一个闭环。这种结构使得链表的遍历可以从任何节点开始并且在遍历到链表末尾时可以无缝地回到链表的开头。循环链表可以是单向的每个节点只有一个指针指向下一个节点或双向的每个节点有两个指针分别指向前一个节点和后一个节点。 循环链表的特点 闭环结构链表的最后一个节点指向头节点形成一个闭环。遍历灵活可以从任何节点开始遍历并且在遍历到链表末尾时可以回到链表的开头。节省空间相比于双向链表单向循环链表只需要一个指针域节省了空间。应用场景常用于需要循环操作的场景如循环队列、约瑟夫环问题等。 循环链表的基本操作
6. 初始化循环链表 初始化一个空的循环链表创建一个头节点并使其指向自身。 #include stdio.h #include stdlib.h// 定义链表节点的类型 typedef int ElemType;typedef struct Node {ElemType data; // 数据域struct Node *next; // 指针域指向下一个节点 } Node, *CircularLinkedList;// 初始化循环链表 CircularLinkedList InitCircularList() {CircularLinkedList L (CircularLinkedList)malloc(sizeof(Node)); // 申请头节点空间if (!L) {printf(内存分配失败\n);exit(1);}L-next L; // 头节点的下一个节点指向自身形成闭环return L; }2. 插入节点 在循环链表中插入节点可以选择在链表的头部或尾部插入。 // 在链表尾部插入节点 void InsertTail(CircularLinkedList L, ElemType e) {Node *p L;while (p-next ! L) { // 找到链表的最后一个节点p p-next;}Node *s (Node *)malloc(sizeof(Node)); // 申请新节点空间if (!s) {printf(内存分配失败\n);exit(1);}s-data e; // 新节点数据域赋值s-next L; // 新节点的指针域指向头节点p-next s; // 原最后一个节点的指针域指向新节点 }3. 删除节点 删除循环链表中的指定节点。 // 删除链表中指定的元素 void DeleteElement(CircularLinkedList L, ElemType e) {Node *p L; // p 指向头节点Node *q; // q 用于指向要删除的节点// 遍历链表找到目标元素的前一个节点while (p-next ! L p-next-data ! e) {p p-next;}// 如果找到了目标元素if (p-next ! L) {q p-next; // q 指向要删除的节点p-next q-next; // 修改前一个节点的指针域跳过目标节点free(q); // 释放目标节点的内存空间printf(元素 %d 已删除\n, e);} else {printf(链表中不存在元素 %d\n, e);} }4. 查找节点 查找循环链表中的指定元素。 // 查找链表中指定的元素 int FindElement(CircularLinkedList L, ElemType e) {Node *p L-next; // 从头节点的下一个节点开始遍历int index 1; // 记录元素的索引位置// 遍历链表查找目标元素while (p ! L) {if (p-data e) {return index; // 返回元素的索引位置}p p-next; // 移动到下一个节点index; // 索引位置加1}return -1; // 如果未找到返回-1 }5. 打印链表 遍历并打印循环链表中的所有元素。 // 打印链表中的所有元素 void DisplayList(CircularLinkedList L) {Node *p L-next; // 从头节点的下一个节点开始遍历while (p ! L) {printf(%d , p-data); // 输出当前节点的数据域p p-next; // 移动到下一个节点}printf(\n); }主函数示例 // 主函数 int main() {CircularLinkedList L InitCircularList(); // 初始化循环链表// 插入一些元素到链表中InsertTail(L, 10);InsertTail(L, 20);InsertTail(L, 30);InsertTail(L, 40);// 打印链表中的所有元素printf(链表中的元素);DisplayList(L);// 查找指定元素ElemType target 30;int index FindElement(L, target);if (index ! -1) {printf(元素 %d 在链表中的位置是 %d\n, target, index);} else {printf(链表中不存在元素 %d\n, target);}// 删除指定元素DeleteElement(L, 30);// 打印删除后的链表printf(删除后的链表);DisplayList(L);return 0; } 3.4双向链表 双向链表是一种链表结构与单向链表不同双向链表中的每个节点除了包含数据域外还包含两个指针分别指向前一个节点和后一个节点。这种结构使得链表的操作更加灵活但也增加了空间的开销。 双向链表的特点 双向遍历可以从任何一个节点开始向前或向后遍历链表。灵活性高插入和删除操作更加方便因为可以直接访问前一个节点和后一个节点。空间开销大每个节点包含两个指针相比于单向链表空间开销更大。应用场景适用于需要频繁插入和删除操作的场景如文本编辑器中的撤销/重做功能。 双向链表的基本操作
7. 初始化双向链表 初始化一个空的双向链表创建一个头节点并使其前后指针都指向自身如果链表为空。 #include stdio.h #include stdlib.h// 定义链表节点的类型 typedef int ElemType;typedef struct Node {ElemType data; // 数据域struct Node *prev; // 指针域指向前一个节点struct Node *next; // 指针域指向下一个节点 } Node, *DoubleLinkedList;// 初始化双向链表 DoubleLinkedList InitDoubleList() {DoubleLinkedList L (DoubleLinkedList)malloc(sizeof(Node)); // 申请头节点空间if (!L) {printf(内存分配失败\n);exit(1);}L-prev L; // 头节点的前指针指向自身L-next L; // 头节点的后指针指向自身return L; }2. 插入节点 在双向链表中插入节点可以选择在链表的头部或尾部插入。 // 在链表尾部插入节点 void InsertTail(DoubleLinkedList L, ElemType e) {Node *p L;while (p-next ! L) { // 找到链表的最后一个节点p p-next;}Node *s (Node *)malloc(sizeof(Node)); // 申请新节点空间if (!s) {printf(内存分配失败\n);exit(1);}s-data e; // 新节点数据域赋值s-next L; // 新节点的后指针指向头节点s-prev p; // 新节点的前指针指向原最后一个节点p-next s; // 原最后一个节点的后指针指向新节点L-prev s; // 头节点的前指针指向新节点 }3. 删除节点 删除双向链表中的指定节点。 // 删除链表中指定的元素 void DeleteElement(DoubleLinkedList L, ElemType e) {Node *p L-next; // p 指向第一个节点// 遍历链表找到目标元素while (p ! L p-data ! e) {p p-next;}// 如果找到了目标元素if (p ! L) {p-prev-next p-next; // 修改前一个节点的后指针p-next-prev p-prev; // 修改后一个节点的前指针free(p); // 释放目标节点的内存空间printf(元素 %d 已删除\n, e);} else {printf(链表中不存在元素 %d\n, e);} }4. 查找节点 查找双向链表中的指定元素。 // 查找链表中指定的元素 int FindElement(DoubleLinkedList L, ElemType e) {Node *p L-next; // 从第一个节点开始遍历int index 1; // 记录元素的索引位置// 遍历链表查找目标元素while (p ! L) {if (p-data e) {return index; // 返回元素的索引位置}p p-next; // 移动到下一个节点index; // 索引位置加1}return -1; // 如果未找到返回-1 }5. 打印链表 遍历并打印双向链表中的所有元素。 // 打印链表中的所有元素 void DisplayList(DoubleLinkedList L) {Node *p L-next; // 从第一个节点开始遍历while (p ! L) {printf(%d , p-data); // 输出当前节点的数据域p p-next; // 移动到下一个节点}printf(\n); }主函数示例 // 主函数 int main() {DoubleLinkedList L InitDoubleList(); // 初始化双向链表// 插入一些元素到链表中InsertTail(L, 10);InsertTail(L, 20);InsertTail(L, 30);InsertTail(L, 40);// 打印链表中的所有元素printf(链表中的元素);DisplayList(L);// 查找指定元素ElemType target 30;int index FindElement(L, target);if (index ! -1) {printf(元素 %d 在链表中的位置是 %d\n, target, index);} else {printf(链表中不存在元素 %d\n, target);}// 删除指定元素DeleteElement(L, 30);// 打印删除后的链表printf(删除后的链表);DisplayList(L);return 0; } 总结 比较项目顺序表链表存储方式顺序存储用一段连续的内存空间存储数据元素。链式存储通过指针将各个数据元素链接起来。随机访问支持随机访问可以在 O (1) 时间内访问任意位置的元素。不支持随机访问访问特定位置元素需要从链表头开始遍历时间复杂度为 O (n)。插入和删除操作在中间位置插入和删除元素时需要移动大量元素时间复杂度为 O (n)。在中间位置插入和删除元素只需修改指针时间复杂度为 O (1)。内存占用需要预先分配连续的内存空间如果空间不足需要进行扩容可能导致大量数据的移动空间较为紧凑没有额外指针占用。按需分配内存不会出现内存浪费但每个节点都需要额外的指针空间相对来说空间占用可能稍大。空间复杂度如果预先分配的空间过大可能会造成空间浪费如果空间不足进行扩容也会有一定开销。一般为 O (n)。每个节点都需要额外指针空间开销相对稳定。一般也为 O (n)。适用场景适合频繁访问元素而插入和删除操作较少的情况。适合频繁进行插入和删除操作的情况。 比较项目单链表循环链表单向循环链表双向循环链表存储方式通过指针将各个数据元素链接起来尾节点指向 NULL。首尾相接形成环状结构。与循环链表类似只是单向循环链表更强调其单向性。通过两个指针分别指向前驱和后继首尾相接形成环状结构。遍历方式从链表头开始顺着指针依次访问每个节点直到尾节点指向 NULL。从链表中任意一个节点开始顺着指针可以循环访问所有节点。与循环链表类似单向遍历。从链表中任意一个节点开始可以顺着指针向前或向后循环访问所有节点。随机访问不支持随机访问访问特定位置元素需要从链表头开始遍历时间复杂度为 O (n)。不支持随机访问时间复杂度为 O (n)。不支持随机访问时间复杂度为 O (n)。不支持随机访问时间复杂度为 O (n)。插入操作在中间位置插入元素需修改前后节点的指针时间复杂度为 O (1)已知插入位置的情况下。在中间位置插入元素需修改前后节点的指针时间复杂度为 O (1)已知插入位置的情况下。与循环链表类似时间复杂度为 O (1)。在中间位置插入元素需修改前后节点的指针时间复杂度为 O (1)已知插入位置的情况下。删除操作在中间位置删除元素需修改前后节点的指针时间复杂度为 O (1)已知删除位置的情况下。在中间位置删除元素需修改前后节点的指针时间复杂度为 O (1)已知删除位置的情况下。与循环链表类似时间复杂度为 O (1)。在中间位置删除元素需修改前后节点的指针时间复杂度为 O (1)已知删除位置的情况下。适用场景适用于插入和删除操作相对较少对遍历顺序没有特殊要求的情况。适用于需要循环遍历的场景如某些算法中需要反复遍历链表。与循环链表类似在需要单向循环遍历的场景中适用。适用于需要双向遍历以及频繁在链表中进行插入和删除操