Skip to content

鏈結結構

刪除速度快，迭代速度慢

內建

宣告
list<int> v;
複製
int v[9]={1,2,3,4,5,6,7,8,9};   
list<int> a(v,v+9);

插入語法：

  1. 串列名稱.insert(迭代器 , 值)
    會在迭代器所指的位址上，加入此值元素，並回傳此新元素位址的迭代器。
  2. 串列名稱.insert(迭代器 , 非負整數N , 值)
    會在迭代器所指的位址上，加入N個此值元素。(在同個位置放入多個重複的)
  3. 串列名稱.insert(迭代器1 , 迭代器2, 迭代器3)
    會將該串列從迭代器2到迭代器3之間的元素複製並且插入迭代器1的位址。

刪除語法：

  1. 串列名稱.remove(資料值)
    會把串列中符合此值的資料都移除掉。
  2. 串列名稱.remove_if(函數)
    會把串列中的值代入此函數，符合此函數的資料都移除掉
  3. 串列名稱.erase(迭代器)
    會把迭代器所指的元素給刪除，並回傳被移除元素後一個節點位址的迭代器。

索引語法：

  1. 串列名稱.begin();
    回傳開頭
  2. 串列名稱.rbegin();
    回傳最後一個資料

操作語法：

  1. 串列名稱.sort();
    排序，可放cmp，不可選擇區間

自製

製作一個struct陣列

struct st{
    int V=0,L=-1,R=-1;
};

V為數值，L為前一個人的index，R為後一個人的index

#include<bits/stdc++.h>
using namespace std;

int n;

struct st{
    int V=0,L=-1,R=-1;
};
st v[10];
int out(){  //輸出
	int w=0;
    while(1){
        cout<<v[w].V<<" ";
        w=v[w].R;
        if(w==n)break;
    }cout<<endl;
}
int de(int i){ //刪除
    int Lindex=v[i].L;
    int Rindex=v[i].R;
    v[Lindex].R=Rindex;
    v[Rindex].L=Lindex;
    v[i].L=-1;
    v[i].R=-1;
}
int main(){
    istringstream cin("5    1 4 9 16");
    cin>>n;
    v[0].R=1;
    for(int i=1;i<n;i++){
        cin>>v[i].V;
        v[i].L=i-1;
        v[i].R=i+1;
    }
    out();
    de(2);
    de(3);
    out();
}

0 1 4 9 16 
0 1 16

範例：

先加後乘與函數

自製鏈結，如果只需要刪除不需要插入

查找 O(1)
刪除 O(1)
插入 O(1) 只能在最後

#include <bits/stdc++.h>
using namespace std;
#define nn "\n"

// 宣告結構
struct li{
    int L;
    int R;
    int value;
};


//宣告型態
vector <li> lis;
map<int,int>index;
int n;


//輸出全部
void output_all(){
    int it=0;
    while(it!=-1){
        cout<<lis[it].value<<" ";
        it=lis[it].R;
    }
    cout<<nn;
    return;
}

//刪除某數到某數
void del(int x,int y){
    //L=x.l  R=x.r
    int LL=lis[index[x]].L;
    int RR=lis[index[y]].R;
    lis[LL].R=RR;
    lis[RR].L=LL;
}


//插入在某數前面(某數,在某數之前)
//void inse(int m,int x){
//    n+=1;
//    index[m]=lis.size();
//    lis[index[x]].L=lis.size();
//
//}


//主程式
int main(){

    istringstream cin("10  \
10 20 50 60 80 90 100 120 150 190");

    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        index[x]=i;//map對應值
        lis.push_back({i-1,i+1,x});//list 的左右、index
    }
    lis[n-1].R=-1;


    //輸出全部
    output_all();

    //刪除20~120
    del(20,120);

    //輸出全部
    output_all();

}

10 20 50 60 80 90 100 120 150 190
10 150 190