프로그래밍 랩 – 7주 리스트.

Presentation on theme: "프로그래밍 랩 – 7주 리스트."— Presentation transcript:

1 프로그래밍 랩 – 7주 리스트

2 Lab 7-1: 리스트 - 배열 배열을 이용한 List 리스트 함수
#define MAX_LIST_SIZE 100 // 배열의 최대크기 typedef int element; typedef struct { int list[MAX_LIST_SIZE]; // 배열 정의 int length; // 현재 배열에 저장된 자료들의 개수 } ArrayListType; 리스트 함수 void init(ArrayListType *L) int is_empty(ArrayListType *L) int is_full(ArrayListType *L) void display(ArrayListType *L) void add(ArrayListType *L, int position, element item) element delete_list(ArrayListType *L, int position) element search(ArrayListType *L, element data) //완성할것

3 Lab 7-2: 연결 리스트 단순 연결 리스트 사용 #define FALSE 0 #define TRUE 1 typedef int element; typedef struct ListNode { element data; struct ListNode *link; } ListNode; typedef struct { ListNode *head; // 헤드포인터 int length;// 노드의 개수 } ListType; void insert_node(ListNode **phead, ListNode *p, ListNode *new_node) void remove_node(ListNode **phead, ListNode *p, ListNode *removed) void init(ListType *list) ListNode *get_node_at(ListType *list, int pos) int get_length(ListType *list) void add(ListType *list, int position, element data) void add_last(ListType *list, element data) void add_first(ListType *list, element data) int is_empty(ListType *list) void Delete(ListType *list, int pos) element get_entry(ListType *list, int pos) void clear(ListType *list) void display(ListType *list) int is_in_list(ListType *list, element item) ListNode *search(ListType *list, element data, int *pos) 찾으면 ListNode 못 찾으면 NULL return // 구현할것

4 Lab 7-3: 문자열 데이터 리스트 Node에 문자열을 Data로 보관 함수들
typedef char * element; typedef struct ListNode { element data; struct ListNode *link; } ListNode; typedef struct { ListNode *head; // 헤드 포인터 int length;// 노드의 개수 } ListType; 함수들 void add_tail(ListType *list, element item) node = (ListNode *)malloc(sizeof(ListNode)); node->data = (element)malloc(strlen(item)+1); // 문자열 저장 void display(ListType *list) int get_length(ListType *list) element get_entry(ListType *list, int n) ListNode *search(ListType *list, element item, int *pos) 찾으면 Pointer 를 return 하고 못 찾으면 NULL return

5 } main() { int i, n; ListType list; ListNode *node; char item[100];
// Lab7-3 문자열을 data로 갖는 리스트 linked list #include <stdio.h> #include <string.h> #include <stdlib.h> #define MAXITEM 100 typedef char * element; typedef struct ListNode { element data; struct ListNode *link; } ListNode; typedef struct { ListNode *head; // 헤드 포인터 int length;// 노드의 개수 } ListType; void add_tail(ListType *list, element item) { } void display(ListType *list) int get_length(ListType *list) element get_entry(ListType *list, int n) // 찾아서 Node를 return, 없으면 NULLt ListNode *search(ListType *list, element item) // 리스트를 초기화한다. void init(ListType *list) if( list == NULL ) return; list->length = 0; list->head = NULL; main() { int i, n; ListType list; ListNode *node; char item[100]; init(&list); add_tail(&list,"마요네즈"); add_tail(&list,"빵"); add_tail(&list,"치즈"); add_tail(&list,"우유"); n = get_length(&list); printf("쇼핑해야할 항목수는 %d입니다.\n", n); display(&list); for(i=0;i<n;i++) printf("%d항목은 %s입니다\n", i,get_entry(&list2,i)); while (1) { int pos; printf("찾을 항목 (종료quit) : "); scanf("%s", data); if (strcmp(data, "quit")==0) break; node = search(&list, data, &pos); if (node!=NULL) printf("[%d:%s]\n", pos, node->data); else printf("Not Found.!\n"); }

6 Lab 7-4: 이중 연결 리스트 left link 와 right link 사용 typedef int element;
typedef struct DlistNode { element data; struct DlistNode *llink; struct DlistNode *rlink; } DlistNode; 함수들 void init(DlistNode *phead) void display(DlistNode *phead) void dinsert_node(DlistNode *before,DlistNode *new_node) void dremove_node(DlistNode *phead_node, DlistNode *removed) DlistNode *search(DlistNode *phead_node, element data, int *pos) 찾으면 DlistNode pointer 못 찾으면 NULL return // 구현할것

7 Lab 7-ACM: 점수집계(2004)

8 Lab 7-ACM2: ACM1용 TEST DATA 생성기 만들기
srand(), rand() 사용 (1 ~ 10 5개 생성) Lab7-ACM2 생성, 복사, Lab7-ACM붙여넣기 KIN 확률이 주어진다면?? (예: KIN 30%)  Lab7-ACM과 합성 Mouse 우측, 표시, Enter로 복사, 우측 붙여넣기 <Lab7-acm2> <Lab7-acm>

9 리스트 ADT 객체: n개의 element형으로 구성된 순서있는 모임 ∙연산: ▪ add_last(list, item) ::= 맨끝에 요소를 추가한다. ▪ add_first(list, item) ::= 맨끝에 요소를 추가한다. ▪ add(list, pos, item) ::= pos 위치에 요소를 추가한다. ▪ delete(list, pos) ::= pos 위치의 요소를 제거한다. ▪ clear(list) ::= 리스트의 모든 요소를 제거한다. ▪ replace(list, pos, item) ::= pos 위치의 요소를 item로 바꾼다. ▪ is_in_list(list, item) ::= item이 리스트안에 있는지를 검사한다. ▪ get_entry(list, pos) ::= pos 위치의 요소를 반환한다. ▪ get_length(list) ::= 리스트의 길이를 구한다. ▪ is_empty(list) ::= 리스트가 비었는지를 검사한다. ▪ is_full(list) ::= 리스트가 꽉찼는지를 검사한다. ▪ display(list) ::= 리스트의 모든 요소를 표시한다.