데이터 구조의 링크 정의 및 기본 작업 실현

지난 블 로그 에서 말 했 듯 이 데이터 구조의 선형 구조 에는 연속 적 인 저장 구조 와 분 산 된 저장 구조 가 있 는데 이번 에는 분 산 된 저장 구조 인 링크 의 작은 정 리 를 쓰 겠 습 니 다.
먼저 링크 의 정 의 를 말씀 드 리 겠 습 니 다. 링크 는 물리 적 저장 장치 에서 비 연속 적 이 고 비 순서 적 인 저장 구조 입 니 다. 링크 의 노드 간 은 지침 을 통 해 연결 되 고 모든 노드 는 하나의 전구 결점 과 하나의 후계 결점 만 있 습 니 다. 그 중에서 첫 번 째 노드 는 전구 결점 이 없고 꼬리 노드 는 후계 결점 이 없습니다.상술 한 서술 은 링크 에 대한 정 의 를 공동으로 구성 했다.
그 다음 에 링크 의 구 조 를 말 해 보 자. 링크 는 머리 노드 + 효과 적 인 노드 로 구성 되 는데 그 중에서 효과 적 인 노드 는 첫 번 째 노드, 일반 노드, 꼬리 노드 로 나 뉜 다.
두 결점: 체인 테이블 에서 유효한 결점 앞의 결점, 두 결점 은 실제 데 이 터 를 저장 하지 않 고 체인 테이블 에 대한 조작 을 편리 하 게 하기 위 한 것 이다.
머리 지침: 머리 결점 은 실제 적 인 의미 가 없고 체인 시계 에 대한 조작 을 편리 하 게 하기 위해 서 일 뿐 머리 지침 은 말 그대로 머리 결점 을 가리 키 는 지침 이다.우 리 는 헤드 포인터 가 가리 키 는 헤드 노드 의 포인터 도 메 인 을 통 해 링크 를 조작 합 니 다.
첫 번 째 노드: 링크 의 첫 번 째 효과 적 인 노드.
끝 점: 링크 의 마지막 효과 적 인 노드, 끝 점 의 지침 영역 이 비어 있 습 니 다.
링크 는 이미 공 부 를 마 쳤 습 니 다. 그러면 다음은 링크 의 구성 인 결점 을 말씀 드 리 겠 습 니 다.링크 는 분 산 된 저장 구조 이기 때문에 주 소 를 통 해 방문 해 야 합 니 다. 그러면 노드 에 다음 노드 의 주 소 를 저장 해 야 합 니 다.아니면 c 언어의 구조 체 를 사용 합 니까?

1 //       
2 typedef struct Node{
3     //   
4     int data;
5     //   
6     struct Node * pNext;
7 }NODE,*PNODE;

결점 정의 가 끝 난 후에 체인 테이블 을 구성 하 는 요소 가 생 겼 으 니 그 다음 에 체인 테이블 을 초기 화해 야 한다.(알고리즘 의 구체 적 인 해석 은 코드 주석 을 보십시오)

 1 /*
 2           
 3      ：        +      ，             
 4 */
 5 PNODE create_list(){
 6     int len;  //          
 7     int val;  //               
 8 
 9     PNODE pHead=(PNODE)malloc(sizeof(NODE));   //    PNODE     ，             （   ）
10     if(pHead==NULL){
11         printf("    ，    ！");
12         exit(-1);
13     }
14     PNODE pTail=pHead;   //    pTail  ，              （           ）
15     pTail->pNext=NULL;  //         ，              
16 
17     printf("            ：");
18     scanf("%d",&len);
19 
20     int i;  //      
21     for(i=0;i<len;i++){
22         printf("    %d     ：",i+1);
23         scanf("%d",&val);
24 
25         PNODE pNew=(PNODE)malloc(sizeof(NODE));  //        ，              
26         if(pNew==NULL){
27         printf("    ，    ！");
28         exit(-1);
29     }
30 
31         /*
32              ，              。
33                pTail   ，                      。
34         pTail->pNext=pNew;    ，                           ，                  
35         pNew->data=val;                     
36         pNew->pNext=NULL;           ，              
37         pTail=pNew;                  ，           ，                 ，                ？
38                  ， pTail        ，  ，pTail=pNew（       pNew     pTail）。  ，  pTail            ，
39                ，          。
40         */
41         pTail->pNext=pNew;
42         pNew->data=val;
43         pNew->pNext=NULL;   
44         pTail=pNew;
45     }
46     return pHead;  //         
47 }

링크 를 만 든 후에 링크 를 옮 겨 다 닐 수 있어 야 합 니 다. 사실은 링크 의 정의 에 따라 ok 입 니 다. 링크 의 모든 노드 에 다음 노드 의 주 소 를 저장 한 이상 링크 의 주 소 를 통 해 노드 를 찾 으 면 됩 니 다.긴 말 하지 않 고 바로 코드 를 올리다

 1 /*
 2        
 3 */
 4 void traverse_list(PNODE pHead){
 5     PNODE p=pHead->pNext;   //      p         ， p         
 6     while(p!=NULL){
 7         printf("%d  ",p->data);
 8         p=p->pNext;   //   p        
 9     }
10     printf("
");
11 }

 다음은 링크 정렬 에 대한 알고리즘 을 쓰 십시오. 여 기 는 가장 간단 한 알고리즘 (나중에 정렬 알고리즘 을 전문 적 으로 배 울 것 입 니 다) 만 사용 하고 상세 한 설명 은 모두 코드 에 있 습 니 다.

 1 /*
 2         
 3             ，                  ，      ，               ，
 4              ，        ，               ，    ，            。 
 5 */
 6 void sort_linst(PNODE pHead){
 7     PNODE p,q;  //    PNODE  ，               
 8     int val;  //  val  ，            
 9     int len=get_len(pHead);  //  len  ，          
10     int i,j;  //  i、j      ，                   “    ”  ，             
11     for(i=0,p=pHead->pNext;i<len-1;i++,p=p->pNext){        //           ，        ，      len-1  
12         for(j=i+1,q=p->pNext;j<len;j++,q=q->pNext){        //           ，        ，     len  
13             if(p->data>q->data){
14                 val=p->data;
15                 p->data=q->data;
16                 q->data=val;
17             }
18         }
19     } 
20 }

 물론 이런 데이터 저장 구 조 를 사용 하면 데이터 의 삽입 과 삭제 알고리즘 을 적지 않 게 사용 해 야 한다.

 1 /*
 2        
 3 */
 4 int insert_link(PNODE pHead,int pos, int val){
 5     int i=0;  //      ，          ，                   
 6     PNODE p=pHead;  //      PNODE   p    ，         
 7     while(p!=NULL&&i<pos-1){  //   p           
 8         p=p->pNext;
 9         i++;
10     } 
11     if(i>pos-1||p==NULL){
12         return 1; //1          
13     } 
14     
15     //         ，  p               ， pos          
16     //                       ，                
17     PNODE pNew=(PNODE)malloc(sizeof(NODE));
18     if(pNew==NULL){
19         printf("      ");
20         exit(-1);
21     }
22     pNew->data=val;
23      PNODE q=p->pNext;  //             
24     p->pNext=pNew;
25     pNew->pNext=q;
26     return 0;  //0         
27      
28 }
29 
30 /*
31        
32 */
33 int delete_link(PNODE pHead,int pos ,int *val){
34     int i=0;  //      ，          ，                   
35     PNODE p=pHead;  //      PNODE   p    ，         
36     while(p!=NULL&&i<pos-1){  //   p           
37         p=p->pNext;
38         i++;
39     } 
40     if(i>pos-1||p==NULL){
41         return 1; //1          
42     } 
43     
44     //                                            
45     PNODE q=p->pNext;  //   q       
46     *val=q->data; 
47     p->pNext=p->pNext->pNext;
48     free(q);
49     q=NULL;
50     return 0; //0         
51 }

실험 후, 사실 if (i > pos - 1 | p = = NULL) 부분의 통 제 를 잘 모 르 겠 습 니 다. 건장 성 이 매우 강 합 니 다. 왜 이렇게 건장 한 지 모 르 겠 습 니 다. 누가 보면 설명 을 해 주 셨 으 면 좋 겠 습 니 다. 여기 서 먼저 감 사 드 립 니 다.