데이터 구조: 선형 데이터 구조 (4) - 목록 (스 택, 대기 열, deques, 목록)

리스트
1.1 목록 의 추상 적 인 데이터 형식
목록 은 항목 의 집합 이 며, 각 항목 은 다른 항목 에 비해 상대 적 인 위 치 를 유지 합 니 다.무질서 목록 의 구 조 는 항목 의 집합 이 며, 각 항목 은 다른 항목 에 비해 상대 적 인 위 치 를 유지 합 니 다.다음은 가능 한 무질서 목록 작업 을 보 여 줍 니 다.
  • List () 새 빈 목록 을 만 듭 니 다.인자 가 필요 없 이 빈 목록 을 되 돌려 줍 니 다.
  • add (item) 는 목록 에 새 항목 을 추가 합 니 다.아 이 템 을 매개 변수 로 해 야 합 니 다. 내용 을 되 돌려 주지 않 습 니 다.이 아 이 템 이 목록 에 없다 고 가정 합 니 다.
  • remove (item) 는 목록 에서 이 항목 을 삭제 합 니 다.이것 은 item 을 매개 변수 로 하고 목록 을 수정 해 야 합 니 다.목록 에 항목 이 존재 한다 고 가정 합 니 다.
  • search (item) 검색 목록 의 항목 입 니 다.아 이 템 을 매개 변수 로 하고 불 값 을 되 돌려 야 합 니 다.
  • isEmpty () 목록 이 비어 있 는 지 확인 합 니 다.인자 가 필요 없 이 불 값 을 되 돌려 줍 니 다.
  • size () 는 목록 의 항목 을 되 돌려 줍 니 다.그것 은 인자 가 필요 없 이 정 수 를 되 돌려 줍 니 다.
  • append (item) 는 목록 의 끝 에 새 항목 을 추가 하여 집합 중의 마지막 항목 으로 만 듭 니 다.아 이 템 을 매개 변수 로 해 야 합 니 다. 내용 을 되 돌려 주지 않 습 니 다.이 항목 이 목록 에 없다 고 가정 합 니 다.
  • index (item) 는 목록 에 있 는 위 치 를 되 돌려 줍 니 다.아 이 템 을 매개 변수 로 하고 색인 을 되 돌려 야 합 니 다.이 항목 이 목록 에 있다 고 가정 합 니 다.
  • insert (pos, item) 는 위치 pos 에서 목록 에 새 항목 을 추가 합 니 다.아 이 템 이 필요 합 니 다. 매개 변수 로 내용 을 되 돌려 주지 않 습 니 다.이 항목 이 목록 에 없 으 며 pos 의 위 치 를 가 질 수 있 는 충분 한 기 존 항목 이 있다 고 가정 합 니 다.
  • pop () 은 목록 의 마지막 항목 을 삭제 하고 되 돌려 줍 니 다.이 목록 에 적어도 한 가지 항목 이 있다 고 가정 하 세 요.
  • pop (pos) 은 위치 pos 의 항목 을 삭제 하고 되 돌려 줍 니 다.이것 은 pos 를 매개 변수 로 하고 항목 을 되 돌려 야 합 니 다.이 항목 이 목록 에 있다 고 가정 합 니 다.

  • 1.2 서열 표 가 있 는 추상 적 인 데이터 형식
    순서 목록 의 목록 형식 입 니 다.예 를 들 어 위 에서 보 여 준 정수 목록 이 서열 표 (오름차 순) 라면  17,26,31,54,77 93 。17 이 가장 작은 종목 이기 때문에, 그것 이 1 위 를 차지한다.93 이 가장 크 기 때문에 마지막 자 리 를 차지한다.
    질서 있 는 목록 의 구 조 는 항목 의 집합 이 며, 항목 마다 잠재 적 특성 을 바탕 으로 하 는 상대 적 인 위 치 를 저장 합 니 다.정렬 은 보통 오름차 나 내림차 순 이 며, 목록 항목 이 정 의 된 의미 있 는 비교 연산 을 가지 고 있다 고 가정 합 니 다.많은 서열 표 작업 은 무질서 목록 의 작업 과 같다.
  • OrderedList () 새 빈 목록 을 만 듭 니 다.인자 가 필요 없 이 빈 목록 을 되 돌려 줍 니 다.
  • add (item) 는 목록 에 새 항목 을 추가 합 니 다.아 이 템 을 매개 변수 로 해 야 합 니 다. 내용 을 되 돌려 주지 않 습 니 다.이 아 이 템 이 목록 에 없다 고 가정 합 니 다.
  • remove (item) 는 목록 에서 이 항목 을 삭제 합 니 다.이것 은 item 을 매개 변수 로 하고 목록 을 수정 해 야 합 니 다.목록 에 항목 이 존재 한다 고 가정 합 니 다.
  • search (item) 검색 목록 의 항목 입 니 다.아 이 템 을 매개 변수 로 하고 불 값 을 되 돌려 야 합 니 다.
  • isEmpty () 목록 이 비어 있 는 지 확인 합 니 다.인자 가 필요 없 이 불 값 을 되 돌려 줍 니 다.
  • size () 는 목록 의 항목 을 되 돌려 줍 니 다.그것 은 인자 가 필요 없 이 정 수 를 되 돌려 줍 니 다.
  • index (item) 는 목록 에 있 는 위 치 를 되 돌려 줍 니 다.아 이 템 을 매개 변수 로 하고 색인 을 되 돌려 야 합 니 다.이 항목 이 목록 에 있다 고 가정 합 니 다.
  • pop () 은 목록 의 마지막 항목 을 삭제 하고 되 돌려 줍 니 다.이 목록 에 적어도 한 가지 항목 이 있다 고 가정 하 세 요.
  • pop (pos) 은 위치 pos 의 항목 을 삭제 하고 되 돌려 줍 니 다.이것 은 pos 를 매개 변수 로 하고 항목 을 되 돌려 야 합 니 다.이 항목 이 목록 에 있다 고 가정 합 니 다.

  • 2. 목록 의 python 구현
    2.1 무질서 목록 구현: 링크
    #  
    class Node(object):
        def __init__(self, data, nextNode = None ):
            self.data = data
            self.nextNode = nextNode
        
        def getData(self):
            return self.data
        
        def setData(self, newdata):
            self.data = newdata
    
        def getNext(self):
            return self.nextNode
        
        def setNext(self, newNext):
            self.nextNode = newNext
            
    class unorderedList(object):
        def __init__(self, head = None):
            self.head = head
            
        def isEmpty(self):
            return self.head == None
        
        def add(self, data):
            newNode = Node(data)
            newNode.setNext(self.head)
            self.head = newNode
        
        def size(self) :
            current = self.head
            count = 0 
            while current != None:
                count += 1
                current = current.getNext ()   #
            return count
        
        def search(self, newdata):
            current = self.head
            found = False
            while not found and current != None:
                data = current.getData()
                if newdata == data:
                    found = True
                else:
                    current = current.getNext()
                    
            return found
        
        def remove(self, newdata):
            current = self.head
            previous = None
            found = False
            while not found  :
                data = current.getData()
                if data == newdata:
                    found = True
                else:
                    previous = current
                    current = current.getNext()
            if previous == None:
                self.head = current.getNext()
            else :
                previous.setNext(current.getNext())

    2.2 질서 있 는 링크
    다른 방법 add (), search ().
    #    
    def orderdedList(object):
        def __init__(self, head = None):
            self.head = head
        
        def search(self,item):
            current = self.head
            found = False
            stop = False
            while current != None and not found and not stop:
                if current.getData() == item:
                    found = True
                else:
                    if current.getData() > item:
                        stop = True
                    else:
                        current = current.getNext()
    
        return found
        
        def add(self,item):
            current = self.head
            previous = None
            stop = False
            while current != None and not stop:
                if current.getData() > item:
                    stop = True
                else:
                    previous = current
                    current = current.getNext()
    
            temp = Node(item)
            if previous == None:
                temp.setNext(self.head)
                self.head = temp
            else:
                temp.setNext(current)
                previous.setNext(temp)

    기타 데이터 구조 원리 소개 실현:
    창고:https://blog.csdn.net/qq_18888869/article/details/88086002
    대기 열:https://blog.csdn.net/qq_18888869/article/details/88134592
    deque:https://blog.csdn.net/qq_18888869/article/details/88137237
    github 코드:https://github.com/makang101/python-data-structure

    좋은 웹페이지 즐겨찾기