ENGINEERING FACULTY CMPE 242 / ISYE 242 / MISY 242 / VCP 215

0 Yorum

 

 

Labwork 10

 

Laboratory Works

Laboratory work will be done at the laboratory.

Consider the following linked list node structure:

 

struct node{

            int data;

struct node *next;

};

 

Implement the following basic functions of the linear linked list structure:

 

  1. Check empty list

 

int is_empty( struct node *header)

{

            if(header==NULL)

                        return 1; //TRUE

else

return 0; //FALSE

}

 

  1. Create a node

 

struct node * newnode(int d)

{

            struct node *temp;

            temp=(struct node *) malloc(sizeof(node));

            temp->data =d;

            temp->next=NULL;

return temp;

}

 

 

  1. Insert a node into front/back/middle of LL

 

struct node * insertFront(struct node *header, int d)

{

            struct node *temp;

            temp=newnode(d);

            temp->next =header;

header=temp;

return header;

}

 

 

struct node * insertBack(struct node *header, int d)

{

            struct node *temp, *headertemp;

            temp=newnode(d);

if(header==NULL)

{

 

header=temp;

return header;

                        }

                        headertemp=header;

                        while(headertemp->next!=NULL)

headertemp =headertemp->next;

headertemp->next=temp;

                        return header;

}

 

void insertAfter(struct node *afterNode, int d)

{

            struct node *temp;

            temp=newnode(d);

                        temp->next=afterNode->next;

                        afterNode->next=temp;

}

 

  1. Delete a node from front/back/middle of LL

struct node * deleteFront(struct node *header)

{

            struct node *temp;

if(header==NULL)

            return header;

temp=header;

            header= header->next;

free(temp);

return header;

}

 

 

struct node * deleteBack(struct node *header)

{

            struct node *temp, *headertemp;

if(header==NULL)

 

return header;

                        headertemp=header;

                        while(headertemp->next->next!=NULL)

headertemp =headertemp->next;

                        temp=headertemp->next;

headertemp->next=NULL;

free(temp);

                        return header;

}

void deleteAfter(struct node *afterNode)

{

            struct node *temp;

            if(afterNode->next==NULL || afterNode==NULL)

                        return;

                        temp =afterNode->next;

                        afterNode->next=temp->next;

                        free(temp); 

}

Task 1: Write down a complete C/C++ program to test your linear linked list implementation. Additionally, write another function which will be used to list the linked list content. Complete your implementation using the following code:

 

header = insertBack(header,2);

header = insertBack(header,4);

header = insertBack(header,6);

 DisplayList(header);

header = insertFront(header,1);

DisplayList(header);

insertAfter(header->next->next,5);

 DisplayList(header);

 header = deleteFront(header);

 DisplayList(header);

 header = deleteBack(header);

 DisplayList(header);

 deleteAfter(header->next);

 DisplayList(header);

 

Task 2: Write a function that inserts a node to nth place of a Linear Linked List. Consider the following prototype:

struct node * insertn (struct node * p, int n);

 

 

Task 3: Write a function that deletes all the nodes in the given linked list.

 

void deletelist (struct node *);

 

Task 4: Write a function that copies a linked list. Source and destination lists are the input parameters to the function.

 

void copylist (struct node *,struct node * );

 

Answer

Task 1: Write down a complete C/C++ program to test your linear linked list implementation. Additionally, write another function which will be used to list the linked list content. Complete your implementation using the following code:

#include <bits/stdc++.h> 
using namespace std; 
  

class Node  
{  
    public: 
    int data;  
    Node* next;  
};  
  

void sortedInsert(Node** head_ref, Node* new_node)  
{  
    Node* current;  

    if (*head_ref == NULL || (*head_ref)->data >= new_node->data)  
    {  
        new_node->next = *head_ref;  
        *head_ref = new_node;  
    }  
    else
    {  
   
        current = *head_ref;  
        while (current->next!=NULL &&  
            current->next->data < new_node->data)  
        {  
            current = current->next;  
        }  
        new_node->next = current->next;  
        current->next = new_node;  
    }  
}  
  

Node *newNode(int new_data)  
{  
   
    Node* new_node =new Node(); 
  
    
    new_node->data = new_data;  
    new_node->next = NULL;  
  
    return new_node;  
}  
  

void printList(Node *head)  
{  
    Node *temp = head;  
    while(temp != NULL)  
    {  
        cout<<temp->data<<" ";  
        temp = temp->next;  
    }  
}  
  

int main()  
{  
   
    Node* head = NULL;  
    Node *new_node = newNode(5);  
    sortedInsert(&head, new_node);  
    new_node = newNode(10);  
    sortedInsert(&head, new_node);  
    new_node = newNode(7);  
    sortedInsert(&head, new_node);  
    new_node = newNode(3);  
    sortedInsert(&head, new_node);  
    new_node = newNode(1);  
    sortedInsert(&head, new_node);  
    new_node = newNode(9);  
    sortedInsert(&head, new_node);  
    cout<<"Created Linked List\n";  
    printList(head);  
  
    return 0;  
}

 

Yorumlar (Toplam: 0)

Sıralama:
😭

Henüz yorum yapılmamış, ilk yorumu siz yazın.

Yorum Yaz

Onay Kodu .