数据结构与算法之双向链表

//双向链表
#include<stdio.h>
#include<malloc.h>
typedef struct Node{

    int data;

    struct Node *prior;

    struct Node *next;

}* Linklist,DuLNode;

bool InitList(Linklist *L)//构造一个空的双向链表
{

    (*L) = (Linklist)malloc(sizeof(DuLNode));//创建头结点，并使头指针指向头结点。

    if((*L)==NULL)
        return false;

    (*L)->next = (*L);
    (*L)->prior = (*L);

    return true;

}

void DestoryList(Linklist *L)//销毁线性表(包括头结点)。
{
    Linklist p,q;

    p = (*L)->next;//指向第一个结点
    while((*L)!=p)
    {
        q = p->next;
        free(p);
        p = q;
    }
    
    free(*L);
    (*L) = NULL;
}

void ClearList(Linklist L)//将线性表清空（不包括头结点）
{
    Linklist p,q;

    p = L->next;//让p指向第一个结点

    while(p!=L)
    {
        q = p->next;
        free(p);
        p = q;
    }
    
    L->next = L;
    L->prior = L;
}

bool ListEmpty(Linklist L)//判断线性表是否为空
{
    if(L->next==L->prior)
    {
        return true;
    }
    else
    {
        return false;
    }
}

int ListLength(Linklist L)//返回线性表中数据元素个数
{
    int i = 0;
    Linklist p;

    p = L->next;//头结点不作为链表的有效元素,p此时指向第一个结点。

    while(p!=L)
    {
        i++;
        p = p->next;
    }

    return i;
}

int GetElem(Linklist L,int item)//返回线性表第item个元素的值
{
    Linklist p;
    int i;

    p = L->next;//让p指向第一个有效结点

    for(i=1;i<item;i++)
    {
        if(p!=L)
            p = p->next;
        else{
            printf("指定查询的位置不存在!\n");
            return -1;
        }
    }
    
    return p->data;
}

int LocateElem(Linklist L,int item)//返回线性表第一个与给定参数匹配的元素的位序，不存在则返回-1
{
    Linklist p;
    int i = 0;
    
    p = L->next;

    while(p!=L)
    {
        i++;

        if(p->data==item)
            return i;

        p = p->next;
    }
    
    return -1;//表示返回指定位置元素失败
}

int PriorElem(Linklist L,int item)//返回线性表中，指定参数的前驱
{
    Linklist p,before;
    
    p = L->next;//p此时指向第一个有效结点

    while(p->next!=L)//从第二有效结点开始遍历（第一有效结点的数据域即使和item相等，也不存在前驱。）
    {
        before = p;
        p = p->next;//p此时指向第二个有效元素

        if(p->data==item)
            return before->data;

        //p = p->next;
    }
    
    return -1;//表示返回指定位置元素失败
}

int NextElem(Linklist L,int item)//返回线性表中，指定参数的后继
{
    Linklist p,tail;
    
    p = L->next;//p此时指向第一个有效元素

    while(p->next!=L)
    {
        tail = p->next;

        if(p->data==item)//最后一个元素是不存在后继的
            return tail->data;

        p = tail;
    }
    
    return -1;//表示返回指定位置元素失败
}

bool ListInsert(Linklist L,int loc,int item)//向线性表指定位置插入元素
{
    Linklist p,New;
    int i=1;//设置为1，很重要哦
    
    if((L)==NULL||loc>ListLength(L)+1||loc<1)//销毁后就不能插入数据了
        return false;

    p = L->next;//指向第一个有效结点或头结点

    while(i<loc-1)//获取第loc-1位置地址
    {
        p = p->next;
        i++;
    }

    New = (Linklist )malloc(sizeof(DuLNode));
    New->data = item;
    New->next = p->next;
    New->prior = p;
    p->next = New;

    return true;
}

bool ListDelete(Linklist L,int loc,int *e)//删除线性表第i个位置的元素，并把删除元素返回
{
    Linklist p,q;
    int i=1;
    
    if(L==NULL||loc>ListLength(L)||loc<1)
        return false;

    p = L->next;//指向第一个有效结点

    while(i<loc-1)//获取第loc-1位置地址
    {
        p = p->next;
        i++;
    }

    q = p->next;//指向位于loc位置的结点
    (*e) = q->data;
    p->next = q->next;
    q->next->prior = p;
    free(q);
    return true;
}

void ListTraverse(Linklist L)//将线性表进行遍历
{
    Linklist p;

    p = L->next;//指向第一个有效结点

    while(p!=L)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

int main()
{

    Linklist L;
    int i,e;
    
    
    if(!InitList(&L))//初始化线性表
    {
        printf("抱歉，内存分配失败！\n");
    }
    
    for(i=1;i<=13;i++)//向线性表中插入新元素
    {
        if(!ListInsert(L,i,i))
        {
            printf("插入失败\n");
            return 0;
        }
    }
    //ListInsert(L,2,6666);

    ListTraverse(L);//遍历线性表
    //DestoryList(&L);//销毁线性表（破坏表结构）
    //ListTraverse(L);//遍历线性表
    //ClearList(L);/清空线性表（不破坏表结构）

    ListDelete(L,2,&e);//删除线性表指定位置元素
    printf("线性表被删除的元素是：%d\n",e);
    printf("执行删除操作后的线性表:");
    ListTraverse(L);//遍历线性表

    if(PriorElem(L,3)!=-1)//获取值为3的元素的前驱
    {
        printf("元素3的前驱为：%d\n",PriorElem(L,3));
    }
    else
    {
        printf("查询的元素可能不存在或者位于线性表的第一个位置不存在前驱！\n");
    }
    
    if(NextElem(L,3)!=-1)//获取值为3的元素的后继
    {
        printf("元素3的后继为：%d\n",NextElem(L,3));
    }
    else
    {
        printf("查询的元素可能不存在或者位于线性表的最后一个位置不存在后继！\n");
    }
    
    if(LocateElem(L,3)!=0)//查询指定元素在线性表中的位置
    {
        printf("值为3的元素在线性表中的位置：%d\n",LocateElem(L,3));
    }
    else
    {
        printf("你所查询的元素不存在\n");
    }

    return 0;
}