자료구조 21.03.30. 수업내용

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study801
{
    class SingleLinkedList
    {
        public Node head;
        public SingleLinkedList()
        {
        }

        public void Add(Node node)
        {
            if (this.head == null)
            {
                this.head = node;
            }
            else
            {
                Node current = this.head;

                while (current != null && current.next != null)
                {
                    current = current.next;
                }
                current.next = node;
            }
        }

        public void Remove(Node node)
        {
            if (this.head == null || node == null)
            {
                return;
            }
            else
            {
                Node current = this.head;
                if (current.next == node)
                {
                    current.next = node.next;
                    node = null;
                }
                else
                {
                    current = current.next;
                }
            }
        }

        public void AddAfter(Node node, Node position)
        {
            if (this.head == null || node == null)
            {
                return;
            }
            else
            {
                Node current = this.head;
                while (current != null && current.next != null)
                {
                    if (current == position)
                    {                        
                        break;
                    }
                    current = current.next;
                }
                node.next = current.next;
                current.next = node;

            }
        }

        public void Print()
        {
            if(this.head == null)
            {
                throw new InvalidOperationException();
            }

            Node current = this.head;
            while(current != null)
            {                
                Console.WriteLine("{0} : {1}", current, current.data);

                if (current.next == null)
                {
                    break;
                }
                current = current.next;
            }
        }


    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study801
{
    class Node
    {
        public int data;
        public Node next;

        public Node(int data)
        {
            this.data = data;
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Threading;
using System.Diagnostics;


namespace Study801
{
    class App
    {
        public App()
        {
            Console.WriteLine("App");
            SingleLinkedList list = new SingleLinkedList();

            Node node1 = new Node(1);
            Node node2 = new Node(2);
            Node node3 = new Node(3);
            Node node4 = new Node(4);
                
            list.Add(node1);
            list.Add(node2);
            list.Add(node3);
            Console.WriteLine(node1.data);

            list.AddAfter(node4, node2);

            list.Print();
        }
    }
}

============================================================================

 

Queue

 

고정 배열을 사용한 Queue구현

 

배열을 사용하여 Queue를 구현하는 가장 단순한 구현은 고정된 배열을 할당하고 Front와 Rear 인덱스를 관리하면서 큐를 구현하는 방식이다. 배열에 새 데이타를 추가할때는 Rear인덱스가 가리키는 배열요소에 데이타를 넣고, 데이타를 읽으며 제거할 때는 Front 인덱스가 있는 배열요소를 제거한다.

 

Queue를 구현하는 기본 과정

 

1. Queue의 초기 상태에서 Front와 Rear 인덱스는 -1로 설정한다.

2. Que에 데이타를 처음 추가할 대, A[0]에 넣고 Front와 Rear는 0이 된다.

3. Queue에 데이타를 추가(Enqueue)할 때, Queue가 가득 찬 상태인지 체크하고, 가득 차지 않았으면 다음 위치 즉(Rear + 1)% A.Length == Front 위치로 이동하여 데이터를 넣는다. 가득 찬 경우(a) 에러를 발생시키거나, (b)배열을 확장하여 데이터를 추가할 수 있게 한다. Queue가 가득 찬 상태인지 체크하는 방법은 Rear의 다음 인덱스가 Front와 같은지 체크하면 되는데, 식으로 (Rear + 1)%A.Length == Front 와 같이 표현할 수 있다.

4. Queue에서 데이타를 읽어 제거(Dequeue)할 대는, 먼저 Queue가 비어있는지 체크하고, 비어있지 않으면 데이타를 읽고 Front를 하나 증가시킨다. Front의 증가는 식으로 Front = (Front + 1) % A.Length 와 같이 표현할 수 있다. Queue에서 마지막 요소를 읽어 낼 때, 즉 Front와 Rear가 같을 때, 데이타를 읽어낸 후 Front와 Rear를 -1로 표현한다. 이는 초기 상태의 Front와 Rear가 -1이었던 것과 같은 상태인데, Queue가 비어 있다는 것을 의미하며, 여기서 -1은 Empty를 표현하는 특별한 값으로 볼 수 있다. 위와같은 구현에서 Queue가 비어 있는지 체크하는 방법은 Front가 Rear가 모두 -1인지 체크하면 된다.

============================================================================

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study801
{
    class QueueCircularArray
    {
        private int[] arr;
        private int front;
        private int rear;
        

        //생성자
        public QueueCircularArray(int capacity)
        {
            //배열 생성
            this.arr = new int[capacity];
            //초기화
            this.front = -1;
            this.rear = -1;
        }

        public void Enqueue(int data)
        {

            if ((this.rear + 1)% this.arr.Length == this.front)
            {
                Console.WriteLine("가득 참");
                throw new ApplicationException("Queue is full.");
            }
            else
            {
                if(this.front == -1)
                {
                    this.front++;
                }
            }

            //다음 인덱스를 구함
            this.rear = (this.rear + 1) % this.arr.Length;

            //넣는다            
            this.arr[this.rear] = data;
        }
        
        public int Dequeue()
        {
            //초기화 상태 (큐가 비어 있음)
            if (this.front == -1 && this.rear == -1)
            {
                throw new ApplicationException("Queue is empty.");
            }
            else
            {
                //front인덱스로 요소를 가져옴 
                int data = this.arr[this.front];

                //마지막요소 
                if (this.front == this.rear)
                {
                    //초기화 
                    this.front = -1;
                    this.rear = -1;
                }
                else
                {
                    //front인덱스 증가 (원형고려)
                    this.front = (this.front + 1) % this.arr.Length;
                }
                return data;
            }
        }

        public void Print()
        {
            for (int i = 0; i < this.arr.Length; i++)
            {
                Console.WriteLine("{0}", this.arr[i]);
            }
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Threading;
using System.Diagnostics;


namespace Study801
{
    class App
    {
        public App()
        {
            Console.WriteLine("App");
            
            QueueCircularArray queue = new QueueCircularArray(4);
            
            queue.Enqueue(1);
            queue.Enqueue(2);
            queue.Enqueue(3);

            Console.WriteLine("result: {0}", queue.Dequeue());
            Console.WriteLine("result: {0}", queue.Dequeue());
            Console.WriteLine("result: {0}", queue.Dequeue());

            queue.Print();
        }
    }
}

============================================================================

연결리스트로 구현한 Queue

 

연결 리스트를 이용하여 Queue를 구현하는 로직은 비교적 간단하다. Queue에 새 데이타를 추가(Enqueue)하기 위해서는 연결 리스트의 마지막에 새 노드를 추가하면 되고, 데이타를 꺼내오기(Dequeue) 위해서는 연결 리스트의 첫 노드를 읽어오면 된다.

 

using System;

namespace ConsoleApp9
{
    public class App
    {
        public App() {
            Console.WriteLine("App");
            QueueLinkedList queue = new QueueLinkedList();
            queue.Enqueue("홍길동");
            queue.Enqueue("임꺽정");
            queue.Enqueue("장길산");

            var result = queue.Dequeue();
            Console.WriteLine(result);
        }
    }
}

using System;

namespace ConsoleApp9
{
    public class Node {
        //Data
        public string data;
        //Node
        public Node next;

        //생성자 
        public Node(string data) {
            this.data = data;
        }
    }
    public class QueueLinkedList
    {
        //Head
        private Node head;
        //Tail 
        private Node tail;
        //생성자 
        public QueueLinkedList() { 

        }

        public void Enqueue(string data) {
            //큐가 비어 있을 경우 
            if (this.head == null)
            {
                this.head = new Node(data);
                this.tail = this.head;
            }
            else 
            {
                //비어 있지 않을 경우에 
                this.tail.next = new Node(data);
                //tail설정 
                this.tail = this.tail.next;
            }
        }

        public string Dequeue() {
            //head에서 꺼냄 
            string result = this.head.data;

            //Queue가 비어 있음 
            if (this.head == null) {
                throw new ApplicationException("Queue is empty.");
            }

            //하나만 남은 경우 
            if (this.head == this.tail)
            {
                //초기화 
                this.head = null;
                this.tail = null;
            }
            else 
            {
                //head설정 
                this.head = this.head.next;
            }
            
            return result;
        }
    }
}

============================================================================

Stack

 

스택 자료구조

스택은 가장 최근에 넣은 데이터를 먼저 꺼내서 사용하는 선형적인 자료구조(Linear Data Structure)이다. 스택은 흔히 LIFO(Last In First Out)라고 불리우는 자료구조로서 나중에 저장된 것을 먼저 꺼내지는 구조를 가지고 있다.

 

배열로 구현한 Stack

 

배열을 사용하여 Stack을 구현하는 가장 단순한 구현은 고정된 배열을 할당하고 스택의 top 인덱스를 사용하여 데이타를 넣고 가져오는 것을 구현하는 방법이다. 스택에서 새 데이타 요소를 추가하는 것을 Push라 하고, 가장 마지막에 추가된 요소를 제거하며 가져오는 것을 Pop이라 한다. 이 Push와 Pop 동작은 스택의 가장 기본적인 행위(메서드)에 해당된다. 구현 방식에 따라 약간 다를 수 있지만 통상 Push()메서드 에서는 top 인덱스를 하나

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study801
{
    class StackArray
    {
        //배열
        private string[] arr;
        //top(인덱스)
        private int top;

        public bool IsEmpty
        {
            get
            {
               return this.top == -1;
            }
        }

        public int Capacity
        {
            get
            {
                return this.arr.Length;
            }
        }
        

        //생성자
        public StackArray(int capacity)
        {
            //배열생성
            this.arr = new string[capacity];
            
            //초기화
            this.top = -1;
        }

        public void Push(string data)
        {
            if (this.top == this.arr.Length - 1)
            {
                //에러, 확장
                this.ReSizeStack();
            }

            //top을 증가 시키고 데이터 넣기
            this.arr[++this.top] = data;
        }

        public void ReSizeStack()
        {
            //크기가 2배인 임시 배열 생성
            int capacity = 2 * (arr.Length - 1);
            var tempArray = new string[capacity];

            //배열 복사
            Array.Copy(this.arr, tempArray, this.arr.Length);
            
            //내 배열에 적용
            this.arr = tempArray;
        }

        public string Pop()
        {
            if (this.IsEmpty)
            {
                throw new ApplicationException("Stack is Empty.");
            }

            return this.arr[this.top--];
        }

        public string Peek()
        {
            if (this.IsEmpty)
            {
                throw new ApplicationException("Stack is Empty.");
            }
            return this.arr[this.top];
        }

        
    }
}

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study801
{
    class App
    {
        public App()
        {
            Console.WriteLine("App");

            StackArray stack = new StackArray(16);
            stack.Push("옥동자");
            stack.Push("메가톤");
            stack.Push("까마쿤");
            stack.Push("빠삐코");

            string result = stack.Peek();
            Console.WriteLine(result);

            result = stack.Pop();
            Console.WriteLine("pop : {0}",result);

            result = stack.Peek();
            Console.WriteLine("peek : {0}", result);

            result = stack.Peek();
            Console.WriteLine("peek : {0}", result);
        }
    }
}

============================================================================

연결리스트로 구현한 Stack

 

1. top 포인터에 새 노드를 추가

2. 새 노드의 next포인터가 이전 노드를 가리키게 해야함.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study801
{
    public class Node
    {
        public string data;
        public Node next;
        public Node(string data)
        {
            this.data = data;
        }
    }
    class StackLinkedList
    {
        public Node top;

        //생성자
        public StackLinkedList()
        {

        }

        public void Push(string data)
        {
            if(this.top == null)
            {
                this.top = new Node(data);
            }
            else	//이 부분이 직관적으로 이해되지 않는다.
            {
                var node = new Node(data);                
                node.next = this.top;
                this.top = node;
            }
        }

        public string Pop()
        {
            if(this.top == null)
            {
                throw new ApplicationException("Stack is empty");

            }
            var result = this.top.data;
            this.top = this.top.next;
            return result;
        }

        public string Peek()
        {
            if(this.top == null)
            {
                throw new ApplicationException("Stack is empty");
            }
            return this.top.data;
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study801
{
    class App
    {        
        public App()
        {
            Console.WriteLine("App");

            StackLinkedList stack = new StackLinkedList();
            stack.Push("장발장");
            stack.Push("홍길동");
            stack.Push("임꺽정");
            stack.Push("니체");
            stack.Push("장영실");

            var result = stack.Pop();
            Console.WriteLine(result);
        }
    }
}

============================================================================

트리(Tree)

 

tree자료구조

 

Tree혹은 Graph는 데이터가 선행적으로 나열되어 있지 않고 여러 노드들이 가지처럼 연결되어 있는 비선형적 자료구조이다. 

공간 낭비를 어느정도 해결하기 위해서 동적배열을 사용할 수 있다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study801
{
    class TreeNode
    {
        public string data;
        public List<TreeNode> links;

        //생성자
        public TreeNode(string data)
        {
            this.data = data;
            this.links = new List<TreeNode>();
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study801
{
    class LCRSNode
    {
        public string data { get; set; }
        public LCRSNode left { get; set; }
        public LCRSNode right { get; set; }

        public LCRSNode(string data)
        {
            this.data = data;
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study801
{
    class App
    {        
        public App()
        {
            Console.WriteLine("App");

            /* var A = new TreeNode("A");
             var B = new TreeNode("B");
             var C = new TreeNode("C");
             var D = new TreeNode("D");

             A.links.Add(B);
             A.links.Add(C);
             A.links.Add(D);

             B.links.Add(new TreeNode("E"));
             B.links.Add(new TreeNode("f"));

             D.links.Add(new TreeNode("G"));

             //A의 자식 노드들을 출력
             foreach(var node in A.links)
             {
                 Console.WriteLine("{0}", node.data);
             }*/

            var A = new LCRSNode("A");
            var B = new LCRSNode("B");
            var C = new LCRSNode("C");
            var D = new LCRSNode("D");
            var E = new LCRSNode("E");
            var F = new LCRSNode("F");
            var G = new LCRSNode("G");

            A.left = B;
            B.right = C;
            C.right = D;

            B.left = E;
            E.right = F;

            D.left = G;

            //A의 자식들 출력
            var temp = A.left;
            Console.Write("A's child's siblings : {0}", temp.data);
            while(temp.right != null)
            {
                temp = temp.right;
                Console.Write(",{0}", temp.data);                
            }
            Console.WriteLine();
        }
    }
}

 

============================================================================

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study801
{
    class LCRSNode
    {
        public LCRSNode left;
        public LCRSNode right;
        public string data;

        public LCRSNode(string data)
        {
            this.data = data;
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study801
{
    class LCRSTree
    {
        public LCRSNode root;

        public LCRSTree(string data)
        {
            root = new LCRSNode(data);
        }

        public LCRSNode AddChild(LCRSNode parent, string data)
        {
            if (parent == null)
                return null;

            LCRSNode child = new LCRSNode(data);

            if(parent.left == null)
            {
                parent.left = child;
            }
            else
            {
                LCRSNode temp = parent.left;

                while(temp.right != null)
                {
                    temp = temp.right;
                }
                temp.right = child;
            }
            return child;
        }

        public LCRSNode AddSibling(LCRSNode node, string data)
        {
            if (node == null)
                return null;

            LCRSNode sibling = new LCRSNode(data);

            while(node.right != null)
            {
                node = node.right;
            }
            node.right = sibling;

            return sibling;
        }

    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study801
{
    class App
    {        
        public App()
        {
            Console.WriteLine("App");

            LCRSTree tree = new LCRSTree("가");

            tree.root = new LCRSNode("가");

            tree.AddChild(tree.root, "나");










            
              
            /*List<LCRSNode> list = new List<LCRSNode>();

            list.Add(new LCRSNode("가"));
            list.Add(new LCRSNode("나"));
            list.Add(new LCRSNode("다"));
            list.Add(new LCRSNode("라"));
            list.Add(new LCRSNode("마"));
            list.Add(new LCRSNode("바"));
            list.Add(new LCRSNode("사"));

            list[0].left = list[1];

            list[1].left = list[4];
            list[1].right = list[2];
            list[2].right = list[3];

            list[4].right = list[5];

            list[3].left = list[6]; */


        }
    }
}

============================================================================

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study801
{
    class LCRSNode
    {
        public LCRSNode left;
        public LCRSNode right;
        public string data;

        public LCRSNode(string data)
        {
            this.data = data;
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study801
{
    class LCRSTree
    {
        public LCRSNode root;

        public LCRSTree(string data)
        {
            root = new LCRSNode(data);
        }

        public LCRSNode AddChild(LCRSNode parent, string data)
        {
            if (parent == null)
                return null;

            LCRSNode node = new LCRSNode(data);

            if(parent.left == null)
            {
                parent.left = node;
            }
            else
            {
                LCRSNode temp = parent.left;
                while (temp.right != null)
                {
                    temp = temp.right;
                }
                temp.right = node;
            }
            return node;            
        }

        public LCRSNode AddSibling(LCRSNode sibling, string data)
        {
            if (sibling == null)
                return null;

            LCRSNode node = new LCRSNode(data);               
            while(sibling.right != null)
            {
                sibling = sibling.right;
            }
            sibling.right = node;
            return node;
        }


        public void PrintLevelOrder()
        {
            var queue = new Queue<LCRSNode>();
            queue.Enqueue(this.root);

            while (queue.Count > 0)
            {                
                LCRSNode node = queue.Dequeue();

                if(node.left != null)
                {
                    queue.Enqueue(node.left);
                }

                while(node != null)
                {
                    Console.WriteLine("{0}", node.data);
                    node = node.right;
                }   
            }
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study801
{
    class App
    {        
        public App()
        {
            Console.WriteLine("App");

            LCRSNode rootNode = new LCRSNode("뿌리");
            LCRSTree tree = new LCRSTree("LCRS나무");
            tree.root = rootNode;

            LCRSNode node1 = tree.AddChild(tree.root, "2세대 첫째");
            LCRSNode node1_2 = tree.AddSibling(node1, "2세대 둘째");
            LCRSNode node1_3 = tree.AddSibling(node1, "2세대 셋째");
            LCRSNode node2 = tree.AddChild(tree.root, "3세대 첫째");
            LCRSNode node2_2 = tree.AddSibling(node2, "3세대 둘째");
            LCRSNode node3 = tree.AddChild(tree.root, "4세대 첫째");
            LCRSNode node3_2 = tree.AddSibling(node3, "4세대 둘째");
            LCRSNode node3_3 = tree.AddSibling(node3, "4세대 셋째");
            LCRSNode node4 = tree.AddChild(tree.root, "5세대 첫째");

            tree.PrintLevelOrder();
        }
    }
}

세대끼리 나뉘어 출력되게 하고싶은데 잘 안된다...