DS_Reversing Linked List

在PTA上刷DS的题目，有些问题和细节，放上来和大家分享和讨论

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤10^5) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

Sample Output:

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifndef NULL
#define NULL 0
#endif // NULL

typedef struct Node *LinkedList;
struct Node
{
   char Address[6];
   int Data;
   char NextAdd[6];
   struct Node *Next;
};
typedef struct stack *Stack;
struct stack
{
   LinkedList Position;
   struct stack *Next;
};

void GetHead(char* Address,int* N,int* All);
LinkedList ReadData(int N);
void SortList(LinkedList L,char* HeadAddress);
void PrintReversing(LinkedList L,int N,int All);
LinkedList MakeEmpty();
LinkedList AddressFind(char* Address, LinkedList L);
Stack CreateStack();
void Push(Stack S,LinkedList item);
LinkedList Pop(Stack S);
int isEmpty(Stack S);
int isFull(Stack S,int N);
void AddLNode(LinkedList L,LinkedList Lnode);
void PrintLinkedList(LinkedList L);


int main()
{
    LinkedList L1;
    char HeadAddress[6];
    int N,All;
    GetHead(HeadAddress,&N,&All);
    L1 = ReadData(All);
    SortList(L1,HeadAddress);
    PrintReversing(L1,N,All);
    return 0;
}
void GetHead(char* Address,int* N,int* All)
{
    scanf("%s %d %d",Address,All,N);
    return;
}
LinkedList ReadData(int All)
{
    int i;
    LinkedList L,ptr,TempN;
    L = MakeEmpty();
    ptr = L;
    for(i = All;i>0;i--)
    {
        TempN = MakeEmpty();
        scanf("%s %d %s",TempN->Address,&(TempN->Data),TempN->NextAdd);
        ptr->Next = TempN;
        ptr = TempN;
    }
    return L;
}

void SortList(LinkedList L,char* HeadAddress)
{
    LinkedList ptr = L;
    LinkedList TempNode;
    char Add[6];
    strcpy(Add,HeadAddress);
    while(ptr->Next)//ptr or ptr->Next
    {
        TempNode = AddressFind(Add,ptr);
        if(TempNode)
        {
            TempNode->Next = ptr->Next;
            ptr->Next = TempNode;
            ptr = TempNode;
            strcpy(Add,ptr->NextAdd);
        }
        else
            return;
    }
}

void PrintReversing(LinkedList L,int N,int All)
{
    int i,Remainder;
    Stack S;
    LinkedList ReList,ReNode;
    LinkedList ptr = L->Next;
    ReList = MakeEmpty();
    if(N == 1)
    {
        for(i = All;i>0;i--)
        {
            //printf("%s %d %s\n",ptr->Address,ptr->Data,ptr->NextAdd);
            AddLNode(ReList,ptr);
            ptr = ptr->Next;
        }
    }
    else
    {
        S = CreateStack();
        Remainder = All%N;
        for(i = All;i>Remainder;i--)
        {

            Push(S,ptr);
            ptr = ptr->Next;
            if(isFull(S,N))
            {
                while(isEmpty(S) == 0)
                {
                   ReNode = Pop(S);
                   AddLNode(ReList,ReNode);
                }
            }
        }
        for(i = Remainder;i>0;i--)
        {
            //printf("%s %d %s\n",ptr->Address,ptr->Data,ptr->NextAdd);
            AddLNode(ReList,ptr);
            ptr = ptr->Next;
        }
    }
    PrintLinkedList(ReList);
}
LinkedList MakeEmpty()
{
    LinkedList L;
    L = (LinkedList)malloc(sizeof(struct Node));
    L->Next = NULL;
    return L;
}

LinkedList AddressFind(char* Address, LinkedList L)
{
    LinkedList ptr = L;
    LinkedList TempP;
    while(ptr->Next)
    {
        if(strcmp(Address,ptr->Next->Address) != 0)
        {
            ptr = ptr->Next;
        }
        else
        {
            TempP = ptr->Next;
            ptr->Next = TempP->Next;
            TempP->Next = NULL;
            return TempP;
        }
    }
    return NULL;
}

Stack CreateStack()
{
    Stack PtrS;
    PtrS = (Stack)malloc(sizeof(struct stack));
    PtrS->Next = NULL;
    return PtrS;
}

void Push(Stack S,LinkedList item)
{
    Stack TempItem;
    TempItem = (Stack)malloc(sizeof(struct stack));
    TempItem->Position = item;
    TempItem->Next = S->Next;
    S->Next = TempItem;
}
LinkedList Pop(Stack S)
{
    if(S->Next == NULL)
    {
        printf("栈空");
        return NULL;
    }
    Stack FirstItem;
    LinkedList ItemData;
    FirstItem = S->Next;
    S->Next = FirstItem->Next;
    ItemData = FirstItem->Position;
    free(FirstItem);
    return ItemData;
}

int isEmpty(Stack S)
{
    return (S->Next == NULL);
}
int isFull(Stack S,int N)
{
   int Num = 0;
   Stack ptr = S;
   while(ptr->Next)
   {
      ptr = ptr->Next;
      Num++;
   }
   if(Num == N)
      return 1;
   else
      return 0;
}
void AddLNode(LinkedList L,LinkedList Lnode)
{
   LinkedList TempP,ptr;
   ptr = L;
   TempP = MakeEmpty();
   strcpy(TempP->Address, Lnode->Address);
   TempP->Data = Lnode->Data;
   strcpy(TempP->NextAdd,"-1");
   while(ptr->Next)
      ptr = ptr->Next;
   strcpy(ptr->NextAdd,TempP->Address);
   ptr->Next = TempP;
}
void PrintLinkedList(LinkedList L)
{
   LinkedList ptr;
   ptr= L->Next;
   while(ptr)
   {
      printf("%s %d %s\n",ptr->Address,ptr->Data,ptr->NextAdd);
      ptr = ptr->Next;
   }
   return;
}