数据结构期末复习(2)链表

链表

链表(Linked List)是一种常见的数据结构,用于存储一系列具有相同类型的元素。链表由节点(Node)组成,每个节点包含两部分:数据域(存储元素值)和指针域(指向下一个节点)。通过节点之间的指针连接,形成一个链式结构。

链表可以分为单向链表和双向链表两种类型。在单向链表中,每个节点只有一个指针,指向下一个节点;而在双向链表中,每个节点有两个指针,分别指向前一个节点和后一个节点。

链表的优点是插入和删除操作的时间复杂度为O(1),而不受数据规模的影响。但是,访问链表中的特定元素需要从头开始遍历链表,时间复杂度为O(n),其中n是链表的长度。

链表在实际应用中有广泛的用途,比如实现栈、队列、哈希表等数据结构,以及解决一些特定的问题,如反转链表、合并有序链表等。

需要注意的是,在使用链表时,我们需要额外的空间来存储指针,因此链表对内存的利用率较低。同时,在频繁插入和删除操作较多,而对访问操作要求不高的情况下,链表是一个较为合适的选择。
在这里插入图片描述
单链表(Singly Linked List)是一种常见的链表结构,由一系列节点按顺序连接而成。每个节点包含两个部分:数据域(存储元素值)和指针域(指向下一个节点)。最后一个节点的指针域指向空(NULL)。

以下是单链表的基本结构:

Node:- 数据域(Data): 存储元素值- 指针域(Next): 指向下一个节点LinkedList:- 头指针(Head): 指向链表的第一个节点

单链表的头指针(Head)用于标识链表的起始位置。通过头指针,可以遍历整个链表,或者在链表中插入、删除节点。

单链表的特点是每个节点只有一个指针域,指向下一个节点,最后一个节点的指针域为空。这意味着,在单链表中,只能从前往后遍历,无法直接访问前一个节点,因此对于某些操作,比如在给定节点之前插入一个新节点,需要额外的操作来处理指针。

需要注意的是,单链表中的节点可以动态地分配内存,这意味着可以根据需求灵活地扩展或缩小链表的长度。

下面是一个示例单链表的结构:

Head -> Node1 -> Node2 -> Node3 -> ... -> NULL

其中,Head是头指针,Node1、Node2、Node3等为节点,箭头表示指针域的指向关系,NULL表示链表的结束。

单链表的操作包括插入节点、删除节点、查找节点、遍历链表等,这些操作可以根据具体需求进行实现。

在这里插入图片描述
题1.若线性表采用链式存储,则表中各元素的存储地址()。
A.必须是连续的
B.部分地址是连续的
C.一定是不连续的
D.不一定是连续的
答案:D
题2.单链表中,增加一个头结点的目的是为了()。
A.使单链表至少有一个结点
B.标识表结点中首结点的位置
C.方便运算的实现
D.说明单链表是线性表的链式存储
答案:C

题1的答案是D. 不一定是连续的。

如果线性表采用链式存储方式,表中各元素的存储地址不需要连续。链式存储通过节点之间的指针连接,每个节点可以分配在内存的任意位置。节点的指针域存储着下一个节点的地址,通过指针的链接,实现了元素之间的逻辑关系。

题2的答案是C. 方便运算的实现。

增加一个头结点的目的是为了方便对单链表进行操作和实现一些常用的操作,如插入、删除、查找等。头结点不存储具体的数据,它的存在主要是为了简化操作,使得对链表的操作更加统一和方便。头结点可以作为操作的起点,避免了对空链表的特殊处理,提高了代码的可读性和可维护性。

引入头结点后,可以带来两个优点:
①由于第一个数据结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作和在表的其他位置上的操作一致,无需进行特殊处理。
②无论链表是否为空,其头指针都指向头结点的非空指针(空表中头结点的指针域为空)。

单链表的实现

以下是单链表的详细实现示例(使用C语言):

  1. 定义节点结构(Node):
struct Node {int data;struct Node *next;
};
  1. 定义链表结构(LinkedList):
struct LinkedList {struct Node *head;
};
  1. 实现插入操作:
void insert(struct LinkedList *list, int data) {struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));  // 创建新节点new_node->data = data;new_node->next = NULL;if (list->head == NULL) {  // 如果链表为空,将新节点设为头节点list->head = new_node;} else {struct Node *current = list->head;while (current->next != NULL) {  // 遍历到最后一个节点current = current->next;}current->next = new_node;  // 将新节点插入在最后一个节点之后}
}
  1. 实现删除操作:
void delete(struct LinkedList *list, int target) {if (list->head == NULL) {  // 如果链表为空,无法删除return;}if (list->head->data == target) {  // 如果要删除的节点是头节点struct Node *temp = list->head;list->head = list->head->next;free(temp);} else {struct Node *current = list->head;while (current->next != NULL && current->next->data != target) {  // 查找要删除节点的前一个节点current = current->next;}if (current->next != NULL) {  // 找到要删除的节点struct Node *temp = current->next;current->next = current->next->next;free(temp);}}
}
  1. 实现查找操作:
int search(struct LinkedList *list, int target) {struct Node *current = list->head;while (current != NULL) {if (current->data == target) {  // 找到匹配的节点return 1;}current = current->next;}return 0;  // 遍历完链表未找到匹配的节点
}
  1. 实现遍历操作:
void traverse(struct LinkedList *list) {struct Node *current = list->head;while (current != NULL) {printf("%d ", current->data);  // 访问节点的数据域current = current->next;}
}

这是一个简单的单链表实现示例。由于C语言需要手动管理内存,因此在使用malloc函数分配内存时需要检查是否分配成功,并在删除节点时需要使用free函数释放内存。您可以根据这个示例进行自定义扩展和适应具体需求。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
有

双链表

在这里插入图片描述

双链表(Doubly Linked List)是一种常见的数据结构,它与单链表相比,在每个节点中都有两个指针,分别指向前一个节点和后一个节点,因此可以实现双向遍历。这使得在双链表中插入、删除节点等操作更加高效。

下面是一个更详细的双链表的 C 代码实现:

#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");exit(1);}newNode->data = data;newNode->prev = NULL;newNode->next = NULL;return newNode;
}// 在链表头部插入节点
void insertFront(Node** head, int data) {Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;} else {newNode->next = *head;(*head)->prev = newNode;*head = newNode;}
}// 在链表末尾插入节点
void insertEnd(Node** head, int data) {Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;} else {Node* curr = *head;while (curr->next != NULL) {curr = curr->next;}curr->next = newNode;newNode->prev = curr;}
}// 在指定位置插入节点
void insertAt(Node** head, int data, int position) {if (position < 1) {printf("无效的位置\n");return;}if (position == 1) {insertFront(head, data);return;}Node* newNode = createNode(data);Node* curr = *head;int count = 1;while (count < position - 1 && curr != NULL) {curr = curr->next;count++;}if (curr == NULL) {printf("无效的位置\n");return;}newNode->next = curr->next;newNode->prev = curr;if (curr->next != NULL) {curr->next->prev = newNode;}curr->next = newNode;
}// 删除链表头部节点
void deleteFront(Node** head) {if (*head == NULL) {printf("链表为空\n");return;}Node* temp = *head;*head = (*head)->next;if (*head != NULL) {(*head)->prev = NULL;}free(temp);
}// 删除链表末尾节点
void deleteEnd(Node** head) {if (*head == NULL) {printf("链表为空\n");return;}Node* curr = *head;while (curr->next != NULL) {curr = curr->next;}if (curr->prev != NULL) {curr->prev->next = NULL;} else {*head = NULL;}free(curr);
}// 删除指定位置节点
void deleteAt(Node** head, int position) {if (*head == NULL || position < 1) {printf("无效的位置\n");return;}if (position == 1) {deleteFront(head);return;}Node* curr = *head;int count = 1;while (count < position && curr != NULL) {curr = curr->next;count++;}if (curr == NULL) {printf("无效的位置\n");return;}if (curr->prev != NULL) {curr->prev->next = curr->next;} else {*head = curr->next;}if (curr->next != NULL) {curr->next->prev = curr->prev;}free(curr);
}// 打印链表
void printList(Node* head) {Node* curr = head;while (curr != NULL) {printf("%d ", curr->data);curr = curr->next;}printf("\n");
}int main() {Node* head = NULL;// 插入节点insertFront(&head, 1);insertEnd(&head, 2);insertEnd(&head, 3);insertAt(&head, 4, 2);// 打印链表printf("双链表:");printList(head);// 删除节点deleteFront(&head);deleteEnd(&head);deleteAt(&head, 1);// 打印链表printf("删除节点后的双链表:");printList(head);return 0;
}

这段代码实现了双链表的创建节点、在链表头部、末尾和指定位置插入节点,以及删除链表头部、末尾和指定位置节点,并且可以打印链表。你可以根据自己的需求进行扩展和修改。

双链表的插入操作

在这里插入图片描述

双链表的插入操作有三种情况:

  1. 在链表头部插入节点
  2. 在链表末尾插入节点
  3. 在指定位置插入节点

下面是这三种情况的详细说明和代码实现。

  1. 在链表头部插入节点

在链表头部插入节点,只需要将新节点插入到原头节点前面,并更新头节点的指针。

void insertFront(Node** head, int data) {Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;} else {newNode->next = *head;(*head)->prev = newNode;*head = newNode;}
}
  1. 在链表末尾插入节点

在链表末尾插入节点,需要遍历整个链表,找到最后一个节点,并将新节点插入到最后一个节点后面。

void insertEnd(Node** head, int data) {Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;} else {Node* curr = *head;while (curr->next != NULL) {curr = curr->next;}curr->next = newNode;newNode->prev = curr;}
}
  1. 在指定位置插入节点

在指定位置插入节点,需要遍历链表,找到指定位置的节点,并将新节点插入到该节点的前面,并更新相邻节点的指针。

void insertAt(Node** head, int data, int position) {if (position < 1) {printf("无效的位置\n");return;}if (position == 1) {insertFront(head, data);return;}Node* newNode = createNode(data);Node* curr = *head;int count = 1;while (count < position - 1 && curr != NULL) {curr = curr->next;count++;}if (curr == NULL) {printf("无效的位置\n");return;}newNode->next = curr->next;newNode->prev = curr;if (curr->next != NULL) {curr->next->prev = newNode;}curr->next = newNode;
}

注意,如果指定位置为1,则直接调用insertFront()函数插入节点。如果指定位置大于链表长度,则插入失败,输出错误信息。

上述代码中,createNode()函数创建一个新节点,Node** head表示指向头节点指针的指针,因为在插入操作中需要修改头节点指针的值,而头节点指针本身是一个指针变量,所以需要使用指向指针的指针来实现修改。

双链表的删除操作

在这里插入图片描述

双链表的删除操作有三种情况:

  1. 删除链表头部节点
  2. 删除链表末尾节点
  3. 删除指定位置节点

下面是这三种情况的详细说明和代码实现。

  1. 删除链表头部节点

删除链表头部节点,只需要将头节点的下一个节点作为新的头节点,并释放原头节点的内存。

void deleteFront(Node** head) {if (*head == NULL) {printf("链表为空\n");return;}Node* temp = *head;*head = (*head)->next;if (*head != NULL) {(*head)->prev = NULL;}free(temp);
}
  1. 删除链表末尾节点

删除链表末尾节点,需要遍历整个链表,找到最后一个节点,并将倒数第二个节点的next指针置为NULL,并释放最后一个节点的内存。

void deleteEnd(Node** head) {if (*head == NULL) {printf("链表为空\n");return;}Node* curr = *head;while (curr->next != NULL) {curr = curr->next;}if (curr->prev != NULL) {curr->prev->next = NULL;} else {*head = NULL;}free(curr);
}
  1. 删除指定位置节点

删除指定位置节点,需要遍历链表,找到指定位置的节点,更新相邻节点的指针,并释放目标节点的内存。

void deleteAt(Node** head, int position) {if (*head == NULL || position < 1) {printf("无效的位置\n");return;}if (position == 1) {deleteFront(head);return;}Node* curr = *head;int count = 1;while (count < position && curr != NULL) {curr = curr->next;count++;}if (curr == NULL) {printf("无效的位置\n");return;}if (curr->prev != NULL) {curr->prev->next = curr->next;} else {*head = curr->next;}if (curr->next != NULL) {curr->next->prev = curr->prev;}free(curr);
}

注意,如果指定位置为1,则直接调用deleteFront()函数删除头部节点。如果指定位置大于链表长度,则删除失败,输出错误信息。

上述代码中,Node** head表示指向头节点指针的指针,因为在删除操作中需要修改头节点指针的值,而头节点指针本身是一个指针变量,所以需要使用指向指针的指针来实现修改。

循环链表

在这里插入图片描述
循环链表是一种特殊的链表,它与普通链表的区别在于,最后一个节点的next指针不是指向NULL,而是指向第一个节点,从而形成一个环形结构。

循环链表有两种基本类型:单向循环链表和双向循环链表。单向循环链表中每个节点只有一个指针域,即指向下一个节点的指针,而双向循环链表中每个节点有两个指针域,即分别指向前一个节点和后一个节点的指针。

下面是一个单向循环链表的定义:

typedef struct Node {int data;struct Node* next;
} Node;typedef struct CircularLinkedList {Node* head;
} CircularLinkedList;

在单向循环链表中,头节点的next指针指向第一个节点,而最后一个节点的next指针则指向头节点。

循环链表的插入和删除操作与普通链表类似,唯一的区别是在插入和删除末尾节点时需要特殊处理,因为末尾节点的next指针指向头节点而非NULL

下面是一个简单的单向循环链表的插入和删除操作的示例代码:

// 创建新节点
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;return newNode;
}// 在链表末尾插入节点
void insertEnd(CircularLinkedList* list, int data) {Node* newNode = createNode(data);if (list->head == NULL) {list->head = newNode;newNode->next = list->head;} else {Node* curr = list->head;while (curr->next != list->head) {curr = curr->next;}curr->next = newNode;newNode->next = list->head;}
}// 删除指定位置的节点
void deleteAt(CircularLinkedList* list, int position) {if (list->head == NULL) {printf("链表为空\n");return;}Node* curr = list->head;Node* prev = NULL;int count = 1;while (count < position && curr->next != list->head) {prev = curr;curr = curr->next;count++;}if (count < position) {printf("无效的位置\n");return;}if (prev == NULL) {Node* tail = list->head;while (tail->next != list->head) {tail = tail->next;}list->head = curr->next;tail->next = list->head;} else {prev->next = curr->next;}free(curr);
}

注意,上述代码中,在删除末尾节点时需要特判。如果目标节点是头节点,则需要更新头节点指针的值,并将最后一个节点的next指针指向新的头节点。如果目标节点不是头节点,则直接更新相邻节点的指针即可。

循环链表的遍历和其他操作与普通链表类似,只需要判断是否回到了头节点即可。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/228460.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Python学习笔记之(一)搭建Python 环境

搭建Python 环境 1. 使用工具准备1.1 Python 安装1.1.1 下载Python 安装包1.1.2 安装Python 1.2 VScode 安装1.2.1 下载VScode安装包1.2.2 给VScode安装Python 扩展 2. 第一次编写Python 程序 本篇文章以Windows 系统为例。 1. 使用工具准备 1.1 Python 安装 1.1.1 下载Pytho…

双向循环链表实现C语言关键字中英翻译机 ฅ( ̳• · • ̳ฅ)

目录 1.双向循环链表的声明与定义&#xff1a; 2. 创建链表并对节点中的数据赋初值 3. 插入节点并链接 4.中英翻译 5. 小游戏的实现 6.菜单的实现 7. 释放内存 8.在主函数中用刚才定义的函数实现各种代码 输入样例&#xff1a; 实现方法&#xff1a;双向循环链表来实…

华为ensp网络设计期末测试题-复盘

网络拓扑图 地址分配表 vlan端口分配表 需求 The device is running!<Huawei>sys Enter system view, return user view with CtrlZ. [Huawei]un in en Info: Information center is disabled. [Huawei]sys S1 [S1]vlan 99 [S1-vlan99]vlan 100 [S1-vlan100]des IT [S1-…

万字长文谈自动驾驶occupancy感知

文章目录 prologuepaper listVision-based occupancy :1. [MonoScene: Monocular 3D Semantic Scene Completion [CVPR 2022]](https://arxiv.org/pdf/2112.00726.pdf)2. [Tri-Perspective View for Vision-Based 3D Semantic Occupancy Prediction [CVPR 2023]](https://arxiv…

跳跃表原理及实现

一、跳表数据结构 跳表是有序表的一种&#xff0c;其底层是通过链表实现的。链表的特点是插入删除效率高&#xff0c;但是查找节点效率很低&#xff0c;最坏的时间复杂度是O(N)&#xff0c;那么跳表就是解决这一痛点而生的。 为了提高查询效率&#xff0c;我们可以给链表加上索…

新手小白:一文带你用vite从零搭建企业级开发环境

在这工作的半年时间里&#xff0c;开始接触了前端开发&#xff0c;技术栈主要用的是 vue2&#xff0c;但是自己利用时间也学习了 vue3&#xff0c;组合式 api 和 vue3 的各种生态比 vue2 好用太多了&#xff0c;特别是状态管理库 pinia 比 vuex 简介很多&#xff0c;构建工具也…

rancher 手册

官方 https://www.rancher.com/https://github.com/rancher/rancherhttps://docs.rke2.io/ rancher kubernetesl yaml deploy rancher serverHelm Deploy Online Rancher DemoHelm & Kubernetes Offline Deploy Rancher v2.7.5 Demohelm upgrade rancher server from v2…

[Linux开发工具]——vim使用

Linux编辑器——vim的使用 一、什么是集成开发环境&#xff1f;二、什么是vim&#xff1f;三、vim的概念四、vim的基本操作五、vim命令模式命令集5.1 移动光标5.2 删除文字5.3 复制粘贴5.4 其他操作 六、vim底行模式命令集6.1 首先在命令模式下shift&#xff1b;进入末行模式。…

uni-app/vue封装etc车牌照输入,获取键盘按键键值

先看下效果如下&#xff1a; 动态图如下 uniapp的keyup获取不到keyCode和compositionstart&#xff0c;compositionend&#xff0c;所以需要监听input节点的keyup事件&#xff0c; 思路以及代码如下&#xff1a; 1.将每一个字符用文本框输入&#xff0c;代码如下 <view …

CEC2017(Python):粒子群优化算法PSO求解CEC2017(提供Python代码)

一、CEC2017简介 参考文献&#xff1a; [1]Awad, N. H., Ali, M. Z., Liang, J. J., Qu, B. Y., & Suganthan, P. N. (2016). “Problem definitions and evaluation criteria for the CEC2017 special session and competition on single objective real-parameter numer…

NullByte

信息收集 # nmap -sn 192.168.1.0/24 -oN live.nmap Starting Nmap 7.94 ( https://nmap.org ) at 2023-12-29 09:23 CST Nmap scan report for 192.168.1.1 Host is up (0.00038s latency). MAC Address: 00:50:56:C0:00:08 (VMware) Nmap scan report for …

PostgreSQL16.1(Windows版本)

1、卸载原有的PostgreSQL &#xfeff; &#xfeff; 点击Next即可。 &#xfeff;&#xfeff; 点击OK即可。 卸载完成。 2、安装 &#xff08;1&#xff09; 前两部直接Next&#xff0c;第二部可以换成自己想要安装的路径。 &#xff08;2&#xff09; 直接点击Next。…

政务大数据能力平台建设方案:文件全文30页,附下载

关键词&#xff1a;智慧政务解决方案&#xff0c;智慧政务建设&#xff0c;智慧政务服务平台&#xff0c;智慧政务大数据&#xff0c;数字政务一体化平台。大数据&#xff0c;政务大数据建设 一、智慧政务建设需求 1、政务服务需求&#xff1a;智慧政务建设需要满足人民群众的…

C++每日一练(8):图像相似度

题目描述 给出两幅相同大小的黑白图像&#xff08;用0-1矩阵&#xff09;表示&#xff0c;求它们的相似度。 说明&#xff1a;若两幅图像在相同位置上的像素点颜色相同&#xff0c;则称它们在该位置具有相同的像素点。两幅图像的相似度定义为相同像素点数占总像素点数的百分比。…

构建基础wlan网络 hcia无线

实验 旁挂组网 二层网络 ac为 dhcp的服务器给ap地址 s1给sta的ip地址 DHCP 业务为直接转发 实验步骤 第一步 poe 开启 poe en 开启 第二步 有线连接 vlan的配置 s1 vlan batch 100 101 连接的端口 port link-type trunk port trunk allow-pass …

pyDAL一个python的ORM(3)建表与表相关操作

1、建表操作define_table() 我们构建2张表&#xff0c;后面示例使用&#xff1a; db.define_table(person,#表名 Field(id, string),#字段名及字段的数据类型 Field(‘name, string), Field(‘dept, string), ) db.define_table(things, Field(id, string), Field(‘nam…

Docker之镜像上传和下载

目录 1.镜像上传 1) 先上百度搜索阿里云 点击以下图片网站 2) 进行登录/注册 3) 使用支付宝...登录 4) 登录后会跳转到首页->点击控制台 5) 点击左上角的三横杠 6) 搜索容器镜像关键词->点击箭头所指 ​ 编辑 7) 进入之后点击实例列表 8) 点击个人实例进入我们的一个…

win/linux 环境查看动态库包含的函数

我们打包了动态库&#xff0c;还要查看是否包含一些函数&#xff0c;需要导出这些函数 在win 环境下可以使用 .def 格式的文件进行操作 ######################################################### 跳过这一步&#xff0c;回到主题&#xff0c;在两个系统平台如何查看动态库包…

轻量封装WebGPU渲染系统示例<55>- 顶点数据更新

当前示例源码github地址: https://github.com/vilyLei/voxwebgpu/blob/feature/material/src/voxgpu/sample/VertexUpdateTest.ts 当前示例运行效果: ​​​​​​​ 此示例基于此渲染系统实现&#xff0c;当前示例TypeScript源码如下: export class VertexUpdateTest {pr…

2023年成都市中等职业学校学生技能大赛“网络搭建及应用”赛项竞赛样卷

2023年成都市中等职业学校学生技能大赛 “网络搭建及应用”赛项竞赛样卷 &#xff08;总分1000分&#xff09; 目录 2023年成都市中等职业学校学生技能大赛 “网络搭建及应用”赛项竞赛样卷 网络建设与调试项目&#xff08;500分&#xff09; 服务器搭建与运维项目&#xff08;…