線性表
定義
一個(gè)最簡(jiǎn)單，最基本的數(shù)據(jù)結(jié)構(gòu)。一個(gè)線性表由多個(gè)相同類(lèi)型的元素穿在一次，并且每一個(gè)元素都一個(gè)前驅(qū)（前一個(gè)元素）和后繼（后一個(gè)元素）。
線性表的類(lèi)型
常見(jiàn)的類(lèi)型：數(shù)組、棧、隊(duì)列、鏈表
這些不同數(shù)據(jù)結(jié)構(gòu)的特性可以解決不同種類(lèi)的問(wèn)題
P3156 【深基15.例1】詢(xún)問(wèn)學(xué)號(hào)
題面
題目描述
有 n(n≤2×106)?名同學(xué)陸陸續(xù)續(xù)進(jìn)入教室。我們知道每名同學(xué)的學(xué)號(hào)（在?1?到?109?之間），按進(jìn)教室的順序給出。上課了，老師想知道第?i?個(gè)進(jìn)入教室的同學(xué)的學(xué)號(hào)是什么（最先進(jìn)入教室的同學(xué)?i=1），詢(xún)問(wèn)次數(shù)不超過(guò)?105?次。
輸入格式
第一行?2?個(gè)整數(shù) n?和?m，表示學(xué)生個(gè)數(shù)和詢(xún)問(wèn)次數(shù)。
第二行?n?個(gè)整數(shù)，表示按順序進(jìn)入教室的學(xué)號(hào)。
第三行?m?個(gè)整數(shù)，表示詢(xún)問(wèn)第幾個(gè)進(jìn)入教室的同學(xué)。
輸出格式
輸出?m?個(gè)整數(shù)表示答案，用換行隔開(kāi)。
輸入輸出樣例
輸入 #1?
10 3 1 9 2 60 8 17 11 4 5 14 1 5 9
輸出 #1?
1 8 5
題解
可以直接設(shè)計(jì)一個(gè)數(shù)組記錄每個(gè)學(xué)生的學(xué)號(hào)，并查詢(xún)那m個(gè)詢(xún)問(wèn)即可。還有一種做法是使STL中的容器Vector，又稱(chēng)可變長(zhǎng)度數(shù)組，為了避免空間開(kāi)的太大兒出現(xiàn)程序性錯(cuò)誤。我在介紹STL的一篇博客寫(xiě)到過(guò)vector的常用操作例如
vector<int> v;
v.push_back(a);
v.size();
v.resize(n,m);?
等等，因此，這道題可以一個(gè)一個(gè)把學(xué)號(hào)讀入然后pushback進(jìn)這個(gè)可變長(zhǎng)度數(shù)組。
代碼
#include<iostream>
#include<vector>
using namespace std;
int n,m,tmp;
int main(){
vector<int> stu;
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>tmp;
stu.push_back(tmp);
}
for(int i=0;i<m;i++){
cin>>tmp;
cout<<stu[tmp-1]<<endl;
}
return 0;
}P3613 【深基15.例2】寄包柜
題面
題目描述
超市里有 n(1≤n≤105)?個(gè)寄包柜。每個(gè)寄包柜格子數(shù)量不一，第?i?個(gè)寄包柜有 ai?(1≤ai?≤105)?個(gè)格子，不過(guò)我們并不知道各個(gè) ai??的值。對(duì)于每個(gè)寄包柜，格子編號(hào)從 1 開(kāi)始，一直到?ai??，F(xiàn)在有 q(1≤q≤105)?次操作：
-
1 i j k：在第?i?個(gè)柜子的第?j?個(gè)格子存入物品 k(0≤k≤109)。當(dāng) k=0?時(shí)說(shuō)明清空該格子。 -
2 i j：查詢(xún)第?i?個(gè)柜子的第?j?個(gè)格子中的物品是什么，保證查詢(xún)的柜子有存過(guò)東西。
已知超市里共計(jì)不會(huì)超過(guò)?107 個(gè)寄包格子，ai??是確定然而未知的，但是保證一定不小于該柜子存物品請(qǐng)求的格子編號(hào)的最大值。當(dāng)然也有可能某些寄包柜中一個(gè)格子都沒(méi)有。
輸入格式
第一行 2 個(gè)整數(shù)?n?和?q，寄包柜個(gè)數(shù)和詢(xún)問(wèn)次數(shù)。
接下來(lái)?q?個(gè)整數(shù)，表示一次操作。
輸出格式
對(duì)于查詢(xún)操作時(shí)，輸出答案，以換行隔開(kāi)。
輸入輸出樣例
輸入 #1?
5 4 1 3 10000 118014 1 1 1 1 2 3 10000 2 1 1
輸出 #1?
118014 1
題解
代碼
B3630 排隊(duì)順序
題面
題目描述
有 n(2≤n≤106)?個(gè)小朋友，他們的編號(hào)分別從?1?到?n?，F(xiàn)在他們排成了一個(gè)隊(duì)伍，每個(gè)小朋友只知道他后面一位小朋友的編號(hào)。現(xiàn)在每個(gè)小朋友把他后面是誰(shuí)告訴你了，同時(shí)你還知道排在隊(duì)首的是哪位小朋友，請(qǐng)你從前到后輸出隊(duì)列中每個(gè)小朋友的編號(hào)。
輸入格式
第一行一個(gè)整數(shù)?n，表示小朋友的人數(shù)。
第二行?n?個(gè)整數(shù)，其中第?i?個(gè)數(shù)表示編號(hào)為?i?的小朋友后面的人的編號(hào)。如果這個(gè)數(shù)是?0，則說(shuō)明這個(gè)小朋友排在最后一個(gè)。
第三行一個(gè)整數(shù)??，表示排在第一個(gè)的小朋友的編號(hào)。
輸出格式
一行?n?個(gè)整數(shù)，表示這個(gè)隊(duì)伍從前到后所有小朋友的編號(hào)，用空格隔開(kāi)。
輸入輸出樣例
輸入 #1復(fù)制文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-657582.html
6 4 6 0 2 3 5 1
輸出 #1復(fù)制文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-657582.html
1 4 2 6 5 3
題解
代碼
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之線性表的類(lèi)型運(yùn)用Linear Lists: 數(shù)組，棧，隊(duì)列，鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
