자료구조(2) : 선형 리스트의 응용 및 구현

쓰고싶은 글씁니다.

 

이번에는 선형리스트의 응용과 구현에 대해 공부했다. 

근데 사실 제목대로라면 구현은 겁나쉽다. 그냥 배열이니까. 그러니 정확히는 응용을 구현한것이다. 제목은 좀 부정확하지만, 내가 공부한 책 부제목이 저렇다. 그래서 딱히 안바꿨다. 뭐라고 제목지어야할지 생각하기 싫어서.....

 

암튼 공부한걸 여기다가 적으면서 이해한걸 다시한번 돌아보는 의미를 갖을려고 글을 쓰는데,  이번에는 글을 쓰기가 힘들다. 

 

이번챕터에서는 선형리스트로 다항식과 행렬을 표현하는것을 공부했는데, 여기다가 내가 짠 코드를 올리기도 그렇고,  일일이 설명하기도 애매하다. 그래서 대충 다항식과 행렬의 추상자료형은 설명하지 않고, 그 둘을 어떻게 나타내는지만 써야겠다.

 

다항식의 경우 A(n)x^n +...... + A(0)x^0의 형태를 띄는데, 지금 이거 보고 선형리스트 같다는 생각이 들었다면, 성공이다. 그냥 배열형태로 짜면 된다. 책에서는 구조체의 형태로 짜서 최고차수를 저장하는 변수와 각 차수에 해당하는 계수를 저장하는 배열로 되어있다. 이정도 들었으면 알아서 짤수 있을거라 생각한다.

하지만, 희소 다항식이란게 있다고 한다. 예시로 x^1000 + x + 1이런 식이다.

이런놈들을 방금과 같이 짠다고 생각해보면, 차수 1000부터 x의 차수 1까지 많은 공간이 낭비될것이다. 그래서 그냥 이차원 배열로 첫번째 열에는 계수 두번째 열에는 차수로 짤수도 있다고 한다.

 

행렬도 동일하다. 이차원배열의 형태로 똑같이 대응하는 경우도 있지만, 희소 행렬 즉 원소 대부분이 0인 행렬들은 공간의 활용도가 많이 떨어지므로 이차원배열로 열을 3까지 설정한뒤, 첫번째 열은 x좌표 두번째 열은 y의 좌표  세번째 열은 해당 값으로 저장하기도 한다. 

 

나머지 추상자료형들은 인터넷 검색하거나 책보면 나올것이므로, 알아서 찾아서 공부하자.