数据结构---线性表

server/2025/2/4 2:35:02/

线性表

顺序表

线性表的顺序存储结构是一种随机存取的存储结构，即通过首地址和元素序号可以在O(1)时间内找到指定的元素。由于线性表的长度可变，且所需最大存储空间随问题的不同而不同，在C/C++中常用动态分配的一维数组(vector)表示线性表
在这里插入图片描述
代码示例如下：

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100  // 定义顺序表的最大长度// 定义顺序表结构
typedef struct {int data[MAX_SIZE];  // 存储数据元素的数组int length;          // 当前顺序表的长度
} SeqList;// 初始化顺序表
void InitList(SeqList *L) {L->length = 0;  // 初始化长度为 0
}// 插入操作
int InsertList(SeqList *L, int i, int e) {// 判断插入位置是否合法if (i < 1 || i > L->length + 1) {printf("插入位置不合法！\n");return 0;  // 插入失败}// 判断顺序表是否已满if (L->length >= MAX_SIZE) {printf("顺序表已满，无法插入！\n");return 0;  // 插入失败}// 将第 i 个位置及之后的元素后移for (int j = L->length; j >= i; j--) {L->data[j] = L->data[j - 1];}// 插入新元素L->data[i - 1] = e;L->length++;  // 长度加 1return 1;     // 插入成功
}// 删除操作
int DeleteList(SeqList *L, int i, int *e) {// 判断删除位置是否合法if (i < 1 || i > L->length) {printf("删除位置不合法！\n");return 0;  // 删除失败}// 返回被删除的元素*e = L->data[i - 1];// 将第 i 个位置之后的元素前移for (int j = i; j < L->length; j++) {L->data[j - 1] = L->data[j];}L->length--;  // 长度减 1return 1;     // 删除成功
}// 查找操作
int LocateElem(SeqList L, int e) {for (int i = 0; i < L.length; i++) {if (L.data[i] == e) {return i + 1;  // 返回元素位置（从 1 开始）}}return 0;  // 未找到
}// 获取元素操作
int GetElem(SeqList L, int i, int *e) {// 判断位置是否合法if (i < 1 || i > L.length) {printf("位置不合法！\n");return 0;  // 获取失败}*e = L.data[i - 1];  // 返回元素值return 1;            // 获取成功
}// 打印顺序表
void PrintList(SeqList L) {printf("顺序表中的元素为：");for (int i = 0; i < L.length; i++) {printf("%d ", L.data[i]);}printf("\n");
}// 主函数测试
int main() {SeqList L;InitList(&L);  // 初始化顺序表// 插入元素InsertList(&L, 1, 10);InsertList(&L, 2, 20);InsertList(&L, 3, 30);PrintList(L);  // 打印顺序表// 查找元素int pos = LocateElem(L, 20);if (pos) {printf("元素 20 的位置是：%d\n", pos);} else {printf("未找到元素 20\n");}// 删除元素int e;if (DeleteList(&L, 2, &e)) {printf("删除的元素是：%d\n", e);}PrintList(L);  // 打印顺序表// 获取元素int value;if (GetElem(L, 1, &value)) {printf("第 1 个元素是：%d\n", value);}return 0;
}

链表

链式存储是一种用一组任意的存储单元来存储线性表中数据元素的方法。采用这种方式存储的线性表简称为线性链表。这些存储单元可以是连续的，也可以是不连续的，甚至可以零散分布在内存中的任意位置。因此，链表中结点的逻辑顺序和物理顺序不一定相同。

为了正确表示结点之间的逻辑关系，在存储每个结点数据的同时，还必须存储其直接后继结点的地址（或位置），这部分信息称为指针（pointer）或链（link）。数据域和指针域共同组成了链表中的结点结构。

单链表：

链表通过每个结点的指针域，将线性表的 n 个结点按照逻辑次序链接在一起。如果每个结点只包含一个指针域，则称为单链表。单链表的指针域指向其后继结点，从而形成一种单向的逻辑链接关系

首元结点：链表中存储第一个数据元素的结点
头指针：通常使用“头指针”来标识一个链表，如单链表L，头指针为NULL的时表示一个空链表。链表非空时，头指针指向的是第一个结点的存储位置。

L->next==NULL;//带头结点的单链表为空时
L=NULL;//不带头结点的单链表为空时

头结点：在单链表的第一个结点之前附加一个结点，称为头结点。头结点的Data域可以不设任何信息，也可以记录表长等相关信息。若链表是带有头结点的，则头指针指向头结点的存储位置。
（无论是否有头结点，头指针始终指向链表的第一个结点。如果有头结点，头指针就指向头结点（只不过头结点的数据域可能为空而已）。）在这里插入图片描述
链表的基本操作示意图
在这里插入图片描述
在这里插入图片描述

//链表
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct Node {int data;struct Node* next;
} Node;// 创建新节点
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));if (!newNode) {printf("Memory allocation failed\n");exit(1);}newNode->data = data;newNode->next = NULL;return newNode;
}// 在链表头部插入节点
void insertAtHead(Node** head, int data) {Node* newNode = createNode(data);newNode->next = *head;*head = newNode;
}// 在链表尾部插入节点
void insertAtTail(Node** head, int data) {Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;return;}Node* temp = *head;while (temp->next != NULL) {temp = temp->next;}temp->next = newNode;
}// 删除指定值的节点
void deleteNode(Node** head, int key) {Node* temp = *head;Node* prev = NULL;// 如果头节点就是要删除的节点if (temp != NULL && temp->data == key) {*head = temp->next;free(temp);return;}// 查找要删除的节点while (temp != NULL && temp->data != key) {prev = temp;temp = temp->next;}// 如果没有找到要删除的节点if (temp == NULL) return;// 从链表中移除节点prev->next = temp->next;free(temp);
}// 打印链表
void printList(Node* head) {Node* temp = head;while (temp != NULL) {printf("%d -> ", temp->data);temp = temp->next;}printf("NULL\n");
}// 释放链表内存
void freeList(Node* head) {Node* temp;while (head != NULL) {temp = head;head = head->next;free(temp);}
}int main() {Node* head = NULL;insertAtHead(&head, 3);insertAtHead(&head, 2);insertAtHead(&head, 1);insertAtTail(&head, 4);insertAtTail(&head, 5);printf("Initial list: ");printList(head);deleteNode(&head, 3);printf("After deleting node with value 3: ");printList(head);freeList(head);return 0;
}

循环链表

循环链表（Circular Linked List）：是一种头尾相接的链表。其特点是最后一个节点的指针域指向链表的头结点，整个链表的指针域连接成一个环。
从循环链表的任意一个节点出发都可以找到链表中的其他节点，使得表处理更加方便灵活。
在这里插入图片描述
1.判断是否是空链表：head->next==head

2.判断是否是表尾节点：p->next==head

#include <stdio.h>
#include <stdlib.h>// 定义循环链表的结点结构
typedef struct Node {int data;           // 数据域struct Node *next;  // 指针域，指向下一个结点
} Node, *CircularLinkedList;// 初始化循环链表
void InitList(CircularLinkedList *L) {*L = (CircularLinkedList)malloc(sizeof(Node));  // 创建头结点(*L)->next = *L;  // 头结点的指针域指向自身，形成循环
}// 插入操作：在循环链表的第 i 个位置插入元素 e
int InsertList(CircularLinkedList L, int i, int e) {Node *p = L;int j = 0;// 找到第 i-1 个结点while (p->next != L && j < i - 1) {p = p->next;j++;}// 判断插入位置是否合法if (j != i - 1) {printf("插入位置不合法！\n");return 0;  // 插入失败}// 创建新结点Node *s = (Node *)malloc(sizeof(Node));s->data = e;// 插入新结点s->next = p->next;p->next = s;return 1;  // 插入成功
}// 删除操作：删除循环链表中第 i 个位置的元素，并将其值返回
int DeleteList(CircularLinkedList L, int i, int *e) {Node *p = L;int j = 0;// 找到第 i-1 个结点while (p->next != L && j < i - 1) {p = p->next;j++;}// 判断删除位置是否合法if (p->next == L || j != i - 1) {printf("删除位置不合法！\n");return 0;  // 删除失败}// 删除结点Node *q = p->next;*e = q->data;p->next = q->next;free(q);  // 释放被删除结点的内存return 1;  // 删除成功
}// 查找操作：查找循环链表中第一个值为 e 的元素的位置
int LocateElem(CircularLinkedList L, int e) {Node *p = L->next;int pos = 1;// 遍历链表while (p != L) {if (p->data == e) {return pos;  // 返回元素位置}p = p->next;pos++;}return 0;  // 未找到
}// 获取元素操作：获取循环链表中第 i 个位置的元素
int GetElem(CircularLinkedList L, int i, int *e) {Node *p = L->next;int j = 1;// 遍历链表while (p != L && j < i) {p = p->next;j++;}// 判断位置是否合法if (p == L || j > i) {printf("位置不合法！\n");return 0;  // 获取失败}*e = p->data;  // 返回元素值return 1;      // 获取成功
}// 打印循环链表
void PrintList(CircularLinkedList L) {Node *p = L->next;printf("循环链表中的元素为：");while (p != L) {printf("%d ", p->data);p = p->next;}printf("\n");
}// 主函数测试
int main() {CircularLinkedList L;InitList(&L);  // 初始化循环链表// 插入元素InsertList(L, 1, 10);InsertList(L, 2, 20);InsertList(L, 3, 30);PrintList(L);  // 打印循环链表// 查找元素int pos = LocateElem(L, 20);if (pos) {printf("元素 20 的位置是：%d\n", pos);} else {printf("未找到元素 20\n");}// 删除元素int e;if (DeleteList(L, 2, &e)) {printf("删除的元素是：%d\n", e);}PrintList(L);  // 打印循环链表// 获取元素int value;if (GetElem(L, 1, &value)) {printf("第 1 个元素是：%d\n", value);}return 0;
}

双向链表

双向链表（Double Linkedd List）:指的是构成链表的每个节点中设立两个指针域：一个指向其直接前驱的指针域prior，一个指向其直接后继的指针域next。这样形成的链表中有两个方向不同的链，故称为双向链表。
将头结点和尾节点连接起来也能构成循环链表，并称之为双向循环链表。
在这里插入图片描述
在这里插入图片描述

#include <stdio.h>
#include <stdlib.h>// 定义双向链表的结点结构
typedef struct Node {int data;               // 数据域struct Node *prev;      // 前驱指针struct Node *next;      // 后继指针
} Node, *DoublyLinkedList;// 初始化双向链表
void InitList(DoublyLinkedList *L) {*L = (DoublyLinkedList)malloc(sizeof(Node));  // 创建头结点(*L)->prev = *L;  // 头结点的前驱指向自身(*L)->next = *L;  // 头结点的后继指向自身
}// 插入操作：在双向链表的第 i 个位置插入元素 e
int InsertList(DoublyLinkedList L, int i, int e) {Node *p = L;int j = 0;// 找到第 i-1 个结点while (p->next != L && j < i - 1) {p = p->next;j++;}// 判断插入位置是否合法if (j != i - 1) {printf("插入位置不合法！\n");return 0;  // 插入失败}// 创建新结点Node *s = (Node *)malloc(sizeof(Node));s->data = e;// 插入新结点s->next = p->next;s->prev = p;p->next->prev = s;p->next = s;return 1;  // 插入成功
}// 删除操作：删除双向链表中第 i 个位置的元素，并将其值返回
int DeleteList(DoublyLinkedList L, int i, int *e) {Node *p = L->next;int j = 1;// 找到第 i 个结点while (p != L && j < i) {p = p->next;j++;}// 判断删除位置是否合法if (p == L || j > i) {printf("删除位置不合法！\n");return 0;  // 删除失败}// 删除结点*e = p->data;p->prev->next = p->next;p->next->prev = p->prev;free(p);  // 释放被删除结点的内存return 1;  // 删除成功
}// 查找操作：查找双向链表中第一个值为 e 的元素的位置
int LocateElem(DoublyLinkedList L, int e) {Node *p = L->next;int pos = 1;// 遍历链表while (p != L) {if (p->data == e) {return pos;  // 返回元素位置}p = p->next;pos++;}return 0;  // 未找到
}// 获取元素操作：获取双向链表中第 i 个位置的元素
int GetElem(DoublyLinkedList L, int i, int *e) {Node *p = L->next;int j = 1;// 遍历链表while (p != L && j < i) {p = p->next;j++;}// 判断位置是否合法if (p == L || j > i) {printf("位置不合法！\n");return 0;  // 获取失败}*e = p->data;  // 返回元素值return 1;      // 获取成功
}// 打印双向链表
void PrintList(DoublyLinkedList L) {Node *p = L->next;printf("双向链表中的元素为：");while (p != L) {printf("%d ", p->data);p = p->next;}printf("\n");
}// 主函数测试
int main() {DoublyLinkedList L;InitList(&L);  // 初始化双向链表// 插入元素InsertList(L, 1, 10);InsertList(L, 2, 20);InsertList(L, 3, 30);PrintList(L);  // 打印双向链表// 查找元素int pos = LocateElem(L, 20);if (pos) {printf("元素 20 的位置是：%d\n", pos);} else {printf("未找到元素 20\n");}// 删除元素int e;if (DeleteList(L, 2, &e)) {printf("删除的元素是：%d\n", e);}PrintList(L);  // 打印双向链表// 获取元素int value;if (GetElem(L, 1, &value)) {printf("第 1 个元素是：%d\n", value);}return 0;
}

有时候，白纸一张更能呈现无尽可能。 —《帕特森》


http://www.ppmy.cn/server/164776.html

相关文章

【人工智能学习笔记 一】 AI分层架构、基本概念分类与产品技术架构

【人工智能学习笔记 一】 AI分层架构、基本概念分类与产品技术架构

新的一年2025要对AI以及LLM有个强化的学习&#xff0c;所以第一篇先对整体有个大概的认知&#xff0c;一直分不清LLM和AI的关系&#xff0c;在整个体系里的位置&#xff0c;以及AIGC是什么东西&#xff0c;AI AGENT类似豆包等和大语言模型的具体关系是什么&#xff0c;整个AI的…
阅读更多...
实现智能教室能耗监测与管理系统的详细方案

实现智能教室能耗监测与管理系统的详细方案

以下是一个完整的实现智能教室能耗监测与管理系统的详细方案，涵盖深度学习模型研发、教室场景适应性分析、系统架构设计、前端展示、后端服务以及测试评估等方面，使用 Python 语言完成。 1. 深度学习模型研发 1.1 数据准备 首先，你需要收集大量的教室照片，并对其中的关键…
阅读更多...
JavaScript 基础 - 7

JavaScript 基础 - 7

关于JS函数部分的学习和一个案例的练习 1 函数封装 抽取相同部分代码封装 优点 提高代码复用性&#xff1a;封装好的函数可以在多个地方被重复调用&#xff0c;避免了重复编写相同的代码。例如&#xff0c;编写一个计算两个数之和的函数&#xff0c;在多个不同的计算场景中都…
阅读更多...
解决MacOS安装软件时提示“打不开xxx软件，因为Apple无法检查其是否包含恶意软件”的问题

解决MacOS安装软件时提示“打不开xxx软件，因为Apple无法检查其是否包含恶意软件”的问题

macOS 系统中如何开启“任何来源”以解决安装报错问题&#xff1f; 大家好&#xff01;今天我们来聊聊在使用 macOS 系统 时&#xff0c;遇到安装应用软件时出现报错的情况。这种情况常常发生在安装一些来自第三方开发者的应用时&#xff0c;因为 macOS 会默认阻止不明开发者的…
阅读更多...
使用飞书群机器人监控服务器GPU使用率

使用飞书群机器人监控服务器GPU使用率

目标&#xff1a;如果服务器GPU空置&#xff0c;可以及时推送消息到飞书群。 其他类似的监控目标也可以修改代码实现。 步骤&#xff1a; (1) 首先在群聊设置加入机器人&#xff0c;复制webhook_url (2) 在服务器后台运行如下代码。注意替换webhook_url """…
阅读更多...
Java面试题2025-并发编程基础（多线程、锁、阻塞队列）

Java面试题2025-并发编程基础（多线程、锁、阻塞队列）

并发编程 一、线程的基础概念 一、基础概念 1.1 进程与线程A 什么是进程&#xff1f; 进程是指运行中的程序。 比如我们使用钉钉&#xff0c;浏览器&#xff0c;需要启动这个程序&#xff0c;操作系统会给这个程序分配一定的资源&#xff08;占用内存资源&#xff09;。 …
阅读更多...
DeepSeek 云端部署，释放无限 AI 潜力！

DeepSeek 云端部署，释放无限 AI 潜力！

1.简介 目前&#xff0c;OpenAI、Anthropic、Google 等公司的大型语言模型&#xff08;LLM&#xff09;已广泛应用于商业和私人领域。自 ChatGPT 推出以来&#xff0c;与 AI 的对话变得司空见惯&#xff0c;对我而言没有 LLM 几乎无法工作。 国产模型「DeepSeek-R1」的性能与…
阅读更多...
LeetCode - #195 Swift 实现打印文件中的第十行

LeetCode - #195 Swift 实现打印文件中的第十行

网罗开发 &#xff08;小红书、快手、视频号同名&#xff09; 大家好&#xff0c;我是 展菲&#xff0c;目前在上市企业从事人工智能项目研发管理工作&#xff0c;平时热衷于分享各种编程领域的软硬技能知识以及前沿技术&#xff0c;包括iOS、前端、Harmony OS、Java、Python等…
阅读更多...
最新文章

Copyright @ 2022~2023