티스토리 뷰


리스트를 C언어로 작성하였습니다.

이 리스트는 제일 앞의 노드(Front)와 제일 뒤의 노드(Back)에 포인터를 가지므로 스택 또는 큐로 사용할 수도 있습니다. 또한 리스트의 데이터들을 순서대로 소팅하는 함수도 구현되어 있습니다.




우선 소스코드들..


list.c : 리스트의 코드

list.h : 리스트의 헤더

main.c : 테스트 한 main 코드





< 리스트의 함수 설명 >


0. 구조체

typedef struct _listnode

{

    int data;

    struct _listnode *next;

} ListNode;


typedef struct _list

{

    ListNode *front, *back;

    int size

} List;

  • 구조체로 실제 노드로 구현된 ListNode와 노드의 시작과 끝을 가리키고 있는 List라는 구조체가 존재합니다.

 제가 만든 리스트를 도식화 한 그림입니다. 



1. 리스트 초기화 함수

List* createList ()

  • 함수명    : createList
  • 리턴타입 : List*
  • 파라미터 : void
  • 리턴값    : 메모리에 리스트 공간을 할당 받은 주소
  • 함수역할 : 리스트 초기화

* 리스트를 초기화 하지 않고 사용하면 무조건 에러가 발생합니다.


2. 리스트 소멸 함수

void destroyList (List* list)

  • 함수명    : destroyList
  • 리턴타입 : void
  • 파라미터 : 초기화 된 리스트
  • 리턴값    : 없음
  • 함수역할 : 리스트 내부의 모든 노드들을 제거하고 리스트를 소멸한다.


3. 리스트 Empty 체크 함수

bool isEmpty (List* list)

  • 함수명    : isEmpty
  • 리턴타입 : bool
  • 파라미터 : 초기화 된 리스트
  • 리턴값    : 리스트가 비어 있을 시 true, 아니면 false를 반환
  • 함수역할 : 리스트가 비었는지 아닌지를 체크
* c언어의 경우 bool 타입이 없기 때문에 typedef 을 이용하여 bool 타입을 강제로 만들었음.


4. 노드 추가 함수

void addFront (List* list, int node)

void addBack (List* list, int node)

  • 함수명    : addFront / addBack
  • 리턴타입 : void
  • 파라미터 : 초기화 된 리스트, 삽입할 노드
  • 리턴값    : 없음
  • 함수역할 : 노드를 각각 제일 앞, 또는 제일 뒤에 삽입한다.


5. 노드를 가져오는 함수

ListNode* getFront (List* list)

ListNode* getBack (List* list)

    • 함수명    : getFront / getBack
    • 리턴타입 : ListNode*
    • 파라미터 : 초기화 된 리스트
    • 리턴값    : 가져오려 하는 노드의 주소
    • 함수역할 : 각각 제일 앞, 또는 제일 뒤에 있는 노드를 가져온다.


6. 노드를 검색하는 함수

ListNode* searchList (List* list, int key)

  • 함수명    : searchList
  • 리턴타입 : ListNode*
  • 파라미터 : 초기화 된 리스트, 찾고자 하는 노드의 데이터 값
  • 리턴값    : 노드를 찾았을 경우 해당 노드의 주소, 찾지 못했을 경우 NULL을 반환
  • 함수역할 : key에 해당하는 데이터를 가진 노드를 찾아서 반환한다.


7. 노드를 제거하는 함수

void removeFront (List* list)

void removeBack (List* list)

  • 함수명    : removeFront / removeBack
  • 리턴타입 : void
  • 파라미터 : 초기화 된 리스트
  • 리턴값    : 없음
  • 함수역할 : 리스트에서 각각 제일 앞, 혹은 제일 뒤의 있는 노드를 제거한다.


8. 특정 노드를 제거하는 함수

void removeKey (List* list, int key)

  • 함수명    : removeKey
  • 리턴타입 : void
  • 파라미터 : 초기화 된 리스트, 제거할 노드의 데이터 값
  • 리턴값    : 없음
  • 함수역할 : Key에 해당하는 노드를 찾아 리스트에서 제거, 찾지 못했을 경우 오류 메시지 출력


9. 리스트를 정렬하는 함수 (sorting)

void listSort (List* list, int mode)

  • 함수명    : listSort
  • 리턴타입 : void
  • 파라미터 : 초기화 된 리스트, 오름차순(0)/내림차순(1)을 선택할 수 있는 모드 
  • 리턴값    : 없음
  • 함수역할 : 선택된 모드에 따라 리스트를 정렬함. bubble sort로 구현되어잇음
                   모드의 경우 0 : 오름차순 / 1 : 내림차순 으로 구현되어 있다. (Define 상수로 정의되어 있다.)



< 리스트 설명 >

 이 리스트는 Front와 Back 노드에 대해 포인터를 가지므로 스택 / 큐로 사용이 가능합니다. 

 - 스택으로 사용할 때, 스택은 FILO (First-In-Last-Out) 이므로
    addBack함수로 데이터를 입력 후 getBack + removeBack 함수를 이용해주면 됩니다.

 - 큐로 사용할 때, 큐는 FIFO (First-In-First-Out) 이므로
    addBack함수로 데이터를 입력 후 getFront + removeFront 함수를 이용해주면 됩니다.

 * 메인함수에 스택의 사용 예시가 있으니 참조하시길 바랍니다.



다음 포스팅은 (아마도) 바이너리 트리입니다.


신고

'C, C++ > 자료구조' 카테고리의 다른 글

C언어로 작성한 리스트  (0) 2013.12.28

댓글
댓글쓰기 폼