문과생이 이해한 파이썬 연결리스트1-연습문제

#c언어로 쉽게 풀어쓴 자료구조 연습문제를 파이썬 코드로 구현

 

 

#9번

#9번
class Node:
    def __init__(self, data):
        self.data=data
        self.link=None
        
class LinkedList:
    def __init__(self, data=None):
        self.head=None
        
    def insert(self, data):
        new_node=Node(data)
        if self.head==None:
            self.head=new_node
            return
        
        node=self.head
        while node.link is not None:
            node=node.link
        node.link=new_node
        
    def __str__(self):
        print_list=''
        node=self.head
        while True:
            if node.link==None:
                break
            print_list+=str(node.data)
            print_list+='-> '
            node=node.link
        print_list+=str(node.data)
        return print_list
        

number_list=LinkedList()

node_num=int(input("노드의 개수>>"))
for i in range(node_num):
    num=int(input('{0}번째 데이터>> '.format(i+1)))
    number_list.insert(num)
    
print(number_list)

---

 

#10번

#10번
class Node:
    def __init__(self, data):
        self.data=data
        self.link=None
        
class LinkedList:
    def __init__(self, data=None):
        self.head=None
        self.size=0
        
    def insert(self, data):
        new_node=Node(data)
        self.size+=1
        if self.head==None:
            self.head=new_node
            return
        
        node=self.head
        while node.link is not None:
            node=node.link
        node.link=new_node
        
    def __str__(self):
        print_list=''
        node=self.head
        while True:
            if node.link==None:
                break
            print_list+=str(node.data)
            print_list+='-> '
            node=node.link
        print_list+=str(node.data)
        return print_list
        

number_list=LinkedList()

node_num=int(input("노드의 개수>>"))
for i in range(node_num):
    num=int(input('{0}번째 데이터>> '.format(i+1)))
    number_list.insert(num)
    
print(number_list)
print('연결 리스트 노드의 개수>>{}'.format(number_list.size))

---

#11번

 

#11번
class Node:
    def __init__(self, data):
        self.data=data
        self.link=None
        
class LinkedList:
    def __init__(self, data=None):
        self.head=None
        self.sum=0
        
    def insert(self, data):
        new_node=Node(data)
        self.sum+=data
        if self.head==None:
            self.head=new_node
            return
        
        node=self.head
        while node.link is not None:
            node=node.link
        node.link=new_node
        
    def __str__(self):
        print_list=''
        node=self.head
        while True:
            if node.link==None:
                break
            print_list+=str(node.data)
            print_list+='-> '
            node=node.link
        print_list+=str(node.data)
        return print_list
        

number_list=LinkedList()

node_num=int(input("노드의 개수>>"))
for i in range(node_num):
    num=int(input('{0}번째 데이터>> '.format(i+1)))
    number_list.insert(num)
    
print(number_list)
print('연결 리스트 노드의 개수>>{}'.format(number_list.sum))

---

#12번

#12번
class Node:
    def __init__(self, data):
        self.data=data
        self.link=None
        
class LinkedList:
    def __init__(self, data=None):
        self.head=None
        
    def insert(self, data):
        new_node=Node(data)
        if self.head==None:
            self.head=new_node
            return
        
        node=self.head
        while node.link is not None:
            node=node.link
        node.link=new_node
        
    def search(self, data):
        num=0
        node=self.head
        while node is not None:
            if node.data==data:
                num+=1
            node=node.link
            
        return num
        
    def __str__(self):
        print_list=''
        node=self.head
        while True:
            if node.link==None:
                break
            print_list+=str(node.data)
            print_list+='-> '
            node=node.link
        print_list+=str(node.data)
        return print_list
        

number_list=LinkedList()

node_num=int(input("노드의 개수>>"))
for i in range(node_num):
    num=int(input('{0}번째 데이터>> '.format(i+1)))
    number_list.insert(num)
    
print(number_list)
data=int(input('탐색할 값을 입력하시오>>'))
print('{}는 연결 리스트에서 {}번 나타납니다.'.format(data, number_list.search(data)))

 

---

#13번

 

#13번

class Node:
    def __init__(self, data):
        self.data=data
        self.link=None
        
class LinkedList:
    def __init__(self, data=None):
        self.head=None
        
    def insert(self, data):
        new_node=Node(data)
        if self.head==None:
            self.head=new_node
            return
        
        node=self.head
        while node.link is not None:
            node=node.link
        node.link=new_node
        
    def search(self, data):
        num=0
        node=self.head
        while node is not None:
            if node.data==data:
                return node
        return False
            
    def delete(self, data):
        delete_node=self.search(data)
        if delete_node is False:
            return
        if delete_node is self.head:
            self.head=delete_node.link
        else:
            node=self.head
            while node.link is not delete_node:
                node=node.link
            node.link=delete_node.link
        
    def __str__(self):
        print_list=''
        node=self.head
        while True:
            if node.link==None:
                break
            print_list+=str(node.data)
            print_list+='-> '
            node=node.link
        print_list+=str(node.data)
        return print_list
        

number_list=LinkedList()

node_num=int(input("노드의 개수>>"))
for i in range(node_num):
    num=int(input('{0}번째 데이터>> '.format(i+1)))
    number_list.insert(num)
    
print(number_list)
data=int(input('삭제할 값을 입력하시오>>'))
number_list.delete(data)
print(number_list)

 

---

#14번

#14번

class Node:
    def __init__(self, name, age, height):
        self.name=name
        self.age=age
        self.height=height
        self.link=None
        
class LinkedList:
    def __init__(self):
        self.head=None
        
    def insert(self, name, age, height):
        new_node=Node(name, age, height)
        if self.head==None:
            self.head=new_node
            return
        
        node=self.head
        while node.link is not None:
            node=node.link
        node.link=new_node
        
    def __str__(self):
        print_list=''
        node=self.head
        while True:
            if node.link==None:
                break
            print_list+='Name: '+node.name+'\n'
            print_list+='Age: '+str(node.age)+'\n'
            print_list+='Heigth: '+str(node.height)+'\n'
            print_list+='\n'
            node=node.link
        return print_list
        
people=LinkedList()
people.insert('kim', 34, 1.7)
people.insert('park', 27, 1.2)
people.insert('lee', 48, 1.4)
people.insert('choi', 30, 1.3)
print(people)

---

#15번

#15번
class Node:
    def __init__(self, data):
        self.data=data
        self.link=None
        
class LinkedList:
    def __init__(self, data=None):
        self.head=None
        
    def insert(self, data):
        new_node=Node(data)
        if self.head==None:
            self.head=new_node
            return
        
        node=self.head
        while node.link is not None:
            node=node.link
        node.link=new_node
        
    def search(self):
        data=[]
        node=self.head
        while node is not None:
            data.append(node.data)
            node=node.link
        return max(data), min(data)
            
    def __str__(self):
        print_list=''
        node=self.head
        while True:
            if node.link==None:
                break
            print_list+=str(node.data)
            print_list+='-> '
            node=node.link
        print_list+=str(node.data)
        return print_list
        

number_list=LinkedList()

node_num=int(input("노드의 개수>>"))
for i in range(node_num):
    num=int(input('{0}번째 데이터>> '.format(i+1)))
    number_list.insert(num)
    
print(number_list)
max, min=number_list.search()
print('최대값>> ', max)
print('최소값>> ', min)

---

#16번

#16번
class Node:
    def __init__(self, data):
        self.data=data
        self.link=None
        
class LinkedList:
    def __init__(self, data=None):
        self.head=None
        self.size=0
        
    def insert(self, data):
        new_node=Node(data)
        self.size+=1
        if self.head==None:
            self.head=new_node
            return
        
        node=self.head
        while node.link is not None:
            node=node.link
        node.link=new_node
        
    def delete(self):
        node=self.head
        for num in range(self.size):
            if node == None:
                break
                
            if node is self.head:
                self.head=node.link
                node=self.head
            elif num%2!=0:
                prev.link=node.link
            
            prev=node
            node=node.link
            
    def __str__(self):
        print_list=''
        node=self.head
        while True:
            if node==None:
                break
            print_list+=str(node.data)
            print_list+='-> '
            node=node.link
        return print_list
        

number_list=LinkedList()

node_num=int(input("노드의 개수>>"))
for i in range(node_num):
    num=int(input('{0}번째 데이터>> '.format(i+1)))
    number_list.insert(num)
    
print(number_list)
number_list.delete()
print(number_list)

---

#17번

#17번

class Node:
    def __init__(self, data):
        self.data=data
        self.link=None
        
class LinkedList:
    def __init__(self, data=None):
        self.head=None
        self.size=0
        
    def insert(self, data):
        new_node=Node(data)
        self.size+=1
        if self.head==None:
            self.head=new_node
            return
        
        node=self.head
        while node.link is not None:
            node=node.link
        node.link=new_node

    def __str__(self):
        print_list=''
        node=self.head
        while True:
            if node==None:
                break
            print_list+=str(node.data)
            print_list+='-> '
            node=node.link
        return print_list
        
class alternate(LinkedList):
    def __init__(self, a, b):
        self.a=a
        self.b=b
        super().__init__()
        
    def working(self):
        node1=self.a.head; node2=self.b.head
        while True:
            if node1 is None:
                while node2 is not None:
                    self.insert(node2.data)
                    node2=node2.link
                return 
            elif node2 is None:
                while node1 is not None:
                    self.insert(node1.data)
                    node1=node1.link
                self.insert()
                return
            else:
                self.insert(node1.data)
                self.insert(node2.data)
            
            node1=node1.link; node2=node2.link;
        

A=LinkedList(); B=LinkedList()

node_num=int(input("A의 노드의 개수>>"))
for i in range(node_num):
    num=int(input('A의 {0}번째 데이터>> '.format(i+1)))
    A.insert(num)
    
node_num=int(input("B의 노드의 개수>>"))
for i in range(node_num):
    num=int(input('B의 {0}번째 데이터>> '.format(i+1)))
    B.insert(num)
    
C=alternate(A,B)
C.working()
print(C)

 

---

#18번

#18번 
class Node:
    def __init__(self, data):
        self.data=data
        self.link=None

class LinkedList:
    def __init__(self):
        self.head=None
            
    def dataCollect(self):
        dataList=[]; num=0
        while True:
            num=int(input('data(0 is quit)>>'))
            if num == 0:
                break
            dataList.append(num)
        self.insert(dataList) 
        
    def insert(self, data):
        dataList=sorted(data)
        
        for item in dataList:
            new_node=Node(item)
            if self.head==None:
                self.head=new_node
            else:
                node=self.head
                while node.link is not None:
                    node=node.link
                node.link=new_node
                
    def concat(self, l1, l2):
        n1=l1.head; n2=l2.head
        dataList=[]
        
        while n1!=None and n2!=None:
            dataList.append(n1.data)
            dataList.append(n2.data)
            
            if n1 is None:
                n2=n2.link
            elif n2 is None:
                n1=n1.link
            else:
                n1=n1.link; n2=n2.link
                
        self.insert(dataList)
        
    def __str__(self):
        printList=''
        node=self.head
        while node.link is not None:
            printList+=str(node.data)+'-> '
            node=node.link
        printList+=str(node.data)
        return printList

if __name__=='__main__':
    print('*******l1의 데이터 삽입을 시작합니다*******')
    l1=LinkedList(); l1.dataCollect(); print(l1); print()
    print('*******l2의 데이터 삽입을 시작합니다*******')
    l2=LinkedList(); l2.dataCollect(); print(l2); print()
    
    print('********l1과 l2의 합병을 시작합니다********')
    l3=LinkedList(); l3.concat(l1, l2)
    print(l3)

 

 

 

---

#19번

 

#19번 

class Node:
    def __init__(self, data):
        self.data=data
        self.link=None
        
class LinkedList:
    def __init__(self):
        self.head=None
    
    def insert(self, data):
        new_node=Node(data)
        
        if self.head==None:
            self.head=new_node; 
        else:
            node=self.head
            while node.link is not None:
                node=node.link
            node.link=new_node
            
    def __str__(self):
        print_list=''
        node=self.head
        while node is not None:
            print_list+=str(node.data)
            if node.link is not None:
                print_list+=' -> '
            node=node.link
        return print_list

class split(LinkedList):
    def __init__(self):
        self.even=LinkedList()  #짝수 노드
        self.odd=LinkedList()   #홀수 노드
    
    def split(self, L):
        node=L; node_num=1
        while node is not None:
            if node_num%2==0:
                self.even.insert(node.data)
                node=node.link; node_num+=1
            else:
                self.odd.insert(node.data)
                node=node.link; node_num+=1
        return self.even, self.odd
        
if __name__=='__main__':
    L=LinkedList()
    for i in range(5):
        L.insert(i)
    print(L)
    print('...리스트를 분리중입니다...\n')
    
    s=split()
    l1, l2=s.split(L.head)
    print('짝수 번째 리스트>> ', l1)
    print('홀수 번째 리스트>> ', l2)

 

---

#20번

 

#19번

class Node:
    def __init__(self, coef, expon):
        self.coef=coef
        self.expon=expon
        self.link=None
        
class poly:
    def __init__(self):
        self.head=None
    
    def insert(self, coef, expon=0):
        new_node=Node(coef, expon)
        
        if self.head==None:
            self.head=new_node; 
        else:
            node=self.head
            while node.link is not None:
                node=node.link
            node.link=new_node
            
    def __str__(self):
        print_list=''
        node=self.head
        while node is not None:
            print_list+=str(node.coef)+'x^'+str(node.expon)
            if node.link is not None:
                print_list+=' + '
            node=node.link
        return print_list
    
class poly_calcul(poly):
    def __init__(self, a, b):
        self.A=a
        self.B=b
        
    def calcul(self):
        node1=self.A.head; node2=self.B.head
        AB=poly()
        
        while node1 != None and node2 != None:
            if node1==None or node2==None:
                if node1==None:
                    while node2 is not None:
                        AB.insert(node2.coef, node2.expon)
                        node2=node2.link
                else:
                    while node1 is not None:
                        AB.insert(node1.coef, node1.expon)
                        node1=node1.link
            else:
                if node1.expon==node2.expon:
                    data=node1.coef+node2.coef
                    AB.insert(data, node1.expon)
                    node1=node1.link; node2=node2.link
                elif node1.expon>node2.expon:
                    AB.insert(node1.coef, node1.expon)
                    node1=node1.link
                elif node1.expon<node2.expon:
                    AB.insert(node2.coef, node2.expon)
                    node2=node2.link
                    
        print('A(x) + B(x) = ', AB)

    def __str__(self):
        super().__str__()
        
if __name__=='__main__':
    #3x^6+7x^3-2x^2-9
    A=poly()
    A.insert(3, 6); A.insert(7, 3); A.insert(-2, 2); A.insert(-9)
    print('A(x) = ', A)

    #-2x^6-4x^4+6x^2+6x+1
    B=poly()
    B.insert(-2,6); B.insert(-4,4); B.insert(6,2); B.insert(6, 1); B.insert(1)
    print('B(x) = ', B)
    
    print('----------------------------------------------------------')
    AB=poly_calcul(A, B)
    AB.calcul()

 

---

#21번

#21번
import math
class Node:
    def __init__(self, coef, expon):
        self.coef=coef
        self.expon=expon
        self.link=None
        
class poly:
    def __init__(self):
        self.head=None
    
    def insert(self, coef, expon=0):
        new_node=Node(coef, expon)
        
        if self.head==None:
            self.head=new_node; 
        else:
            node=self.head
            while node.link is not None:
                node=node.link
            node.link=new_node
            
    def poly_add(self, key):
        node=self.head
        data=0
        while node:
            if node.expon == 0:
                data+=node.coef
            else:
                data+=node.coef*math.pow(key,node.expon)
            node=node.link
        return data
            
    def __str__(self):
        print_list=''
        node=self.head
        while node:
            print_list+=str(node.coef)+'x^'+str(node.expon)
            if node.link is not None:
                print_list+=' + '
            node=node.link
        return print_list
        
if __name__=='__main__':
    #x^3+2x+6
    A=poly()
    A.insert(1, 3); A.insert(2, 1); A.insert(6)
    print('A(x) = ', A)
    
    print('----------------------------------------------------------')
    print('x가 2일 때>>', A.poly_add(2))

 

 

 

---

#23번

#23번
class Node:
    def __init__(self, data):
        self.data=data
        self.link=None
        
class SortedList:
    def __init__(self, data=None):
        node=Node(data)
        self.head=node
        
    def insert(self, data):
        new_node=Node(data)
        if self.head.data==None:
            self.head=new_node
            return 
        
        node=self.head
        if node.data>new_node.data:
            new_node.link=node
            self.head=new_node
            return 
            
        while node.link is not None:
            leading=node.link
            if node.data<=new_node.data and new_node.data<leading.data:
                node.link=new_node
                new_node.link=leading
                return
            node=leading
            leading=leading.link
            
        node.link=new_node 
        
    def __str__(self):
        print_list=''
        node=self.head
        while True:
            if node.link==None:
                break
            print_list+=str(node.data)
            print_list+='-> '
            node=node.link
        print_list+=str(node.data)
        return print_list
        

number_list=SortedList()

node_num=int(input("노드의 개수>>"))
for i in range(node_num):
    num=int(input('{0}번째 데이터>> '.format(i+1)))
    number_list.insert(num)
print(number_list)

 

---

#24번

#24번

class Node:
    def __init__(self, data):
        self.data=data
        self.link=None
        
class LinkedList:
    def __init__(self, data):
        new_node=Node(data)
        self.head=new_node
        
    def insert(self, data):
        new_node=Node(data)
        node=self.head
        while node.link is not None:
            node=node.link
        node.link=new_node
        
    def __str__(self):
        print_list=''
        node=self.head
        count=0
        while True:
            if node.link==None:
                break
            print_list+=str(node.data)
            print_list+=' '
            node=node.link
            count+=1
            if count==5:
                print_list+='\n'
                count=0
                
        return print_list            
        
matrix=LinkedList(0)

for i in range(5):
    for j in range(5):
        if (i+j)%7==0:
            matrix.insert(1)
        else:
            matrix.insert(0)
            
print(matrix)