C 언어 가 단일 체인 표 데이터 구 조 를 만 들 고 조작 하 는 인 스 턴 스 튜 토리 얼

1.체인 시 계 를 왜 사용 합 니까?
배열 은 같은 데 이 터 를 저장 하 는 집합 으로서 우리 에 게 프로그램 디자인 에 많은 편 의 를 가 져 다 주 고 유연성 을 높 였 다.그러나 수조 에 도 폐단 이 있다.만약 에 배열 의 크기 가 정 의 될 때 미리 규정 해 야 하고 프로그램 에서 조정 할 수 없다.그러면 프로그램 설계 에서 서로 다른 문제 에 대해 30 개의 크기 의 배열 이 필요 하고 50 개의 배열 의 크기 가 필요 하 며 통일 하기 어렵다.우 리 는 가능 한 최대 수요 에 따라 배열 을 정의 할 수 있 을 뿐 일정한 저장 공간의 낭 비 를 초래 할 수 있다.
우 리 는 동태 적 인 배열 을 구성 하여 수시로 배열 의 크기 를 조정 하여 서로 다른 문제 의 수 요 를 만족 시 킬 수 있 기 를 바란다.링크 는 우리 가 필요 로 하 는 동적 배열 이다.이것 은 프로그램의 실행 과정 에서 필요 에 따라 데이터 저장 이 있 으 면 시스템 에 저장 공간 을 신청 하 는 것 으로 저장 구역 에 대한 낭 비 는 결코 구성 되 지 않 는 다.
체인 테이블 은 복잡 한 데이터 구조 로 그 데이터 간 의 상호 관 계 는 체인 테이블 을 세 가지 로 나눈다.그것 이 바로 단일 체인 테이블,순환 체인 테이블,양 방향 체인 테이블 이다.다음은 하나씩 소개 할 것 이다.
2,단 방향 링크
단일 체인 시트 는 메모리 의 첫 번 째 주 소 를 가리 키 는 헤드 노드 헤드 가 있 습 니 다.링크 의 모든 노드 의 데이터 유형 은 구조 체 유형 이 고 노드 는 두 개의 구성원 이 있다.전체 구성원(실제 저장 해 야 할 데이터)과 다음 구조 체 유형 노드 를 가리 키 는 지침,즉 다음 노드 의 주소(사실은 이 단일 링크 는 전체 데 이 터 를 저장 하 는 동적 배열)이다.링크 는 이 구조 에 따라 각 노드 에 대한 방문 은 링크 의 머리 에서 찾 아야 하고 후속 노드 의 주 소 는 현재 노드 에서 제시 해 야 한다.표 에서 그 노드 를 방문 하 더 라 도 링크 의 머리 부터 순 서 를 뒤로 찾 아야 합 니 다.링크 의 끝 노드 는 후속 노드 가 없 기 때문에 포인터 필드 가 비어 있 고 NULL 로 쓰 입 니 다.
그림 에서 보 듯 이:

위의 그림 은 이러한 의 미 를 보 여 준다.링크 의 각 노드 가 메모리 에 저 장 된 주 소 는 연속 적 인 것 이 아니 라 각 노드 의 주 소 는 필요 할 때 시스템 에 분 배 를 신청 하 는 것 이다.시스템 은 메모리 의 현재 상황 에 따라 주 소 를 연속 으로 분배 할 수도 있 고 점프 식 으로 주 소 를 분배 할 수도 있다.
3.단 방향 링크 프로그램의 실현
(1)링크 노드 의 데이터 구조 정의

struct node 
{ 
  int num; 
  struct node *p; 
} ; 

링크 노드 의 정의 에서 하나의 정형 적 인 구성원 을 제외 하고 구성원 p 는 노드 유형 과 똑 같은 지침 을 가리킨다.
링크 노드 의 데이터 구조 에서 매우 특수 한 점 은 구조 체 내의 포인터 필드 의 데이터 형식 이 정의 되 지 않 은 성공 적 인 데이터 형식 을 사용 한 것 이다.이것 은 C 에서 먼저 사용 한 후에 정의 할 수 있 는 데이터 구 조 를 유일 하 게 규정 한 것 이다.
(2)링크 생 성,출력 절차
단일 체인 시트 의 생 성 과정 은 다음 과 같은 몇 단계 가 있 습 니 다.
1)링크 의 데이터 구 조 를 정의 합 니 다.
2)빈 테이블 만 들 기;
3)malloc()함 수 를 이용 하여 시스템 에 노드 를 분배 할 것 을 신청 합 니 다.
4)새 노드 의 포인터 구성원 을 빈 값 으로 지정 합 니 다.빈 시계 라면 새 노드 를 표 머리 에 연결 합 니 다.만약 빈 시계 가 아니라면,새로
노드 가 표 끝 을 받 습 니 다.
5)후속 노드 가 링크 에 접속 해 야 하 는 지 판단 하고 3 으로 이동 하면 끝 납 니 다.
단일 체인 시트 의 출력 과정 은 다음 과 같은 몇 단계 가 있다.
1)시계 머리 찾기;
2)빈 테이블 이 아니면 출력 노드 의 값 구성원 이 빈 테이블 이면 종료 합 니 다.
3)링크 의 증 가 를 추적 하면 다음 노드 의 주 소 를 찾 을 수 있다.
4)2 로 이동).
(3)프로그램 코드 예:
정수 단일 체인 표를 만 들 고 0 이하 의 수 를 입력 하 며 링크 를 만 들 고 링크 의 값 을 출력 합 니 다.프로그램 은 다음 과 같 습 니 다.

#include <stdlib.h> /* ma l l o c ( )     */ 
#include <stdio.h> 
 //①         
struct node 
{ 
  int num; 
  struct node *next; 
}; 
//     
struct node *creat();  
void print(); 
main( ) 
{ 
 
  struct node *head; 
  head=NULL;  //②      
  head=creat(head);/*     */ 
  print(head);/*     */ 
} 
/******************************************/  
struct node*creat(struct node *head)/*              */ 
{ 
  struct node*p1,*p2; 
  int i=1; 
//③  malloc ( )              
  p1=p2=(struct node*)malloc(sizeof(struct node));/*   */  
  printf("    ，     0  ，      ：p1_ADDR= %d
",p1); 
  scanf("%d",&p1->num);/*      */ 
  p1->next=NULL;/*          */ 
  while(p1->num>0)/*         0*/ 
  { 
//④             。    ，         ；     ，        ;  
    if(head==NULL) 
      head=p1;/*  ，    */ 
    else  
      p2->next=p1;/*   ，    */ 
    p2=p1; 
 
    p1=(struct node*)malloc(sizeof(struct node));/*      */ 
    i=i+1; 
    printf("    ，     0  ，      ：p%d_ADDR= %d
",i,p2); 
    scanf("%d",&p1->num);/*      */ 
//⑤                ，    3 )，    ;  
  } 
//==============        ：（  @daling_datou  ）================================ 
  free(p1); //       ，       
  p1=NULL;  //      
  p2->next = NULL; //    ，     
  printf("      （END）
");  
//============================================== 
  return head;/*        */ 
} 
/*******************************************/ 
void print(struct node*head)/*  head          */ 
{ 
  struct node *temp; 
  temp=head;/*        */ 
 
  printf("


       ：
"); 
  while(temp!=NULL)/*      */ 
  { 
    printf("%6d
",temp->num);/*        */ 
    temp=temp->next;/*      */ 
  } 
  printf("      !!"); 
} 

링크 를 만 드 는 과정 에서 링크 의 헤드 포인터 가 매우 중요 한 매개 변수 입 니 다.링크 에 대한 출력 과 검색 은 모두 링크 의 머리 에서 시작 해 야 하기 때문에 링크 를 만 든 후에 체인 헤더 노드 의 주소,즉 헤드 포인터 로 돌아 가 야 합 니 다.
프로그램 실행 절차:

4,단일 체인 테이블 작업 기초 예시

#include <stdio.h> 
#include <malloc.h> 
#define LEN sizeof(NODE) 
 
typedef struct _NODE//     
{ 
  int val; 
  struct _NODE* next; 
} NODE, *PNODE; 
 
void print(PNODE head){//       
  while (head) 
  { 
    printf("%3d",head->val); 
    head = head->next; 
  } 
  printf("
"); 
} 
 
void insertHead(PNODE *pHead, int val){//    
  PNODE n = (PNODE)malloc(LEN); 
  n->val = val; 
  n->next = *pHead; 
  *pHead = n; 
} 
 
void insertTail(PNODE *pHead, int val){//    
  PNODE t = *pHead; 
  PNODE n = (PNODE)malloc(LEN); 
  n->val = val; 
  n->next = NULL; 
  if (*pHead == NULL) 
  { 
    n->next = *pHead; 
    *pHead = n; 
  }else{ 
    while (t->next) 
    { 
      t = t->next; 
    } 
    t->next = n; 
  } 
} 
 
void deleteHead(PNODE *pHead){//    
  if (*pHead == NULL) 
  { 
    return; 
  } 
  else 
  { 
    PNODE t = *pHead; 
    *pHead = (*pHead)->next; 
    free(t); 
  } 
} 
 
void deleteTail(PNODE *pHead){//    
  PNODE t = *pHead; 
  if (t == NULL) 
  { 
    return; 
  } 
  else if (t->next == NULL) 
  { 
    free(t); 
    *pHead = NULL; 
  } 
  else{     
    while (t->next->next != NULL) 
    { 
      t = t->next; 
    } 
    free(t->next); 
    t->next = NULL; 
  } 
} 
 
PNODE findByVal(PNODE head, int val){//                
  while (head != NULL && head->val != val) 
  { 
    head = head->next; 
  } 
  return head; 
} 
 
PNODE findByIndex(PNODE head, int index){//        
  if (index == 1) 
  { 
    return head; 
  } 
  else 
  { 
    int c = 1; 
    while (head != NULL && index != c) 
    { 
      head = head->next; 
      c++; 
    } 
  } 
  return head; 
} 
 
void insertByIndex(PNODE *pHead, int index, int val){//         
  if (index == 1) 
  { 
    insertHead(pHead, val); 
  } 
  else 
  { 
    PNODE t = findByIndex(*pHead,index - 1); 
    if (t == NULL) 
    { 
      return; 
    } 
    else 
    { 
      PNODE n = t->next; 
      t->next = (PNODE)malloc(LEN); 
      t->next->next = n; 
      t->next->val = val; 
    } 
  } 
} 
 
void deleteByIndex(PNODE *pHead, int index)//           
{ 
  if (index == 1) 
  { 
    deleteHead(pHead); 
  } 
  else 
  { 
    PNODE t= findByIndex(*pHead, index - 1); 
    if (t == NULL || t->next == NULL) 
    { 
      return; 
    }else{ 
      PNODE n = t->next->next; 
      free(t->next); 
      t->next = n; 
    } 
  } 
} 
 
void deleteByVal(PNODE *pHead, int val)//              
{ 
  if (*pHead == NULL)//       
  { 
    return; 
  } 
  else 
  { 
    if ((*pHead)->val == val)//       ，   
    { 
      deleteHead(pHead); 
    } 
    else 
    { 
      PNODE t = *pHead; 
      while (t->next != NULL && t->next->val != val)//  ， t next    next          
      { 
        t = t->next; 
      } 
      if (t->next)//  t              
      { 
        PNODE n = t->next->next;//        
        free(t->next); 
        t->next = n; 
      } 
    } 
  } 
} 
 
void clear(PNODE *pHead)//     
{ 
  while ((*pHead) != NULL) 
  { 
    deleteHead(pHead);//     
  } 
} 
 
void main() 
{ 
  PNODE head = NULL; 
 
  insertTail(&head,1); 
  deleteHead(&head); 
  insertTail(&head,2); 
  insertTail(&head,3); 
  insertTail(&head,4); 
  insertTail(&head,5); 
  insertTail(&head,6); 
 
  print(head); 
  insertByIndex(&head, 6, 9); 
  print(head); 
  //deleteByIndex(&head,3); 
  deleteByVal(&head, 2); 
  print(head); 
  clear(&head); 
  print(head); 
  insertByIndex(&head,1,12); 
  print(head); 
}