博客

内容：

1）实现单链表的以下基本操作：建立单链表，查找单链表，插入单链表，删除单链表。

2）采用单链表结构编程实现：两个有序单链表的归并运算。

实现思路：

① 定义数据域类型；

② 定义单链表，分为数据域和指针域；

③ 分别编写实现前插法创建单链表、后插法创建单链表、初始化单链表、单链表的查找、向单链表插入元素、删除单链表中某元素、遍历单链表并显示、求单链表最大节点、判断单链表是否为空、求单链表长度、逆转单链表、两个有序单链表的归并等函数功能；

④ 在主函数中定义单链表；

⑤ 使用while实现循环操作，当输入指令小于等于0 退出；

⑥ 使用switch根据指令选项判断需要执行的指令（先创建单链表才可以进行后续操作）；

⑦ 执行某些指令之前要先判空；

⑧ 接受退出指令退出；

⑨ 程序退出

程序实现：

#include <iostream>

using namespace std;

typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;

void InitList(LinkList &L) //初始化单链表
{
    L=new LNode;
    L->next=NULL;
}

LNode *LocateElem(LinkList L,int e)  //单链表的查找
{
    LNode *p=L->next;
    while(p && p->data!=e)
        p=p->next;
    return p;
}

int ListInsert(LinkList &L,int i,int e) //单链表插入元素
{
    LNode *p=L;
    int j=0;
    while(p && j<i-1)
    {
        p=p->next;
        j++;
    }

    if(!p || j>i-1)
        return 0;

    LNode *s=new LNode;
    s->data=e;
    s->next=p->next;
    p->next=s;
    return 1;
}

int ListDelete(LinkList &L,int i) //单链表删除元素
{
    LNode *p=L;
    int j=0;
    while((p->next) && (j<i-1))
    {
        p=p->next;
        j++;
    }
    if(!(p->next) || j>i-1)
        return 0;
    LNode *s=new LNode;
    s=p->next;
    p->next=s->next;
    delete s;
    return 1;
}

void CreateList_H(LinkList &L,int n) //前插法创建单链表
{
    InitList(L);
    for(int i=0;i<n;i++)
    {
        LNode *p=new LNode;
        cout<<"请输入第"<<i+1<<"个元素：";
        cin>>p->data;
        p->next=L->next;
        L->next=p;
    }
}

void CreateList_R(LinkList &L,int n) //后插法创建单链表
{
    InitList(L);
    LNode *r=L;
    for(int i=0;i<n;i++)
    {
        LNode *p=new LNode;
        cout<<"请输入第"<<i+1<<"个元素：";
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}

void PrintList(LinkList &L)  //遍历单链表并显示
{
    LNode *p=L->next;
    while(p)
    {
        cout<<p<<"<=>"<<p->data<<endl;
        p=p->next;
    }

}

void ListMax(LinkList &L) //求单链表最大结点
{
    LNode *p=L->next;
    LNode *q=L->next;
    while(p)
    {
        if(q->data<p->data)
        {
            q=p;

        }
        p=p->next;
    }
    cout<<q<<"<=>"<<q->data<<endl;
}

bool ListEmpty(LinkList &L) //判空
{
    if(L==NULL)
        return false;
    return true;
}

int ListLength(LinkList &L) //单链表长度
{
    int l=0;
    LNode *p=L->next;
    while(p)
    {
        l++;
        p=p->next;
    }
    return l;
}

void MergeList_L(LinkList &LA,LinkList &LB,LinkList &LC) //有序链表归并
{
    LNode *pa=LA->next;
    LNode *pb=LB->next;
    LC=LA;
    LNode *pc=LC;
    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 LB;
}

void nizhuan(LinkList &L)  //单链表逆转
{
    LNode *p=L->next;
    LNode *q=p->next;
    while(q)
    {
            LNode *s=q->next;
            q->next=p;
            p=q;
            q=s;
    }
    L->next->next=NULL;
    L->next=p;
    cout<<"逆转之后的顺序为："<<endl;
    PrintList(L);
}

int main()
{
    LinkList L=NULL;

    cout<<"1 前插创建单链表"<<endl;
    cout<<"2 后插创建单链表"<<endl;
    cout<<"3 查找单链表"<<endl;
    cout<<"4 插入单链表"<<endl;
    cout<<"5 删除单链表"<<endl;
    cout<<"6 遍历单链表"<<endl;
    cout<<"7 查找单链表最大节点"<<endl;
    cout<<"8 单链表的长度"<<endl;
    cout<<"9 逆转单链表"<<endl;
    cout<<"10 两个有序单链表的归并"<<endl;
    cout<<"    输入小于等于0的指令退出程序！"<<endl;
    int ip;
    while(1)
    {
        cout<<endl;
        cout<<"**********************************************************"<<endl;
        cout<<"请输入操作指令："<<endl;
        cin>>ip;
        if(ip<=0)
            break;
        else
        {
            switch(ip)
            {
            case 1:
                {
                    cout<<"请输入单链表的长度：";
                    int n;
                    cin>>n;
                    CreateList_H(L,n);
                    break;
                }
            case 2:
                {
                    cout<<"请输入单链表的长度：";
                    int n;
                    cin>>n;
                    CreateList_R(L,n);
                    break;
                }
            case 3:
                {
                    if(ListEmpty(L))
                    {
                        cout<<"请输入要查找的数据：";
                        int e;
                        cin>>e;
                        LNode *p=LocateElem(L,e);
                        cout<<"查找的数据的地址为："<<p<<endl;

                    }
                    else
                    {
                        cout<<"线性表为空！"<<endl;
                    }
                    break;

                }
            case 4:
                {
                    if(ListEmpty(L))
                    {
                        cout<<"请依次输入插入数据的位置、插入的数据元素";
                        int i,e;
                        cin>>i>>e;
                        int flag=ListInsert(L,i,e);
                        if(flag==1)
                            cout<<"插入成功！"<<endl;
                        else
                            cout<<"插入失败！"<<endl;
                    }
                    else
                    {
                        cout<<"线性表为空！"<<endl;
                    }
                    break;
                }
            case 5:
                {
                    if(ListEmpty(L))
                    {
                        cout<<"请输入要删除元素的位置：";
                        int i;
                        cin>>i;
                        int flag=ListDelete(L,i);
                        if(flag==1)
                            cout<<"删除成功！"<<endl;
                        else
                            cout<<"删除失败！"<<endl;
                    }
                    else
                    {
                        cout<<"线性表为空！"<<endl;
                    }
                    break;
                }

            case 6:
                {
                    if(ListEmpty(L))
                    {
                        PrintList(L);
                    }
                    else
                    {
                        cout<<"线性表为空！"<<endl;
                    }
                    break;
                }
            case 7:
                {
                    if(ListEmpty(L))
                    {
                        ListMax(L);
                    }
                    else
                    {
                        cout<<"线性表为空！"<<endl;
                    }
                    break;
                }
            case 8:
                {
                    if(ListEmpty(L))
                    {
                        cout<<"单链表的长度为："<<ListLength(L)<<endl;
                    }
                    else
                    {
                        cout<<"线性表为空！"<<endl;
                    }
                    break;
                }
            case 9:
                {
                    if(ListEmpty(L))
                    {
                        nizhuan(L);
                        cout<<"单链表逆转成功！"<<endl;
                    }
                    else
                    {
                        cout<<"线性表为空！"<<endl;
                    }
                    break;
                }
            case 10:
                {
                    LinkList LA;
                    LinkList LB;
                    LinkList LC;
                    InitList(LC);
                    cout<<"请输入单链表LA的长度：";
                    int n;
                    cin>>n;
                    CreateList_R(LA,n);

                    cout<<"请输入单链表LB的长度：";
                    cin>>n;
                    CreateList_R(LB,n);

                    cout<<"单链表LA的元素为："<<endl;
                    PrintList(LA);
                    cout<<"单链表LB的元素为："<<endl;
                    PrintList(LB);
                    cout<<endl;

                    MergeList_L(LA,LB,LC);
                    cout<<"单链表LC的元素为："<<endl;
                    PrintList(LC);
                    break;
                }
            default:
                {
                    cout<<"请输入正确的指令！"<<endl;
                    break;
                }
            }
        }
    }
    return 0;
}