数据结构 链表

单链表:单链表用来写邻接表,邻接表用来存储图和树

双链表:用来优化某些问题

单链表

链式存储

#include<stdio.h>

#include<stdlib.h>

int cont = 0;

//结构体

typedef struct List {

int data; //数据域

struct List* next; //指针域,指向当前结点的下一个结点,next指针的作用:1.直接访问下一个结点2.进行链表的遍历

}List,*Listptr; //类型名

//创建链表

_Bool CreateList(Listptr *head) { //若改变一级指针的值【一级指针所存储的地址】,只能找到二级指针进行修改,Listptr本身就是一级指针,Listptr*是二级指针【传参过程,如果想要改变参数本身,只能使用指针/引用进行】

*head = (Listptr)malloc(sizeof(List));//为第一个结点【头节点,什么都不放】申请空间 “=”改变指针的指向 malloc()请的空间是void*类型

//C语言指针赋值的规则:基类型相容,修饰符种类与个数:左边>右边

if(*head){

(*head)->data = 0;

(*head)->next = NULL;//指向为空,避免野指针的出现

return 1;

}

else

return 0;

}

//头插法

void Insert(Listptr head) {

Listptr temp;//要插入的结点

CreateList(&temp);//对新的结点进行申请空间和初始化结点

scanf("%d", &temp->data);

temp->next = head->next;//改变next指针的指向,先进行这一步,防止数据丢失

head->next = temp;

}

//尾插法,引入一个Listptr end(尾结点),指向最后一个结点

//尾插法 未引入尾结点

void Bottom_Insert(Listptr head) {

Listptr temp;

CreateList(&temp);

scanf("%d", &temp->data);

while (head->next) {

head = head->next;

}

head->next = temp;

}

//特定位置插

void Particular_Insert(Listptr head, int index) {

Listptr temp;

CreateList(&temp);

scanf("%d", &temp->data);

int i = 0; //此时位置从0开始算起

//int i = 1; 此时位置从1开始算起

while (i < index && head) {

i++;

head = head->next;

}

if (i == index && head) { //找到特定位置,并且该位置不是尾结点

temp->next = head->next;

head->next = temp;

}

else if (i == index && !head) { //找到特定位置,但是该位置是尾结点

head->next = temp;

}

else { //未找到特定位置

printf("插入失败\n");

}

}

//查——遍历查找

Listptr Search(Listptr head,int check) {

Listptr i = head;//i指针指向头结点,头结点不存放数据,故不用判断

while (i->next) {//i->next!=NULL;的时候进行循环

i = i->next;

cont++;

if (i->data == check) {

return i;

}

}

return NULL;

}

//按个数查找,只查找一个

Listptr SearchIndex(Listptr head, int index) {

int i = 0;

while (i < index && head != NULL) { //当查到找到或者查到末尾时停止

i++;

head = head->next;

}

if (head && i==index) //找到

return head;

else

return NULL;

}

//输出——遍历输出

void Print(Listptr head) {

Listptr i = head;//i本身就是一个指针

while (i->next) {//i->next!=NULL;的时候进行循环

i = i->next;

printf("%d ", i->data);

}

printf("\n");

}

//删1——删除特定的结点——按结点个数来查找

//需要遍历查到特定结点

_Bool DeleteNode(Listptr head,int index,int *e){

int i = 0;

Listptr front = head;

i = 1;

head = head->next;

while (i < index && head!= NULL) {

front = head;

head = head->next;

i++;

}

if (i == index && head != NULL) {//head就是查找的结点,front就是查找的前一个值

Listptr t = head;

front->next = head->next;

*e = t->data;

free(t);

return 1;

}

return 0;

}

//删2——删除特定结点——按结点个数查找

//使用查找函数查找

_Bool DeleteNode_SearchIndex(Listptr head, int index, int* e) {

Listptr front = SearchIndex(head, index - 1);

head = SearchIndex(head, index);

if (head && front) {

Listptr t = head;

front->next = head->next;

*e = t->data;

free(t);

return 1;

}

return 0;

}

//改

_Bool Alert(Listptr head, int index, int data) {

head = SearchIndex(head, index);

if (head) {

head->data = data;

return 1;

}

else

return 0;

}

int main() {

Listptr head; //第一个结点的指针

CreateList(&head);//对链表进行初始化

for (int i = 0;i < 10;i++) {

Insert(head);//插入

}

Print(head);//输出

for (int i = 0;i < 5;i++) {

int index = 0;

scanf("%d", &index);

printf("%d\n", SearchIndex(head, index)->data);

scanf("%d", &index);

int data;//删除

if (DeleteNode(head, index, &data)) {

printf("删除成功,删除值为%d\n", data);

}

else

printf("删除失败\n");

Print(head);

scanf("%d%d", &index, &data);

if (Alert(head, index, data)) {//更改

printf("更改成功\n");

}

else

printf("更改失败\n");

Print(head);

}

for (int i = 0;i < 10;i++) {

int check = 0;

scanf("%d", &check);

if (!Search(head, check)) {//查找

printf("没查到\n");

}

else

printf("第%d个结点\n",cont);

}

return 0;

}

自己码代码

#include<stdio.h>

#include<stdlib.h>

typedef struct List {

int data;

struct List* next;

}List,*Listptr;

int cont=0;

//初始化

_Bool CreateList(Listptr* head) {

*head = (Listptr)malloc(sizeof(List));

if (*head) {

(*head)->data = 0;

(*head)->next = NULL;

return 1;

}

else

return 0;

}

//头插法

void Insert(Listptr head) {

Listptr temp;

CreateList(&temp);

scanf("%d", &temp->data);

temp->next = head->next;

head->next = temp;

}

//尾插法

void Bottom_Insert(Listptr head) {

Listptr temp;

CreateList(&temp);

scanf("%d", &temp->data);

while (head->next) {

head = head->next;

}

head->next = temp;

}

//特定位置插

void Particular_Insert(Listptr head, int index) {

Listptr temp;

CreateList(&temp);

scanf("%d", &temp->data);

int i = 0;

while (i < index && head) {

i++;

head = head->next;

}

if (i == index && head) {

temp->next = head->next;

head->next = temp;

}

else if (i == index && !head) {

head->next = temp;

}

else {

printf("插入失败\n");

}

}

//查1——按值查找

Listptr Search(Listptr head, int check) {

Listptr i;

i = head;

while (i->next) {

i = i->next;

cont++;

if (i->data == check) {

return i;

}

}

return NULL;

}

//查2——按结点位置查找

Listptr SearchIndex(Listptr head, int index) {

int i = 0;

while (i < index && head) {

i++;

head = head->next;

}

if (head && i == index) {

return head;

}

else

return NULL;

}

//输出

void Print(Listptr head) {

Listptr i = head;

while (i->next) {

i = i->next;

printf("%d ", i->data);

}

printf("\n");

}

//删——删除特定节点

_Bool DeleteNode(Listptr head, int index, int* e) {

Listptr front = SearchIndex(head, index - 1);

head = SearchIndex(head, index);

if (head && front) {

Listptr t = head;

front->next = head->next;

*e = t->data;

free(t);

return 1;

}

return 0;

}

//改

_Bool Alert(Listptr head, int index, int data) {

head = SearchIndex(head, index);

if (head) {

head->data = data;

return 1;

}

else

return 0;

}

int main() {

Listptr head;

CreateList(&head);

for (int i = 0;i < 5;i++) {

Insert(head);//头插法

}

Print(head);

Bottom_Insert(head);//尾插法

Print(head);

int index1;

scanf("%d", &index1);

Particular_Insert(head, index1);//特定位置插入

Print(head);

int check;

scanf("%d", &check);

Search(head, check);//按值查找

printf("值为%d的是第%d个结点\n", check, cont);

int index2;

scanf("%d", &index2);

printf("第%d个结点的值为%d\n", index2, SearchIndex(head, index2)->data);//按位置查找

int index3;

scanf("%d", &index3);

int data1;

if (DeleteNode(head, index3, &data1)) {//删

printf("删除成功,删除值为%d\n", data1);

}

else

printf("删除失败\n");

Print(head);

int index4, data2;

scanf("%d%d", &index4, &data2);

if (Alert(head, index4, data2)) {//改

printf("更改成功\n");

}

else

printf("更改失败\n");

Print(head);

return 0;

}

顺序存储

用数组模拟链表,静态链表,比动态链表快(因为 new 生成新结点慢)

//链表的顺序存储,用数组来模拟链表

#include<stdio.h>

#define N 100

typedef struct List {//typedef作用:将后面的定义变量的语句变成给类型重命名的语句

int data;

int next;//索引,下标可以替代next指针,以此来访问下一个结点

}List, * Listptr;

List heap[100] = { 0 };//数组代表堆这个空间

//确定数组未使用空间为空 1.逐个遍历——麻烦 2.将空余空间构成链表【整体过程存在两个链表,一个是有数据即将使用的链表,一个是空余未使用空间串联构成的备用链表(当需要空间的时候,自取)】

//初始化

int head, leisure;//分别代表两个链表的头指针,head是using链表的头指针,用来指向第一个结点,leisure是空余链表的头指针

void InitHeap() {

int i;

head = 0;

//heap[0].next = 1;//用来存储空余链表的第一个结点的下标

heap[N - 1].next = 0;//0代表为空,意思是什么都不指向,指向为NULL,next只要为0,就相当于什么都不指向,指向为空

for (i = 0;i < N - 1;i++) {

heap[i].next = i + 1;

}

}

//模仿malloc

int Malloc() {//空间申请,申请一个结点的空间,一个结点==数组中的一个元素

int temp;

if (heap[0].next) {//heap[0].next==0 整个堆中没有空余空间,反之有空余空间

temp = heap[0].next;//临时变量存储要删除的结点

heap[0].next = heap[heap[0].next].next;//利用第一个结点指向第三个结点,第一个结点存储的第二个结点的下标,第二个结点存储的第三个结点的下标

return temp;//返回刚申请空间的索引

}

else {

return 0;//无法申请空间

}

}

//模仿free

void Free(int index) {//动态链表中释放空间,静态链表中将正在使用链表中的结点放在空余链表中

//因为这个空间本来就有,所以就不用再申请了

heap[index].next = heap[0].next;

heap[0].next = index;

}

//增——头插法

_Bool InsertHead() {

int temp = Malloc();

if (temp) {

heap[temp].next = head;

head = temp;

return 1;

}

else

return 0;

}

//按data值查找

int Search(int check) {

int temp = head;//将第一个结点的索引赋给temp,所以heap[temp]指的是第一个结点

while (temp) {

if (heap[temp].data == check) {

return temp;

}

else {

temp = heap[temp].next;

}

}

}

//按索引查找

int SearchByIndex(int Index) {

int i = head, cont = 0;

while (i < Index && i != 0) {

cont++;

if (cont == Index) {

return i;

}

else {

i = heap[i].next;

}

}

return 0;

}

//改

_Bool Alert(int index, int data) {

int temp = Search(index);

if (temp) {

heap[temp].data = data;

return 1;

}

else

return 0;

}

//删

_Bool Delete(int index) {

int front = SearchByIndex(index - 1), aim = SearchByIndex(index);

if (aim && front) {//从第二个结点开始删除

int temp = aim;//存储要删除的结点

heap[front].next = heap[aim].next;//将目标前一个结点指向目标后一个结点

Free(temp);

}

else if (aim) {//从第一个结点开始删除

int temp = aim;

front = heap[aim].next;//如果使用 heap[front].next = heap[aim].next;将会丢失空余链表剩下的部分,因为你直接将空余链表的头结点指向第二个结点,使得空余链表的后面的空结点丢失

Free(temp);

}

}

int main() {

return 0;

}

Acwing 课程

代码

//使用两个数组模拟链表

#include<iostream>

using namespace std;

const int N = 100010;

//head表示头结点的下标,头结点最开始指向一个空结点(用-1表示),每次插入一个新的元素

//e[i]表示结点i的值,ne[i]表示结点i的next指针是多少

//idx存储当前已经用到哪个点

int head, e[N], ne[N], idx;

//初始化

void init() {

head = -1;//表示空集

idx = 0;

}

//头插法 分两步进行

void add_to_head(int x) {

e[idx] = x;//存储数值

ne[idx] = head;//第一步

head = idx;//第二步

idx++;

}

//指定位置插

//将x插到下标是k这个点后面

//分两步进行

void add(int k, int x) {

e[idx] = x;

ne[idx] = ne[k];

ne[k] = idx;

idx++;

}

//删除特定位置的点

//删去下标为k的后面的一个点

void remove(int k) {

ne[k] = ne[ne[k]];

}

int main() {

return 0;

}

题目

实现一个单链表,链表初始为空,支持三种操作:

(1) 向链表头插入一个数;

(2) 删除第k个插入的数后面的数;

(3) 在第k个插入的数后插入一个数

现在要对该链表进行M次操作,进行完所有操作后,从头到尾输出整个链表。

注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数,则按照插入的时间顺序,这n个数依次为:第1个插入的数,第2个插入的数,…第n个插入的数。

输入格式

第一行包含整数M,表示操作次数。

接下来M行,每行包含一个操作命令,操作命令可能为以下几种:

(1) “H x”,表示向链表头插入一个数x。//头插法

(2) “D k”,表示删除第k个输入的数后面的数(当k为0时,表示删除头结点)。//第k个输入,下标为k-1,即删除下标为k-1后面的数

(3) “I k x”,表示在第k个输入的数后面插入一个数x(此操作中k均大于0)。//即在下标为k-1后插入一个数

输出格式

共一行,将整个链表从头到尾输出。

数据范围

1 ≤ M ≤ 100000 1≤M≤1000001≤M≤100000

所有操作保证合法。

输入样例

10

H 9

I 1 1

D 1

D 0

H 6

I 3 6

I 4 5

I 4 5

I 3 4

D 6

输出样例

6 4 6 5

注意点

1.插入、删除操作都是对第k个数后面的数进行操作的,因为指针域存储的是下一个节点。

2.删除时,首先要考虑是否删除的是头节点。

3.输出时从头结点开始,末尾是空,指向−1。

4.scanf在读入字符时不会跳过空格,还是用cin。

//使用两个数组模拟链表

#include<iostream>

using namespace std;

const int N = 100010;

//head表示头结点的下标

//e[i]表示结点i的值,ne[i]表示结点i的next指针是多少

//idx存储当前已经用到哪个点

int head, e[N], ne[N], idx;

//初始化

void init() {

head = -1;//表示空集

idx = 0;

}

//头插法 分两步进行

void add_to_head(int x) {

e[idx] = x;//存储数值

ne[idx] = head;//第一步

head = idx;//第二步

idx++;

}

//指定位置插

//将x插到下标是k这个点后面

//分两步进行

void add(int k, int x) {

e[idx] = x;

ne[idx] = ne[k];

ne[k] = idx;

idx++;

}

//删除特定位置的点

//删去下标为k的后面的一个点

void remove(int k) {

ne[k] = ne[ne[k]];

}

int main() {

int M;

cin >> M;

init();

while (M--) {

int k, x;

char op;

cin >> op;

if (op == 'H') {

cin >> x;

add_to_head(x);

}

else if (op == 'D') {

cin >> k;

if (!k)

head = ne[head];//删除头结点,使head指向它现在指向的点的下一个点,head指向的点就是head本身

remove(k - 1);//因为第一个插入的点下标是0,以此类推

}

else {

cin >> k >> x;

add(k - 1, x);

}

}

for (int i = head;i != -1;i = ne[i])

cout << e[i] << ' ';

return 0;

}

邻接表

实际上就是开了 n 个单链表。

双链表

一个结点有两个指针,分别指向它的左边和右边,l[N],r[N],不专门定义头结点head和尾结点tail,下标为0的点是最左边的点,下标为1的点是最右边的点。

代码

#include<iostream>

using namespace std;

const int N = 100010;

int e[N], l[N], r[N], idx;

//初始化

void init() {

//0表示左端点,1表示右端点,最开始的时候,0号点的右边是1号点,1号点的左边是0号点

r[0] = 1, l[1] = 0;

idx = 2;

}

//增——两种选择,插入到某点的右边或插入到某点的左边

//在下标为k的点的右边插入一个数

void add(int k, int x) {

e[idx] = x;

r[idx] = r[k];

l[idx] = k;

l[r[k]] = idx;

r[k] = idx;

idx++;

}

//在下标为k的点的左边插入一个数

//可以重新写,也可以直接调用,即在l[k]的右边插入一个数 add(l[k],x)

//删

//删除下标为k的点

void remove(int k) {

r[l[k]] = r[k];

l[r[k]] = l[k];

}

int main() {

return 0;

}



 

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Freeswitch中CHANNEL_HANGUP外呼挂断事件

1.CHANNEL_HANGUP外呼挂断事件 事件详细 ################## 外呼挂断&#xff1a;############################# [EslMessage{contentTypecommand/reply, headers3, body0 lines}] 2023-11-16T03:41:33.5140800 INFO c.e.c.v.s.c.i.FsServerEventHandler - eventReceived:…

vue2 mixin的方式 大屏适配(缩放居中的方式)

使用要求&#xff1a;指定容器的 id 为 bigScreenContainer 一、效果图 不管你的屏幕多大都会根据设计稿 1920*1080 进行缩放 图一&#xff1a;缩小的效果 图二&#xff1a;放大的效果 二、使用方式 <template><div id"bigScreenContainer" ref"big…

【Proteus仿真】【Arduino单片机】HC05蓝牙通信

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用Proteus8仿真Arduino单片机控制器&#xff0c;使用PCF8574、LCD1602液晶、HC05蓝牙传感器等。 主要功能&#xff1a; 系统运行后&#xff0c;LCD1602显示蓝牙接收数据。 二、软件设计 /* 作者…

axios升级依赖版本后报错SyntaxError: Cannot use import statement outside a module

Axios构建为ES模块&#xff0c;而不是在Node中运行时的CommonJs。Jest的问题是它在Node中运行代码。这就是为什么告诉Jest转换Axios有效的原因。 Axios SDK附带了一个用于Node env的内置CommonJs文件。因此&#xff0c;我们可以通过将以下内容添加到您的package.json来修复它&a…

微服务架构之路7,Nacos配置中心的Pull原理,附源码

目录 一、本地配置二、配置中心1、以Nacos为例&#xff1a;2、Pull模式3、也可以通过Nacos实现注册中心 三、配置中心提供了哪些功能四、如何操作配置中心1、配置注册2、配置反注册3、配置查看4、配置变更订阅 五、主流的微服务注册中心有哪些&#xff0c;如何选择&#xff1f;…

C# 图解教程 第5版 —— 第15章 事件

文章目录 15.1 发布者和订阅者15.2 源代码组件概览15.3 声明事件15.4 订阅事件15.5 触发事件15.6 标准事件的用法15.6.1 通过扩展 EventArgs 来传递数据15.6.2 移除事件处理程序 15.7 事件访问器 15.1 发布者和订阅者 ​ 发布者 / 订阅者模式&#xff1a;发布者定义了一系列事…

Transformer

1. 整体架构 2. Encoder 1&#xff09;输入部分&#xff1a;Embeding 位置编码 位置编码没搞懂

小程序转换工具—Antmove 使用教学

自从微信小程序问世以后&#xff0c;字节、阿里、百度巨头们都各自搞各自的小程序平台&#xff0c;各有各的技术标准。基础技术都大差不差&#xff0c;但就是没法统一。搞得我们这些对接各平台的程序猿们苦不堪言。 虽说uniapp、Taro、Mpvue、Weex、Flutter都支持跨平台小程序…

LeetCode | 232. 用栈实现队列

​ LeetCode | 232. 用栈实现队列 OJ链接 解题思路&#xff1a; 此题可以用两个栈实现&#xff0c;一个栈进行入队操作&#xff0c;另一个栈进行出队操作出队操作&#xff1a; 当出队的栈不为空是&#xff0c;直接进行出栈操作&#xff0c;如果为空&#xff0c;需要把入队的…

HarmonyOS 实战项目

引言 本章将介绍如何在 HarmonyOS 上进行实际项目开发。我们将从项目需求分析开始&#xff0c;逐步完成项目的设计、开发、测试和上线过程。 目录 项目需求分析项目设计项目开发项目测试项目上线总结 1. 项目需求分析 项目需求分析是项目开发的关键阶段之一&#xff0c;它…

C#,数值计算——插值和外推,Base_interp的计算方法与源程序

1 文本格式 using System; namespace Legalsoft.Truffer { /// <summary> /// Abstract base class used by all interpolation routines in this chapter. /// Only the routine interp is called directly by the user. /// </summary> pu…

Digicert证书:您的网络安全守护神

在当今数字化的世界中&#xff0c;网络安全已经成为每一个企业和个人必须面对的问题。而Digicert品牌证书&#xff0c;就是您网络安全的最佳选择。它不仅具有强大的安全性和稳定性&#xff0c;还能广泛应用于各种场景&#xff0c;为您提供全方位的保护。 首先&#xff0c;我们要…

Paypal发布公开信,三月已过,PYUSD发展如何?

2023年8月8日&#xff0c;美国支付巨头Paypal正式宣布推出其稳定币PYUSD&#xff0c;成为美国传统大型金融机构发行稳定币的首家企业。 当时&#xff0c;正值美国SEC与加密交易所Coinbase、Binance的诉讼白热化&#xff0c;Paxos被迫停止发行BUSD的阶段&#xff0c;在此背景下&…

计算机网络———ipv6简解

文章目录 1.前言&#xff1a;2. ipv6简单分析&#xff1a;2.1.地址长度对比2.2. ipv6包头分析2.3. ipv6地址的压缩表示&#xff1a;2.3. NDP&#xff1a;2.4. ipv6地址动态分配&#xff1a; 1.前言&#xff1a; 因特网地址分配组织)宣布将其最2011年2月3日&#xff0c;IANA (In…

从0开始学习JavaScript--JavaScript 循环与迭代详解

JavaScript中的循环和迭代是编写高效和灵活代码的关键。循环用于重复执行一段代码&#xff0c;而迭代则用于遍历数据结构。本文将深入研究JavaScript中常见的循环结构和迭代方法&#xff0c;并通过丰富的示例代码来帮助读者更好地理解和运用这些概念。 基本的for循环 for循环…

【微软技术栈】C#.NET 内存映射文件

本文内容 进程、视图和管理内存使用内存映射文件编程示例 内存映射文件包含虚拟内存中文件的内容。 借助文件和内存空间之间的这种映射&#xff0c;应用&#xff08;包括多个进程&#xff09;可以直接对内存执行读取和写入操作&#xff0c;从而修改文件。 可以使用托管代码访…

前端404页面的制作

1、背景 前端开发经常遇到输入路径不存在的问题&#xff0c;为此&#xff0c;把之前项目的404拿出来供大家参考。代码很简单&#xff0c;适合新手入手&#xff0c;效果如下&#xff1a; 2、代码引用的是element-plus框架 <template><div><el-result icon"…

String字符串性能优化的几种方案

原创/朱季谦 String字符串是系统里最常用的类型之一&#xff0c;在系统中占据了很大的内存&#xff0c;因此&#xff0c;高效地使用字符串&#xff0c;对系统的性能有较好的提升。 针对字符串的优化&#xff0c;我在工作与学习过程总结了以下三种方案作分享&#xff1a; 一.优…

linux虚拟机环境快速搭建redis5.x版本的主从集群总结

原创/朱季谦 我在阿里云服务器上曾参与过公司redis集群的搭建&#xff0c;但时间久了&#xff0c;都快忘记当时的搭建过程了&#xff0c;故而决定在虚拟机centOS 7的环境&#xff0c;自行搭建一套redis5.x版本的集群&#xff0c;该版本集群的搭建比较方便&#xff0c;不用再像…

上海亚商投顾:沪指低开低走 抖音概念股逆势爆发

上海亚商投顾前言&#xff1a;无惧大盘涨跌&#xff0c;解密龙虎榜资金&#xff0c;跟踪一线游资和机构资金动向&#xff0c;识别短期热点和强势个股。 一.市场情绪 沪指昨日震荡调整&#xff0c;深成指跌超1%&#xff0c;创业板指跌超1.8%。抖音概念股逆势爆发&#xff0c;佳…