首页 > 编程语言 >【算法竞赛】链表

【算法竞赛】链表

时间:2024-09-17 15:24:55浏览次数:8  
标签:node 竞赛 int 链表 算法 nodes now nextid

链表的特点是用一组位于任意位置的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以不连续。

链表是容易理解和操作的基本数据结构,它的操作有初始化、添加、遍历、插入、删除、查找、释放等。

链表分为单向链表和双向链表,如图所示.
在这里插入图片描述
链表的各节点首尾相接,最后的next指针指向第一个data,第一个pre指针指向最后的data.

单向链表只有一个遍历方向,双向链表有两个遍历方向,比单向链表的访问方便一些,也快一些.

在需要频繁访问前后几个节点的场合可以使用双向链表.

使用链表时,可以直接用STLlist,也可以自己写链表.

如果自己写代码实现链表,有两种编码实现方法:动态链表、静态链表.

在算法竞赛中为加快编码速度,一般用静态链表或STLlist.

例1.1
在这里插入图片描述

动态链表

动态链表需要临时分配链表节点,使用完毕后释放链表节点.

动态链表的优点是能及时释放空间,不使用多余内存;缺点是需要管理空间,容易出错.

动态链表是“教科书式”的标准做法.以下代码用动态单向链表实现了例1.1.

#include <bits/stdc++.h>
struct node 
{
	int data;
	node * next;
};

int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	
	node *head,*now;
	//建立链表头节点
	head=new node;
	head->data=1;
	head->next=NULL;
	
	now=head;
	//建立链表
	node*p;
	for(int i=2;i<=n;i++)
	{
		p=new node;
		p->data=i;
		now->next=p;
		now=p;
	}
	now->next=head;
	
	node*prev=head;
	now=head;
	while(n--)
	{
		for(int i=1;i<m;i++)
		{
			prev=now;
			now=now->next;
		}
		printf("%d",now->data);
		prev->next=now->next;
		delete now;
		now=prev->next;
	}
	printf("%d",now-data);
    delete now;
    return 0;
	
}

静态链表

动态链表虽然“标准”,但是竞赛中一般不用.
算法竞赛对内存管理要求不严格,为加快编码速度,一般就在题目允许的存储空间内静态分配,省去了动态分配和释放的麻烦.

静态链表使用预先分配的一段连续空间存储链表.
从物理存储的意义上讲,“连续空间"并不符合链表的本义,因为链表的优点就是能克服连续存储的弊端,但是用连续空间实现的链表,在逻辑上是成立的.

具体有两种做法:
①定义链表结构体数组,和动态链表的结构差不多;
②使用一维数组,直接在数组上进行链表操作.
本节给出3段代码:用结构体数组实现单向静态链表、用结构体数组实现双向静态链表、用一维数组实现单向静态链表.

用结构体数组实现单向静态链表

用结构体数组实现单向静态链表,注意静态分配应该定义在全局,不能定义在函数内部.

#include<bits/stdc++.h>
const int N = 105;
struct node{
    int id, nextid;
    // int data; //如有必要, 定义一个有意义的数据
}nodes[N];
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    nodes[0].nextid = 1;
    for(int i = 1; i <= n; i++){
        nodes[i].id = i;
        nodes[i].nextid = i + 1;
    }
    nodes[n].nextid = 1;
    int now = 1, prev = 1;
    while((n--) > 1){
        for(int i = 1; i < m; i++){
            prev = now;
            now = nodes[now].nextid;
        }
        printf("%d ", nodes[now].id);
        nodes[prev].nextid = nodes[now].nextid;
        now = nodes[prev].nextid;
    }
    printf("%d", nodes[now].nextid);
    return 0;
}

用结构体数组实现双向循环链表

#include <bits/stdc++.h>
const int N = 105;

struct node{
    // int data;
    int id;
    int preid, nextid;
}nodes[N];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    nodes[0].nextid = 1;
    for(int i = 1; i <= n; i++)
    {
        nodes[i].id = i;
        nodes[i].preid = i - 1;
        nodes[i].nextid = i + 1;
    }
    nodes[n].nextid = 1;
    nodes[1].preid = n;
    int now = 1;
    while((n--) > 1)
    {
        int prev = nodes[now].preid, next = nodes[now].nextid;
        
        nodes[prev].nextid = nodes[now].nextid;
        nodes[next].preid = nodes[now].preid;
        for(int i = 1; i < m; i++)
        {
            now = nodes[now].nextid;
        }
        printf("%d ", nodes[now].id);
    }
    printf("%d", nodes[now].nextid);
    return 0;
}

用一维数组实现单向静态链表

这是最简单的实现方法。定义一个一维数组nodes[],nodes[i]的i就是节点的值,而nodes[i]的值是下一个节点。
它的使用环境很有限,因为它的节点只能存一个数据,就是i。


#include<bits/stdc++. h>

int nodes[150];

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	
	for(int i=1;i<=n-1;i++) 
		nodes[i] = i+1;
	
	nodes[n] = 1;
	int now = 1, prev = 1;
	
	while((n--)>1) >1)
	{
		for(int i=1; 1; i<m; i++)
		{
			prev = now; 
			now = nodes[now];
		}
		printf("%d", now);
		nodes[prev] = nodes[now];
		now = nodes[prev];
	}
	printf("%d", now);
	return 0;
}

C++ STL List

在算法竞赛或工程项目中常常使用C++STLlist。list。list是双向链表,由标准模板库(Standard Template Library,STL)管理,通过指针访问节点数据,高效率地删除和插入。
请熟悉list的初始化、插入、删除、遍历、查找、释放。下面是用list实现例1.1的代码。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    cin>>n>>m;
    list<int> node;
    for(int i = 1; i <= n; i++)
    {
        node.push_back(i);
    }
    list<int>::iterator it = node.begin();
    while(node.size() > 1)
    {
        for(int i = 1; i < m; i++)
        {
            it++;
            if(it == node.end())
            {
                it = node.begin();
            }
        }
        cout<<*it<<" ";
        list<int>::iterator next = ++it;
        node.erase(--it);
        if(next == node.end())
        {
            next = node.begin();
        }
        it = next;
    }
    cout<<*it;
    return 0;
}

标签:node,竞赛,int,链表,算法,nodes,now,nextid
From: https://blog.csdn.net/Sakura_ding/article/details/142314458

相关文章

  • 【加密算法基础——AES CBC模式代码解密实践】
    AES解密实践之代码实现AES解密使用python脚本比较灵活,但是一定要保证脚本是调试过的,才能在找到正确的密文,密钥,初始向量的情况下,解出正确的明文。但是对于AES解密,命令行无法处理key截断的问题。实际测试了一下,CBC模式,对于key截断的问题可以解决,但是CFB模式,目前还无法实验......
  • leetCode2:两数相加(链表)
    题目:给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字。请你将两个数相加,并以相同形式返回一个表示和的链表。你可以假设除了数字0之外,这两个数都不会以0开头。思路:遍历两个链表,逐位相加,还要加上进位结......
  • Leetcode 19.删除链表的倒数第第N个结点
    1.题目基本信息题目:给你一个链表,删除链表的倒数第n个结点,并且返回链表的头结点。地址:https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/2.解题方法2.1.解题思路使用快慢指针2.2.解题步骤第一步,初始化快指针为head,慢指针指向一个哑结点,哑结点......
  • 代码随想录算法训练营,9月17日 | 669. 修剪二叉搜索树,108.将有序数组转换为二叉搜索树,5
    669.修剪二叉搜索树题目链接:669.修剪二叉搜索树文档讲解︰代码随想录(programmercarl.com)视频讲解︰修剪二叉搜索树日期:2024-09-17想法:节点为空返回空,值在中间时,继续递归左右两边,小于时递归右子树,大于时递归左子树Java代码如下:classSolution{publicTreeNodetrimBST......
  • 从kaggle竞赛零基础上手CV实战(Deepfake检测)
    关注B站可以观看更多实战教学视频:hallo128的个人空间从kaggle竞赛零基础上手CV实战从kaggle竞赛零基础上手CV实战(Deepfake检测)目录从kaggle竞赛零基础上手CV实战(Deepfake检测)背景介绍学习地址课程大纲课程特色适用人群背景介绍随着人工智能技术的迅猛发展,深......
  • 《算法妙趣生,代码启征程》---第一期:双指针算法
      写这个系列是为了记录我所学习的模块,进行分析+总结+归纳。如果你也对算法感兴趣,可以跟着我一起学习总结,我会在我理解明白了的基础上,进行尽可能详细,通俗易懂的语言进行表达。目录 1.是什么2.题目解析(1)移动零 283.移动零-力扣(LeetCode)(2)复写零 1089.......
  • 【SCI2区】麻雀搜索算法SSA-TCN-Multihead-Attention回归预测(多输入单输出)【含Matlab
    ✅博主简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,Matlab项目合作可私信或扫描文章底部QQ二维码。......
  • 贪心算法-找不重叠的区间段
    1.说明有N个区间片段,查找其中不重叠的片段最大个数。例如(68),(24),(35),(15),(59),(810)这6个片段中,不重叠的片段最大个数为3,分别为(24),(68),(810)。2.解析先按照起始位置从小到大进行排序,使用贪心算法使有效片段尽可能小,即结束位置更靠前。当前片段如果属于上个有效片段的子段,......
  • pta重排链表(一个很清晰的实现,完全模拟链表的实现)
    #include<iostream>#include<iomanip>#include<unordered_map>#include<string>usingnamespacestd;constintN=100010;unordered_map<string,string>neStr;unordered_map<string,int>eStr;stringheadStr;intn;......
  • C#数据结构与算法实战入门指南
    前言在编程领域,数据结构与算法是构建高效、可靠和可扩展软件系统的基石。它们对于提升程序性能、优化资源利用以及解决复杂问题具有至关重要的作用。今天大姚分享一些非常不错的C#数据结构与算法实战教程,希望可以帮助到有需要的小伙伴。C#经典十大排序算法主要讲解C#经典......