[자료구조] 중간고사 요점정리

-자료구조 이론 (중간고사) 시험정리

 

-1강.

알고리즘 : 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법.

알고리즘을 기술하는 데는 자연어, 흐름도, 의사 코드, 프로그래밍 언어 방법이 있다.

수행시간이 짧을수록 효율적인 알고리즘.

수행시간 측정방법 #include<time.h> 선언, start=clock()//측정할 코드//finish=clock()

duration=(double)(finish-start)/CLOCKS_PER_SEC; 사용.

알고리즘의 복잡도는 대게 시간복잡도를 말함.

시간복잡도 : 수행시간이 아닌 연산들이 몇 번이나 수행되는지를 숫자로 표시.

빅오 표기법 : 함수에서 차수가 가장 큰 항만을 고려하면 충분.

O(1)->O(logn)->O(n)->O(nlogn)->O(n²)->O(n³)->O(2ⁿ)->O(n!)//숫자↑, 복잡도↑

빅오 표기법 이외에 빅오메가 표기법(하한 표시), 빅세타 표기법(가장 정밀)도 존재.

최선, 평균, 최악 중 최악의 경우의 수행시간이 시간복잡도의 척도로 많이 쓰임.

 

-2강.

recursion(순환) : 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 함.

문제 해결을 위한 두 가지 방식 : Recursive algorithm, Iterative algorithm.

Recursive call이 일어나지 않는 부분이 반드시 존재해야 함.

순환 알고리즘은 이해하기 쉽고 프로그래밍이 쉬운 장점.

순환 알고리즘은 수행시간과 기억공간의 사용이 비효율적인 게 단점.

 

-3강.

배열: 타입이 같은 데이터들을 하나로 묶는 방법.

1차원 배열 //문자형 A[i]의 주소는 base + i*sizeof(문자형).

2차원 배열 (M*N)//문자형 A[i][j]의 주소는 base + (i*N + j)*sizeof(문자형)

n차원 배열도 위와 비슷한 방법으로 구함. 배열의 첫 번째 요소는 필요 없음.

구조체 : 타입이 다른 데이터를 하나로 묶는 방법.

구조체 형식을 정의한 후 구조체 변수를 선언해야 함.

typedef를 사용하여 프로그래머가 이해하기 쉬운 타입 이름을 부여함.

다항식의 연산을 구조체 배열에 저장하면 메모리 공간의 효율이↑,연산은 복잡.

dot(.) 멤버 연산자를 사용해서 구조체의 요소에 접근할 수 있다.

구조체 안에 구조체를 넣을 수 있다.

포인터 : 다른 변수의 주소를 가지고 있는 변수

&연산자 : 변수의 주소를 추출 / *연산자 : 포인터가 가르키는 곳의 내용 추출.

포인터의 형변환 : 필요한 때마다 형변환하는 것이 가능하다.

함수 인자 전달 방식인 Call-by-value는 호출한 쪽의 값이 변화되지는 않는다.

함수 인자로 포인터를 사용하면 외부 변수의 값 변경이 가능.

배열의 이름 : 사실상 포인터와 같은 역할.

-> : 구조체의 요소에 접근하는 연산자.

자체 참조 구조체 : 필드 중에 자기 자신을 가르키는 포인터가 존재하는 구조체.

정적 메모리 할당 : 크기가 변경될 수 없다.//메모리 공간 낭비 발생,

동적 메모리 할당 : 메모리를 매우 효율적으로 사용 가능.

동적 메모리 할당 코드 : 변수 = (문자형 포인터)malloc(sizeof(문자형));

동적 메모리 반납 : free(변수)

 

-6강.

리스트 : 순서를 가진 항목들의 모임.

배열로 리스트를 구현할 시 구현이 간단하다는 장점, 크기가 제한되는 단점.

배열로 구현된 리스트에서도 항목 추가 연산, 항목 삭제 연산이 가능.

연결 리스트 사용 시 연산이 용이하고 연속된 메모리 공간이 필요 없고 크기 제한 X.

노드(node) : 리스트의 한 개 항목을 저장하기 위한 구조.

노드의 data type은 data field 와 link field로 구성.

헤드 포인터(head pointer) : 리스트의 첫 번재 노드를 가르키는 변수.

단순 연결 리스트 : 하나의 링크 필드를 이용하여 연결. 마지막 노드의 링크값은 NULL.

단순 열결 리스트의 구성 : typedef int element; typedef struct ListNode {

element data; struct ListNode *link; } ListNode;

노드의 생성 : ListNode *p1; p1 = (ListNode *)malloc(sizeof(ListNode));

삽입의 3가지 경우 : 1. head가 NULL인 경우, 2. p가 NULL인 경우, 3. 일반적인 경우.

삭제의 2가지 경우 : 1. p가 NULL인 경우, 2. p가 NULL인 경우.

방문 연산 : display 함수는 p->link를 p가 NULL이 될 때까지 호출해야 함.

탐색 연산 : p->data 가 찾고자 하는 값 x 와 같을 때 return x 함. 없을 시 NULL 반환.

합병 연산 : 2개의 리스트가 NULL인지 유의, 마지막 노드의 링크를 head2의 연결.

reverse 함수는 순회 포인터를 p,q,r 사용, p는 역순으로 만들 리스트, q는 역순으로 만들 노드, r은 역순으로 된 리스트 r은 q, q는 p를 차례로 따라간다.

 

-7강.

원형 연결 리스트 : 마지막 노드의 링크가 첫 번째 노드를 가르키는 리스트.

원형 연결 리스트는 원칙적으로 헤드 포인터만 있으면 된다.

이중 연결 리스트 : 공간을 많이 차지하지만 두 개의 링크로 선행과 후속 노드를 저장.

헤더 노드(header node) : 리스트의 가장 처음에 나오는 노드, 데이터는 X.

삽입의 경우, 연결하는 순서가 중요함.

삭제의 경우, 양쪽을 같은 방법으로 작성하면 됨.

 

-4강.

Stack : Last In First Out.

스택에는 2가지의 기본 연산이 있다, 하나는 삽입 연산(push), 삭제 연산(pop).

스택에 가장 먼저 들어온 요소 stack[0], 가장 최근에 들어온 요소 stack[top].

올바른 괄호 조건 : 1. 왼쪽 개수 = 오른쪽 개수, 2. 왼쪽 우선, 3. 다른 괄호 쌍과 교차X.