index * 데이터타입 크기
고정된 크기
연속된 메모리 할당은 불편함
단점
1. 공간 효율성이 떨어짐
2. 차곡차곡성을 지키기 위해 많은 계산이 필요함
3. dynamic한 data를 다루기에 한계가 있음
장점
1. ramdomly access //memory access에 uniform함
2.
malloc으로 공간을 dynamic하게 잡을 수있지만 index는 포인터(한정적인 문제)
-> 포인터를 실시간으로 만들자
인덱스 + 담을 공간 + 포인터 1개 생성(다음 것을 가리키는)
-> data 만드는 개수만큼 포인터 생성
데이터를 새로 받는 만큼 포인터를 생성해서 다음 데이터를 받는 ..
동적으로
Linked List
장점
1. 가변적으로 확대하거나 축소할 수 있음
2. 추가/삭제가 용이 연결 관계만 바꾸면 됌 비용이 쌈
단점
1. array는 geometric하게 가능하지만 linked list는 연결관계 순으로 접근해야 함(상보적 관계)
2. 순서 관계가 헷갈림? (dellema)
3.
-> 사용자는 개발 특성에 따라 적절한 List 사용
single Linked List, array list의 살짝 변형
연결관계에 Link -> 다음 array
출발점을 별도의 variable에 저장
한계점: capacity만큼 꽉 잡고 있어서 늘리거나 그런거 ㄴ
code/Apr12/arrlist.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef
struct {
int arrlen ;
int size ;
int first ;
char * data ;
int link ;
}
arrlist_t ;
arrlist_t * create_arrlist (int capacity)
{
if (capacity <= 0) {
return NULL ;
}
arrlist_t * l = (arrlist_t *) malloc(sizeof(arrlist_t)) ;
if (l == NULL) {
return NULL ;
}
l->arrlen = capacity + 1 ; // +1 ? 0번 index를 null 값으로
l->size = 0 ;
l->first = 0 ;
l->data = (char **) calloc(l->arrlen, sizeof(char *)) ;
l->link = (int *) calloc(l->arrlen, sizeof(int)) ;
memset(l->link, 0, l->arrlen * sizeof(int)) ;
if (l->data == NULL || l->link == NULL) {
free(l) ;
return NULL ;
}
return l ; }
int insert_arrlist (arrlist_t l, char s)
{
if (s == NULL)
return 0 ;
if (l->size == l->arrlen - 1)
return 0 ;
int next = 1 ;
while (l->data[next] != NULL) {
next++ ;
}
l->data[next] = s ;
l->link[next] = 0 ;
/* TODO */
l->size++ ;
return 1 ;}
char delete_arrlist (arrlist_t l, char * s)
{
if (l->size == 0)
return NULL ;
int i, prev ;
/* TODO */
char * r = l->data[i] ;
l->data[i] = NULL ;
if (prev == 0) {
l->first = l->link[i] ;
}
else {
l->link[prev] = l->link[i] ;
}
return r ;}
void print_arrlist (arrlist_t * l)
{
int i ;
for (i = l->first ; i != 0 ; i = l->link[i]) {
printf("%s ", l->data[i]) ;
}
printf("\n") ;
}
void free_arrlist (arrlist_t * l)
{
free(l->data) ;
free(l->link) ;
free(l) ;
}
int main () //string 입력을 받음, string표현하는 포인터를 저장
{
arrlist_t * l = create_arrlist(30) ;
insert_arrlist(l, "BAT") ;
insert_arrlist(l, "CAT") ;
insert_arrlist(l, "EAT") ;
insert_arrlist(l, "FAT") ;
insert_arrlist(l, "GAT") ;
insert_arrlist(l, "HAT") ;
insert_arrlist(l, "VAT") ;
insert_arrlist(l, "WAT") ;
delete_arrlist(l, "FAT") ;
delete_arrlist(l, "VAT") ;
print_arrlist(l) ;
free_arrlist(l) ;
return EXIT_SUCCESS ;}
code/Apr12/arrlist.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef
struct {
int arrlen ;
int size ;
int first ;
char * data ;
int link ;
}
arrlist_t ;
arrlist_t * create_arrlist (int capacity)
{
if (capacity <= 0) {
return NULL ;
}
arrlist_t * l = (arrlist_t *) malloc(sizeof(arrlist_t)) ;
if (l == NULL) {
return NULL ;
}
l->arrlen = capacity + 1 ;
l->size = 0 ;
l->first = 0 ;
l->data = (char **) calloc(l->arrlen, sizeof(char *)) ;
l->link = (int *) calloc(l->arrlen, sizeof(int)) ;
memset(l->data, 0, ----)
memset(l->link, 0, l->arrlen * sizeof(int)) ;
if (l->data == NULL || l->link == NULL) {
free(l) ;
return NULL ;
}
return l ; }
int insert_arrlist (arrlist_t l, char s)
{
if (s == NULL)
return 0 ;
if (l->size == l->arrlen - 1) // size가 꽉 차서 못받음
return 0 ;
// allocate
int next = 1 ;
while (l->data[next] != NULL) { //새로 넣을 위치
next++ ;
}
l->data[next] = s ;
l->link[next] = 0 ; //다음이 없는 -> 링크 값 0으로 표현
/* TODO: link 마지막 애랑 연결시켜주는 */
if (l-> first == 0){
l->first = next;
}
else{
//int i;
//for (i =. ->fisrst; l->link[i] !=0; i= l->link[i]);
i = l->first;
while(l-> link[i] !=0){
i= l-> link[i]
}
// l->link[0] ==0, while의 의도
l-> link[i] = next //후임이 생겼다 개념
}
l->size++ ;
return 1 ;}
char delete_arrlist (arrlist_t l, char * s)
{
if (l->size == 0)
return NULL ;
int i, prev ; //i는 빼야되는 인덱스, prev는 그것의 앞에꺼
/* TODO */
//i는 first로 시작, s= string이 같을 때 까지 반복
prev =0;
i = l->first;
while(i != 0){
if}
while(*s != data[i]){
}
char * r = l->data[i] ;
l->data[i] = NULL ;
if (prev == 0) { //뺄게없다, first인 경우-> prev가 없음
l->first = l->link[i] ;
}
else {
l->link[prev] = l->link[i] ;
}
return r ;}
void print_arrlist (arrlist_t * l)
{
int i ;
for (i = l->first ; i != 0 ; i = l->link[i]) {
printf("%s ", l->data[i]) ;
}
printf("\n") ;
}
void free_arrlist (arrlist_t * l)
{
free(l->data) ;
free(l->link) ;
free(l) ;
}
int main ()
{
arrlist_t * l = create_arrlist(30) ;
insert_arrlist(l, "BAT") ;
insert_arrlist(l, "CAT") ;
insert_arrlist(l, "EAT") ;
insert_arrlist(l, "FAT") ;
insert_arrlist(l, "GAT") ;
insert_arrlist(l, "HAT") ;
insert_arrlist(l, "VAT") ;
insert_arrlist(l, "WAT") ;
delete_arrlist(l, "FAT") ;
delete_arrlist(l, "VAT") ;
print_arrlist(l) ;
free_arrlist(l) ;
return EXIT_SUCCESS ;}
