算法的阶梯

Even and odd linked list

2018-08-29  本文已影响9人  Tedisaname

Even and odd list
Given a single linked list, put all the odd and even nodes together. Note >that the odd and even nodes here refer to the parity of the node number, >not the parity of the value of the node.

// C codes:
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>    //function to exit()
#define OK 1    //status for 1
#define ERROR 0 //status for 0

//struct for a node
typedef struct Node{
    int data;
    struct Node * next;
}Node,*PNode;

// Function to the linked list initialization 
int Initialization(PNode& head)
{
    head = (PNode)malloc(sizeof(Node));//create a head Node
    head->next = NULL;//initialize the head node
    return OK;
}


//crerate the linked list from user input
void create(PNode head)
{

    int m,a;
    PNode p, q;
    printf("Please input the length of the linked list:");
    scanf("%d",&m); 
    q = NULL;
    for(int i = 0; i < m; i++)
    {
        scanf("%d",&a);
        p = (PNode)malloc(sizeof(Node));
        p->data = a;
        p->next = NULL;
        if(head->next == NULL)//attention!!!!head ->next == NULL ,not head == NULL
        head->next = p;//head directly points to p if the head points to NULL 
        else
        q->next = p;//else,pointer q points to the p;
        
        q = p;//pointer q points to p   
    }
        
}


//print all the emements of linked list
void printLinkedlist(PNode head)
{
    PNode t = head->next;//the next field of the head pointer is the first valid node attention~!!!!!!
    while(t != NULL)
    {
        printf("%d ",t->data);
        t = t->next;
    }
    printf("\n");
}
//Function to get the length of the linked list
int getlength(PNode head)
{
    int k = 0;
    PNode t = head->next;
    while(t != NULL)
    {
        k++;
        t = t->next;
    }
    return k;
}
//Function to the even and odd linked list
PNode evenOddList(PNode A,PNode result,int len)
{
    int j = 1;
    PNode p,q,w; 
    p = A->next;
    q = NULL;
    
    while(p != NULL && j <= len)
    {
        
        if(j % 2 == 1)
        {
             PNode w = (PNode)malloc(sizeof(Node));
             w->data = p->data;
             w->next = NULL;
            if(result->next == NULL)
                result->next = w;
            else
                q->next = w;
            
            q = w;  
        }
        j++;
        p = p->next;
    }
    
    j = 1; 
    p = A->next;
    while(p != NULL && j <= len)
    {
        
        if(j % 2 == 0)
        {
             PNode w = (PNode)malloc(sizeof(Node));
             w->data = p->data;
             w->next = NULL;
            if(result->next == NULL)
                result->next = w;
            else
                q->next = w;
            
            q = w;  
        }
        j++;
        p = p->next;
    }
    
    return result;
}

int main()
{
    PNode A,result;//create two nodes of two linked list A and result
    if(Initialization(A)){
        printf("Initialization successful!\n");
    }
    else
    {
        printf("Initialization failed!\n"); 
        exit(ERROR);
    }   
    create(A);//Create linked list from the function to  user input
    
    printLinkedlist(A);//print list before sorting  
    
    int len = getlength(A);//get the length of the linked list
    
    printf("the length of the linked list is %d\n",len);
    
    if(Initialization(result)){
        printf("Initialization successful!\n");
    }
    else
    {
        printf("Initialization failed!\n"); 
        exit(ERROR);
    }   
    
    evenOddList(A,result,len);//Function is called to create the even and odd linked list
    printLinkedlist(result);//print the linked list of the even and
    return 0;
}

driver data to test:
input: 1->2->3->4->5->NULL
output: 1->3->5->2->4->NULL

You can leave me a message if you find out anything incorrect in my diary, I'll correct it, thanks.

上一篇下一篇

猜你喜欢

热点阅读