포인터와 연결리스트

포인터란 알기 쉽게 선언한 변수의 주소를 할당한 메모리이다.

int x = 10;
int* p;
p = &i;

위의 식에서 x의 주소값을 p에 저장하고 p를 포인터변수라고 한다.

표현	자료형	동일한 표현
'a'	char
ch	char	*p, **p
p	char*	&ch, *pp
pp	char**	&p

앞서배운 배열도 사실 포인터의 개념이 들어간다. 배열에서 int A[5];라는 배열을 선언했을 때 A의 이름을 가진 주소값은 A[0]에 대치된다. 그리고 동일하게 사칙연산이 적용된다.

#include <iostream.h>
using namespace std;

int main(){
	int arr[2][3] = {{11,12,13},{21,22,23}};
    int* arrM[2] = {arr[0], arr[1]};
    int** pp = arrM;
    cout << pp[1][2] << endl;
}

//결과값 : 23

* 포인터는 NULL로 초기화하는 것이 좋으며, 초기화가 안된 포인터변수는 접근시 위험하다.

---

정적메모리 할당 vs 동적메모리 할당

• 정적메모리의 크기는 프로그램이 시작하기 전 결정
• 실행 도중에 크기 변경 불가능
• 더 큰 입력들어오면 처리 불가능, 더 작은 입력시에는 메모리 낭비
• ex) int i; int* p; int A[10];

• 동적메모리의 크기는 실행도중에 할당
• 필요한 만큼만 할당받고 반납가능
• 메모리가 효율적이나 사용안하면 반납해야함
• ex) char *pc = new char[100] , delete pc;
• 2차원배열을 할당하고 싶으면 이중포인터를 사용해야한다.

// 여기서 mat : int**형 , mat[i] : int*형, mat[i][j] : int형


int** alloc2DInt(int rows, int cols)
{
	if(rows <= 0 || clos <= 0 ){
    	return NULL; }
    int** mat = new int* [rows];
    for(int i = 0; i<rows; i++){
    	mat[i] = new int [cols]; }
    return mat;
}

void free2DInt(int** mat, int rows, int cols=0)
{
	if( mat != NULL){
    	for(int i=0; i<rows; i++){
        	delete [] mat[i];}
        delete [] mat;
    }
}

---

연결 리스트(Linked Representation)

• 노드라 하는 <항목, 주소> 쌍을 가진다.
• 데이터필드(항목), 링크필드(주소)를 기반으로 값과 포인터로 구성되어있다.
• 데이터의 삽입과 삭제가 보다 용이하다
• 연속된 메모리 공간이 필요없고, 처음 크기를 제한할 필요가 없다
• But 구현이 어렵고 오류발생이 많다.

// Student.h
#include <cstring>
#include <cstdio>

class Student{
	int id;
    char name[MAX_STRING];
    char dept[MAX_STRING];
public:
	Student(int i =0, char* n="", char* d="") { set(i, n, d); }
    void set(int i, char* n, char* d) {
    	id = i;
        strcpy(name, n);
        strcpy(dept, d);
    }
    void display() {
    	printf("학번 : %-15d 성명: %-10s 학과: %-20s\n", id, name, dept);
    }
};

//Node.h
#include "Student.h"

class Node : public Student {
	Node* link;
public:
	Node(int id=0, char* name="", char* dept="")
    	: Student(id, name, dept) { link = NULL; }
    ~Node(void) { }
    Node* getLink() { return link; }
    void setLink(Node* p) { link = p; }
};

// LinkedStack.h

#include "Node.h"

class LinkedStack {
	Node* top;
public:
	LinkedStack() { top = NULL; }
    ~LinkedStack() { while(!isEmpty()) delete pop(); }
    bool isEmpty() { return top == NULL; }
    
    void push( Node* p) {
    	if(isEmpty()) { top = p;}
        else {
        	p->setLink(top);
            top = p;
        }
   }
   Node* pop() {
   		if(isEmpty()) { return NULL; }
        else {
        	Node* p = top;
            top = top->getLink();
            return p;
        }
   }
   int size() {
   		Node* p;
        int count = 0;
        for(Node* p = top; p != NULL; p = p->link){
        	count++;}
        return count;
   }
   Node* peek() { return top; }
   void display() {
   		printf("[LinkedStack]\n");
        for(Node* p = top; p != NULL; p=p->getLink()){
        	p->display();
            printf("\n");
        }
   }
};

// LinkedStack.cpp
#include "LinkedStack.h"
#inlcude <cstdio>

int main()
{
	LinkedStack stack;
    stack.push(new Node(20221218, "글쓰기", "국어국문학과"));
    stack.push(new Node(20221217, "수학쌤", "수학과"));
    stack.push(new Node(20221216, "영어쌤", "영문학과"));
    stack.display();
    
    Node *node = stack.pop();
    printf("[pop항목]\n");
    node->display();
    printf("\n");
    delete node;
    stack.display();
    return 0;
}

---

연결리스트로 구현한 큐

// Node.h
#include <cstdio>

class Node{
	Node* link;
    int data;
public:
	Node(int val =0) : data(val), link(NULL) {}
    Node* getLink() { return link; }
    void setLink(Node* next) { link = next; }
    void display() { printf(" <%2d>", data); }
};

// LinkedQueue.h

#include "Node.h"

class LinkedQueue {
	Node* front;
    Node* rear;
public:
	LinkedQueue() : front(NULL), rear(NULL) { }
    ~LinkedQueue() { while(!isEmpty()) delete dequeue(); }
    bool isEmpty() { return front == NULL; }
    
    void enqueue(Node* p) {
    	if(isEmpty()) { front = rear = p; }
        else{
        	rear->setLink(p);
            rear = p;
        }
    }
    
    Node* dequeue() {
    	if(isEmpty()) { return NULL; }
        else{
        	Node* p = front;
            front = front->getLink();
            if(front == NULL) { rear = NULL; }
            return p;
        }
    }
    Node* peek() { return front; }
};

// LinkedQueue.cpp
#include "LinkedQueue.h"

int main()
{
	LinkedQueue que;
    for(int i=1; i<10; i++){
    	que.enqueue(new Node(i));}
    que.display();
    delete que.dequeue();
    delete que.dequeue();
    delete que.dequeue();
    que.display();
}

// [큐 내용] : < 1>< 2>< 3>< 4>< 5>< 6>< 7>< 8>< 9>
// [큐 내용] : < 4>< 5>< 6>< 7>< 8>< 9>