Danh sách liên kết

1. Giới thiệu

Cấu trúc danh sách liên kết

Danh sách liên kết (linked list) được dùng để lưu giữ các phân tử có cùng kiểu giá trị. Bên dưới là ví dụ minh họa sử dụng danh sách liên kết gồm 4 phần tử để lưu giữ dãy A, B, C, D. Phần tử đầu tiên của danh sách liên kết gọi là “head”.
Trong khi các phần tử trong mảng được lưu giữ liên tiếp trong bộ nhớ, thì các phần tử trong danh sách liên kết có thể nằm ở các vị trí khác nhau trong bộ nhớ. Mỗi phần tử (node) trong danh sách liên kết gồm hai thành phần:
• “data”: Lưu giữ dữ liệu.
• “next”: Con trỏ liên kết chỉ đến phần tử tiếp theo trong danh sách liên kết.

2. Duyệt trên danh sách liên kết

Bắt đầu từ phần tử đầu tiên ”head”, di chuyển đến các phần tử khác trên danh sách liên kết dựa vào biến con trỏ liên kết “next” như bên dưới.

3. Truy cập phần tử trong danh sách liên kết

Để truy cập phần tử thứ p trong danh sách liên kết, chúng ta phải di chuyển từ phần tử đầu tiên (head) cho đến phần tử thứ p như bên dưới.

4. Chèn một phần tử vào danh sách liên kết

Để chèn một phần tử có giá trị X vào vị trí p trong danh sách liên kết, chúng ta tiến hành hai bước cơ bản sau:
• Tạo một phần tử mới chứa giá trị X.
• Gán giá trị con trỏ liên kết “next” của phần tử thứ (p-1) và phần tử mới như bên dưới.

5. Xóa một phần tử khỏi danh sách liên kết

Để xóa phần tử tại vị trí p khỏi danh sách liên kết, chúng ta thay đổi giá trị con trỏ liên kết
“next” của phần tử thứ (p-1) như hình dưới. Sau đó xóa phần tử thứ p ra khỏi bộ nhớ!

6. Danh sách liên kết đôi

Danh sách liên kết được trình bày ở trên được gọi là danh sách liên kết đơn, bởi vì mỗi phần tử trong danh sách liên kết đơn có đúng một biến con trỏ liên kết “next” chỉ đến phần tử tiếp theo trong danh sách.Việc duyệt trên danh sách liên kết đơn chỉ thực hiện được theo một chiều từ đầu danh sách đến cuối danh sách và không thực hiện được theo chiều ngược lại.

Danh sách liên kết đôi là mở rộng của danh sách liên kết đơn, trong đó mỗi phần tử có hai con trỏ liên kết:
• “previous” trỏ đến phần tử phía trước trong danh sách.
• “next” trỏ đến phần tử tiếp theo trong danh sách.
Bên dưới là ví dụ minh họa sử dụng danh sách liên kết đôi để lưu giữ dãy A, B, C, D. Phần tử đầu tiên của danh sách liên kết đôi gọi là “head”, phần tử cuối cùng gọi là “tail”.

Danh sách liên kết đôi thường được dùng trong các bài toán cần duyệt trên danh sách theo cả hai chiều. Nó cũng hay được dùng trong các bài toán mà các phép toán chèn và xóa các phần tử trong danh sách thường diễn ra ở một trong hai đầu của danh sách bởi vì các phép toán này được thực hiện một cách nhanh chóng.

7. So sánh cấu trúc danh sách liên kết và cấu trúc mảng

• Các phần tử trong mảng được lưu giữ liên tục trong bộ nhớ, cho nên việc truy cập và thay đổi giá trị một phần tử bất kì trong mảng rất nhanh. Các phần tử trong danh sách liên kết được lưu giữ tại các vị trí khác nhau trong bộ nhớ máy tính, cho nên việc truy cập và thay đổi giá trị một phần tử bất kì tốn nhiều thời gian.
• Kích thước của mảng phải được xác định và khai báo trước khi sử dụng, điều này dẫn đến khó khăn và dư thừa bộ nhớ trong các bài toán mà số lượng các phần tử không được xác định trước. Khi sử dụng danh sách liên kết, chúng ta không phải khai báo trước kích thước của danh sách. Chúng ta chỉ xin cấp phát bộ nhớ khi thêm phần tử mới vào danh sách liên kết, và sẽ xóa phần tử đó khỏi bộ nhớ khi nó bị xóa khỏi danh sách liên kết.

NKLUCK – spoj

Đề bài:

Thuật toán:

    Để giải bài toán này, ta giải bài toán trung gian khác như sau
    Gọi

    • A là số đoạn nhận X là phần tử trung vị
    • B là số đoạn nhận X + 1 là phần tử trung vị

    => Result = (A – B) / (n * (n + 1) / 2) ;

    Để tính số đoạn nhận X là phần tử trung vị ta chuyển đổi mảng A về, nếu A[i] >= X => A[i] = 1 ngược lại A[i] = 0.

    Một đoạn nhận X là trung vị khi và chỉ khi tổng của đoạn đó ko âm. Đến đây, ta dùng cây BIT để tính toán .

Code:

#include <bits/stdc++.h>
using namespace std;
 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define long long long
 
const int N = 1e6+10;
 
class FenwickTree {
private:
    long t[N][2];
public:
    void update(int x, int type) {
        for (; x <= N; x += x & -x)
            t[x][type]++;
    }
    long get(int x, int type) {
        long res = 0;
        for (; x > 0; x -= x & -x)
            res += t[x][type];
        return res;
    }
} BIT;
 
int n, m, k;
int a[N], f[N], b[N];
 
void Enter() {
    scanf("%d%d", &n, &k);
    FOR(i, 1, n) scanf("%d", &a[i]);
}
 
long calc(int x, int type) {
    m = 0;
    for (int i = 1; i <= n; ++i) {
        f[i] = f[i-1] + (a[i] >= x);
        b[++m] = 2 * f[i] - i - 1;
        b[++m] = 2 * f[i-1] - i;
    }
 
    sort(b + 1, b + m + 1);
 
    long res = 0;
    FOR(i, 1, n) {
        int cur = lower_bound(b + 1, b + m + 1, 2 * f[i - 1] - i) - b;
        BIT.update(cur, type);
        cur = lower_bound(b + 1, b + m + 1, 2 * f[i] - i - 1) - b;
        res += BIT.get(cur, type);
    }
    return res;
}
 
void Process() {
    long res = calc(k, 0) - calc(k + 1, 1);
    double ans = 1ll * n * (n + 1) / 2;
    ans = res / ans;
    printf("%.6lf", ans);
}
 
int main() {
 //   freopen("input.in", "r", stdin);
 
    Enter();
    Process();
 
    return 0;
}

C11PAIRS – spoj

Đề bài

Thuật toán

-Đầu tiên ta khởi tạo một stack để lưu chiều cao của các bạn theo thứ tự không tăng (s[i]<=s[i-1])

-Đầu tiên ta cho a[n] vào stack, khởi tạo ds=0,sn=1(sn là số phần tử trong ngăn xếp);

-Duyệt i từ n-1 về 1, với mỗi i:

+Tìm vị trí cuối cùng trong stacks mà s[i]>a[i], giả sử ta gọi là vt.

+Nếu vt=0 nghĩa là người đứng ở vị trí i có thể nhìn thấy mọi người trong stack vì vậy ds+=sn;

+Nếu vt!=0 nghĩa là người đứng ở vị trí i có thể nhìn thấy từ người thứ vt đến người thứ sn trong stack vì vậy ds+=(sn-vt+1);

+Tiếp theo ta sẽ bỏ các s[i]<a[i] trong stack sau đó thêm a[i] vào stack.

-Kết quả của bài này chính là ds.

-Từ đó ta thu được thuật toán với đpt O(n*log(n)), mặc dù có thể giảm đpt xuống còn O(n) nhưng mình thấy thuật toán này khá đơn giản và dễ code, có thể là ngắn hơn. Đây là code của mình:

Code

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 1E6+3;
const int oo = 1e9+3;
 
int n, i, j, a[MAXN], c[MAXN], s[MAXN], top, tmp;
ll ans;
 
int main() {
        ios_base::sync_with_stdio(0); cin.tie(0);
    	#ifndef ONLINE_JUDGE
    	freopen("test.inp", "r", stdin);
    	freopen("test.out", "w", stdout);
    	#endif //yeulaptrinh.pw
    cin >> n;
    FOR(i,1,n) cin >> a[i];
 
    top = 0;
    FOR(i,1,n) {
        tmp = 1;
        while (top&&s[top]<=a[i]) {
            ans += c[top];
            if (s[top]==a[i]) tmp += c[top];
            c[top] = 0; top--;
        }
        if (top) ans++;
        // push
        top++;
        s[top] = a[i];
        c[top] = tmp;
    }
    cout << ans;
	return 0;
}

NKINV – spoj

Đề bài

Thuật toán

  • Interval Tree

Code

uses    math;
const   fi='';
        fo='';
        maxn = 60000+3;
var     t       :array[1..maxn*4] of longint;
        i,j,n   :longint;
        a       :ARRAY[1..maxn] of longint;
        ma      :longint;
        res     :int64;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n);for i:=1 to n do read(a[i]);
        close(input);
end;
procedure update(k,l,r,i:longint);
var     m :longint;
begin
        if (i<l) or (i>r) then exit;
        if l=r then
                begin
                        inc(t[k]);
                        exit;
                end;
        m := (l+r) div 2;
        update(k*2,l,m,i);
        update(k*2+1,m+1,r,i);
        t[k] := t[k*2] + t[k*2+1];
end;
function get(k,l,r,i,j:longint):longint;
var     m,tam1,tam2     :longint;
begin
        if i>j then exit(0);
        if (i>r) or (j<l) then exit(0);
        if (i<=l) and (j>=r) then
                begin
                        exit(t[k]);
                end;
        m := (l+r) div 2;
        tam1 := get(k*2,l,m,i,j);
        tam2 := get(k*2+1,m+1,r,i,j);
        get:= tam1+tam2;
end;
procedure process;
var     i :longint;
begin
        for i:=1 to n do ma := max(ma,a[i]);
        res := 0;
        for i:=1 to n do
                begin
                        res := res + get(1,1,ma,a[i]+1,ma);
                        update(1,1,ma,a[i]);
                end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.

NKLINEUP – spoj

Đề bài:

Thuật toán:

  • Interval tree

Code:

#include <bits/stdc++.h>
using namespace std;
 
int n,q;
vector<int> a;
vector< pair<int,int> > node;
int resmax, resmin;
 
void Init_Tree(int k, int l, int r, int i)
{
    if(l>i || r<i) return;
    if(l==r)
    {
        node[k]=make_pair(a[i],a[i]);
        return;
    }
    int m=(l+r)/2;
    Init_Tree(2*k,l,m,i);
    Init_Tree(2*k+1,m+1,r,i);
    node[k]=make_pair(max(node[2*k].first, node[2*k+1].first),min(node[2*k].second, node[2*k+1].second));
}
 
void Init()
{
    scanf("%d%d",&n,&q);
    a.resize(n+2);
    node.resize(4*n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        Init_Tree(1,1,n,i);
    }
}
 
void Query(int k, int l, int r, int A, int B)
{
    if(l>B || r<A) return;
    if(A<=l && B>=r)
    {
        resmax=max(resmax,node[k].first);
        resmin=min(resmin,node[k].second);
        return;
    }
    int m=(l+r)/2;
    Query(2*k,l,m,A,B);
    Query(2*k+1,m+1,r,A,B);
}
 
void Solve()
{
    for (int i=1;i<=q;i++)
    {
        int A, B;
        scanf("%d%d",&A,&B);
        resmax=0;
        resmin=10000000;
        Query(1,1,n,A,B);
        printf("%dn",resmax-resmin);
    }
}
 
int main()
{
    Init();
    Solve();
}
uses    math;
const   fi='';
        fo='';
        maxn=50000;
        maxq=200000;
type    arrp=record
                dau:longint;
                cuoi:longint;
                end;
var     i,j,n,q:longint;
        f:text;
        res1,res2:longint;
        a:array[1..maxn] of longint;
        p:array[1..maxq] of arrp;
        mind,maxd:array[1..maxn*4] of longint;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n,q);
    for i:=1 to n do readln(f,a[i]);
    for i:=1 to q do readln(f,p[i].dau,p[i].cuoi);
    close(f);
end;
procedure update(k,l,r:longint);
var     mid:longint;
begin
    if l=r then
    begin
        maxd[k]:=a[l];
        mind[k]:=a[l];
    end
    else
    begin
        mid:=(l+r) div 2;
        update(k*2,l,mid);
        update(k*2+1,mid+1,r);
        mind[k]:=min(mind[k*2],mind[k*2+1]);
        maxd[k]:=max(maxd[k*2],maxd[k*2+1]);
    end;
end;
procedure find(k,l,r:longint);
var     mid:longint;
begin
    if (l>j) or (r<i) then exit;
    if (i<=l) and (j>=r) then
    begin
        res1:=min(res1,mind[k]);
        res2:=max(res2,maxd[k]);
        exit;
    end;
    mid:=(l+r) div 2;
    find(k*2,l,mid);
    find(k*2+1,mid+1,r);
end;
procedure xuat;
var     k:longint;
begin
    assign(f,fo);
    rewrite(f);
    update(1,1,n);
    for k:=1 to q do
    begin
        res1:=high(longint);
        res2:=0;
        i:=p[k].dau;
        j:=p[k].cuoi;
        find(1,1,n);
        writeln(f,res2-res1);
    end;
    close(f);
end;
begin
    nhap;
    xuat;
end.

VOSSEQ – spoj

Đề bài:

Thuật toán:

  • Đọc kỹ đề bài nhé.
  • Đề yêu cầu tìm dãy A có thứ tự từ điển bé nhất chứ không phải có độ dài bé nhất nhé.
  • Ta sẽ sử dụng Heap Min. Trong code bên dưới, mình chuyển các giá trị nguyên dương thành nguyên âm nên Heap Max chuyển thành Heap Min

Code:

#include <bits/stdc++.h>
#define taskname "VOSSEQ"
#define oo INT_MAX
#define maxn 1000001
using namespace std;
//const int maxn =1000001;
int m,k,maxa=-oo,u,a[maxn],d[maxn],res[maxn];
vector <int> v[maxn];
priority_queue <int> q;
void nhap()
{
    cin >> m;
    for(int i=1;i<=m;i++)
    {
        cin >> k;
        for(int i=1;i<=k;i++)
        {
            cin >> a[i];
            maxa=max(maxa,a[i]);
        }
        for(int i=1;i<k;i++)
        {
            v[a[i]].push_back(a[i+1]);
            d[a[i+1]]++;  
        }
    }
}
void xuli()
{
    int cnt=0;
    for(int i=1;i<=maxa;i++)
        if(!d[i]) q.push(-i);
    while(!q.empty())
    {
        u=-q.top();
        q.pop();
        res[++cnt]=u;
        for(int i=0;i<v[u].size();i++)
        {
            d[v[u][i]]--;
            if(!d[v[u][i]]) q.push(-v[u][i]);
        }
    }
    for(int i=1;i<=maxa;i++) cout << res[i] << " ";
}
int main()
{
    //freopen(taskname".INP","r",stdin);
    //freopen(taskname".OUT","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);cout.tie(NULL);
    nhap();
    xuli();
    return 0;
}

KPLANK – spoj

Đề bài:

Thuật toán:

  • Sừ dụng thuật toán tìm max/min trên một đoạn tịnh tiến.

Code:

uses math;
const
  fi='';
  fo='';
  maxn=trunc(1e6)+3;
var
  st : array[1..maxn] of longint;
  a,l,r : array[1..maxn] of longint;
  i,j,n : longint;
  res : int64;
  top : longint;
procedure enter;
  begin
    assign(input,fi);reset(input);
    readln(n);
    for i:=1 to n do read(a[i]);
  end;
procedure push(x : longint);
  begin
    inc(top);
    st[top] := x;
  end;
function get: longint;
  begin
    get := st[top];
  end;
procedure process;
  begin
    top :=0 ;
    for i:=1 to n do
      begin
        while (top<>0) and (a[get]>=a[i]) do dec(top);
        if top=0 then l[i] := 0 else l[i] := get;
        push(i);
      end;
    top := 0;
    for i:=n downto 1 do
      begin
        while (top<>0) and (a[get]>=a[i]) do dec(top);
        if top=0 then r[i]:=n+1 else r[i] := get;
        push(i);
      end;
    for i:=1 to n do
      if r[i]-l[i]-1>=a[i] then
        res := max(res, a[i]);
end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(res);
  end;
begin
  enter;
  process;
  print;
end.