| Introduction to Data structures |
|
| Introduction |
|
| Software engineering is the study of ways in which to create large and complex computer applications and that generally involve many programmers and designers. At the heart of software engineering is with the overall design of the applications and on the creation of a design that is based on the needs and requirements of end users. While software engineering involves the full life cycle of a software project, is includes many different components - specification, requirements gathering, design, verification, coding, testing,quality assurance, user acceptance testing, production, and ongoing maintenance. |
|
| Having an in-depth understanding on every component of software engineering is not mandatory, however, it is important to understand that the subject of data structures and algorithms is concerned with the coding phase. The use of data structures and algorithms is the nuts-and-blots used by programmers to store and manipulate data. |
|
|
|
| Data Structures & Algorithms - Defined |
|
| A data structure is an arrangement of data in a computer's memory or even disk storage. An example of several common data structures are arrays, linked lists, queues, stacks,binary trees, and hash tables. Algorithms, on the other hand, are used to manipulate the data contained in these data structures as in searching and sorting. |
| Many algorithms apply directly to a specific data structures. When working with certain data structures you need to know how to insert new data, search for a specified item, and deleting a specific item. |
|
| Commonly used algorithms include are useful for: |
- Searching for a particular data item (or record).
- Sorting the data. There are many ways to sort data. Simple sorting, Advanced sorting
- Iterating through all the items in a data structure. (Visiting each item in turn so as to display it or perform some other action on these items)
|
|
| Characteristics of Data Structures |
|
| Data Structure | Pros | Cons |
| Array | Quick inserts
Fast access if index known | Slow search
Slow deletes
Fixed size |
| Ordered Array | Faster search than unsorted array | Slow inserts
Slow deletes
Fixed size |
| Stack | Last-in, first-out acces | Slow access to other items |
| Queue | First-in, first-out access | Slow access to other items |
| Linked List | Quick inserts
Quick deletes | Slow search |
| Binary Tree | Quick search
Quick inserts
Quick deletes
(If the tree remains balanced) | Deletion algorithm is complex |
| Heap | Quick inserts
Quick deletes
Access to largest item | Slow access to other items |
| Graph | Best models real-world situations | Some algorithms are slow and very complex |
|
|
|
|
|
| Pointer |
|
| Introduction to Pointer |
|
| To understand pointers, you need a basic knowledge of how your computer stores infor-mation in memory. The following is a somewhat simplified account of PC memory storage.Pointers are so commonly used as references that sometimes people use the word “pointer” to refer to references in general; however, more properly it only applies to data structures whose interface explicitly allows it to be manipulated as a memory address. |
|
- Pointers provide an indirect method of accessing variables. The reason why pointers are hard to understand is because they aren't taught in a manner that is understandable. Think for a minute about a typical textbook. It will usually have a table of contents, some chapters, and an index. What if you were looking in the Weiss book for information on printf? You'd look at the index for printf. The index will tell you where information on printf is located within the book. Conceptually, this is how pointers work! Re-read this analogy if you didn't get it the first time. This is important. You must understand that pointers are indirect references.
- Because the conceptual view of a pointer is important in the understandability pointers, let's try to put this in terms that are more simple.
- Let's say you need some information about a secret party that's happening later in the day, but you only have one friend (Yes, I know that's sad). And your friend's name is "Pointer Joe." However, he isn't very helpful directly because he doesn't really know anything about the party, but he tells you that he knows someone with that secret information. So any info you want, Pointer Joe will just get from his friend. This is approximately how a pointer works.
- You may be wondering, what is the point of this (no pun intended)? Why don't I just make all variables without the use of pointers? It's because sometimes you can't. What if you needed an array of ints, but didn't know the size of the array before hand? What if you needed a string, but it grew dynamically as the program ran? What if you need variables that are persistent through function use without declaring them global (remember the swap function)? They are all solved through the use of pointers. Pointers are also essential in creating larger custom data structures, such as linked lists.
|
|
|
|
| So now that you understand how pointers work, let's define them a little better. |
|
- A pointer when declared is just a reference. DECLARING A POINTER DOES NOT CREATE ANY SPACE FOR THE POINTER TO POINT TO. We will tackle this dynamic memory allocation issue later.
- A pointer is a reference to an area of memory in the heap. The heap is a dynamically allocated area of memory when the program runs.
|
|
|
|
|
| Pointer |
|
| Declaration & Syntax |
|
| Pointers are declared by using the * in front of the variable identifier. For example: |
int *ip;
float *fp = NULL; |
|
| This declares a pointer, ip, to an integer. Let's say we want ip to point to an integer. The second line declares a pointer to a float, but initializes the pointer to point to the NULL pointer. The NULL pointer points to a place in memory that cannot be accessed. NULL is useful when checking for error conditions and many functions return NULL if they fail. |
|
int x = 5;
int *ip;
ip = &x; |
|
| We first encountered the & operator first in the I/O section. The & operator is to specify the address-of x. Thus, the pointer, ip is pointing to x by assigning the address of x. This is important. You must understand this concept. |
|
| This brings up the question, if pointers contain addresses, then how do I get the actual value of what the pointer is pointing to? This is solved through the * operator. The * dereferences the pointer to the value. So, |
| printf("%d %d\n", x, *ip); |
| would print 5 5 to the screen. |
|
| There is a critical difference between a dereference and a pointer declaration: |
int x = 0, y = 5, *ip = &y;
x = *ip; |
|
| The statement int *ip = &y; is different than x = *ip;. The first statement does not dereference, the * signifies to create a pointer to an int. The second statement uses a dereference. |
| Remember the swap function? We can now simulate call by reference using pointers. Here is a modified version of the swap function using pointers: |
void swap(int *x, int *y) {
int tmp;
tmp = *x;
*x = *y;
*y = tmp;
}
int main() {
int a = 2, b = 3;
swap(&a, &b);
return EXIT_SUCCESS;
} |
|
| This snip of swapping code works. When you call swap, you must give the address-of a and b, because swap is expecting a pointer. Why does this work? It's because you are giving the address-of the variables. This memory does not "go away" or get "popped off" after the function swap ends. The changes within swap change the values located in those memory addresses. |
|
|
|
|
| Pointer |
|
| Working with Pointers |
|
| Imagine that we have an int called i. Its address could be represented by the symbol &i. If the pointer is to be stored as a variable, it should be stored like this. |
| int *pi = &i; |
|
| int * is the notation for a pointer to an int. & is the operator which returns the address of its argument. When it is used, as in &i we say it is referencing i. |
|
| The opposite operator, which gives the value at the end of the pointer is *. An example of use, known as de-referencing pi, would be |
| i = *pi; |
|
| Take care not to confuse the many uses of the * sign; Multiplication, pointer declaration and pointer de-referencing. |
| This is a very confusing subject, so let us illustrate it with an example. The following function fiddle takes two arguments, x is an int while y is a pointer to int. It changes both values. |
|
fiddle(int x, int *y)
{ printf(" Starting fiddle: x = %d, y = %d\n", x, *y);
x ++;
(*y)++;
printf("Finishing fiddle: x = %d, y = %d\n", x, *y);
} |
|
| since y is a pointer, we must de-reference it before incrementing its value. |
| A very simple program to call this function might be as follows. |
main();
{ int i = 0;
int j = 0;
printf(" Starting main : i = %d, j = %d\n", i, j);
printf("Calling fiddle now\n");.
fiddle(i, &j);
printf("Returned from fiddle\n");
printf("Finishing main : i = %d, j = %d\n", i, j);
} |
|
| Note here how a pointer to int is created using the & operator within the call fiddle(i, &j);. |
| The result of running the program will look like this. |
Starting main : i = 0 ,j = 0
Calling fiddle now
Starting fiddle: x = 0, y = 0
Finishing fiddle: x = 1, y = 1
Returned from fiddle
Finishing main : i = 0, j = 1 |
|
| After the return from fiddle the value of i is unchanged while j, which was passed as a pointer, has changed. |
| To summarise, if you wish to use arguments to modify the value of variables from a function, these arguments must be passed as pointers, and de-referenced within the function. |
|
| Where the value of an argument isn't modified, the value can be passed without any worries about pointers. |
|
|
|
|
| Array |
|
| Introduction to Arrays |
|
| An array is a data structure used to process multiple elements with the same data type when a number of such elements are known. You would use an array when, for example, you want to find out the average grades of a class based on the grades of 50 students in the class. Here you cannot define 50 variables and add their grades. This is not practical. Using an array, you can store grades of 50 students in one entity, say grades, and you can access each entity by using subscript as grades[1], grades[2]. Thus you have to define the array of grades of the float data type and a size of 50. An array is a composite data structure; that means it had to be constructed from basic data types such as array integers. |
|
| An array is a fixed-sized, homogeneous, and widely-used data structure. By homogeneous, we mean that it consists of components which are all of the same type, called element type or base type. And by fixed sized, we mean that the number of components is constant, and so does not change during the lifetime of the structure. An array is also called a random-access data structure, because all components can be selected at random and are equally accessible. An array can be used to structure several data objects in the programming languages. A component of an array is selected by giving its subscript, which is an integer indicating the position of the component in the sequence. Therefore, an array is made of the pairs (value, index); it means that with every index, a value is associated. If every index is one single value then it is called a one-dimensional array, whereas if every index is a n-tuple {i1, i2, i3,….., in}, the array is called a n-dimensional array. |
|
|
|
| Program |
#include <stdio.h>
main()
{
int a[5]; \\A
for(int i = 0;i<5;i++)
{
a[i]=i;\\B
}
printarr(a);
}
void printarr(int a[])
{
for(int i = 0;i<5;i++)
{
printf("value in array %d\n",a[i]);
}
} |
|
| Explanation |
- Statement A defines an array of integers. The array is of the size 5—that means you can store 5 integers.
- Array elements are referred to using subscript; the lowest subscript is always 0 and the highest subscript is (size –1). If you refer to an array element by using an out-of-range subscript, you will get an error. You can refer to any element as a[0], a[1],a[2], etc.
- Generally, you can use a for loop for processing an array. For the array, consecutive memory locations are allocated and the size of each element is same.
- The array name, for example, a, is a pointer constant, and you can pass the array name to the function and manipulate array elements in the function. An array is always processed element by element.
- When defining the array, the size should be known.
|
|
|
| Memory Representation |
|
| An array is represented in memory by using a sequential mapping. The basic characteristic of the sequential mapping is that every element is at a fixed distance apart. Therefore, if the ith element is mapped into a location having an address a, then the (i + 1)th element is mapped into the |
|
|
|
|
| memory location having an address (a + 1), as shown in Representation of an array. |
|
| The address of the first element of an array is called the base address, so the address of the the ith element is Base address + offset of the ith element from base address where the offset is computed as: |
| Offset of the ith element = number of elements before the ith * size of each element. |
|
| If LB is the lower bound, then the offset computation becomes: |
| offset = (i - LB) * size. |
|
|
| Representation of Two-Dimensional Array |
|
| A two-dimensional array can be considered as a one-dimensional array whose elements are also one-dimensional arrays. So, we can view a two dimensional array as one single column of rows and map it sequentially as shown in image below . Such a representation is called a row-major representation. |
|
|
|
| Row-major representation of a two-dimensional array |
|
| The address of the element of the ith row and the jth column therefore is: |
| addr(a[i, j]) = ( number of rows placed before ith row * size of a row) + (number of elements placed before the jth element in the ith row * size of element) |
|
| where: |
| Number of rows placed before ith row = (i – LB1), and LB1 is the lower bound of the first dimension. |
| Size of a row = number of elements in a row * a size of element. |
|
| Number of elements in a row = (UB2 – LB2+1), where UB2 and LB2 are the upper and lower bounds of the second dimension, respectively. |
|
| Therefore: |
| addr(a[i, j]) = ((i - LB1) * (UB2 - LB2+1) * size) + ((j - LB2)*size) |
|
| It is also possible to view a two-dimensional array as one single row of columns and map it sequentially as shown in image below. Such a representation is called a column-major representation. |
|
|
|
| Column major representation of a two-dimensional array |
|
| The address of the element of the ith row and the jth column therefore is: |
| addr(a[i, j]) = ( number of columns placed before jth column * size of a column) + (number of elements placed before the ith element in the jth column * size of each element) |
|
| Number of columns placed before jth column = (j - LB2) where LB2 is the lower bound of the second dimension. |
|
| Size of a column = number of elements in a column * size of element Number of elements in a column = (UB1 – LB1 + 1), where UB1 and LB1 are the upper and lower bounds of the first dimension, respectively. |
|
| Therefore: |
| addr(a[i, j]) = ((j - LB2) * (UB1 - LB1+1) * size) + ((i - LB1)*size) |
|
|
|
|
| Array |
|
| Application of Arrays |
|
| Whenever we require a collection of data objects of the same type and want to process them as a single unit, an array can be used, provided the number of data items is constant or fixed. Arrays have a wide range of applications ranging from business data processing to scientific calculations to industrial projects. |
|
|
| Implementation of a Static Contiguous List |
|
| A list is a structure in which insertions, deletions, and retrieval may occur at any position in the list. Therefore, when the list is static, it can be implemented by using an array. When a list is implemented or realized by using an array, it is a contiguous list. By contiguous, we mean that the elements are placed consecutively one after another starting from some address, called the base address. The advantage of a list implemented using an array is that it is randomly accessible. The disadvantage of such a list is that insertions and deletions require moving of the entries, and so it is costlier. A static list can be implemented using an array by mapping the ith element of the list into the ith entry of the array, as shown below: |
|
|
|
|
|
| A complete C program for implementing a list with operations for reading values of the elements of the list and displaying them is given here: |
|
#include<stdio.h>
#include<conio.h>
void read(int *,int);
void dis(int *,int);
void main()
{
int a[5],i,sum=0;
clrscr();
printf("Enter the elements of array \n");
read(a,5); /*read the array*/
printf("The array elements are \n");
dis(a,5);
}
void read(int c[],int i)
{
int j;
for(j=0;j<i;j++)
scanf("%d",&c[j]);
fflush(stdin);
}
void dis(int [],int i)
{
int j;
for(j=0;j<i;j++)
printf("%d ",d[j]);
printf("\n");
} |
|
|
|
|
| Array |
|
| Array Manipulation |
|
| Shown next are C programs for carrying out manipulations such as finding the sum of elements of an array, adding two arrays, and reversing an array. |
|
|
| Program |
|
| ADDITION OF THE ELEMENTS OF THE LIST |
|
#include<stdio.h>
#include<conio.h>
void main()
{
void read(int *,int);
void dis(int *,int);
int a[5],i,sum=0;
clrscr();
printf("Enter the elements of list \n");
read(a,5); /*read the list*/
printf("The list elements are \n");
dis(a,5);
for(i=0;i<5;i++)
{
sum+=a[i];
}
printf("The sum of the elements of the list is %d\n",sum);
getch();
}
void read(int c[],int i)
{
int j;
for(j=0;j<i;j++)
scanf("%d",&c[j]);
fflush(stdin);
}
void dis(int d[],int i)
{
int j;
for(j=0;j<i;j++)
printf("%d ",d[j]);
printf("\n");
} |
|
|
| Example |
|
| Input |
| Enter the elements of the first array |
|
15
30
45
60
75 |
|
| Output |
| The elements of the first array are |
| 15 30 45 60 75 |
|
| The sum of the elements of an array is 225. |
|
| Addition of the two lists |
| Suppose the first list is |
1
2
3
4
5 |
|
| and the second list is |
5
6
8
9
10 |
|
| The first element of first list is added to the first element of the second list, and the result of the addition is the first element of the third list. |
|
| In this example, 5 is added to 1, and the first element of third list is 6. |
| This step is repeated for all the elements of the lists and the resultant list after the addition is |
6
8
11
13
15 |
|
#include<stdio.h>
#include<conio.h>
void main()
{
void read(int *,int);
void dis(int *,int);
void add(int *,int *,int * ,int);
int a[5],b[5],c[5],i;
clrscr();
printf("Enter the elements of first list \n");
read(a,5); /*read the first list*/
printf("The elements of first list are \n");
dis(a,5); /*Display the first list*/
printf("Enter the elements of second list \n");
read(b,5); /*read the second list*/
printf("The elements of second list are \n");
dis(b,5); /*Display the second list*/
add(a,b,c,i);
printf("The resultant list is \n");
dis(c,5);
getch();
}
void add(int a[],int b[],int c[],int i)
{
for(i=0;i<5;i++)
{
c[i]=a[i]+b[i];
}
}
void read(int c[],int i)
{
int j;
for(j=0;j<i;j++)
scanf("%d",&c[j]);
fflush(stdin);
}
void dis(int d[],int i)
{
int j;
for(j=0;j<i;j++)
printf("%d ",d[j]);
printf("\n");
} |
|
|
| Elucidation |
- Repeat step (2) for i=0,1,2,… (n−1), where n is the maximum number of elements in a list.
- c[i] = a[i]+b[i], where a is the first list, b is the second list, and c is the resultant list; a[i] denotes the ith element of list a.
|
|
|
| Example |
|
| Input |
| Enter the elements of the first list |
1
2
3
4
5 |
|
| Output |
| The elements of the first list are |
| 2 3 4 5 |
|
| Input |
| Enter the elements of the second list |
6
7
8
9
10 |
|
| Output |
| The elements of the second list are |
| 6 7 8 9 10 |
|
| The resultant list is |
| 7 9 11 13 15 |
|
| Inverse of the list |
|
| The following program makes a reverse version of the list. |
#include<stdio.h>
#include<conio.h>
void main()
{
void read(int *,int);
void dis(int *,int);
void inverse(int *,int);
int a[5],i;
clrscr();
read(a,5);
dis(a,5);
inverse(a,5);
dis(a,5);
getch();
}
void read(int c[],int i)
{
int j;
printf("Enter the list \n");
for(j=0;j<i;j++)
scanf("%d",&c[j]);
fflush(stdin);
}
void dis(int d[],int i)
{
int j;
printf("The list is \n");
for(j=0;j<i;j++)
printf("%d ",d[j]);
printf("\n");
}
void inverse(int inver_a[],int j)
{
int i,temp;
j-;
for(i=0;i<(j/2);i++)
{
temp=inver_a[i];
inver_a[i]=inver_a[j];
inver_a[j]=temp;
j-;
}
} |
|
|
| Example |
|
| Input |
| Enter the list |
10
20
30
40
50 |
|
| Output |
| The list is |
| 10 20 30 40 50 |
|
| The inverse of the list is |
| 50 40 30 20 10 |
|
| This is another version of an inverse program, in which another list is used to hold the reversed list. |
#include<stdio.h>
#include<conio.h>
void main()
{
void read(int *,int);
void dis(int *,int);
void inverse(int *,int *,int);
int a[5],b[5];
clrscr();
read(a,5);
dis(a,5);
inverse(a,b,5);
dis(b,5);
getch();
}
void read(int c[],int i)
{
int j;
printf("Enter the list \n");
for(j=0;j<i;j++)
scanf("%d",&c[j]);
fflush(stdin);
}
void dis(int d[],int i)
{
int j;
printf("The list is \n");
for(j=0;j<i;j++)
printf("%d ",d[j]);
printf("\n");
}
void inverse(int a[],int inverse_b[],int j)
{
int i,k;
k=j-1;
for(i=0;i<j;i++)
{
inverse_b[i]=a[k];
k-;
}
} |
|
|
| Example |
|
| Input |
| Enter the list |
10
20
30
40
50 |
|
| Output |
| The list is |
| 10 20 30 40 50 |
|
| The inverse of the list is |
| 50 40 30 20 10 |
|
|
|
|
| Array |
|
| Merging Array |
|
| Assume that two lists to be merged are sorted in descending order. Compare the first element of the first list with the first element of the second list. If the element of the first list is greater, then place it in the resultant list. Advance the index of the first list and the index of the resultant list so that they will point to the next term. If the element of the first list is smaller, place the element of the second list in the resultant list. Advance the index of the second list and the index of the resultant list so that they will point to the next term. |
|
| Repeat this process until all the elements of either the first list or the second list are compared. If some elements remain to be compared in the first list or in the second list, place those elements in the resultant list and advance the corresponding index of that list and the index of the resultant list. |
|
| Suppose the first list is 10 20 25 50 63, and the second list is 12 16 62 68 80. The sorted lists are 63 50 25 20 10 and 80 68 62 16 12. |
|
| The first element of the first list is 63, which is smaller than 80, so the first element of the resultant list is 80. Now, 63 is compared with 68; again it is smaller, so the second element in the resultant list is 68. Next, 63 is compared with 50. In this case it is greater, so the third element of the resultant list is 63. |
|
| Repeat this process for all the elements of the first list and the second list. The resultant list is 80 68 63 62 50 25 20 16 12 10. |
|
| Program |
|
#include<stdio.h>
#include<conio.h>
void read(int *,int);
void dis(int *,int);
void sort(int *,int);
void merge(int *,int *,int *,int);
void main()
{
int a[5],b[5],c[10];
clrscr();
printf("Enter the elements of first list \n");
read(a,5); /*read the list*/
printf("The elements of first list are \n");
dis(a,5); /*Display the first list*/
printf("Enter the elements of second list \n");
read(b,5); /*read the list*/
printf("The elements of second list are \n");
dis(b,5); /*Display the second list*/
sort(a,5);
printf("The sorted list a is:\n");
dis(a,5);
sort(b,5);
printf("The sorted list b is:\n");
dis(b,5);
merge(a,b,c,5);
printf("The elements of merged list are \n");
dis(c,10); /*Display the merged list*/
getch();
}
void read(int c[],int i)
{
int j;
for(j=0;j<i;j++)
scanf("%d",&c[j]);
fflush(stdin);
}
void dis(int d[],int i)
{
int j;
for(j=0;j<i;j++)
printf("%d ",d[j]);
printf("\n");
}
void sort(int arr[] ,int k)
{
int temp;
int i,j;
for(i=0;i<k;i++)
{
for(j=0;j<k-i-1;j++)
{
if(arr[j]<arr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
void merge(int a[],int b[],int c[],int k)
{
int ptra=0,ptrb=0,ptrc=0;
while(ptra<k && ptrb<k)
{
if(a[ptra] < b[ptrb])
{
c[ptrc]=a[ptra];
ptra++;
}
else
{
c[ptrc]=b[ptrb];
ptrb++;
}
ptrc++;
}
while(ptra<k)
{
c[ptrc]=a[ptra];
ptra++;ptrc++;
}
while(ptrb<k)
{
c[ptrc]=b[ptrb];
ptrb++; ptrc++;
}
} |
|
|
| Example |
|
|
|
|
|
| Elucidation |
|
- ptra=0, ptrb=0, ptrc=0;
- If the element in the first list pointed to by ptra is greater than the element in the second list pointed to by ptrb, place the element of the first list in the resultant list at the index equal to ptrc. Increment ptra or ptrc by one, or else place the element of the second list in the resultant list at the index equal to ptrc. Increment ptrb and ptrc by 1. Repeat this step until ptra is greater than the number of terms in the first list and ptrb is greater than the number of terms in the second list.
- If the first list has any elements, place one in the resultant list pointed to by ptrc, and increment ptra and ptrc. Repeat this step until ptra is greater than the number of terms in the first list.
- If the second list has any elements, place one in the resultant list pointed to byptrc, and increment ptrb and ptrc. Repeat this step until ptrb is greater than the number of terms in the first list.
|
|
|
|
|
| Array |
|
| Sorting Arrays |
|
| We encounter several applications that require an ordered list. So it is required to order the elements of a given list either in ascending/increasing order or descending/decreasing order, as per the requirement. This process is called sorting. |
|
| Sorting Array using Bubble Sort |
|
| Bubble sorting is a simple sorting technique in which we arrange the elements of the list by forming pairs of adjacent elements. That means we form the pair of the ith and (i+1)thelement. If the order is ascending, we interchange the elements of the pair if the first element of the pair is greater than the second element. That means for every pair(list[i],list[i+1]) for i :=1 to (n-1) if list[i] > list[i+1], we need to interchange list[i] andlist[i+1]. Carrying this out once will move the element with the highest value to the last or nth position. Therefore, we repeat this process the next time with the elements from the first to (n-1)th positions. This will bring the highest value from among the remaining (n-1)values to the (n-1)th position. We repeat the process with the remaining (n-2) values and so on. Finally, we arrange the elements in ascending order. This requires to perform (n-1) passes. In the first pass we have (n-1) pairs, in the second pass we have (n-2) pairs, and in the last (or (n-1)th) pass, we have only one pair. Therefore, the number of probes or comparisons that are required to be carried out is |
|
|
|
| and the order of the algorithm is O(n2). |
|
| Program |
|
#include <stdio.h>
#define MAX 10
void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
void bsort(int list[], int n)
{
int i,j;
for(i=0;i<(n-1);i++)
for(j=0;j<(n-(i+1));j++)
if(list[j] > list[j+1])
swap(&list[j],&list[j+1]);
}
void readlist(int list[],int n)
{
int i;
printf("Enter the elements\n");
for(i=0;i<n;i++)
scanf("%d",&list[i]);
}
void printlist(int list[],int n)
{
int i;
printf("The elements of the list are: \n");
for(i=0;i<n;i++)
printf("%d\t",list[i]);
}
void main()
{
int list[MAX], n;
printf("Enter the number of elements in the list max = 10\n");
scanf("%d",&n);
readlist(list,n);
printf("The list before sorting is:\n");
printlist(list,n);
bsort(list,n);
printf("The list after sorting is:\n");
printlist(list,n);
} |
|
|
| Output |
|
|
|
|
|
|
|
| Stack and Queue |
|
| Introduction to Stack and Queue |
|
| There are many applications requiring the use of the data structures stacks and queues. The most striking use of a data structure stack is the runtime stack that a programming language uses to implement a function call and return. Similarly, one of the important uses of a data structure queue is the process queue maintained by the scheduler. Both these data structures are modified versions of the list data structure, so they can be implemented using arrays or linked representation. |
|
| Stack |
|
| A stack is a list in which all insertions and deletions are made at one end, called the top. The last element to be inserted into the stack will be the first to be removed. Thus stacks are sometimes referred to as Last In First Out (LIFO) lists. |
|
|
| Queue |
|
|
| A Queue is 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 (the rear of the queue). |
|
|
|
|
| Stack and Queue |
|
| Working with Stacks |
|
| A stack is simply a list of elements with insertions and deletions permitted at one end—called the stack top. That means that it is possible to remove elements from a stack in reverse order from the insertion of elements into the stack. Thus, a stack data structureexhibits the LIFO (last in first out) property. Push and pop are the operations that are provided for insertion of an element into the stack and the removal of an element from the stack, respectively. Shown in the image below are the effects of push and pop operations on the stack. |
|
|
|
|
| Stack operations. |
|
| Since a stack is basically a list, it can be implemented by using an array or by using a linked representation. |
|
|
| Array Implementation of a Stack |
|
|
| When an array is used to implement a stack, the push and pop operations are realized by using the operations available on an array. The limitation of an array implementation is that the stack cannot grow and shrink dynamically as per the requirement. |
|
| Program |
| A complete C program to implement a stack using an array appears here: |
|
#include <stdio.h>
#define MAX 10 /* The maximum size of the stack */
#include <stdlib.h>
void push(int stack[], int *top, int value)
{
if(*top < MAX )
{
*top = *top + 1;
stack[*top] = value;
}
else
{
printf("The stack is full can not push a value\n");
exit(0);
}
}
void pop(int stack[], int *top, int * value)
{
if(*top >= 0 )
{
*value = stack[*top];
*top = *top - 1;
}
else
{
printf("The stack is empty can not pop a value\n");
exit(0);
}
}
void main()
{
int stack[MAX];
int top = -1;
int n,value;
do
{
do
{
printf("Enter the element to be pushed\n");
scanf("%d",&value);
push(stack,&top,value);
printf("Enter 1 to continue\n");
scanf("%d",&n);
} while(n == 1);
printf("Enter 1 to pop an element\n");
scanf("%d",&n);
while( n == 1)
{
pop(stack,&top,&value);
printf("The value poped is %d\n",value);
printf("Enter 1 to pop an element\n");
scanf("%d",&n);
}
printf("Enter 1 to continue\n");
scanf("%d",&n);
} while(n == 1);
} |
|
| Example |
|
|
|
|
| Implementation of a Stack Using Linked Representation |
|
| Initially the list is empty, so the top pointer is NULL. The push function takes a pointer to an existing list as the first parameter and a data value to be pushed as the second parameter, creates a new node by using the data value, and adds it to the top of the existing list. A pop function takes a pointer to an existing list as the first parameter, and a pointer to a data object in which the popped value is to be returned as a second parameter. Thus it retrieves the value of the node pointed to by the top pointer, takes the top point to the next node, and destroys the node that was pointed to by the top. |
|
| If this strategy is used for creating a stack with the previously used four data values: 10, 20, 30, and 40, then the stack is created as shown below: |
|
|
|
|
|
| Linked stack |
|
| Program |
| A complete C program for implementation of a stack using the linked list is given here: |
|
# include <stdio.h>
# include <stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *push(struct node *p, int value)
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
/* creates new node
using data value
passed as parameter */
if(temp==NULL)
{
printf("No Memory available Error\n");
exit(0);
}
temp->data = value;
temp->link = p;
p = temp;
return(p);
}
struct node *pop(struct node *p, int *value)
{
struct node *temp;
if(p==NULL)
{
printf(" The stack is empty can not pop Error\n");
exit(0); }
*value = p->data;
temp = p;
p = p->link;
free(temp);
return(p);
}
void main()
{
struct node *top = NULL;
int n,value;
do
{
do
{
printf("Enter the element to be pushed\n");
scanf("%d",&value);
top = push(top,value);
printf("Enter 1 to continue\n");
scanf("%d",&n);
} while(n == 1);
printf("Enter 1 to pop an element\n");
scanf("%d",&n);
while( n == 1)
{
top = pop(top,&value);
printf("The value poped is %d\n",value);
printf("Enter 1 to pop an element\n");
scanf("%d",&n);
}
printf("Enter 1 to continue\n");
scanf("%d",&n);
} while(n == 1);
} |
|
| Example |
|
|
|
|
|
|
|
| Stack and Queue |
|
| Working with Queues |
|
| One of the applications of the stack is in expression evaluation. A complex assignment statement such as a = b + c*d/e–f may be interpreted in many different ways. Therefore, to give a unique meaning, the precedence and associativity rules are used. But still it is difficult to evaluate an expression by computer in its present form, called the infix notation. In infix notation, the binary operator comes in between the operands. A unary operator comes before the operand. To get it evaluated, it is first converted to the postfix form, where the operator comes after the operands. For example, the postfix form for the expression a*(b–c)/d is abc–*d/. A good thing about postfix expressions is that they do not require any precedence rules or parentheses for unique definition. So, evaluation of a postfix expression is possible using a stack-based algorithm. |
|
| Program |
|
| Convert an infix expression to prefix form. |
|
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define N 80
typedef enum {FALSE, TRUE} bool;
#include "stack.h"
#include "queue.h"
#define NOPS 7
char operators [] = "()^/*+-";
int priorities[] = {4,4,3,2,2,1,1};
char associates[] = " RLLLL";
char t[N]; char *tptr = t; // this is where prefix will be saved.
int getIndex( char op ) {
/*
* returns index of op in operators.
*/
int i;
for( i=0; i<NOPS; ++i )
if( operators[i] == op )
return i;
return -1;
}
int getPriority( char op ) {
/*
* returns priority of op.
*/
return priorities[ getIndex(op) ];
}
char getAssociativity( char op ) {
/*
* returns associativity of op.
*/
return associates[ getIndex(op) ];
}
void processOp( char op, queue *q, stack *s ) {
/*
* performs processing of op.
*/
switch(op) {
case ')':
printf( "\t S pushing )...\n" );
sPush( s, op );
break;
case '(':
while( !qEmpty(q) ) {
*tptr++ = qPop(q);
printf( "\tQ popping %c...\n", *(tptr-1) );
}
while( !sEmpty(s) ) {
char popop = sPop(s);
printf( "\tS popping %c...\n", popop );
if( popop == ')' )
break;
*tptr++ = popop;
}
break;
default: {
int priop; // priority of op.
char topop; // operator on stack top.
int pritop; // priority of topop.
char asstop; // associativity of topop.
while( !sEmpty(s) ) {
priop = getPriority(op);
topop = sTop(s);
pritop = getPriority(topop);
asstop = getAssociativity(topop);
if( pritop < priop || (pritop == priop && asstop == 'L')
|| topop == ')' ) // IMP.
break;
while( !qEmpty(q) ) {
*tptr++ = qPop(q);
printf( "\tQ popping %c...\n", *(tptr-1) );
}
*tptr++ = sPop(s);
printf( "\tS popping %c...\n", *(tptr-1) );
}
printf( "\tS pushing %c...\n", op );
sPush( s, op );
break;
}
}
}
bool isop( char op ) {
/*
* is op an operator?
*/
return (getIndex(op) != -1);
}
char *in2pre( char *str ) { /*
* returns valid infix expr in str to prefix.
*/
char *sptr;
queue q = {NULL};
stack s = NULL;
char *res = (char *)malloc( N*sizeof(char) );
char *resptr = res;
tptr = t;
for( sptr=str+strlen(str)-1; sptr!=str-1; -sptr ) {
printf( "processing %c tptr-t=%d...\n", *sptr, tptr-t );
if( isalpha(*sptr) ) // if operand.
qPush( &q, *sptr );
else if( isop(*sptr) ) // if valid operator.
processOp( *sptr, &q, &s );
else if( isspace(*sptr) ) // if whitespace.
;
else {
fprintf( stderr, "ERROR:invalid char %c.\n", *sptr );
return "";
}
}
while( !qEmpty(&q) ) {
*tptr++ = qPop(&q);
printf( "\tQ popping %c...\n", *(tptr-1) );
}
while( !sEmpty(&s) ) {
*tptr++ = sPop(&s);
printf( "\tS popping %c...\n", *(tptr-1) );
}
*tptr = 0;
printf( "t=%s.\n", t );
for( -tptr; tptr!=t-1; -tptr ) {
*resptr++ = *tptr;
}
*resptr = 0;
return res;
}
int main() {
char s[N];
puts( "enter infix freespaces max 80." );
gets(s);
while(*s) {
puts( in2pre(s) );
gets(s);
}
return 0;
} |
|
| Output |
|
|
|
|
|
| Elucidation |
|
- In an infix expression, a binary operator separates its operands (a unary operator precedes its operand). In a postfix expression, the operands of an operator precede the operator. In a prefix expression, the operator precedes its operands. Like postfix, a prefix expression is parenthesis-free, that is, any infix expression can be unambiguously written in its prefix equivalent without the need for parentheses.
- To convert an infix expression to reverse-prefix, it is scanned from right to left. A queue of operands is maintained noting that the order of operands in infix and prefix remains the same. Thus, while scanning the infix expression, whenever an operand is encountered, it is pushed in a queue. If the scanned element is a right parenthesis (‘)’), it is pushed in a stack of operators. If the scanned element is a left parenthesis (‘(‘), the queue of operands is emptied to the prefix output, followed by the popping of all the operators up to, but excluding, a right parenthesis in the operator stack.
- If the scanned element is an arbitrary operator o, then the stack of operators is checked for operators with a greater priority then o. Such operators are popped and written to the prefix output after emptying the operand queue. The operator o is finally pushed to the stack.
- When the scanning of the infix expression is complete, first the operand queue, and then the operator stack, are emptied to the prefix output. Any whitespace in the infix input is ignored. Thus the prefix output can be reversed to get the required prefix expression of the infix input.
|
|
| Example |
| If the infix expression is a*b + c/d, then different snapshots of the algorithm, while scanning the expression from right to left, are shown in the Table below |
|
Scanning the infex expression a*b+c/d from right to left
|
| STEP | REMAINING EXPRESSION | SCANNED ELEMENT | QUEUE OF OPERANDS | STACK OF OPERATORS | PREFIX OUTPUT |
| 0 | a*b+c/d | nil | empty | empty | nil |
| 1 | a*b+c/ | d | d | empty | nil |
| 2 | a*b+c | / | d | / | nil |
| 3 | a*b+ | c | d c | / | nil |
| 4 | a*b | + | empty | + | dc/ |
| 5 | a* | b | b | + | dc/ |
| 6 | a | * | b | * + | dc/ |
| 7 | nil | a | b a | * + | dc/ |
| 8 | nil | nil | empty | empty | dc/ba*+ |
|
|
| The final prefix output that we get is dc/ba*+ whose reverse is +*ab/cd, which is the prefix equivalent of the input infix expression a*b+c*d. Note that all the operands are simply pushed to the queue in steps 1, 3, 5, and 7. In step 2, the operator / is pushed to the empty stack of operators. |
|
| In step 4, the operator + is checked against the elements in the stack. Since / (division) has higher priority than + (addition), the queue is emptied to the prefix output (thus we get ‘dc’ as the output) and then the operator / is written (thus we get ‘dc/’ as the output). The operator + is then pushed to the stack. In step 6, the operator * is checked against the stack elements. Since * (multiplication) has a higher priority than + (addition), * is pushed to the stack. Step 8 signifies that all of the infix expression is scanned. Thus, the queue of operands is emptied to the prefix output (to get ‘dc/ba’), followed by the emptying of the stack of operators (to get ‘dc/ba*+’). |
|
|
| Points to remember |
|
- A prefix expression is parenthesis-free.
- To convert an infix expression to the postfix equivalent, it is scanned from right to left. The prefix expression we get is the reverse of the required prefix equivalent.
- Conversion of infix to prefix requires a queue of operands and a stack, as in the conversion of an infix to postfix.
- The order of operands in a prefix expression is the same as that in its infix equivalent.
- If the scanned operator o1 and the operator o2 at the stack top have the same priority, then the associativity of o2 is checked. If o2 is right-associative, it is popped from the stack.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 comments: