Linked Lists And Stack Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

There is a question in front of us that why do we need Data Structure. If we talk about the programming then the basic entity we are using is “data” and getting expected required output according the specification. Every program consists of statements and lager the program more complexity it will contain. To reduce its complexity, to reduce size of the program, to reduce redundancy of data, to reduce the usage of RAM memory, to reduce compilation time we need Data Structure. Different kinds of data structures such as Linked list, Stacks, Queues are suited to different programming application.

A Linked Lists are the method of organizing stored data in a computer's memory or on a storage medium based on the logical order of the data and not the physical order. All stored data records are assigned a physical address in memory that the computer uses to locate the information. A linked list arranges the data by logic rather than by physical address. A linked list is a complex data structure, especially useful in systems or applications programming. A linked list is comprised of a series of nodes, each node containing a data element, and a pointer to the next node i.e. each node contain the address of the next node.

A Stacks is an abstract data type and Data Structure which works on the principle of Last In First Out (LIFO) i.e. the element inserted last is at the top position and the deletion is done from the top position. Insertion of the elements is known as push while deletion from top of the stack is known as pop. Unlike that of array, the definition of stack provides for the insertion and deletion of items, so that a stack is a dynamic, constantly changing object.

A Queue in an ordered collection of items from which items may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end (called the rear of the queue). This makes the queue First In First Out (FIFO) data Structure. Queues provide services in computer science, transport and operations research where various entities such as data, objects, persons, or events are stored and held to be processed later.

DESCRIPTION OF THE ASSIGNMENT

In first part of the assignment is regarding the application of the stack ,where we need to convert the infix expression into post fix expression

The second part of our assignment is regarding the application of Linked List data Structure. The program is keep track of records regarding the Employee Information (Employee name, Employee code, Employee Salary) which is of string, integer, and integer data type respectively. This program consists of different function for input from users and for displaying the contents of the Linked List which consists of Employee name, Employee code and Employee salary. There are different functions used to insert the Employee values at the end and the start of the Linked List, function used to display the all Employee information and function used to remove any Employee information

PART A: stack (FLOWCHARTS)

1) flowchart of main function in stack

Infix to post fix

Screen shots of stack

It's the screen shot of the stack interface which is mentioning to enter the infix

This screenshot will explain about the stack by entering the values for infix

It's the output of stack after entering the values

Source code of stack

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include<math.h>

#include<string.h>

#define Blank ' '

#define Tab '\t'

#define MAX 50

long int pop ();

prec(char symbol );

white_space(char symbol);

push(long int symbol);

long int eval_post();

char infix[MAX], postfix[MAX];

long int stack[MAX];

int top;

infix_to_postfix();

void main()

{

long int value;

char choice='y';

while(choice == 'y')

{

top = 0;

printf("Enter infix : ");

fflush(stdin);

gets(infix);

infixtopostfix();

printf("Postfix : %s\n",postfix);

value=eval_post();

printf("Value of expression : %ld\n",value);

printf("Want to continue(y/n) : ");

scanf("%c",&choice);

}

}/*End of main()*/

infixtopostfix()

{

int i,p=0,type,precedence,len;

char next ;

stack[top]='#';

len=strlen(infix);

infix[len]='#';

for(i=0; infix[i]!='#';i++)

{

if( !white_space(infix[i]))

{

switch(infix[i])

{

case '(':

push(infix[i]);

break;

case ')':

while((next = pop()) != '(')

postfix[p++] = next;

break;

case '+':

case '-':

case '*':

case '/':

case '%':

case '^':

precedence = prec(infix[i]);

while(stack[top]!='#' && precedence<= prec(stack[top]))

postfix[p++] = pop();

push(infix[i]);

break;

default: /*if an operand comes */

postfix[p++] = infix[i];

}/*End of switch */

}/*End of if */

}/*End of for */

while(stack[top]!='#')

postfix[p++] = pop();

postfix[p] = '\0' ; /*End postfix with'\0' to make it a string*/

}/*End of infixtopostfix()*/

/* This function returns the precedence of the operator */

prec(char symbol )

{

switch(symbol)

{

case '(':

return 0;

case '+':

case '-':

return 1;

case '*':

case '/':

case '%':

return 2;

case '^':

return 3;

}/*End of switch*/

}/*End of prec()*/

push(long int symbol)

{

if(top > MAX)

{

printf("Stack overflow\n");

exit(1);

}

else

{

top=top+1;

stack[top] = symbol;

}

}/*End of push()*/

long int pop()

{

if (top == -1 )

{

printf("Stack underflow \n");

exit(2);

}

else

return (stack[top--]);

}/*End of pop()*/

white_space(char symbol)

{

if( symbol == Blank || symbol == Tab || symbol == '\0')

return 1;

else

return 0;

}/*End of white_space()*/

long int eval_post()

{

long int a,b,temp,result,len;

int i;

len=strlen(postfix);

postfix[len]='#';

for(i=0;postfix[i]!='#';i++)

{

if(postfix[i]<='9' && postfix[i]>='0')

push( postfix[i]-48 );

else

{

a=pop();

b=pop();

switch(postfix[i])

{

case '+':

temp=b+a; break;

case '-':

temp=b-a;break;

case '*':

temp=b*a;break;

case '/':

temp=b/a;break;

case '%':

temp=b%a;break;

case '^':

temp=pow(b,a);

}/*End of switch */

push(temp);

}/*End of else*/

}/*End of for */

result=pop();

return result;

}/*End of evalpost */

PART B: link list (FLOW CHART)

1) flowchart of initialization

2) flowchart of void display function

3) flowchart of the function void menu display

4) flowchart of adding employee node

5) flowchart of deletion of employee node

6)Flowchart of deletion of node by position

7) flowchart of deletion of node by employee ID

PART B: linklist (SOURCE CODE)

#include "stdio.h"

#include "string.h"

#include "stdlib.h"

#define TRUE 1

#define FALSE 0

#define MAX_EMP_NAME 25

#define MAX_EMP_ADDRESS 50

typedef enum{

POS_BEGIN=0,

POS_END

}POSITION;

typedef struct emp_node{

unsigned int emp_id;

unsigned int emp_salary;

unsigned int emp_ph_no;

unsigned char emp_name[MAX_EMP_NAME];

unsigned char emp_address[MAX_EMP_ADDRESS];

struct emp_node *next;

}EMP_NODE;

void Display_Menu(void);

void Add_Emp_Node(void);

void Display_List(void);

void Del_Emp_Node(void);

void Del_Node_ByPosition(POSITION pos);

void Del_Node_ByEmpId(unsigned int emp_id);

EMP_NODE *Get_Emp_Node(void);

EMP_NODE *head_node=NULL;

int main (void)

{

Display_Menu();

exit(1);

}

void Display_Menu(void)

{

unsigned int choice;

do

{

printf("\n Employee Database \n");

printf("----------------------------\n");

printf("\nPlease enter your choice\n");

printf("----------------------------\n");

printf("1. Add Record\n");

printf("2. Delete Record\n");

printf("3. Display Records\n");

printf("4. Exit\n");

printf("----------------------------\n");

scanf("%d",&choice);

switch(choice)

{

case 1: Add_Emp_Node();

break;

case 2: if(head_node != NULL)

{

Del_Emp_Node();

}

else

{

printf("Cannot delete from an empty list!!!!!\n");

}

break;

case 3: Display_List();

break;

case 4: printf("Exiting...\n");

exit(1);

default:printf("Invalid Choice!!!\n");

break;

}

}while(choice!=4);

}

void Add_Emp_Node(void)

{

EMP_NODE *emp_node,*temp_emp_node,*prev_emp_node;

emp_node = Get_Emp_Node();

if(NULL == emp_node)

{

printf("\nMemory Allocation Error!!!!!!!!!\n");

printf("Exiting...\n");

exit(1);

}

printf("Please enter Employee ID:");

scanf("%d",&emp_node->emp_id);

printf("Please enter Employee Salary:");

scanf("%d",&emp_node->emp_salary);

printf("Please enter Employee Ph No:");

scanf("%d",&emp_node->emp_ph_no);

printf("Please enter Employee Name:");

scanf("%s",&emp_node->emp_name);

printf("Please enter Employee Address:");

scanf("%s",&emp_node->emp_address);

emp_node->next=NULL;

if(NULL == head_node)

{

head_node = emp_node;

}

else

{

temp_emp_node = head_node;

prev_emp_node = NULL;

do

{

if(strcmp(temp_emp_node->emp_name,emp_node->emp_name)<=0)

{

prev_emp_node = temp_emp_node;

}

temp_emp_node = temp_emp_node->next;

}while(temp_emp_node!=NULL);

if(NULL == prev_emp_node)

{

emp_node->next = head_node;

head_node = emp_node;

}

else

{

emp_node->next = prev_emp_node->next;

prev_emp_node->next = emp_node;

}

}

}

void Del_Emp_Node(void)

{

unsigned int emp_id;

unsigned char choice_temp;

printf("\n-----Delete Record---------\n");

printf("1. Delete from beginning\n");

printf("2. Delete from end\n");

printf("3. Delete by employee id\n");

printf("-------------------------------\n");

scanf("%d",&choice_temp);

switch(choice_temp)

{

case 1:Del_Node_ByPosition(POS_BEGIN);

break;

case 2:Del_Node_ByPosition(POS_END);

break;

case 3:printf("\nEnter employee id to be deleted:");

scanf("%d",&emp_id);

Del_Node_ByEmpId(emp_id);

break;

default:printf("Invalid Choice!!!\n");

break;

}

}

void Del_Node_ByPosition(POSITION pos)

{

EMP_NODE *temp_emp_node,*prev_temp_node;

temp_emp_node = head_node;

if(temp_emp_node->next == NULL)

{

free(temp_emp_node);

head_node = NULL;

}

else if(POS_BEGIN == pos)

{

head_node = temp_emp_node->next;

free(temp_emp_node);

}

else

{

while(temp_emp_node->next!=NULL)

{

prev_temp_node = temp_emp_node;

temp_emp_node = temp_emp_node->next;

}

prev_temp_node->next = NULL;

free(temp_emp_node);

}

}

void Del_Node_ByEmpId(unsigned int emp_id)

{

EMP_NODE *temp_emp_node,*prev_temp_node;

unsigned char bFound = FALSE;

temp_emp_node = head_node;

prev_temp_node = NULL;

do

{

if(emp_id == temp_emp_node->emp_id)

{

bFound = TRUE;

break;

}

prev_temp_node = temp_emp_node;

temp_emp_node = temp_emp_node->next;

}while(temp_emp_node!=NULL);

if(bFound)

{

if(temp_emp_node!= head_node)

{

prev_temp_node->next = temp_emp_node->next;

}

free(temp_emp_node);

}

else

{

printf("\nNo match found for employee id\n");

}

}

void Display_List(void)

{

EMP_NODE *temp_emp_node;

temp_emp_node = head_node;

if(NULL == head_node)

{

printf("\nNo Records In The Database!!!!!!!!\n");

}

else

{

printf("\nEmployee Id| Name | Salary | Address | Phone No \n");

printf("--------------------------------------------------------------\n");

do

{

printf("\n%d\t\t%s\t%d\t\t%s\t%d\n",temp_emp_node->emp_id,temp_emp_node->emp_name,temp_emp_node->emp_salary,temp_emp_node->emp_address,temp_emp_node->emp_ph_no);

temp_emp_node = temp_emp_node->next;

}while(temp_emp_node!=NULL);

}

}

EMP_NODE *Get_Emp_Node(void)

{

EMP_NODE *temp_node;

temp_node = (EMP_NODE *) malloc(sizeof(EMP_NODE));

return(temp_node);

}

Linklist (SCREEN SHOT)

1)screen shot of main menu

It's the main interface of linklist which consist of add record,deletion,display and exit

This screen shot describes about the addition of records and displaying the records according to the specification

Screenshot of deleting records from the employee database ,options are also mention their in the database according to the specification

Screenshot of deletion of node by employee ID in this screenshot we had deleted the employee ID of 001

screenshot of validation

It's the screenshot of database with validation displays and menas that from an empty record data wont be displayed unless we are adding the data

It's the screenshot of the validation in deletetion of records defines that we wont be able to delete from an empty record

Limitations

* The details about employee database has been mentioned using c application.

* The employee details are limited

* There should be more better navigation controls and user interactivity.

Assumptions

* It is assumed that the host computer has a C Run time Environment.

* It is assumed that the user has basic computer knowledge required to operate a computer.

Further Development

* The employee system can be extended to be integrated with a bigger system.

* Administrator rights and user verification issues should be addressed.

* Complete details of the employee can be stored in a database.

Conclusion

Finally, I have come to realize the truth, which I had been ignoring. I know completely accept to the fact that C is truly one of the greatest programming languages of our times. C being versatile is also very much portable which gives it the added advantage.

All things, by standing I would like to summarize what this assignment and in whole the module has taught me. It has most important, taught me the concepts of POINTER Programming concepts.

All in all, it was a great learning experience.

REFERENCES:-

Ø LIPSCHUTZ, S. (2006). DATA STRUCTURES (2nd edition ed.). New Delhi: Tata Mcgraw-Hill.

Ø Roberts L.Kruse, B. p. (2001). Data Structures and program desine in C. New Delhi: Prentice-Hall of india.

Ø wirth, N. (February,2001). Algorithms+Data Structure=Programs. New Delhi: Prentice-Hall of india.

Ø Yedidyah Langsam, M. M. (June,2001). Data Structures using c And c++. (2nd. edition, Ed.) New Delhi: Prentice-Hall of india .

Ø http://www.opengroup.org/onlinepubs/009695399/basedefs/stdlib.h.html,30/03/08,3:40

Ø http://brickos.sourceforge.net/docs/APIs/html-c/stdlib_8h.html,29/03/08,9:45

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.