C++ 单链表的基本操作

C++ 单链表的基本操作

实验二：单链表的基本操作

编写一个完整的程序，实现单链表的建立、插入、删除、输出等基本操作。

（1）建立一个带头结点的单链表。

（2）计算单链表的长度，然后输出单链表。

（3）查找值为x的直接前驱结点q。

（4）删除值为x的结点。

（5）把单向链表中元素逆置（不允许申请新的结点空间）。

（6）已知单链表中元素递增有序，请写出一个高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，他们的值可以和表中的元素相同，也可以不同）。

（7）同（6）的条件，试写一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间，并分析你的算法时间复杂度。

（8）利用（1）建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。

（9）在主函数中设计一个简单的菜单，分别测试上述算法。

代码

#include <stdio.h>
#include
<stdlib.h >

typedef struct node
{
    int data;
    struct node * next;
}Lnode, * LinkList;

int m = sizeof(Lnode);

/* 建立新的链表 */
void Bulid_List( LinkList root )
{
    int num;
    LinkList s, p;
    s = root->next;
    int n;
    printf( "请输入新建链表的长度n数据:\n" );
    scanf( "%d", &n );

    printf( "请依次建立链表：" );
    for ( int i = 0; i < n; i++ )
        {
            scanf( "%d", &num );
            s->data = num;
            p = (LinkList) malloc( m );
            s->next = p;
            s = p;
            s->next = NULL;
        }

        printf( "链表已建立！\n" );
}


/* 对链表的输出，包括长度和元素 */
void OutPut_list( LinkList root )
{
    int len = 0;
    LinkList s;
    s = root->next;

    if ( s->next == NULL )
        printf( "单链表无数据，请先新建单链表。\n" );
    else
    {
        while ( s->next != NULL )
        {
            s = s->next;
            len++;
        }

        printf( "单链表的长度为：%d\n", len );
    printf( "单链表的数据如下:\n" );
    s = root->next;

    while ( s->next != NULL )
    {
        printf( "%d ", s->data );

        s = s->next;
    }
    printf( "\n" );

    }
}


void Find_list( LinkList root, int x )
{
    LinkList s, p;

    if ( root->next->next == NULL )
        printf( "单链表无数据，请先新建单链表。\n" );
    else
    {
        s = root->next;
        p = root->next->next;
        if ( s->data == x )
            printf( "此X值无前驱结点。\n" );
        else
        {
            while ( p->next != NULL )
            {
                if ( p->data == x )
                {
                    printf( "此X值的前驱结点的值为：%d\n", s->data );
                    return;
                }

                else
                {
                    s = p;
                    p = p->next;
                }
            }
            printf( "此链表不存在值为X的结点。\n" );
        }
    }
    return;
}

void Delete_list( LinkList root, int x )
{
    LinkList s;
    int
    flag;

    if ( root->next->next == NULL )
        printf( "单链表无数据，请先新建单链表。\n" );
    else
    {
        flag = 0;
        while ( root->next != NULL )
        {
            if ( root->next->data == x )
            {
                if ( root->next->next != NULL )
                {
                    s = root->next;
                    root->next = root->next->next;
                    free( s );
                    flag = 1;
                    return;
                }
            }
            else
                root = root->next;
        }
        if ( flag == 0 )
            printf( "待删除的数据不存在。\n" );
    }

    return;
}

LinkList NEW()
{
    LinkList new_node;
    new_node = (LinkList) malloc( m );
    new_node->next = NULL;
    new_node->data = 0;
    return(new_node);
}

/* 分解链表 */
void Divid( LinkList head )
{
    LinkList head_odd, head_even, p_odd, p_even, p, s;
    head_odd = NEW();
    head_even = NEW();
    p = head->next;
    p_odd = head_odd;
    p_even = head_even;
    while ( p != NULL )
    {
        s = p;
        p = p->next;
        if ( s->data % 2 == 0 )
        {
            p_odd->next = s;
            p_odd = p_odd->next;
            p_odd->next = NULL;
        }
        else
            {
                p_even->next = s;
                p_even = p_even->next;
                p_even->next = NULL;
            }
            }
            printf( "构建成功！\n" );
        printf( "奇数链表为：" );
        p = head_even->next;
        while ( p->next != NULL )
        {
            printf( "%d ", p->data );
            p = p->next;
        }
        printf( "\n偶数链表为：" );
        p = head_odd;
        while ( p->next != NULL )
        {
            printf( "%d ", p->next->data );
            p = p->next;
        }
        printf( "\n" );
    }/* 6 */
}

void DelteAndFree_list( LinkList root )
{
    LinkList s, p, t, k;
    int min, max;
    if ( root == NULL )
        printf( "单链表无数据，请先新建单链表。\n" );
    else
    {
        printf( "请输入所要min的值，max的值(min < max):\n" );
        scanf( "%d%d", &min, &max );
        s = root->next;
        p = root;
        while ( s->data < min )
        {
            s = s->next;
            p = p->next;
        }
        t = p;
        while ( s->data < max )
        {
            s = s->next;
            t = t->next;
        }

        s = p->next;
        p->next = t->next->next;
        t->next = NULL;
        while ( s->next != NULL )
        {
            k = s;
            s = s->next;
            free( k );
        }
        free( s );
    }
    return;
}

void DeleteCommon_list( LinkList root )
{
    LinkList s, p, t;
    if ( root->next->next == NULL )
        printf( "单链表无数据，请先新建单链表。\n" );
    else
    {
        s = root->next;
        p = root->next->next;
        while ( p->next != NULL )
        {
            if ( s->data == p->data )
            {
                t = p;
                p = p->next;
                s->next = p;
                free( t );
            }
            else
            {
               s = s->next;
               p = p->next;
            }
        }
    }
    return;
}

void Reserve_list( LinkList root )   /* 链表的逆置 */
{
    LinkList s, p, t;
    s = root->next;
    root->next = NULL;
    while ( s->next != NULL )
        {
            p = s->next;
            s->next = root->next;
            root->next = s;
            s = p;
        }

        LinkList head;
    head = (LinkList) malloc( m );
    head->next = NULL;
    t = root;
    while ( t->next != NULL )
        {
            t = t->next;
        }
        t->next = head;
    return;
}

void print() /* 打印菜单 */
{
    printf( "\n菜单如下：\n" );
    printf( "1.建立单链表\n" );
    printf( "2.计算单链表的长度并输出\n" );
    printf( "3.查找值为x的直接前驱结点q\n" );
    printf( "4.删除值为x的节点\n" );
    printf( "5.逆置单链表\n" );
    printf( "6.将单链表递增排序后删除表中所有值大于mink且小于maxk的元素\n" );
    printf( "7.将单链表递增排序后删除表中所有值相同的多余元素\n" );
    printf( "8.分解单链表，一个为奇数，另一个为偶数\n" );
    printf( "0.EXIT\n\n" );
    printf( "请输入你选菜单的数字：\n" );
}

int main( void ) /* 循环菜单 */
{
    LinkList root;
    int x;
    root = (LinkList) malloc( m );
    root->next = NULL;
    root->next = (LinkList) malloc( m );
    root->next->next = NULL;
    bool flag;
    int op;
    print();

    while ( scanf( "%d", &op ) != EOF ) /* show_arr(&arr); */
    {
        flag = true;
        switch ( op )
        {
        case 0:
           flag = false;
           break;
        case 1:
           Bulid_List( root );
           break;
        case 2:
           OutPut_list( root );
           break;
        case 3:
           printf( "请输入所要查找的x:\n" );
           scanf( "%d", &x );
           Find_list( root, x );
           break;
        case 4:
           printf( "请输入所要删除值x:\n" );
           scanf( "%d", &x );
           Delete_list( root, x );
           break;
        case 5:
           Reserve_list( root );
           break;
        case 6:
           DelteAndFree_list( root );
           break;
        case 7:
           DeleteCommon_list( root );
           break;
        case 8:
           Divid( root );
           break;
        default:
           printf( "您真笨，输入的数字非法，程序已退出！！\n" );
           break;
       }

        if ( !flag )
        {
            printf( "程序将退出！！谢谢使用！！\n" );
            break;
        }
        else{
            print();
        }
    }
    return(0);
}