'연결리스트' 태그의 글 목록

연결리스트

연결리스트 code 2008.06.09

연결리스트 code

URUZ-7 2008. 6. 9. 03:44

2008. 6. 9. 03:44

//linkded list.c

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

****************************************************************
CODE WRITTEN BY NADIA MIJA, MARCH 27, 2003, BUCHAREST,ROMANIA
****************************************************************
You can use this code for any purpuses except publication or selling.
****************************************************************

1) TNODE -- the list nodes type; 
	- lkey -- list key = a value which is different for each node of the list; it can be useful for some applications
		it's recommendended to use it
	- name - a string information used only for example; here must be the real information of the list
	- next - the next node pointer; 
	
2) void CreateList() -- creates a list; for any TNODE structure (general function)
3) void ViewAllList() -- shows the list items for any TNODE structure (general function);  
4) void DeleteList() -- removes completely the entire list ; (general function)
5) TNODE* FindNode(int key) -- returns a pointer to a list-node which has the lkey-value equal-to key-parameter; 
	(general function)
6) TNODE* InsertAfterKey(int key) -- inserts a new node (list item) after a list-node which has the lkey-value equal-to 
	key-parameter; (general function)
7) TNODE* InsertAfterLast() -- inserts a new node (list item) after the last-node of the list ; (general function)
8) TNODE* InsertBeforeFirst() -- inserts a new node (list item) before the first-node of the list; (general function)
9) TNODE* InsertBeforeKey(int key) -- inserts a new node (list item) before a list-node which has the lkey-value equal-to 
	key-parameter; (general function)
10) void RemoveByKey(int key) -- removes a list-node which has the lkey-value equal-to 
	key-parameter; (general function)
11) void RemoveFirst() -- removes the first node of the list; (general function)
12) void RemoveLast() -- removes the last node of the list; (general function)

I ALSO HAVE WRITTEN A FEW FUNCTIONS WHICH ARE DEPENDENT TO THE TNODE STRUCTURE; THEY NEED TO BE REWRITTEN FOR EVERY 
APPLICATION

1) void FreeNode(TNODE *p)//function specific to the application -- deallocates the memory for the p node
2) int LoadNode(TNODE *p) //function specific to the application -- loads the information into the nodes of the list
	but should always return these values
	   0 - Error
	   1 - ok;
      -1 - no more data to load 
	  In this case (meaning my function) you shuld reply - anything for yes
														- n/N for no
3) void PrintNode(TNODE *p) //function specific to the application -- shows the information of the p node

PLEASE ALSO READ THE COMMENTS IN THE CODE FOR MORE INFORMATION

****************************************************************

typedef struct node {
	int lkey;	//key node
	char name[10]; //specific to the application; node's information 
	struct node* next;
} TNODE;

TNODE *first, *last; //pointers to the first and last element of the linked list

int LoadNode(TNODE *p);
void FreeNode(TNODE *p);
void PrintNode(TNODE *p);

void CreateList() //this function can be used no matter what the structure TNODE looks like
{					// meaning it can be used for any type of applications concerning lists
	TNODE *p;		//general function
	int n=sizeof(TNODE);

first=last=0; //empty list 
	for(;;)
	{
		if( (p=(TNODE*)malloc(n))==0 ) //allocation could not be made
		{
			printf("\nNot enough memory");
			break;
		}

if(LoadNode(p)!=1)
		{
			FreeNode(p);
			break;
		}

p->next=0;
		if (first==0) //this list was empty since now
			first=last=p;
		else
		{
			last->next=p;
			last=p;
		}
	}
}

int LoadNode(TNODE *p) //function specific to the application
{						//but should always return these values
	/* 0 - Error
	   1 - ok;
      -1 - no more data to load */

char opt;
	printf("\nNew node?");
	opt=getche();
	opt=toupper(opt);
	if(opt!='N')
	{
		puts("\nPlease insert data for the current node:");
		printf("\nlkey:\t");
		if (scanf("%d",&(p->lkey))!=1) return 0; //could not read lkey value for current node

printf("\nname:\t");if (scanf("%s",p->name)!=1) return 0; 
		return 1;
	}
	else
		return -1;	
}
void FreeNode(TNODE *p)//function specific to the application
{
	free(p);
}

void ViewAllList()//general function
{
	TNODE *p;
	p=first;
	while(p)
	{
		PrintNode(p);
		p=p->next;
	}
}

TNODE* FindNode(int key) //general function
//serches and returns the node having the lkey value equal to the key parameter
{
	TNODE *p;
	p=first;
	while(p)
	{
		if(p->lkey == key) return p;
		p=p->next;
	}
	return 0; //value not found
}

void PrintNode(TNODE *p) //function specific to the application
{
	if(p) printf("\n%d\t%s",p->lkey,p->name);
}

TNODE* InsertBeforeFirst()
//general function
//returns the node inserted
//or 0 for failed insertion 
{
	TNODE *p;
	int n=sizeof(TNODE);
	if (((p=(TNODE*)malloc(n))!=0) && (LoadNode(p)==1)) //a new node has been succesfully allocated and loaded
	{
		if (first==0) //list was empty
		{
			p->next=0;
			first=last=p;
		}
		else
		{
			p->next=first;
			first=p;
		}
		return p;
	}
	if(p==0) //not enough memory
		printf("\nNot enough memory");
	else //the node could not be loaded
		FreeNode(p);
	return 0; //there is no node inserted before first -- insertion failed
}

TNODE* InsertBeforeKey(int key)
//general function
//returns the node inserted
//or 0 for failed insertion 
{
	TNODE *p, *q, *q1;
	//p=the new node to insert
	//q=key
	//q1=the node before key
	int n=sizeof(TNODE);

//find q, q1
	q1=0;
	q=first;
	while(q)
	{
		if(q->lkey == key) break; //key node found
		q1=q; //keep on searching for key node
		q=q->next;
	}

if(q==0) 
	{
		printf("\nThere is no node having such a key or the list is empty");//this case also includes the case of empty list
		return 0;//there is no node having such a key -- insertion can't be made
	}

//now the key was found -- so we try to make the insertion
	if (((p=(TNODE*)malloc(n))!=0) && (LoadNode(p)==1)) //a new node has been succesfully allocated and loaded
	{
		if(q==first) //we have to insert before the first node
		{
			p->next=first;
			first=p;	
		}
		else //the key node is not the first one
		{
			p->next=q;
			q1->next=p;
		}
		return p;
	}
	if(p==0) //not enough memory
		printf("\nNot enough memory");
	else //the node could not be loaded
		FreeNode(p);
	return 0; //there is no node inserted before key -- insertion failed
}

TNODE* InsertAfterKey(int key)
//general function
//returns the node inserted
//or 0 for failed insertion

{
	TNODE *p, *q;
	//p=the new node to insert
	//q=key
	int n=sizeof(TNODE);
	
	//find q
	q=first;
	while(q)
	{
		if(q->lkey == key) break; //key node found
		q=q->next; //keep on searching for key node
	}
	if(q==0) 
	{
		printf("\nThere is no node having such a key or the list is empty");//this case also includes the case of empty list
		return 0;//there is no node having such a key -- insertion can't be made
	}

//now the key was found -- so we try to make the insertion
	if (((p=(TNODE*)malloc(n))!=0) && (LoadNode(p)==1)) //a new node has been succesfully allocated and loaded
	{
		if(q==last) //we have to insert after the last node
		{
			p->next=0;
			last->next=p;
			last=p;
		}
		else //the key node is not the last one
		{
			p->next=q->next;
			q->next=p;
		}
		return p;
	}
	if(p==0) //not enough memory
		printf("\nNot enough memory");
	else //the node could not be loaded
		FreeNode(p);
	return 0; //there is no node inserted after key -- insertion failed

}

TNODE* InsertAfterLast()
//general function
//returns the node inserted
//or 0 for failed insertion 
{
	TNODE *p;
	int n=sizeof(TNODE);
	if (((p=(TNODE*)malloc(n))!=0) && (LoadNode(p)==1)) //a new node has been succesfully allocated and loaded
	{
		p->next=0;
		if (first==0) //list was empty
			first=last=p;
		else
		{
			last->next=p;
			last=p;
		}
		return p;
	}
	if(p==0) //not enough memory
		printf("\nNot enough memory");
	else //the node could not be loaded
		FreeNode(p);
	return 0; //there is no node inserted after last -- insertion failed	
}

void RemoveFirst()
//general function
//removes the first node of the list; pre and post-conditions: none
{
	TNODE *p;
	
	if(first==0)//list was empty
		return;

if(first==last)//there is just one node 
	{
		FreeNode(first);
		first=last=0;
		return;
	}
	
	p=first;
	first=first->next;
	FreeNode(p);
}

void RemoveLast()
//general function
//removes the last node of the list; pre and post-conditions: none
{
	TNODE *p, *q;
	
	if(first==0)//list was empty
		return;

if(first==last)//there is just one node 
	{
		FreeNode(first);
		first=last=0;
		return;
	}

q=0;//there are at least 2 nodes
	p=first;
	while(p!=last) 
	{
		q=p;
		p=p->next;
	}//so we have q=the node before the last one

p=last;//now we're going to remove the last node
	FreeNode(p);
	q->next=0;
	last=q;

}

void RemoveByKey(int key)
{
	TNODE *p, *q;
	//p - the key node
	//q=the node before the key node 
	
	if(first==0)//list was empty
		return;

q=0;//there are at least 2 nodes
	p=first;
	while(p) 
	{
		if(p->lkey == key) break; //key node found
		q=p;
		p=p->next;
	}//so we have q=the node before the key one; p=key node

if(!p)//There is no node having such a key
	{
		printf("\nThere is no node having such a key");
		return;
	}

if(first==last)//there is just one node which is the key node
	{
		FreeNode(first);
		first=last=0;
		return;
	}

if(p==first) //first is the key node
	{
		first=first->next;
		FreeNode(p);
		return;
	}

if(p==last) // last was the key node
	{
		q->next=0;
		last=q; 
		FreeNode(p);
		return;
	}

q->next=p->next;	
	FreeNode(p);
}

void DeleteList()
{
	TNODE *p;

p=first;
	while(p)
	{
		first=first->next;
		FreeNode(p);
		p=first;
	}
	last=0;
}

void main()
{
	CreateList();//this is an example of using these fonctions
	ViewAllList();
	InsertAfterLast();
	ViewAllList();
	RemoveFirst();
	ViewAllList();
	InsertAfterKey(1);//by example
	ViewAllList();
	RemoveByKey(1);
	ViewAllList();
	DeleteList();
	ViewAllList();

}

PREV 이전 1 NEXT 다음

Hisworld.tistory.com

연결리스트

연결리스트 code

+ Recent posts

티스토리툴바