C program that uses
functions to perform the followingoperations on singly linked
list.:i) Creation ii) Insertion iii) Deletion iv) Traversali)
Creation
program code:
#include<stdio.h>
#include<stdlib.h>
#define NULL 0
struct linked_list
{
int number;
struct linked_list *next;
};
typedef struct linked_list node;
/* node type defined */
main()
{
node *head;
void create(node *p);
int count(node *p);
void print(node *p);
head = (node
*)malloc(sizeof(node));
create(head);
printf("\n");
printf(head);
printf("\n");
printf("\nNumber of items =
%d \n", count(head));
}
void create(node *list)
{
printf("Input
a number\n");
printf("(type -999 at end):
");
scanf("%d", &list
-> number);
/* create current node */
if(list->number ==
-999){list->next = NULL;
}
else
/*create next node */
{
list->next = (node
*)malloc(sizeof(node));
create(list->next);
*/ Recursion occurs */
}
return;
}
void print(node *list)
{
if(list->next != NULL)
{
printf("%d-->",list
->number);
/* print
current item */
if(list->next->next
== NULL)
printf("%d",
list->next->number);
print(list->next);
/* move to next item */
}
return;
}
int count(node *list)
{
if(list->next == NULL)
return (0);
else
return(1+ count(list->next));
}
ii) Insertion
node *insert(node *head)
{
node *find(node *p, int a);
node *new;
/* pointer to new node */
node *n1;
/* pointer to node preceding key node */
int key;int x;
/* new item (number) to be inserted */
printf("Value of new
item?");
scanf("%d", &x);
printf("Value of key item ?
(type -999 if last) ");
scanf("%d", &key);
if(head->number == key)
/* new node is first */
{new = (node *)malloc(size
of(node));
new->number = x;new->next =
head;head = new;
}
Else
/* find key node and insert new node */
{
/* before the key node */
n1 =
find(head, key);
/* find key node
*/
if(n1 == NULL)
printf("\n key is not found
\n");
else
/* insert new node */
{
new = (node
*)malloc(sizeof(node));
new->number = x;
new->next = n1->next;
n1->next = new;
}
}
return(head);
}
node *find(node *lists, int key)
{
if(list->next->number == key)
/* key found */
return(list);
else
if(list->next->next == NULL)
/* end */
return(NULL);
else
find(list->next, key);
}
iii) Deletion
node *delete(node *head)
{
node *find(node *p, int a);
int key;
/* item to be deleted */
node *n1;
/* pointer to node preceding key node */
node *p;
/* temporary pointer */
printf("\n What is the
item (number) to be deleted?");
scanf("%d", &key);
if(head->number == key)
/* first node to be deleted) */
{
p = head->next;
/* pointer to 2nd node
in list */
free(head);
/* release space of key node */
head = p;
/* make head to point to 1st node */
}
else{n1 = find(head, key);
if(n1 == NULL)
printf("\n key not found
\n");
else
/* delete key node */
{
p = n1->next->next;
/* pointer to the nodefollowing
the keynode */
free(n1->next);
/* free key node */
n1->next = p;
/* establish link */
}
}
return(head);
}
iv) Traversal
#include <stdio.h>
#include <stdlib.h>
#define NULL 0
struct linked_list
{
int number;
struct linked_list *next;
};
typedef struct linked_list node;
main ()
{
int n;
node *head = NULL;
void print(node *p);
node *insert_Sort(node *p, int n);
printf("Input the list
of numbers.\n");
printf("At end, type
-999.\n");
scanf("%d",&n);
while(n != -999)
{
if(head == NULL)
/* create 'base' node */
{
head = (node
*)malloc(sizeof(node));
head ->number = n;
head->next = NULL;
}
Else
/* insert next item */
{
head = insert_sort(head,n);
}
scanf("%d", &n);
}
printf("\n");
print(head);
print("\n");
}
node *insert_sort(node
*list, int x)
{
node *p1, *p2, *p;
p1 = NULL;
p2 = list;
/* p2 points to first node */
for( ; p2->number < x ; p2 =
p2->next)
{
p1 = p2;
if(p2->next == NULL)
{
p2 = p2->next;
/* p2 set to NULL */
break;
/* insert new node at end */
}
}
/* key node found */
p = (node
*)malloc(sizeof(node));
/* space for new node */
p->number = x;
/* place value in the new node */
p->next = p2;
/* link new node to key node */
if (p1 ==
NULL)list = p;
/* new node becomes the firstnode
*/
Else
p1->next = p;
/* new node inserted after1st
node */
return (list);
}
void print(node *list)
{
if (list == NULL)
printf("NULL");
else
{
printf("%d-->",list->number);
print(list->next);
}
return;
}
No comments:
Post a Comment