반응형
시간 째 들여다 보고 있는중인데 당췌 어떻게 시작을 해야 할지..


% 연결리스트와 관련하여 다음 문제에 대한 프로그램을 작성하시오.
1) 연결리스트의 맨끝에 새로운 노드를 삽입하기 위한 다음 함수 프로그램을 작성하시오.
void linkedlist_tail_insert(node*, head_ptr, int data) ;

2) 연결리스트에서 데이터 값이 42를 지닌 노드가 몇 개 존재하는지를 출력하기 위한 함수 프로그램을 작성하시오. 단, head_ptr은 첫 노드를 가리키며, 연결리스트가 비어있을 수 도 있다.
int count_value42 ( const node* head_ptr)

3) head1, head2로 표시되는 각각의 연결리스트가 오름차순으로 정렬되어 있다고 가정하자. 이 연결리스트 두 개를 파라미터로 받아서 합병(merge)된 연결리스트의 첫 노드를 가리키는 head3를 return하는 함수 프로그램을 작성하시오. 단, 합병된 연결리스트는 정렬되어 있어야 한다.

이게 문제 인데요.. 설명 좀 덧붙여주세여...
어떻게 돌아가는지 도통 이해가 안되는 군요....

-----------------------------------------------------------------------------------

자료구조가 같은지 모르겠네요.

main() 함수에서 사용하도록 되어 있습니다. 확인해 보세요.

궁금한 점 있으면 연락주세요.

좋은 하루 되세요.


#include "stdlib.h"
#include "string.h"


typedef struct NODE node;
struct NODE
{
   int data;
   node* next;
};


void linkedlist_tail_insert(node** head_ptr, int data)
{
   node* node_ptr;
   node* new_node = (node*)malloc(sizeof(node));
   new_node->data = data;
   new_node->next = NULL;

   if((*head_ptr) == NULL)
   {
      (*head_ptr) = new_node;
   }
   else
   {
      for(node_ptr = (*head_ptr); node_ptr->next != NULL; node_ptr = node_ptr->next)
      {
         ;/*nothing*/
      }
      node_ptr->next = new_node;
   }
}


void linkedlist_free(node* head_ptr)
{
   node* node_ptr;
   node* node_ptr_temp;

   if(head_ptr != NULL)
   {
      for(node_ptr = head_ptr, node_ptr_temp = head_ptr; node_ptr_temp != NULL; node_ptr = node_ptr_temp)
      {
         node_ptr_temp = node_ptr->next;
         delete node_ptr;
      }
   }
}


void linkedlist_print(node* head_ptr)
{
   int i=1;
   node* node_ptr;
   if(head_ptr != NULL)
   {
      for(node_ptr = head_ptr; node_ptr != NULL; node_ptr = node_ptr->next)
      {
         printf("%d, %d\n", i++, node_ptr->data);
      }
   }
}


int count_value42 ( const node* head_ptr)
{
   int count = 0;
   const node* node_ptr;

   if (head_ptr != NULL)
   {
      for(node_ptr = head_ptr; node_ptr->next != NULL; node_ptr = node_ptr->next)
      {
         if (node_ptr->data == 42)
         {
            count++;
         }
      }
   }
   return count;
}


node* linkedlist_merge (node* head1, node* head2)
{
   node* head3 = NULL;
   node* new_node = NULL;

   node* node_ptr1 = head1;
   node* node_ptr2 = head2;
   node* node_ptr3 = head3;

   while((node_ptr1 != NULL) || (node_ptr2 != NULL))
   {
      if (node_ptr1 == NULL)
      {
         linkedlist_tail_insert(&head3, node_ptr2->data);
         node_ptr2 = node_ptr2->next;
      }
      else if (node_ptr2 == NULL)
      {
         linkedlist_tail_insert(&head3, node_ptr1->data);
         node_ptr1 = node_ptr1->next;
      }
      else
      {
         if (node_ptr1->data > node_ptr2->data)
         {
            linkedlist_tail_insert(&head3, node_ptr2->data);
            node_ptr2 = node_ptr2->next;
         }
         else
         {
            linkedlist_tail_insert(&head3, node_ptr1->data);
            node_ptr1 = node_ptr1->next;
         }
      }
   }

   return head3;
}


void main()
{
   node* head1 = NULL;
   node* head2 = NULL;
   node* head3 = NULL;


   linkedlist_tail_insert(&head1, 10);
   linkedlist_tail_insert(&head1, 20);
   linkedlist_tail_insert(&head1, 40);
   linkedlist_tail_insert(&head1, 42);
   linkedlist_tail_insert(&head1, 60);
   linkedlist_tail_insert(&head1, 70);


   linkedlist_tail_insert(&head2, 0);
   linkedlist_tail_insert(&head2, 30);
   linkedlist_tail_insert(&head2, 42);
   linkedlist_tail_insert(&head2, 42);
   linkedlist_tail_insert(&head2, 50);
   linkedlist_tail_insert(&head2, 80);
   linkedlist_tail_insert(&head2, 90);


   head3 = linkedlist_merge(head1, head2);

   printf("head1 : %d\n", count_value42(head1));
   linkedlist_print(head1);
   printf("head2 : %d\n", count_value42(head2));
   linkedlist_print(head2);
   printf("head3 : %d\n", count_value42(head3));
   linkedlist_print(head3);


   linkedlist_free(head1);
   linkedlist_free(head2);
   linkedlist_free(head3);


   getchar();
}

반응형

'자료구조 & 알고리즘' 카테고리의 다른 글

2차원배열의 포인터  (0) 2007.03.14
이진탐색트리의 완결판!!!!  (1) 2007.03.14
초보를 위한 프로그래밍 입문서  (0) 2007.03.14
Posted by Real_G