데이터 구조 (1) - 선형 구조

1. 순차 저장

//List.h

#ifndef LIST_H_

#define LIST_H_



#define MAXSIZE 100

typedef struct _Poly

{

    int a;

    int n;

    bool operator == (_Poly e)

    {

        if (a == e.a && n == e.n)

            return true;

        else

            return false;

    }

}Poly;



#define ElemType Poly



typedef struct _Node

{

    ElemType data[MAXSIZE];

    int last;

}Node;



class List

{

private:

    Node *data;

public:

    List();

    ~List();

    void Insert(ElemType e, int index);

    void Remove(int index);

    int Find(ElemType e);

    ElemType FindKth(int k);

    int Length();

};

#endif



//List.cpp

#include "List.h"

#include <iostream>



List::List()

{

    data = new Node();

    data->last = -1;

}



List::~List()

{

    delete data;

}



void List::Insert(ElemType e, int index)

{

    if (data->last == MAXSIZE - 1)

    {

        std::cout << "   " << std::endl;

        return;

    }

    if (index < 0 || index >(data->last + 1))

    {

        std::cout << "       " << std::endl;

        return;

    }

    for (int i = data->last; i >= index; i--)

    {

        data->data[i + 1] = data->data[i];

    }

    data->data[index] = e;

    data->last++;

}





void  List::Remove(int index)

{

    if (index < 0 || index > data->last)

    {

        std::cout << "       " << std::endl;

        return;

    }



    for (int i = index; i < data->last; i++)

    {

        data->data[i] = data->data[i + 1];

    }

    data->last--;

}



int  List::Find(ElemType e)

{

    for (int i = 0; i < data->last; i++)

    {

        if (data->data[i] == e)

            return i;

    }

    return -1;

}

ElemType  List::FindKth(int k)

{

    if (k < 0 || k > data->last)

    {

        std::cout << "       " << std::endl;

    }

    return data->data[k];

}

int  List::Length()

{

    return (data->last + 1);

}

 
2. 체인 메모리

//PList.h

#ifndef PLIST_H_

#define PLIST_H_



#define MAXSIZE 100

typedef struct _Poly

{

    int a;

    int n;

    bool operator == (_Poly e)

    {

        if (a == e.a && n == e.n)

            return true;

        else

            return false;

    }

}Poly;



#define ElemType Poly



typedef struct _PNode

{

    ElemType data;

    _PNode* next;

}PNode;



class PList

{

private:

    PNode *head;

public:

    PList();

    ~PList();

    void Insert(ElemType e, int index);

    void Remove(int index);

    int Find(ElemType e);

    ElemType FindKth(int k);

    int Length();

};

#endif



//PList.cpp

#include "PList.h"

#include <iostream>



PList::PList()

{

    head = new PNode();

    head->next = NULL;

}



PList::~PList()

{

    delete head;

}



void PList::Insert(ElemType e, int index)

{

    PNode *p = head;

    PNode *s = new PNode();

    s->data = e;

    s->next = NULL;

    if (index > Length())

        std::cout << "      " << std::endl;



    int i = 0;

    while (p && i < index)

    {

        p = p->next;

        i++;

    }

    s->next = p->next;

    p->next = s;

}





void  PList::Remove(int index)

{

    PNode *p = head;

    PNode *s = new PNode();

    if (index > Length())

        std::cout << "      " << std::endl;



    int i = 0;

    while (p && i < index)

    {

        p = p->next;

        i++;

    }

    s = p->next;

    p->next = s->next;

    delete s;

}



int  PList::Find(ElemType e)

{

    PNode *p = head;

    int i = 0;

    while (p)

    {

        if (p->data == e)

            return i;

        i++;

        p = p->next;

    }

    return -1;

}

ElemType  PList::FindKth(int k)

{

    PNode *p = head;

    if (k < 0 || k > Length())

    {

        std::cout << "       " << std::endl;

    }

    int i = 0;

    while (p && i < k)

    {

        p = p->next;

        i++;

    }

    return p->next->data;

}

int  PList::Length()

{

    PNode *p = head;

    int i = 0;

    while (p)

    {

        i++;

        p = p->next;

    }

    return i;

    

}

3. 테스트 사례

//main.cpp

#include <iostream>

#include <stdlib.h>

#include "PList.h"

using namespace std;





int main()

{

    PList L;

    for (int i = 0; i < 5; i++)

    {

        Poly t = { i, i };

        L.Insert(t, i);

    };

    cout << "last:" << L.Length() << endl;

    Poly e = { 2, 2 };

    cout << "Find return:" << L.Find(e) << endl;

    for (int i = 0; i < 4; i++)

    {

        cout << L.FindKth(i).a << "X" << L.FindKth(i).n  << " + ";

    }

    cout << L.FindKth(4).a << "X" << L.FindKth(4).n << endl;

    system("pause");

    return 0;

}