双向链表的操作

2015 年 02 月 20 日

5335 次浏览

6041字数

#include <iostream>
using namespace std;

//打印选项
void printTheSelect()
{
    cout<<"\n1.初始化双向链表
2.打印双向链表\n3.逆序打印双向链表\n";
    cout<<"4.求链表长度
5.判断链表是否为空\n6.清空链表\n";
    cout<<"7.插入元素\n8.删除元素\n9.删除链表\n0.退出
";
}

typedef struct DuLnode
{
    int data;              //数据
    struct DuLnode *prior; //前驱
    struct DuLnode *next;  //后继
}DuLnode,*DuLinkList;

//初始化双向链表
void initDlist(DuLinkList &L)
{
    int x;
    DuLinkList p,q;//p,q就是struct DuLnode *
    //L = new DuLnode;
    L = (DuLinkList)malloc(sizeof(DuLnode));
    L->next = NULL;
    L->prior = NULL;
   
   
    p = L;
    cout<<"输入双向链表的元素，每输入一个元素后按回车，输入0表示结束.\n";
    cin>>x;
    while(x != 0)//尾插法
    {
        q = (DuLinkList)malloc(sizeof(DuLnode));
        q->data = x;
        q->next = NULL;
        q->prior = p;
        p->next = q;
        p = q;
        cin>>x;
    }
    cout<<"双向链表构造完毕!\n";
}

//打印双向链表
void printDlist(DuLinkList &L)
{
    DuLinkList p;
    if(L == NULL)
    {
        cout<<"链表不存在，请先初始化!\n";
    }
    else if(L->next == NULL)
    {
        cout<<"链表为空!\n";
    }
    else
    {
        cout<<"链表的元素为：
";
        p = L->next;//p指向第一个元素
        while(p)
        {
            cout<<p->data<<" ";
            p = p->next;
        }
        cout<<endl;
    }
}

//逆序打印双向链表
void printDlistFromLast(DuLinkList &L)
{
    DuLinkList p;
   
    if(L == NULL)
    {
        cout<<"链表不存在，请先初始化!\n";
    }
    else if( L->next == NULL )
    {
        cout<<"链表为空!\n";
    }
    else
    {
        p = L->next;//
        while(p->next)
        {
            p = p->next;
        }
        //p指向了最后一个
        
        while(p->prior)
        {
            cout<<p->data<<" ";
            p = p->prior;
        }
    }
}

//求链表长度
int lengthDlist(DuLinkList &L)
{
    int i = 0;
   
    if(L == NULL)
    {
        cout<<"链表不存在，请先初始化!\n";
    }
    else
    {
        DuLinkList p = L->next;
        while(p)
        {
            i++;
            p = p->next;
        }
    }
   
    return i;
}

//判断链表是否为空
void isEmptyOrNotDlist(DuLinkList &L)
{
    if(L == NULL)
    {
        cout<<"链表不存在，请先初始化!\n";
    }
    else if( L->next == NULL )
    {
        cout<<"链表为空!\n";
    }
    else
    {
        cout<<"链表非空!\n";
    }
}

//把双向链表置空(头结点保留)
void clearTheDlist(DuLinkList &L)
{
    if(L==NULL)
    {
        cout<<"链表不存在，请先初始化!\n";
    }
    else
    {
        DuLinkList p,q;
        p = q = L->next;   //是p、q指向第一个元素
        L->next = NULL;
        
        while(p)          //逐个释放元素所占内存
        {
            p = p->next;
            free(q);
            q = p;
        }
    }
}

//删除双向链表
void delTheDlist(DuLinkList &L)
{
    clearTheDlist(L);
    free(L);
    L = NULL;
}

//在双向链表中第i个位置后面插入元素m
void insertElmToDlist(DuLinkList &L)
{
    int i,m;
    cout<<"输入插入的元素:\n";
    cin>>m;
    cout<<"输入插入的位置:\n";
    cin>>i;
    DuLinkList p,q;
    p = L;
    int j = 0;
   
    if(L == NULL)
    {
        cout<<"链表不存在，请先初始化!\n";
    }
    else if(L->next == NULL)
    {
        cout<<"链表为空，请初始化后再进行插入数据操作!\n";
    }
    else if( i<1 || i>lengthDlist(L)+1 )
    {
        cout<<"插入位置错误!\n";
    }
    else
    {
        while( j<i-1 )//找到前一个元素
        {
            p = p->next;
            j++;
        }
        
        if( j == lengthDlist(L) )
        //如果在最后一个元素后面插入m
        {
            q = (DuLinkList)malloc(sizeof(DuLnode));
            q->data = m;
            q->next = NULL;
            q->prior = p;
            p->next = q;
        }
        else
        {
            q = (DuLinkList)malloc(sizeof(DuLnode));
            q->data = m;
            
            q->next = p->next;
            p->next->prior = q;
            q->prior = p;
            p->next = q;
            
        }
    }
}

//删除双向链表中的第i个元素
void delElmFromDlist(DuLinkList &L)
{
    int i;
    cout<<"输入要删除的位置:";
    cin>>i;
    int j = 0;
    DuLinkList p = L;
   
    if(L == NULL)
    {
        cout<<"链表不存在，请先初始化!\n";
    }
    else if( i<1 || i>lengthDlist(L) )
    {
        cout<<"删除的位置不存在!\n";
    }
    else
    {
        while( j<i )//找到第i个元素
        {
            p = p->next;
            j++;
        }
        
        if( j == lengthDlist(L) )//如果是最后一个元素
        {
            p->prior->next = NULL;
            free(p);
        }
        else
        {
            p->prior->next = p->next;
            p->next->prior = p->prior;
            free(p);
        }
    }
}


int main()
{
    int i;
    DuLinkList L = NULL;
    printTheSelect();
    cout<<"请输入操作:";
    cin>>i;
    while( 0 != i)
    {
        switch(i)
        {
            case 1:initDlist(L);
                break;
            case 2:printDlist(L);
                break;
            case 3:printDlistFromLast(L);
                break;
            case 4:cout<<"链表长度为:"<<lengthDlist(L)<<endl;
                break;
            case 5:isEmptyOrNotDlist(L);
                break;
            case 6:clearTheDlist(L);
                break;
            case 7:insertElmToDlist(L);
                break;
            case 8:delElmFromDlist(L);
                break;
            case 9:delTheDlist(L);
                break;
            default:cout<<"输入错误，请重新输入!\n";
                break;
        }
        printTheSelect();
        cout<<"请输入操作:";
        cin>>i;
    }
    if(0 == i)
    {
        cout<<"程序退出....\n";
    }
    return 0;
}