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

线性表之链式表

主要内容

  1. 单链表
  2. 双链表和循环链表

链式表是一种常见的数据结构,它由一系列节点组成,每个节点包含数据和指向下一个节点的指针。链式表具有灵活的插入和删除操作,但访问元素的效率较低。

一.单链表

单链表是最简单的链表结构之一。它由一系列节点组成,每个节点包含数据和指向下一个节点的指针。单链表的特点是只能从头节点开始依次访问每个节点,无法直接访问任意位置的节点。这使得单链表在插入和删除操作时效率较高,但在查找和访问特定节点时效率较低。

1.头插法建立单链表

代码如下(示例):

C语言代码:

#include <stdio.h>
#include <stdlib.h>typedef struct Node {int data;struct Node* next;
} Node;Node* createListByHeadInsert(int arr[], int n) {Node* head = (Node*)malloc(sizeof(Node));head->next = NULL;for (int i = 0; i < n; i++) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = arr[i];newNode->next = head->next;head->next = newNode;}return head;
}

Python代码:

class Node:def __init__(self, data):self.data = dataself.next = Nonedef create_list_by_head_insert(arr):head = Node(None)for data in arr:new_node = Node(data)new_node.next = head.nexthead.next = new_nodereturn head

2.尾插法建立单链表

代码如下(示例):

C语言代码:

Node* createListByTailInsert(int arr[], int n) {Node* head = (Node*)malloc(sizeof(Node));head->next = NULL;Node* tail = head;for (int i = 0; i < n; i++) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = arr[i];newNode->next = NULL;tail->next = newNode;tail = newNode;}return head;
}

Python代码:

def create_list_by_tail_insert(arr):head = Node(None)tail = headfor data in arr:new_node = Node(data)tail.next = new_nodetail = new_nodereturn head

3.按序号查找结点值

代码如下(示例):

C语言代码:

int getElemByIndex(Node* head, int index) {Node* p = head->next;int i = 1;while (p && i < index) {p = p->next;i++;}if (!p || i > index) {return -1;}return p->data;
}

Python代码:

def get_elem_by_index(head, index):p = head.nexti = 1while p and i < index:p = p.nexti += 1if not p or i > index:return -1return p.data

4.按值查找表结点

代码如下(示例):

C语言代码:

Node* locateElem(Node* head, int value) {Node* p = head->next;while (p && p->data != value) {p = p->next;}return p;
}

Python代码:

def locate_elem(head, value):p = head.nextwhile p and p.data != value:p = p.nextreturn p

5.插入节点操作

代码如下(示例):

C语言代码:

void insertElem(Node* head, int index, int value) {Node* p = head;int i = 0;while (p && i < index - 1) {p = p->next;i++;}if (!p || i > index - 1) {return;}Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = value;newNode->next = p->next;p->next = newNode;
}

Python代码:

def insert_elem(head, index, value):p = headi = 0while p and i < index - 1:p = p.nexti += 1if not p or i > index - 1:returnnew_node = Node(value)new_node.next = p.nextp.next = new_node

6.删除结点操作

代码如下(示例):

C语言代码:

void deleteElem(Node* head, int value) {Node* p = head;while (p->next && p->next->data != value) {p = p->next;}if (p->next) {Node* temp = p->next;p->next = temp->next;free(temp);}
}

Python代码:

def delete_elem(head, value):p = headwhile p.next and p.next.data != value:p = p.nextif p.next:temp = p.nextp.next = temp.nextdel temp

7.求表长操作

代码如下(示例):

C语言代码:

int getLength(Node* head) {Node* p = head->next;int length = 0;while (p) {length++;p = p->next;}return length;
}

Python代码:

def get_length(head):p = head.nextlength = 0while p:length += 1p = p.nextreturn length

二.双链表和循环链表

双链表在单链表的基础上增加了一个指向前一个节点的指针。这样一来,双链表可以双向遍历,即可以从头节点向后遍历,也可以从尾节点向前遍历。这种特性使得双链表在某些场景下具有更高的灵活性和效率。

1.双链表的插入操作

代码如下(示例):

C语言实现:

void insertNode(struct Node* prevNode, int newData) {if (prevNode == NULL) {printf("The given previous node cannot be NULL");return;}struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = newData;newNode->next = prevNode->next;prevNode->next = newNode;newNode->prev = prevNode;if (newNode->next != NULL) {newNode->next->prev = newNode;}
}

Python实现:

def insertNode(prev_node, new_data):if prev_node is None:print("The given previous node cannot be NULL")returnnew_node = Node(new_data)new_node.next = prev_node.nextprev_node.next = new_nodenew_node.prev = prev_nodeif new_node.next is not None:new_node.next.prev = new_node

2.双链表的删除操作

代码如下(示例):

C语言实现:

void deleteNode(struct Node** head_ref, struct Node* del) {if (*head_ref == NULL || del == NULL) {return;}if (*head_ref == del) {*head_ref = del->next;}if (del->next != NULL) {del->next->prev = del->prev;}if (del->prev != NULL) {del->prev->next = del->next;}free(del);
}

Python实现:

def deleteNode(head_ref, del_node):if head_ref is None or del_node is None:returnif head_ref == del_node:head_ref = del_node.nextif del_node.next is not None:del_node.next.prev = del_node.previf del_node.prev is not None:del_node.prev.next = del_node.nextdel_node = None

循环链表是一种特殊的链表结构,其尾节点指向头节点,形成一个闭环。循环链表可以用于模拟循环队列或循环缓冲区等场景,其特点是可以无限循环访问节点。

3.循环单链表

代码如下(示例):

C语言实现:

struct Node {int data;struct Node* next;
};void insertNode(struct Node** head_ref, int newData) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));struct Node* last = *head_ref;newNode->data = newData;newNode->next = *head_ref;if (*head_ref == NULL) {newNode->next = newNode;} else {while (last->next != *head_ref) {last = last->next;}last->next = newNode;}*head_ref = newNode;
}

Python实现:

class Node:def __init__(self, data):self.data = dataself.next = Nonedef insertNode(head_ref, new_data):new_node = Node(new_data)last = head_refnew_node.next = head_refif head_ref is None:new_node.next = new_nodeelse:while last.next != head_ref:last = last.nextlast.next = new_nodehead_ref = new_node

循环双链表是一种特殊的链式表,它的最后一个节点指向第一个节点,而第一个节点指向最后一个节点,形成一个循环。循环双链表可以在任意位置插入和删除节点。

4.循环双链表的插入操作

代码如下(示例):

C语言实现:

typedef struct Node {int data;struct Node* prev;struct Node* next;
} Node;void insert(Node* head, int data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->prev = head;newNode->next = head->next;head->next->prev = newNode;head->next = newNode;
}

Python实现:

class Node:def __init__(self, data):self.data = dataself.prev = Noneself.next = Nonedef insert(head, data):new_node = Node(data)new_node.prev = headnew_node.next = head.nexthead.next.prev = new_nodehead.next = new_node

5.循环双链表的删除操作

代码如下(示例):

C语言实现:

void delete(Node* node) {node->prev->next = node->next;node->next->prev = node->prev;free(node);
}

Python实现:

def delete(node):node.prev.next = node.nextnode.next.prev = node.prev

静态链表是一种使用数组来模拟链表结构的数据结构。它的特点是在静态分配的数组中维护节点的关系,而不是使用指针。静态链表在某些特定场景下可以减少指针操作的开销,但也限制了链表的动态性和灵活性。

6.静态链表的基本操作

代码如下(示例):

C语言实现:

#define MAX_SIZE 100
typedef struct {int data;int next;
} Node;int allocate(Node* arr) {int i = arr[0].next;if (i != -1) {arr[0].next = arr[i].next;}return i;
}void deallocate(Node* arr, int i) {arr[i].next = arr[0].next;arr[0].next = i;
}

Python实现:

MAX_SIZE = 100
class Node:def __init__(self, data, next):self.data = dataself.next = nextdef allocate(arr):i = arr[0].nextif i != -1:arr[0].next = arr[i].nextreturn idef deallocate(arr, i):arr[i].next = arr[0].nextarr[0].next = i

总结

以上是今天要讲的内容,学到了链式表中单链表、双链表、循环链表和静态链表的相关操作。
线性表–链式表-1

相关文章:

线性表之链式表

文章目录 主要内容一.单链表1.头插法建立单链表代码如下&#xff08;示例&#xff09;: 2.尾插法建立单链表代码如下&#xff08;示例&#xff09;: 3.按序号查找结点值代码如下&#xff08;示例&#xff09;: 4.按值查找表结点代码如下&#xff08;示例&#xff09;: 5.插入节…...

[Docker]十.Docker Swarm讲解

一.Dokcer Swarm集群介绍 1.Dokcer Swarm 简介 Docker Swarm 是 Docker 公司推出的用来管理 docker 集群的工具&#xff0c; 使用 Docker Swarm 可以快速方便的实现 高可用集群 ,Docker Compose 只能编排单节点上的容器, Docker Swarm 可以让我们在单一主机上操作来完成对 整…...

相机机模组需求示例

产品需求名称摄像头采集图片数据补充说明产品需求描述 As&#xff1a;用户 I want to&#xff1a;通过相机模组获取到自定义格式图片数据&#xff0c;要求包括&#xff1a; 1、支持多种场景&#xff0c;如&#xff1a;手持相机拍摄舌苔 2、支持图片分辨率至少达到1920X1080 3、…...

Uniapp 微信登录流程解析

本文将介绍在 Uniapp 应用中实现微信登录的流程&#xff0c;包括准备工作、授权登录、获取用户信息等步骤。 内容大纲&#xff1a; 介绍Uniapp和微信登录&#xff1a; 简要介绍 Uniapp 框架以及微信登录的重要性和流行程度。 准备工作&#xff1a; 注册微信开发者账号创建应用…...

红旗Asianux Server Linux V8 安装万里数据库(GreatSQL)

红旗Asianux Server Linux V8 安装万里数据库&#xff08;GreatSQL&#xff09; 红旗Asianux介绍&#xff1a; 红旗Asianux Server Linux 8.0是为云时代重新设计的操作系统&#xff0c;为云时代的到来引入了大量新功能&#xff0c;包括用于配置管理、快速迁移框架、编程语言和…...

一文2000字使用JMeter进行接口测试教程!(建议收藏)

安装 使用JMeter的前提需要安装JDK&#xff0c;需要JDK1.7以上版本目前在用的是JMeter5.2版本&#xff0c;大家可自行下载解压使用 运行 进入解压路径如E: \apache-jmeter-5.2\bin&#xff0c;双击jmeter.bat启动运行 启动后默认为英文版本&#xff0c;可通过Options – Cho…...

Spark---介绍及安装

一、Spark介绍 1、什么是Spark Apache Spark 是专为大规模数据处理而设计的快速通用的计算引擎。Spark是UC Berkeley AMP lab (加州大学伯克利分校的AMP实验室)所开源的类Hadoop MapReduce的通用并行计算框架&#xff0c;Spark拥有Hadoop MapReduce所具有的优点&#xff1b;但…...

uni-app:实现request请求的递归(设置request请求的访问次数),并且调用自定义方法给出返回值

一、效果展示 失败效果 成功效果 二、写入后端请求部分 分析 ①自定义一个模块common.js主要用于封装所有的请求函数 ②核心代码 function requestWithRetry(cmd, username, password, retryCount) {return new Promise((resolve, reject) > {uni.request({url: ip sys…...

数据结构-归并排序+计数排序

1.归并排序 基本思想&#xff1a; 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并&#xff0c;得到完全有序的序列&#xff1b;即先使每个子序列有序&#xff0c;再使子序列段间有序。若将两个有序表合并成一个…...

Qml使用cpp文件的信号槽

文章目录 一、C文件Demo二、使用步骤1. 初始化C文件和QML文件&#xff0c;并建立信号槽2.在qml中调用 一、C文件Demo Q_INVOKABLE是一个Qt元对象系统中的宏&#xff0c;用于将C函数暴露给QML引擎。具体来说&#xff0c;它使得在QML代码中可以直接调用C类中被标记为Q_INVOKABLE的…...

聚类笔记:HDBSCAN

1 算法介绍 DBSCAN/OPTICS层次聚类主要由以下几步组成 空间变换构建最小生成树构建聚类层次结构(聚类树)压缩聚类树提取簇 2 空间变换 用互达距离来表示两个样本点之间的距离 ——>密集区域的样本距离不受影响——>稀疏区域的样本点与其他样本点的距离被放大——>…...

【Python】批量将PDG合成PDF,以及根据SS号重命名秒传的文件

目录 说明批量zip2pdf批量zip2pdf下载SS号重命名源代码SS号重命名源代码下载附录&#xff0c;水文年鉴 说明 1、zip2pdf是一个开源软件&#xff0c;支持自动化解压压缩包成PDG&#xff0c;PDG合成PDF&#xff0c;笔者在其基础上做了部分修改&#xff0c;支持批量转换。 2、秒…...

2023亚太杯数学建模A题思路 - 采果机器人的图像识别技术

# 1 赛题 问题A 采果机器人的图像识别技术 中国是世界上最大的苹果生产国&#xff0c;年产量约为3500万吨。与此同时&#xff0c;中国也是世 界上最大的苹果出口国&#xff0c;全球每两个苹果中就有一个&#xff0c;全球超过六分之一的苹果出口 自中国。中国提出了一带一路倡议…...

3、LeetCode之无重复字符的最长子串

给定一个字符串 s &#xff0c;请你找出其中不含有重复字符的 最长子串 的长度 输入: s "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"&#xff0c;所以其长度为 3。转载&#xff1a; C常用语法——unordered_set 题目主要思想&#xff…...

CONDITIONS EVALUATION REPORT-解决方案

在启动SpringBoot项目时&#xff0c;提示一堆的Positive matches、Negative matches&#xff08;如下代码框&#xff09;,感觉像是报错了样。但用SpringBoot的Test类操作数据库的Insert是成功的。提示这些信息通过网上搜索主要讲配置类被Spring容器加载与被加载的说明。名词解释…...

计算机网络——路由

文章目录 1. 前言&#xff1a;2. 路由基础2.1. 路由的相关概念2.2. 路由的特征2.3. 路由的过程 3 路由协议3.1. 静态路由&#xff1a;3.2. 动态路由&#xff1a;3.2.1. 距离矢量协议3.2.2. OSPF协议&#xff1a;3.2.2.1.OSPF概述OSPF的工作原理路由计算功能特性 3.2.2.2.OSPF报…...

python+requests+pytest+allure自动化框架

1.核心库 requests request请求 openpyxl excel文件操作 loggin 日志 smtplib 发送邮件 configparser unittest.mock mock服务 2.目录结构 base utils testDatas conf testCases testReport logs 其他 2.1base base_path.py 存放绝对路径,dos命令或Jenkins执行…...

css3

基础 <!DOCTYPE html> <html><head><meta charset"utf-8"><title>style</title><!-- link&#xff08;外部样式&#xff09;和style&#xff08;内部样式&#xff09;优先级相同&#xff0c;重复写会覆盖 --><link re…...

超级应用平台(HAP)起航

各位明道云用户和伙伴&#xff0c; 今天&#xff0c;我们正式发布明道云10.0版本。从这个版本开始&#xff0c;我们将产品名称正式命名为超级应用平台&#xff08;Hyper Application Platform, 简称HAP&#xff09;。我们用“超级”二字表达产品在综合能力方面的突破&#xff…...

cocos2dx ​​Animate3D(二)

Twirl 扭曲旋转特效 // 持续时间(时间过后不会回到原来的样子) // 整个屏幕被分成几行几列 // 扭曲中心位置 // 扭曲的数量 // 振幅 static Twirl* create(float duration, const Size& gridSize, const Vec2& position, unsigned int twirls, float amplitude)…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...

Python网页自动化Selenium中文文档

1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API&#xff0c;让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API&#xff0c;你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...