# Data Structures...

• ### Question

• Anyone Interested in Data Structures, like sorting techniques, trees, graph theory..

We can start discussing topics related to data structres here.. have question and answers for them...
Wat say?? Reply to kick start this topic...
Wednesday, April 25, 2007 3:56 PM

• Sure varun...

I am also interested in DS...

Wednesday, April 25, 2007 5:01 PM
• Yes, I am too interested in Data Structures.
Thursday, April 26, 2007 12:23 PM

I think how about discussing the sorting techniques... What are their uses and how they are better in different situations...

I have studied
Selection sort
Bubble sort
Insertion Sort
Shell Sort
Merge Sort
Quick Sort

Thursday, April 26, 2007 1:44 PM
• Same here...

Have u studied Heap Sort??

Thursday, April 26, 2007 4:49 PM
• we do have heap sort in course but its still to cover.. will be doing it in next 10 days..
i forgot to mention the Radix sort.. we have also done that...

Well merge sort is the fastest, but it eats up lot of memory, the best thing in merge sort is that it dosent have any worse case.. where else you would find a worse case for every other sorting technique..

does anyone have the code for this sorts?? I have written them in C, would share it here...
Also would like others to share their code first..

We can discuss on them and find out if we can get something even better than what we have
Thursday, April 26, 2007 6:35 PM
• heres my code sample for selection sort...share yours too

Code Snippet

for(int x=0; x<n; x++)

{

int index_of_min = x;

for(int y=x; y<n; y++)

{

if(array[index_of_min]<array[y])

{

index_of_min = y;

}

}

int temp = array[x];

array[x] = array[index_of_min];

array[index_of_min] = temp;

}

The first loop goes from 0 to n, and the second loop goes from x to n, so it goes from 0 to n, then from 1 to n, then from 2 to n and so on. The multiplication works out so that the efficiency is n*(n/2), though the order is still O(n^2).

Friday, May 4, 2007 10:01 PM
• Well buddy mine is same... but i will give you a code which will help you compare the selection sort and the bubble sort in real time...

have a look at this
//WAP to sort a big list using selection sort and bubble sort to see the time diff..

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<time.h>
#define length 30000
void generate(int list[]);
void bubblesort(int list[]);
void selectionsort(int list[]);

void main()
{
int i;
int list[length];
float start, end;
clrscr();
generate(list);
start = clock();

bubblesort(list);
end = clock();

printf("Sorted using bubble sort\n");
printf("Time taken = %f press a key....", (end-start)/CLK_TCK);

getch();
generate(list);
start = clock();
selectionsort(list);
end = clock();
printf("The list is sorted using Selection sort\n");
printf("Time taken = %f press a key....", (end-start)/CLK_TCK);

getch();
}

void generate(int list[])
{
int i;
for(i=0;i<length;i++)
list[i] = random(30000);
}

void bubblesort(int list[])
{
int i, j, min;
for (i=length-1;i>0; i--)
{
for(j=0; j<i; j++)
{
if (list[j+1] < list[j])
{
min = list[j+1];
list[j+1] = list[j];
list[j] = min;
}
}
}
}

void selectionsort(int list[])
{
int i, j, min, min_scorer;
for(i=0;i<length-1;i++)
{
min = list[i];
min_scorer = i;
for(j=i+1; j<length; j++)
{
if(list[j] < min)
{
min = list[j];
min_scorer = j;
}
}
list[min_scorer] = list[i];
list[i] = min;
}
}

/*            OUTPUT
Sorted using bubble sort
Time taken = 4.175824 press a key....
The list is sorted using Selection sort
Time taken = 0.934066 press a key....
*/

Saturday, May 5, 2007 2:31 AM
• I know that its not good code, but i have created these when i was in 2nd year of my BCA,  at tha time i was just a starter but the programs work exactly as the algorithm says
Bubble Sort :

#include<stdio.h>
#include<conio.h>

int BUB_SORT (int arr[],int n)
{
int i,k,temp,ptr;
for (i=0 ; i<n-1 ; i++)
{
ptr = 0;
printf("Phase : %d\n",i+1);
while (ptr<n-i)
{
if (arr[ptr] > arr[ptr+1] )
{
temp = arr[ptr];
arr[ptr] = arr[ptr+1];
arr[ptr+1] = temp;
}
ptr = ptr+1;
for (k=0 ; k<n ; k++)
{
printf("%3d",arr[k]);
}
printf("\n");
}
}
return *arr;
}

void main()
{
int arr[11];
int temp, ptr, k, n=11,i=1;
clrscr();
printf("Enter now many numbers do you wantto sort : ");
scanf("%d",&n);
for (k=0 ; k<n ; k++)
{
printf("Enter arr[%d] : ",k);
scanf("%d",&arr[k]);
}
BUB_SORT(arr,n);
printf("\n");
for (k=0 ; k<n ; k++)
{
printf("%3d",arr[k]);
}
getch();
}
Saturday, May 5, 2007 4:13 AM

• Insertion sort

#include<stdio.h>
#include<conio.h>

int INS_SORT(int arr[],int n)
{
int k,ptr,i,temp;
arr[0] = -32768;
for (k=2 ; k<n ; k++)
{
temp = arr[k];
ptr = k-1;
while (temp < arr[ptr] )
{
arr[ptr+1] = arr[ptr];
ptr = ptr-1;
}
arr[ptr+1] = temp;
}
return *arr;
}

void main()
{
int arr[11];
int temp, ptr, k, n=11,i=1;
clrscr();
printf("Enter now many numbers do you wantto sort : ");
scanf("%d",&n);
n++;
for (k=1 ; k<n ; k++)
{
printf("Enter arr[%d] : ",k-1);
scanf("%d",&arr[k]);
}

arr[0] = -32768;
INS_SORT(arr,n);

for (k=1 ; k<n ; k++)
{
printf("%3d",arr[k]);
}
getch();
}
Saturday, May 5, 2007 4:14 AM

• Quick Sort:

#include<stdio.h>
#include<conio.h>

int QCK_SORT(int arr[], int lb, int ub)
{
int flag=1,i,j,key,temp;
if (lb < ub)
{
i=lb;
j=ub+1;
key = arr[lb];
while (flag)
{
i=i+1;
while (arr[i] < key)
{
i=i+1;
}
j=j-1;
while (arr[j] > key)
{
j=j-1;
}
if (i<j)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
else
{
flag = 0;
}
}
temp = arr[lb];
arr[lb] = arr[j];
arr[j] = temp;
QCK_SORT(arr,lb,j-1);
QCK_SORT(arr,j+1,ub);
}
return *arr;
}
void main()
{
int arr[11];
int temp, ptr, k, n=11,i=1,lb=0,ub;
clrscr();
printf("Enter now many numbers do you want to sort : ");
scanf("%d",&n);
ub = n;
for (k=0 ; k<n ; k++)
{
printf("Enter arr[%d] : ",k);
scanf("%d",&arr[k]);
}
QCK_SORT(arr,lb,ub);
for (k=0 ; k<n ; k++)
{
printf("%3d\t",arr[k]);
}
getch();
}
Saturday, May 5, 2007 4:14 AM

• Selection Sort :

#include<stdio.h>
#include<conio.h>

int SEL_SORT (int arr[],int n)
{
int i,x,temp,y;
for (i=0 ; i<n ; i++)
{
x=MIN(arr,i,n);
temp = arr[i];
arr[i] = arr[x];
arr[x] = temp;
}
return *arr;
}

int MIN(int arr[],int i, int n)
{
int min,x,loc;
min = arr[i];
loc = i;
for (x=i+1 ; x<n+1 ; x++)
{
if (min > arr[x] )
{
min = arr[x];
loc = x;
}
}
return loc;
}

void main()
{
int arr[11];
int temp, ptr, k, n=11,i=1;
clrscr();
printf("Enter now many numbers do you want to sort : ");
scanf("%d",&n);
for (k=0 ; k<n ; k++)
{
printf("Enter arr[%d] : ",k);
scanf("%d",&arr[k]);
}
SEL_SORT(arr,n);

for (k=0 ; k<n ; k++)
{
printf("%3d\t",arr[k]);
}
getch();
}
Saturday, May 5, 2007 4:15 AM
• Well buddy as i had guessed, your quick sort code has a problem.. please try running it.. this was the problem that i used to face... the last elemnt in the array is lost and a garbage is assigned...

I will show you my code.. this code also give step by step values of the array as things change... I m sure you will like it...
// This program sorts the data by using Quick Sort Technique...

#include<stdio.h>
#include<conio.h>
void quicksort(int list[], int start, int end);
int size;
void main()
{
int list[30], i;
//    clrscr();
printf("Please give the size of the list : ");
scanf("%d",&size);
for(i=0;i<size;i++)
scanf("%d",&list[i]);

quicksort(list, 0, size-1);
printf("\nThe Sorted List : ");
for(i=0;i<size;i++)
printf("%d ",list[i]);

getch();
}

void quicksort(int list[], int start, int end)
{
int z, i=start, j=end-1, pivot, tmp;

printf("The Unsorted List : ");
for(z=0;z<size;z++)
printf("%d ",list[z]);
printf("\n");
pivot = list[end];
printf("Pivot %d Start %d end %d \n",pivot, list[i], list[j]);
while(i<=j)
{
while(list[i]<=pivot && i<=j)
i++;
while(list[j]>=pivot && i<=j)
j--;
if(i<=j)
{
tmp = list[i];
list[i] = list[j];
list[j] = tmp;
}
}
list[end] = list[i];
list[i] = pivot;
printf("List After Shifting the elements :");
for(z=0;z<size;z++)
printf("%d ",list[z]);
printf("\n i = %d j = %d\n",i,j);

if(start<i-1)
quicksort(list,start, i-1);
if(end>j+1)
quicksort(list,j+1,end);
}

/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Output
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Please give the size of the list : 8
4 8 3 7 5 1 2 6
The Unsorted List : 4 8 3 7 5 1 2 6
Pivot 6 Start 4 end 2
List After Shifting the elements :4 2 3 1 5 6 8 7
i = 5 j = 4
The Unsorted List : 4 2 3 1 5 6 8 7
Pivot 5 Start 4 end 1
List After Shifting the elements :4 2 3 1 5 6 8 7
i = 4 j = 3
The Unsorted List : 4 2 3 1 5 6 8 7
Pivot 1 Start 4 end 3
List After Shifting the elements :1 2 3 4 5 6 8 7
i = 0 j = -1
The Unsorted List : 1 2 3 4 5 6 8 7
Pivot 4 Start 1 end 3
List After Shifting the elements :1 2 3 4 5 6 8 7
i = 3 j = 2
The Unsorted List : 1 2 3 4 5 6 8 7
Pivot 3 Start 1 end 2
List After Shifting the elements :1 2 3 4 5 6 8 7
i = 2 j = 1
The Unsorted List : 1 2 3 4 5 6 8 7
Pivot 2 Start 1 end 1
List After Shifting the elements :1 2 3 4 5 6 8 7
i = 1 j = 0
The Unsorted List : 1 2 3 4 5 6 8 7
Pivot 7 Start 6 end 8
List After Shifting the elements :1 2 3 4 5 6 7 8
i = 6 j = 5

The Sorted List : 1 2 3 4 5 6 7 8
*/

Saturday, May 5, 2007 1:14 PM
• @Varun, i ahve tried the code in TC, and it works fine . There seems nothign wrong in the quicksort logic, May be in other compilers there is something scricter in return the pointers, ilke "Cannot return reference to localvariable" stuffs, and may be thats why you are facing the problem ?

I have tried it for 10 elements, and it worked perfectly, and no garbage. The logic of your code, and my code, seems the same, except that you have coded it differently.

If you find out why my code behaves strangely at your end, then do let me know We can get to know something new
Saturday, May 5, 2007 2:10 PM
• Yo harshil i found the problem... the problem is in the code....
now what you pass from the main as the value of ub i.e. n is wrong.. it should be n-1,
because we pass the value of the address of the last array element...
i.e. lets say when you have 10 elements, the last adress would be 9 and not 10...
but you have passed the value of 10, which creates a problem....

now here is the reason why you were not able to trace it...
What i did was that i displayed the whole array eveytime quicksort is called... this is what i found..
I tried it on VC++ first.. so in VC the garbage value was negative, i.e. it is the smallest, so it gets to the place 1 and so we get a garbage their...
Now in Turbo, there is some very big positive value as garbage, due to it this value stays at the end of the array and so we dont get to notice it...

So, in short, while calling the quicksort function,
it should not be     QCK_SORT(arr,lb,ub);
but it should be    QCK_SORT(arr,lb,ub-1);

Try out this.. this will make your code perfect...
And yes our logic are same, we both are doing the Standard Quick Sort...

If anyone is having a difficulty in Quick sort, tell us.. we would explain how it works..
Saturday, May 5, 2007 3:33 PM
• Hey Varun, Thanks for pointing out the mistake. But i have a clarification for that. I porpusely put ub, cause as you can see in my code, i have put j-- before entering into the loop, so when ub will be passed into the function as j, it will decrement first , so its value will be one less than what ever it is.

But i also agree with you, that we enter the adderss of the last element, but i have done it a different way. I agree with your clarification, and i stand with it  No such problems ...
Saturday, May 5, 2007 4:34 PM
• Hey friends,

i have complete notes on data structures . i hope, it will be useful to me and everyone who r here. so keep gathering and sharing knowledge.

the link for the file is :

http://rapidshare.com/files/29661021/data_structures.pdf

Bye

Saturday, May 5, 2007 6:21 PM
• Thanks Sunil for the help
Saturday, May 5, 2007 6:41 PM
• Why data structure programs are so long?
Saturday, May 5, 2007 7:13 PM
• thanks varun for that comparison program, it was indeed, a good one, i had known the difference in time for processing, but your ur program worked it out practically......

Sunil_Raj_fd640cmscomforums wrote:
 Hey friends,   i have complete notes on data structures . i hope, it will be useful to me and everyone who r here. so keep gathering and sharing knowledge.   the link for the file is :   http://rapidshare.com/files/29661021/data_structures.pdf   Bye

common yaar, you should atleast make sure, before posting a link, that its not broken, there is not file existing at the place of link provided by you....

Deepak_Sharma_1d9447 wrote:
 Why data structure programs are so long?

Well, good question, but i dont think they are really long, because if you see actual c programs at the machine level, then these data structure programs are just ants...

But do notice one thing, although they are long, they are quite simple to understand, because they have a simple logic....

Saturday, May 5, 2007 7:40 PM
• yaar Anoop

i have uploaded the best source of information and full notes regarding data structures. i tried just now also when u said there was no file. its working successfully. its an acrobat file type of notes containing 179 pages of notes. i hope u try once. if again problem arises, plz tell me without any hesitation.  i will upload any new one.

No quarrels or misunderstandings.  lets rock everybody

Bye

Sunday, May 6, 2007 2:47 AM
• The link is working guys and its really good...
Thankz Sunil.. even i have some stuff of data structures.. tell me where to upload them.. i will do it if you want so...

And please share more of such stuff if anyone has so....
Sunday, May 6, 2007 4:41 AM
• Yes friends, the link is working perfectly fine, i have even downloaded, and its good source of information if you want to really go deep into structures.

And about the size of the datastructures programs, if you can see theere is lto of logic written in the void main itself we just have one line calling the function that performs the operatin. And that function aint that big. Also the logic is simple ....... Just ignore the main() part, and concentrate no the core, you will feel that its easy and also very good.
Sunday, May 6, 2007 4:55 AM
• Thnx friends for ur kind support . i would like to upload still more , if u wish to have.

just simple, go to www.rapidshare.com. in the main screen, u will find browse button. put ur notes which is located in ur pc and upload it. after uploading, the link will be dispalyed. copy the link.

Thats it. u have done!!!!!!

Bye

Sunday, May 6, 2007 7:04 AM
Sunday, May 6, 2007 9:45 PM
• Hey Anoop,

Come on yaar, no need of saying thnx. its a knowledge . i believing in sharing the knowledge rathar than hiding. i would be happy if that could be useful to u and all. and i would like to learn which i doesn't knowbecause i am nt a genius . would u plz help me??

Keep sharing the knowledge.

Bye

Monday, May 7, 2007 2:37 AM

• Linked List : Insertion and Deletion

#include<stdio.h>
#include<conio.h>
#include<alloc.h>

struct node
{
int data;
};
void main()
{
struct node *p;
int x,loc=0,cnt=0;
clrscr();
p=NULL;
while (1)
{
if (cnt !=0)
{
printf("\nEnter the position \n\t0 = start of list\n\tafter NUM(loc)\n : ");
scanf("%d",&loc);
}
cnt++;
if (loc == -1)
{
disp(p);
getch();
break;

}
printf("Enter number to insert : ");
scanf("%d",&x);
if (x==-1)
{
disp(p);
getch();
break;
}
insert (&p,x,loc);
disp(p);
printf("\n");
}
loc=1;
while (1)
{
if (loc == -1)
{
disp(p);
getch();
break;
}
printf("Del by value or loc:1 || 2");
scanf("%d",&loc);
if (loc == 1)
{
printf("Enter value to delete : ");
scanf("%d",&loc);
delval (&p,loc);
}
if(loc == -1)
{
disp(p);
getch();
break;
}
else
{
printf("Enter location to delete : ");
scanf("%d",&loc);
delloc (&p,loc);
}
disp(p);
}
getch();
}

insert (struct node **q , int num,int loc)
{
struct node *temp,*r;
int i=1;
temp = *q;
if (loc == 0)
{
r =(struct node *)malloc(sizeof(struct node));
r->data = num;
*q  = r;
return 0;
}
else
{
for (i=1 ; i<loc || temp !=NULL  ; i++,    temp = temp->link)
{
if (i == loc)
{
printf("\nPosition Found\n");
r =(struct node *)malloc(sizeof(struct node));
r->data = num;
return 0;
}
}
}
{
printf("Invalid position [Check the size of the Link List ] \n");
}
return 0;
}

disp (struct node *q)
{
while (q!=NULL)
{
printf("%5d",q->data);
}
return 0;
}

delloc (struct node **q , int loc )
{
struct node *temp,*prev;
int i;
temp = *q;
if (loc == 1)
{
return 0;
}
prev = *q;
for (i=1 ; i<loc || temp !=NULL  ; i++,    temp = temp->link)
{
if (i == loc)
{
}
prev = temp;
}
{
printf("Invalid position [Check the size of the Link List ] \n");
}
return 0;
}
delval (struct node **q , int num )
{
struct node *temp,*prev;
int i;
temp = prev = *q;
while (temp!=NULL)
{
if (temp->data == num)
{
if (prev == *q)
{
}
else
{
}
return 0;
}
prev = temp;
}
printf("Invalid position [Check the size of the Link List ] \n");
return 0;
}
Monday, May 7, 2007 9:38 AM

• Tower of Hanoi : Recursion (Usage of inbuilt stacks)

#include<stdio.h>
#include<conio.h>

int CNT=1;

void hanoi (int n, char a, char b, char c)
{
if (n==1)
{
printf(" %3d. Move %2d disk from %c->%c\n",CNT++,n,a,c);
return;
}
else
{
hanoi(n-1,a,c,b);
printf(" %3d. Move %2d disk from %c->%c\n",CNT++,n,a,c);
hanoi(n-1,b,a,c);
return;
}
}
void main()
{
int no;
clrscr();
printf("Enter no of disks : ");
scanf("%d",&no);
clrscr();
printf("n = %d\n",no);
hanoi(no,'A','B','C');
getch();
}
Monday, May 7, 2007 9:40 AM

• Stack Implementation : Convert Infix Notation to PostFix Notation

#include<stdio.h>
#include<conio.h>

int PRIORITY(char ch)
{
if (ch=='(' || ch==')')
return 4;
else if (ch=='^')
return 3;
else if (ch=='*' || ch=='/')
return 2;
else if (ch=='+' || ch=='-')
return 1;
else
return 0;
}

void main()
{
char stack[40],p[40];
char str[40]={"a+(b*c-(d/e^f)*g)*h"};
int top=-1,p_cnt=0;
int i,j,k,len;
clrscr();
printf("Enter any Infix Equation  : ");
gets(str);
printf("\nSymbol\t\tStack\t\tPostfix");
len=strlen(str);
str[len]=')';
str[len+1]='\0';
for (i=0 ; str[i] ; i++)
{
if (i==0)
{
stack[++top]='(';
printf("\n\t\t(\n\r");
}
printf("%c\t\t",str[i]);
if ( (str[i]>='a' && str[i]<='z') || (str[i]>='A' && str[i]<='Z')  || (str[i]>='0' && str[i]<='9') )
{
p[p_cnt++]=str[i];
}
else
{
if (str[i]!=')')
{
if (PRIORITY(str[i]) > PRIORITY(stack[top]) || (stack[top]=='(') )
{
stack[++top]=str[i];
}
else
{
p[p_cnt++]=stack[top];
stack[top]=str[i];
}
}
else if (str[i]==')')
{
while (stack[top]!='(')
{
p[p_cnt++]=stack[top--];
}
top--;
}
}
for (j=0 ; j<=top ; j++)
{
printf("%c",stack[j]);
}
printf("\t\t");
for (j=0 ; j<p_cnt ; j++)
{
printf("%c",p[j]);
}
printf("\n");
delay(100);
}
for (j=0 ; j<=top ; j++)
{
printf("%c",stack[j]);
}
getch();
}
Monday, May 7, 2007 9:41 AM

• Stack Implementation : Evaluating a Postfix Expression

#include<math.h>
#include<stdio.h>
#include<conio.h>

void main()
{
char str[40]={"53+2*697-/-"};
int stack[40];
int i,j,top=-1,a,b;
clrscr();
printf("Enter any Postfix Equation : ");
//    gets(str);
str[strlen(str)]=')';
str[strlen(str)+1]='\0';
printf("\n\n");
printf("Symbol\t\tStack\n");

for (i=0 ; str[i]!=')' ; i++)
{
printf("%3c\t\t",str[i]);
if (str[i]>='0' && str[i]<='9')
{
stack[++top]=str[i]-48;
}
else
{
a=stack[top--];
b=stack[top--];
if (str[i]=='+')
stack[++top]=b+a;
if (str[i]=='-')
stack[++top]=b-a;
if (str[i]=='/')
stack[++top]=b/a;
if (str[i]=='*')
stack[++top]=b*a;
if(str[i]=='^')
stack[++top]=pow(b,a);
}
for (j=0 ; j<=top ; j++)
{
printf("%2d,",stack[j]);
}
printf("\b \n");
delay(100);
}
printf("\n\n ANS = %d",stack[top]);
getch();
}
Monday, May 7, 2007 9:42 AM
• some really good programs harshil.....
Tuesday, May 8, 2007 10:53 AM
• Really nice programs harshil, Specially the Hanoi one, I was looking for it for a long time...
But m still not clear with the functions... As it is the exams are going on so not able to concentrate  more on this rite now...
anyways thankz for the codes..
I will post mine codes afterwards.. most of them are in C++, rite now i m preparing codes in C++ for data structures,...
Tuesday, May 8, 2007 11:54 AM
• Yaar Varun,

Wishing u all the very best for ur exams

Tuesday, May 8, 2007 12:11 PM
• @Annop - Yes m8, i have done a lot of work on those programs i have done many more, but i just cant find where i have stored them. Ill post more when i find those

@Varun - Have a look at it later, you will see that its very easy, and also resembels the exact steps of solving the hanoi problem.

Tuesday, May 8, 2007 1:51 PM
• A simple but very imp Data structures question...

We all have studied Hashing Techniques... now in hashing technique we see that at all the place where we use modular, we use a prime number... can anyone tell me why a prime number ???
I tried searching for the answer but was not able to get one...
Wednesday, May 9, 2007 4:03 PM
• The reason i think why prime values are used specially large prime numbers, because the hash value thus generated by the hash function can be different as far as possible.
But instead if we dont use a prime number, we will get many of its factors, and hence the hash value thus generated can be repetitive and around the factors.

The main desirable property of the hash function is that, it should generate different values most of the time, and not take much time to calculate.

I guess from the 1st desirable property, we can try to guess out the use of a prime number.

Also in Encryption techniques, especially in RSA , prime numbers are also used , for the same very purpose.
Wednesday, May 9, 2007 4:37 PM
• Hey guys where is everyone?? Why has the disscussion been stopped here... lets talk about something new....

I have just witnessed a new problem, Actually our Sir was talking about it...

There was a Traveling Company's Website project... now the website helped the user to plan out a trip in India... but the project lacked something... i.e. Website was not able to show near by places as options.. for e.g. I m searching for Ahmedabad, then the website could have shown me nearby places, like Vadodra, Gandhinagar, Maninagar.. etc.. all the famous places around my searched place...

Now let us try to solve it using Data Strucutres.. how can we do it?? how can we make the Website more intelligent ???
Tuesday, May 15, 2007 9:29 AM
• I think this is a bit twisted. But we can implement it using a collection or a link list.

May be the structure of a node in the link list can have a pointer to a LINKED-LIST that contains the neighbourhood cities/places ID.

and each node in the main link list, will have a unique ID corresponding to the city. May be this idea can work ?

I think others can discuss more about it.
Tuesday, May 15, 2007 10:33 AM
• varun i think, its similar to travelling saleperson problem?..isnt it?.....
Tuesday, May 15, 2007 6:57 PM
• Well the actual problem is to store the data in such a way that we can retrive the logically connected data easily...

So for that i saw 2 options using data structures...

1. To store the data in a Multiway tree, this way we can get the connected data from that node only....

2. Better option :- storing the data in a graph.. so that all the nodes are connected and we get the near by nodes from it.....

What do you say?? disuss more on it.. this is the practilce application of the structures that we studied..
Wednesday, May 16, 2007 11:57 AM
• I guess thats what i have said in my earlier post. The datastructure that i explained is a graph. But i explained it more programmatically .

The graph would be the best datastructure. And it would also resemble the real world's map.

Have a graph, and have it indexed and pointing to the nodes in the graph, so that searching for a particular location can be easy and faster. After finding the node in the graph, we can easily find its neighbours.

Wednesday, May 16, 2007 1:16 PM
• ya thatz rite... you suggested the same thing..
So isnt the data structures great.. I have also heard that Google uses a lot of data strucutres.. this is the reason that it is so fast...

So lets try this.. give out the practicle applications of data structres.. where they are practically applied.... like for trees, linklists and all
Wednesday, May 16, 2007 5:53 PM
• Yes Varun, data structures help really lot. Once they are implemented properly, and encapsulated, they can be used again and again, also with very ease.  The main part lies in creating the data structure logic. The usage of it in any program becomes so easy.

Wednesday, May 16, 2007 7:13 PM
• Ok people.. I m asking some questions...

1st general one,then i will start asking my assignment questions.. they are 1 liner easy questions.. this way you will get some good questions to answer and also this question bank is from a Companies placement preparation kit.. so it will be also useful to you,....

Thursday, May 17, 2007 5:52 PM
• Q1.) What is data structure.

Q2.) What is data type

Q3.) What is linear Data structure

Q4.) What is non-linear Data Structure

Q5.) What is the difference between data type and data structure.
Thursday, May 17, 2007 5:55 PM
• Ans.1.

In the field of computer science, a data structure is a way of storing data in a computer so that it can be used efficiently. Often a carefully chosen data structure will allow the most efficient algorithm to be used. The choice of the data structure often begins from the choice of an abstract data structure. A well-designed data structure allows a variety of critical operations to be performed, using as few resources, both execution time and memory space, as possible. Data structures are implemented using the data types, references and operations on them provided by a programming language.

Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to certain tasks. For example, B-trees are particularly well-suited for implementation of databases, while routing tables rely on networks of machines to function.

In the design of many types of programs, the choice of data structures is a primary design consideration, as experience in building large systems has shown that the difficulty of implementation and the quality and performance of the final result depends heavily on choosing the best data structure. After the data structures are chosen, the algorithms to be used often become relatively obvious. Sometimes things work in the opposite direction - data structures are chosen because certain key tasks have algorithms that work best with particular data structures. In either case, the choice of appropriate data structures is crucial.

This insight has given rise to many formalised design methods and programming languages in which data structures, rather than algorithms, are the key organising factor. Most languages feature some sort of module system, allowing data structures to be safely reused in different applications by hiding their verified implementation details behind controlled interfaces. Object-oriented programming languages such as C++ and Java in particular use classes for this purpose.

Since data structures are so crucial to professional programs, many of them enjoy extensive support in standard libraries of modern programming languages and environments, such as C++'s Standard Template Library, the Java API, and the Microsoft .NET Framework.

The fundamental building blocks of most data structures are arrays, records, discriminated unions, and references. For example, the nullable reference, a reference which can be null, is a combination of references and discriminated unions, and the simplest linked data structure, the linked list, is built from records and nullable references.

There is some debate about whether data structures represent implementations or interfaces. How they are seen may be a matter of perspective. A data structure can be viewed as an interface between two functions or as an implementation of methods to access storage that is organized according to the associated data type

I know i have copied and pasted from a website, but i think i wouldn't be able to explain much better than the one that i posted above
Thursday, May 17, 2007 6:48 PM
• Ans.2.

A data type is a constraint placed upon the interpretation of data in a type system in computer programming. Common types of data in programming languages include primitive types (such as integers, floating point numbers or characters), tuples, records, algebraic data types, abstract data types, reference types, classes and function types. A data type describes representation, interpretation and structure of values manipulated by algorithms or objects stored in computer memory or other storage device. The type system uses data type information to check correctness of computer programs that access or manipulate the data.
Thursday, May 17, 2007 6:48 PM
• Even I can search and post the answers here.. but the basic purpose is that people search for the answers and in the progress they will learn new things.. so it dosent matter if you copy paste the answers.. you have to just study them, it is the only requirement...

Also where are the other people interested in the Data Structures.. I have a list of 70 questions.. and if only 1 person is going to answer, then i will just forward the list to him directly...

Wake up people and start searching for the answers...
Friday, May 18, 2007 3:25 AM
• I agree with you Varun. One can post the answers frmo the other sites, while that also promotes himself learning about the same.

Where are the other guys ? why have you become cold ? Guys this is really a good topic to discuss about. I think people are tired to learn new things .
Friday, May 18, 2007 5:50 AM
• yes, this really charges everyoneup to learn new things at the same time share also....so keep up the good work guys and lets continue to shower the knowledge....
Monday, May 21, 2007 11:55 AM
• Someone please post the answer to the rest of the questions. What is everyone doing ? And varun after the answers are given, start posting the other questions that you have of Data Structuers. Even if no one is interested, i am surely interested in it
Monday, May 21, 2007 2:06 PM

### All replies

• Sure varun...

I am also interested in DS...

Wednesday, April 25, 2007 5:01 PM
• Yes, I am too interested in Data Structures.
Thursday, April 26, 2007 12:23 PM

I think how about discussing the sorting techniques... What are their uses and how they are better in different situations...

I have studied
Selection sort
Bubble sort
Insertion Sort
Shell Sort
Merge Sort
Quick Sort

Thursday, April 26, 2007 1:44 PM
• Same here...

Have u studied Heap Sort??

Thursday, April 26, 2007 4:49 PM
• we do have heap sort in course but its still to cover.. will be doing it in next 10 days..
i forgot to mention the Radix sort.. we have also done that...

Well merge sort is the fastest, but it eats up lot of memory, the best thing in merge sort is that it dosent have any worse case.. where else you would find a worse case for every other sorting technique..

does anyone have the code for this sorts?? I have written them in C, would share it here...
Also would like others to share their code first..

We can discuss on them and find out if we can get something even better than what we have
Thursday, April 26, 2007 6:35 PM
• heres my code sample for selection sort...share yours too

Code Snippet

for(int x=0; x<n; x++)

{

int index_of_min = x;

for(int y=x; y<n; y++)

{

if(array[index_of_min]<array[y])

{

index_of_min = y;

}

}

int temp = array[x];

array[x] = array[index_of_min];

array[index_of_min] = temp;

}

The first loop goes from 0 to n, and the second loop goes from x to n, so it goes from 0 to n, then from 1 to n, then from 2 to n and so on. The multiplication works out so that the efficiency is n*(n/2), though the order is still O(n^2).

Friday, May 4, 2007 10:01 PM
• Well buddy mine is same... but i will give you a code which will help you compare the selection sort and the bubble sort in real time...

have a look at this
//WAP to sort a big list using selection sort and bubble sort to see the time diff..

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<time.h>
#define length 30000
void generate(int list[]);
void bubblesort(int list[]);
void selectionsort(int list[]);

void main()
{
int i;
int list[length];
float start, end;
clrscr();
generate(list);
start = clock();

bubblesort(list);
end = clock();

printf("Sorted using bubble sort\n");
printf("Time taken = %f press a key....", (end-start)/CLK_TCK);

getch();
generate(list);
start = clock();
selectionsort(list);
end = clock();
printf("The list is sorted using Selection sort\n");
printf("Time taken = %f press a key....", (end-start)/CLK_TCK);

getch();
}

void generate(int list[])
{
int i;
for(i=0;i<length;i++)
list[i] = random(30000);
}

void bubblesort(int list[])
{
int i, j, min;
for (i=length-1;i>0; i--)
{
for(j=0; j<i; j++)
{
if (list[j+1] < list[j])
{
min = list[j+1];
list[j+1] = list[j];
list[j] = min;
}
}
}
}

void selectionsort(int list[])
{
int i, j, min, min_scorer;
for(i=0;i<length-1;i++)
{
min = list[i];
min_scorer = i;
for(j=i+1; j<length; j++)
{
if(list[j] < min)
{
min = list[j];
min_scorer = j;
}
}
list[min_scorer] = list[i];
list[i] = min;
}
}

/*            OUTPUT
Sorted using bubble sort
Time taken = 4.175824 press a key....
The list is sorted using Selection sort
Time taken = 0.934066 press a key....
*/

Saturday, May 5, 2007 2:31 AM
• I know that its not good code, but i have created these when i was in 2nd year of my BCA,  at tha time i was just a starter but the programs work exactly as the algorithm says
Bubble Sort :

#include<stdio.h>
#include<conio.h>

int BUB_SORT (int arr[],int n)
{
int i,k,temp,ptr;
for (i=0 ; i<n-1 ; i++)
{
ptr = 0;
printf("Phase : %d\n",i+1);
while (ptr<n-i)
{
if (arr[ptr] > arr[ptr+1] )
{
temp = arr[ptr];
arr[ptr] = arr[ptr+1];
arr[ptr+1] = temp;
}
ptr = ptr+1;
for (k=0 ; k<n ; k++)
{
printf("%3d",arr[k]);
}
printf("\n");
}
}
return *arr;
}

void main()
{
int arr[11];
int temp, ptr, k, n=11,i=1;
clrscr();
printf("Enter now many numbers do you wantto sort : ");
scanf("%d",&n);
for (k=0 ; k<n ; k++)
{
printf("Enter arr[%d] : ",k);
scanf("%d",&arr[k]);
}
BUB_SORT(arr,n);
printf("\n");
for (k=0 ; k<n ; k++)
{
printf("%3d",arr[k]);
}
getch();
}
Saturday, May 5, 2007 4:13 AM

• Insertion sort

#include<stdio.h>
#include<conio.h>

int INS_SORT(int arr[],int n)
{
int k,ptr,i,temp;
arr[0] = -32768;
for (k=2 ; k<n ; k++)
{
temp = arr[k];
ptr = k-1;
while (temp < arr[ptr] )
{
arr[ptr+1] = arr[ptr];
ptr = ptr-1;
}
arr[ptr+1] = temp;
}
return *arr;
}

void main()
{
int arr[11];
int temp, ptr, k, n=11,i=1;
clrscr();
printf("Enter now many numbers do you wantto sort : ");
scanf("%d",&n);
n++;
for (k=1 ; k<n ; k++)
{
printf("Enter arr[%d] : ",k-1);
scanf("%d",&arr[k]);
}

arr[0] = -32768;
INS_SORT(arr,n);

for (k=1 ; k<n ; k++)
{
printf("%3d",arr[k]);
}
getch();
}
Saturday, May 5, 2007 4:14 AM

• Quick Sort:

#include<stdio.h>
#include<conio.h>

int QCK_SORT(int arr[], int lb, int ub)
{
int flag=1,i,j,key,temp;
if (lb < ub)
{
i=lb;
j=ub+1;
key = arr[lb];
while (flag)
{
i=i+1;
while (arr[i] < key)
{
i=i+1;
}
j=j-1;
while (arr[j] > key)
{
j=j-1;
}
if (i<j)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
else
{
flag = 0;
}
}
temp = arr[lb];
arr[lb] = arr[j];
arr[j] = temp;
QCK_SORT(arr,lb,j-1);
QCK_SORT(arr,j+1,ub);
}
return *arr;
}
void main()
{
int arr[11];
int temp, ptr, k, n=11,i=1,lb=0,ub;
clrscr();
printf("Enter now many numbers do you want to sort : ");
scanf("%d",&n);
ub = n;
for (k=0 ; k<n ; k++)
{
printf("Enter arr[%d] : ",k);
scanf("%d",&arr[k]);
}
QCK_SORT(arr,lb,ub);
for (k=0 ; k<n ; k++)
{
printf("%3d\t",arr[k]);
}
getch();
}
Saturday, May 5, 2007 4:14 AM

• Selection Sort :

#include<stdio.h>
#include<conio.h>

int SEL_SORT (int arr[],int n)
{
int i,x,temp,y;
for (i=0 ; i<n ; i++)
{
x=MIN(arr,i,n);
temp = arr[i];
arr[i] = arr[x];
arr[x] = temp;
}
return *arr;
}

int MIN(int arr[],int i, int n)
{
int min,x,loc;
min = arr[i];
loc = i;
for (x=i+1 ; x<n+1 ; x++)
{
if (min > arr[x] )
{
min = arr[x];
loc = x;
}
}
return loc;
}

void main()
{
int arr[11];
int temp, ptr, k, n=11,i=1;
clrscr();
printf("Enter now many numbers do you want to sort : ");
scanf("%d",&n);
for (k=0 ; k<n ; k++)
{
printf("Enter arr[%d] : ",k);
scanf("%d",&arr[k]);
}
SEL_SORT(arr,n);

for (k=0 ; k<n ; k++)
{
printf("%3d\t",arr[k]);
}
getch();
}
Saturday, May 5, 2007 4:15 AM
• Well buddy as i had guessed, your quick sort code has a problem.. please try running it.. this was the problem that i used to face... the last elemnt in the array is lost and a garbage is assigned...

I will show you my code.. this code also give step by step values of the array as things change... I m sure you will like it...
// This program sorts the data by using Quick Sort Technique...

#include<stdio.h>
#include<conio.h>
void quicksort(int list[], int start, int end);
int size;
void main()
{
int list[30], i;
//    clrscr();
printf("Please give the size of the list : ");
scanf("%d",&size);
for(i=0;i<size;i++)
scanf("%d",&list[i]);

quicksort(list, 0, size-1);
printf("\nThe Sorted List : ");
for(i=0;i<size;i++)
printf("%d ",list[i]);

getch();
}

void quicksort(int list[], int start, int end)
{
int z, i=start, j=end-1, pivot, tmp;

printf("The Unsorted List : ");
for(z=0;z<size;z++)
printf("%d ",list[z]);
printf("\n");
pivot = list[end];
printf("Pivot %d Start %d end %d \n",pivot, list[i], list[j]);
while(i<=j)
{
while(list[i]<=pivot && i<=j)
i++;
while(list[j]>=pivot && i<=j)
j--;
if(i<=j)
{
tmp = list[i];
list[i] = list[j];
list[j] = tmp;
}
}
list[end] = list[i];
list[i] = pivot;
printf("List After Shifting the elements :");
for(z=0;z<size;z++)
printf("%d ",list[z]);
printf("\n i = %d j = %d\n",i,j);

if(start<i-1)
quicksort(list,start, i-1);
if(end>j+1)
quicksort(list,j+1,end);
}

/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Output
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Please give the size of the list : 8
4 8 3 7 5 1 2 6
The Unsorted List : 4 8 3 7 5 1 2 6
Pivot 6 Start 4 end 2
List After Shifting the elements :4 2 3 1 5 6 8 7
i = 5 j = 4
The Unsorted List : 4 2 3 1 5 6 8 7
Pivot 5 Start 4 end 1
List After Shifting the elements :4 2 3 1 5 6 8 7
i = 4 j = 3
The Unsorted List : 4 2 3 1 5 6 8 7
Pivot 1 Start 4 end 3
List After Shifting the elements :1 2 3 4 5 6 8 7
i = 0 j = -1
The Unsorted List : 1 2 3 4 5 6 8 7
Pivot 4 Start 1 end 3
List After Shifting the elements :1 2 3 4 5 6 8 7
i = 3 j = 2
The Unsorted List : 1 2 3 4 5 6 8 7
Pivot 3 Start 1 end 2
List After Shifting the elements :1 2 3 4 5 6 8 7
i = 2 j = 1
The Unsorted List : 1 2 3 4 5 6 8 7
Pivot 2 Start 1 end 1
List After Shifting the elements :1 2 3 4 5 6 8 7
i = 1 j = 0
The Unsorted List : 1 2 3 4 5 6 8 7
Pivot 7 Start 6 end 8
List After Shifting the elements :1 2 3 4 5 6 7 8
i = 6 j = 5

The Sorted List : 1 2 3 4 5 6 7 8
*/

Saturday, May 5, 2007 1:14 PM
• @Varun, i ahve tried the code in TC, and it works fine . There seems nothign wrong in the quicksort logic, May be in other compilers there is something scricter in return the pointers, ilke "Cannot return reference to localvariable" stuffs, and may be thats why you are facing the problem ?

I have tried it for 10 elements, and it worked perfectly, and no garbage. The logic of your code, and my code, seems the same, except that you have coded it differently.

If you find out why my code behaves strangely at your end, then do let me know We can get to know something new
Saturday, May 5, 2007 2:10 PM
• Yo harshil i found the problem... the problem is in the code....
now what you pass from the main as the value of ub i.e. n is wrong.. it should be n-1,
because we pass the value of the address of the last array element...
i.e. lets say when you have 10 elements, the last adress would be 9 and not 10...
but you have passed the value of 10, which creates a problem....

now here is the reason why you were not able to trace it...
What i did was that i displayed the whole array eveytime quicksort is called... this is what i found..
I tried it on VC++ first.. so in VC the garbage value was negative, i.e. it is the smallest, so it gets to the place 1 and so we get a garbage their...
Now in Turbo, there is some very big positive value as garbage, due to it this value stays at the end of the array and so we dont get to notice it...

So, in short, while calling the quicksort function,
it should not be     QCK_SORT(arr,lb,ub);
but it should be    QCK_SORT(arr,lb,ub-1);

Try out this.. this will make your code perfect...
And yes our logic are same, we both are doing the Standard Quick Sort...

If anyone is having a difficulty in Quick sort, tell us.. we would explain how it works..
Saturday, May 5, 2007 3:33 PM
• Hey Varun, Thanks for pointing out the mistake. But i have a clarification for that. I porpusely put ub, cause as you can see in my code, i have put j-- before entering into the loop, so when ub will be passed into the function as j, it will decrement first , so its value will be one less than what ever it is.

But i also agree with you, that we enter the adderss of the last element, but i have done it a different way. I agree with your clarification, and i stand with it  No such problems ...
Saturday, May 5, 2007 4:34 PM
• Hey friends,

i have complete notes on data structures . i hope, it will be useful to me and everyone who r here. so keep gathering and sharing knowledge.

the link for the file is :

http://rapidshare.com/files/29661021/data_structures.pdf

Bye

Saturday, May 5, 2007 6:21 PM
• Thanks Sunil for the help
Saturday, May 5, 2007 6:41 PM
• Why data structure programs are so long?
Saturday, May 5, 2007 7:13 PM
• thanks varun for that comparison program, it was indeed, a good one, i had known the difference in time for processing, but your ur program worked it out practically......

Sunil_Raj_fd640cmscomforums wrote:
 Hey friends,   i have complete notes on data structures . i hope, it will be useful to me and everyone who r here. so keep gathering and sharing knowledge.   the link for the file is :   http://rapidshare.com/files/29661021/data_structures.pdf   Bye

common yaar, you should atleast make sure, before posting a link, that its not broken, there is not file existing at the place of link provided by you....

Deepak_Sharma_1d9447 wrote:
 Why data structure programs are so long?

Well, good question, but i dont think they are really long, because if you see actual c programs at the machine level, then these data structure programs are just ants...

But do notice one thing, although they are long, they are quite simple to understand, because they have a simple logic....

Saturday, May 5, 2007 7:40 PM
• yaar Anoop

i have uploaded the best source of information and full notes regarding data structures. i tried just now also when u said there was no file. its working successfully. its an acrobat file type of notes containing 179 pages of notes. i hope u try once. if again problem arises, plz tell me without any hesitation.  i will upload any new one.

No quarrels or misunderstandings.  lets rock everybody

Bye

Sunday, May 6, 2007 2:47 AM
• The link is working guys and its really good...
Thankz Sunil.. even i have some stuff of data structures.. tell me where to upload them.. i will do it if you want so...

And please share more of such stuff if anyone has so....
Sunday, May 6, 2007 4:41 AM
• Yes friends, the link is working perfectly fine, i have even downloaded, and its good source of information if you want to really go deep into structures.

And about the size of the datastructures programs, if you can see theere is lto of logic written in the void main itself we just have one line calling the function that performs the operatin. And that function aint that big. Also the logic is simple ....... Just ignore the main() part, and concentrate no the core, you will feel that its easy and also very good.
Sunday, May 6, 2007 4:55 AM
• Thnx friends for ur kind support . i would like to upload still more , if u wish to have.

just simple, go to www.rapidshare.com. in the main screen, u will find browse button. put ur notes which is located in ur pc and upload it. after uploading, the link will be dispalyed. copy the link.

Thats it. u have done!!!!!!

Bye

Sunday, May 6, 2007 7:04 AM
Sunday, May 6, 2007 9:45 PM
• Hey Anoop,

Come on yaar, no need of saying thnx. its a knowledge . i believing in sharing the knowledge rathar than hiding. i would be happy if that could be useful to u and all. and i would like to learn which i doesn't knowbecause i am nt a genius . would u plz help me??

Keep sharing the knowledge.

Bye

Monday, May 7, 2007 2:37 AM
•  Sunil_Raj_fd640cmscomforums wrote:
 Thnx friends for ur kind support . i would like to upload still more , if u wish to have. Varun, u asked that where to upload naa? just simple, go to www.rapidshare.com. in the main screen, u will find browse button. put ur notes which is located in ur pc and upload it. after uploading, the link will be dispalyed. copy the link. Thats it. u have done!!!!!! Bye

Thankz for it buddy.. i will upload the stuff as soon as my exams are over.. will get buddy for the next week now... hope you all will continue over here...
Monday, May 7, 2007 4:01 AM

#include<stdio.h>
#include<conio.h>
#include<alloc.h>

struct node
{
int data;
};

void main()
{
struct node *p;
clrscr();
p = NULL;
append(&p,10);
append(&p,20);
append(&p,30);
append(&p,40);
display(p);
insert(p,20,25);
printf("\n");
display(p);
del(p,0);
printf("\n");
display(p);
getch();
}

append (struct node **q, int num)
{
struct node *temp,*r;
if (*q == NULL)
{
temp = (struct node *) malloc(sizeof(struct node));
temp->data = num;
*q = temp;
}
else
{

temp = *q;
r = (struct node *) malloc(sizeof(struct node));
r->data = num;
{
}

}
return 0;
}

display (struct node *q)
{
while (q!=NULL)
{
printf("\n<<<%5d>>>",q->data);
}
return 0;
}

insert (struct node *q,int loc,int num)
{
struct node *r;
while (q!=NULL)
{
if (q->data == loc)
{
//            printf("found");
break;
}
}
r = (struct node *) malloc (sizeof(struct node));
r->data = num;
return 0;
}

del (struct node *q, int num)
{
struct node *p;
p = 0;
while (q !=NULL)
{
if (num == 0)
{
}
else
if (q->data == num)
{

}
p = q;
}

}
Monday, May 7, 2007 9:36 AM

# include<stdio.h>
# include<conio.h>
# include<alloc.h>

struct node
{
int data;
};
void main()
{
struct node *p,*a,*temp;
clrscr();
p = NULL;
a = NULL;
append(&p,10);
append(&p,11);
append(&p,12);
append(&p,13);
append(&p,14);
append(&a,15);
append(&a,16);
append(&a,17);
append(&a,18);
disp(p);
printf("\n");
disp(a);
printf("\n");
merge(p,a);
printf("\n\n\n");
disp(p);
printf("\n\n\n");
del(&p,10);
printf("\n\n\n");
disp(p);
getch();
}
append(struct node **q,int num)
{
struct node *temp,*r;
temp = *q;
if(*q == NULL)
{
r = (struct node *)malloc(sizeof (struct node));
r->data = num;
*q = r;
}
else
{
{
}
r = (struct node *)malloc(sizeof (struct node));
r->data = num;
}
return 0;
}
disp(struct node *q)
{
while(q != NULL)
{
printf("%5d",q->data);
}
return 0;
}

merge(struct node *b,struct node *c)
{
struct node *temp;
temp = b;
{
}
return 0;
}
del(struct node **q, int num)
{

struct node *prew,*temp;
prew = NULL;
temp = *q;
while(1)
{
printf("%5d",temp->data);
if(num == temp->data)
{
printf("\n{Found %5d}",temp->data);
printf("prew = %5d",prew->data);
if(prew == NULL)
{
printf("first element:");
}
else
{
}
break;
}
{
break;
}
prew = temp;
}
return 0;
}

Monday, May 7, 2007 9:37 AM

• Linked List : Insertion and Deletion

#include<stdio.h>
#include<conio.h>
#include<alloc.h>

struct node
{
int data;
};
void main()
{
struct node *p;
int x,loc=0,cnt=0;
clrscr();
p=NULL;
while (1)
{
if (cnt !=0)
{
printf("\nEnter the position \n\t0 = start of list\n\tafter NUM(loc)\n : ");
scanf("%d",&loc);
}
cnt++;
if (loc == -1)
{
disp(p);
getch();
break;

}
printf("Enter number to insert : ");
scanf("%d",&x);
if (x==-1)
{
disp(p);
getch();
break;
}
insert (&p,x,loc);
disp(p);
printf("\n");
}
loc=1;
while (1)
{
if (loc == -1)
{
disp(p);
getch();
break;
}
printf("Del by value or loc:1 || 2");
scanf("%d",&loc);
if (loc == 1)
{
printf("Enter value to delete : ");
scanf("%d",&loc);
delval (&p,loc);
}
if(loc == -1)
{
disp(p);
getch();
break;
}
else
{
printf("Enter location to delete : ");
scanf("%d",&loc);
delloc (&p,loc);
}
disp(p);
}
getch();
}

insert (struct node **q , int num,int loc)
{
struct node *temp,*r;
int i=1;
temp = *q;
if (loc == 0)
{
r =(struct node *)malloc(sizeof(struct node));
r->data = num;
*q  = r;
return 0;
}
else
{
for (i=1 ; i<loc || temp !=NULL  ; i++,    temp = temp->link)
{
if (i == loc)
{
printf("\nPosition Found\n");
r =(struct node *)malloc(sizeof(struct node));
r->data = num;
return 0;
}
}
}
{
printf("Invalid position [Check the size of the Link List ] \n");
}
return 0;
}

disp (struct node *q)
{
while (q!=NULL)
{
printf("%5d",q->data);
}
return 0;
}

delloc (struct node **q , int loc )
{
struct node *temp,*prev;
int i;
temp = *q;
if (loc == 1)
{
return 0;
}
prev = *q;
for (i=1 ; i<loc || temp !=NULL  ; i++,    temp = temp->link)
{
if (i == loc)
{
}
prev = temp;
}
{
printf("Invalid position [Check the size of the Link List ] \n");
}
return 0;
}
delval (struct node **q , int num )
{
struct node *temp,*prev;
int i;
temp = prev = *q;
while (temp!=NULL)
{
if (temp->data == num)
{
if (prev == *q)
{
}
else
{
}
return 0;
}
prev = temp;
}
printf("Invalid position [Check the size of the Link List ] \n");
return 0;
}
Monday, May 7, 2007 9:38 AM

• Tower of Hanoi : Recursion (Usage of inbuilt stacks)

#include<stdio.h>
#include<conio.h>

int CNT=1;

void hanoi (int n, char a, char b, char c)
{
if (n==1)
{
printf(" %3d. Move %2d disk from %c->%c\n",CNT++,n,a,c);
return;
}
else
{
hanoi(n-1,a,c,b);
printf(" %3d. Move %2d disk from %c->%c\n",CNT++,n,a,c);
hanoi(n-1,b,a,c);
return;
}
}
void main()
{
int no;
clrscr();
printf("Enter no of disks : ");
scanf("%d",&no);
clrscr();
printf("n = %d\n",no);
hanoi(no,'A','B','C');
getch();
}
Monday, May 7, 2007 9:40 AM

• Stack Implementation : Convert Infix Notation to PostFix Notation

#include<stdio.h>
#include<conio.h>

int PRIORITY(char ch)
{
if (ch=='(' || ch==')')
return 4;
else if (ch=='^')
return 3;
else if (ch=='*' || ch=='/')
return 2;
else if (ch=='+' || ch=='-')
return 1;
else
return 0;
}

void main()
{
char stack[40],p[40];
char str[40]={"a+(b*c-(d/e^f)*g)*h"};
int top=-1,p_cnt=0;
int i,j,k,len;
clrscr();
printf("Enter any Infix Equation  : ");
gets(str);
printf("\nSymbol\t\tStack\t\tPostfix");
len=strlen(str);
str[len]=')';
str[len+1]='\0';
for (i=0 ; str[i] ; i++)
{
if (i==0)
{
stack[++top]='(';
printf("\n\t\t(\n\r");
}
printf("%c\t\t",str[i]);
if ( (str[i]>='a' && str[i]<='z') || (str[i]>='A' && str[i]<='Z')  || (str[i]>='0' && str[i]<='9') )
{
p[p_cnt++]=str[i];
}
else
{
if (str[i]!=')')
{
if (PRIORITY(str[i]) > PRIORITY(stack[top]) || (stack[top]=='(') )
{
stack[++top]=str[i];
}
else
{
p[p_cnt++]=stack[top];
stack[top]=str[i];
}
}
else if (str[i]==')')
{
while (stack[top]!='(')
{
p[p_cnt++]=stack[top--];
}
top--;
}
}
for (j=0 ; j<=top ; j++)
{
printf("%c",stack[j]);
}
printf("\t\t");
for (j=0 ; j<p_cnt ; j++)
{
printf("%c",p[j]);
}
printf("\n");
delay(100);
}
for (j=0 ; j<=top ; j++)
{
printf("%c",stack[j]);
}
getch();
}
Monday, May 7, 2007 9:41 AM

• Stack Implementation : Evaluating a Postfix Expression

#include<math.h>
#include<stdio.h>
#include<conio.h>

void main()
{
char str[40]={"53+2*697-/-"};
int stack[40];
int i,j,top=-1,a,b;
clrscr();
printf("Enter any Postfix Equation : ");
//    gets(str);
str[strlen(str)]=')';
str[strlen(str)+1]='\0';
printf("\n\n");
printf("Symbol\t\tStack\n");

for (i=0 ; str[i]!=')' ; i++)
{
printf("%3c\t\t",str[i]);
if (str[i]>='0' && str[i]<='9')
{
stack[++top]=str[i]-48;
}
else
{
a=stack[top--];
b=stack[top--];
if (str[i]=='+')
stack[++top]=b+a;
if (str[i]=='-')
stack[++top]=b-a;
if (str[i]=='/')
stack[++top]=b/a;
if (str[i]=='*')
stack[++top]=b*a;
if(str[i]=='^')
stack[++top]=pow(b,a);
}
for (j=0 ; j<=top ; j++)
{
printf("%2d,",stack[j]);
}
printf("\b \n");
delay(100);
}
printf("\n\n ANS = %d",stack[top]);
getch();
}
Monday, May 7, 2007 9:42 AM
•  Sunil_Raj_fd640cmscomforums wrote:
 Hey Anoop, Come on yaar, no need of saying thnx. its a knowledge . i believing in sharing the knowledge rathar than hiding. i would be happy if that could be useful to u and all. and i would like to learn which i doesn't knowbecause i am nt a genius . would u plz help me??   Keep sharing the knowledge.   Bye

sure man!!!

Tuesday, May 8, 2007 10:45 AM
• some really good programs harshil.....
Tuesday, May 8, 2007 10:53 AM
• Really nice programs harshil, Specially the Hanoi one, I was looking for it for a long time...
But m still not clear with the functions... As it is the exams are going on so not able to concentrate  more on this rite now...
anyways thankz for the codes..
I will post mine codes afterwards.. most of them are in C++, rite now i m preparing codes in C++ for data structures,...
Tuesday, May 8, 2007 11:54 AM
• Yaar Varun,

Wishing u all the very best for ur exams

Tuesday, May 8, 2007 12:11 PM
• @Annop - Yes m8, i have done a lot of work on those programs i have done many more, but i just cant find where i have stored them. Ill post more when i find those

@Varun - Have a look at it later, you will see that its very easy, and also resembels the exact steps of solving the hanoi problem.

Tuesday, May 8, 2007 1:51 PM
• A simple but very imp Data structures question...

We all have studied Hashing Techniques... now in hashing technique we see that at all the place where we use modular, we use a prime number... can anyone tell me why a prime number ???
I tried searching for the answer but was not able to get one...
Wednesday, May 9, 2007 4:03 PM
• The reason i think why prime values are used specially large prime numbers, because the hash value thus generated by the hash function can be different as far as possible.
But instead if we dont use a prime number, we will get many of its factors, and hence the hash value thus generated can be repetitive and around the factors.

The main desirable property of the hash function is that, it should generate different values most of the time, and not take much time to calculate.

I guess from the 1st desirable property, we can try to guess out the use of a prime number.

Also in Encryption techniques, especially in RSA , prime numbers are also used , for the same very purpose.
Wednesday, May 9, 2007 4:37 PM
• Hey guys where is everyone?? Why has the disscussion been stopped here... lets talk about something new....

I have just witnessed a new problem, Actually our Sir was talking about it...

There was a Traveling Company's Website project... now the website helped the user to plan out a trip in India... but the project lacked something... i.e. Website was not able to show near by places as options.. for e.g. I m searching for Ahmedabad, then the website could have shown me nearby places, like Vadodra, Gandhinagar, Maninagar.. etc.. all the famous places around my searched place...

Now let us try to solve it using Data Strucutres.. how can we do it?? how can we make the Website more intelligent ???
Tuesday, May 15, 2007 9:29 AM
• I think this is a bit twisted. But we can implement it using a collection or a link list.

May be the structure of a node in the link list can have a pointer to a LINKED-LIST that contains the neighbourhood cities/places ID.

and each node in the main link list, will have a unique ID corresponding to the city. May be this idea can work ?

I think others can discuss more about it.
Tuesday, May 15, 2007 10:33 AM
• varun i think, its similar to travelling saleperson problem?..isnt it?.....
Tuesday, May 15, 2007 6:57 PM
• Well the actual problem is to store the data in such a way that we can retrive the logically connected data easily...

So for that i saw 2 options using data structures...

1. To store the data in a Multiway tree, this way we can get the connected data from that node only....

2. Better option :- storing the data in a graph.. so that all the nodes are connected and we get the near by nodes from it.....

What do you say?? disuss more on it.. this is the practilce application of the structures that we studied..
Wednesday, May 16, 2007 11:57 AM
• I guess thats what i have said in my earlier post. The datastructure that i explained is a graph. But i explained it more programmatically .

The graph would be the best datastructure. And it would also resemble the real world's map.

Have a graph, and have it indexed and pointing to the nodes in the graph, so that searching for a particular location can be easy and faster. After finding the node in the graph, we can easily find its neighbours.

Wednesday, May 16, 2007 1:16 PM
• ya thatz rite... you suggested the same thing..
So isnt the data structures great.. I have also heard that Google uses a lot of data strucutres.. this is the reason that it is so fast...

So lets try this.. give out the practicle applications of data structres.. where they are practically applied.... like for trees, linklists and all
Wednesday, May 16, 2007 5:53 PM
• Yes Varun, data structures help really lot. Once they are implemented properly, and encapsulated, they can be used again and again, also with very ease.  The main part lies in creating the data structure logic. The usage of it in any program becomes so easy.

Wednesday, May 16, 2007 7:13 PM
• Ok people.. I m asking some questions...

1st general one,then i will start asking my assignment questions.. they are 1 liner easy questions.. this way you will get some good questions to answer and also this question bank is from a Companies placement preparation kit.. so it will be also useful to you,....

Thursday, May 17, 2007 5:52 PM
• Q1.) What is data structure.

Q2.) What is data type

Q3.) What is linear Data structure

Q4.) What is non-linear Data Structure

Q5.) What is the difference between data type and data structure.
Thursday, May 17, 2007 5:55 PM
• Ans.1.

In the field of computer science, a data structure is a way of storing data in a computer so that it can be used efficiently. Often a carefully chosen data structure will allow the most efficient algorithm to be used. The choice of the data structure often begins from the choice of an abstract data structure. A well-designed data structure allows a variety of critical operations to be performed, using as few resources, both execution time and memory space, as possible. Data structures are implemented using the data types, references and operations on them provided by a programming language.

Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to certain tasks. For example, B-trees are particularly well-suited for implementation of databases, while routing tables rely on networks of machines to function.

In the design of many types of programs, the choice of data structures is a primary design consideration, as experience in building large systems has shown that the difficulty of implementation and the quality and performance of the final result depends heavily on choosing the best data structure. After the data structures are chosen, the algorithms to be used often become relatively obvious. Sometimes things work in the opposite direction - data structures are chosen because certain key tasks have algorithms that work best with particular data structures. In either case, the choice of appropriate data structures is crucial.

This insight has given rise to many formalised design methods and programming languages in which data structures, rather than algorithms, are the key organising factor. Most languages feature some sort of module system, allowing data structures to be safely reused in different applications by hiding their verified implementation details behind controlled interfaces. Object-oriented programming languages such as C++ and Java in particular use classes for this purpose.

Since data structures are so crucial to professional programs, many of them enjoy extensive support in standard libraries of modern programming languages and environments, such as C++'s Standard Template Library, the Java API, and the Microsoft .NET Framework.

The fundamental building blocks of most data structures are arrays, records, discriminated unions, and references. For example, the nullable reference, a reference which can be null, is a combination of references and discriminated unions, and the simplest linked data structure, the linked list, is built from records and nullable references.

There is some debate about whether data structures represent implementations or interfaces. How they are seen may be a matter of perspective. A data structure can be viewed as an interface between two functions or as an implementation of methods to access storage that is organized according to the associated data type

I know i have copied and pasted from a website, but i think i wouldn't be able to explain much better than the one that i posted above
Thursday, May 17, 2007 6:48 PM
• Ans.2.

A data type is a constraint placed upon the interpretation of data in a type system in computer programming. Common types of data in programming languages include primitive types (such as integers, floating point numbers or characters), tuples, records, algebraic data types, abstract data types, reference types, classes and function types. A data type describes representation, interpretation and structure of values manipulated by algorithms or objects stored in computer memory or other storage device. The type system uses data type information to check correctness of computer programs that access or manipulate the data.
Thursday, May 17, 2007 6:48 PM
• Even I can search and post the answers here.. but the basic purpose is that people search for the answers and in the progress they will learn new things.. so it dosent matter if you copy paste the answers.. you have to just study them, it is the only requirement...

Also where are the other people interested in the Data Structures.. I have a list of 70 questions.. and if only 1 person is going to answer, then i will just forward the list to him directly...

Wake up people and start searching for the answers...
Friday, May 18, 2007 3:25 AM
• I agree with you Varun. One can post the answers frmo the other sites, while that also promotes himself learning about the same.

Where are the other guys ? why have you become cold ? Guys this is really a good topic to discuss about. I think people are tired to learn new things .
Friday, May 18, 2007 5:50 AM
• yes, this really charges everyoneup to learn new things at the same time share also....so keep up the good work guys and lets continue to shower the knowledge....
Monday, May 21, 2007 11:55 AM
• Someone please post the answer to the rest of the questions. What is everyone doing ? And varun after the answers are given, start posting the other questions that you have of Data Structuers. Even if no one is interested, i am surely interested in it
Monday, May 21, 2007 2:06 PM
• Sure buddy.. if no one else want to answer than let it be.. people it dosent take time to search for the answers, specially for data structures.. so start searching and post the answers.. then i will post more questions.. there is a long list for us to answer...
Monday, May 21, 2007 3:49 PM
• #include <stdio.h>
#include <conio.h>
#include <string.h>

void main(){
int i,n;
char name[15][20];
void namesort(char name[15][20], int);
clrscr();
printf("How many names u want to enter : ");
scanf("%d",&n);
printf("\n\n****Enter Input Data****\n");
for(i=0;i<n;i++){
flushall();
printf("Enter a name : ");
gets(name);
}
namesort(name,n);
printf("\n\n\n******After Sorting******\n");
for(i=0;i<n;i++)
printf("%s\n",name);
getch();
}

void namesort(char name[15][20],int n){
int i,j;
char *temp;
for(i=0;i<n;i++){
for(j=0;j<n-1;j++){
if(strcmp(name[j],name[j+1])>0){
strcpy(temp,name[j]);
strcpy(name[j],name[j+1]);
strcpy(name[j+1],temp);
}
}
}
}

Monday, May 21, 2007 4:30 PM
• @Varun, i think noone is interested in answering. I think you start posting the next set of questions, if noone want to answer, atleast they can know the questions and prepare if they want for their interview, or for their knowledge.
Monday, May 21, 2007 5:19 PM