과연 이 문제가 맞는것인지...
글쓴이: sadrove / 작성시간: 금, 2003/09/19 - 2:57오후
먼저 제가 해야할 일을 부탁드려서 죄송합니다..
제가 원하는 건 문제를 풀어달라는게 아니라...문제가 잘못된것인지..
아니면 제가 잘못 생각하고 있는것인지 알고 싶어서요.. :(
일단 문제는 다음과 같습니다.
Quote:
n(>1)개의 리스트가 1차원 배열 space[m]에 순차적으로 표현된다고 가정하자
0 <= i < n 에 대해 front[i]는 i번째 리스트의 첫째 원소 위치보다 1이 작은 위치를, rear[i]는 i번째 리스트의 마지막 원소를 가리킨다고 하자.
rear[i] <= front[i+1], 0<= i < n이고 front[n] = m-1 이라고 가정한다.
이 리스트에 대해 삽입과 삭제를 수행하는 함수들이다.
문제 : front[i]와 rear[i]에 대한 적절한 초기화와 경계조건을 구하라.
원형큐를 말하는 것 같은데..아무리 봐도 이상합니다..
1. front[i]는 i번째 리스트의 첫째 원소 위치보다 1이 작은 위치
이 말 이상하지 않은가요..? 도대체 어느 위치를 말하는 걸까요. i=3이라고 한다면 3번째 리스트의 첫째원소 위치? i는 위치를 말하는건데 위치의 첫째원소라뇨..?... 전 일단, i를 3이라고 했을경우 1이 작은 위치니까 front[i]는 space[2]위치를 가리킨다고 생각했습니다..
2. rear[i] <= front[i+1] 이 부분입니다..
rear[i]는 space배열의 마지막 위치이고, front[i]는 임의의 i위치보다 1이 작은 위치인데 어떻게 front[i+1]이 rear[i]보다 작을 수가 있죠..?..같을 수는 있겠지만요...
3. 제 말대로 한다면 초기화는 front[i] = 0; rear[i] = m-1; 이 될 것 같은데..
경계조건이란 rear가 front와 같아질 경우 더이상 데이터삽입을 못하게 하는
것을 말하는 거 같구요...
4. 대체 이 문제는 어떻게 생긴 자료구조를 말하는 걸까요..?.. :?
몇시간째 같은 문제로 고민중이네요..
그냥 누군가가 문제가 이상한거야~ 라고 한마디만 해주면 좋으련만.. :D
한 수 가르침 부탁드립니다..^^
Forums:
문제대로 space[m]에 n개의 리스트의 데이터들이 순차적으로 저장됩니
문제대로 space[m]에 n개의 리스트의 데이터들이 순차적으로 저장됩니다.
즉 space[m] = { 0번째 리스트의 첫번째 데이터, 0번째 리스트의 두번째 데이터, ..., 0번째 리스트의 마지막 데이터, 1번째 리스트의 첫번째 데이터, ...,
(n-1)번째 리스트의 첫번째 데이터, ..., (n-1)번째 리스트의 마지막 데이터 }
대충 이런 형태입니다.
front[i]+1는 i번째 리스트의 첫번째 데이터가 space[m]상에서 몇번째에 위치하고 있는 지를 나타냅니다.
또한 rear[i]는 i번째 리스트의 마지막 데이터가 space[m]상에서 몇번째 원소인지를 나타내구요.
순차적으로 놓여있으니 당연히 rear[i] <= front[i+1]이겠지요..
도움이 되었을지..
답변감사드립니다..그런데..
답변 감사드립니다..
제가 잘못 생각했었나봐요..^^..
그런데...그래도 한가지 의문점은요...
만일 데이터가
0번째 리스트 : 1,2,3,4
1번째 리스트 : 5,6,7,8
2번째 리스트 : 9,10,11,12
라면
space배열은 : 1,2,3,4,5,6,7,8,9,10,11,12 겠죠..?
i가 만일 1이라고 가정한다면요..
front[i+1]와 rear[i]는요...
각각 '6' 데이터 위치와 '8'데이터 위치 같은데요...
어떻게 이게 rear[i] <= front[i+1] 이렇게 되는지 이해가 안됩니다...
아고..또 잘 못 생각하는 것 같은 불길한 예감이..^^;...
[quote]0번째 리스트 : 1,2,3,4 1번째 리스트 : 5,6
i=1이면
rear[i]=rear[1]=8의 위치=7
front[i+1]=front[2]=(9의 위치)-1=8-1=7
따라서 rear[1]<=front[2]가 만족됩니다.
..
i가 1이라면 front[i+1]은 front[2]이 므로
2번째 리스트의 9의 위치에서 -1을 한 '8'의 위치가 되겠네요
( 배열이 0부터 시작하므로 실제 값은로는 7이 겠죠)
rear[1]또한 '8'의 위치를 가리키겠네요.
여기서는 front[i+1] == rear[i] 가 동일하게 나왔네요..
i번째 리스트의 마지막 위치가 (즉 rear[i]) 가 i+1번째 리스트의 첫 위치
보다 작아야 되는 것은 당연하겠죠..
감사합니다..
말끔히 이해가 되었네요..^^..
감사합니다..꾸벅..
앗..죄송..한가지만 더..
에고..결국 다시 질문을 올리네요..^^...죄송..
자료구조는 이해했는데요...
이 space배열에 값을 삽입하려는데...
굳이 front[]와 rear[] 이렇게 두개가 있을 필요가 있을까요..?
걍 변수 하나만 있어도 충분히 값을 넣을 수 있지 않나요...?
왜 저리 힘들게 되어 있는지 모르겠습니다..
front가 굳이 리스트의 첫번원소 위치보다 1이 작은 위치값을 갖는지도 모르겠고요...
뭔가 그럴만한 이유가 있는거겠죠..?.^^
댓글 달기