C语言链式存储结构的详细讲解
在我们学习过顺序存储结构之后,我们会发现顺序存储结构往往会有一个内存空间有限或者内存分配过多的情况以及我们需要频繁进行插入删除操作的时候,会发现使用顺序表会很麻烦,但是,本篇文章将会教你如何使用链式存储结构,使得我们的效率提升.
它是通过通过一组任意的存储单元来存储线性表中的数据元素,为了建立各个元素之间的联系,我们需要在每一个结点后面存放一个指针域来指向此结点的后继结点,所以会建立一个结构体,一个结点由一个数据域data和一个指针域next组成
typedef struct LNode{
ElemType data;//数据域
struct LNode* next;//指针域
}LNode,*LinkList;//将struct重命名
ps:实际下面的LNode 和*LinkList可以看成
typedef struct LNode LNode;就是倒时侯声明结构体的时候可以直接使用LNode去声明而不需要使用struct LNode
#include<malloc.h>
#define Elemtype int
typedef struct LNode
{
Elemtype data;
struct LNode* next;
}LNode,*LinkList;
void InitLink(LinkList* L)
{
(*L) = (LNode*)malloc(sizeof(LNode));//初始化头结点
(*L)->next = NULL;
}
头插法就是通过先创建一个结点,然后用结点的数据域接收我们输入的数据,让每次生成的结点拼接到头结点的后面
图解
代码实现
void ListInsert(LinkList* L)
{
int input = 0;//数据域
LNode* s;
printf("请输入一个数(输入0退出):->");
scanf("%d", &input);
while (input)
{
s = (LNode*)malloc(sizeof(LNode));
s->data = input;
s->next = (*L)->next;
(*L)->next = s;
printf("请输入一个数(输入0退出):->");
scanf("%d", &input);
}
}
输出结果
采用头插法建立单链表,写入数据的顺序和生成单链表中的元素的顺序的恰恰相反的每个结点插入的时间为O(1),所以单链表的头插法可以用来解决元素逆置的问题,那么如果使用不带头结点的头插法进行结点的插入,只需要把插入的代码改为s->next = head; head =s;就可以了
头插法固然简单,但是它写入与链表元素存储的顺序不一致,如果我们想要让写入的数据和链表生成和元素的数据域顺序一致,那么就可以使用链表的尾插法进行创建链表
图解
ps:通过上面的图解我们可以看到,我们需要再初始化一个指针,让它时刻指向的是尾结点
代码实现
void ListInsertTail(LinkList* L)
{
int input = 0;
LNode* s;
LNode* r;//指向尾结点
r = (*L);
printf("请输入一个数(输入0退出):->");
scanf("%d", &input);
while (input)
{
s = (LNode*)malloc(sizeof(LNode));
s->data = input;
r->next = s;
r = s;//让r指向尾结点
printf("请输入一个数(输入0退出):->");
scanf("%d", &input);
}
}
运行结果
因为尾插法附设了一个指向表尾结点的指针,因此时间复杂度与头插法相同
因为在链式存储中不具备随机存储的功能,所以我们要查找某个结点的话,只能从表头依次向后查找
代码实现
int Get_Elem(LinkList* L,int i)
{
if (i < 1)
printf("i is overflow\n");
int j = 1;
LNode* s;
s = (*L)->next;//第一个结点
while (s != NULL && j < i)
{
s = s->next;
j++;
}
return s->data;
}
运行结果
ps:这里的位序不是下标,而是指在第几个结点,是从1开始计数的,从上图可知,我们在单链表中查找某一个元素的时间复杂度为O(n)
实现思路:首先我们需要找到要插入位序的前驱结点,然后用指针域进行连接
图解
注意:我们要先让新结点s指向结点i-1的next指向的那个结点,如果先让i-1的next指向s,会导致断链,所以此处我们要先让s的next指向结点i-1的next指向的那个结点
代码实现
void InsertNode(LinkList* L, int i)
{
if (i < 1)
{
printf("The Linklist is overflow!\n");
}
int input = 0;
int j = 1;//遍历位序
LNode* q;
q = (*L)->next;
printf("请输入你要插入的数据元素:->");
scanf("%d", &input);
LNode* s = (LNode*)malloc(sizeof(LNode));
while (q != NULL && j < i-1)//找到第i-1个元素
{
q = q->next;
j++;
}
s->data = input;
s->next = q->next;
q->next = s;
}
运行结果
实现思路也是和在第i个结点前插入结点是一样的,我们只需要先找到第i-1个结点然后通过改变指针域指向的结点,达到删除效果
图解
代码实现
void PopNode(LinkList* L, int i)
{
if (i < 1)
{
printf("The Linklist is overflow!\n");
}
int j = 1;//遍历位序
LNode* q;
q = (*L)->next;
while (q != NULL && j < i - 1)//找到第i-1个元素
{
q = q->next;
j++;
}
LNode* s = q->next;//令s为要删除的结点
q->next = s->next;
free(s);
}
运行结果
扩展: 如果要删除指定结点p,以我们上面的做法就是直接遍历链表找到p的前驱结点,然后使用删除结点的基本删除操作进行删除,其实,也可以直接通过找到p结点的的方式将p结点进行删除,实质就是将p的后继结点的数据元素赋值给p元素,从而达到删除结点的目的.
主要实现思想:
- 定义一个结点q = p->next
2.让p的后继结点的data赋值给p结点的data(p->data=q->data)
3.让p结点指针指向p的后继结点q的后继结点(p->next = q->next)
4.最后释放q结点(free(q))
从上面对单链表的学习可以知道,单链表结点只能从头结点依次遍历去找到对应的结点,使得单链表执行删除插入操作的时候只能通过从头开始遍历找到前驱结点的方法实现插入删除某个结点的操作,为了解决单链表上述的缺点,引入了双链表,双链表里面有两个指针front和next前者指向前驱结点,后者指向后继结点
#define Elemtype int
typedef struct LNode
{
Elemtype data;//数据域
struct LNode* front;//指向前驱结点
struct LNode* next;//指向后继结点
}*LinkList,LNode;
void InitDlink(LinkList* L)
{
(*L) = (LNode*)malloc(sizeof(LNode));
(*L)->front = NULL;
(*L)->next = NULL;
}
代码实现
void PushNode(LinkList* L)
{
int input = 0;
LNode* s;
LNode* head;
head = (*L);
printf("请输入一个数(输入0停止输入):->");
scanf_s("%d", &input);
while (input)
{
s = (LNode*)malloc(sizeof(LNode));
s->data = input;
s->next = head->next;
if (head->next != NULL)
{
head->next->front = s;//将s结点插入到head结点之后
}
head->next = s;
s->front = head;
printf("请输入一个数(输入0停止输入):->");
scanf("%d", &input);
}
}
双链表使用头插法时,要注意当你插入的结点是链表中第一个结点时,头结点是不存在后继的前驱的,所以我们这里要对链表第一个个结点插入进行条件判断,以便正确将结点插入
图解
上述插入结点的代码顺序也不是唯一的,当然也可以交换顺序但是,前两行代码必须在head->next = s
之前
删除某个指定结点内容为3的结点
图解
代码实现
void PopNode(LinkList* L,int data)
{
LNode* p = (*L)->next;
while (p && p->data != data)
{
p = p->next;
}
if (p == NULL) //要删除的结点不在链表中
{
printf("此结点不存在\n");
}
LNode* q = p->front;//找到要删除的结点p的前驱结点q
q->next = p->next;//要删除结点在链表末端
if (p->next != NULL)//删除结点不是链表末端结点
{
p->next->front = q;
}
free(p);
}
运行结果
(1)要删除的链表结点不在链表末端
(2)删除链表结点不存在
循环单链表和单链表的区别就在于表中的最后一个结点的next指向的不是NULL而是链表的头结点,从而使得链表成为一个环形
图解
代码实现
#include <stdio.h>
#include <stdlib.h>
// 定义循环单链表节点结构体
typedef struct node {
int data;
struct node *next;
} Node, *LinkList;
// 创建循环单链表
LinkList create_list(int n) {
LinkList head, p, q;
int i;
head = (LinkList)malloc(sizeof(Node));
head->data = 0;
head->next = head;
q = head;
for (i = 0; i < n; i++) {
p = (LinkList)malloc(sizeof(Node));
printf("请输入第%d个节点的值：", i+1);
scanf("%d", &p->data);
q->next = p;
q = p;
}
q->next = head;
return head;
}
// 遍历循环单链表
void traverse_list(LinkList L) {
LinkList p = L->next;
int i = 0;
while (p != L) {
printf("第%d个节点的值为：%d\n", i+1, p->data);
p = p->next;
i++;
}
}
//在循环单链表中插入节点
void insert_node(LinkList L, int pos, int val) {
LinkList p, q;
int i = 0;
p = L->next;
while (p != L && i < pos-1) {
p = p->next;
i++;
}
if (p == L || i > pos-1) {
printf("插入位置不合法！\n");
return;
}
q = (LinkList)malloc(sizeof(Node));
q->data = val;
q->next = p->next;
p->next = q;
}
//在循环单链表中删除节点
void delete_node(LinkList L, int pos) {
LinkList p, q;
int i = 0;
p = L->next;
while (p != L && i < pos-1) {
p = p->next;
i++;
}
if (p == L || p->next == L || i > pos-1) {
printf("删除位置不合法！\n");
return;
}
q = p->next;
p->next = q->next;
free(q);
}
int main() {
LinkList L;
int n, pos, val;
printf("请输入循环单链表的长度：");
scanf("%d", &n);
L = create_list(n);
traverse_list(L);
printf("请输入要插入的位置和值：");
scanf("%d%d", &pos, &val);
insert_node(L, pos, val);
traverse_list(L);
printf("请输入要删除的节点位置：");
scanf("%d", &pos);
delete_node(L, pos);
traverse_list(L);
return 0;
}
循环双链表其实就是在循环单链表的基础上让头结点前驱指针指向表尾结点
图解
代码实现
以下是一个简单的循环双链表实现的C语言代码：
```c
#include <stdio.h>
#include <stdlib.h>
//定义循环双链表节点结构体
typedef struct node {
int data;
struct node *prev;
struct node *next;
} Node, *LinkList;
// 创建循环双链表
LinkList create_list(int n) {
LinkList head, p, q;
int i;
head = (LinkList)malloc(sizeof(Node));
head->data = 0;
head->prev = head;
head->next = head;
q = head;
for (i = 0; i < n; i++) {
p = (LinkList)malloc(sizeof(Node));
printf("请输入第%d个节点的值：", i+1);
scanf("%d", &p->data);
p->prev = q;
q->next = p;
q = p;
}
q->next = head;
head->prev = q;
return head;
}
//遍历循环双链表
void traverse_list(LinkList L) {
LinkList p = L->next;
int i = 0;
while (p != L) {
printf("第%d个节点的值为：%d\n", i+1, p->data);
p = p->next;
i++;
}
}
//在循环双链表中插入节点
void insert_node(LinkList L, int pos, int val) {
LinkList p, q;
int i = 0;
p = L->next;
while (p != L && i < pos-1) {
p = p->next;
i++;
}
if (p == L || i > pos-1) {
printf("插入位置不合法！\n");
return;
}
q = (LinkList)malloc(sizeof(Node));
q->data = val;
q->prev = p;
q->next = p->next;
p->next->prev = q;
p->next = q;
}
//在循环双链表中删除节点
void delete_node(LinkList L, int pos) {
LinkList p, q;
int i = 0;
p = L->next;
while (p != L && i < pos-1) {
p = p->next;
i++;
}
if (p == L || p->next == L || i > pos-1) {
printf("删除位置不合法！\n");
return;
}
q = p->next;
p->next = q->next;
q->next->prev = p;
free(q);
}
int main() {
LinkList L;
int n, pos, val;
printf("请输入循环双链表的长度：");
scanf("%d", &n);
L = create_list(n);
traverse_list(L);
printf("请输入要插入的位置和值：");
scanf("%d%d", &pos, &val);
insert_node(L, pos, val);
traverse_list(L);
printf("请输入要删除的节点位置：");
scanf("%d", &pos);
delete_node(L, pos);
traverse_list(L);
return 0;
}
静态链表是通过数组来描述线性表的链式存储结构,结点里面也是由数据域和指针域组成,但是静态链表中的指针域不是结点的地址而是数组下标静态链表也是在内存中开辟一片连续的内存空间
图解
这里我的结束标识是指针下标为-1的结点,而-2代表的是分配的那一片内存空间的空闲区域
主要是要学会单链表的插入删除操作才可以更好的理解其他的链式存储方式,双链表的头插法插入节点一定要记得考虑是否插入的节点是链表中的第一个节点,它是不存在后继的前驱指针的,进行删除操作时也要考虑自己删除的是否为链表的栈顶结点(末端结点)删除时,要知道栈顶结点是不存在前驱结点的.
我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h
我正在寻找执行以下操作的正确语法(在Perl、Shell或Ruby中):#variabletoaccessthedatalinesappendedasafileEND_OF_SCRIPT_MARKERrawdatastartshereanditcontinues. 最佳答案 Perl用__DATA__做这个:#!/usr/bin/perlusestrict;usewarnings;while(){print;}__DATA__Texttoprintgoeshere 关于ruby-如何将脚
我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i
有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？ 最佳
几个月前，我读了一篇关于rubygem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：
给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最
我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_
无论您是想搭建桌面端、WEB端或者移动端APP应用，HOOPSPlatform组件都可以为您提供弹性的3D集成架构，同时，由工业领域3D技术专家组成的HOOPS技术团队也能为您提供技术支持服务。如果您的客户期望有一种在多个平台（桌面/WEB/APP，而且某些客户端是“瘦”客户端）快速、方便地将数据接入到3D应用系统的解决方案，并且当访问数据时，在各个平台上的性能和用户体验保持一致，HOOPSPlatform将帮助您完成。利用HOOPSPlatform，您可以开发在任何环境下的3D基础应用架构。HOOPSPlatform可以帮您打造3D创新型产品，HOOPSSDK包含的技术有：快速且准确的CAD
目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非
?博客主页：https://xiaoy.blog.csdn.net?本文由呆呆敲代码的小Y原创，首发于CSDN??学习专栏推荐：Unity系统学习专栏?游戏制作专栏推荐：游戏制作?Unity实战100例专栏推荐：Unity实战100例教程?欢迎点赞?收藏⭐留言?如有错误敬请指正！?未来很长，值得我们全力奔赴更美好的生活✨------------------❤️分割线❤️-------------------------