第一章 线性表

顺序表的实现

1.基本操作

#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()
{
    
/* 测试样例： 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<<"该处下标值:"<<tmp<<endl;
    else
        cout<<"给出下标错误"<<endl;
    sq.locate(4);
    tmp=sq.locate(3);
    if(tmp!=-1)
        cout<<"位于下标:"<<tmp<<endl;
    else
        cout<<"顺序表中不存在改值。"<<endl;
    return 0;
}

2.两个有序顺序表元素的合并

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.删除线性表中所有值为x的元素

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.实现对线性表的逆置

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;
    }
}

单链表的基本操作

#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;
    /* 头插法 for(int i=0;i<n;i++) { node *s=new node; s->data=a[i]; s->nxt=p->nxt; p->nxt=s; }*/
    /* 尾插法*/
    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) //头结点不断后移
    {
    
        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<<"元素位数:"<<link.locate(4)<<endl;
    return 0;
}

双链表

插入、删除操作

#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; //关键关键关键关键关键关键关键
}
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;
}

循环链表

带尾指针的单链表构造：

Linklist::Linklist(int a[],int n)
{
    
    rear=new Dulnode;
    rear->nxt=NULL;
    Dulnode *p=rear; //记录开始时头节点位置
    for(int i=0;i<n;i++)
    {
    
        Dulnode* s=new Dulnode; //尾插法不断插入，尾指针不断后移
        s->data=a[i];
        rear->nxt=s;
        rear=s;
        //cout<<p->data<<endl;
    }
    rear->nxt=p; //关键关键关键关键关键关键关键，指向头节点
    //cout<<p->data<<endl;
    len=n;
}

遍历：

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

循环双链表的构造同理，插入和删除操作是注意指针的变化。

静态链表

数组模拟的链表，受空间大小的影响

void SList::ins(int i,int k)  //将节点插在i的后面
{
    
    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)  //删除结点p的后继节点
{
    
    q=data[p].nxt;
    data[p].nxt=data[q].nxt;
    data[q].nxt=avail;
    avail=q;
}