선형 표 의 체인 식 저장 구조 학습 총화

3146 단어 데이터 구조
정의: n 개의 노드 가 하나의 링크 로 연결 되 는데 그것 이 바로 선형 표 의 체인 식 저장 구조 이다.
노드 (Node): 데이터 필드 와 포인터 필드 로 구성 되 고 전 자 는 데이터 요소 정 보 를 저장 하 며 후 자 는 후계 위치 정 보 를 저장 합 니 다.
public class ListNode {
      int data;
      ListNode next;
      ListNode(int x) 
      { 
          data = x; 
      }
}

헤드 포인터 와 헤드 노드: 링크 의 첫 번 째 노드 의 저장 위 치 를 헤드 포인터 라 고 합 니 다.체인 시계 가 비어 있 든 없 든 헤드 포인터 가 비어 있 지 않 습 니 다.헤드 포인터 는 링크 의 필수 요소 이다.단일 체인 표 의 첫 번 째 결점 앞 에 결점 을 하나 설치 하여 두 결점 이 라 고 한다.헤드 노드 의 데이터 필드 는 어떠한 정보 도 저장 하지 않 을 수 있 습 니 다.머리 결점 이 반드시 링크 의 필요 한 요소 가 아니다.
링크 i 번 째 데이터 가 져 오기 (노드 번 호 는 1 부터, 아래 와 같 음): 1. 하나의 노드 p 가 링크 의 첫 번 째 노드 를 가리 키 고 j 를 1 부터 초기 화 합 니 다.2 j 가 i 보다 작 으 면 체인 시 계 를 옮 겨 다 니 며 p 의 바늘 을 뒤로 이동 시 키 고 다음 노드 를 계속 가리 키 며 j 누적 1;3. 링크 끝 p 가 비어 있 으 면 i 번 째 요소 가 존재 하지 않 음 을 나타 낸다.4. 찾 는 데 성공 하면 결점 p 의 데 이 터 를 되 돌려 줍 니 다.5. 두 결점 이 있 으 면 j 를 0 부터 초기 화 합 니 다.
public static int get(ListNode head,int index){
        ListNode p=head;
        int j=1; //head      ,   j=1
        while(p!=null&&jreturn p==null?0:p.data;
    }

단일 링크 에 삽 입 된 표준 구문:
//   p     s
s.next=p.next;
p.next=s;

단일 링크 에서 삭 제 된 표준 구문:
//  p       
Node q=p.next;
p.next=q.next

주: i 번 째 결점 에 결점 을 추가 하거나 i 번 째 결점 을 삭제 하면 모두 i - 1 번 결점 을 찾 습 니 다. 즉, 상기 문장의 p 는 i - 1 번 결점 입 니 다.
단일 체인 시트 생 성
//  10   ,    1-10
//   
ListNode head=new ListNode(1);
ListNode cur=head;
for(int i=2;i<=n;i++){
    cur.next=new ListNode(i);
    cur=cur.next;
}
cur.next=null;
//   
ListNode head=new ListNode(1);
head.next=null;
ListNode cur=null;
for(int i=n;i>=2;i--){
    cur=new ListNode(i);
    cur.next=head.next;
    head.next=cur;
}

좋은 웹페이지 즐겨찾기