Hi all,
Sorry if its a newbie post, but I'm currently trying to finish a program that sorts a binary search tree using the quicksort method. It seems like it should work, but whenever I run it, the program stops at a certain part in the program and encounters a bug or some sort of error. I've located where I think this bug is coming from, but haven't found a way to fix it.
Any help would be greatly appreciated!
Here is the code for the current state of the program, w/ some comments:
/* File: treeQSort.c
* This program uses the quicksort procedure to sort a given
* binary search tree with the help of arrays.
*/
#include <stdio.h>
#include "genlib.h"
#include "simpio.h"
#include "strlib.h"
#define size 8
typedef struct nodeT{
string key;
struct nodeT *left, *right;
} nodeT,*treeT;
string grtr[size];
string arr[size];
void InsertNode(treeT *tptr,string key) // Inserts nodes into the tree
{
treeT t;
int sign;
t=*tptr;
if(t==NULL){
t=New(treeT);
t->key = CopyString(key);
t->left = t->right = NULL;
*tptr = t;
return;
}
sign = StringCompare(key,t->key);
if(sign==0)return;
if(sign<0){
InsertNode(&t->left,key);
}
else {
InsertNode(&t->right,key);
}
}
void addnodes(treeT t, int i) // adds the nodes within the tree to arr
{
if(t!=NULL){
addnodes(t->left, i);
arr[i]=t->key;
i=i+1;
addnodes(t->right, i);
}
}
treeT putnodes(treeT t, int i) // transfers the sorted list of nodes to the tree
{
if(t!=NULL){
putnodes(t->left, i);
t->key=arr[i];
i++;
putnodes(t->right, i);
}
}
void DisplayTree(treeT t) // Displays the tree
{
if(t!=NULL){
DisplayTree(t->left);
printf("%s\n",t->key);
DisplayTree(t->right);
}
}
void quicksort(int l, int r) // Sorts the nodes using the quicksort procedure
{
int pos, i, n=0;
string pivot;
pos=l;
pivot=arr[pos];
arr[pos]=arr[l];
for(i=l+1;i<=r;i++)
{
if(StringLength(arr[i])>StringLength(pivot))
{
grtr[n]=arr[i];
n++;
}
if(StringLength(arr[i])<=StringLength(pivot))
{
arr[pos]=arr[i];
pos++;
}
// PROGRAM SEEMS TO BE ENCOUNTERING A BUG DURING THIS LOOP - TRIED TO FIND A WAY TO FIX IT,
// BUT I COULDN'T STOP THE BUG/ERROR FROM OCCURING
}
for(i=0;grtr[i]!=0;i++)
{
arr[(r+1)-n+i]=grtr[i];
}
for(i=0;i<size;i++)
{
grtr[i]=NULL;
}
arr[pos]=pivot;
if(pos-1>=0)
{
quicksort(0, pos-1);
}
if(r-pos>1)
{
quicksort(pos+1, r);
}
}
main()
{
int i, l=0, r=size-1;
treeT T=NULL;
for(i=0;i<size;i++)
{
grtr[i]=NULL;
}
printf("This program uses the quicksort procedure to sort a binary search tree\n");
printf("of strings, sorting by the length of each string node.\n");
InsertNode(&T,"ads");
InsertNode(&T->left,"agwrehse");
InsertNode(&T->left->right, "a");
InsertNode(&T->left->left, "aassadf");
InsertNode(&T->left->right->left, "dddeeeeeeeeee");
InsertNode(&T->right,"ffffffffffds");
InsertNode(&T->right->left, "sa");
InsertNode(&T->right->right,"gasdse");
printf("Here is the tree with unsorted nodes:\n\n");
DisplayTree(T);
i=0;
addnodes(T, i);
quicksort(l, r);
i=0;
T=putnodes(T, i);
printf("\n\nHere is the tree with its nodes sorted:\n\n");
DisplayTree(T);
getchar();
}
