双向链表的基本操作

实验三:双向链表的基本操作

   1.利用尾插法建立一个双向链表。    2.遍历双向链表。    3.实现双向链表中删除一个指定元素。 4.在非递减有序双向链表中实现插入元素e仍有序算法。    5.判断双向链表中元素是否对称若对称返回1否则返回0。 6.设元素为正整型,实现算法把所有奇数排列在偶数之前。    7.在主函数中设计一个简单的菜单调试上述算法。

参考源码

#include <stdio.h>
#include <stdlib.h>
#define ERROR       -1
#define OK      1
#define OVERFLOW    -2
typedef int ElemType;
typedef int Status;
typedef struct DuLNode {
    ElemType    data;
    struct DuLNode  *prior;
    struct DuLNode  *next;
}DuLNode, * DuLinkList;
/* 创建双链表 */
Status InsertDuLinkList_real( DuLinkList L )
{
    int n, i, c;
    printf( "请输入要创建双链表的长度n=" );
    scanf( "%d", &n );
    DuLinkList p, dl;
    dl = L;
    printf( "请依次输入数据:" );
    for ( i = 0; i < n; i++ )
    {
        if ( !(p = (DuLinkList) malloc( sizeof(DuLNode) ) ) )
            return(OVERFLOW);
        scanf( "%d", &c );
        p->data     = c;
        dl->next    = p;
        p->prior    = dl;
        p->next     = L;
        L->prior    = p;
        dl      = p;
    }
    return(OK);
}


/* 遍历双链表 */
Status pDuLinkList( DuLinkList L )
{
    DuLinkList dl;
    dl = L->next;
    while ( dl->next != L )
    {
        printf( "%d ", dl->data );
        dl = dl->next;
    }
    printf( "%d\n", dl->data );
    return(OK);
}


DuLinkList GetElemP_DuL( DuLinkList L, ElemType i )
{
    DuLinkList dl;
    dl = L->next;
    while ( dl != L )
    {
        if ( dl->data == i )
            return(dl);
    }
    return(NULL);
}


/* 双链表的删除,实现双向链表中删除一个指定元素 */
Status LinkDelete_Dul( DuLinkList L, int i )
{
    DuLinkList p;
    if ( !(p = GetElemP_DuL( L, i ) ) )
        return(ERROR);
    p->prior->next =
        p->next;
    p->next->prior =
        p->prior;
    free( p );
    return(OK);
}


Status GetLengthOfDL( DuLinkList L )
{
    int     n = 0;
    DuLinkList  dl;
    dl = L->next;
    while ( dl != L )
    {
        n++;
        dl = dl->next;
    }
    return(n);
}


/* 实现双链表的指定位置的删除 */
Status LinkDelete_Dd( DuLinkList L, int i )
{
    if ( i > GetLengthOfDL( L ) || i < 1 )
    {
        printf( "删除下标非法!\n" );
        return(ERROR);
    }
    DuLinkList  dl;
    int     n = 1;
    dl = L->next;
    while ( n < i )
    {
        n++;
        dl = dl->next;
    }
/* p = dl->prior; */
    dl->prior->next =
        dl->next;
    dl->next->prior =
        dl->prior;
    free( dl );
    return(OK);
}


/* 排序 */
Status sortDuLinkList( DuLinkList L )
{
    int n = GetLengthOfDL( L );
/* printf("%d",n); */
    int     t;
    DuLinkList  p;
    for ( int i = 1; i < n; i++ )
    {
        p = L->next;
        for ( int j = 0; j < n - i; j++ )
        {
            if ( p->data >
                 p->next->data )
            {
                t   = p->data;
                p->data =
                    p->next->data;
                p->next->data = t;
            }
            p = p->next;
        }
    }
    return(OK);
}


/* 插入 */
Status InsertDuL( DuLinkList L, int n )
{
/* printf("dd"); */
    DuLinkList p, dl;
    if ( !(dl = (DuLinkList) malloc( sizeof(DuLNode) ) ) )
        return(OVERFLOW);
    p       = L->next;
    dl->data    = n;
    while ( p->data < n )
        p = p->next;
    printf( "%d", p->data );
    p->prior->next  = dl;
    dl->prior   = p->prior;
    p->prior    = dl;
    dl->next    = p;
    return(OK);
}


/* 判断双链表是否对称 */
Status isReturnDuL( DuLinkList L )
{
    DuLinkList p, q;
    p   = L->next;
    q   = L->prior;
    int n = GetLengthOfDL( L );
    if ( n % 2 )
    {
        while ( p->data == q->data && p != q )
        {
            p = p->next; q = q->prior;
        }
        if ( q == p )
            return(1);
        else
            return(0);
    }else{
        while ( p->data == q->data && p->next != q )
        {
            p = p->next; q = q->prior;
        }
        if ( p->data == q->data )
            return(1);
        else
            return(0);
    }
}


/* 实现算法把所有奇数排列在偶数之前 */
Status inLawSort( DuLinkList L )
{
    DuLinkList  p, dl, p1;
    int     i, n = GetLengthOfDL( L );
    i   = 0;
    p   = L->next;
    dl  = L->prior;
    while ( i < n )
    {
        if ( (p->data) % 2 != 0 )
        {
            i++;
            p = p->next;
        }else  {
            p1      = p->next;
            p->next->prior  =
                p->prior;
            p->prior->next =
                p->next;
            p->next     = L;
            p->prior    = dl;
            dl->next    = p;
            L->prior    = p;
            dl      = p;
            p       = p1;
            i++;
        }
    }
    return(OK);
}


void print()
{
    printf( "欢迎测试双链表,菜单如下:\n" );
    printf( "1.运用尾差法创建双链表\n" );
    printf( "2.遍历双向链表\n" );
    printf( "3.实现双链表删除一个指定元素\n" );
    printf( "4.在非递减有序双向链表中实现插入元素e仍有序\n" );
    printf( "5.判断双向链表中元素是否对称若对称返回1否则返回0\n" );
    printf( "6.实现算法把所有奇数排列在偶数之前\n" );
    printf( "0.EXIT\n" );
    printf( "请选择操作序号:" );
}


int main()
{
    DuLinkList  L;
    Status      e, ch, n;
    bool        flag = true;
    L       = (DuLinkList) malloc( sizeof(DuLNode) );
    L->prior    = NULL;
    L->next     = NULL;
    print();
    while ( scanf( "%d", &ch ) != EOF )
    {
        switch ( ch )
        {
        case 0:
            flag = false;
            break;
        case 1:
            if ( InsertDuLinkList_real( L ) )
                printf( "创建成功!\n" );
            else
                printf( "创建失败!\n" );
            break;
        case 2:
            if ( pDuLinkList( L ) )
                printf( "遍历成功!\n" );
            else
                printf( "遍历失败!\n" );
            break;
        case 3:
            printf( "请选择删除方式:1.删除指定元素  2.删除制定下标\n" );
            printf( "请输入选择序号e=" );
            scanf( "%d", &e );
            switch ( e )
            {
            case 1:
                printf( "请输入指定元素n=" );
                   
                scanf( "%d", &n );

                if ( LinkDelete_Dul( L, n ) )
                       
                    printf( "指定元素已删除!\n" );
                else
                       
                    printf( "指定元素删除失败!\n" );
                break;
            case 2:
                printf( "请输入指定下标n=" );
                scanf( "%d", &n );
                if ( LinkDelete_Dd( L, n ) )
                       
                    printf( "指定下标删除成功!\n" );
                else
                       
                    printf( "指定下标删除失败!\n" );
            }
            break;
        case 4:
            printf( "按非递减排序双链表!\n" );
            sortDuLinkList( L );
            pDuLinkList( L );
            printf( "请输入插入的元素n=" );
            scanf( "%d", &n );
            if ( InsertDuL( L, n ) )
                printf( "插入成功!\n" );
            else
                printf( "插入失败!\n" );   
            break;
        case 5:
            if ( isReturnDuL( L ) )
                printf( "1\n" );
            else
                printf( "0\n" );
            break;
        case 6:
            if ( inLawSort( L ) )
            {
                printf( "奇前偶后排序成功!\n" );
                pDuLinkList( L );
            }else
                printf( "奇前偶后排序失败!\n" );
            break;
        default:
            printf( "输入错误!\n" );
        }
        if ( !flag )
            break;
    }
    return(0);
}

参考

迁移自谢先斌的博客:http://blog.sina.com.cn/s/blog_002e203101010bvk.html

完毕。