전체 : 4,150,784 명
어제 : 0 명
오늘 : 0 명

리스트 자료구조의 기본적인 개념

진혼이중주 | 2008.05.16 15:11 | 조회 8037

※자료구조 공부하면서 기본적인 자료리스트 구조의 개념을 정리해봤어요 ㅎㅎ

단순 자료 리스트 구조는 다음과 같이 기본인 개념으로 나눌수 있다.

Head(머리) -> 자료1 -> 자료2 -> 자료3 -> 자료4 -> Tail (꼬리)

->의 관계는 포인터의 관계이다. 이것을 C++의 언어로 풀이하자면 다음과 같이 표현할수 있다.

다음은 c++로 표현했을때의 자료구조리스트 추상적인 모습이다.

class node

{

private:

자료

다음 자료의 node클래스포인터

public:

적절한 자료 처리의 클래스멤버함수.

}

다음은 c로 표현했을때의 리스트 자료구조의 추상적인 모습이다.

typedef struct node

{

자료

다음자료의 node구조체 포인터

}

적절한 자료 처리의 전역 함수

개념을 깨닳는게 중요하다.

여기서 개념을 찾기에는 어린시절의 꼬리잡기 놀이가 여기에 적용되면 좋겠다.

꼬리 잡기를 하는 각 사람과 사람이 자료라고 생각 해보자 그리고 그 사람은 앞에사람을 붙잡고 있다.

이것을 조금 다르게 표현하자면 사람은 자기 앞의 사람을 잡고 있다는 표현을 가르킨다는 표현으로 바꿔 보자?

무엇이 떠오르는가? 그렇다 바로 포인터다. 그리고

머리와 꼬리는 자료를 가지고 있지는 않다 그렇다면 왜 필요한것인가 자료를 관리하기 편해서라고 할수 있다.

항상 머리는 자료를 가지고 있지는 않지만 항상 누군가를 가르켜야 한다. 그리고 꼬리는 누군가를 가르키지는 않지만

항상 누군가에 의해 가르킴을 받고 있어야 한다. 그래야 자료의 소거의 삽입이 편한다.

이제까지의 개념을 가슴에 담아보고 다음의 코드를 읽어라... 코드의양이 많아 보이기는 하지만

결코 저 이론에서는 벗어나지 않았다.

음 비쥬얼 스튜디오를 쓰시는 분은 비쥬얼 스튜디오 C문서에다가 드르륵 긁어서 붙여넣기 한다음에

전체 드레그 한다음에 Alt + F8누르시면 자동으로 정렬이랑 들여쓰기가 됩니다. 참고 하세요.



#include
#include

typedef struct _node
{
int key;
struct _node *next;
} node;

node *head, *tail;


void init_list(void)
{
head = (node*) malloc(sizeof(node));
tail = (node*) malloc(sizeof(node));
head->next = tail;
tail->next = tail;

}


int delete_next (node * t)
{
node *s;
if (t->next == tail )
return 0;

s = t->next;
t->next = t->next->next;
free(s);
return 1;
}

node * insert_after(int k, node* t)
{
node* s;
s= (node*) malloc(sizeof (node));
s->key = k;
s->next = t->next;
t->next = s;

return s;
}


node* find_node(int k)
{
node* s;
s = head->next;
while(s->key != k && s != tail)
s = s->next;
return s;
}

int delete_node (int k)
{
node* s;
node* p;

p = head;
s = p->next;
while(s ->key != k && s != tail)
{
p = p->next;
s = p->next;
}
if(s != tail )
{
p->next = s->next;
free(s);
return 1;

}
else
return 0;
}


node* insert_node(int t, int k)
{
node* s;
node* p;
node* r;

p =head;
s = p -> next;

while(s ->key != k && s != tail)
{
p= p->next;
s= p->next;
}
if ( s != tail)
{
r = (node*) malloc( sizeof (node));
r->key = t;
p->next = r;
r->next = s;
}
return p->next;
}

node* ordered_insert( int k)
{
node* s;
node* p;
node* r;

p = head;
s = p->next;

while(s->key <= k && s != tail)
{
p = p->next;
s = p->next;
}

r =(node*) malloc(sizeof(node));
r->key = k;
p->next = r;
r->next = s;

return r;
}


void print_list(node* t)
{
printf("n");
while( t != tail )
{
printf("%-8d", t->key);
t = t->next;
}
}


node* delete_all(void)
{
node* s;
node * t;
t = head->next;

while (t != tail)
{
s = t;
t = t->next;
free(s);
}

head->next = tail;
return head;
}

void main(void)
{
node* t;
init_list();

ordered_insert(10);
ordered_insert(5);
ordered_insert(8);
ordered_insert(3);
ordered_insert(1);
ordered_insert(7);
ordered_insert(8);

printf("nInitial Linked list is");
print_list(head->next);

printf("nFinding 4 is %ssuccessful", find_node(4) == tail ? "un" : "");

t = find_node(5);

printf("nFinding 5 is &ssuccessful", t == tail ? "un" : "");

printf("nInerting 9 after 5");
insert_after(9, t);
print_list(head->next);

t = find_node(10);
printf("nDeleting next last node");
delete_next(t);
print_list(head->next);


t = find_node(3);
printf("nDeleting next 3");
delete_next(head->next);
print_list(head->next);

printf("nInsert node 2 befor 3");
insert_node(2, 3);
print_list(head->next);

printf("nDeleting node 2");
if(! delete_node(2))
printf("n deleting 2 is unsuccessful");
print_list(head->next);

printf("nDeleting node : 1");
delete_node(1);
print_list(head->next);

printf("nDeleting all node");
delete_all();
print_list(head->next);
}

twitter facebook me2day 요즘
스크롤압박-..-ㅋ
스크롤압박-..-ㅋ
05.18 15:58 | Нyan™님 | 신고 | 수정 | 삭제
댓글 0
입력상자 늘리기
흠... 천천히 배워가야겟네요...

흠... 천천히 배워가야겟네요...

06.20 14:27 | s파란별님 | 신고 | 수정 | 삭제
댓글 0
입력상자 늘리기
head 와 tail 을 쓰지않고 연결하는 방법도있지않나요?ㅎ;왠지 쓰기..
head 와 tail 을 쓰지않고 연결하는 방법도있지않나요?ㅎ;
왠지 쓰기는 head tail이 존재하는쪽이 편하긴 한거같은데..
05.26 04:57 | Quartz님 | 신고 | 수정 | 삭제
댓글 0
입력상자 늘리기
댓글쓰기 - 로그인한 후 댓글작성권한이 있을 경우 이용하실 수 있습니다.

비밀번호 확인

댓글 등록시에 입력했던 비밀번호를 입력해 주세요.
87개(1/5페이지)
rss
C
번호 제목 작성자 작성일 조회
87 배열설정 쉽게하기 부보 2012.12.22 2147
86 [고급]연습문제[11] 권율 2010.01.10 9660
85 [고급]C언어에서 포인터 이용한 간단한 암호 ~[8] 쫭구 2009.11.11 9478
84 [중급]BOF의 개념과 BOF를 이용한 해킹 방법[10] Ezbeat 2010.03.19 10252
83 [중급]ReadProcessMemory & WriteProcessMemory사진[8] COOLSOFT 2009.06.04 10033
82 [기초]C언어의 탄생 배경[20] COOLSOFT 2007.11.03 10137
81 [기초]비주얼 C++ 설치하기사진첨부파일[15] COOLSOFT 2007.10.27 7297
80 [기초]Microsoft Visual C++ Windows Applications by Example첨부파일[4] COOLSOFT 2009.04.03 7400
79 [기초][TIP]swap함수 매크로 한줄로 끝내기[9] secretofsh 2009.03.05 10739
78 [기초]c# 화면캡쳐프로그램 -소스포함 |첨부파일[12] 야옹이 2008.12.25 13038
77 [기초]주민번호를 만들어내는 규칙에 대해서 설명과 소스[26] COOLSOFT 2008.07.12 10298
76 [기초]윈도우 기본 창 생성 소스 -주석 포함-[7] 진혼이중주 2008.05.31 10894
75 [기초]WIN 32 API 시작하기전에 간단히 알아두기[10] 진혼이중주 2008.05.31 9485
74 [기초]c++ 강좌 #3 변수와 상수 (1)[15] 진혼이중주 2008.05.28 8986
73 [기초]C++ 강좌 #2 C++언어의 기본적인 구조[6] 진혼이중주 2008.05.28 6070
72 [기초]C++ 강좌 #1[12] 진혼이중주 2008.05.28 6849
>> [기초]리스트 자료구조의 기본적인 개념[3] 진혼이중주 2008.05.16 8038
70 [기초]두 자리 수 이상의 곱셈에 대한 알고리즘[5] 진혼이중주 2008.05.16 7277
69 [기초]Turbo 2.0 설치 및 사용법첨부파일[2] 진혼이중주 2008.05.16 8914
68 [기초]삼성 프로그래머들의 C/C++ 코딩 스타일의 지침서첨부파일[41] 진혼이중주 2008.05.05 15626
처음페이지이전 10 페이지12345다음 10 페이지마지막페이지