[CㆍC++로 배우는 자료구조론] 05 리스트 연습문제

4. 나.

5. 다.

6. 다

7. 가. 배열

8. 

void Delete(listType *Lptr, int Position)

{

if ((Position > (Lptr->Count)) || (Position < 1))

printf("Position out of Range");

else if(Lptr->Count == 1)

{

Lptr->Count = 0;

}

else

{

for (int i = (Position - 1); i < (Lptr->Count - 1); i++)

Lptr->Data[i] = Lptr->Data[i + 1];

Lptr->Count--;

}

};

9. 

void Retrieve(listType *Lptr, int Position, int *Itemptr)

{

if (Lptr->count == 0)

printf("\n No Data In List\n");

else if (Position <= 0 || Position > Lptr->count)

printf("\n Wrong Position\n");

else

{

Nptr Temp = Lptr->head;

for (int i = 0; i < (Position - 1); i++)

Temp = Temp->next;

*Itemptr = Temp->data;

}

};

10. 함수 중에 아무것도 되지 않는다. 이니시를 안하면 쓰레기값이 들어있기때문에 당연.

13. 잘 작동한다.

14. 

void Delete(AlistType *Lptr, int Position)

{

if ((Position > (Lptr->Count)) || (Position < 1))

printf("Position out of Range");

else if(Lptr->Count == 1)

{

Lptr->Count = 0;

}

else

{

for (int i = (Position - 1); i < (Lptr->Count - 1); i++)

Lptr->Data[i] = Lptr->Data[i + 1];

Lptr->Count--;

}

};

18.  

가. 22

나. r

다. Kim

19.

int i;

for(  i = 9; i > 4; i-- )

{

Myarray[ i ] =  Myarray[ i - 1 ];

}

Myarray[ i ] = 27;

20. 

가. 

Cur = Head;

Head = Head->Next;

free(Cur);

나.

Cur = Head;

for (int i = 1; i < 4; i++)

Cur = Cur->next;

다.

Cur = (*Node)malloc(sizeof(Node));

Cur->Data = 33;

Cur->Next = NULL;

Prev = Head;

for (int i = 1; i < 5; i++)

Prev = Prev->next;

Prev->next = Cur;

21.

가.

Head = (ptrType)malloc(sizeof(node));

Head->Items = 'B';

newPtr = (ptrType)malloc(sizeof(node));

newPtr->Items = 'E'

Head->next = newPtr;

newPtr = (ptrType)malloc(sizeof(node));

newPtr->Items = 'J'

newPtr->next = NULL;

Head->next->next = newPtr;

22.

ptrType Cur = Head;

ptrType Prev = Cur;

ptrType Temp = (ptrType)malloc(sizeof(node));

Temp->Ch = 'K';

Temp->Next = NULL;

While(Cur->Ch <= Temp->Ch && Cur->next != NULL)

{

Prev = Cur;

Cur = Cur->next;

}

if(Cur->next == NULL)

Cur->next = Temp;

else if(Cur == Prev)

{

Temp->next = Cur;

Head = Temp;

}

else

{

Temp->next = Cur;

Prev->next = Temp;

}

23. 

void listClass::~listClass()

{

while(ADT_LIST.IsEmpty() == False)

ADT_LIST.Delete(ADT_LIST.count);

}

24.

 -22번 문제의 node를 기준으로 생각해보면

ptrType ReverseList (ptrType Head)

{

ptrType NewHead, Curr, Prev;

if( Head != NULL )

{

Curr = Head;

NewHead = new node;

( NewHead->Ch = Curr->Ch );

( NewHead->Next = NULL );

Curr = Curr->Next;

while (Curr != NULL)

{

(  Prev = new node;  )

(  Prev->Ch = Curr->Ch;  )

(  Prev->Next = NewHead;  )

(  NewHead = Prev;  )

(  Curr = Curr->Next;   )

}

}

else

{

NewHead = NULL;

}

return NewHead;

}

25. 

ptrType Merge(ptrType Head1, ptrTypeHead2)

{

ptrType Temp, NewHead;

if( Head1 == NULL )

{

NewHead = Head2;

}

else if( Head2 == NULL )

{

NewHead = Head1;

}

else if( Head1->Ch >= Head2->Ch )

{

NewHead = Head1;

Head1 = Head1->Next;

}

else

{

NewHead = Head2;

Head2 = Head2->Next;

}

Temp = NewHead;

while( !(Head1 == NULL && Head2 == NULL ) )

{

if( Head1 == NULL )

{

Temp->Next = Head2;

break;

}

else if( Head2 == NULL )

{

Temp->Next = Head1;

break;

}

else if( Head1->Ch < Head2->Ch )

{

Temp->Next = Head1;

Head1 = Head1->Next;

}

else

{

NewHead = Head2;

Head2 = Head2->Next;

}

Temp = Temp->Next;

}

}

26. 

typedef struct arraies

{

HeadPtr[200];

} TotalList;

typedef WaitNode* HeadPtr;

typedef struct Node

{

int Age;

Node* Next;

} WaitNode;

27.

node* ListRetrieve (node* Head)

{

ptrType ptr = Head;

while( ptr != NULL )

{

if( ptr->Data == 25 )

return ptr;

else

ptr = ptr->next;

}

return ptr;

}

28.

노드의 순서를 역순으로 하여 입력된 Head의 맨 끝을 Head가 가리키게 하는 함수이다.

Reverse.

29. 

이것도 28번이랑 동일한 작동을 하는 Reverse 함수이다.

심지어 24번 문제의 답.

30.

void Retrieve_odd(ptrType Head)

{

ptrType Temp=Head;

while(Temp != NULL)

{

if(Temp->Data % 2 == 1)

cout << Temp->data << " ";

Temp = Temp->Next;

}

}

31.

void Insert_25(ptrType Head)

{

ptrType Temp = Head, Prev = Head;

ptyType p = new node;

p->Data = 25;

p->Next = NULL;

while(Temp->Next != NULL)

{

if( Temp->Next->Data > Prev->Data )

Prev = Temp;

Temp = Temp->Next;

}

p->Next = Prev->Next;

Prev->Next = p;

}

32. 

p*의 다음 노드를 가리키는 포인터 t 를 하나 생성한다.

*p노드가 *p노드와 다음 다음의 노드를 연결시킨다.

p*노드의 다음 노드를 가라키고 있던 t를 통해 그 노드를 해제시킨다.

33.

일단 노드를 가리킬 수 있는 새로운 포인터를 생성하고,

노드 만큼의 새로운 공간을 만들어 그걸 가리키게 한다.

그 다음 새로 만들어진 노드 t가 *p노드의 다음을 가리키게 하고.

*p노드는 t를 가리키게 한다. 

34.

void PrintSameData(ptrType Head, int DataToMatch)

{

ptrType Temp = Head;;

while(Temp != NULL)

{

if( Temp->Data == DataToMatch )

cout << Temp->Data << " ";

Temp = Temp->Next;

}

}

35.

int Count42( const node* head_ptr ) 

{

int count = 0;

node* Temp = head_ptr;

if( Temp == NULL )

return 0;

else

{

}

}

36.

int sum_data( const node* head_ptr )

{

int sum = 0;

if( head_ptr == NULL )

return sum;

else

{

node* Temp = head_ptr;

while( Temp != NULL )

{

sum += Temp->Data;

Temp = Temp->Next;

}

return sum;

}

}

37.

void list_tail_insert( node* head_ptr, int Data )

{

if( head_ptr->Next == NULL )

{

head_ptr->Next = (node *)malloc( sizeof( node ) );

head_ptr->Next->Data = Data;

head_ptr->Next->Next = NULL;

return void;

}

else

{

list_tail_insert( head_ptr->Next, Data );

}

}

39.

void PasteNode( const Nptr Head, Nptr * NewHead, Nptr * NewTail )

{

if ( Head == NULL )

return;

else

{

Nptr Temp = Head;

*NewHead = new node;

*NewHead->Data = Temp->Data;

*NewHead->Next = NULL;

NewTemp = *NewHead;

Temp = Temp->Next;

while( Temp != NULL )

{

NewTemp->Next = new node;

NewTemp->Data = Temp->data;

NewTemp->Next = NULL;

Temp = Temp->Next;

NewTemp = NewTemp->Next;

}

*NewTail = NewTemp;

}

}

41.

 - 선언되자마자 초기화 되는 경우

 - 함수 파라미터로 넘어가는 경우

 - 함수 리턴값으로 넘어가는 경우

42.

bool List::deleteNum(int DataToSearch)

{

if (Header == NULL)

return false;

else

{

Nptr Temp = Header;

while (Temp != NULL)

{

if (Temp->Data == DataToSearch)

return true;

Temp = Temp->Next;

}

return false;

}

}

43.

bool listClass::IsSorted()

{

Nptr Temp = Header;

while ((Temp->Next != NULL) && (Temp->Next->Data > Temp->Data))

Temp = Temp->Next;

if (Temp->Next != NULL)

return false;

else

return true;

}

44.

( Cur == NULL )

( Head = Temp )

( return Cur )

45.

void addNode( Nptr &Head, int Position, int Value )

{

Nptr p = (Nptr)malloc(sizeof(Node));

if( ( Position < 1 ) || ( Position > Head->Count+1 ) )

{

printf(" Out of Position ");

return;

}

else

{

Temp = Head;

for (int i = 0 ; i< (Position-1); i++)

Temp = Temp->Next;

p->Data = Value;

p->Next = Temp->Next;

Temp->Next = p;

Head->Data++; // 빈 노드의 데이터를 카운트로 사용

}

}

46.

void swap( listnode *first, int swapkey )

{

listnode* Temp = first;

listnode* Temp2;

while( Temp->Next != NULL && Temp->key != swapkey )

Temp = Temp->next;

if( Temp->Next == NULL )

return void;

else

{

Temp2 = Temp->next;

Temp->next = Temp2->next;

Temp2->prev = Temp->prev;

Temp2->next = Temp;

Temp->prev = Temp2;

}

}

47.

( temp->Data = a->Data )

( first = temp )

( last->next = temp )

( last = temp )

( temp->Data = b->Data )

( first = temp )

( last->next = temp )

( last->next = NULL )

49.

왜냐하면 배열은 왼쪽이 작은 숫자의 인덱스, 오른쪽이 큰 숫자의 인덱스이기 때문이다.

50.

bool IsInList( Nptr List, Int Data )

{

if( List == NULL )

return false;

else

{

Nptr Temp = List;

while( Temp != NULL && Temp->Data != Data )

Temp = Temp->Next;

if( Temp == NULL )

return false;

else

return true;

}

}

void Merge( Const Nptr Head1, Const Nptr Head2 )

{

//정렬 1

Nptr Temp1, Temp2, Start, Min;

Nptr NewHead1 = NULL, NewHead2 = NULL, Merged = NULL;

if( Head1 != NULL )

{

Temp1 = Head1->Next;

Temp2 = NewHead1;

Start = Head1;

Min = Head1;

while( Start->Next != NULL )

{

while( Temp1 != NULL )

{

if ( Temp1 < Min && !( IsInList(NewHead1, Temp1->Data ) )

Min = Temp;

Temp1 = Temp1->Next;

}

Nptr p = new Node;

p->Data = Min->Data;

p->Next = NULL;

if( NewHead1 = NULL )

{

NewHead1 = p;

Temp2 = NewHead;

}

else

{

Temp2->Next = p;

Temp2 = Temp2->Next;

}

Start = Start->Next;

Min = Start;

Temp1 = Start->Next;

}

Nptr p = new Node;

p->Data = Start->Data;

p->Next = NULL;

Temp2->Next = p;

}

// 정렬 2 

if( Head2 != NULL )

{

Temp1 = Head2->Next;

Temp2 = NewHead2;

Start = Head2;

Min = Head2;

while( Start->Next != NULL )

{

while( Temp1 != NULL )

{

if ( Temp1 < Min && !( IsInList(NewHead2, Temp1->Data ) )

Min = Temp;

Temp1 = Temp1->Next;

}

Nptr p = new Node;

p->Data = Min->Data;

p->Next = NULL;

if( NewHead2 = NULL )

{

NewHead2 = p;

Temp2 = NewHead;

}

else

{

Temp2->Next = p;

Temp2 = Temp2->Next;

}

Start = Start->Next;

Min = Start;

Temp1 = Start->Next;

}

Nptr p = new Node;

p->Data = Start->Data;

p->Next = NULL;

Temp2->Next = p;

}

//합병

Temp1 = NewHead1;

Temp2 = NewHead2;

while( Temp1 != NULL || Temp2 != NULL )

{

if( Temp1 = NULL )

{

if( Merge = NULL )

{

Nptr p = new Node;

p->Data = Temp2->Data;

p->Next = NULL;

Merge = p;

Start = Merge;

}

else

{

Nptr p = new Node;

p->Data = Temp2->Data;

p->Next = NULL;

Start->Next = p;

Start = Start->Next;

}

Temp2 = Temp2->Next;

}

else if( Temp2 = NULL )

{

if( Merge = NULL )

{

Nptr p = new Node;

p->Data = Temp1->Data;

p->Next = NULL;

Merge = p;

Start = Merge;

}

else

{

Nptr p = new Node;

p->Data = Temp1->Data;

p->Next = NULL;

Start->Next = p;

Start = Start->Next;

}

Temp1 = Temp1->Next;

}

else // Temp1 != NULL && Temp2 != NULL

{

if( Temp1->Data < Temp2->Data )

{

if( Merge = NULL )

{

Nptr p = new Node;

p->Data = Temp1->Data;

p->Next = NULL;

Merge = p;

Start = Merge;

}

else

{

Nptr p = new Node;

p->Data = Temp1->Data;

p->Next = NULL;

Start->Next = p;

Start = Start->Next;

}

Temp1 = Temp1->Next;

}

else

{

if( Merge = NULL )

{

Nptr p = new Node;

p->Data = Temp2->Data;

p->Next = NULL;

Merge = p;

Start = Merge;

}

else

{

Nptr p = new Node;

p->Data = Temp2->Data;

p->Next = NULL;

Start->Next = p;

Start = Start->Next;

}

Temp2 = Temp2->Next;

}

}

}

//출력

Temp1 = Merged;

while( Temp1 != NULL )

{

cout << Temp1->Data << " ";

Temp1 = Temp1->Next;

}

// 사실 출력이 끝난 후 Merged, NewHead1, NewHead2 의 모든 노드들을 delete 해주어야 한다.

}