연결된 목록은 어떤 저장 구조에 저장된 선형 목록입니다.

연결된 목록은 "체인으로 연결된" 저장 구조에 저장된 선형 목록입니다. 연결 리스트의 데이터 요소가 차지하는 저장 단위 주소는 연속적이거나 불연속적일 수 있으며, 해당 저장 공간은 필요에 따라 일시적으로 동적으로 할당될 수 있습니다. 데이터 요소 간의 논리적 관계는 "체인"으로 표현될 수 있습니다.

이 튜토리얼의 운영 환경: Windows 7 시스템, Dell G3 컴퓨터.

순차 테이블 저장 구조의 단점을 극복하고 저장 공간을 최대한 활용하며 운영 효율성을 향상시키기 위해 선형 테이블은 또 다른 저장 구조인 체인 저장 구조를 사용할 수 있습니다. 선형 목록의 연결된 저장 구조를 "링크 목록"이라고 합니다

1. 연결 목록 개요

연결 목록의 데이터 요소가 차지하는 저장 단위 주소는 필요에 따라 연속적이거나 불연속적일 수 있습니다. 해당 저장 공간의 할당을 일시적이고 동적으로 적용하며, 데이터 요소 간의 논리적 관계는 "체인"으로 표현될 수 있습니다.

연결된 목록의 삽입 및 삭제에는 데이터 요소 이동이 필요하지 않으며 체인만 수정하면 됩니다.

연결리스트 분류:

1. 연결리스트 메모리 할당 방식에 따라 분류

1 동적 연결 리스트

② 정적 연결 리스트

1 연결 방식에 따라 분류

1 단일 연결 리스트

② 순환 연결 리스트

3 이중 연결 리스트

(모두 동적 연결 리스트임)

2. 단일 연결 리스트의 정의

1. 정의

각 데이터 요소 ai와 그 직접적인 후속 요소 간의 논리적 관계를 표현하기 위해 데이터 요소 ai+1, 각 데이터 요소에 대해 자신의 정보를 저장하는 것 외에도 ai는 직계 후임자(후임자의 저장 위치 - 주소)를 나타내는 정보 를 저장하기 위해 도 필요합니다.

데이터 요소 정보를 저장하는 필드를 데이터 필드라고 하며, 직접적인 후속 위치를 저장하는 필드를 포인터 필드라고 합니다. 포인터 필드에 저장되는 정보를 포인터 또는 체인이라고 합니다.

이 두 부분의 정보는 node라고 불리는 데이터 요소 ai의 저장 이미지를 구성합니다.

n개의 노드는 선형 목록(a1, a2, a3,...,an)의 연결 저장 구조인 연결 목록에 연결됩니다. 연결 목록의 각 노드에는 하나의 포인터 필드만 포함되기 때문입니다. 이라는 싱글 링크드 리스트 입니다.

선형 목록에는 항상 머리와 꼬리가 있으며 연결 목록도 예외는 아닙니다. 연결된 목록에 있는 단일 연결 목록의 첫 번째 노드에 대한 포인터를 헤드 포인터라고 합니다. 전체 연결 목록에 대한 액세스는 헤드 포인터에서 시작해야 하며 각 후속 노드는 후속 노드가 가리킵니다. 이전 노드 위치의 포인터입니다. 연결된 목록의 마지막 노드에 대한 포인터는 "null(보통 NULL로 표시됨)", 즉 널 포인터입니다.

연결된 목록에서 다양한 작업을 쉽게 구현하기 위해 단일 연결 목록의 첫 번째 데이터 노드 앞에 동일한 유형의 노드가 설정됩니다. 이 노드를 헤드 노드라고 합니다.

헤드 노드의 데이터 필드에는 연결 목록의 길이와 같은 특수 플래그 정보를 저장할 수 있거나 데이터를 저장할 수 없습니다.

링크드 리스트의 첫 번째 데이터 노드와 마지막 노드를 헤드 노드 및 테일 노드라고도 합니다.

2. 헤드 포인터와 헤드 노드의 유사점과 차이점

헤드 포인터:

• 헤드 포인터는 연결된 목록에 있는 첫 번째 노드를 가리키는 포인터를 나타냅니다. 헤드 노드, 이는 헤드 노드를 가리키는 포인터입니다.
• 헤드 포인터에는 식별 기능이 있으며, 헤드 포인터는 연결 리스트의 이름으로 자주 사용됩니다.
• 링크드 리스트가 비어 있든 없든 헤드 포인터는 비어 있지 않습니다. 헤드 포인터는 연결 리스트의 필수 요소입니다.

헤더 노드:

• 헤드 노드는 작업의 통일성과 편의를 위해 설정되며 첫 번째 요소의 노드 앞에 배치되며 해당 데이터 필드는 일반적으로 의도되지 않습니다.
• 헤드 노드를 사용하면 첫 번째 요소 노드 앞에 노드를 삽입하고 첫 번째 노드를 삭제하는 작업이 다른 노드의 작업과 통합됩니다.
• 헤드 노드가 반드시 연결 리스트의 필수 요소는 아닙니다.

3. 코드 데모

/*线性表的单链表存储结构*/
/*结点定义*/
typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;

/*单链表定义*/
typedef struct Node *LinkList;

3. 단일 연결 리스트의 연산

1. 삽입 연산

1) 삽입 시뮬레이션

요소 e를 저장하는 노드가 s라고 가정하고 ai 노드 뒤에 s를 삽입합니다.

생각하기: 삽입 코드의 두 문장을 바꿀 수 있나요?

아니요, 전환하면 s의 포인터 필드가 ai+1의 주소를 가리키지 않기 때문에 ai+1과 같은 후속 요소를 찾을 수 없습니다.

2) 단일 연결 리스트의 노드에 i번째 데이터를 삽입하는 알고리즘 아이디어

• 노드 p가 연결 리스트의 첫 번째 노드를 가리키도록 선언하고 j=1;
• j
• 연결된 목록의 끝에서 p가 비어 있으면 i번째 요소가 존재하지 않는다는 의미입니다. 검색이 성공하면 빈 노드 s가 생성됩니다(malloc 함수 사용)
• 데이터 요소 e를 s->data에 할당합니다. 즉, s->data=e;
• 에 대한 표준 문을 삽입합니다. s->next=p->next; p->next=s;
• 반품에 성공했습니다.

2. 삭제 연산

1) 삭제 시뮬레이션

요소 ai를 저장한 노드가 q이고, 단일 연결 리스트에서 노드 q를 삭제하는 연산을 구현한다고 가정합니다.

2) 단일 연결 리스트에서 i번째 데이터 노드를 삭제하는 알고리즘 아이디어

• 연결 리스트의 첫 번째 노드를 가리키는 노드 p를 선언하고, j=1;
• j<일 때 초기화합니다. ;i, traverse 연결된 리스트에서 p의 포인터가 뒤로 이동하여 계속해서 다음 노드인 j++를 가리키도록 합니다.
• 연결된 리스트의 끝에서 p가 비어 있으면 i번째 요소가 비어 있다는 의미입니다. 검색이 성공하면 노드 p-> q
• 다음에 할당합니다. 표준 문을 삽입합니다. p->next=q->next;
• q 노드를 e=로 할당합니다. q->data;
• q 노드를 해제하세요
• 성공을 반환합니다.

4. 단일 연결 리스트 구조와 순차 리스트 구조 비교

저장 방법:

• 순차 테이블은 연속 저장 장치를 사용하여 선형 리스트의 데이터 요소를 순차적으로 저장합니다.
• 단일 연결 리스트는 연결 저장 장치를 사용합니다. 임의의 저장 단위 그룹을 사용하여 선형 테이블 요소를 저장하는 구조

시간 성능:

①Lookup

• Sequential table O(1)
• Singly linked list O(n)

②삽입 및 삭제

• Sequential 테이블 O(n)
• 단일 연결 리스트 O(1)

공간 성능:

• 시퀀스 테이블은 미리 할당된 저장 공간이 필요하므로 크게 분할하면 낭비가 됩니다.
• 단일 연결 리스트는 미리 저장 공간을 할당할 필요가 없으며, 필요한 만큼 할당할 수 있으며, 요소 수에는 제한이 없습니다.

자세한 내용은 지식, FAQ 칼럼을 방문해 보세요!

위 내용은 연결된 목록은 어떤 저장 구조에 저장된 선형 목록입니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!