第一章 线性表

1.基本操作

#include 

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
    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
    if(i<1||i>n)
        return -1;
    return data[i-1];
}
int Seqlist::locate(int k)
{
    for(int i=0;i

    int a[N],n;
    cin>>n;
    for(int i=0;i>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<<"该处下标值:"< 
2.两个有序顺序表元素的合并
 
void mg(Seqlist &s1,Seqlist &s2,Seqlist &s3)
{

    int i=0,j=0,k=0;
    while(i
        if(s1.data[i] 
3.删除线性表中所有值为x的元素
 
void del_x(Seqlist& s1,int k,Seqlist& s2)
{
    int g=0;
    for(int i=0;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
        int tmp=data[i];
        data[i]=data[n-i-1];
        data[n-i-1]=tmp;
    }
}
 
单链表的基本操作 
#include 

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
        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
        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
        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
        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<data<<" ";
        p=p->nxt;
    }
    cout<
    int a[105],n;
    cin>>n;
    for(int i=0;i>a[i];
    Linklist link=Linklist(a,n);
    link.print();

    cout< 
双链表 
插入、删除操作
 
#include 

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
        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<data<<" ";
        p=p->nxt;
    }
    cout<
    if(i<1||i>len+1)
        return 0;
    Dulnode *p=first;
    int j=0;
    while(jnxt,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(jnxt,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>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
        Dulnode* s=new Dulnode; //尾插法不断插入，尾指针不断后移
        s->data=a[i];
        rear->nxt=s;
        rear=s;
        //cout<data<nxt=p; //关键关键关键关键关键关键关键，指向头节点
    //cout<data< 
遍历：
 
void Linklist::print()
{
    Dulnode *p=rear->nxt->nxt;
    while(p!=rear->nxt)
    {
        cout<data<<" ";
        p=p->nxt;
    }
    cout< 
循环双链表的构造同理，插入和删除操作是注意指针的变化。
 
静态链表 
数组模拟的链表，受空间大小的影响
 
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;
}