LinuxQuestions.org
LinuxAnswers - the LQ Linux tutorial section.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices



Reply
 
Search this Thread
Old 05-04-2005, 09:38 PM   #1
dilberim82
Member
 
Registered: Apr 2001
Location: NY
Distribution: used to be Redhat, now Debian Sarge
Posts: 291

Rep: Reputation: 30
linked list + c


I have a linked list homework and i am almost done with it but for some reason i can not delete from the middle of the list... I've been working on this for the last 2 weeks and read tons of books but i cannot get it to work. Here is my code:

Code:
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int pid;
	int aTime;
	int cpuBurst;
	struct LINK * next;
}LINK;

LINK * deletenode(LINK *listPointer, int delvalue);
void printList(LINK * listPointer);
LINK * addjob(LINK *listPointer, int lpid, int laTime, int lcpuBurst);
LINK * nextjob(LINK * listPointer);

main(){

LINK listPid, listTime, listBurst, *listPointer;
int pdata, cdata;
int lpid, laTime, lcpuBurst, temp = 1;
listPointer = NULL;
int counter = 0;

printf("Enter number of processes that will be entered to PCB: ");
	 scanf("%d", &temp);
		
while(counter < temp)
{
	printf("\nEnter process id, arrival time, and CPU Burst Time in the same order\n");
	printf("\nEnter a process to add to PCB: ");
	scanf("%d %d %d", &lpid, &laTime, &lcpuBurst);
	printf("\n");  

	listPointer = addjob (listPointer, lpid, laTime, lcpuBurst);	
	counter++;
}

counter = 0;
while(counter < temp){
	printf("These are the processes in the Linked List: \n");
	printList(listPointer);
	listPointer = nextjob(listPointer);
	counter++;
	}

}

LINK * addjob(LINK *listPointer, int lpid, int laTime, int lcpuBurst)
{
	LINK *lp = listPointer;
	if(listPointer != NULL)
	{
		while(listPointer -> next != NULL)
			listPointer = (LINK *)listPointer -> next;
		listPointer->next = (struct LINK *)malloc(sizeof(LINK));
		listPointer = (LINK *)listPointer -> next;
		listPointer->next = NULL;
		listPointer->pid = lpid;
		listPointer->aTime = laTime;
		listPointer->cpuBurst = lcpuBurst;
		return lp;
	}
	else{
	   listPointer = (LINK *) malloc(sizeof(LINK));
	   listPointer->next = NULL;
	   listPointer->pid = lpid;
	   listPointer->aTime = laTime;
	   listPointer->cpuBurst = lcpuBurst;
	   return listPointer;
	}
}

LINK * nextjob(LINK * listPointer){
	LINK * tmp = listPointer;
	LINK * tmp2 = (LINK *)tmp -> next;

	int delvalue;
	
	while(tmp->next != NULL){
		if(tmp->cpuBurst <= tmp2->cpuBurst){
			tmp2 = (LINK *)tmp2->next;
		}  //end if
		else{
			tmp = tmp2;
			tmp2 = (LINK *)tmp2->next;
		}  //end else
	}  //end while
	
	printf("Process id %d, with Arrival Time %d ", tmp->pid, tmp->aTime); 
		printf("and CPU Burst Time of %d will be scheduled\n", tmp->cpuBurst);

	delvalue = tmp->pid;	
	deletenode(listPointer, delvalue);
	return listPointer;
}

LINK * deletenode(LINK *listPointer, int delvalue)
{
	LINK *temp, *old;
	
	temp = listPointer;
	old = listPointer;
	
	//Head is the node to be deleted
	if(temp->pid == delvalue)
	{
		listPointer = (LINK *)temp->next;
		free(temp);
		return listPointer;
	}
	else
	{
		while(temp != NULL)
		{
			if(temp->pid == delvalue)
			{
			old->next = temp->next;
			free(temp);
			return listPointer;
			} //End if
			old = temp;
			temp = (LINK *)temp->next;
		
		} //End while
	} //End else
return listPointer;
}
/*
LINK * deletenode(LINK *listPointer, int delvalue)
{
	LINK *old, *cur;
	*old = *listPointer;
	
	*cur = *listPointer;
	
	while(cur != NULL)
	{
		//printf("while value: %d \n", cur->pid);
		if(cur->pid == delvalue)
		{
			if(cur == listPointer)
			{
				listPointer = (LINK *) cur->next;
				free(cur);
				return listPointer;
			} //end inner if
			
			else
			{
				//printf("Else");
				old->next = (LINK *)cur->next;
				printf("Deleting PID: %d \n", cur->pid);
				free(cur);
				return listPointer;
			} //end else
		} //end if
		
		else
		{
			old = cur;
			cur = (LINK *)cur->next;
			printf("Cur Pid: %d \n", cur->pid);
			printf("old pid: %d\n", old->pid);
		} //end else
	} // end while
	printf("\nElement %d not found", delvalue);

return listPointer;

} //end delete node
*/
void printList(LINK * listPointer)
{
	printf("Process   ,Arrival Time, CPU Burst Time\n");
	if(listPointer == NULL)
		printf("List is empty");
	else{
		while(listPointer != NULL){
			printf("%d,   %d,   %d\n", listPointer->pid, listPointer->aTime, listPointer->cpuBurst);
			listPointer = (LINK *)listPointer->next;
		}
	}
	
}
When i run pid 10, 8 , 5, 4, 3, 2 it deletes fine (from the end of the list), however when i try to delete from the middle of the list it does not work. so if i have a list 10, 5, 8, 9 and want to delete 5, it won't delete it (gives me a segmentation fault). What am i doing wrong? or does anybody have a good delete function?
 
Old 05-04-2005, 11:38 PM   #2
Matir
Moderator
 
Registered: Nov 2004
Location: San Jose, CA
Distribution: Ubuntu
Posts: 8,507

Rep: Reputation: 118Reputation: 118
I would implement the delete slightly differently. Code that calls it will need to be modified slightly.
Code:
void deleteNode(LINK **list, int key){
    LINK *curr=*list;
    LINK *tmp=NULL;

    if(curr->pid == key){
        *list=curr->next;
        free(curr);
        return;
    }

    while(curr->next != NULL){
        if(curr->next->pid == key){
            tmp=curr->next;
            curr->next=curr->next->next;
            free(tmp);
        }
        curr=curr->next;
    }
}
This implementation SHOULD work. I just wrote it off the top of my head, so if it's buggy, I'm sorry.
 
Old 05-04-2005, 11:54 PM   #3
dilberim82
Member
 
Registered: Apr 2001
Location: NY
Distribution: used to be Redhat, now Debian Sarge
Posts: 291

Original Poster
Rep: Reputation: 30
Why did you use void if you don't mind me asking? How do we know if we change the head node? Is **list what keeps track of deleting the head node...because i have to return it to main function from the nextjob. one more question when i am calling this function, do i use:

deleteNode(&listPointer, int key)
 
Old 05-04-2005, 11:57 PM   #4
Matir
Moderator
 
Registered: Nov 2004
Location: San Jose, CA
Distribution: Ubuntu
Posts: 8,507

Rep: Reputation: 118Reputation: 118
Yep, you use that code exactly. Sorry I didn't clarify that point. Generally, the 'node **' syntax is preferred because it makes it impossible to forget capturing the return value. Your original code could've been called as 'deletenode(listpointer,key)' without resetting the listpointer... and that would leave things REALLY messed up.

(Just FYI, //-style comments are from C++ and only supported by GCC as a GNU extension to C... if you use a non-GCC compiler (though I think MS's compiler supports it as well) you may get syntax errors from it... just wanted you to be aware)
 
Old 05-05-2005, 12:15 AM   #5
dilberim82
Member
 
Registered: Apr 2001
Location: NY
Distribution: used to be Redhat, now Debian Sarge
Posts: 291

Original Poster
Rep: Reputation: 30
thanks

Thanks a lot matir, i will try that code in a couple of hours... I never had problems with // style comments so i use them extensively but its a good point to make in case i have problems in the future (i am sure i will :-) ). Thanks again, i appreciate it.
 
Old 05-05-2005, 12:48 AM   #6
freegianghu
Member
 
Registered: Oct 2004
Location: somewhere in the street
Distribution: Window$
Posts: 192

Rep: Reputation: 30
I has few comments:

Quote:
Code:
void deleteNode(LINK **list, int key){
    LINK *curr=*list;
    LINK *tmp=NULL;

    if(curr->pid == key){ /* curr should not be NULL */ 
        *list=curr->next;
        free(curr);
        return;
    }

    while(curr->next != NULL){
        if(curr->next->pid == key){
            tmp=curr->next;
            curr->next=curr->next->next;
            free(tmp); 
            /* why not return here ???  */ 
        }
        curr=curr->next;
    }
}
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
C++ Linked List question lowpro2k3 Programming 3 06-16-2005 11:15 AM
cirular linked list pantera Programming 8 04-21-2005 07:59 AM
how to free linked list containers? rgiggs Programming 3 07-30-2004 02:24 PM
C++ linked list fun chens_83 Programming 2 08-04-2003 08:40 AM
book linked list in C jetfreggel Programming 14 03-16-2003 11:52 AM


All times are GMT -5. The time now is 12:17 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration