C로 연결된 목록 : C로 연결된 목록을 구현하는 방법?



C의 Linked List에 대한 그의 블로그는 C의 Linked List 데이터 구조를 소개하고 예제를 통해 연결된 목록 구현을 자세히 이해하는 데 도움을줍니다.

배열 다음으로 가장 많이 사용되는 데이터 구조는 Linked List입니다. 연결 목록은 각 노드에 값과 체인의 다음 노드에 대한 포인터가 포함 된 노드 체인으로 구성된 선형 데이터 구조입니다. 이 기사에서는 C에서 연결 목록을 구현하는 방법을 살펴 보겠습니다.

C에서 연결 목록이란 무엇입니까?

연결된 목록은 선형 데이터 구조입니다. 모든 연결 목록에는 데이터 섹션과 노드라고하는 목록에서 다음 요소의 주소를 보유하는 주소 섹션의 두 부분이 있습니다.





연결 목록의 크기는 고정되어 있지 않으며 목록의 모든 위치에 데이터 항목을 추가 할 수 있습니다. 단점은 노드에 도달하려면 첫 번째 노드에서 필요한 노드까지 계속 이동해야한다는 것입니다. Linked List는 배열과 비슷하지만 배열과 달리 메모리에 순차적으로 저장되지 않습니다.

가장 많이 사용되는 연결 목록 유형은 다음과 같습니다.



  1. 단일 링크 목록
  2. 이중 링크 목록

연결 목록의 예

형식 : [데이터, 주소]

머리-> [3,1000]-> [43,1001]-> [21,1002]



이 예에서 숫자 43은 위치 1000에 있고 주소는 이전 노드에 있습니다. 이것이 연결 목록이 표시되는 방식입니다.

C ++ 프로그램에서 배열 정렬

기본 연결 목록 기능

C의 연결 목록에 구현할 수있는 여러 기능이 있습니다. 예제 프로그램을 통해 이해해 봅시다.먼저 목록을 만들고 표시하고 임의의 위치에 삽입하고 위치를 삭제합니다. 다음 코드는 목록에서 작업을 수행하는 방법을 보여줍니다.

#include #include void create () void display () void insert_begin () void insert_end () void insert_pos () void delete_begin () void delete_end () void delete_pos () struct node {int info struct node * next} struct node * start = NULL int main () {int choice while (1) {printf ( 'n MENU n') printf ( 'n 1.Create n') printf ( 'n 2.Display n') printf ( 'n 3.Insert at 시작 n ') printf ('n 4. 끝에 삽입 n ') printf ('n 5. 지정된 위치에 삽입 n ') printf ('n 6. 처음부터 삭제 n ') printf ('n 7. 삭제 끝부터 n ') printf ('n 8. 지정된 위치에서 삭제 n ') printf ('n 9.Exit n ') printf ('n ----------------- --------------------- n ') printf ('선택 항목 입력 : t ') scanf ('% d ', & choice) switch (choice) {사례 1 : create () 브레이크 케이스 2 : display () 브레이크 케이스 3 : insert_begin () 브레이크 케이스 4 : insert_end () 브레이크 케이스 5 : insert_pos () 브레이크 케이스 6 : delete_begin () 브레이크 케이스 7 : delete_end () 브레이크 케이스 8 : delete_pos () break case 9 : exit (0) break default : printf ( 'n Wrong Choice : n') break}} return 0} voi d create () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ( 'nOut of Memory Space : n') exit (0) } printf ( 'nEnter the data value for the node : t') scanf ( '% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} void display () {구조체 노드 * ptr if (start == NULL) {printf ( 'nList가 비어 있습니다 : n ') return} else {ptr = start printf ('n 목록 요소는 : n ') while (ptr! = NULL) {printf ('% dt ', ptr-> info) ptr = ptr-> next}}} void insert_begin () {struct node * temp temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ( 'nOut of Memory Space : n') return} printf ( 'nEnter the 노드의 데이터 값 : t ') scanf ('% d ', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {temp-> next = start start = temp }} void insert_end () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ( 'nOut of Memory Space : n') return} 피 rintf ( 'nEnter the data value for the node : t') scanf ( '% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} void insert_pos () {struct node * ptr, * temp int i, pos temp = (struct node *) malloc ( sizeof (struct node)) if (temp == NULL) {printf ( 'nOut of Memory Space : n') return} printf ( 'nEnter the position for the new node to be insert : t') scanf ( '% d' , & pos) printf ( 'n 노드의 데이터 값 입력 : t') scanf ( '% d', & temp-> info) temp-> next = NULL if (pos == 0) {temp-> next = start start = temp} else {for (i = 0, ptr = startinext if (ptr == NULL) {printf ( 'nPosition not found : [조심해서 처리] n') return}} temp-> next = ptr-> next ptr -> next = temp}} void delete_begin () {struct node * ptr if (ptr == NULL) {printf ( 'nList is Empty : n') return} else {ptr = start start = start-> next printf ( ' n 삭제 된 요소는 : % dt ', ptr-> info) free (ptr)}} void delete_end () {struct node * temp, * ptr if (start == NULL) {printf ('nList is Empty : ') exit (0) } else if (start-> next == NULL) {ptr = start start = NULL printf ( 'n 삭제 된 요소는 : % dt', ptr-> info) free (ptr)} else {ptr = start while (ptr- > next! = NULL) {temp = ptr ptr = ptr-> next} temp-> next = NULL printf ( 'n 삭제 된 요소는 : % dt', ptr-> info) free (ptr)}} void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ( 'nThe List is Empty : n') exit (0)} else {printf ( 'n 삭제할 노드의 위치 입력 : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf ('n 삭제 된 요소는 : % dt ', ptr-> info) free (ptr )} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ( 'nPosition not Found : n') return}} temp-> next = ptr-> next printf ( 'n 삭제 된 요소는 다음과 같습니다. % dt ', ptr-> info) free (ptr)}}}

이 코드의 첫 번째 부분은 구조를 만드는 것입니다. 연결 목록 구조는 우리가 필요로하는 데이터와 주소를 보유 할 수 있도록 생성됩니다. 이것은 컴파일러에게 노드가 어떻게되어야하는지에 대한 아이디어를 제공하기 위해 수행됩니다.

struct node {int info struct node * next}

구조에는 데이터를 저장하기위한 info라는 데이터 변수와 주소를 가리키는 포인터 변수가 있습니다. 다음과 같이 연결된 목록에서 수행 할 수있는 다양한 작업이 있습니다.

  • 창조하다()
  • 디스플레이()
  • insert_begin ()
  • insert_end ()
  • ] 삽입 _pos ()
  • delete_begin ()
  • delete_end ()
  • delete_pos ()

이러한 기능은 메뉴 구동 주 기능에 의해 호출됩니다. 주요 기능에서는 사용자가 프로그램에서 수행하려는 작업을 기반으로 사용자로부터 입력을받습니다. 입력은 사용자 입력에 따라 스위치 케이스로 전송됩니다.

제공된 입력에 따라 함수가 호출됩니다. 다음으로 해결해야 할 여러 기능이 있습니다. 이러한 각 기능을 살펴 보겠습니다.

기능 생성

먼저 연결 목록을 생성하는 생성 기능이 있습니다. 이것이 연결 목록을 만드는 기본 방법입니다. 코드를 살펴 보겠습니다.

메서드 오버로딩과 메서드 재정의의 차이점
void create () {struct node * temp, * ptr printf ( 'nEnter the data value for the node : t') scanf ( '% d', & temp-> info) temp-> next = NULL if (start == NULL ) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}}

산출

삽입-연결된 목록-Edureka

먼저, 두 개의 포인터가 노드, ptr 및 임시 . 사용자로부터 연결 목록에 추가해야하는 값을 가져 와서 임시 변수의 정보 부분에 저장하고 주소 부분 인 next의 temp를 null에 할당합니다. 목록의 시작을 유지하는 시작 포인터가 있습니다. 그런 다음 목록의 시작을 확인합니다. 목록의 시작이 null이면 시작 포인터에 temp를 할당합니다. 그렇지 않으면 데이터가 추가 된 마지막 지점으로 이동합니다.

이를 위해 ptr에 시작 값을 할당하고 ptr-> next = null . 그런 다음 ptr-> 다음 임시 주소. 비슷한 방식으로 처음에 삽입, 끝에 삽입, 지정된 위치에 삽입하는 코드가 있습니다.

디스플레이 기능

표시 기능에 대한 코드는 다음과 같습니다.

void display () {struct node * ptr if (start == NULL) {printf ( 'nList is empty : n') return} else {ptr = start printf ( 'nThe List elements are : n') while (ptr! = NULL) {printf ( '% dt', ptr-> info) ptr = ptr-> 다음}}}

산출

디스플레이 함수에서 먼저 목록이 비어 있는지 확인하고 비어 있으면 반환합니다. 다음 부분에서는 시작 값을 ptr에 할당합니다. 그런 다음 ptr이 null이 될 때까지 루프를 실행하고 ptr이 null이 될 때까지 각 노드에 대한 데이터 요소를 인쇄하여 목록의 끝을 지정합니다.

기능 삭제

다음은 연결 목록에서 노드를 삭제하는 코드입니다.

void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ( 'nThe List is Empty : n') exit (0)} else {printf ( 'nEnter the position of the 삭제할 노드 : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf ('n 삭제 된 요소는 : % dt ', ptr-> info ) free (ptr)} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ( 'nPosition not Found : n') return}} temp-> next = ptr-> next printf ( 'nThe 삭제 된 요소는 다음과 같습니다. % dt ', ptr-> info) free (ptr)}}}

산출

삭제 과정에서 먼저 목록이 비어 있는지, 만약 있다면 존재하는지 확인합니다. 비어 있지 않으면 사용자에게 삭제할 위치를 묻습니다. 사용자가 위치를 입력하면 첫 번째 위치인지 확인하고 예인 경우 할당합니다. ptr 시작 포인터를 다음 위치로 이동하고 ptr을 삭제합니다. 만약 위치가 0이 아닙니다 , 그런 다음 0에서 사용자가 입력 한 pos까지 for 루프를 실행하고 pos 변하기 쉬운. 입력 한 위치가 없는지 여부를 결정하는 if 문이 있습니다. 만약 ptr은 null과 같습니다. 이면 존재하지 않습니다.

우리 ptr을 temp에 할당 for 루프에서 ptr은 다음 부분으로 이동합니다. 그 후 위치가 발견되면. 값을 유지하기 위해 임시 변수를 만듭니다. ptr-> 다음 따라서 ptr을 건너 뜁니다. 그런 다음 ptr이 삭제됩니다. 마찬가지로 첫 번째 및 마지막 요소 삭제에 대해 수행 할 수 있습니다.

이중 연결 목록

두 가지가 있기 때문에 이중 연결 목록이라고합니다. 포인터 , 한 지점은 다음 노드를 가리키고 다른 지점은 이전 노드를 가리 킵니다. 이중 연결에서 수행되는 작업은 단일 연결 목록의 작업과 유사합니다. 다음은 기본 작업에 대한 코드입니다.

#include #include struct Node typedef struct Node * PtrToNode typedef PtrToNode 목록 typedef PtrToNode Position struct Node {int e Position 이전 Position 다음} void Insert (int x, List l, Position p) {Position TmpCell TmpCell = (struct Node *) malloc (sizeof (struct Node)) if (TmpCell == NULL) printf ( '메모리 부족') else {TmpCell-> e = x TmpCell-> 이전 = p TmpCell-> next = p-> 다음 p-> next = TmpCell}} void Delete (int x, List l) {Position p, p1, p2 p = Find (x, l) if (p! = NULL) {p1 = p-> 이전 p2 = p-> 다음 p1- > next = p-> next if (p2! = NULL) // 노드가 마지막 노드가 아닌 경우 p2-> previous = p-> previous} else printf ( '요소가 존재하지 않습니다 !!! n')} void Display (List l) {printf ( 'The list element are ::') Position p = l-> next while (p! = NULL) {printf ( '% d->', p-> e) p = p- > 다음}} int main () {int x, pos, ch, i List l, l1 l = (struct Node *) malloc (sizeof (struct Node)) l-> previous = NULL l-> next = NULL List p = l printf ( 'L의 이중 연결 목록 구현 IST ADTnn ') do {printf ('nn1. CREATEn 2. DELETEn 3. DISPLAYn 4. QUITnn 선택 항목 입력 :: ') scanf ('% d ', & ch) switch (ch) {case 1 : p = l printf ('삽입 할 요소 입력 :: ') scanf ( '% d', & x) printf ( '요소의 위치 입력 ::') scanf ( '% d', & pos) for (i = 1 inext} Insert (x, l, p) break case 2 : p = l printf ( '삭제할 요소를 입력하세요 ::') scanf ( '% d', & x) Delete (x, p) break case 3 : 디스플레이 (l) 중단}} while (ch<4) } 

산출

빅 데이터 분석 적용

따라서 보시다시피 작업의 개념은 매우 간단합니다. 이중 연결 목록은 C 프로그래밍 언어의 단일 연결 목록과 동일한 작업을 수행합니다. 유일한 차이점은 이중 연결 목록에서 목록을 더 잘 탐색하는 데 도움이되는 또 다른 주소 변수가 있다는 것입니다.

C에서 단일 및 이중 연결 목록에 대한 기본 작업을 수행하는 방법을 이해 하셨기를 바랍니다.

Java의 Linked List를 배우고 싶다면 여기 .

질문이 있으시면 'C로 연결된 목록'의 댓글 섹션에있는 모든 질문에 자유롭게 질문하시면 저희 팀이 기꺼이 답변 해 드리겠습니다.