분야
hwp4. 리스트의 노드수를 계산하는 함수 length를 작성하라.
5. P를 단순 연결 리스트의 첫 번째 노드를 가리키는 포인터라 하자. 노드 P에서부터 하나씩 건너서 있는 노드들을 전부 삭제하는 프로시저를 작성하라.(즉 첫 번째, 세 번째, 다섯 번째 등의 노드들이 삭제된다.) 작성한 알고리즘의 시간 복잡도는 얼마인가?
6. x = (, ․ ․ ․, ), y = (, ․ ․ ․, )을 두 연결 리스트라 하자. 각 리스트에서 노드들은 데이터 필드값의 오름차순으로 되어 있다고 가정하라. 두 연결 리스트를 합병하여 역시 같은 순서를 유지하는 새로운 연결 리스트 z를 만드는 알고리즘을 작성하라. 합병한 후에 x와 y는 각각 독립적으로 존재하지 않는다. 즉, 초기에 x와 y에 있었던 각 노드들은 병합 후에는 z에 있게 된다. 새로운 노드는 사용할 수 없다. 작성한 알고리즘의 시간 복잡도는 얼마인가?
7. = (, ․ ․ ․, ), = (, ․ ․ ․, )을 두 연결 리스트라 하자. 두 리스트를 병합하여 m n 이면 = (x1, y1, x2, y2, ..., xm, ym, xm+1, ..., xn), m > n 이면 = (x1, y1, x2, y2, ..., xn, yn, yn+1, ..., ym )을 얻는 함수를 작성하라.
8. 연결 리스트를 왼쪽에서 오른쪽으로 순회해 나가는 동안 링크를 반대로 만들어 양 방향으로 이 리스트를 순회해 나가는 것이 가능하다. (즉, 왼쪽에서 오른쪽으로, 그리고 제한적으로 오른쪽에서 왼쪽으로) 변수 ptr은 현재 시험하고 있는 노드를 가리키고, left는 그 왼쪽 노드를 가리킨다. ptr의 왼쪽에 있는 모든 노드들의 링크가 반대로 되어있다.
(a) 주어진 위치에서 ptr을 n 노드만큼 오른쪽으로 옮기는 함수를 작성하라.
(b) 주어진 위치에서 ptr을 n 노드만큼 왼쪽으로 옮기는 함수를 작성하라.
4.3절
1. 회문(palindrome)은 앞에서나 뒤에서나 철자가 같은 단어나 구를 말한다. 예를 들어 “reviver" 와 "Able was I ere I saw Elba"는 모두 회문이다. 단어나 구가 회문이 되는지는 스택을 이용해서 검사할 수 있다. 단어나 구가 회문이면 TRUE를, 아니면 FALSE를 반환하는 함수를 작성하라.
2. 수식에 있는 중첩된 괄호의 짝이 맞는지를 스택을 이용해서 검사할 수 있다. 이를 수행하는 함수를 작성하라.
4.4절
7. [프로그래밍 과제] 다항식들을 표현하고 관리하는 연결 할당 시스템(linked allocation system)을 설계하고 작성하라. 헤드 노드를 가진 원형 연결 리스트를 사용하고, 다항식의 각 항은 다음 구조를 가진 노드로 표현한다.
#include
#include
/* 리스트 노드 구조체 :
데이터와 노드 포인터를 가진다.
*/
typedef struct list_node *list_pointer;
typedef struct list_node{
int data;
list_pointer link;
} list_node;
// 함수 원형들을 선언
int length(list_pointer p);
void print_list(list_pointer p);
void create_node(list_pointer *p);
void list_delete(list_pointer p);
/* 메인함수 :
리스트의 추가, 삭제, 프린트와 길이 계산 가능
*/
void main()
{
// 메뉴 선택을 위한 변수
int c;
// 리스트의 길이를 헤아리기 위한 변수
int count;
// 리스트의 최상위 포인터
list_pointer ptr = NULL;
while (1)
{
.....
c로 쓴 자료구조론
<이석호 저>
<교보문고>
연습문제 4장 풀이입니다.
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
