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

线性表之链式表

news 2025/7/27 23:50:58

文章目录

主要内容

  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

http://www.lryc.cn/news/241810.html

相关文章：

  • [Docker]十.Docker Swarm讲解
  • 相机机模组需求示例
  • Uniapp 微信登录流程解析
  • 红旗Asianux Server Linux V8 安装万里数据库(GreatSQL)
  • 一文2000字使用JMeter进行接口测试教程！（建议收藏）
  • Spark---介绍及安装
  • uni-app:实现request请求的递归（设置request请求的访问次数），并且调用自定义方法给出返回值
  • 数据结构-归并排序+计数排序
  • Qml使用cpp文件的信号槽
  • 聚类笔记：HDBSCAN
  • 【Python】批量将PDG合成PDF，以及根据SS号重命名秒传的文件
  • 2023亚太杯数学建模A题思路 - 采果机器人的图像识别技术
  • 3、LeetCode之无重复字符的最长子串
  • CONDITIONS EVALUATION REPORT-解决方案
  • 计算机网络——路由
  • python+requests+pytest+allure自动化框架
  • css3
  • 超级应用平台（HAP）起航
  • cocos2dx ​​Animate3D（二）
  • 基于java技术的社区交易二手平台
  • （Matalb回归预测）GA-BP遗传算法优化BP神经网络的多维回归预测
  • 【Docker】从零开始：10.registry搭建私有仓库
  • 树莓派上使用Nginx通过内网穿透实现无公网IP访问内网本地站点
  • 长征故事vr互动教育体验系统让师生感同身受
  • 汽车级芯片NCV7518MWATXG 可编程六沟道低压侧 MOSFET预驱动器 特点、参数及应用
  • 【分布式】小白看Ring算法 - 03
  • 使用Git bash切换Gitee、GitHub多个Git账号
  • 【RtpRtcp】1： webrtc m79：audio的ChannelReceive 创建并使用
  • Ubuntu系统安装docker
  • 如何访问linux上的web服务