[자료구조] 연결 리스트 4 (연결 스택과 큐, 다항식, 이중 연결 리스트)

연결 스택과 큐

연결 스택

• top에서 노드 삽입, 삭제 용이
• top: 스택의 톱 노드를 가리키는 전용 데이터 멤버
• 초기엔 top = 0

template <class T>
void LinkedStack<T>::Push(const T &e)
{
    top = new ChainNode<T>(e, top);
}

template <class T>
void LinkedStack<T>::Pop()
{ // 스택의 첫 번째 노드를 삭제
    if (IsEmpty())
        throw "Stack is empty. Cannot delete.";
    ChainNode<T> *delNode = top;
    top = top->link; // top노드를 삭제
    delete delNode;  // 메모리 할당 해제
}

 

연결 큐

• rear에서 노드 삽입 용이
• front에서 노드 삽입, 삭제 용이
• rear: 큐의 마지막 노드를 가리키는 전용 데이터 멤버
• front: 큐의 처음 노드를 가리키는 전용 데이터 멤버
• 초기 front와 rear는 0

template <class T>
void LinkedQueue<T>::Push(const T &e)
{
    if (IsEmpty())
        front = rear = new ChainNode(e, 0); // 큐가 비어있는 경우
    else
        rear = rear->link = new ChainNode(e, 0); // 노드를 생성해서 연결
}

template <class T>
void LinkedQueue<T>::Pop()
{ // 큐의 첫 번째 노드를 삭제
    if (IsEmpty())
        throw "Queue is empty. Cannot delete.";
    ChainNode<T> *delNode = front;
    front = front->link; // 체인의 첫 번째 노드 삭제
    delete delNode;      // 메모리 할당 해제
}

 

 

다항식

• \(a(x) = a_{m}x^{e_{m}} + ... + a_{1}x^{e_{1}}\)
• \(a_{i}\): 0이 아닌 계수
• \(e_{i}\): 음가 아닌 정수 지수
• \(e_{m} > e_{m-i} > ... > e_{2} > e_{1} ≥ 0\)
• 리스트를 사용해서 클래스 Polynomial(다항식) 구현
  • Polynomial은 List에 IS-IMPLEMENTED-BY 관계

 

 

Polynomial 클래스의 정의

struct Term
{             // Term의 모든 멤버는 묵시적으로 public
    int coef; // 계수
    int exp;  // 지수
    Term Set(int c, int e)
    {
        coef = c;
        exp = e;
        return *this;
    };
};

class Polynomial
{
public:
    // 정의된 공용 함수들
private:
    Chain<Term> poly;
};

 

다항식의 덧셈

Polynomial Polynomial::operator+(const Polynomial &b) const
{ // 두 다항식의 합 리턴
    Term temp;
    Chain<Term>::ChainIterator ai = poly.begin(),
                               bi = b.poly.begin();
    Polynomial c; // c는 a, b를 더한 다항식
    while (ai && bi)
    { // 한쪽 다항식의 항을 전부 더할 때까지 반복
        if (ai->exp == bi->exp)
        {                                  // ai, bi의 차수가 같다면
            int sum = ai->coef + bi->coef; // ai, bi의 계수를 더해줌
            if (sum)
                c.poly.InsertBack(temp.Set(sum, ai->exp));
            ai++;
            bi++; // 각각의 다항식의 다음 노드로 변경
        }
        else if (ai->exp < bi->exp)
        {
            c.poly.InsertBack(temp.Set(bi->coef, bi->exp));
            bi++; // next term of b
        }
        else
        {
            c.poly.InsertBack(temp.Set(ai->coef, ai->exp));
            ai++; // next term of a
        }         // 더 큰쪽 차수의 항을 c에 추가함
    }
    while (ai)
    { // a의 남은 부분을 복사
        c.poly.InsertBack(temp.Set(ai->coef, ai->exp));
        ai++;
    }
    while (bi)
    { // b의 남은 부분을 복사
        c.poly.InsertBack(temp.Set(bi->coef, bi->exp));
        bi++;
    }
    return c;
}

 

시간복잡도 - O(m +n)

 

다항식의 원형 리스트 표현

원형 리스트 표현

\(3x^{14}+2x^{8}+1\)

- 0인 다항식을 특수 경우로 처리해야 함

 

헤더 노드 사용

 

프로그램

void Equivalence()
{
    // 초기화
    while more pairs
    {
        input the next pair (i,j);
        process this pair;
    }
    initialize for output;
    for (each object not yet output)
        output the equivalence class that contains this object;
}

 

구현

class ENode
{
friend void Equivalence();
public:
    ENode(int d = 0) // 생성자
    {
        data = d;
        link = 0;
    }
private:
    int data;
    ENode *link;
};

void Equivalence()
{
    // 등가 쌍을 입력받고 등가 클래스를 출력
    ifstream inFile("equiv.in", ios::in); // "equiv.in"은 입력 파일
    if (!inFile)
        throw "Cannot open input file.";
    int i, j, n;
    inFile >> n; // 객체의 수를 입력받음

    // first 배열과 out 배열을 초기화함
    ENode **first = new ENode *[n]; // ENode 포인터 배열
    bool *out = new bool[n];        // 불리언 배열
    // fill 함수를 사용하여 초기화함
    fill(first, first + n, static_cast<ENode *>(0)); // first를 null로 초기화함
    fill(out, out + n, false);                       // out을 false로 초기화함

    // Phase 1: 등가 쌍을 입력함
    inFile >> i >> j;
    while (inFile.good())
    { // 파일의 끝까지 읽음
        // first[i]와 first[j]에 새로운 ENode를 삽입함
        first[i] = new ENode(j);
        first[j] = new ENode(i);
        // 다음 등가 쌍을 읽음
        inFile >> i >> j;
    }

    // Phase 2: 등가 클래스를 출력함
    for (i = 0; i < n; i++)
    {
        if (!out[i])
        { // 출력해야 함
            cout << endl
                 << "새로운 클래스: " << i;
            out[i] = true;
            ENode *x = first[i];
            ENode *top = 0; // 스택 초기화
            while (1)
            { // 클래스의 나머지를 찾음
                while (x)
                { // 리스트를 처리함
                    j = x->data;
                    if (!out[j])
                    { // 출력해야 함
                        cout << ", " << j;
                        out[j] = true;
                        ENode *y = x->link;
                        x->link = top;
                        top = x;
                        x = y;
                    }
                    else
                        x = x->link;
                } // while(x)의 끝
                if (!top)
                    break;
                x = first[top->data];
                top = top->link; // 스택에서 제거함
            }                    // while(1)의 끝
        }                        // if(!out[i])의 끝
    }                            // for(i = 0; i < n; i++)의 끝

    // 동적으로 할당된 메모리 해제함
    for (i = 0; i < n; i++)
    {
        while (first[i])
        {
            ENode *delnode = first[i];
            first[i] = delnode->link;
            delete delnode;
        }
    }
    delete[] first;
    delete[] out;
}

 

 

이중 연결 리스트

- 각 노드는 전방과 후방을 가리키는 두 개의 링크를 가짐

헤더 노드를 가진 공백 이중 연결 원형 리스트

헤더 노드가 있는 이중 연결 원형 리스트

 

이중 연결 리스트 클래스

class DblList;

class DblListNode
{
friend class DblList;
private:
    int data;
    DblListNode *left, *right;
};

class DblList
{
public:
    // 연산자 오버로딩 함수들
    //
    //
private:
    DblListNode *first; // header 노드 가리킴
};

 

이중 연결 원형 리스트로부터 삭제

x를 가리키는 링크 제거

void DblList::Delete(DblListNode *x)
{
    if (x == first)
        throw "Deletion of header node not permitted";
    else
    {
        x->left->right = x->right;
        x->right->left = x->left;
        delete x;
    }
}

 

이중 연결 원형 리스트에 삽입

노드 x의 오른편에 노드 p 삽입

void DblList::Insert(DblListNode *p, DblListNode *x)
{ // 노드 x의 오른편에 노드 p 삽입
    p->left = x;
    p->right = x->right;
    x->right->left = p;
    x->right = p;
}