linked list + c

dilberim82 · 05-04-2005, 08:38 PM

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?

Matir · 05-04-2005, 10:38 PM

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.

dilberim82 · 05-04-2005, 10:54 PM

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)

Matir · 05-04-2005, 10:57 PM

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)

dilberim82 · 05-04-2005, 11:15 PM

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.

freegianghu · 05-04-2005, 11:48 PM

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;
    }
}