C++开学第二次作业(5.14)-白红宇

C++开学第二次作业(5.14)

阅读量：5255 次

发布时间：2019-06-14

本文共 2871 字，大约阅读时间需要 9 分钟。

开学第二次作业(5.14)

题目

给定一个常数K以及一个单链表L，请编写程序将L中每K个结点反转。例如：给定L为1→2→3→4→5→6，K为3，则输出应该为3→2→1→6→5→4；如果K为4，则输出应该为4→3→2→1→5→6，即最后不到K个元素不反转。输入格式：每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(<= 105)、以及正整数K(<=N)，即要求反转的子链结点的个数。结点的地址是5位非负整数，NULL地址用-1表示。接下来有N行，每行格式为：Address Data Next其中Address是结点地址，Data是该结点保存的整数数据，Next是下一结点的地址。输出格式：对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。输入样例：00100 6 400000 4 9999900100 1 1230968237 6 -133218 3 0000099999 5 6823712309 2 33218输出样例：00000 4 3321833218 3 1230912309 2 0010000100 1 9999999999 5 6823768237 6 -1

这题大家每个人都做过了,不过是换成了新的方法--链表而已,也没啥好说的了,不过需要注意的是,本题一开始依然是不能创建链表的,应该要先把每个节点先存储起来(用原来的老方法),之后再创建链表、反转链表,仅此而已。

以下给出代码(这次作业代码后面有彩(吐)蛋(槽))

#include
    
     #include
     
      #include
      
       using namespace std;struct Link{    int Data;    int Adress;    Link *nx;};int N,K;int f[1000050] = {0};int Now[100050] = {0};int Back[100050] = {0};int Data[100050] = {0};void CreatLink(Link *head)//创建链表 {    Link *p,*q = head;    int coun = 0;    int t = 0;    while (Back[t] != -1)    {        t = f[Back[t]];        p = new Link;        p->Data = Data[t];        p->Adress = Now[t];        q->nx = p;        q = p;        coun++;    }    N = coun; //可能有链表外的点     p->nx = NULL;    return;}Link* Rotation(Link *p,Link *q)//p为需要反转的前一个节点, q为需要反转最后一个结点的后一个 {    Link *r1 = p->nx;   //当前反转的结点    Link *r2;           //记录当前反转结点的下一个节点     Link *r3 = p->nx;   //记录反转的第一个结点,用于最后要连到全部反转后的下一个结点     while (r1 != q)    {        r2 = r1->nx;        r1->nx = p->nx;        p->nx = r1;        r1 = r2;    }    r3->nx = q;    return r3;//返回反转段的最后一个结点 }int main(){//  freopen("xx.txt","r",stdin);    /*保存各个点*/     scanf("%d %d %d",&Back[0],&N,&K);    int i;    for (i = 1; i < N + 1; i++)    {        scanf("%d %d %d",&Now[i],&Data[i],&Back[i]);        f[Now[i]] = i;    }    /*创建链表*/     Link *head = new Link;    head->nx = NULL;    CreatLink(head);    /*反转链表*/     int T = N/K;    Link *p,*q = head;    for (i = 0; i < T; i++)     {        p = q;        int coun = 0;        while(coun < K)        {            coun++;            q = q->nx;        }        q = Rotation(p,q->nx);    }    /*输出链表 */     p = head->nx;    delete head;    while (p->nx)    {        printf("%05d %d %05d\n",p->Adress ,p->Data, p->nx->Adress);        q = p;        p = p->nx;        delete q;//C程序设计平台上面这句话留着会给你2个RE,我不知道为啥     }    printf("%05d %d -1\n",p->Adress ,p->Data);    delete p;        return 0; }