연결리스트 code

//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(); }