单链表的实现

本文主要是介绍单链表的实现，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

包括：创建，遍历，查找，删除，插入，两个有序链表的合并

#include<bits/stdc++.h>
using namespace std;
#define OK 1
#define ERROR -1
#define OVERFLOW -1
typedef struct lnode
{
    int data;
    struct lnode *next;
}lnode,*linklist;
//后插法 
void Getlist(linklist &L)
{
    L=new lnode;
    L->next=NULL;
    linklist r=L;
    int n;
    cout<<"请输入数据（-1为结束标志）：";
    cin>>n;
    while(n!=-1)
    {
    linklist p=new lnode;
    p->data=n;
    p->next=NULL;
    r->next=p;
    r=p;
    cin>>n;
    }
}
//遍历
int travellist(linklist &L)
{
    linklist p=L->next;
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    cout<<endl;    
} 
//查找 
int Locatedlist(linklist &L,int e)
{
    linklist p;
    p=L->next;
    int count=0;
    while(p!=NULL)
    {
        count++;
        if(p->data==e)
        return count;
        p=p->next;
    }
    return ERROR;
}
//查找，返回地址
//加星号表示返回地址，返回的地址类型需要与子函数的类型相同 
//lnode *locatedlist(linklist &L,int e)
//{
//    linklist p;
//    p=L->next;
//    while(p&&p->data!=e)
//    {
//        p=p->next;
//    }
//    return p;
// } 
//插入 
int Insertlist(linklist &L,int i)
{
    int e;
    cout<<"请输入要插入的数据：";
    cin>>e; 
    linklist p=L;
    int j=0;
    //找到i-1的位置，即j=i-1
    while(p&&j<i-1) 
    {
        p=p->next;
        j++;
    }
    //如果j<1或j>i-1，ERROR 
    if(!p||j>i-1)
    return ERROR;
    linklist s=new lnode;
    s->data=e;
    s->next=p->next;
    p->next=s;
    return OK;
}
//删除 
int Datalist(linklist &L,int i)
{
    int e;
    linklist p=L;
    int j=0;
    while((p->next)&&(j<i-1))
    {
        p=p->next;j++;
    }
    //i>n或i<1，ERROR 
    //实际上是把指针放到了i-1的位置上，要删除i，所以p->next不为空 
    if(!(p->next)||j>i-1) return ERROR;
    linklist s;
    s=p->next;
    p->next=s->next;
    e=s->data;
    delete s;
    return OK;
}
//合并,L1,L2都为升序排序 
void Mergelist(linklist &L1,linklist &L2)
{
    int e;
    L1=new lnode;
    L1->next=NULL;
    linklist r1=L1;
    cout<<"请输入L1链表的数据（-1）结束：";
    cin>>e;
    while(e!=-1)
    {
        linklist p1=new lnode;
        p1->next=NULL;
        p1->data=e;
        r1->next=p1;
        r1=p1;
        cin>>e;
    }
    travellist(L1);
    L2=new lnode;
    L2->next=NULL;
    linklist r2=L2;
    cout<<"请输入L2链表的数据（-1）结束：";
    cin>>e;
    while(e!=-1)
    {
        linklist p2=new lnode;
        p2->next=NULL;
        p2->data=e;
        r2->next=p2;
        r2=p2;
        cin>>e;
    }
    travellist(L2);
    linklist pa=L1->next;
    linklist pb=L2->next;
    linklist pc=L1;
    while(pa&&pb)
    {
        if(pa->data<=pb->data)
        {
            pc->next=pa;
            pc=pa;
            pa=pa->next;
        }
        else
        {
            pc->next=pb;
            pc=pb;
            pb=pb->next;
        }
    }
    pc->next=pa?pa:pb;
    delete L2;
    cout<<"合并后的数据为：";
    travellist(L1);
 } 
//主函数 
int main()
{ 
    char n;    
    cout<<"1.创建链表"<<endl;
    cout<<"2.查找数据"<<endl; 
    cout<<"3.删除第i个数据"<<endl;
    cout<<"4.在第i个元素的位置插入数据"<<endl;
    cout<<"5.将L1和L2合并"<<endl;
    cout<<"按0结束操作"<<endl;
    cin>>n;
    while(n!='0')
    {
    int a,b,c;
    switch(n)
    {
        case '1':
            linklist l;
            Getlist(l);
            travellist(l);
            break;
        case '2':
            cout<<"请输入要查找的元素：";
            cin>>a;
            cout<<"数据的位置为：";
            cout<<Locatedlist(l,a)<<endl;
            break;
        case '3':
            cout<<"请输入要删除的数据位置：";
            cin>>a;
            Datalist(l,a);
            travellist(l);
            break;
        case '4':
            cout<<"请输入要插入数据的位置：";
            cin>>a;
            cout<<endl;
            Insertlist(l,a);
            travellist(l);
            break;
        case '5':
            linklist l1,l2;
            Mergelist(l1,l2);
            break;
        default: cout<<"无效输入"<<endl;break; 
    }
    cout<<"请选择下一个操作："<<endl;
    cout<<"1.创建链表"<<endl;
    cout<<"2.查找数据"<<endl; 
    cout<<"3.删除第i个数据"<<endl;
    cout<<"4.在第i个元素的位置插入数据"<<endl;
    cout<<"5.将L1和L2合并"<<endl;
    cout<<"按0结束操作"<<endl;
    cin>>n;
    }
}

1.创建：

 2.查找：

 3.删除

 4.插入：

 5.合并：

这篇关于单链表的实现的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！