ZISUOJ 数据结构-线性表

题目列表:

问题 A: 逆序链表建立

思路:

        可以使用头插法插入所有元素后正序遍历输出或者使用尾插法逆序遍历,推荐使用双链表。这是链表系列的第一个题,那这个题下面的参考题解的各种解法我会尽可能写全一些。

参考题解1(数组模拟单链表使用头插法及正序遍历):

#include<bits/stdc++.h>
using namespace std;
constexpr int N = 1e5+5;
int head,e[N],ne[N],idx;//数组模拟链表 
void init(){//初始化链表 head=-1;idx=0;
}
void add(int x){//头插法,插入x e[idx]=x,ne[idx]=head,head=idx++; 
} 
void solve(){init();int t;while(cin >> t,t>=0){add(t);}for(int i = head;i!=-1;i=ne[i]){int j = e[i];cout << j << ' ';}cout << '\n';
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T = 1;//cin >> T;while(T--) solve();return 0;
}

参考题解2(数组模拟双链表使用头插法顺序遍历):

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5+5;
int e[N],l[N],r[N],idx;
void init(){r[0]=1,l[1]=0,idx=2;
}
void add_to_head(int x){e[idx]=x,r[idx]=r[0],l[idx]=0,r[0]=idx++;
}
void solve(){init();int t;while(cin >> t,t>=0) add_to_head(t);for(int i = 0;i!=1;i=r[i]){if(i==0) continue;int j = e[i];cout << j << ' ';}cout << '\n';
}
int main(){ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);int T = 1;
//	cin >> T;while(T--) solve();return 0;
}

参考题解3(数组模拟双链表使用尾插法逆序遍历):

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5+5;
int e[N],l[N],r[N],idx;
void init(){r[0]=1,l[1]=0,idx=2;
}
void add_to_tail(int x){e[idx]=x,r[idx]=1,l[idx]=l[1],l[1]=idx++;
}
void solve(){init();int t;while(cin >> t,t>=0) add_to_tail(t);for(int i = 1;i!=0;i=l[i]){if(i==1) continue;int j = e[i];cout << j << ' ';}cout << '\n';
}
int main(){ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);int T = 1;
//	cin >> T;while(T--) solve();return 0;
}

参考题解4(使用stl的双链表list头插法顺序遍历):

#include <bits/stdc++.h>
using namespace std;
list<int> a;
void solve(){int t;while(cin >> t,t>=0) a.push_front(t);for(auto i = a.begin();i!=a.end();i++){cout << *i << ' ';}cout << '\n';
}
int main(){ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);int T = 1;
//	cin >> T;while(T--) solve();return 0;
}

参考题解5(使用stl的双链表list尾插法逆序遍历):

#include <bits/stdc++.h>
using namespace std;
list<int> a;
void solve(){int t;while(cin >> t,t>=0) a.push_back(t);for(auto i = a.rbegin();i!=a.rend();i++){cout << *i << ' ';}cout << '\n';
}
int main(){ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);int T = 1;
//	cin >> T;while(T--) solve();return 0;
}

参考题解6(手搓单链表):

#include <bits/stdc++.h> 
using namespace std;
#define ElemType int
struct LNode{ElemType data;LNode *next;
};
LNode *init(){LNode *head;head=(LNode *)malloc(sizeof(LNode));head->next=NULL;return head;
}
void add_to_head(LNode *head,ElemType x){LNode *p;p = (LNode *)malloc(sizeof(LNode));p->data=x;p->next=head->next;head->next=p;
}
void add_to_tail(LNode *head,ElemType x){LNode *p;p = (LNode *)malloc(sizeof(LNode));p->data=x;p->next=NULL;if(head->next==NULL){head->next=p;}else{LNode *q;q=head->next;while(q->next!=NULL) q=q->next;q->next=p;}
}
LNode *find_x(LNode *head,ElemType x){LNode *p;p = head->next;while(p->data!=x&&p->next!=NULL){p=p->next;}if(p->next==NULL) return head;else return p;
}
void delete_k(LNode *head,LNode *p){if(head->next==NULL){cout << "delete is failed.\n";}LNode *q;q = head;while(q->next!=p){q=q->next;}q->next=p->next;free(p);
}
LNode *find_max_element(LNode *head,ElemType &max_element){if(head->next==NULL) return head;LNode *p,*q;p = head->next;while(p->next!=NULL){if(p->data>max_element){max_element=p->data;q = p;}p=p->next;}if(p->data>max_element){max_element=p->data;q = p;}return q;
}
LNode *sort_LNode(LNode *head){if(head->next==NULL){cout << "the LNode which you wanna sort is empty!\n";return head;}LNode *p,*q,*pos;p = head;q = init();ElemType max_element = -1;pos=find_max_element(p,max_element);while(pos!=p){add_to_head(q,pos->data);delete_k(p,pos);max_element = -1;pos=find_max_element(p,max_element);}return q;
}
LNode *merge_LNode(LNode *head1,LNode *head2){if(head1->next==NULL&&head2->next==NULL){cout << "two of LNodes is empty!\n";return head1;}LNode *p;p = head1;while(p->next!=NULL){p=p->next;}p->next=head2->next;free(head2);return head1;
}
void print(LNode *head){if(head->next==NULL){cout << "This LNode is empty!\n";return;}LNode *p;p=head->next;while(p->next!=NULL){cout << p->data << ' ';p=p->next;}cout << p->data << '\n';
}
void solve(){LNode *L = init();ElemType t;while(cin >> t,t>=0) add_to_head(L,t);print(L);
}
int main(){ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);int T = 1;
//	cin >> T;while(T--) solve();return 0;
}

问题 B: 顺向链表建立

思路:

        这个题头插还是尾插法不影响查找,只要遍历一遍链表判断即可。

参考题解1(数组模拟单链表):

#include<bits/stdc++.h>
using namespace std;
constexpr int N = 1e5+5;
int head,e[N],ne[N],idx;//数组模拟链表 
void init(){//链表初始化 head=-1;idx=0;
}
void add(int x){//头插法 e[idx]=x,ne[idx]=head,head=idx++;
}
void solve(){init();int t;while(cin >> t,t>=0) add(t);int x;cin >> x;for(int i = head;i!=-1;i=ne[i]){int j = e[i];if(x==j){cout << "YES\n";return;}}cout << "NO\n";
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T = 1;//cin >> T;while(T--) solve();return 0;
}

参考题解2(使用stl的list):

#include <bits/stdc++.h>
using namespace std;
list<int> a;
void solve(){int t;while(cin >> t,t>=0) a.push_back(t);int x;cin >> x;for(auto i = a.begin();i!=a.end();i++){if(*i==x){cout << "YES\n";return;}}cout << "NO\n";
}
int main(){ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);int T = 1;
//	cin >> T;while(T--) solve();return 0;
}

问题 C: 结点删除

思路:

        其实题目的意思,如果重复出现要找的数都要删除它,这里既以使用数组模拟双链表删除,但使用stl的list进行删除指定元素更加便捷。

参考题解:

#include <bits/stdc++.h>
using namespace std;
list<int> a;
void solve(){int t;while(cin >> t,t>=0) a.push_back(t);int x;cin >> x;//要查找的数 if(find(a.begin(),a.end(),x)==a.end()) cout << "NO\n";else{a.remove(x);for(auto i=a.begin();i!=a.end();i++) cout << *i << ' ';cout << '\n';}
}
int main(){ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);int T = 1;
//	cin >> T;while(T--) solve();return 0;
}

问题 D: 有序链表

思路:

        可以使用数组模拟两个单链表,每次循环找第一个链表里的最大值,然后将这个最大值头插到第二个链表并删除第一个链表中的该节点,最后遍历输出第二个链表即可。当然,用stl的list写起来更快。

参考题解1(数组模拟两个单链表求解):

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e4+5;
int e1[N],l1[N],r1[N],idx1;
int e2[N],l2[N],r2[N],idx2;
void init(int (&l)[N],int (&r)[N],int &idx){r[0]=1,l[1]=0,idx=2;
}
void add(int (&e)[N],int (&l)[N],int (&r)[N],int &idx,int k,int x){e[idx]=x;r[idx]=r[k],l[idx]=k;l[r[k]]=idx,r[l[k]]=idx++;
}
void remove(int (&l)[N],int (&r)[N],int k){l[r[k]]=l[k],r[l[k]]=r[k];
}
void solve(){init(l1,r1,idx1);//初始化链表 int t,cnt=0;//cnt用于记录链表的大小(元素个数)while(cin >> t,t>=0) add(e1,l1,r1,idx1,0,t),cnt++;int maxn=-1,maxidx;init(l2,r2,idx2);//初始化结果链表 for(int k = 1;k<=cnt;k++){maxn=-1;for(int i = 0;i!=1;i=r1[i]){if(i==0) continue;int j = e1[i];if(j>maxn){maxn=j;maxidx=i;}}add(e2,l2,r2,idx2,0,maxn);remove(l1,r1,maxidx);}for(int i = 0;i!=1;i=r2[i]){if(i==0) continue;int j = e2[i];cout << j << ' ';}cout << '\n';
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T = 1;//cin >> T;while(T--) solve(); return 0;
}

参考题解2(使用stl的list求解):

#include <bits/stdc++.h>
using namespace std;
list<int> a;
void solve(){int t;while(cin >> t,t>=0) a.push_back(t);a.sort();for(auto i = a.begin();i!=a.end();i++) cout << *i << ' ';cout << '\n';
}
int main(){ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);int T = 1;
//	cin >> T;while(T--) solve();return 0;
}

问题 E: 链表合并

思路:

        同理,可以用数组模拟三个双链表,然后循环找前两个链表中的最大值,然后头插到第三个链表中并且删除指定链表中的指定节点,最后遍历输出第三个链表即可。stl的list也能轻松解决。

参考题解1(使用数组模拟三个双链表解决):

#include<bits/stdc++.h>
using namespace std;
constexpr int N = 1e4+5;
int e1[N],l1[N],r1[N],idx1;
int e2[N],l2[N],r2[N],idx2;
int e3[N],l3[N],r3[N],idx3;
void init(int (&l)[N],int (&r)[N],int &idx){r[0]=1,l[1]=0,idx=2;
}
void add_to_k(int (&e)[N],int (&l)[N],int (&r)[N],int &idx,int k,int x){e[idx]=x;r[idx]=r[k],l[idx]=k;l[r[k]]=idx,r[l[k]]=idx++;
}
void remove(int (&l)[N],int (&r)[N],int k){l[r[k]]=l[k],r[l[k]]=r[k];
}
void solve(){init(l1,r1,idx1);init(l2,r2,idx2);int t,cnt1=0,cnt2=0;//cnt记录链表的大小 while(cin >> t,t>=0) add_to_k(e1,l1,r1,idx1,0,t),cnt1++;while(cin >> t,t>=0) add_to_k(e2,l2,r2,idx2,0,t),cnt2++;init(l3,r3,idx3);int maxn = -1,maxidx,flag=0;for(int x = 0;x<cnt1+cnt2;x++){maxn=-1;for(int i = 0;i!=1;i=r1[i]){if(i==0) continue;int j = e1[i];if(j>maxn){flag=1;maxn = j;maxidx = i;}}for(int i = 0;i!=1;i=r2[i]){if(i==0) continue;int j = e2[i];if(j>maxn){flag=2;maxn=j;maxidx=i;}}add_to_k(e3,l3,r3,idx3,0,maxn);if(flag==1){remove(l1,r1,maxidx);}else{//flag==2remove(l2,r2,maxidx);}}for(int i = 0;i!=1;i=r3[i]){if(i==0) continue;int j = e3[i];cout << j << ' ';}cout << '\n';
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T = 1;//cin >> T;while(T--) solve();return 0;
}

参考题解2(stl yyds):

#include <bits/stdc++.h>
using namespace std;
list<int> a,b;
void solve(){int t;while(cin >> t,t>=0) a.push_back(t);while(cin >> t,t>=0) b.push_back(t);a.splice(a.end(),b);a.sort();for(auto i = a.begin();i!=a.end();i++) cout << *i << ' ';cout << '\n';
}
int main(){ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);int T = 1;
//	cin >> T;while(T--) solve();return 0;
}

问题 F: 双向链表(完善程序)

思路:

        数组模拟双链表的填空题,想明白最后题目要我们输出的右侧第一个大于它的数,我们可以让每个结点的后继指向第一个大于它的数(若没有,则指向n+1)。

参考题解:

#include<iostream>
using namespace std;
const int N=100010;
int n,l[N],r[N],a[N];
int main()
{cin>>n;for(int i=1;i<=n;i++){int x;cin>>x;
//        _____(1)_____;a[x]=i;}for(int i=1;i<=n;i++){
//        r[i]=____(2)_____;r[i]=i+1;l[i]=i-1;}for(int i=1;i<=n;i++){
//      l[_____(3)_____]=l[a[i]];
//		r[l[a[i]]]=r[_____(4)____];l[r[a[i]]]=l[a[i]];r[l[a[i]]]=r[a[i]];}for(int i=1;i<=n;i++) 
//		cout<<_____(5)_____<<" ";cout<<r[i]<<" ";cout<<endl;return 0;
}

问题 G: 手拉手游戏

思路:

        这是上一题F题的具体应用,把F题的代码修改一下搬过来即可。

参考题解:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e2+5;
int n;
int e[N],l[N],r[N],idx;
void solve(){cin >> n;string s;cin >> s;s=' '+s;for(int i = 1;i<=n;i++){int x = s[i]-'0';e[x]=i; }for(int i = 1;i<=n;i++){l[i]=i-1,r[i]=i+1;}for(int i = 1;i<=n;i++){l[r[e[i]]]=l[e[i]];r[l[e[i]]]=r[e[i]];}for(int i = 1;i<=n;i++){cout << r[i];}cout << '\n';
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T = 1;//cin >> T;while(T--) solve();return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【OTA】STM32-OTA升级——持续更新

【OTA】STM32-OTA升级——持续更新 文章目录 前言一、ymodem串口协议1、Ymodem 协议2、PC3、蓝牙4、WIFI云平台 二、UDS车载协议1.UDS协议 总结 前言 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、ymodem串口协议 1、Ymodem 协议 STM32 Ymodem …

【I/O】基于事件驱动的 I/O 模型---Reactor

Reactor 模型 BIO 到 I/O 多路复用 为每个连接都创建一个线程 假设我们现在有一个服务器&#xff0c;想要对接多个客户端&#xff0c;那么最简单的方法就是服务端为每个连接都创建一个线程&#xff0c;处理完业务逻辑后&#xff0c;随着连接关闭线程也要销毁&#xff0c;但是…

每日一题(leetcode238):除自身以外数组的乘积--前缀和

不进阶是创建两个数组&#xff1a; class Solution { public:vector<int> productExceptSelf(vector<int>& nums) {int nnums.size();vector<int> left(n);vector<int> right(n);int mul1;for(int i0;i<n;i){mul*nums[i];left[i]mul;}mul1;for…

前端开发攻略---根据音频节奏实时绘制不断变化的波形图。深入剖析如何通过代码实现音频数据的可视化。

1、演示 2、代码分析 逐行解析 JavaScript 代码块&#xff1a; const audioEle document.querySelector(audio) const cvs document.querySelector(canvas) const ctx cvs.getContext(2d)这几行代码首先获取了 <audio> 和 <canvas> 元素的引用&#xff0c;并使用…

Java编程练习之抽象类与抽象方法

使用抽象类和抽象方法时&#xff0c;需要遵循以下原则&#xff1a; 1&#xff09;在抽象类中&#xff0c;可以包含抽象方法&#xff0c;也可以不包含抽象方法&#xff0c;但是包含了抽象方法的类必须被定义为抽象类&#xff1b; 2&#xff09;抽象类不能直接被实例化&#xf…

BugKu:Flask_FileUpload

Flask_FileUpload 解题思路 查看源码&#xff1a; 编写上传的文件 获得结果 小结 文件上传漏洞&#xff1a; 文件上传漏洞是指用户上传了一个可执行的脚本文件&#xff0c;并通过此脚本文件获得了执行服务器端命令的能力。这种攻击方式是最为直接和有效的&#xff0c;“文件上…

探索ERC20代币:构建您的第一个去中心化应用

下面文章中会涉及到该资源中的代码&#xff0c;如果想要完整版代码可以私信我获取&#x1f339; 文章目录 概要整体架构流程技术名词解释ERC20智能合约web3.js 技术细节ERC20合约部署创建前端界面前端与智能合约互连运行DAPP 小结 概要 在加密货币世界中&#xff0c;ERC20代币…

poi-tl的使用(通俗易懂,全面,内含动态表格实现 包会!!)

最近在做项目时候有一个关于解析Html文件&#xff0c;然后将解析的数据转化成word的需求&#xff0c;经过调研&#xff0c;使用poi-tl来实现这个需求&#xff0c;自己学习花费了一些时间&#xff0c;现在将这期间的经验总结起来&#xff0c;让大家可以快速入门 poi-tl的介绍 …

大数据产品有哪些分类?各类里知名大数据产品都有哪些?

随着互联网技术的持续进步和全球数字化转型的推进&#xff0c;我们正处于一个数据爆炸的时代。在这样的大背景下&#xff0c;大数据已经逐渐崭露头角&#xff0c;成为了推动各行各业发展的关键因素和核心资源。大数据不仅仅是指数据的规模巨大&#xff0c;更重要的是它蕴含的价…

Python八股文:基础知识Part2

1. Python中变量的保存和访问 Python中的变量实际上是一个指向对象的引用&#xff0c;每个对象都有一个唯一的标识符&#xff08;即内存地址&#xff09;。对于一些不可变对象&#xff0c;如字符串和整数&#xff0c;因为它们的值不可更改&#xff0c;所以当多个变量引用相同的…

彩虹聚合DNS管理系统源码

聚合DNS管理系统可以实现在一个网站内管理多个平台的域名解析&#xff0c;目前已支持的域名平台有&#xff1a;阿里云、腾讯云、华为云、西部数码、CloudFlare。本系统支持多用户&#xff0c;每个用户可分配不同的域名解析权限&#xff1b;支持API接口&#xff0c;支持获取域名…

建造者模式:构造复杂对象的艺术

在面向对象的设计中&#xff0c;建造者模式是一种重要的创建型设计模式&#xff0c;专门用来构建复杂的对象。它主要目的是将对象的构造代码与其表示代码分离&#xff0c;使同样的构建过程可以创建不同的表示。本文将详细介绍建造者模式的定义、实现、应用场景以及优缺点&#…

虚拟货币:数字金融时代的新工具

在数字化时代的到来之后&#xff0c;虚拟货币逐渐成为了一种广为人知的金融工具。虚拟货币是一种数字化的资产&#xff0c;它不像传统货币那样由政府或中央银行发行和监管。相反&#xff0c;虚拟货币通过密码学技术和分布式账本技术来实现去中心化的发行和交易。 虚拟货币的代…

内网通如何去除广告,内网通免广告生成器

公司使用内网通内部传输确实方便&#xff01;但是会有广告弹窗推送&#xff01;这个很烦恼&#xff01;那么如何去除广告呢&#xff01; 下载&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1CVVdWexliF3tBaFgN1W9aw?pwdhk7m 提取码&#xff1a;hk7m ID&#xff1a;…

如何进行宏观经济预测

理性预期经济学提出了理性预期的概念&#xff0c;强调政府在制定各种宏观经济政策时&#xff0c;要考虑到各行为主体预期对政策实施有效性的影响&#xff0c;积极促成公众理性预期的形成&#xff0c;从而更好地实现宏观调控的目标。政府统计要深入开展统计分析预测研究&#xf…

享元模式:优化资源利用的高效策略

在面向对象的软件开发中&#xff0c;享元模式是一种结构型设计模式&#xff0c;旨在减少内存使用&#xff0c;通过共享尽可能多的相似对象来提高应用程序的效率。本文将详细介绍享元模式的定义、实现、应用场景以及优缺点。 1. 享元模式的定义 享元模式&#xff08;Flyweigh…

免费的 ChatGPT 网站(六个)

&#x1f525;博客主页&#xff1a; 小羊失眠啦. &#x1f3a5;系列专栏&#xff1a;《C语言》 《数据结构》 《C》 《Linux》 《Cpolar》 ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 文章目录 一、insCode二、讯飞星火三、豆包四、文心一言五、通义千问六、360智脑 现在智能…

PoE 技术

1 PoE 技术产生背景 随着 WLAN 、 VoIP 、网络视频监控等新业务的飞速发展,大量的无线 LAN 访问点、 IP 电话、 IP 网络摄像头等基于 IP 的终端出现在工业现场。这些设备通常数量众多、位置特殊 、 布线复杂、设备取电困难,其实施部署不仅消耗大量人力物力,…

终端界面外观修改

终端界面外观修改 考虑到实验报告等内容截取命令行会出现不清晰现象 所以特意对cmd命令行的界面外观修改方便打印的时候清晰显示内容 流程 1.右键命令行窗口&#xff0c;点击属性 2.点击颜色 3.选择屏幕背景&#xff0c;窗口颜色选择白色 4.选择屏幕文字&#xff0c;点…

【计算机毕业设计】基于Java+SSM的实战开发项目150套(附源码+演示视频+LW)

大家好&#xff01;我是程序猿老A&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f9e1;今天给大家分享150的Java毕业设计&#xff0c;基于ssm框架&#xff0c;这些项目都经过精心挑选&#xff0c;涵盖了不同的实战主题和用例&#xff0c;可做毕业设计和课程…