[자료구조] 순차자료구조와 선형리스트

(2020.12.17)

 

참고 도서

https://book.naver.com/bookdb/book_detail.nhn?bid=10896666

C로 배우는 쉬운 자료구조

시험을 앞두고,,, 정리 중,,, (시험 하루 전)

자료구조 재수강을 위해 열심히 정리 중이다...

 

---

 

 

순차 자료구조

▶ 순차 자료 구조의 개념

구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장하는 구현 방식

 

▶ 순차 자료 구조의 메모리 저장 방식

메모리의 저장 시작 위치부터 빈자리 없이 자료를 순서대로 연속하여 저장한다.

논리적인 순서와 물리적인 순서가 일치하는 구현방식이다.

 

▶ 순차 자료 구조의 연산 특징

삽입 삭제 연산을 해도 빈자리 없이 자료가 순서대로 연속하여 저장된다.

변경된 논리적인 순서와 저장된 물리적인 순서가 일치한다.

 

▶ 순차 자료 구조의 프로그램 기법

배열을 이용한 구현

 

 

---

 

선형 리스트

 

▶ 리스트

리스트 이름 = ( 원소 1, 원소 2, ..., 원소 n )    //리스트 표현 형식

공백 리스트 이름 = ( )                          // 공백 리스트 형식

 

 

▶ 선형 리스트의 구분

선형 리스트는 메모리에 저장하는 구현 방식에 따라 위처럼 구분된다.

 

▶ 순차 자료구조에서의 원소의 위치

순차 자료구조는 원소들이 순서대로 연속하여 저장되기 때문에

시작 위치와 원소 크기를 알면 특정 원소의 위치를 쉽게 알 수 있다.

​

시작 위치가 a, 원소의 크기가 n인 선형리스트

i번째 원소의 위치= a + (i-1) x n

 

 

▶ 선형 리스트에서의 원소 삽입

선형 리스트는 순차 자료구조 방식으로 구현하기 때문에 삽입 후에도 논리적 순서와 물리적 순서가 일치해야한다.

--> 물리적으로 원소를 삽입할 자리를 마련한 후 원소를 삽입해야한다.

--> 삽입할 위치 다음에 있는 원소를 한 자리씩 미뤄야한다.

 

 

♬ 원소가 n개인 선형 리스트에 k번 자리에 원소를 삽입하기 ♬

k번 원소부터 마지막 원소인 (n-1)번 원소까지 총 (n-1) - k + 1 개 원소를 옮겨야한다.

--> 빈자리를 만들기 위한 이동 횟수 = (n-1) - k + 1 = ( 마지막 원소의 인덱스 ) - ( 삽입할 자리의 인덱스 ) + 1

 

 

▶ 선형 리스트에서의 원소 삭제

선형 리스트 에서의 원소 삽입과 마찬가지로 논리적 순서와 물리적 순서가 일치해야한다.

--> 원소를 삭제한 위치 뒤에 있는 원소를 모두 한 자리씩 앞으로 옮겨야한다.

♬ 원소가 n개인 선형 리스트에 k번 자리에 있는 원소를 삭제하기 ♬

(k+1) 번 원소부터 마지막 원소인 (n-1)번 원소까지 총 (n-1) - (k-1) + 1 개 원소를 옮겨야한다.

--> 필요한 이동 횟수 = (n-1) -(k+1)+1 = n - 1 - k = ( 마지막 원소의 인덱스 ) - (삭제한 원소의 인덱스)

 

---

선형 리스트의 구현

 

▶ 1차원 배열을 이요한 선형 리스트 구현

int age [4] = { 15,20,52,57 }

 

▶ 2차원 배열을 이용한 선형 리스트의 구현

2019~2020년 분기별 붕어빵 판매량 리스트

int boong[2][4] = {{04,27,06,13},{01,95,10,13}};

2019~2020 분기별 붕어빵 판매량 선형 리스트

 

2차원 배열 구조를 논리적으로 표현할 때는 행과 열의 구조로 나타내고,

이를 메모리에 저장할 때는 1차원 구조로 저장된다.

--> 2차원 논리적 순서가 1차원 물리적 순서로 변환된다.

--> 이때, 행우선 순서와 열 우선 순서 두가지의 방법이 있다.

 

 

 

 

♬ 행 우선 순서 방법 ♬

위의 리스트를 행 우선 순서 방법으로 나타내면 밑의 그림과 같은 순서가 된다.

행을 기준으로 같은 행 안에 있는 열을 먼저 저장하는 방법이다.

 

 

 

 

♬ 열 우선 순서 방법 ♬

위의 리스트를 열 우선 순서 방법으로 나타내면 밑의 그림과 같은 순서가 된다.

열을 기준으로 같은 열 안에 있는 행을 먼저 저장하는 방법이다.

​

 

​▶ 행 우선 순서 방법과 열 우선 순서 방법에서의 원소의 위치

 

행의 개수가 ni이고, 열의 개수가 nj인 2차원 배열 A[i][j]의 시작 주소가 a이고, 원소의 길이가 l이다.

A[i][j]의 위치

--> 행 우선 순서 방법 : a + ( i x nj + j ) x l

--> 열 우선 순서 방법 : a + ( j x ni + i ) x l

 

 

---

 

다항식의 선형 리스트 표현

 

P(x)= 6x427 + x2 + 3 을 2차원 배열을 이용한 순차 자료구조로 만들면,

이 다항식은 최고차항이 427이지만, 항의 개수는 3개밖에 없는 희소 다항식이기 때문에

2차원 배열로 표현하는 것이 좋다.

 

 

---

 

행렬의 선형 리스트 표현

 

♪ 행렬: 행과 열로 구성된 자료구조

행 m개, 열 n개이면 m x n 행렬이라고 한다.

--> 이 행렬을 구성하는 원소 개수는 (m x n ) 개가 된다.

​

♪ 전치행렬: 행렬의 행과 열을 서로 바꿔 구성한 행렬

m x n 행렬의 전치행렬은 n x m 행렬이 된다.

​

전치행렬로 변환

 

​

♪ 희소행렬

희소행렬 H의 2차원 배열 표현 1

 

​

​

희소행렬 H의 2차원 배열 표현 2

 

​

두번째 2차원 배열 표현이 훨씬 자리가 적게 드는 것을 볼 수 있다.

​

---

처음부터 티스토리를 하던가... 블로그로 시작했으면 블로그를 계속 하던가... 왜 둘다 하느라 이렇게 시간을 쓰고 있는건지.....

블로그에 있는거 티스토리로 옮기고 티스토리에 새로 올린거 블로그에 다시 올리고... 

그치만 둘다 포기 할 수 없다!!!!!!!!

둘 중에 하나를 고를 수가 없다.... 나중엔 블로그 버릴듯...

둘다 열심히 올려야지.....