-스택 리스트

-결과

구현 소스

실행 화면

예제소스

원하는 만큼의 데이터를 입력받고 출력

#include stdio.h
#include stdlib.h
#include conio.h

void main() {
	int i, input;
	int *arr;
	printf("몇개의 숫자 데이터를 입력하실건가요? : ");
	scanf("%d", &input);
	arr = (int *)malloc(sizeof(int)*input);	//입력받은 n만큼 동적할당

	printf("차례대로 입력하세요.\n");
	for (i = 0; i < input; i++)
	{
		scanf("%d", &arr[i]);
	}

	printf("입력된 데이터는 ");
	for (i = 0; i < input; i++)
        {
		printf("%d ", arr[i]);
	}
	printf("입니다\n");
	getch();
}

실행화면

큐(Queue)란?

 큐는 리스트의 한쪽 끝에서만 삽입과 삭제가 일어나는 스택과는 달리 리스트의 한쪽 끝에서는 원소들이 삭제되고 반대쪽 끝에서는 원소들의 삽입만 가능하게 만든 순서화된 리스트. 가장 먼저 리스트에 삽입된 원소가 가장 먼저 삭제되므로 선입 선출(先入先出)인 FIFO(first in first out) 리스트라고 한다.

[그림 7-28] 큐 구조

ㆍ한쪽에서는 입력만 다른 한쪽에서는 출력만 가능함.(입구와 출구가 다름)

ㆍ먼저 입력한값이 먼저 출력 → First Input First Out  → FIFO 라고불림

 구현 소스

스택(Stack)이란?

 스택(stack)은 모든 원소들의 삽입(insert)과 삭제(delete)가 리스트의 한쪽 끝에서만 수행되는 제한 조건을 가지는 선형 자료 구조(linear data structure)로서, 삽입과 삭제가 일어나는 리스트의 끝을 top이라 하고, 다른 한쪽 끝을 bottom이라 한다. 스택의 top에 새로운 원소를 삽입하는 것을 push라 하고, 가장 최근에 삽입된 원소를 의미하는 스택의 top으로부터 한 원소를 제거하는 것을 pop이라 한다.

ㆍTop이라고 불리는 한쪽 끝에서만 삽입 삭제가 행해짐.(입구와 출구가 같음)

ㆍ나중에 입력한값이 가장 먼저 출력 → Last Input First Out  → LIFO 라고불림

 구현 소스

Stack보고서.hwp

이진 탐색이란?

이진 탐색(binary search)이라는 말 그대로 탐색하는 방법중 하나인데 순차 탐색과는 다르게 정렬된 데이터 집합을 이분화하면서 탐색하는 것이다.

예를들면, 가나다순으로 정렬되어 있는 전화번호부에서 임의의 사람에 대한 전화번호를 찾는 경우가 있다.

[그림 8-5]의 정렬된 데이터 집합에서 이진 탐색을 이용해 데이터 15를 탐색하는 과정을 살펴보자.

[그림 8-5] 이진 탐색을 위한 데이터 집합

① 중간에 위치한 데이터인 11과 찾고자 하는 15가 같은지 비교한다.

② 중간에 위치한 데이터인 11보다 찾고자 하는 데이터인 15가 크므로 중간 데이터 11의 오른쪽에 위치한 데이터들에 대해 이진 탐색을 수행한다.

③ 탐색 영역의 중간에 위치한 데이터인 17과 찾고자 하는 15가 같은지 비교한다.

④ 중간에 위치한 데이터인 17보다 찾고자 하는 데이터인 15가 작으므로 중간 데이터 17 왼쪽에 위치한 데이터들에 대해 이진 탐색을 수행한다.

⑤ 탐색 영역의 중간에 위치한 데이터인 15와 찾고자 하는 15가 같은지 비교한다. 원하는 데이터이므로 탐색을 종료한다.

내가짜본

이진탐색 소스(c언어)

이진탐색의 장점과 단점

-장점 : 이진탐색 방법은 순차탐색처럼 하나하나 일일히 값을 확인하지 않고 효과적으로 원하는 값을 찾아낼 수 있다.

-단점 : 배열이 반듯히 정렬되어 있어야 한다는 제약이있다.

버블정렬과 선택정렬은 정렬되지 않은 배열을 정렬하는 가장 기초적이면서 방법이다.

→버블 정렬(bubble sort)은 서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방식이다.

[그림 8-1] 정렬되지 않은 데이터

① 가장 작은 데이터인 1을 가장 앞에 위치한 15와 교환한다. 가장 작은 데이터가 가장 앞에 위치하게 된다.

② 첫 번째 데이터를 제외한 나머지 데이터에서 가장 작은 데이터인 3을 두 번째 데이터인 11과 교환한다.

③ 첫 번째, 두 번째 데이터를 제외한 나머지 데이터에서 가장 작은 데이터인 8을 세 번째 데이터인 15와 교환한다.

④ 첫 번째, 두 번째, 세 번째 데이터를 제외한 나머지 데이터에서 가장 작은 데이터인 11을 네 번째 데이터인 11과 교환한다. 같은 데이터이므로 위치의 변화는 없다.

⑤ 데이터들에 대한 정렬이 완료된다.

 

[네이버 지식백과] 버블 정렬 (컴퓨터 개론, 2013.3.10, 한빛아카데미(주))

내가짜본

버블정렬 소스(c언어)

→선택 정렬(selection sort)은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다. 

[그림 8-3] 정렬되지 않은 데이터

① 첫 번째 데이터인 15와 두 번째 데이터인 11을 비교해 큰 데이터를 뒤로 위치시킨다. 15가 크므로 둘의 위치를 바꾼다.

② 두 번째 데이터인 15와 세 번째 데이터인 1을 비교하는데, 앞에 위치한 15가 크므로 둘의 위치를 바꾼다.

③ 마찬가지 방식을 적용해 세 번째 데이터인 15와 네 번째 데이터인 3의 위치를 바꾼다.

④ 마찬가지 방식을 적용해 네 번째 데이터인 15와 마지막 데이터인 8의 위치를 바꾼다. 가장 큰 데이터인 15가 가장 뒤에 위치하게 된다.

⑤ 처음부터 다시 시작한다. 첫 번째 데이터인 11과 두 번째 데이터인 1의 크기를 비교하는데 앞에 위치한 11이 크므로 둘의 위치를 바꾼다.

⑥ 마찬가지 방식을 적용해 두 번째 데이터인 11과 세 번째 데이터인 3의 위치를 바꾼다.

⑦ 마찬가지 방식을 적용해 세 번째 데이터인 11과 네 번째 데이터인 8의 위치를 바꾼다. 두 번째로 큰 데이터인 11이 뒤에서 두 번째에 위치하게 된다.

⑧ 처음부터 다시 시작한다. 첫 번째 데이터인 1과 두 번째 데이터인 3의 크기를 비교하는데 앞에 위치한 1이 작으므로 그대로 둔다.

⑨ 두 번째 데이터인 3과 세 번째 데이터인 8의 크기를 비교하는데, 앞에 위치한 3이 작으므로 그대로 둔다. 세 번째로 큰 데이터인 8이 뒤에서 세 번째에 위치하게 된다.

⑩ 처음부터 다시 시작한다. 첫 번째 데이터인 1과 두 번째 데이터인 3의 크기를 비교하는데, 앞에 위치한 1이 작으므로 그대로 둔다. 데이터들에 대한 정렬이 완료된다.

 

[네이버 지식백과] 선택 정렬 (컴퓨터 개론, 2013.3.10, 한빛아카데미(주))

내가짜본

선택정렬 소스(C언어)

두 정렬방법의 공통점과 차이점

-공통점 : 배열을 정렬하는 기초적인 방법으로 효과적이지 못하다.

-차이점 : 버블정렬은 인접한데이터 끼리 서로 비교를 통해 서로 데이터를 바꾸어 비효율적이지만 그에비에 선택정렬은 가장 작은 값을 먼저 찾은다음 서로 데이터를 바꾸어 비교적 효율적이다.