Hoguz

풀어본 결과를 올리는 것일뿐, 정답은 아니라는점... 주륵..

2.7 각각 정렬되어 있는 2개의 단순 연결리스트를 하나의 정렬된 단순연결리스트로 만드는 함수를 작성하시오

(이하 함수는 clsss안에서 만듬)

def add_two(self, slst):

sh = slst.head

fh = self.head

while sh != None:

if fh.item >sh.item:

self.insert_front(sh.item);

sh = sh.next

else:

fh = fh.next

continue;

1. 외부서 리스트를 받는다.

2. 각 리스트의 헤드를 초기화

3.여기서 기준이 될 리스트를 정해준다, 여기선 fh가 기준

원리는 fh, sh를 비교하고 fh보다 작으면 앞에다 넣고

sh를 옆으로 옮긴다. fh는 옮기지 않는다

4. 3이 아닐 경우 기준을 옮겨준다.

node와 item이 좀 헷갈림..

2.10

각 노드에 1개의 정수가 저장된 단순연결리스트와 정수 k가 주어질때 이 단순연결리스트를 하나는 k와 같거나 작은 정수를 가진 연결리스트로, 다른 하나는 k보다 큰 정수를 가진 노드들로만 구성된 연결 리스트로 분리하는 함수를 작성하시오

def seperate(self, k):

s = tdlist();

m = tdlist();

num = 0;

dh = self.head;

while num < self.size:

if dh.item < k:

s.insert_front(dh.item);

dh = dh.next;

num += 1;

elif dh.item >= k:

m.insert_front(dh.item)

dh = dh.next;

num += 1;

elif dh == None:

break;

return(s, m)

1. 두개의 클래스를 만든다. 값을 나눠야 하니까..

2. num은 while의 플래그로 횟수를 카운트 한다.

즉 처음 단순연결리스트의 사이즈 횟수만큼 돌아간다

3. 해당 아이템이 지정된 수 보다 작으면 s, 크거나 같으면 m에 넣는다

여기서도 헷갈리는 부분으 dh와 dh.item, 

None은 노드 값이라 dh.item이 아닌 dh와 비교해야하는 듯

파이썬 자료구조 책 공부중..

챕터2, 2.9번 문제 풀이

1. 제일 마지막 노드의 아이템을 변수에 저장

(제일 첫번째 노드 역시 변수에)

2. insert_after 메서드를 활용하여 self.head를 제일 뒤에 삽입

3. 제일 앞에 노드를 삭제

4. 제일 앞 노드와 1번에서 저장한 변수 값이 같아질때까지 실행

이 함수를 재귀로 돌리면 1번이 계속 리셋이 되서

함수 내에서 while문으로 작성함

def reverse(self):

p = self.head

for i in range(self.size -1):

p = p.next

#이를 통해서 p에 제일 마지막 아이템을 저장.

#여기서 size만큼 돌리게 되면 p에 None이 저장됨

while self.head != p:

self.insert_after(self.head.item, p):

#여기서 self.head는 node 객체(item, link)이므로 

#item만을 넣기 위해 item으로 적용

self.delete_front():

대충 기억나는건 이정도..

파이썬을 이용하여 자료구조 공부중

자료구조를 이해하기에 앞서 노드, 레퍼런스도 정리를 하면 좋다..

우선 해당 노드를 증명? 정의? 하는 것은 바로 앞이라는 점.

orange - apple - kiwi 가 있다고 할때

orange를 정의하는 것은 제일 앞에 있는 head라는 점

따라서 위에 리스트를 다시 적으면

head - head.next - head.next.next(next는 클래스에서 따로 정의) 라 할 수 있다.

스택:

노드는 뒤로 추가되고, 또한 뒤로 나간다.

즉 a, b, c, d 순으로 입력을 하게 되면

d가 제일 뒤에 오고 아웃 시켜도 d가 나온다.

이를 응용해서 1,2,3,4,5 가 순서대로 입력 될때 pop()으로 나타 낼 수 없는 수열 등의 문제가 많이 나온다.

예) 54123은 불가능.

이와 관련하여 해당 입력수들이 트루인지 거짓인지 찾는 코드 작성해봐야지...