양방향 연결 리스트
자료구조 & 알고리즘 :
2007. 5. 12. 12:45
반응형
001: #include <stdio.h> 002: #include <stdlib.h> 003: 004: typedef struct ListNode{ 005: struct ListNode *font_link; //앞에 노드를 가리킨다. 006: int data; 007: struct ListNode *link; // 자체참조구조체변수를 위한 포인터변수 선언 008: } ListNode; 009: 010: void insert(ListNode *head, int data); //알맞은 곳에 붙인다. 011: ListNode* head_insert(ListNode *head, int data); //새로운 입력 값이 가장 클 경우 맨 앞에 넣는다. 012: ListNode* create_node(ListNode *link, int data); //초기에 리스트가 비었을 경우 리스트를 생성 한다. 013: void display_recur(ListNode *h); // 리스트 전체 출력한다. 014: 015: int main(void) 016: { 017: ListNode *head = NULL; 018: 019: int num, i; 020: 021: for(i = 0; i < 5; i++) { 022: printf(" %d 번째 input data : ", i+1); 023: scanf("%d", &num); 024: 025: if (head == NULL) //현재 리스트가 비어 있다면 026: head=create_node(head, num); //리스트를 생성하여서 head에 넣는다. 027: else if (head->data < num) //비어있지 않고 값이 가장 클 경우 맨 앞에 붙인다. 028: head=head_insert(head, num); 029: else //현재 데이터보다 새로운 데이터가 작으면 알맞은 곳에 붙인다. 030: insert(head, num); 031: 032: display_recur(head); 033: } 034: display_recur(head); 035: return 0; 036: } 037: 038: ListNode* create_node(ListNode *link, int data) 039: { 040: ListNode *new_node; // 새로운노드생성 041: new_node = (ListNode *) malloc (sizeof(ListNode)); // 용량동적할당 042: if(new_node == NULL) printf("메모리 할당에러 \n"); 043: new_node->data = data; // 값을 넣음 044: new_node->link = NULL; // 다음노드로 link 045: new_node->font_link=NULL; 046: return (new_node); // 노드반환 047: } 048: 049: //출력함수 050: void display_recur(ListNode *h) 051: { 052: if(h==NULL) 053: printf("Empty list.\n"); 054: else{ 055: ListNode *p = h; 056: 057: printf("value : "); 058: 059: if( p != NULL ) // NULL이 나올 때까지 060: { 061: printf("%d ", p->data); // data값출력 062: display_recur(p->link); // 다음 노드로 link 063: } 064: } 065: } 066: 067: //알맞은 곳에 붙인다. 068: void insert(ListNode *head, int num) 069: { 070: if(head->data < num){ 071: ListNode *new_node; 072: new_node = (ListNode *) malloc (sizeof(ListNode)); 073: new_node->data = num; 074: new_node->link = head; 075: new_node->font_link=head->font_link; 076: head->font_link->link=new_node; 077: head->font_link=new_node; 078: } 079: else if(head->link == NULL){ 080: ListNode *new_node; 081: new_node = (ListNode *) malloc (sizeof(ListNode)); 082: new_node->data = num; 083: new_node->link = NULL; 084: new_node->font_link=head; 085: head->link=new_node; 086: } 087: else if(head->data > num) 088: insert(head->link, num); 089: } 090: 091: //새로운 입력 값이 가장 클 경우 맨 앞에 넣는다. 092: ListNode* head_insert(ListNode *head, int data) 093: { 094: ListNode *new_node; 095: new_node = (ListNode *) malloc (sizeof(ListNode)); 096: new_node->data = data; 097: new_node->link = head; 098: new_node->font_link=NULL; 099: head->font_link=new_node; 100: return (new_node); 101: }
반응형
'자료구조 & 알고리즘' 카테고리의 다른 글
n-Queens 알고리즘 (0) | 2007.04.21 |
---|---|
Dijkstra 알고리즘 증명 (0) | 2007.04.21 |
Kruskal 알고리즘 증명 (0) | 2007.04.21 |