데이터 구조 - 링크 목록 (linkedlist)
10751 단어 LinkedList
1. 단 방향 링크
2. 꼬리 포인터 가 달 린 단 방향 링크
3. 양 방향 순환 링크
이하 분류 하여 설명 한다
1. 단 방향 링크
기본 요소: * front / / 헤드 노드
* next / / 다음 노드
성명: node < T > * p;
초기 화: p = new node < T > (nodeValue, nextpointer);
간단 한 반복:
1 template <typename T>
2 void writeLinkedList(node<T> *front)
3 {
4 node<T> *curr;
5 curr=front;
6 while(curr!=NULL)
7 {
8 cout<<curr->nodeValue<<" ";
9 curr=curr->next;
10 }
11 }
요소 삽입
- 시계 머리 에 꽂 기:
node
newnode=new node
front=newnode;/ / 새 노드 를 헤드 포인터 로 만 들 기
- 어느 위치 에 꽂 기:
node
while(curr->nodevalue!=searchItem){
prev=curr;
curr=curr->next;
}
newnode->next=curr;
prev->next=newnode;
요소 삭제
- 헤더 삭제
node
front=front->next;
delete curr;
- 원소 삭제
node
while(curr->nodevalue!=searchItem){
prev=curr;
curr=curr->next;
}
prev->next=curr->next;
delete curr;
구체 적 인 코드 구현:
1 void eraseValue(node<T> *front,const T &target)
2 {
3 node<T>*curr=front,*prev=NULL;
4 bool FoundItem=false;
5 while(curr!=NULL && !FoundItem) //
6 {
7 if(curr->nodeValue==target)
8 {
9 if(prev==NULL) //
10 front=front->next;
11 else
12 prev->next=curr->next;
13 delete curr;
14 FoundItem=true;
15 }
16 else
17 {
18 prev=curr;
19 curr=curr->next;
20 }
21 }
22 }
2. 더 블 포인터 단 방향 링크
기본 요소: 단 방향 링크 를 바탕 으로
* back / / 꼬리 포인터
/ / 각종 조작 은 단 방향 링크 와 유사 하 며, 끝 에 데이터 와 끝 을 삽입 하여 삭제 합 니 다. 여 기 는 일일이 열거 하지 않 습 니 다.
3. 양 방향 순환 링크
헤더 (헤더):
prev 포인터 와 next 포인터 만 포함 되 어 있 습 니 다. data 가 없습니다.
dlinkedlist 클래스
1 class dnode
2 {
3 public:
4 T nodeValue;
5 dnode <T> *prev;
6 dnode <T> *next;
7 dnode(){
8 next=this;
9 prev=this;
10 // , nodeValue
11 }
12 dnode(const T & value):
13 nodeValue(value)
14 {
15 next=this;
16 prev=this;
17 }
18 dnode <T> *insert (dnode <T>*curr,const T&item)
19 {
20 dnode<T> *newNode,*prevNode;
21 newNode=new dnode<T>(item); //
22 prevNode=curr->prev;
23
24 newNode->prev=prevNode;
25 newNode->next=curr;
26 prevNode->next=newNode;
27 curr->prev=newNode;
28
29 return newNode;
30 }
31 void erase(dnode<T> *curr)
32 {
33 if(curr->next==curr)// list
34 return;
35
36 curr->prev->next=curr->next;
37 curr->next->prev=curr->prev;
38
39 delete curr;
40 }
41 void writeDlinkedlist(dnode<T> *header)//
42 {
43 dnode<T> *p=header->next;
44 while(p!=header)
45 {
46 cout<<p->nodeValue<<" ";
47 p=p->next;
48 }
49 }
50 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
알고리즘 체조 18단일 링크 목록과 정수 "k"가 인수로 전달됩니다. 리스트의 k요소씩 반전시키는 알고리즘 체조. k<=1이면 목록은 변경되지 않습니다. k >= n(n은 링크 목록 길이)이면 전체 링크 목록을 뒤집습니다. 다음은 k...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.