5 Replies - 20133 Views - Last Post: 01 April 2007 - 10:19 PM Rate Topic: -----

#1 kkgaming  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 75
  • Joined: 07-February 07

Linked List Insertion Sort

Posted 30 March 2007 - 10:08 PM

Here is what I have so far for this linked list assignment, I am just trying to figure out how to get this part of the code to work reading from the infile or a file. Right now the numbers are randomly generated, I want to read them from the infile, I don't know how I would go about doing this.

 /* insertion sort */
	srand( time(0) );

	BasePtr start, p, add;
	int x;
	tmp = GetNode(0);
	start=tmp;

	for (i = 1; i < 10; ++i)
	{
		x = rand() % 100 + 1;
		//printf("Inserting %d\n", x);
		add = GetNode(x);
		p = FindInsLoc( start, add );
		start = InsertNodeAfter( start, p, add );
		//printf("Version %d: \n", i);
		//PrintList( start );
	}

	printf("Sorted list ----- \n");
	PrintList( start );



also I am not sure how to make it work for front of the list and
insert at front of list correctly.


Anyway, I am trying to do this part of the assignment (for the insertion sort)

# Input: File containing a list of Base 21 numbers

* Name of this file is supplied on the command line
* First element in file is number of entries
* You may assume all numbers have at most 4 digits

# Output File containing a sorted list of Base 21 numbers and the decimal equivalent

* Name of this file is supplied on the command line
* First element in file is number of entries


Here is what I got: Any help would be greatly apperciated.


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

/* --------------------------------------------------------------------- */

struct NumNodeType
{
	int dat;
	struct NumNodeType *next;
};

/* Define new type names:  BaseElem   and   BasePtr   
 * to refer to the list nodes.  These new names can
 * be used in place of struct NumNodeType and
 * struct NumNodeType *  repsectively.
 */
typedef struct NumNodeType BaseElem;
typedef struct NumNodeType * BasePtr;


/* --------------------------------------------------------------------- */

BasePtr GetNode( int val )
{
	BasePtr node;
	node = malloc( sizeof(BaseElem) );
	node->dat = val;
	node->next = NULL;
	return node;	
}


int Length( BasePtr first )
{
	BasePtr move;
	int len=0;
	move = first;
	while (move != NULL)
	{
		len++;
		move = move->next;
	}
	return len;
}


void PrintNode( BasePtr node )
{
	printf("Val: %d\n", node->dat);
}

void PrintList( BasePtr first )
{
	BasePtr move;
	move = first;
	while (move != NULL)
	{
		PrintNode( move );
		move = move->next;
	}
}

void PrintNodeFile( FILE *ofp, BasePtr node )
{
	fprintf(ofp, "Val: %d\n", node->dat);
}

void PrintListFile( FILE *ofp, BasePtr first )
{
	BasePtr move;
	move = first;
	while (move != NULL)
	{
		PrintNodeFile( ofp,  move );
		move = move->next;
	}
}

int Compare( int x, int y)
{
	if (x < y) return -1;
	else if (x == y) return 0;
	else if (x > y) return 1;
}

BasePtr FindInsLoc( BasePtr first, BasePtr node )
{
	BasePtr move, prev;
	int val1, val2;
	int res = -1;
	val2 = node->dat;
	move = first;
	prev = move;

	val1 = move->dat;
	res = Compare( val1, val2 );

	while ( res < 0 && move != NULL)
	{
		prev = move;
		move = move->next;
		if (move != NULL)
		{
			val1 = move->dat;
			res = Compare( val1, val2 );
		}
	}	
	return prev;
}

BasePtr InsertNodeAfter( BasePtr first, BasePtr loc, BasePtr node)
{
	//printf("Insert %d after %d\n", node->dat, loc->dat);
	node->next = loc->next;
	loc->next = node;
	return first;
}


/* --------------------------------------------------------------------- */

int main( int argc, char *argv[] )
{
	BasePtr head, tail, tmp;
	int i;

	FILE *infile, *outfile;
	/* verify that 2 parameters were passed */	
	if ( argc != 3)
	{
		printf("Usage: a.out infile outfile\n");
		return 1;
	}
	/* open input file */
	infile = fopen( argv[1], "r");
	if (!infile)
	{
		printf("ERROR: file %s not available\n", argv[1]);
		return 1;	
	}
	/* open output file */
	outfile = fopen( argv[2], "w");
	if (!outfile)
	{
		printf("ERROR: file %s not available\n", argv[2]);
		return 1;	
	}

	tmp = GetNode(1);
	head=tmp;
	tail=tmp;

	for (i = 2; i <= 7; ++i)
	{
		tmp = GetNode(i);
		tail->next = tmp;
		tail = tmp;
	}

	PrintList( head );

	fprintf(outfile, "Starting --\n");
	PrintListFile(outfile, head );
	fprintf(outfile, "Stopping --\n");
	i = Length( head );
	printf("List size: %d\n", i); 


	
  /* insertion sort */
	srand( time(0) );

	BasePtr start, p, add;
	int x;
	tmp = GetNode(0);
	start=tmp;

	for (i = 1; i < 10; ++i)
	{
		x = rand() % 100 + 1;
		//printf("Inserting %d\n", x);
		add = GetNode(x);
		p = FindInsLoc( start, add );
		start = InsertNodeAfter( start, p, add );
		//printf("Version %d: \n", i);
		//PrintList( start );
	}

	printf("Sorted list ----- \n");
	PrintList( start );

	return 0;
}



This post has been edited by kkgaming: 01 April 2007 - 07:33 PM


Is This A Good Question/Topic? 1
  • +

Replies To: Linked List Insertion Sort

#2 kkgaming  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 75
  • Joined: 07-February 07

Re: Linked List Insertion Sort

Posted 01 April 2007 - 07:29 PM

I am not exactly sure where to start with this base 21 part of the program, can anyone help?
Was This Post Helpful? 0
  • +
  • -

#3 lifeRoot  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 23
  • Joined: 01-April 07

Re: Linked List Insertion Sort

Posted 01 April 2007 - 08:34 PM

To read numbers from a file into a linked list I would do something to this effect:

FILE *fileP;
int i, num, numEntries;

//Associate the file pointer to the text file...
fileP = fopen(fileName, "r");

//Scan in number of entries...
fscanf(fileP, %d, &numEntries);

//Read in numbers till all the entries have been accounted for...
for(i=0; i<numEntries; i++) {
	
	 //Scan in number...
	 fscanf(fileP, %d, &num);
	
	 //Pass number to function that stores it in a linked list...
	 //"head" is the head of our linked list...
	 insert(head, num);
}



Now that we have all of our numbers in a linked list we can just use a simple sorting algorithm to sort it (bubblesort, qsort, etc..)

hope that helps:)
Was This Post Helpful? 0
  • +
  • -

#4 kkgaming  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 75
  • Joined: 07-February 07

Re: Linked List Insertion Sort

Posted 01 April 2007 - 09:37 PM

How would the function itself looked if I did it that way. I have a function already, but it isn't working... So you pass num and head up to the function, right?
Was This Post Helpful? 0
  • +
  • -

#5 lifeRoot  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 23
  • Joined: 01-April 07

Re: Linked List Insertion Sort

Posted 01 April 2007 - 09:58 PM

Well, if you are using linked lists and want to dynamically allocate memory as you read each number in I would do something like this:
//"ll" is my linked list

void insert(struct ll* head, int num) {

//First check to see if any nodes exists yet...
//If not... make the first node...
if (head == NULL) {
	 head->data = num;
	 head->next = NULL;
}

else {
	 //Create pointer to temporary nodes...
	 struct ll* temp = NULL;
		 struct ll* cur = NULL;

	 //Create new node...
	 temp = malloc(sizeof(struct ll));

	 //Add in data...
	 temp->data = num;

	 //Now we need to link the new node to the list...
	 //Move to the last node... 
	 while(cur->next != NULL)
		  cur = cur->next;

	 //Link nodes...
	 cur->next = temp;
}

}



I might be forgetting something but I think that's the basic's... I have a terrible memory :/

This post has been edited by lifeRoot: 01 April 2007 - 09:59 PM

Was This Post Helpful? 0
  • +
  • -

#6 kkgaming  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 75
  • Joined: 07-February 07

Re: Linked List Insertion Sort

Posted 01 April 2007 - 10:19 PM

I am getting a little confused.... Anyway here is my Printlist function:

void PrintList( BasePtr first )
{
	BasePtr move;
	move = first;
	while (move != NULL)
	{
		PrintNode( move );
		move = move->next;
	}
}


BasePtr is my linked list....

Here is my GetNode Function

//creates new nodes in list (call this function)
BasePtr GetNode( int val )
{
	BasePtr node;
	node = malloc( sizeof(BaseElem) );
	node->dat = val;
	node->next = NULL;
	return node;	
}


I am not sure how I would change this to what you told me:

/* insertion sort */
	srand( time(0) );

	BasePtr start, p, add;
	int x;
	tmp = GetNode(0);
	start=tmp;

	for (i = 1; i < 10; ++i)
	{
		x = rand() % 100 + 1;
		//printf("Inserting %d\n", x);
		add = GetNode(x);
		p = FindInsLoc( start, add );
		start = InsertNodeAfter( start, p, add );
		//printf("Version %d: \n", i);
		//PrintList( start );
	}

	printf("Sorted list ----- \n");
	PrintList( start );

	



here is full program as of now:

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

/* --------------------------------------------------------------------- */

struct NumNodeType
{
	int dat;
	struct NumNodeType *next;
};

/* Define new type names:  BaseElem   and   BasePtr   
 * to refer to the list nodes.  These new names can
 * be used in place of struct NumNodeType and
 * struct NumNodeType *  repsectively.
 */
typedef struct NumNodeType BaseElem;
typedef struct NumNodeType * BasePtr;


/* --------------------------------------------------------------------- */

BasePtr GetNode( int val )
{
	BasePtr node;
	node = malloc( sizeof(BaseElem) );
	node->dat = val;
	node->next = NULL;
	return node;	
}


int Length( BasePtr first )
{
	BasePtr move;
	int len=0;
	move = first;
	while (move != NULL)
	{
		len++;
		move = move->next;
	}
	return len;
}


void PrintNode( BasePtr node )
{
	printf("Val: %d\n", node->dat);
}

void PrintList( BasePtr first )
{
	BasePtr move;
	move = first;
	while (move != NULL)
	{
		PrintNode( move );
		move = move->next;
	}
}

void PrintNodeFile( FILE *ofp, BasePtr node )
{
	fprintf(ofp, "Val: %d\n", node->dat);
}

void PrintListFile( FILE *ofp, BasePtr first )
{
	BasePtr move;
	move = first;
	while (move != NULL)
	{
		PrintNodeFile( ofp,  move );
		move = move->next;
	}
}

int Compare( int x, int y)
{
	if (x < y) return -1;
	else if (x == y) return 0;
	else if (x > y) return 1;
}

BasePtr FindInsLoc( BasePtr first, BasePtr node )
{
	BasePtr move, prev;
	int val1, val2;
	int res = -1;
	val2 = node->dat;
	move = first;
	prev = move;

	val1 = move->dat;
	res = Compare( val1, val2 );

	while ( res < 0 && move != NULL)
	{
		prev = move;
		move = move->next;
		if (move != NULL)
		{
			val1 = move->dat;
			res = Compare( val1, val2 );
		}
	}	
	return prev;
}

BasePtr InsertNodeAfter( BasePtr first, BasePtr loc, BasePtr node)
{
	//printf("Insert %d after %d\n", node->dat, loc->dat);
	node->next = loc->next;
	loc->next = node;
	return first;
}


/* --------------------------------------------------------------------- */

int main( int argc, char *argv[] )
{
	BasePtr head, tail, tmp;
	int i;

	FILE *infile, *outfile;
	/* verify that 2 parameters were passed */	
	if ( argc != 3)
	{
		printf("Usage: a.out infile outfile\n");
		return 1;
	}
	/* open input file */
	infile = fopen( argv[1], "r");
	if (!infile)
	{
		printf("ERROR: file %s not available\n", argv[1]);
		return 1;	
	}
	/* open output file */
	outfile = fopen( argv[2], "w");
	if (!outfile)
	{
		printf("ERROR: file %s not available\n", argv[2]);
		return 1;	
	}

	tmp = GetNode(1);
	head=tmp;
	tail=tmp;

	for (i = 2; i <= 7; ++i)
	{
		tmp = GetNode(i);
		tail->next = tmp;
		tail = tmp;
	}

	PrintList( head );

	fprintf(outfile, "Starting --\n");
	PrintListFile(outfile, head );
	fprintf(outfile, "Stopping --\n");
	i = Length( head );
	printf("List size: %d\n", i); 


	/* now make it work some some random data; the above
	 * code is a test case in a controlled situation to make
	 * sure things appear to work
	 */
  /* insertion sort */
	srand( time(0) );

	BasePtr start, p, add;
	int x;
	tmp = GetNode(0);
	start=tmp;

	for (i = 1; i < 10; ++i)
	{
		x = rand() % 100 + 1;
		//printf("Inserting %d\n", x);
		add = GetNode(x);
		p = FindInsLoc( start, add );
		start = InsertNodeAfter( start, p, add );
		//printf("Version %d: \n", i);
		//PrintList( start );
	}

	printf("Sorted list ----- \n");
	PrintList( start );

	return 0;
}

This post has been edited by kkgaming: 01 April 2007 - 10:38 PM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1