- 예전에 1학년 때 잘못된 방법으로 짠 것을 이제야 제대로(?) 고쳐서 올립니다. 창피한 역사는 빨리 지워버려야...
그냥 링크드 리스트 ¶
#include<iostream>
using namespace std;
struct Node{ //Structure 'Node' has its own data and link to next node
int data; //Data of node
Node * nextNode; //Address value of next node
Node(int initialData){ //Constructor with initializing data
data=initialData; //Assign data
nextNode='\0'; //Assign null value to address of next node
}
Node(){} //An empty constructor to reduce warning in compile time
};
int enterData(); //Function which enter the data of node
void displayList(Node * argNode); //Function which displays the elements of linked list
Node * allocateNewNode(Node * argNode, int argData);//Function which allocate new node in memory
int main()
{
Node * firstAddress=new Node(enterData());//Create the first address to linked list
Node * currentNode;//Create temporary node which indicates the last node of linked list
currentNode=firstAddress;
//Create the next node to linked list
for(int i=0;i<7;i++)
currentNode=allocateNewNode(currentNode, enterData());
displayList(firstAddress);
return 0;
}
void displayList(Node * argNode)
{
cout<<"Address\t Data Value\tNext Address\n";
Node * tempNode; //Temporary node to tour linked list
tempNode=argNode;
do{
cout<<tempNode<<"\t"<<tempNode->data<<"\t"<<tempNode->nextNode<<"\n";
if(tempNode->nextNode=='\0')//Exit from do-while loop if value of next node is null
break;
else //Go to the next node if there is next node
tempNode=tempNode->nextNode;
}while(1);
}
Node * allocateNewNode(Node * argNode, int argData)
{
argNode->nextNode=new Node(argData);
return argNode->nextNode;
}
int enterData()
{
int returnData;
cout<<"Node에 들어갈 데이터 값을 입력하시오.";
cin>>returnData;
return returnData;
}
자유공간리스트(?) 사용 ¶
- 숙제 스펙(자유공간리스트) 맞추느라 좀 지저분하네요. 조만간 필요없는 부분은 지워서...
#include<iostream>
using namespace std;
struct Node{ //Structure 'Node' has its own data and link to next node
int data; //Data of node
Node * nextNode; //Address value of next node
Node(int initialData){ //Constructor with initializing data
data=initialData; //Assign data
nextNode='\0'; //Assign null value to address of next node
}
Node(){nextNode='\0';} //An empty constructor to reduce warning in compile time
};
#define MAX_OF_LIST 8 //Maximum number of linked list and free space list
int enterData(); //Function which enter the data of node
void displayList(Node * argNode); //Function which displays the elements of linked list
Node * allocateNewNode(Node * argNode, int argData, int * argNumberOfElements);//Function which allocates new node in memory
Node * reverseList(Node * argNode);//Function which reverses the sequence of the list
void eraseLastNode(Node * argNode, Node ** argFreeNode, int * argNumberOfList, int * argNumberOfFreeSpace);//Function which deletes the last node of the list
void getNode(Node * argNode, Node ** argFreeNode, int * argNumberOfList, int * argNumberOfFreeSpace);//Function which takes the node from free space list
void returnNode(Node * argNode, Node ** argFreeNode, int * argNumberOfList, int * argNumberOfFreeSpace);//Function which return a node of linked list to free space list
int main()
{
int elementsOfLinkedList=0;
int elementsOfFreeSpaceList=0;
Node * firstAddress=new Node(enterData());//Create the first address to linked list
elementsOfLinkedList++;//Set 1 to number of node.
Node * currentNode;//Create temporary node which indicates the last node of linked list
Node * freeSpaceList=NULL;//Create free space list
currentNode=firstAddress;
//Create the next node to linked list
for(int i=0;i<8;i++)
currentNode=allocateNewNode(currentNode, enterData(), &elementsOfLinkedList);
displayList(firstAddress);
firstAddress=reverseList(firstAddress);
displayList(firstAddress);//Display reversed list
eraseLastNode(firstAddress, &freeSpaceList, &elementsOfLinkedList, &elementsOfFreeSpaceList);
eraseLastNode(firstAddress, &freeSpaceList, &elementsOfLinkedList, &elementsOfFreeSpaceList);
eraseLastNode(firstAddress, &freeSpaceList, &elementsOfLinkedList, &elementsOfFreeSpaceList);
eraseLastNode(firstAddress, &freeSpaceList, &elementsOfLinkedList, &elementsOfFreeSpaceList);
displayList(firstAddress);//Display the linked list with modified data
displayList(freeSpaceList);//Display free space list with deleted data from linked list
getNode(firstAddress, &freeSpaceList, &elementsOfLinkedList, &elementsOfFreeSpaceList);
getNode(firstAddress, &freeSpaceList, &elementsOfLinkedList, &elementsOfFreeSpaceList);
getNode(firstAddress, &freeSpaceList, &elementsOfLinkedList, &elementsOfFreeSpaceList);
getNode(firstAddress, &freeSpaceList, &elementsOfLinkedList, &elementsOfFreeSpaceList);
displayList(firstAddress);//Display the linked list with data which are taken from free space list
displayList(freeSpaceList);//Display the empty free space list
returnNode(firstAddress, &freeSpaceList, &elementsOfLinkedList, &elementsOfFreeSpaceList);
displayList(firstAddress);
displayList(freeSpaceList);
return 0;
}
void displayList(Node * argNode)
{
Node * tempNode; //Temporary node to tour linked list
tempNode=argNode;
cout<<"Address\t Data Value\tNext Address\n";
do{
if(tempNode==NULL)
{
cout<<"Sorry... There is no node to display.\n";
break;
}
else
{
cout<<tempNode<<"\t"<<tempNode->data<<"\t"<<tempNode->nextNode<<"\n";
if(tempNode->nextNode==NULL)//Exit from do-while loop if value of next node is null
break;
else //Go to the next node if there is next node
tempNode=tempNode->nextNode;
}
}while(1);
}
Node * allocateNewNode(Node * argNode, int argData, int * argNumberOfElements)
{
if((*argNumberOfElements)>=MAX_OF_LIST)
{
cout<<"Out of maximum size of memory! Your input will be cancelled."<<endl;
return NULL;
}
(*argNumberOfElements)++;
argNode->nextNode=new Node(argData);
return argNode->nextNode;
}
int enterData()
{
int returnData;
cout<<"Please input the data to the node.";
cin>>returnData;
return returnData;
}
Node * reverseList(Node * argNode)
{
Node * firstTempNode;
Node * secondTempNode=NULL;
Node * thirdTempNode=argNode;
while(thirdTempNode!=NULL)
{
firstTempNode=secondTempNode;
secondTempNode=thirdTempNode;
thirdTempNode=thirdTempNode->nextNode;//Go one step to next node
secondTempNode->nextNode=firstTempNode;
}
argNode=secondTempNode;//Set address of the last node at first address
return argNode;
}
void eraseLastNode(Node * argNode, Node ** argFreeNode, int * argNumberOfList, int * argNumberOfFreeSpace)
{
Node * tempNode=argNode;
Node * tempPreviousNode;
Node ** tempFreeNode=argFreeNode;
if(tempNode==NULL)
cout<<"You have no node to erase.\n";
else
{
while(tempNode->nextNode!=NULL)
{//Go to the last node of the linked list
tempPreviousNode=tempNode;
tempNode=tempNode->nextNode;
}//Save the last node and the second node at back
if(tempNode->nextNode==NULL)
{//At the last node,
if((*argNumberOfList)>0 && (*argNumberOfFreeSpace)<MAX_OF_LIST)
{
if(*argFreeNode==NULL)
{//If free space list is empty
*argFreeNode=tempPreviousNode->nextNode;
tempPreviousNode->nextNode=NULL;
}//Link the last node of the linked list to free space list
else
{//If free space list has one node at least
tempNode->nextNode=*argFreeNode;
*argFreeNode=tempPreviousNode->nextNode;
(*argFreeNode)->nextNode=(*tempFreeNode)->nextNode;
tempPreviousNode->nextNode=NULL;
}/*Link the Free space list to the last node of linked list and
link the last node of the linked list to free space list*/
(*argNumberOfList)--;
(*argNumberOfFreeSpace)++;
}
else
cout<<"An error occurs in erasing process."<<endl;
}
}
}
void getNode(Node * argNode, Node ** argFreeNode, int * argNumberOfList, int * argNumberOfFreeSpace)
{
Node * tempNode=argNode;
Node ** tempFreeNode=argFreeNode;
if(*tempFreeNode==NULL)
cout<<"You have no node to reuse in free space list.\n";
else
{
while(tempNode->nextNode!=NULL)
{//Go to the last node of linked list
tempNode=tempNode->nextNode;
}
if((*argNumberOfList)<MAX_OF_LIST && (*argNumberOfFreeSpace)>0)
{
if(tempNode->nextNode==NULL)
{//Link the first node of free space list to the last node of linked list
tempNode->nextNode=(*tempFreeNode);
(*tempFreeNode)=(*tempFreeNode)->nextNode;
tempNode->nextNode->nextNode=NULL;
}
}
else
cout<<"An error occurs in getting process."<<endl;
}
}
void returnNode(Node * argNode, Node ** argFreeNode, int * argNumberOfList, int * argNumberOfFreeSpace)
{
Node * tempNode=argNode;
Node ** tempFreeNode=argFreeNode;
Node * tempPreviousNode;
if(tempNode==NULL)
cout<<"You have no node to return.\n";
else
{
int returnData;
cout<<"Input the data value of node that you want to return to the free space list."<<endl;
cin>>returnData;
//Input data which you want to return to free space list
while(tempNode->nextNode!=NULL)
{//Go to the last node of the linked list
if((*argNumberOfList)>0 && (*argNumberOfFreeSpace)<MAX_OF_LIST)
{
if(tempNode->data==returnData)
{//Search the data which you entered
cout<<"You want to return node with "<<returnData<<endl;
tempPreviousNode->nextNode=tempNode->nextNode;
if(*argFreeNode!=NULL)
tempNode->nextNode=(*argFreeNode)->nextNode;
else
tempNode->nextNode=NULL;
*argFreeNode=tempNode;
(*argNumberOfList)--;
(*argNumberOfFreeSpace)++;
}
else
{
tempPreviousNode=tempNode;
tempNode=tempNode->nextNode;
}
}
else
cout<<"An error occurs in returning process."<<endl;
}//Save the last node and the second node at back
}
}
----
작성자: Yggdrasil
----
LinkedList
