참된코딩

▷ 단방향 연결 리스트(Linked List)

형태

▷구성방법

시작전.

 1). 데이터를 담을 구조체를 만든다.

 2). 헤드(Head)변수를 만든다.

0. 데이터 출력.

 1). 헤드를 가르킬 임시 노드 변수를 만든다.

 2). 노드가 null이 아닐경우 그 노드가 가지고 있는 데이터를 출력한다.

 3). 노드를 한칸 앞으로 이동해준다.

 4). 현재 노드가 null이 나올때까지 2~3번을 반복한다.

1. 데이터 추가

 1). 노드를 생성한다.

 2). 헤드의 포인터를 처음 생성된 노드에 가르킨다.

 3). 노드를 생성한다.

 4). 헤드를 가르킬 임시 노드 변수를 만든다.

 5). 현재 노드가 가르키는게 null이 나올때까지 노드 이동을 한다.

 6). 현재 노드가 가르키는게 null일경우 새롭게 추가한 노드를 가르킨다.

 7). 데이터를 추가 할 때 마다 4~6번을 반복한다.

2. 데이터 모두 삭제.

 1). 헤드를 담을 임시 노드 변수를 생성한다.

 2). 헤드 노드를 한 칸 앞으로 이동시킨다.

 3). 임시 노드 변수를 삭제한다.

 4). 헤드가 가르키는 노드가 null일때까지 1~3번을 반복한다.

3. 데이터 선택 삭제

 1). 자신이 삭제할 데이터를 담을 변수를 하나 만들어서 데이터를 입력받는다

 2). 첫 번째 노드(헤드)가 삭제할 데이터이면 새로운 노드 변수를 만들어 헤드를 담고

     헤드를 한 칸 전진한 뒤 만든 변수를 삭제.

 3). 첫 번째 노드(헤드)가 삭제할 데이터가 아니라면 헤드를 담을 변수와 헤드를 담을 변수의 전 노드를 가르킬 변수를

     만든다.

 4). 노드를 한 칸씩 전진 시키며 자신이 입력한 데이터와 같은지 비교한다. 

 5). 같다면 삭제 전용 변수의 포인터를 처음 만든 노드에 가르키고 두 번째 만든 노드는 처음 만든 노드가 가르키는 노드를 가르      킨다.

 6). 삭제 전용 노드 변수를 삭제한다.

4. 데이터 선택 추가.

  1). 삽입할 데이터를 입력받는다.

  2). 몇 번째에 삽입할건지 인덱스를 입력 받는다.

  3). 첫 번째 인덱스에 데이터를 삽입할 경우 새롭게 만든 노드를 헤드에 연결시킨 뒤

      헤드를 새롭게 만든 노드를 가르킨다.

  4). 첫 번째 인덱스에 데이터를 삽입하는게 아닐경우 입력받은 인덱스 - 1 만큼 노드를 이동한다.

      새롭게 만든 노드를 현재 노드의 다음 노드에 연결 시킨뒤 현재 노드의 포인터를 새롭게 만든 노드에 가르킨다.

0). 데이터 출력 (Data DisPlay)

1). 데이터 추가(DataAdd)

2). 데이터 모두 삭제(Data All Delete)

3). 데이터 선택 삭제(Data Select Delete)

예외처리 추가.

4). 데이터 선택 삽입(Data Select Insert)

▷ 연결 리스트(Linked List)

1. 단방향 연결 리스트.

- 한쪽 방향으로 연결된 리스트이다.

- 자료 생성시 노드가 생성되고 포인터는 생성된 포인터를 가르킨다.

2. 양방향 연결 리스트

- 양쪽 방향으로 연결된 리스트이다.

- 자료 생성시 노드가 생성되고 포인터는 생성된 포인터를 가르킨다.

그리고 새로 생성된 노드의 포인터는 전 노드를 가르킨다.

3. 환형 연결 리스트

- 양방향 연결 리스트와 비슷하지만 마지막 노드의 포인터가 가리키는 노드는 리스트의 처음 노드이다.

장점: 늘어선 노드의 중간지점 자료의 추가와 삭제가 O(1)의 시간내에 가능하다.

단점: 특정 위치의 데이터를 검색하는데에 O(n)의 시간이 걸린다는 단점이 있다.

▷ 퀵 정렬 (Quick Sort)

 정렬 알고리즘 중에 평균 실행 속도가 가장 빠르고 우수하므로 퀵 정렬(Quick sort)라는 명칭으로 불린다.

▷ 정렬방법.

1. 먼저 PIVOT 계수를 정한다. PIVOT 계수는 임의로 선정할 수 있으나, 중간 크기의 숫자를 PIVOT 계수로 선정하는 것이 가장 효율적이기 때문에 대부분 3개의 임의의 숫자를 랜덤으로 선택한 후 3개 중 가운데 값을 PIVOT 계수로 정한다.

2. PIVOT 값과 LEFT 값을 비교한다. 만약 LEFT 값이 PIVOT 값보다 크다면 PIVOT 값과 RIGHT 값을 비교한다.

RIGHT 값이 PIVOT 값보다 크다면, RIGHT 인덱스를 왼쪽으로 위치시킨 후 다시 PIVOT 값과 비교한다.

3. RIGHT 값이 PIVOT 값보다 작다면, LEFT 값과 RIGHT 값을 바꾼 후, LEFT 값을 오른쪽으로 한칸 전진시킨다.

4. LEFT 값과 RIGHT 값이 만날 때까지 2~3번 과정을 반복한다.

5. LEFT와 RIGHT가 만나면 해당 값과 PIVOT 값을 비교한다. PIVOT 값이 크면 오른 쪽 작으면 왼쪽에 위치 시킨다.

6. 3을 기준으로 블록을 크게 3보다 큰 값, 3보다 작은 값으로 나뉘게 된다. 3보다 작은 블록에 대해 다시 PIVOT 계수를 설정한다.

7. 기존에 한 방식대로 다시 LEFT와 RIGHT 값을 PIVOT과 비교한 후, 값을 교환한다.

8. 3보다 큰 블록에 대해서도 위와 같이 비교한다.

9. 최종 sorting이 완료된다.

Code.

결과