Sunday, May 16, 2010

Implementing a list data structure using an array, in C


Long time since I interacted with C. I thought IIIT-A interviews are coming closer and they also have a coding test in which they ask to write programs, so I went off to revise data structures with C. I planned to study lists, linked lists, stacks, queues, trees and graphs and implement them all using C.
The first one on the target was lists. So I started off and wrote a lists demo program. I'm posting the program below. It may come handy to you if you are a student searching something for your assignment.
Compile it in GCC. You may also compile on Windoze but I haven't tested on Windoze.
The program allows to:
  1. Print all the values stored
  2. Insert a new value at specified position
  3. Insert a value at the end of the list(append)
  4. Delete a value at specified position
  5. Delete all occurences of a value from the list
  6. Find all occurences of an item
  7. Empty the list
I've also made the text colourful using the escape sequences for colours. Those \33[31m things are for colouring the text displayed while executing the program.

Here's the program.


#include <stdio.h>
#define SIZE 65536
#define ENDMARKER -65535

int data[SIZE];

int print_all();
int add(int pos, int datum);
int delete(int pos);
int append(int datum);
int delall(int datum);
int find(int datum);
int print(int pos);
int empty();

int main(){
int pos, datum;
int option;
data[0]=ENDMARKER;
printf("\n\33[36mWelcome to the list data structure demonstration program! The program starts with a list of integers(initially empty). Through this program's interface, you can insert items into the list at desired positions, or at the end; delete an item from the list from an specific position, or all occurences of an item from the list; find the position(s) of an item in the list; view all the items of the list; view an item stored at a particular position; or you may also empty the list.\n");
while(option!='9'){
printf("\n\33[32mMenu\n----\n");
printf("1. View all the items");
printf("\n2. Add an item at a given position");
printf("\n3. Add an item at the end of the list");
printf("\n4. Delete an item at a given position");
printf("\n5. Delete all occurences of an item value");
printf("\n6. Print an item at the given position");
printf("\n7. Find all the occurances of an item");
printf("\n8. Empty the list.");
printf("\n9. Exit\nEnter your choice and hit the enter key:");
scanf("%d",&option);
switch(option){
case 1:
print_all();
break;
case 2:
printf("\n\33[33mPlease enter the position where item should be inserted: ");
scanf("%d",&pos);
printf("Please enter the item value to be inserted: ");
scanf("%d",&datum);
add(pos, datum);
break;
case 3:
printf("\n\33[33mPlease enter the item value to be inserted at the end of the list: ");
scanf("%d",&datum);
append(datum);
break;

case 4:
printf("\n\33[33mPlease enter the position of the item to be deleted: ");
scanf("%d",&pos);
delete(pos);
break;
case 5:
printf("\n\33[33mPlease enter the item to be deleted from the list: ");
scanf("%d",&datum);
delall(datum);
break;
case 6:
printf("\n\33[33mPlease enter the position of the item whose value is to be printed: ");
scanf("%d",&pos);
print(pos);
break;
case 7:
printf("\n\33[33mPlease enter the item value whose position is to be found: ");
scanf("%d",&datum);
find(datum);
break;
case 8:
empty();
break;
case 9:
printf("\n\33[34mThank you for using this program. Have a nice time!\n\33[37m");
return(1);
break;
default:
printf("\n\33[31mInvalid use. Please retry.\n");
break;
}
}
printf("\33[37m");
return (0);
}

int num_items(){
int num=0;
int i;
for(i=0;data[i]!=ENDMARKER;i++);
return i;
}

int print_all(){
if(data[0]==ENDMARKER){
printf("\n\33[31mNo items could be found in the list.\nYou may insert some data first, before experimenting.\n");
return 0;
}
printf("\nFollowing items were found in the list:\n\n");
printf("\33[35mPosition\tItem\n");
printf("--------\t----\n");
int i;
for(i=0;data[i]!=ENDMARKER;i++){
printf("%8d\t%4d\n",i,data[i]);
}
printf("\n");
return 1;
}

int add(int pos, int datum){
if((pos>num_items()) || pos<0){
printf("\n\33[31mYou can't enter an item at this location because the list is full upto %d position. You can enter items from 0th position upto %dth position.\n",num_items(),num_items());
return (0);
}
data[num_items()+1]=ENDMARKER;
int i;
for(i=num_items();i>=pos;i--){
data[i]=data[i-1];
}
data[pos]=datum;
printf("\nThe item %d has been successfully inserted at the position %d.\nThe modified list is as follows.\n\n",datum,pos);
printf("\33[35mPosition\tItem\n");
printf("--------\t----\n");
for(i=0;data[i]!=ENDMARKER;i++){
printf("%8d\t%4d\n",i,data[i]);
}
printf("\n");
return 1;
}

int append(int datum){
data[num_items()+1]=ENDMARKER;
data[num_items()]=datum;
printf("\nThe item %d has been successfully appended to the list.\n The modified list is as follows.\n\n",datum);
printf("\33[35mPosition\tItem\n");
printf("--------\t----\n");
int i;
for(i=0;data[i]!=ENDMARKER;i++){
printf("%8d\t%4d\n",i,data[i]);
}
printf("\n");
return 1;
}

int delete(int pos){
if((pos>num_items()) || pos<0){
printf("\n\33[31mThat location doesn't hold any data value. Please enter a location that contains a value. Locations from 0 up to %d hold data values.\n",num_items());
return (0);
}
if(num_items()==0){
printf("\n\33[31mThe list is empty. No deletion possible.\n");
return 0;
}
int i;
for(i=pos;i<=num_items();i++){
data[i]=data[i+1];
}
data[num_items()]=ENDMARKER;
printf("\nThe item stored at the position %d has been successfully deleted.\n The modified list is as follows.\n\n",pos);
printf("\33[35mPosition\tItem\n");
printf("--------\t----\n");
for(i=0;data[i]!=ENDMARKER;i++){
printf("%8d\t%4d\n",i,data[i]);
}
printf("\n");
return 1;
}

int delall(int datum){
int i;
if(num_items()==0){
printf("\n\33[31mThe list is empty. No deletion possible.\n");
return 0;
}
int found=0;
for(i=0;i<=num_items();i++){
if(data[i]==datum){
found=1;
break;
}
}
if(found==0){
printf("\n\33[31mThe requested item wasn't found in the list. Deletion not possible.\n");
return (0);
}
for(i=0;data[i]!=ENDMARKER;i++){
if(data[i]==datum){
int j;
for(j=i;data[j+1]!=ENDMARKER;j++){
data[j]=data[j+1];
}
data[j]=ENDMARKER;
i--;
}
}
printf("\nAll the occurences of %d have been deleted from the list. The modified list is as follows:\n\n",datum); 
printf("\33[35mPosition\tItem\n");
printf("--------\t----\n");
for(i=0;data[i]!=ENDMARKER;i++){
printf("%8d\t%4d\n",i,data[i]);
}
printf("\n");
return 1;
}

int find(int datum){
int i;
if(num_items()==0){
printf("\n\33[31mThe list is empty.\n");
return 0;
}
int found=0;
for(i=0;i<=num_items();i++){
if(data[i]==datum){
found=1;
break;
}
}
if(found==0){
printf("\n\33[31mThe requested item wasn't found in the list.\n");
return (0);
}
printf("\n\33[35mPosition\tItem\n");
printf("--------\t----\n");
for(i=0;i<=num_items();i++){
if(data[i]==datum)printf("%8d\t%4d\n",i,data[i]);
}
return 1;
}

int print(int pos){
if(num_items()==0){
printf("\n\33[31mThe list is empty.\n");
return 0;
}
if(pos<0 || pos>=num_items()){
printf("\n\33[31mThats an invalid location.\n");
return 0;
}
printf("\n\33[35mPosition\tItem\n");
printf("--------\t----\n");
printf("%8d\t%4d\n",pos,data[pos]);
return 1;
}

int empty(){
if(num_items()==0){
printf("\n\33[31mThe list is already empty.\n");
return 0;
}
data[0]=ENDMARKER;
printf("\nThe list has been successfully emptied.\n");
return 1;
}

No comments: