DSA using C – Sorting Techniques ”; Previous Next Overview Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. Most common orders are numerical or lexicographical order. Importance of sorting lies in the fact that data searching can be optimized to a very high level if data is stored in a sorted manner. Sorting is also used to represent data in more readable formats. Some of the examples of sorting in real life scenarios are following. Telephone Directory − Telephone directory keeps telephone no. of people sorted on their names. So that names can be searched. Dictionary − Dictionary keeps words in alphabetical order so that searching of any work becomes easy. Types of Sorting Following is the list of popular sorting algorithms and their comparison. Sr.No Technique & Description 1 Bubble Sort Bubble sort is simple to understand and implement algorithm but is very poor in performance. 2 Selection Sort Selection sort as name specifies use the technique to select the required item and prepare sorted array accordingly. 3 Insertion Sort Insertion sort is a variation of selection sort. 4 Shell Sort Shell sort is an efficient version of insertion sort. 5 Quick Sort Quick sort is a highly efficient sorting algorithm. Print Page Previous Next Advertisements ”;
Category: dsa Using C
DSA using C – Queue
DSA using C – Queue ”; Previous Next Overview Queue is kind of data structure similar to stack with primary difference that the first item inserted is the first item to be removed (FIFO – First In First Out) where stack is based on LIFO, Last In First Out principal. Queue Representation Basic Operations insert / enqueue − add an item to the rear of the queue. remove / dequeue − remove an item from the front of the queue. We”re going to implement Queue using array in this article. There is few more operations supported by queue which are following. Peek − get the element at front of the queue. isFull − check if queue is full. isEmpty − check if queue is empty. Insert / Enqueue Operation Whenever an element is inserted into queue, queue increments the rear index for later use and stores that element at the rear end of the storage. If rear end reaches to the last index and it is wrapped to the bottom location. Such an arrangement is called wrap around and such queue is circular queue. This method is also termed as enqueue operation. void insert(int data){ if(!isFull()){ if(rear == MAX-1){ rear = -1; } intArray[++rear] = data; itemCount++; } } Remove / Dequeue Operation Whenever an element is to be removed from queue, queue get the element using front index and increments the front index. As a wrap around arrangement, if front index is more than array”s max index, it is set to 0. int removeData(){ int data = intArray[front++]; if(front == MAX){ front = 0; } itemCount–; return data; } Example QueueDemo.c Live Demo #include <stdio.h> #include <string.h> #include <stdlib.h> #include <stdbool.h> #define MAX 6 int intArray[MAX]; int front = 0; int rear = -1; int itemCount = 0; int peek(){ return intArray[front]; } bool isEmpty(){ return itemCount == 0; } bool isFull(){ return itemCount == MAX; } int size(){ return itemCount; } void insert(int data){ if(!isFull()){ if(rear == MAX-1){ rear = -1; } intArray[++rear] = data; itemCount++; } } int removeData(){ int data = intArray[front++]; if(front == MAX){ front = 0; } itemCount–; return data; } int main() { /* insert 5 items */ insert(3); insert(5); insert(9); insert(1); insert(12); // front : 0 // rear : 4 // —————— // index : 0 1 2 3 4 // —————— // queue : 3 5 9 1 12 insert(15); // front : 0 // rear : 5 // ——————— // index : 0 1 2 3 4 5 // ——————— // queue : 3 5 9 1 12 15 if(isFull()){ printf(“Queue is full!n”); } // remove one item int num = removeData(); printf(“Element removed: %dn”,num); // front : 1 // rear : 5 // ——————- // index : 1 2 3 4 5 // ——————- // queue : 5 9 1 12 15 // insert more items insert(16); // front : 1 // rear : -1 // ———————- // index : 0 1 2 3 4 5 // ———————- // queue : 16 5 9 1 12 15 // As queue is full, elements will not be inserted. insert(17); insert(18); // ———————- // index : 0 1 2 3 4 5 // ———————- // queue : 16 5 9 1 12 15 printf(“Element at front: %dn”,peek()); printf(“———————-n”); printf(“index : 5 4 3 2 1 0n”); printf(“———————-n”); printf(“Queue: “); while(!isEmpty()){ int n = removeData(); printf(“%d “,n); } } Output If we compile and run the above program then it would produce following output − Queue is full! Element removed: 3 Element at front: 5 ———————- index : 5 4 3 2 1 0 ———————- Queue: 5 9 1 12 15 16 Print Page Previous Next Advertisements ”;
DSA using C – Useful Resources ”; Previous Next The following resources contain additional information on DSA using C. Please use them to get more in-depth knowledge on this. Useful Links on DSA using C Wiki Page for Data Structures – Check out data structures in a very generic way Data Structures – A very good article on Data Structures Compile and Execute C Online – High end server giving opportunity to compile and execute C progams online. Notes on K&R2 – A great companion to K&R2 Programming in C – Literature, History and Culture of C Programming Language. Learn GNU Debugger – GDB – A debugging tool to debug errors in C and C++ programs. Useful Books on DSA using C To enlist your site on this page, please drop an email to [email protected] Print Page Previous Next Advertisements ”;
DSA using C – Stack
DSA using C – Stack ”; Previous Next Overview Stack is kind of data structure which allows operations on data only at one end. It allows access to the last inserted data only. Stack is also called LIFO (Last In First Out) data structure and Push and Pop operations are related in such a way that only last item pushed (added to stack) can be popped (removed from the stack). Stack Representation We”re going to implement Stack using array in this article. Basic Operations Following are two primary operations of a stack which are following. Push − push an element at the top of the stack. Pop − pop an element from the top of the stack. There is few more operations supported by stack which are following. Peek − get the top element of the stack. isFull − check if stack is full. isEmpty − check if stack is empty. Push Operation Whenever an element is pushed into stack, stack stores that element at the top of the storage and increments the top index for later use. If storage is full then an error message is usually shown. // Operation : Push // push item on the top of the stack void push(int data) { if(!isFull()){ // increment top by 1 and insert data intArray[++top] = data; } else { printf(“Cannot add data. Stack is full.n”); } } Pop Operation Whenever an element is to be popped from stack, stack retrives the element from the top of the storage and decrements the top index for later use. // Operation : Pop // pop item from the top of the stack int pop() { //retrieve data and decrement the top by 1 return intArray[top–]; } Example StackDemo.c Live Demo #include <stdio.h> #include <string.h> #include <stdlib.h> #include <stdbool.h> // size of the stack int size = 8; // stack storage int intArray[8]; // top of the stack int top = -1; // Operation : Pop // pop item from the top of the stack int pop() { //retrieve data and decrement the top by 1 return intArray[top–]; } // Operation : Peek // view the data at top of the stack int peek() { //retrieve data from the top return intArray[top]; } //Operation : isFull //return true if stack is full bool isFull(){ return (top == size-1); } // Operation : isEmpty // return true if stack is empty bool isEmpty(){ return (top == -1); } // Operation : Push // push item on the top of the stack void push(int data) { if(!isFull()){ // increment top by 1 and insert data intArray[++top] = data; } else { printf(“Cannot add data. Stack is full.n”); } } main() { // push items on to the stack push(3); push(5); push(9); push(1); push(12); push(15); printf(“Element at top of the stack: %dn” ,peek()); printf(“Elements: n”); // print stack data while(!isEmpty()){ int data = pop(); printf(“%dn”,data); } printf(“Stack full: %sn” , isFull()?”true”:”false”); printf(“Stack empty: %sn” , isEmpty()?”true”:”false”); } Output If we compile and run the above program then it would produce following output − Element at top of the stack: 15 Elements: 15 12 1 9 5 3 Stack full: false Stack empty: true Print Page Previous Next Advertisements ”;
DSA using C – Linked List
DSA using C – Linked List ”; Previous Next Overview Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list the second most used data structure after array. Following are important terms to understand the concepts of Linked List. Link − Each Link of a linked list can store a data called an element. Next − Each Link of a linked list contain a link to next link called Next. LinkedList − A LinkedList contains the connection link to the first Link called First. Linked List Representation As per above shown illustration, following are the important points to be considered. LinkedList contains an link element called first. Each Link carries a data field(s) and a Link Field called next. Each Link is linked with its next link using its next link. Last Link carries a Link as null to mark the end of the list. Types of Linked List Following are the various flavours of linked list. Simple Linked List − Item Navigation is forward only. Doubly Linked List − Items can be navigated forward and backward way. Circular Linked List − Last item contains link of the first element as next and and first element has link to last element as prev. Basic Operations Following are the basic operations supported by a list. Insertion − add an element at the beginning of the list. Deletion − delete an element at the beginning of the list. Display − displaying complete list. Search − search an element using given key. Delete − delete an element using given key. Insertion Operation Insertion is a three step process − Create a new Link with provided data. Point New Link to old First Link. Point First Link to this New Link. //insert link at the first location void insertFirst(int key, int data){ //create a link struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; //point it to old first node link->next = head; //point first to new first node head = link; } Deletion Operation Deletion is a two step process − Get the Link pointed by First Link as Temp Link. Point First Link to Temp Link”s Next Link. //delete first item struct node* deleteFirst(){ //save reference to first link struct node *tempLink = head; //mark next to first link as first head = head->next; //return the deleted link return tempLink; } Navigation Operation Navigation is a recursive step process and is basis of many operations like search, delete etc. − Get the Link pointed by First Link as Current Link. Check if Current Link is not null and display it. Point Current Link to Next Link of Current Link and move to above step. Note − //display the list void printList(){ struct node *ptr = head; printf(“n[ “); //start from the beginning while(ptr != NULL){ printf(“(%d,%d) “,ptr->key,ptr->data); ptr = ptr->next; } printf(” ]”); } Advanced Operations Following are the advanced operations specified for a list. Sort − sorting a list based on a particular order. Reverse − reversing a linked list. Sort Operation We”ve used bubble sort to sort a list. void sort(){ int i, j, k, tempKey, tempData ; struct node *current; struct node *next; int size = length(); k = size ; for ( i = 0 ; i < size – 1 ; i++, k– ) { current = head ; next = head->next ; for ( j = 1 ; j < k ; j++ ) { if ( current->data > next->data ) { tempData = current->data ; current->data = next->data; next->data = tempData ; tempKey = current->key; current->key = next->key; next->key = tempKey; } current = current->next; next = next->next; } } } Reverse Operation Following code demonstrate reversing a single linked list. void reverse(struct node** head_ref) { struct node* prev = NULL; struct node* current = *head_ref; struct node* next; while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } *head_ref = prev; } Example LinkedListDemo.c Live Demo #include <stdio.h> #include <string.h> #include <stdlib.h> #include <stdbool.h> struct node { int data; int key; struct node *next; }; struct node *head = NULL; struct node *current = NULL; //display the list void printList(){ struct node *ptr = head; printf(“n[ “); //start from the beginning while(ptr != NULL){ printf(“(%d,%d) “,ptr->key,ptr->data); ptr = ptr->next; } printf(” ]”); } //insert link at the first location void insertFirst(int key, int data){ //create a link struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; //point it to old first node link->next = head; //point first to new first node head = link; } //delete first item struct node* deleteFirst(){ //save reference to first link struct node *tempLink = head; //mark next to first link as first head = head->next; //return the deleted link return tempLink; } //is list empty bool isEmpty(){ return head == NULL; } int length(){ int length = 0; struct node *current; for(current = head; current!=NULL; current = current->next){ length++; } return length; } //find a link with given key struct node* find(int key){ //start from the first link struct node* current = head; //if list is empty if(head == NULL){ return NULL; } //navigate through list while(current->key != key){ //if it is last node if(current->next == NULL){ return
DSA using C – Circular Linked List ”; Previous Next Overview Circular Linked List is a variation of Linked list in which first element points to last element and last element points to first element. Both Singly Linked List and Doubly Linked List can be made into as circular linked list. Singly Linked List as Circular Doubly Linked List as Circular As per above shown illustrations, following are the important points to be considered. Last Link”next points to first link of the list in both cases of singly as well as doubly linked list. First Link”s prev points to the last of the list in case of doubly linked list. Basic Operations Following are the important operations supported by a circular list. insert − insert an element in the start of the list. delete − insert an element from the start of the list. display − display the list. Length Operation Following code demonstrate insertion operation at in a circular linked list based on single linked list. //insert link at the first location void insertFirst(int key, int data){ //create a link struct node *link = (struct node*) malloc(sizeof(struct node)); link->key =key; link->data=data; if (isEmpty()) { head = link; head->next = head; } else { //point it to old first node link->next = head; //point first to new first node head = link; } } Deletion Operation Following code demonstrate deletion operation at in a circular linked list based on single linked list. //delete first item struct node * deleteFirst(){ //save reference to first link struct node *tempLink = head; if(head->next == head){ head = NULL; return tempLink; } //mark next to first link as first head = head->next; //return the deleted link return tempLink; } Display List Operation Following code demonstrate display list operation in a circular linked list. //display the list void printList(){ struct node *ptr = head; printf(“n[ “); //start from the beginning if(head != NULL){ while(ptr->next != ptr){ printf(“(%d,%d) “,ptr->key,ptr->data); ptr = ptr->next; } } printf(” ]”); } Example DoublyLinkedListDemo.c Live Demo #include <stdio.h> #include <string.h> #include <stdlib.h> #include <stdbool.h> struct node { int data; int key; struct node *next; }; struct node *head = NULL; struct node *current = NULL; bool isEmpty(){ return head == NULL; } int length(){ int length = 0; //if list is empty if(head == NULL){ return 0; } current = head->next; while(current != head){ length++; current = current->next; } return length; } //insert link at the first location void insertFirst(int key, int data){ //create a link struct node *link = (struct node*) malloc(sizeof(struct node)); link->key =key; link->data=data; if (isEmpty()) { head = link; head->next = head; } else { //point it to old first node link->next = head; //point first to new first node head = link; } } //delete first item struct node * deleteFirst(){ //save reference to first link struct node *tempLink = head; if(head->next == head){ head = NULL; return tempLink; } //mark next to first link as first head = head->next; //return the deleted link return tempLink; } //display the list void printList(){ struct node *ptr = head; printf(“n[ “); //start from the beginning if(head != NULL){ while(ptr->next != ptr){ printf(“(%d,%d) “,ptr->key,ptr->data); ptr = ptr->next; } } printf(” ]”); } main() { insertFirst(1,10); insertFirst(2,20); insertFirst(3,30); insertFirst(4,1); insertFirst(5,40); insertFirst(6,56); printf(“Original List: “); //print list printList(); while(!isEmpty()){ struct node *temp = deleteFirst(); printf(“nDeleted value:”); printf(“(%d,%d) “,temp->key,temp->data); } printf(“nList after deleting all items: “); printList(); } Output If we compile and run the above program then it would produce following output − Original List: [ (6,56) (5,40) (4,1) (3,30) (2,20) ] Deleted value:(6,56) Deleted value:(5,40) Deleted value:(4,1) Deleted value:(3,30) Deleted value:(2,20) Deleted value:(1,10) List after deleting all items: [ ] Print Page Previous Next Advertisements ”;
DSA using C – Parsing Expressions ”; Previous Next Ordinary arithmetic expressions like 2*(3*4) are easier for human mind to parse but for an algorithm it would be pretty difficult to parse such an expression. To ease this difficulty, an arithmetic expression can be parsed by an algorithm using a two step approach. Transform the provided arithmetic expression to postfix notation. Evaluate the postfix notation. Infix Notation Normal arithmetic expression follows Infix Notation in which operator is in between the operands. For example A+B here A is first operand, B is second operand and + is the operator acting on the two operands. Postfix Notation Postfix notation varies from normal arithmetic expression or infix notation in a way that the operator follows the operands. For example, consider the following examples. Sr. No. Infix Notation Postfix Notation 1 A+B AB+ 2 (A+B)*C AB+C* 3 A*(B+C) ABC+* 4 A/B+C/D AB/CD/+ 5 (A+B)*(C+D) AB+CD+* 6 ((A+B)*C)-D AB+C*D- Infix to PostFix Conversion Before looking into the way to translate Infix to postfix notation, we need to consider following basics of infix expression evaluation. Evaluation of the infix expression starts from left to right. Keep precedence in mind, for example * has higher precedence over +. For example 2+3*4 = 2+12. 2+3*4 = 14. Override precedence using brackets, For example (2+3)*4 = 5*4. (2+3)*4= 20. Now let us transform a simple infix expression A+B*C into a postfix expression manually. Sr.No Character read Infix Expressed parsed so far Postfix expression developed so far Remarks 1 A A A 2 + A+ A 3 B A+B AB 4 * A+B* AB + can not be copied as * has higher precedence. 5 C A+B*C ABC 6 A+B*C ABC* copy * as two operands are there B and C 7 A+B*C ABC*+ copy + as two operands are there BC and A Now let us transform the above infix expression A+B*C into a postfix expression using stack. Sr.No Character read Infix Expressed parsed so far Postfix expression developed so far Stack Contents Remarks 1 A A A 2 + A+ A + push + operator in a stack. 3 B A+B AB + 4 * A+B* AB +* Precedence of operator * is higher than +. push * operator in the stack. Otherwise, + would pop up. 5 C A+B*C ABC +* 6 A+B*C ABC* + No more operand, pop the * operator. 7 A+B*C ABC*+ Pop the + operator. Now let us see another example, by transforming infix expression A*(B+C) into a postfix expression using stack. Sr.No Character read Infix Expressed parsed so far Postfix expression developed so far Stack Contents Remarks 1 A A A 2 * A* A * push * operator in a stack. 3 ( A*( A *( push ( in the stack. 4 B A*(B AB *( 5 + A*(B+ AB *(+ push + in the stack. 6 C A*(B+C ABC *(+ 7 ) A*(B+C) ABC+ *( Pop the + operator. 8 A*(B+C) ABC+ * Pop the ( operator. 9 A*(B+C) ABC+* Pop the rest of the operator(s). Example Now we”ll demonstrate the use of stack to convert infix expression to postfix expression and then evaluate the postfix expression. Live Demo #include<stdio.h> #include<string.h> //char stack char stack[25]; int top=-1; void push(char item) { stack[++top]=item; } char pop() { return stack[top–]; } //returns precedence of operators int precedence(char symbol) { switch(symbol) { case ”+”: case ”-”: return 2; break; case ”*”: case ”/”: return 3; break; case ”^”: return 4; break; case ”(”: case ”)”: case ”#”: return 1; break; } } //check whether the symbol is operator? int isOperator(char symbol) { switch(symbol){ case ”+”: case ”-”: case ”*”: case ”/”: case ”^”: case ”(”: case ”)”: return 1; break; default: return 0; } } //converts infix expression to postfix void convert(char infix[],char postfix[]){ int i,symbol,j=0; stack[++top]=”#”; for(i=0;i<strlen(infix);i++){ symbol=infix[i]; if(isOperator(symbol)==0){ postfix[j]=symbol; j++; } else { if(symbol==”(”){ push(symbol); } else { if(symbol==”)”){ while(stack[top]!=”(”){ postfix[j]=pop(); j++; } pop();//pop out (. } else {
DSA using C – Algorithms
DSA using C – Algorithms ”; Previous Next Algorithm Algorithm is a step by step procedure, which defines a set of instructions to be executed in certain order to get the desired output. In term of data structures, following are the categories of algorithms. Search − Algorithms to search an item in a datastrucure. Sort − Algorithms to sort items in certain order Insert − Algorithm to insert item in a datastructure Update − Algorithm to update an existing item in a data structure Delete − Algorithm to delete an existing item from a data structure Algorithm analysis Algorithm analysis deals with the execution time or running time of various operations of a data structure. Running time of an operation can be defined as no. of computer instructions executed per operation. As exact running time of any operation varies from one computer to another computer, we usually analyze the running time of any operation as some function of n, where n is the no. of items processed in that operation in a datastructure. Asymptotic analysis Asymptotic analysis refers to computing the running time of any operation in mathematical units of computation. For example, running time of one operation is computed as f(n) and of another operation as g(n2). Which means first operation running time will increase linearly with the increase in n and running time of second operation will increase exponentially when n increases. Similarly the running time of both operations will be nearly same if n is significantly small. Asymptotic Notations Following are commonly used asymptotic notations used in calculating running time complexity of an algorithm. Ο Notation Ω Notation θ Notation Big Oh Notation, Ο The Ο(n) is the formal way to express the upper bound of an algorithm”s running time. It measures the worst case time complexity or longest amount of time an algorithm can possibly take to complete. For example, for a function f(n) Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. } Big Oh notation is used to simplify functions. For example, we can replace a specific functional equation 7nlogn + n – 1 with Ο(f(nlogn)). Consider the scenario as follows − 7nlogn +n – 1 ≤ 7nlogn + n 7nlogn +n – 1 ≤ 7nlogn + nlogn for n ≥ 2 so that logn ≥ 1 7nlogn +n – 1 ≤ 8nlogn It demonstrates that f(n) = 7nlogn +n – 1 is within the range of outout of O(nlogn) using constants c = 8 and n0 = 2. Omega Notation, Ω The Ω(n) is the formal way to express the lower bound of an algorithm”s running time. It measures the best case time complexity or best amount of time an algorithm can possibly take to complete. For example, for a function f(n) Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. } Theta Notation, θ The θ(n) is the formal way to express both the lower bound and upper bound of an algorithm”s running time. It is represented as following. θ(f(n)) = { g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. } Print Page Previous Next Advertisements ”;
DSA using C – Overview
DSA using C – Overview ”; Previous Next What is a Data Structure? Data Structure is a way to organized data in such a way that it can be used efficiently. Following terms are foundation terms of a data structure. Interface − Each data structure has an interface. Interface represents the set of operations that a datastructure supports.An interface only provides the list of supported operations, type of parameters they can accept and return type of these operations. Implementation − Implementation provides the internal representation of a data structure. Implementation also provides the definition of the algorithms used in the operations of the data structure. Characteristics of a Data Structure Correctness − Data Structure implementation should implement its interface correctly. Time Complexity − Running time or execution time of operations of data structure must be as small as possible. Space Complexity − Memory usage of a data structure operation should be as little as possible. Need for Data Structure As applications are getting complex and data rich, there are three common problems applications face now-a-days. Data Search − Consider an inventory of 1 million(106) items of a store. If application is to search an item. It has to search item in 1 million(106) items every time slowing down the search. As data grows, search will become slower. Processor speed − Processor speed although being very high, falls limited if data grows to billion records. Multiple requests − As thousands of users can search data simultaneously on a web server,even very fast server fails while searching the data. To solve above problems, data structures come to rescue. Data can be organized in a data structure in such a way that all items may not be required to be search and required data can be searched almost instantly. Execution Time Cases There are three cases which are usual used to compare various data structure”s execution time in relative manner. Worst Case − This is the scenario where a particular data structure operation takes maximum time it can take. If a operation”s worst case time is ƒ(n) then this operation will not take time more than ƒ(n) time where ƒ(n) represents function of n. Average Case − This is the scenario depicting the average execution time of an operation of a data structure. If a operation takes ƒ(n) time in execution then m operations will take mƒ(n) time. Best Case − This is the scenario depicting the least possible execution time of an operation of a data structure. If a operation takes ƒ(n) time in execution then actual operation may take time as random number which would be maximum as ƒ(n). Print Page Previous Next Advertisements ”;
DSA using C – Search Techniques ”; Previous Next Search refers to locating a desired element of specified properties in a collection of items. We are going to start our discussion using following commonly used and simple search algorithms. Sr.No Technique & Description 1 Linear Search Linear search searches all items and its worst execution time is n where n is the number of items. 2 Binary Search Binary search requires items to be in sorted order but its worst execution time is constant and is much faster than linear search. 3 Interpolation Search Interpolation search requires items to be in sorted order but its worst execution time is O(n) where n is the number of items and it is much faster than linear search. Print Page Previous Next Advertisements ”;