[HUFS/자료구조] #3 리스트와 집합

리스트(list) / 선형 리스트(linear list)

집합과 달리 순서를 가진 항목들의 모임이다

자료의 접근 위치가 자유롭다

리스트 ADT(추상자료형) ~ insert와 append의 차이!

리스트의 배열 구조와 연결된 구조의 차이

리스트 용어 정리

파이썬 리스트

일반적으로 사용하던 파이썬에서의 리스트 개념이다

 

처음부터 필요한 양보다 넉넉한 용량을 사용하는데, 여기서 데이터가 더 들어온다면,,

확장된 새로운 배열을 만들고 기존 배열을 복사해 추가 삽입한다 /  동적 배열(dynamic array)

파이썬 리스트의 시간 복잡도

함수 배열로 구현한 리스트

전역변수와 함수로 리스트 ADT를 구현한다

확장된 리스트에 영향을 주기 위해 함수에 global 추가

클래스 배열로 구현한 리스트

생성자와 self를 활용하는 것 외에는 거의 유사하다

변수만 추가하면 여러 리스트를 쓸 수 있어서 편하다

라인 편집기

텍스트 파일을 편집할 수 있는 라인 편집기를 구현해보자

class ArrayList:          
    def __init__( self ):
        self.items = []        
    def insert(self, pos, elem) :
        self.items.insert(pos, elem)
    def delete(self, pos) :
        self.items.pop(pos)
    def isEmpty( self ):
        return self.size() == 0
    def getEntry(self, pos) :
        return self.items[pos]
    def size( self ):
        return len(self.items)
    def clear( self ) :
        self.items = []    
    def find(self, item) :
        return self.items.index(item)
    def replace(self, pos, elem) :
        self.items[pos] = elem
    def sort(self) :
        self.items.sort()
    def merge(self, lst) :
        self.items.extend(lst)
    def display(self, msg='ArrayList:' ):
        print(msg, self.size(), self.items)
        
def myLineEditor() :    
    list = ArrayList()    
    while True :
        command = input("[메뉴선택] i-입력, d-삭제, r-변경, p-출력, l-파일읽기, s-저장, q-종료=> ")
        if command == 'i' :        
            pos = int( input("  입력행 번호: "))
            str = input("  입력행 내용: ")        
            list.insert(pos, str)        
        elif command == 'd' :            
            pos = int( input("  삭제행 번호: "))
            list.delete(pos)            
        elif command == 'r' :            
            pos = int( input("  변경행 번호: "))
            str = input("  변경행 내용: ")        
            list.replace(pos, str)                
        elif command == 'q' : return            
        elif command == 'p' :                    
            print('Line Editor')
            for line in range (list.size()) :   
                print('[%2d] '%line, end='')    
                print(list.getEntry(line))      
            print()                                
        elif command == 'l' :                    
            filename = 'test.txt'
            infile = open(filename , "r")       
            lines = infile.readlines()            
            for line in lines:                    
                list.insert(list.size(), line.rstrip('\n'))
            infile.close()            
        elif command == 's' :        
            filename = 'test.txt'
            outfile = open(filename , "w")
            for i in range(list.size()) :
                outfile.write(list.getEntry(i)+'\n')
            outfile.close()
myLineEditor()

집합(set)

원소의 중복을 허용하지 않고 선형 자료구조가 아니기 때문에 순서가 없다

집합의 ADT(추상자료형)

리스트로 집합을 구현

집합의 연산들 (중복 체크를 위해 if문이 추가됨) / 밑은 합집합, 교집합, 차집합

 이러한 리스트/집합 추상 자료형들로 코드를 작성할 수 있어야 한다!