데이터 구조 - 링크 목록 (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;
newnode=new node(item,front);/ / 새 노드 의 next 지향 헤드 포인터
front=newnode;/ / 새 노드 를 헤드 포인터 로 만 들 기
- 어느 위치 에 꽂 기:
node *prev=NULL,*curr=front;
while(curr->nodevalue!=searchItem){
  prev=curr;
  curr=curr->next;
}
newnode->next=curr;
prev->next=newnode;
 
요소 삭제
- 헤더 삭제
node *curr=front;
front=front->next;
delete curr;
- 원소 삭제
node *prev=NULL,*curr=front;
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 }

좋은 웹페이지 즐겨찾기