单链表的基本运算

#include<iostream>
using namespace std;
#include<stdio.h>
#include<malloc.h>
#define ElemType int

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LinkNode;

void CreateListF(LinkNode *&L,ElemType a[],int n)// 头插法
{
    LinkNode *p;
    L =(LinkNode *)malloc(sizeof(LinkNode));
    L->next=NULL;
    for(int i = 0;i<n;i++)
    {
        p = (LinkNode *)malloc(sizeof(LinkNode));
        p->data = a[i];
        p->next = L->next;
        L->next = p;
    }
}

void CreateListR(LinkNode *&L,ElemType a[],int n)//尾插法
{
    LinkNode *p ,*r;
    L = (LinkNode *)malloc(sizeof(LinkNode));
    L->next =NULL;
    r = L;
    for(int i =0 ;i<n;i++)
    {
        p = (LinkNode *) malloc(sizeof(LinkNode));
        p->data = a[i];
        r->next = p;//p插入r结点后
        r = p;
    }
    r->next = NULL;//尾结点置空
}

void InitList(LinkNode *&L)
{
    L= (LinkNode *)malloc(sizeof(LinkNode));
    L->next = NULL;
}

void DestortyList(LinkNode *&L)
{
    LinkNode *pre =L, *p = pre->next;
    while(p!= NULL)
    {
        free(pre);
        pre = p;
        p= p->next;//p，pre同步后移
    }
    free(pre);
}

bool ListEmpty(LinkNode *L)
{
    return (L->next ==NULL);
}

int ListLength(LinkNode *L)
{
    int j = 0;
    LinkNode *p = L;
    while(p->next != NULL)
    {
        j++;
        p = p->next;
    }
    return j;
}

void DispList(LinkNode *L)
{
    LinkNode *p= L->next;
    while(p!=NULL)
    {
        cout<<" "<<p->data;
        p = p->next;
    }
    cout<<endl;
}

int GetElem(LinkNode *L,int i,ElemType &e)
{
    int j=0;
    LinkNode *p = L;
    if(i<0 ) 
        return false;
    while(j <i && p!=NULL)
    {
        j++;
        p=p->next;
    }
    if(p==NULL)
    {
        return false;
    }
    else
    {
        e = p->data;
        return true;
    }
}

int LocateElem(LinkNode *L,ElemType e)
{
    int i =1;
    LinkNode *p = L->next;
    while(p!= NULL && p->data != e)
    {
        i++;
        p=p->next;
    }
    if( p==NULL)
    {
        return false;
    }
    else
    {
        return (i);
    }
}

bool LinktInsert(LinkNode *&L,int i ,ElemType e)
{
    int j = 0;
    LinkNode *p = L,*r;
    if(i< 0) return false;
    while( j<i-1 && p!=NULL)
    {
        j++;
        p=p->next;
    }
    if(p == NULL) return false;
    else
    {
        r = (LinkNode *)malloc(sizeof(LinkNode));
        r->data = e;
        r->next = p->next;
        p->next =r;
        return true;   
    }
}

bool ListDelete(LinkNode *&L,int i,ElemType &e)
{
    int j = 0;
    LinkNode *p = L,*q;
    if(i<0) return false;
    while( j<i-1 && p!=NULL)
    {
        j++;
        p = p->next;
    }
    if(p==NULL)
    {
        return false;
    }
    else//找到i-1个结点
    {
        q = p->next;//q指向第i个结点
        if(q==NULL)
            return false;
        else
        {
            e = q->data;
            p->next = q->next;//删除q结点
            free(q);//释放q结点
            return true;
        }
    }
}

void Split(LinkNode *&L,ElemType x)//将列表按按x拆分
{
    LinkNode *p =L->next ,*q,*r;
    L->next = NULL;
    r = L;
    while(p!=NULL)
    {
        if(p->data < x)//p结点小于x，插入到开头
        {
            q = p->next;
            p->next = L->next;
            L->next = p;
            if(p->next ==NULL)//若p结点是第一个在开头的结点
            {
                r = p;//则是尾结点
            }
            p = q;
        }
        else//若p结点大于等于x，则将其插入表尾
        {
            r->next = p;
            r = p;
            p = p->next;
        }
    }
    r->next =NULL;
}

void Merge(LinkNode *L1,LinkNode *L2,LinkNode *&L3)//将L1，L2个并产生L3
{
    LinkNode *p =L1->next;
    LinkNode *q =L2->next;
    LinkNode *r;
    L3 = L1;
    r = L3;//r指向新建链表的头结点 
    free(L2);//释放L2的头结点
    while(p!=NULL && q !=NULL)
    {
        r->next = p;
        r =p;
        p = p->next;
        r->next =q;
        r =q;
        q = q->next;
    }
    r->next = NULL;
    if(q!=NULL)
    {
        p =q;
    }
    r->next = p;
}

void Sort(LinkNode *&L)//单链表递增排序
{
    LinkNode *p;
    LinkNode *q;
    LinkNode *pre;
    p = L->next->next;//p 指向L的第二个结点
    L->next->next = NULL;//L中保留一个数据结点
    while(p != NULL)
    {
        q = p->next;//q 指向p下一个结点
        pre = L;//pre指向头结点
        while(pre->next != NULL && pre->next->data < p->data)//如果L中pre—>next值小于p的data
        {
            pre = pre->next;//找到pre的位置
        }
        p->next = pre->next;
        pre->next = p;
        p = q;
    }
}

void Union(LinkNode *ha,LinkNode *hb,LinkNode *&hc)
{
    LinkNode *pa = ha->next;
    LinkNode *pb = hb->next;
    LinkNode *s;
    LinkNode *tc;
    hc = (LinkNode*)malloc(sizeof(LinkNode));//hc头结点
    tc = hc;
    while(pa != NULL && pb != NULL)
    {
        if(pa->data < pb->data)
        {
            s = (LinkNode *)malloc(sizeof(LinkNode));
            s->data = pa->data;//新结点赋值
            tc->next = s;
            tc = s;
            pa = pa->next;
        }
        else if(pa->data > pb->data)
        {
            s = (LinkNode*)malloc(sizeof(LinkNode));
            s->data = pb->data;
            tc->next = s;
            tc = s;
            pb = pb->next;
        }
        else// data == 
        {
            s = (LinkNode*)malloc(sizeof(LinkNode));
            s->data = pa->data;
            tc->next = s;
            tc = s;
            pa = pa->next;
            pb = pb->next;
        }
    }
    if(pb != NULL)//余下的结点
        pa = pb;//copy
    while(pa != NULL)
    {
        s = (LinkNode*)malloc(sizeof(LinkNode));
        s->data = pa->data;
        tc->next = s;
        tc = s;
        pa = pa->next;
    }
    tc->next = NULL;
}

void InsertSect(LinkNode * ha,LinkNode * hb,LinkNode *&hc)//两个有序表的交集
{
    LinkNode *pa = ha->next;
    LinkNode *pb;
    LinkNode *s;
    LinkNode *tc;
    hc = (LinkNode *)malloc(sizeof(LinkNode));
    tc = hc;
    while(pa != NULL)
    {
        pb = hb ->next;
        while(pb != NULL && pb->data < pa->data)
        {
            pb = pb->next;
        }
        if(pb != NULL && pb->data == pa->data)
        {
            s = (LinkNode*)malloc(sizeof(LinkNode));
            s->data = pa->data;//copy
            tc->next = s;
            tc = s;
        }
        pa = pa->next;
    }
    tc->next = NULL;
}

void Subs(LinkNode *ha,LinkNode *hb,LinkNode *&hc)
{
    LinkNode *pa = ha->next;
    LinkNode *pb;
    LinkNode *tc;
    LinkNode *s;
    hc = (LinkNode*)malloc(sizeof(LinkNode));
    tc = hc;
    while(pa != NULL)
    {
        pb = hb->next;
        while( pb != NULL && pb->data < pa->data)
        {
            pb = pb->next;
        }
        if(!(pb != NULL && pb->data == pa->data))//pa结点不在pb中
        {
            s = (LinkNode*)malloc(sizeof(LinkNode));
            s ->data = pa->data;
            tc ->next = s;
            tc = s;
        }
        pa = pa->next;
    }
    tc->next = NULL;
}

int main()
{
    LinkNode *h;
    ElemType e;
    cout<<"初始化链表"<<endl;
    InitList(h);
    cout<<"依次插入97，98，99，100，101"<<endl;
    LinktInsert(h,1,97);
    LinktInsert(h,2,98); LinktInsert(h,3,99); LinktInsert(h,4,100); LinktInsert(h,5,101);
    cout<<"Print"<<endl;
    DispList(h);
    cout<<"Length is "<<ListLength(h)<<endl;
    GetElem(h,3,e);
    cout<<"第3个元素为"<<e<<endl;
    cout<<"在第4个位置上插入 60"<<endl;
    LinktInsert(h,4,60);
    cout<<"Print "<<endl;
    DispList(h);
    cout<<"删除第3 个元素"<<endl;
    ListDelete(h,3,e);
    cout<<"Print"<<endl;
    DispList(h);
    cout<<"释放单链表"<<endl;
    DestortyList(h);
    LinkNode *L;
    ElemType a[] ={105,106,101,100,103,104,105,106,101,102,107,108};
    int n = 8;
    CreateListR(L,a,n);
    cout<<"L :"<<endl;
    DispList(L);
    ElemType x =104;
    cout<<"以104划分"<<endl;
    Split(L,x);
    cout<<"L: "<<endl;
    DispList(L);
    cout<<"释放L"<<endl;
    DestortyList(L);
//~~~~~~~~~~~~~~~~~~~~~
    LinkNode *L1;
    LinkNode *L2;
    LinkNode *L3;
    LinkNode *L4;
    LinkNode *L5;
    LinkNode *L6;
    ElemType b[] ={100,101,102,103,104,105,106,107,108};
    int m = 8;
    CreateListR(L1,b,n);
    cout<<"L1"<<endl;
    DispList(L1);

    ElemType c[]={1,3,4,5,6};
    ElemType d[]={2,4,5,6,7};
    int nn = 5;
    CreateListR(L2,c,nn);
    CreateListR(L4,d,nn);
    
    cout<<"L2"<<endl;
    DispList(L2);
    cout<<"L4"<<endl;
    DispList(L4);

    cout<<"L2 L4 Union"<<endl;
    Union(L2,L4,L5);
    DispList(L5);

    cout<<"L1 L2 Merage"<<endl;
    Merge(L1,L2,L3);

    cout<<"L3"<<endl;
    DispList(L3);

    cout<<"L3 Sort"<<endl;
    Sort(L3);
    DispList(L3);
    cout<<" L2 L4 Sect"<<endl;
    InsertSect(L2,L4,L6);
    DispList(L6);
    cout<<"Free";
    DestortyList(L1);
    DestortyList(L2);
    DestortyList(L3);
    DestortyList(L4);
    DestortyList(L5);
    DestortyList(L6);
    return 1;
}