3. 리스트

자료구조에서의 추상 자료형(ADT)

• 구체적인 기능의 완성과정을 언급하지 않고 순수하게 기능이 무엇인지를 나열한 것
• c언어의 경우 단순히 구조체만을 정의했다고 자료형이 완성되는것이 아니라 연산(기능)도 추가되어야 완성되는것
• 사용자가 구조체의 정의를 알 필요는 없기때문에 구조체의 정의를 추상 자료형에 추가할 필요가 없다.
• ex) FILE구조체 내부 모습을 몰라도 파일과 관련된 연산을 모두 처리할 수 있다.
• 결국 구조체의 추상 자료형에는 연산(기능, 메서드)만 추가되어 있다.
• 어떠한 자료구조이건 자료구조의 구현과 구현된 자료구조의 활용은 완전히 구분되어야 한다.

  Wallet의 ADT

  1. int TakeoutMoney(Wallet* pw, int coinNum, int billNum)

     • 전달된 주소의 지갑에서 돈을 꺼냄
     • 두번째 인자로 꺼낼 동전의 수, 세번째 인자로 꺼낼 지폐의 수를 전달
     • 꺼내고자 하는 돈의 총액이 반환
       
       

  2. void PutMoney(Wallet* pw, int coinNum, int billNum)

     • 전달된 주소의 지갑에 돈을 넣음
     • 두번째 인자로 넣을 동전의 수, 세번째 인자로 넣을 지폐의 수 전달
     • 넣은만큼 개수 증가

리스트

• 리스트와 연결 리스트는 같은것인가?
  x
  리스트는 순차리스트(배열기반), 연결 리스트(메모리 동적할당) 으로 나뉘기 때문에

• 리스트 자료구조는 데이터를 나란히 저장하며, 중복된 데이터의 저장을 막지 않는다
  
  

리스트의 ADT

• 접근방식 : 데이터를 나란히 저장할지를 고민하는것이 아닌 나란히 저장되어있다는 특성을 이용해 제공해야할 기능을 정의해야 함

1. void ListInit(List* plist)
   • 초기화 할 리스트의 주소값을 인자로 전달
   • 리스트 생성 후 가장 먼저 호출되어야 함
     
     
2. void LInsert(List* plist, LData data)
   • 리스트에 데이터 저장
     
     
3. int LFirst(List* plist, LData* pdata)
   • 첫번째 데이터가 pdata가 가리키는 메모리에 저장
     
     
4. int LNext(List* plist, Ldata* pdata)
   • 참조된 데이터의 다음 데이터가 pdata가 가리키는 위치에 저장됨
     
     
5. LData LRemove(List* plist)
   • LFirst or LNext 함수의 마지막 반환 데이터 삭제
     
     
6. int LCount(List* plist)
   • 리스트에 저장되어있는 데이터의 수를 반환

ArrayList.h
#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__

#define TRUE 1
#define FALSE 0

#define LIST_LEN 100

typedef struct __ArrayList{ //배열기반 리스트를 정의한 구조체
	LData arr[LIST_LEN];
    int numOfData;
    int curPosition;
} ArraList;

typedef ArrayList List;

void ListInit(List* plist);
void LInsert(List* plist, LData data);
void LFirst(List* plist, LData* pdata);
void LNext(List* plist, LData* pdata);
LData LRemove(List* plist);
int LCount(List* plist);

#endif

struct 구조체 이름 : 구조체 생성
typedef : 구조체 별칭 지정

실제 리스트가 어떻게 구현되어있는지는 알 필요 없고 기능만 숙지하면 됨

배열의 장,단점

• 장점
  • 배열의 길이가 초기에 결정되어야 하므로 변경이 불가능
  • 삭제 과정에서 데이터 이동이 빈번하게 발생함
• 장점
  • 인덱스 값을 사용해 데이터 참조가 쉬움