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

柔情只为你懂 2022-10-22 11:59 117阅读 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 f2()//f()函数的改进
    {
        //第一步, 把数据导入数组中
        int T[list_Length];
        struct Node* p=head->next;
        int i=0;
        while(p!=NULL)
        {
            T[i]=p->data;
            p=p->next;
            i++;
        }
        //第二步, 逆序输出数组中的数据
        i=list_Length-1;
        while(i>=0)
        {
            if(i!=0)//当前输出元素不是输出序列的最后一个
                printf("%d ", T[i]);
            else//当前输出元素是输出序列的最后一个
                printf("%d\n", T[i]);
            i--;
        }
        return ;
    }//时间复杂度降为O(n)
    
    int main()
    {
        int c;
        Create_LinkList();//创建头结点
        while(1)
        {
            scanf("%d", &c);
            Node_Insert(c);
            if(getchar()=='\n')
            {
                break;
            }
        }
        f2();
        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/b19071e6090d428b8bb9d74940b2e295.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70 1]: /images/20221022/8668ceb0414d4dcb8da594c07c98ceaa.png