C# 4주차 2일 수업 내용 : 자료구조 (21.03.30)

단일 연결 리스트 연습

 

using System;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

namespace Study00
{
    public class App
    {
        //생성자 
        public App()
        {
            SingleLinkedList list = new SingleLinkedList();
            var head = new Node(1);
            list.Add(head);
            list.Add(new Node(2));
            var node3 = new Node(3);
            list.AddAfter(head, node3);
            list.Print();
            Console.WriteLine("------------------");
            list.Remove(node3);
            list.Print();
        }

    }
}

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

namespace Study00
{
    public class Node
    {
        public int data;
        public Node next;
        public Node(int data)
        {
            this.data = data;
        }
    }
    public class SingleLinkedList
    {
        private Node head;  //head부터 순차적 접근하기위함 
        //생성자 
        public SingleLinkedList()
        {
        }

        //노드 추가 
        public void Add(Node node)
        {
            if (this.head == null)
            {
                this.head = node;
            }
            else
            {
                //head부터 next가 null인것 찾기 
                //비교대상을 임시저장 
                Node current = this.head;
                while (current != null && current.next != null)
                {
                    //next가 있음 
                    current = current.next;
                }
                //새로운 노드 연결 
                current.next = node;
            }
        }

        //노드 수 세기 
        public int Count()
        {
            int count = 0;
            Node current = this.head;
            while (current != null)
            {
                count++;
                current = current.next;
            }
            return count;
        }

        public void Print()
        {
            if (this.head == null)
            {
                throw new InvalidOperationException();
            }
            Node current = head;
            while (current != null)
            {
                Console.WriteLine(current.data);
                current = current.next;
            }
        }

        //노드 추가 
        public void AddAfter(Node current, Node newNode)
        {

            if (this.head == null || current == null || newNode == null)
            {
                throw new InvalidOperationException();
            }

            newNode.next = current.next;
            current.next = newNode;
        }

        //노드 삭제 
        public void Remove(Node target)
        {
            if (this.head == null || target == null)
            {
                return;
            }

            //지우려고 하는 노드가 헤드라면 
            //헤드의 다음노드를 헤드로 
            if (this.head == target)
            {
                this.head = this.head.next;
                target = null;
            }
            else
            {
                Node current = this.head;
                //지우려고 하는 노드의 앞 노드 
                while (current != null && current.next != target)
                {
                    current = current.next;
                }
                current.next = target.next;
            }
        }
    }
}

 

QueueCircularArray (원형 배열로 만든 큐)

 

using System;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

namespace Study00
{
    public class App
    {
        //생성자 
        public App()
        {
            Console.WriteLine("App");
            QueueCircularArray queue = new QueueCircularArray(4);
            queue.Enqueue("홍길동");
            queue.Enqueue("임꺽정");
            queue.Enqueue("장길산");
            queue.Enqueue("장길산2");
            queue.Enqueue("장길산3");

            queue.Print();

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

        }

    }
}

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

namespace Study00
{
    class QueueCircularArray
    {
        //배열
        private string[] arr;
        //front
        private int front;
        //rear
        private int rear;

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

        public void Enqueue(string data)
        {

            //가득찬 상태를 확인
            if((this.rear + 1) % this.arr.Length == this.front)
            {
                Console.WriteLine("가득 참");
                Array.Resize<string>(ref arr, arr.Length + 1);
                
            }
            else
            {
                if (this.front == -1)
                {
                    this.front++;
                }
                
            }
            //다음 인덱스를 구함
            this.rear = (this.rear + 1) % this.arr.Length;
            Console.WriteLine("rear : {0}", this.rear);
            //넣는다
            this.arr[this.rear] = data;

        }

        public string Dequeue()
        {
            //큐가 비어있는지 체크
            if (front == -1 && rear == -1)
            {
                throw new ApplicationException("Empty");
            }
            else
            {
                //front인덱스를 요소로 가져옴
                string data = this.arr[this.front];

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

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

 

QueueLinkedList (연결 리스트로 만튼 큐)

 

using System;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

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

            queue.Print();
            Console.WriteLine();
            queue.Dequeue();
            queue.Print();

            Console.WriteLine();
            queue.Dequeue();
            queue.Print();
        }

    }
}

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

namespace Study00
{
    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 = null;
        //Tail
        private Node tail = null;
        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);
                this.tail = this.tail.next;
            }
        }

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

            //head에서 꺼냄
            string result = this.head.data;


            if (this.head == this.tail)
            {
                //초기화
                this.head = null;
                this.tail = null;
            }
            else
            {
                //head 설정
                this.head = this.head.next;
            }

            return result;
        }

        public void Print()
        {
            if(this.head == null)
            {
                throw new InvalidOperationException("Queue is Empty");
            }
            Node current = head;
            while(current != null)
            {
                Console.WriteLine(current.data);
                current = current.next;
            }
        }
    }
}

 

배열로 stack 만들기

 

using System;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

namespace Study00
{
    public class App
    {
        //생성자 
        public App()
        {
            Console.WriteLine("App");
            StackArray stack = new StackArray(2);
            stack.Push("홍길동");
            stack.Push("임꺽정");
            stack.Push("장길산");
            stack.Push("고길동");

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

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

        }

    }
}

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

namespace Study00
{

    public 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()
        {
            Console.WriteLine("배열의 크기가 증가했습니다.");
            Array.Resize<string>(ref this.arr, this.arr.Length * 2);
        }

        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];
        }

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

 

StackLinkedList

 

using System;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

namespace Study00
{
    public class App
    {
        //생성자 
        public App()
        {
            Console.WriteLine("App");
            StackLinkedList stack = new StackLinkedList();
            stack.Push("홍길동");
            stack.Push("장길산");
            stack.Push("임꺽정");
            stack.Push("고길동");

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

        }

    }
}

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

namespace Study00
{
    public class StackLinkedList
    {

        private Node top;
        private Node next;

        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;
        }
        public void Print()
        {
            if (this.top == null)
            {
                throw new ApplicationException("Stack is empty");
            }
            Node current = this.top;
            while(current != null)
            {
                Console.WriteLine(current.data);
                current = current.next;
            }
        }
    }
}

 

정적 TreeNode

 

using System;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

namespace Study00
{
    public class App
    {
        //생성자 
        public App()
        {
            var A = new TreeNode("A");
            var B = new TreeNode("B");
            var C = new TreeNode("C");
            var D = new TreeNode("D");

            A.links[0] = B;
            A.links[1] = C;
            A.links[2] = D;

            B.links[0] = new TreeNode("E");
            B.links[1] = new TreeNode("F");

            D.links[0] = new TreeNode("G");

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

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

namespace Study00
{
    public class TreeNode
    {
        public string data;
        public TreeNode[] links;
        //생성자 
        public TreeNode(string data, int max = 3)
        {
            this.data = data;
            this.links = new TreeNode[max];
        }
    }
}

 

동적 TreeNode

using System;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

namespace Study00
{
    public class App
    {
        //생성자 
        public 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.Write("{0} ", node.data);
            }
        }
    }
}

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

namespace Study00
{
    public class TreeNode
    {
        public string data;
        public List<TreeNode> links;
        //생성자 
        public TreeNode(string data, int max = 3)
        {
            this.data = data;
            this.links = new List<TreeNode>();
        }
    }
}

 

Left Right 탐색

 

using System;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

namespace Study00
{
    public class App
    {
        //생성자 
        public App()
        {
            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("{0} ", temp.data);
            while (temp.right != null)
            {
                temp = temp.right;
                Console.Write("{0} ", temp.data);
            }
        }
    }
}

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

namespace Study00
{
    public class LCRSNode
    {
        public string data;
        public LCRSNode left;   //child
        public LCRSNode right;  //sibiling 
        //생성자 
        public LCRSNode(string data)
        {
            this.data = data;
        }
    }
}

LCRSTree 구조

 

using System;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

namespace Study00
{
    public class App
    {
        //생성자 
        public App()
        {
            Console.WriteLine("App");

            LCRSTree tree = new LCRSTree("A");

            var A = tree.root;

            var B =tree.AddChild(A, "B");
            tree.AddChild(A, "C");

            var D = tree.AddSibiling(B, "D");

            tree.AddChild(B, "E");
            tree.AddChild(B, "F");
            tree.AddChild(D, "G");

            tree.PrintLevelOrder();

        }
    }
}

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

namespace Study00
{
    public 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;

            var node = new LCRSNode(data);

            //부모의 왼쪽 노드가 있는지 보고 없으면 넣고
            if(parent.left == null)
            {
                parent.left = node;
            }
            else
            {
                //있으면 그 노드의 오른쪽 있는지 검사
                var temp = parent.left;
                while(temp.right != null)
                {
                    temp = temp.right;
                }
                temp.right = node;
            }

            return node;
        }

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

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

            var sibiling = new LCRSNode(data);
            node.right = sibiling;
            return sibiling;
        }

        public void PrintLevelOrder()
        {
            //Queue에 Root 노드 추가
            var queue = new Queue<LCRSNode>();
            queue.Enqueue(this.root);

            //Queue에 요소가 있으면 계속
            while(queue.Count > 0)
            {
                //꺼내서
                var node = queue.Dequeue();

                //자식 있는거 확인해서 있으면 Queue에 등록
                if(node.left != null)
                {
                    queue.Enqueue(node.left);
                }
                Console.WriteLine();
                //출력 후 오른쪽 형제가 있는지 검사
                while(node != null)
                {
                    Console.Write("{0}", node.data);
                    node = node.right;
                }
            }
        }
    }
}

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

namespace Study00
{
    public class LCRSNode
    {
        public string data;
        public LCRSNode left;
        public LCRSNode right;
        public LCRSNode(string data)
        {
            this.data = data;
        }
    }
}