A self referential structure includes at least one member that is a pointer to the structure of its own kind. A chain of such structures can be expressed as follows.
struct name {
member 1;
member 2;
:
struct name *pointer;
};
The above mentioned structure prototype describes one node (many such inter-connected nodes create a chain of structures) that comprises two logical segments. One of them stores information and the other one is a pointer indicating where the next component can be found.
The following figure depicts the composition of such a node,
Fig 11.1 : A simple description of nodes that creates a chain of structures.
Such self-referential structures are very useful in applications that involve linked data structures, such as lists and trees. Unlike a static data structure like an array where the number of elements that can be inserted is limited by the size of the array, a self-referential structure can dynamically be expanded or contracted. Operations like insertion or deletion of nodes in a self-referential structure involve simple and straight forward alteration of pointers .
11.1 LINEAR (SINGLY) LINKED LIST
A linear linked list is a chain of structures where each node points to the next node to create a list. To keep track of the starting node’s address a dedicated pointer is used (start pointer). The end of the list is indicated by a NULL pointer. In order to create a linked list of integers, we define each of its element (called node) using the following declaration.
struct node_type {
int data;
struct node_type *next;
};
struct node_type *start=NULL;
Note, the second member points to a node of same type.
Fig. 11.2 : A linear linked list.
Let us now develop a C program to manipulate linked lists. For this purpose we introduce a few basic functions which can be used to create a list, displaying its contents, inserting into a list and deleting an existing element. We also introduce two functions reverse and rec_reverse for reversing the elements of the list. When a list is created a pointer called start is used to indicate the beginning of the list. A function create_node, creates a node and returns a pointer to it. The function insert, is used to insert a new node in an existing list provided the data is not already present in the list. If it is not present, we place the data in a manner so that the new element is appended at the end of the list.
Example 11.1 :
# include
struct node_type {
int data;
struct node_type *next;
};
typedef struct node_type list;
void show_list(); /* displays list contents */
list *reverse(); /* reverses the list */
list *rec_reverse(); /* recursive list reverse */
list *insert();
list *create_node();
list *delete();
list *find();
main()
{
list temp,start=NULL;/* start points to the first node of the list */
char c=‘y’;
int n;
while(c != ‘n’ && c != ‘N’)
{
printf(“\nEnter the data :”);
scanf(“%d”,&n);
fflush(stdin);
temp=create_node();
temp->data=n;
temp->next=NULL;
if(!find(start,temp->data))
start=insert(start,temp);
printf(“\nDo you want to enter new data in the list :”);
scanf(“%c”,&c);
fflush(stdin);
}
while(c != ‘n’ && c != ‘N’)
{
printf(“\nEnter the data to be deleted :”);
scanf(“%d”,&n);
fflush(stdin);
if(find(start,n))
start=delete(start,n);
printf(“\nDo you want to delete another data from the list :”);
scanf(“%c”,&c);
fflush(stdin);
}
show_list(start);
temp=reverse(start);
show_list(start);
start=rec_reverse(temp);
show_list(start);
}
/* allocates memory for a new node */
list *create-node()
{
list *new;
new=(list *)malloc(sizeof(list));
new->next=NULL;
return(new);
}
/*recursive function to create and insert a new node at the end of the list */
list *insert(st,ndt)
list *st,*ndt;
{
if(!st)
return(ndt);
st->next=insert(st->next,ndt);
return(st);
}
/* searches a data item in the list and returns the node address that matches data; in case no match found returns NULL */
list *find(st,dt)
list *st;
int dt;
{
while(st)
if(st->data == dt)
return(st);
else
st=st->next;
return(st);
}
void show_list(list *temp)
{
while(temp)
{
printf(“\nThis node content is %d\n”,temp->data);
temp=temp->next;
}
printf(“\n”);
}
/* non recursive reverse list */
list reverse(list *l)
{
list *nxt,*temp;
if(!l)
return(l);
else
{
nxt=l->next;
l->next=NULL;
while(nxt)
{
temp=nxt->next;
nxt->next=l;
l=nxt;
nxt=temp;
}
return(l);
}
}
/* recursive reverse list */
list rec_reverse(list l)
{
list temp;
if(l == NULL || l->next == NULL)
return(l);
else
{
temp=rec_reverse(l->next);
l->next->next=l;
l->next=NULL;
return(temp);
}
}
/* recursive function for deleting a node from the list */
list *delete(st,n)
list *st;
int n;
{
list *tmp;
if(!st)
return(st);
if(st->data == n)
{
tmp=st;
st=st->next;
free(tmp);
return(st);
}
st->next=delete(st->next,n);
return(st);
1. Identify which one of the following declarations correctly defines a self referential data structure : a. struct class_1 { char name[31]; : struct class_2 *c; }; b. struct class_1 { char name[31]; : struct class_1 *c; }; c. struct class_1 { char name[31]; : struct class_1 c; }; 2. Identify the errors (if any) in the following C programs : a. The function add_list inserts a new node (nw) at the beginning of the list pointed to by the start pointer : add_list(list *start, list *nw) { if(start) start=nw; else nw->nxt=start; }
}
b. The function display_list (start pointer is passed as an argument) recursively displays all the nodes in the list : display_list(list *st) { if(st) return; printf(“\nData : “%d”, st->data); display_list(st->nxt); }
11.2 ORDERED LINKED LISTS
The process of creation of an ordered singly linked list (e.g. inserting a new element maintaining the increasing order) revolves around three basic operations, insertion at the beginning of the list, insertion in the middle or appending at the end. For example, suppose we would like to create a lexicographically ordered list with 4 nodes, having data values “bat”, “mat”, “cat” and “ant” respectively. Since “bat” is the first node to be inserted, this node address is assigned to start (which was initially set to NULL, indicating the list was empty).
To maintain the increasing order (lexicographically) the data for the next node “mat” is appended at the end of the list. To implement such an operation we use two pointers prev and curr, where curr pointer is used to traverse the list and prev follows it i.e. prev will point to the preceding node of the list pointed to by curr. After comparing new node information (“mat”) with the existing node information (“bat”), curr is made to point to the next node in the list (curr = curr->next) which is NULL here, i.e., the end of the list. Prior to that prev is assigned the old value of curr. Since the curr pointer now has NULL value , it indicates a new node is to be appended. This is achieved by attaching the newnode to the node pointed by prev i.e. prev->next now points to the address of the new node.
For the next insertion, the curr and prev are reset to start. To insert a new node information “cat” the previously mentioned steps are repeated. The comparison of new node information (“cat”) and current node information (“bat”) indicates that “cat” should appear after “bat” according to the lexicographical order. Hence, curr is made to point to next node that stores “mat” and the process of comparing new node and current node information continues. The prev pointer follows curr, and points to the first node of the list (“bat”).
The next comparison finds “cat” is to be placed before “mat” (pointed to by curr). Hence the new node information “cat” is to be inserted in between “bat” (pointed to by prev) and “mat” (pointed to by curr). To achieve the requisite insertion, prev->next is made to point to the newnode created to accommodate “cat” and newnode->next is made to point to the node pointed to by curr i.e. newnode->next=curr.
The next node to be inserted contains data “ant”, which is placed before the first element’s data in the list i.e. “bat”. Here the comparison with the first node indicates that the new node is to be inserted before “bat” that means the start needs to be redefined. This context is trapped by comparing the address of prev and curr, if both of them are stuck at start, it indicates insertion is to take place at the beginning.
void sort_insert(start,newnode)
list *start,*newnode;
{
list *prev,*curr;
if(!start)
start=newnode;
else
{
for(curr=start,prev=start;(curr) && strcmp(newnode->data,curr->data) >0 ;prev=curr,curr=curr->next);
if(prev == curr) /* insertion to be done at the beginning */
{
newnode->next=start;
start=newnode;
}
else
{
prev->next=newnode;
newnode->next=curr;
}
}
return;
}
No comments:
Post a Comment