[IT] C언어 입문(13) 자료구조(data structure) 예시 - 연결리스트(linked list)

 * Unions

 - The same syntax as structures

 - But, members share storage

 - Union은 Structure에 비해 메모리 공간을 아낄 수는 있으나 요즘엔 그닥...

 - 어떤 변수로 액세스 하느냐에 따라서 달라짐;;

 

structure와 union의 차이점

---

struct foo {
	int n;
	float r;
} p;

 ==> p   n |      |

            r  |      |

 

union foo {
	int n;
	float r;
} q;

  ==> q   n, r  |      |

 

---

typedef union foo {
	int n;
	float r;
} number;                 // number type 정의

int main(void)
{
	number m;         // number type 선언
	m.n = 2345;
	printf("n: %10d   r: %16.10e\n", m.n, n.r);
	m.r = 2.345;
	printf("n: %10d   r: %16.10e\n", m.n, m.r);
	return 0;
}

---

 

 * Bit Fields

 - An int or unsigned member of a structure or union can be declared to consist of a specified number of bits

 - bit_field_member ::= { int | unsigned} { identifier }opt : expr

 - expr ::= constant_integral_expression

 - Unnamed bit fields can be used for padding and alignment purposes

 

struct foo {
	int a : 2;
	unsigned b: 4;
} a;

struct bar {
	usigned n1 : 14, n2 : 14, n3 : 4, n4 : 6, n5 : 6, n6 : 6;    // bit field 개념 사용
}

 

 

 * Enumeration Types

 - A means of naming a finite set

 - User defined types

 - enum_declaration ::= enum_type_specifier { identifier { , identifier }* }opt;

 - enum_type_specifier ::= enum e_tag { e_list } | enum e_tag | enum { e_list }

 - e_tag ::= identifier

 - e_list ::= enumerator { , enumerator }*

 - enumerator ::= identifier { = constant_integer_expression }opt

 

enum day { sun, mon, tue, wed, thu, fir, sat };      //day라는 새로운 type 형성, 선언, 내부에선 모두 정수로 처리됨

enum day { sun=1, mon, tue, wed, thu, fri, sat } p, q, r;

enum day { sun=7, mon, tue, wed=2, thu, fri, sat} p, q, r;

 

---

enum day { sun, mon, tue, wed, thu, fir, sat };

typedef enum day day;

day nextDay( day d )
{
	day next_day;
	switch( d ) {       //스위치 문의 조건은 정수값만, enum은 내부적으로 정수형으로 표현하므로 가능
		case sum:
			next_day=mon;
		break;

		case mon:
			next_day=tue;
		break;

		...

		case sat:
			next_day=sun;
		break;
	}
	return next_day;
}

 

---

좀 더 간결하게 표현하면

 

enum day { sun, mon, tue, wed, thu, fri, sat };

typedef enum day day;

day nextDay( day d )
{
	assert( (int) d >= 0 && (int) d < 7 );     // 정상 범위의 값이 넘어오는지 error check
	return ( (day)  ( ((int) d + 1) %7 ) );    // 정수값을 다시 day로 type casting
}

---

 

 

□ linked list

 * Linked List

 - Consists of a sequence of nodes, each containing arbitrary data fields and one or two references ("links") pointing to the next and / or previous nodes.

 - A self-referential date type because it contains a pointer or link to another datum of the same type.

 - Permits insertion and removal of nodes at any point in the list in constant time. but do not allow random access.

 - 배열보다 더 데이터를 아낄 수 있음..

 

#include <stdio.h>
#include <stdlib.h>

typedef char DATA;           // 코드의 확장, 호환성을 위해... 

struct linked_list {         // linked list는 structure 형태로 만듦
	DATA d;
	struct linked_list *next;
};

typedef struct linked_list ELEMENT;
typedef ELEMENT *LINK;
...
LINK head;
head = malloc(sizeof(ELEMENT));
head->d = 'n';          // 포인터를 거쳐서 access하므로 'LINK.member'형태가 아닌 '->' 표시를 사용 
head->next = NULL;

 

---

서브루틴 예시

LINK stringToList (char s[])
{
	LINK head;

	if ( s[0] == '\0' )
		return NULL;
	else {
		head = malloc(sizeof(ELEMENT));
		head->d = s[0];
		head -> next = stringToList(s+1);
		return head;
	}
}

---

※ C언어 입문 시리즈
1. Introduction - C언어의 역사와 기본 개념
2. Variables - 변수, 대입연산자, 구문규칙, 데이터타입 등
3. Data types, 데이터 타입(자료형)
4. Operators, 연산자 - scanf, 산술연산자, 관계연산자, 증감연산자, 대입연산자, 동등연산자 등
5. Operators, 연산자 - 논리연산자, 단축평가, 대입연산자, if문 및 while문 활용
6. Control flow, 제어흐름 - While문, For문, If문, do-while문 등 루프문
7. Function, 함수 - Goto문, getchar와 putchar, 함수 정의와 프로토타입 선언
8. Scope rules/recursion, 변수의 영역규칙과 재귀호출, 난수생성 예시
9. Array와 Pointers, 배열과 포인터
10. Pointer, 역참조, swap 함수 활용, 배열과 포인터 비교
11. File operation 파일연산, String, 다차원 배열 예시
12. structure, union, enumerated types - 구조체, 공용체, 열거체
13. 자료구조(data structure) 예시 - 연결리스트(linked list)
14. C 전처리기(C preprocessor), 함수 포인터(function pointer)