1. 리스트의 특징과 ADT
우선 순차리스트와 연결리스트는 구현 방법을 기준으로 한 구분이므로 ADT가 동일하다고 해서 문제가 되지는 않는다.
<리스트의 특징>
1. 데이터의 저장 형태 - 데이터를 나란히 저장
2. 저장 특성 - 중복이 되는 데이터의 저장을 허용
<리스트의 ADT>
1. 초기화
2. 저장
3. 저장된 첫 데이터 탐색
4. 다음 데이터 탐색 // 3,4가 구분되는 이유는 필요에 따라 첫데이터로 돌아가서 처음부터 탐색해야 할 필요성이 다분하기 때문
5. 삭제
6, 데이터의 수 반환
2. 리스트의 ADT를 기반으로 정의된 main함수
#include <stdio.h>
#include "ArrayList.h"
int main(void)
{
/*** ArrayList의 생성 및 초기화 ***/
List list; //리스트의 생성
int data; // int형 변수 data
ListInit(&list); //리스트의 초기화
/*** 5개의 데이터 저장 ***/
LInsert(&list, 1); LInsert(&list, 2);
LInsert(&list, 3); LInsert(&list, 4);
LInsert(&list, 5); //주소값을 인자로 전달하면서 리스트에 자료 저장
//나란히 저장하면 방향이 어디든 리스트
/*** 저장된 데이터의 전체 출력 ***/
printf("현재 데이터의 수: %d \n", LCount(&list));
if(LFirst(&list, &data)) // 텃번째 데이터 변수 data에 저장
{
printf("%d ", data); //첫번째 변수 출력
while(LNext(&list, &data)) // 두 번째 이후의 데이터 조회
printf("%d ", data);
}
printf("\n\n");
/*** 홀수를 탐색하여 모두 삭제 ***/
if(LFirst(&list, &data))
{
if(data % 2 == 1) // 확인 후 삭제 는 전형적인 패턴
LRemove(&list);
while(LNext(&list, &data))// list의 주소만 알고도 첫번쨰 데이터가 아닌 현재 데이터의 삭제가 가능하다니?
{
if(data % 2 == 1)
LRemove(&list);
}
}
/*** 삭제 후 저장된 데이터 전체 출력 ***/
printf("현재 데이터의 수: %d \n", LCount(&list));
if(LFirst(&list, &data))
{
printf("%d ", data);
while(LNext(&list, &data))
printf("%d ", data);
}
printf("\n\n");
return 0;
}3. 헤더파일
#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__
#define TRUE 1
#define FALSE 0
/*** ArrayList의 정의 ****/ //정형화되어있으므로 익혀두자.
#define LIST_LEN 100
typedef int LData; //다양한 데이터의 수용을 위해 typedef int LDa ta라 하고 필요시 int를 char, double 등으로 변경
typedef struct __ArrayList
{
LData arr[LIST_LEN]; //배열리스트이므로 배열 필요!
int numOfData; //numofData필수! 데이터 추가에 특히 용이
int curPosition; //데이터의 삭제에 용이하고 여기서는 구현되지 않았지만 데이터의 삽입에도 용이하다.
} ArrayList;
/*** ArrayList와 관련된 연산들 ****/
typedef ArrayList List;
void ListInit(List * plist);//리스트 구조체의 주소를 받아 초기화
void LInsert(List * plist, LData data);//리스트 구조체의 주소를 받아 삽입(맨마지막에 삽입하는 함수이다. 즉, 어디에 삽입할지는 상관없이 주소와 데이터만 있으면 된다.)
int LFirst(List * plist, LData * pdata);//리스트의 처음부터 탐색하는 함수
int LNext(List * plist, LData * pdata);//LFirst, LNext해서 해당칸에 있는 데이터는 pdata에 저장된 변수에 저장하고자 약속, 이 pdata가 홀수인지등을 찾아서 LRemove등의 동작을 한다.
LData LRemove(List * plist);//주소만 있으면 되는게 curPoint는 이미 리스트 구조체에 저장되어 있다.
int LCount(List * plist);
//나라면 Lprint함수를 정의해 curPosition을 반환했을 것
#endif헤더 파일과 main함수를 보고 직접 구현해보는 과정을 꼭 겪어보자!
4. 헤더파일을 보고 구현한 함수들, 그리고 내가 구현한 코드와 강의와의 비교
#include <stdio.h>
#include "ArrayList.h"
//리스트 초기화 먼저
void ListInit(List* plist)
{
int i;
for (i = 0; i < LIST_LEN; i++) plist->arr[i] = 0;
plist->numOfData = 0;
//**강의에서는 plist->curPosition = -1; 로 초기화**
}
//리스트에 데이터를 저장한다.
void LInsert(List* plist, LData data) //Ldata는 현재는 int, 필요에 따라 헤더파일에서 변경 가능
{
int i = 0;
plist->arr[plist->numOfData] = data;
plist->numOfData++;//curPosition을 이용하지 않은 이유 : list의 주소와 넣을 자료말고는 정보를 주지 않는다는 것은 어디에 넣겠다는 말이 없고 그럼 일반적으로 마지막에 넣겠다는 의미**,curPosition을 쓰면 중간에 삽입될 여지가 있다.**
}
int LFirst(List* plist, LData* pdata) //리스트의 첫번째 데이터를 받는다.
{
*pdata = plist->arr[0];
plist->curPosition = 0;
if (plist->arr[0]) return 1;//return 1과 return 0는 이 때 가 아니라 남아있는 데이터가 없을 때 쓰는 것.
else return 0;
}//이 때 LNext가 다음걸 출력하게 하려면 어떻게 해야하지? main에 count같은게 없는데? 아하 curPosition !
//즉, 이 코드는 if(plist->numOfData == 0) return 0;
else return 1; 하는게 맞았다.
int LNext(List* plist, LData* pdata)
{
*pdata = plist->arr[++(plist->curPosition)];
if (plist->arr[plist->curPosition]) return 1;
else return 0;//return 1 과 return 0는 이 때 쓰는게 아니라 더 이상 찾을 게 없을 때 0을 반환하고자 쓰는 것
}
//즉, 이 코드는 if(plist->curPosition >= (plist->numOfData) - 1) return 0; 을 처음에 적어주는게 맞다.
else면 마지막에 return 1;
int LCount(List* plist)
{
return plist->numOfData;
}
LData LRemove(List* plist)
{
int i;
int x = plist->numOfData;
LData y = plist->arr[plist->curPosition];
for (i = plist -> curPosition; i < x; i++)
{
plist -> arr[i] = plist -> arr[i + 1];//하나씩 땡끼는 과정
}
plist -> arr[x] = 0;//이전 마지막 칸은 0으로 비워주기
plist->numOfData--;
return y;//1. 삭제할 데이터는 반환하는 것이 옳다!!!!!!! 써먹을 일이 많을 것
}//curPosition은 가장 최근에 참조가 이루어진 데이터를 가리키는 것이 맞다. 안 그러면 A B C D E에서 C가 삭제되어 A B D E가 된후 LNext를 하게 되면 D를 건너뛰게 된다.
//따라서 plist->curPosition--가 필수.5. 리스트에 구조체 변수 저장하기
리스트에 구조체 변수를 저장하면 소스파일을 내가 구현할 때 = 0 으로 초기화하던 것만 제외하면 나머지는 손댈게 없다.
data변수가 걱정될 수 있어도
data변수 역시 정의한 구조체 변수와 같은 자료형으로 정의하면 문제될게 없다.
(구조체 A와 B가 저장돼있으면 A = B라고 쓰기 가능)
따라서 LInsert, LFirst, LNext, LRemove 모두 그대로 쓸 수 있다.
6. 주소를 Data로 썼을 때
저장된 자료의 메모리 주소를 데이터로 쓰고 그 주소는 malloc으로 할당받았을 때, free는 자료구조내부에서가 아닌 main에서 해주는 것이 맞다.
범용성있는 소스파일에서 받아오는게 주소인지 아닌지, malloc으로 할당받은 것인지 아닌지도 알 수 없기 때문이다.
그리고 이러한 경우들때문에 삭제시 삭제된 data를 리턴해주는게 맞다.
