링크드리스트(Linked list)

 

링크드리스트(Linked list)

 

 

 

fire 첫 번째 숙제

링크리스트.

 

1->2->3->23->20

 

입력 받음과 동시에 정렬해버리고

연결연결~

 

#include <iostream>
using namespace std;

struct Foo { /* 리스트 구조체 */
 int data;
 Foo *p;
};

Foo *p1; /* 리스트의 시작을 가리키는 헤더 노드 */

void In(int num); /* 노드 삽입 */
bool Del(int num);/* 노드 제거 */
void out(); /* 리스트 순회 */

int main()
{
 
 int num;
 bool res;
 bool flag=false;

 while (true) {

  cout << "\n"<<endl;
  cout << "1. 한개의 수를 입력하기!!"<<endl;
  cout << "2. 한개의 수를 제거하기!!"<<endl;
  cout << "3. 링크해서 출력하기"<<endl;
  cout << "Q. 종료하기." << endl;
  char s;
  cin>> s;
 
  switch(s)
  { /* 선택한 메뉴에 따른 연산 */
  case '1':
   cout <<"데이터를 입력하세요!! : "<< endl;
    cin>> num;
  
 In(num);

    cout <<"입력되었습니다.\n"<< endl;
   break;
 
  case '2':
  
   cout << "삭제할 데이터를 입력하세요"<<endl;
      cin >> num;

   res= Del(num);

   if(res == true)
   {
     cout << "삭제되었습니다." <<endl;
   }
   else
   {
     cout << num <<"(은/는) 찾지못하였습니다."<<endl;
   }
   break;

  case '3':
 
   out();
       break;
  case 'q':
  case 'Q':
   cout << "프로그램을 종료합니다." << endl;
  
  flag = true;
  break;
  default :
   cout << "잘못입력하셨습니다" <<endl;
   
 
  }
  if(flag == true)
  {
   break;
  }
 }

}

void In(int num) // 노드 삽입
{
 Foo *current=p1; // 노드의 처음부터 검색
 
 Foo *prev=NULL;
 
 Foo *newNode = new Foo; // 삽입한 노드의 메모리 할당
 
 newNode->data = num; // 자료 저장

 

 /* 자료를 오름차순으로 정렬하며 포인터를 이용하여 정렬하는 위치를 찾아감 */
 
 while (current != NULL && num > current->data) { // 노드의 끝이거나, 자료의 위치를 찾으면 검색 종료
  prev = current; // 현재 위치를 prev에 저장
  current = current->p; // 다음 노드로 넘어감
 }

 if (prev == NULL) { // Header 노드가 비었을 경우 (while 을 한번도 안거쳤을 경우)
  p1 = newNode; // 노드의 시작을 삽입한 노드로 변경 //
 }
 else {
  prev->p = newNode; // 삽입 위치가 처음이 아니라면 이전 노드의 다음 노드를 현재노드로 변경
 }

 newNode->p = current; // 삽입한 노드의 다음 노드를 현재 위치로 저장
}

bool Del(int num)
{
  Foo *current = p1;
  Foo *prev=NULL;

  if(current == NULL)
  {
    return false;         //비어 있다면 삭제 실패
  }
 
  while(current != NULL && num != current->data)
  {
   prev = current;

   current = current->p;
 
  }

  if(current == NULL)
  {
   return false;        //끝까지 검색한 후 삭제 실패
  }

  if(prev == NULL)
  {
   p1=current ->p; // 찾을 위치가 처음인 경우
  }
  else // 처음이 아닌 경우
  {
   prev->p = current ->p;  // 삭제할 노드의 링크 제거(이전 노드의 링크를 다음 노드로 연결)
  }
 

  delete [] current;
 
  return true;
 

}

 

void out() // 리스트 순회
{
 Foo *current = p1; // 리스트의 처음부터 검색
 

 while (current != NULL ) { // 리스트의 끝까지 검색
 
 

  cout<<""<<current->data;  // 출력
 
  if (current->p != NULL)  cout<<" -> ";
     
  current = current->p; // 다음 노드로 넘어감 */
 }
}