리스트 - 1

리스트

• 목록이나 도표처럼 여러 데이터를 관리할 수 있는 자료형을 추상화
• 데이터 삽입, 삭제, 검색 등 필요한 작업을 가함
• 스택과 큐는 리스트의 특수한 경우에 해당

추상 자료형 리스트 - 목록

 

Position	Name	Quantity
1	Beer	10
2	Gum	5
3	Apple	4
4	Potato	8
5	Onion	8
...	...	...

 

추상 자료형 리스트의 작업

Insert(Position, Data)

= 데이터를 해당 위치(Position)에 넣기

Delete(Position)

= 해당 위치(Position)의 데이터를 삭제

Retrieve(Position, Data)

= 해당 위치(Position)의 데이터를 Data 변수에 복사

Create( )

= 빈 리스트 만들기

Destroy( )

= 리스트 없애기

IsEmpty( )

= 빈 리스트인지 확인

Length( )

= 몇 개의 항목인지 계산

 

C배열에 의한 리스트

#define MAX 100                             최대 100개 데이터를 저장 

  typedef struct           

  { int Count;                                리스트 길이(데이터 개수)를 추적 

   int Data[MAX];                         리스트 데이터는 정수형 

  } listType;                                 리스트 타입은 구조체 

  void Insert(listType *Lptr, int Position, int Item); 해당 위치에 데이터를 삽입 

  void Delete(listType *Lptr, int Position);   해당 위치 데이터를 삭제 

  void Retrieve(listType *Lptr, int Position, int *ItemPtr); 

  찾은 데이터를 *ItemPtr에 넣음 

  void Init(listType *Lptr);                 초기화   

  bool IsEmpty(listType *Lptr);             비어있는지 확인  

  int Length(listType *Lptr);                리스트 내 데이터 개수 

 

연결 리스트 기초

typedef struct nodeRecord{

   int Data;                              노드 내부의 실제 데이터 또는 레코드

   struct nodeRecord* Next;  Next가 가리키는 것은 node 타입

} node;                                    구조체에 node라는 새로운 타입명 부여

typedef node* Nptr;              Nptr 타입이 가리키는 것은 node 타입

Nptr p, q;                                Nptr 타입 변수 p,q를 선언

노드 만들기, 이어 붙이기

p = (node*)malloc(sizeof(node));

p->Data = 33;

p->Next = (node*)malloc(sizeof(node));

p->Next->Data = 22;

p->Next->Next = NULL;

공간 반납

Nptr Head;

Head = (node*)malloc(sizeof(node));

Head->Data = 11;

Head->Next = NULL;

free Head;

Head = NULL;

디스플레이

Temp = Head;

While (Temp != NULL){

       printf("%d ", Temp->Data);

       Temp = Temp->Next;

}

 

간단한 삽입

p = (node*)malloc(sizeof(node));

p->Data = 8;

p->Next = Temp->Next;

Temp->Next = p;

 

간단한 삭제

p= Temp->Next;

Temp->Next = Temp->Next->Next  //Temp->Next = p->Next;

free p;