双链表的基本运算

佚名 6年前 (2018-11-26) 算法 1027人围观抢沙发百度已收录

#include<iostream>
using namespace std;
#include<malloc.h>
typedef char ElemType;
typedef struct DNode
{
    ElemType data;
    struct DNode *prior;
    struct DNode *next;
}DLinkNode;

void CreateListF(DLinkNode *&L,ElemType a[],int n)//头插法
{
    DLinkNode *s;
    L  = (DLinkNode*)malloc(sizeof(DLinkNode));
    L->prior = L->next = NULL;
    for(int i =0;i<n;i++)
    {
        s = (DLinkNode *)malloc(sizeof(DLinkNode));
        s->data = a[i];
        s->next = L->next;
        if(L->next != NULL)//结点s插在原开始结点之前，头结点之后
            L->next->prior = s;
        L->next = s;
        s->prior = L;
    }
}

void CreateListR(DLinkNode *&L,ElemType a[],int n)//尾插法
{
    DLinkNode *s,*r;
    L  = (DLinkNode*)malloc(sizeof(DLinkNode));//头结点
    L ->prior = L->next = NULL;
    r = L;//r始终指向终端结点。开始为头结点
    for(int i = 0;i<n;i++)
    {
        s =(DLinkNode*)malloc(sizeof(DLinkNode));//创建新结点
        s->data  = a[i];
        r->next = s;//s插入r之后
        s->prior = r;
        r = s;
    }
    r->next = NULL;
}

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

void DestoryList(DLinkNode *&L)
{
    DLinkNode *pre = L;
    DLinkNode *p = L->next;
    while(p != NULL)
    {
        free(pre);
        pre = p;
        p = p->next;//pre p 同时后移
    }
    free(p);
}

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

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


void DispList(DLinkNode *L)
{
    DLinkNode *p= L->next;
    while(p != NULL)
    {
        cout<<p->data;
        p = p->next;
    }
    cout<<endl;
}
bool GetElem(DLinkNode *L,int i,ElemType &e)
{
    int j = 0;
    DLinkNode *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(DLinkNode *L,ElemType e)
{
    int  i = 1;
    DLinkNode *p = L->next;
    while(p!= NULL && p->data != e)//查找第一个值为e的
    {
        i++;
        p = p->next;
    }
    if(p == NULL)
    {
        return false;
    }
    else
    {
        return (i);
    }
}

bool ListInsert(DLinkNode *&L,int i,ElemType e)
{
    int j = 0;
    DLinkNode *p = L;
    DLinkNode *s;
    if(i < 0)
        return false;
    while(p!=NULL && j < i -1)//查找待插入的前一个 
    {
        j++;
        p = p->next;
    }
    if(p == NULL)
        return  false;
    else
    {
        s = (DLinkNode*)malloc(sizeof(DLinkNode));//找到前一个
        s->data = e;
        s->next = p->next;
        if(p->next != NULL)
        {
            p->next->prior = s;//s插入p之后
        }
        s->prior = p;
        p->next = s; 
    }
}

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

int main()
{
    DLinkNode *d;
    ElemType e;
    cout<<"双链表操作"<<endl;
    InitList(d);
    ListInsert(d,1,'a');
    ListInsert(d,2,'b');
    ListInsert(d,3,'c');
    ListInsert(d,4,'d');
    ListInsert(d,5,'e');
    cout<<"D-> ";
    DispList(d);
    cout<<"The Length is "<<ListLength(d)<<endl;
    cout<<"The third Elem is:";
    GetElem(d,3,e);
    cout<<e<<endl;
    cout<<"Delete fourth Elem->";
    ListDelete(d,4,e);
    DispList(d);
    return 1;
}

　运算结果