[大数据]c2.LinerList(DLinkList)

DLinkList

/*链式存储（双链表）*/
#include <cstdio>
#include <stdlib.h>
#include <iostream>
using namespace std;
typedef int Elemtype;

typedef struct DNode
{
    int ListLength;
    Elemtype data;
    DNode *prior;
    DNode *next;
}DNode,*DLinkList;

bool InitList(DLinkList &L)//初始化双链表
{
    L=new DNode;
    if(L==NULL){return false;}
    L->next=NULL;
    L->prior=NULL;
    return true;
}

bool GetElem(DLinkList L,int i,Elemtype &e)//双链表按节点取值
{
    DLinkList p=new DNode;
    p=L->next;
    int j=1;
    while(p&&j<i)//只到i-1位
    {
        p=p->next;
        ++j;
    }
    if(!p||j>i){return false;}
    e=p->data;
    return true;
}
DNode *LocateElem(DLinkList L,Elemtype e)//双链表按值查找,返回该节点
{
    DNode *p=new DNode;
    p=L->next;
    while(p && p->data!=e)
    {
        p=p->next;
    }
    return p;

}
bool ListInsert(DLinkList &L,int i,Elemtype e)
{
    Elemtype t;
    if(!GetElem(L,i,t)){return false;}//if合法判断
    DLinkList pl=new DNode;
    pl=L;int j=0;
    while(j<i-1)//到i-1
    {
        pl=pl->next;
        j++;
    }
    DLinkList temp=new DNode;
    temp->data=e;
    temp->next=pl->next;
    temp->prior=pl;
    pl->next=temp;
    temp->next->prior=temp;
    L->ListLength++;
    return true;
}
bool ListDelete(DLinkList &L,int i)
{
    Elemtype t;
    if(!GetElem(L,i,t)){return false;}//if合法判断
    DLinkList p=new DNode;int j=0;
    p=L;
    while(j<i-1)
    {
        p=p->next;
        j++;
    }
    DLinkList temp=new DNode;
    temp=p->next;
    p->next=temp->next;
    temp->next->prior=p;
    L->ListLength--;
    return true;
}

void CreateList(DLinkList &L,int i)//正序输入创建双链表
{
    DLinkList r=new DNode;
    r=L;
    for(int j=0;j<i;j++)
    {
        DLinkList p =new DNode;
        cin >> p->data;
        p->next=NULL;p->prior=r;r->next=p;
        r=p;
    }
    L->ListLength=i;
}
void UnionList(DLinkList &LA,DLinkList &LB,DLinkList &LC)//双链表的连接
{
    LC=LA;
    DLinkList p=new DNode;
    p=LA->next;
    while(p->next!=NULL)
    {
        p=p->next;
    }
    p->next=LB->next;
    LB->next->prior=p;
    LC->ListLength=LA->ListLength+LB->ListLength;
}
void PrintList(DLinkList L)
{
    DLinkList p=L;
    while(p->next!=NULL)
    {
        p=p->next;
        cout << p->data << " ";
    }
    cout << endl;
}


int main()
{
    DLinkList t,t1,t2;
    InitList(t);InitList(t1);InitList(t2);
    CreateList(t,5);CreateList(t1,5);
    PrintList(t);PrintList(t1);
    UnionList(t,t1,t2);
    PrintList(t2);
    //Elemtype TEMP;
    //GetElem(t,3,TEMP);
    //cout<<"third:" <<TEMP << endl;
    //DNode *pl=LocateElem(t,4);
    //if(pl){cout <<pl->data<<endl;}
    //Elemtype insert_var=8;
    //ListInsert(t,3,insert_var);
    //PrintList(t);
    //ListDelete(t,3);
    //PrintList(t);

    return 0;


}