Data Structures and algorithms using c .ppt

Abstract Data Type A collection of related data is known as an abstract data type (ADT) Data Structure = ADT + Collection of functions that operate on the ADT

Data Structure • Consist of the data structure definition and a collection of functions that operate on the struct – We will never access the struct directly!

• Separate what you can do with data from how it is represented • Other parts of the program interacts with data through provided operations according to their specifications • Implementation chooses how to represent data and implement its operations

Multiple Implementations • An ADT can have several implementations • Interface functions are the same • Application programs will not see any difference

ADT: Linear list • A sequence of elements • There is first and last element • Each element has previous and next – Nothing before first – Nothing after last

Why linked lists ? • A linked list is a dynamic data structure. – It can grow or shrink in size during the execution of a program. – It can be made just as long as required. – It does not waste memory space. • Linked lists provide flexibility in allowing the items to be rearranged efficiently. – Insert an element. – Delete an element.

• What we can do with a linear list? – Delete element – Insert element – Find element – Traverse list

Illustration: Insertion Item to be inserted X A B A B C C X

Illustration: Deletion C A B A B C

In essence ... • For insertion: – A record is created holding the new item. – The next pointer of the new record is set to link it to the item which is to follow it in the list. – The next pointer of the item which is to precede it must be modified to point to the new item. • For deletion: – The next pointer of the item immediately preceding the one to be deleted is altered, and made to point to the item following the deleted item.

Traverse: list  elements in order • get_first(list) - – returns first element if it exists • get_next(list) - – returns next element if it exists • Both functions return NULL otherwise • Calling get_next in a loop we will get one by one all elements of the list

How we can implement a list? • Array? • Search is easy (sequential or binary) • Traversal is easy: for(i = first; i <= last; ++i) process(a[i]); • Insert and delete is not easy – a good part of the array has to be moved! • Hard to guess the size of an array

A linked list implementation • Linked list is a chain of elements • Each element has data part and link part pointing to the next element

Main operations • Create list • Add node – beginning,middle or end • Delete node – beginning,middle or end • Find node • Traverse list

Conceptual Idea List implementation and the related functions Insert Delete Traverse

Example: Working with linked list • Consider the structure of a node as follows: struct stud { int roll; char name[25]; int age; struct stud *next; }; /* A user-defined data type called “node” */ typedef struct stud node; node *head;

Creating a List • To start with, we have to create a node (the first node), and make head point to it. head = (node *) malloc (sizeof (node)); head next age name roll

Contd. • If there are n number of nodes in the initial linked list: – Allocate n records, one by one. – Read in the fields of the records. – Modify the links of the records so that the chain is formed.

void create_list (node *list) { int k, n; node *p; printf (“n How many elements?”); scanf (“%d”, &n); list = (node *) malloc (sizeof (node)); p = list; for (k=0; k<n; k++) { scanf (“%d %s %d”, &p->roll, p->name, &p->age); p->next = (node *) malloc (sizeof (node)); p = p->next; } free (p->next); p->next = NULL; } To be called from the main() function as: node *head; ……. create_list (head);

Traversing the List • Once the linked list has been constructed and head points to the first node of the list, – Follow the pointers. – Display the contents of the nodes as they are traversed. – Stop when the next pointer points to NULL.

void display_list (node *list) { int k = 0; node *p; p = list; while (p != NULL) { printf (“Node %d: %d %s %d”, k, p->roll, p->name, p->age); k++; p = p->next; } }

Inserting a Node in the List • The problem is to insert a node before a specified node. – Specified means some value is given for the node (called key). – Here it may be roll. • Convention followed: – If the value of roll is given as negative, the node will be inserted at the end of the list.

• When a node is added at the beginning, – Only one next pointer needs to be modified. • head is made to point to the new node. • New node points to the previously first element. • When a node is added at the end, – Two next pointers need to be modified. • Last node now points to the new node. • New node points to NULL. • When a node is added in the middle, – Two next pointers need to be modified. • Previous node now points to the new node. • New node points to the next node.

void insert_node (node *list) { int k = 0, rno; node *p, *q, *new; new = (node *) malloc (sizeof (node)); scanf (“%d %s %d”, &new->roll, new->name, &new->age); printf (“nInsert before roll (-ve for end):”); scanf (“%d”, &rno); p = list; if (p->roll == rno) /* At the beginning */ { new->next = p; list = new; }

while ((p != NULL) && (p->roll != rno)) { q = p; p = p->next; } if (p == NULL) /* At the end */ { q->next = new; new->next = NULL; } if (p->roll == rno) /* In the middle */ { q->next = new; new->next = p; } } The pointers q and p always point to consecutive nodes.

Deleting an Item • Here also we are required to delete a specified node. – Say, the node whose roll field is given. • Here also three conditions arise: – Deleting the first node. – Deleting the last node. – Deleting an intermediate node.

void delete_node (node *list) { int rno; node *p, *q; printf (“nDelete for roll :”); scanf (“%d”, &rno); p = list; if (p->roll == rno) /* Delete the first element */ { list = p->next; free (p); }

while ((p != NULL) && (p->roll != rno)) { q = p; p = p->next; } if (p == NULL) /* Element not found */ printf (“nNo match :: deletion failed”); if (p->roll == rno) /* Delete any other element */ { q->next = p->next; free (p); } }

Doubly linked list A B C Assignment : Insertion, deletion in a doubly linked list

A First-in First-out (FIFO) List Also called a QUEUE In Out A C B A B

A Last-in First-out (LIFO) List In Out A B C C B Also called a STACK

More Stacks • A stack is a LIFO structure: Last In First Out

Basic Operations with Stacks • Push – Add and item • Overflow • Pop – Remove an item • Underflow • Stack Top – What’s on the Top • Could be empty

Push • Adds new data element to the top of the stack

• Removes a data element from the top of the stack Pop

• Checks the top element. Stack is not changed Stack Top

STACK push create pop isfull isempty

Assume:: stack contains integer elements void push (stack s, int element); /* Insert an element in the stack */ int pop (stack s); /* Remove and return the top element */ void create (stack s); /* Create a new stack */ int isempty (stack s); /* Check if stack is empty */ int isfull (stack s); /* Check if stack is full */

• We shall look into two different implementations of stack: – Using arrays – Using linked list

Stack Implementation Using Arrays • Basic idea. – Declare an array of fixed size (which determines the maximum size of the stack). – Keep a variable which always points to the “top” of the stack.

Declaration #define MAXSIZE 100 struct lifo { int st[MAXSIZE]; int top; }; typedef struct lifo stack;

Stack Creation void create (stack s) { s.top = 0; /* Points to last element pushed in */ }

Pushing an element onto the stack void push (stack s, int element) { if (s.top == (MAXSIZE-1)) { printf (“n Stack overflow”); break; } else { s.top ++; s.st [s.top] = element; }

Removing/Popping an element from the stack int pop (stack s) { if (s.top == 0) { printf (“n Stack underflow”); break; } else { return (s.st [s.top --]); } }

Checking for stack full / empty int isempty (stack s) { if (s.top == 0) return 1; else return (0); } int isfull (stack s) { if (s.top == (MAXSIZE – 1)) return 1; else return (0); }

Stack Implementation Using Linked List • Very similar to the linked list implementation discussed earlier. struct lifo { int element; struct lifo *next; }; typedef struct lifo stack; stack *top;

Contd. • Basic concept: – Insertion (push) and deletion (pop) operations take place at one end of the list only. – For stack creation / push operation • Required to call malloc function – How to check stack underflow? • Easy. Simply check if top points to NULL. – How to check overflow? • Check is malloc returns –1.

Sample Usage stack A, B; create (A); create (B); push (A, 10); push (A, 20); push (A, 30); push (B, 5); push (B, 25); push (B, 10); printf (“n%d %d %d”, pop(A), pop(A), pop(A)); printf (“n%d %d %d”, pop(B), pop(B), pop(B)); if (not isfull (A)) push (A, 50); if (not isempty (A)) k = pop (A); 30 20 10 10 25 5

• A queue is a FIFO structure: Fast In First Out Queues in Our Life

Basic Operations with Queues • Enqueue - Add an item to the end of queue • Overflow • Dequeue - Remove an item from the front • Could be empty • Queue Front - Who is first? • Could be empty • Queue End - Who is last? • Could be empty

Queue implementation with arrays

Queue will overgrow the array • Should we use VERY L A R G E ARRAYS?

Array implementation of queues 11 37 22 15 3 -7 1 queueAry maxsize count front rear front rear 7 4 1 5

Structure for a queue array struct intqueue { int *queueArray; int maxSize; int count; int front; int rear; };

Queue Implementation Using Linked List • Basic idea: – Create a linked list to which items would be added to one end and deleted from the other end. – Two pointers will be maintained: • One pointing to the beginning of the list (point from where elements will be deleted). • Another pointing to the end of the list (point where new elements will be inserted). Front Rear

Assume:: queue contains integer elements void enqueue (queue q, int element); /* Insert an element in the queue */ int dequeue (queue q); /* Remove an element from the queue */ queue *create (); /* Create a new queue */ int isempty (queue q); /* Check if queue is empty */ int size (queue q); /* Return the number of elements in queue */

Creating a queue front = NULL; rear = NULL;

Inserting an element in queue void enqueue (queue q, int x) { queue *ptr; ptr = (queue *) malloc (sizeof (queue)); if (rear == NULL) /* Queue is empty */ { front = ptr; rear = ptr; ptr->element = x; ptr->next = NULL; } else /* Queue is not empty */ { rear->next = ptr; ptr ->element = x; ptr->next = NULL; } }

Deleting an element from queue int dequeue (queue q) { queue *old; if (front == NULL) /* Queue is empty */ printf (“n Queue is empty”); else if (front == rear) /* Single element */ { k = front->element; free (front); front = rear = NULL; return (k); } else { k = front->element; old = front; front = front->next; free (old); return (k); } }

Checking if empty int isempty (queue q) { if (front == NULL) return (1); else return (0); }

Data Structures and algorithms using c .ppt

More Related Content

Similar to Data Structures and algorithms using c .ppt

Recently uploaded

Data Structures and algorithms using c .ppt