逆序(算法时间复杂度为n^2)

落日映苍穹つ 2022-10-22 11:58 18阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70][]

#include<stdio.h>
    #include<stdlib.h>
    struct Node
    {
        int data;
        struct Node* next;
    };
    
    short list_Length;//全局变量list_Length记录当前表长
    struct Node* head;//全局指针head, 负责指向当前链表的头结点
    struct Node* rear;//全局指针rear, 负责指向当前表尾结点: 如果表为空, 那么rear指向头结点
    
    void Create_LinkList()//创建链表, 即初始化头结点
    {
        head=(struct Node*)malloc(sizeof(struct Node));
        if(head!=NULL)//结点申请成功
        {
            head->data=0;//头结点的数据域置零
            rear=head;//表尾指针暂时指向头结点
            head->next=NULL;
            list_Length=0;
        }
        else//结点申请失败
        {
            printf("头结点申请失败!\n");
        }
        return ;
    }
    
    void Node_Insert(int c)//插入新结点到链表中
    {
        struct Node* p;
        p=(struct Node*)malloc(sizeof(struct Node));//申请新的Node结点
        if(p!=NULL)//结点申请成功
        {
            p->data=c;//新结点的数据由函数外传入
            p->next=NULL;
            rear->next=p;//插入结点前的表尾结点的next指针指向当前结点
            rear=p;//表尾指针指向当前新申请结点
            list_Length++;//表长+1
        }
        else
        {
            printf("结点申请失败!\n");
            return ;
        }
    }
    
    void f()//逆序输出当前链表中的数据
    {
        int i, n=list_Length;
        struct Node* p;
        while(n>=1)
        {
            i=1;
            p=head;p指针指向头结点
            while(i<=n)
            {
                p=p->next;
                i++;
            }//找到表中第n个结点
            if(n!=1)//n!=1 -> 当前数据不是输出序列的最后一个
                printf("%d ", p->data);
            else
                printf("%d\n", p->data);
            n--;
        }
        return ;
    }
    
    void Traversal()//遍历链表并输出各结点数据域中的值
    {
        struct Node* p;
        p=head->next;
        while(p!=NULL)
        {
            printf("%d ", p->data);;//输出当前结点数据域中的值
            p=p->next;
        }
        printf("\n");
        return ;
    }
    
    int main()
    {
        int c;
        Create_LinkList();//创建头结点
        while(1)
        {
            scanf("%d", &c);
            Node_Insert(c);
            if(getchar()=='\n')
            {
                break;
            }
        }
        f();
        return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70]: /images/20221022/28d9806b9a7a47168dd442689525abe7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70 1]: /images/20221022/f208ecc53a784c7dbea6dff69f8f66d7.png