線性表

定義

一個最簡單，最基本的數據結構。一個線性表由多個相同類型的元素穿在一次，并且每一個元素都一個前驅（前一個元素）和后繼（后一個元素）。

線性表的類型

常見的類型：數組、棧、隊列、鏈表

這些不同數據結構的特性可以解決不同種類的問題

P3156 【深基15.例1】詢問學號

題面

題目描述

有 n(n≤2×106)?名同學陸陸續續進入教室。我們知道每名同學的學號（在?1?到?109?之間），按進教室的順序給出。上課了，老師想知道第?i?個進入教室的同學的學號是什么（最先進入教室的同學?i=1），詢問次數不超過?105?次。

輸入格式

第一行?2?個整數 n?和?m，表示學生個數和詢問次數。

第二行?n?個整數，表示按順序進入教室的學號。

第三行?m?個整數，表示詢問第幾個進入教室的同學。

輸出格式

輸出?m?個整數表示答案，用換行隔開。

輸入輸出樣例

輸入 #1?

10 3
1 9 2 60 8 17 11 4 5 14
1 5 9

輸出 #1?

1
8
5

題解

可以直接設計一個數組記錄每個學生的學號，并查詢那m個詢問即可。還有一種做法是使STL中的容器Vector，又稱可變長度數組，為了避免空間開的太大兒出現程序性錯誤。我在介紹STL的一篇博客寫到過vector的常用操作例如
vector<int> v;

v.push_back(a);

v.size();

v.resize(n,m);?

等等，因此，這道題可以一個一個把學號讀入然后pushback進這個可變長度數組。

代碼

#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)?個寄包柜。每個寄包柜格子數量不一，第?i?個寄包柜有 ai?(1≤ai?≤105)?個格子，不過我們并不知道各個 ai??的值。對于每個寄包柜，格子編號從 1 開始，一直到?ai?。現在有 q(1≤q≤105)?次操作：

• 1 i j k：在第?i?個柜子的第?j?個格子存入物品 k(0≤k≤109)。當 k=0?時說明清空該格子。
• 2 i j：查詢第?i?個柜子的第?j?個格子中的物品是什么，保證查詢的柜子有存過東西。

已知超市里共計不會超過?107 個寄包格子，ai??是確定然而未知的，但是保證一定不小于該柜子存物品請求的格子編號的最大值。當然也有可能某些寄包柜中一個格子都沒有。

輸入格式

第一行 2 個整數?n?和?q，寄包柜個數和詢問次數。

接下來?q?個整數，表示一次操作。

輸出格式

對于查詢操作時，輸出答案，以換行隔開。

輸入輸出樣例

輸入 #1?

5 4
1 3 10000 118014
1 1 1 1
2 3 10000
2 1 1

輸出 #1?

118014
1

題解

代碼

B3630 排隊順序

題面

題目描述

有 n(2≤n≤106)?個小朋友，他們的編號分別從?1?到?n。現在他們排成了一個隊伍，每個小朋友只知道他后面一位小朋友的編號。現在每個小朋友把他后面是誰告訴你了，同時你還知道排在隊首的是哪位小朋友，請你從前到后輸出隊列中每個小朋友的編號。

輸入格式

第一行一個整數?n，表示小朋友的人數。

第二行?n?個整數，其中第?i?個數表示編號為?i?的小朋友后面的人的編號。如果這個數是?0，則說明這個小朋友排在最后一個。

第三行一個整數??，表示排在第一個的小朋友的編號。

輸出格式

一行?n?個整數，表示這個隊伍從前到后所有小朋友的編號，用空格隔開。

輸入輸出樣例

輸入 #1復制

6
4 6 0 2 3 5
1

輸出 #1復制

1 4 2 6 5 3

題解

代碼