Chapter I linear table

Implementation of sequence table

1. Basic operation

#include <bits/stdc++.h>

using namespace std;
const int N=1e5+5;
struct Seqlist
{
    
public:
    Seqlist(){
    };
    Seqlist(int a[],int len);
    ~Seqlist(){
    }
    bool ins(int i,int k);
    bool del(int i);
    int get_elem(int i);
    int locate(int k);
    void print();
private:
    int data[N];
    int n;
};
Seqlist::Seqlist(int a[],int len)
{
    
    for(int i=0;i<len;i++)
        data[i]=a[i];
    n=len;
}
bool Seqlist::ins(int i,int k)
{
    
    if(i<1||i>n+1)
        return 0;
    for(int j=n;j>=i;j--)
    {
    
        data[j]=data[j-1];
    }
    data[i-1]=k;
    n++;
    return 1;
}
bool Seqlist::del(int i)
{
    
    if(i<1||i>n)
        return 0;
    for(int j=i;j<=n;j++)
        data[j-1]=data[j];
    n--;
    return 1;
}
void Seqlist::print()
{
    
    for(int i=0;i<n;i++)
        cout<<data[i]<<" ";
    cout<<endl;
}
int Seqlist::get_elem(int i)
{
    
    if(i<1||i>n)
        return -1;
    return data[i-1];
}
int Seqlist::locate(int k)
{
    
    for(int i=0;i<n;i++)
        if(data[i]==k)
        return i;
    return -1;
}
int main()
{
    
/*  The test sample ： 5 5 4 3 2 1 */
    int a[N],n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    Seqlist sq=Seqlist(a,n);
    sq.ins(2,3);
    sq.print();
    sq.del(1);
    sq.print();
    int tmp=sq.get_elem(3);
    if(tmp!=-1)
        cout<<" The subscript value here :"<<tmp<<endl;
    else
        cout<<" Given subscript error "<<endl;
    sq.locate(4);
    tmp=sq.locate(3);
    if(tmp!=-1)
        cout<<" In the subscript :"<<tmp<<endl;
    else
        cout<<" There is no change value in the sequence table ."<<endl;
    return 0;
}

2. The combination of two ordered table elements

void mg(Seqlist &s1,Seqlist &s2,Seqlist &s3)
{
    

    int i=0,j=0,k=0;
    while(i<s1.n&&j<s2.n)
    {
    
        if(s1.data[i]<s2.data[j])
            s3.data[k++]=s1.data[i++];
        else
            s3.data[k++]=s2.data[j++];
    }
    while(i<s1.n)
        s3.data[k++]=s1.data[i++];
    while(j<s2.n)
        s3.data[k++]=s2.data[j++];
    s3.n=k;
}

3. Delete all values in the linear table as x The elements of

void del_x(Seqlist& s1,int k,Seqlist& s2)
{
    
    int g=0;
    for(int i=0;i<s1.n;i++)
    {
    
        if(s1.data[i]!=k)
        {
    
            s2.data[g++]=s1.data[i];
        }
    }
    s2.n=g;
}

4. Realize the inverse of linear table

void Seqlist::rev()
{
    
    int k=n/2;
    for(int i=0;i<k;i++)
    {
    
        int tmp=data[i];
        data[i]=data[n-i-1];
        data[n-i-1]=tmp;
    }
}

Basic operation of single chain table

#include <bits/stdc++.h>

using namespace std;
struct node
{
    
    int data;
    node* nxt;
};
struct Linklist
{
    
public:
    Linklist(){
    }
    Linklist(int a[],int len);
    ~Linklist();
    int link_get(int i);
    int locate(int k);
    bool ins(int i,int k);
    int del(int i);
    void print();
private:
    node* first;
};
Linklist::Linklist(int a[],int n)
{
    
    first=new node;
    first->nxt=NULL;
    node *p=first;
    /*  The first interpolation  for(int i=0;i<n;i++) { node *s=new node; s->data=a[i]; s->nxt=p->nxt; p->nxt=s; }*/
    /*  The tail interpolation */
    for(int i=0;i<n;i++)
    {
    
        node *s=new node;
        s->data=a[i];
        p->nxt=s;
        p=s;
    }
    p->nxt=NULL;
}
Linklist::~Linklist()
{
    
    node* p=first;
    while(first!=NULL) // The head node keeps moving back 
    {
    
        first=first->nxt;
        delete p;
        p=first;
    }
}
int Linklist::link_get(int i)
{
    
    if(i==0)
        return first->data;
    if(i<0)
        return -1;
    node* p=first->nxt;
    int j=1;
    while(p!=NULL&&j<i)
    {
    
        p=p->nxt;j++;
    }
    return p->data;
}
int Linklist::locate(int k)
{
    
    node *p=first->nxt;
    int j=1;
    while(p!=NULL)
    {
    
        if(p->data==k)
             return j;
        p=p->nxt;
        j++;
    }
    return -1;
}
bool Linklist::ins(int i,int k)
{
    
    node* p=first;
    int j=0;
    while(p!=NULL&&j<i-1)
    {
    
        p=p->nxt;j++;
    }
    if(p==NULL)
        return 0;
    node* s=new node;
    s->data=k;
    s->nxt=p->nxt;
    p->nxt=s;
    return 1;
}
int Linklist::del(int i)
{
    
    node *p=first;
    int j=0;
    while(p!=NULL&&j<i-1)
    {
    
        p=p->nxt;j++;
    }
    if(p==NULL)
        return -1;
    node *q=p->nxt;
    int x=q->data;
    p->nxt=q->nxt;
    delete q;
    return x;
}
void Linklist::print()
{
    
    node *p=first->nxt;
    while(p!=NULL){
    
        cout<<p->data<<" ";
        p=p->nxt;
    }
    cout<<endl;
}
int main()
{
    
    int a[105],n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    Linklist link=Linklist(a,n);
    link.print();

    cout<<link.link_get(3)<<endl;

    link.ins(2,7);
    link.print();

    link.del(1);
    link.print();

    cout<<" Element bits :"<<link.locate(4)<<endl;
    return 0;
}

Double linked list

Insert 、 Delete operation

#include <bits/stdc++.h>

using namespace std;
struct Dulnode
{
    
    int data;
    Dulnode* prior,*nxt;
};
class Linklist
{
    
public:
    Linklist(int a[],int n);
    ~Linklist();
    bool ins(int i,int k);
    bool del(int i);
    void print();
private:
    Dulnode *first;
    int len;
};
Linklist::Linklist(int a[],int n)
{
    
    first=new Dulnode;
    first->nxt=first->prior=NULL;
    Dulnode *p=first;
    for(int i=0;i<n;i++)
    {
    
        Dulnode* s=new Dulnode;
        s->data=a[i];
        p->nxt=s;
        s->prior=p;
        p=s;
    }
    p->nxt=NULL; // Key key key key key key 
}
Linklist::~Linklist()
{
    
    Dulnode *p=first;
    while(first!=NULL)
    {
    
        first=first->nxt;
        delete p;
        p=first;
    }
}
void Linklist::print()
{
    
    Dulnode *p=first->nxt;
    while(p)
    {
    
        cout<<p->data<<" ";
        p=p->nxt;
    }
    cout<<endl;
}
bool Linklist::ins(int i,int k)
{
    
    if(i<1||i>len+1)
        return 0;
    Dulnode *p=first;
    int j=0;
    while(j<i-1)
        p=p->nxt,j++;
    Dulnode *q=p->nxt;
    Dulnode *s=new Dulnode;
    s->data=k;
    s->nxt=q;
    s->prior=p;
    q->prior=s;
    p->nxt=s;
    len++;
    return 1;
}
bool Linklist::del(int i)
{
    
    if(i<0||i>len)
        return 0;
    Dulnode *p=first;
    int j=0;
    while(j<i-1)
        p=p->nxt,j++;
    Dulnode *q=p->nxt;
    p->nxt=q->nxt;
    q->nxt->prior=p;
    len--;
    return 1;
}
int main()
{
    
    int a[105],n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    Linklist ls=Linklist(a,n);
    ls.ins(3,100);
    ls.print();

    ls.del(2);
    ls.print();
    return 0;
}

Circular linked list

Single linked list construction with tail pointer ：

Linklist::Linklist(int a[],int n)
{
    
    rear=new Dulnode;
    rear->nxt=NULL;
    Dulnode *p=rear; // Record the position of the header node at the beginning 
    for(int i=0;i<n;i++)
    {
    
        Dulnode* s=new Dulnode; // The tail interpolation method keeps inserting , The tail pointer keeps moving back 
        s->data=a[i];
        rear->nxt=s;
        rear=s;
        //cout<<p->data<<endl;
    }
    rear->nxt=p; // Key key key key key key , Point to the head node 
    //cout<<p->data<<endl;
    len=n;
}

Traverse ：

void Linklist::print()
{
    
    Dulnode *p=rear->nxt->nxt;
    while(p!=rear->nxt)
    {
    
        cout<<p->data<<" ";
        p=p->nxt;
    }
    cout<<endl;
}

The construction of circular double linked list is the same , Insert and delete operations are concerned with pointer changes .

Static list

Array simulated linked list , Affected by the size of the space

void SList::ins(int i,int k)  // Insert the node in i Behind 
{
    
    int s=avail;
    avail=data[avail].nxt;
    data[s].x=k;
    data[s].nxt=data[i].nxt;
    data[i].nxt=s;
}
void SList::del(int p)  // Delete node p Successor node 
{
    
    q=data[p].nxt;
    data[p].nxt=data[q].nxt;
    data[q].nxt=avail;
    avail=q;
}