재 학 데이터 구조 001 ― 링크 기본 조작 과 일원 다항식 을 더 하 다.

1. 링크 의 기본 동작
링크 데이터 구조의 정의: 링크 는 한편 으로 는 노드 에 데 이 터 를 저장 해 야 하고 다른 한편 으로 는 '단서' 를 저장 해 야 하기 때문에 구조 체 로 링크 노드 데이터 유형 을 정의 한다.


  
  
  
  
   
   
   
   struct Node; 
   
   
   
   typedef struct Node *PtrToNode; 
   
   
   
   typedef PtrToNode List; 
   
   
   
   typedef PtrToNode Position; 
   
   
   
   typedef int ElementType; 
   
   
   
   struct Node  
   
   
   
   { 
   
   
   
       ElementType Element; 
   
   
   
       Position Next; 
   
   
   
   };

링크 의 조작 이 그리 많 지 않 습 니 다. 다음은 자주 사용 하 는 조작 입 니 다.


  
  
  
  
   
   
   
   //     
   
   
   
   List CreateList(); 
   
   
   
   //     
   
   
   
   void TraverseList(List L); 
   
   
   
   //     
   
   
   
   List MakeEmpty(List L); 
   
   
   
   //           
   
   
   
   int IsEmpty(List L); 
   
   
   
   //               
   
   
   
   int IsLast(Position P, List L); 
   
   
   
   //             。 
   
   
   
   //              ，      NULL 
   
   
   
   Position Find(ElementType X, List L); 
   
   
   
   //           
   
   
   
   void Delete(ElementType X, List L); 
   
   
   
   //                  
   
   
   
   Position FindPrevious(ElementType X, List L); 
   
   
   
   //               
   
   
   
   void Insert(ElementType X, List L, Position P); 
   
   
   
   //     
   
   
   
   void DeleteList(List L); 
   
   
   
   //         
   
   
   
   Position Header(List L); 
   
   
   
   //              
   
   
   
   Position First(List L); 
   
   
   
   //             
   
   
   
   Position Advance(Position P); 
   
   
   
   //           
   
   
   
   ElementType Retrive(Position P);

다음은 기본 조작 과 간단 한 사용 을 실현 하 는 완전한 예 이다.


  
  
  
  
   
   
   
   #include <stdio.h> 
   
   
   
   #include <stdlib.h> 
   
   
   
    
   
   
   
   struct Node; 
   
   
   
   typedef struct Node *PtrToNode; 
   
   
   
   typedef PtrToNode List; 
   
   
   
   typedef PtrToNode Position; 
   
   
   
   typedef int ElementType; 
   
   
   
   struct Node  
   
   
   
   { 
   
   
   
       ElementType Element; 
   
   
   
       Position Next; 
   
   
   
   }; 
   
   
   
    
   
   
   
   //     
   
   
   
   List CreateList(); 
   
   
   
   //     
   
   
   
   void TraverseList(List L); 
   
   
   
   //     
   
   
   
   List MakeEmpty(List L); 
   
   
   
   //           
   
   
   
   int IsEmpty(List L); 
   
   
   
   //               
   
   
   
   int IsLast(Position P, List L); 
   
   
   
   //             。 
   
   
   
   //              ，      NULL 
   
   
   
   Position Find(ElementType X, List L); 
   
   
   
   //           
   
   
   
   void Delete(ElementType X, List L); 
   
   
   
   //                  
   
   
   
   Position FindPrevious(ElementType X, List L); 
   
   
   
   //               
   
   
   
   void Insert(ElementType X, List L, Position P); 
   
   
   
   //     
   
   
   
   void DeleteList(List L); 
   
   
   
   //         
   
   
   
   Position Header(List L); 
   
   
   
   //              
   
   
   
   Position First(List L); 
   
   
   
   //             
   
   
   
   Position Advance(Position P); 
   
   
   
   //           
   
   
   
   ElementType Retrive(Position P); 
   
   
   
    
   
   
   
   int IsEmpty(List L) 
   
   
   
   { 
   
   
   
        
   
   
   
       return L->Next == NULL; 
   
   
   
   } 
   
   
   
    
   
   
   
   int IsLast(Position P, List L) 
   
   
   
   { 
   
   
   
       return P->Next == NULL; 
   
   
   
   } 
   
   
   
    
   
   
   
   Position Find(ElementType X, List L) 
   
   
   
   { 
   
   
   
       Position P = L->Next; 
   
   
   
       while(P != NULL && P->Element != X) 
   
   
   
       { 
   
   
   
           P = P->Next; 
   
   
   
       } 
   
   
   
       return P; 
   
   
   
   } 
   
   
   
    
   
   
   
   void Delete(ElementType X, List L) 
   
   
   
   { 
   
   
   
       Position P,TmpCell; 
   
   
   
       P = FindPrevious(X,L);   
   
   
   
       if(!IsLast(P,L)) 
   
   
   
       { 
   
   
   
           TmpCell = P->Next; 
   
   
   
           P->Next = TmpCell->Next; 
   
   
   
           free(TmpCell); 
   
   
   
       } 
   
   
   
   } 
   
   
   
    
   
   
   
   Position FindPrevious(ElementType X, List L) 
   
   
   
   { 
   
   
   
       Position P = L; 
   
   
   
       while(P->Next != NULL && P->Next->Element != X) 
   
   
   
       { 
   
   
   
           P = P->Next; 
   
   
   
       } 
   
   
   
       return P; 
   
   
   
   } 
   
   
   
    
   
   
   
   void Insert(ElementType X, List L, Position P) 
   
   
   
   { 
   
   
   
       Position TmpCell; 
   
   
   
       TmpCell = malloc(sizeof(struct Node)); 
   
   
   
       if(TmpCell == NULL) 
   
   
   
       { 
   
   
   
           printf("Out of space!
"); 
   
   
   
           return; 
   
   
   
       } 
   
   
   
       TmpCell->Element = X; 
   
   
   
       TmpCell->Next = P->Next; 
   
   
   
       P->Next = TmpCell; 
   
   
   
   } 
   
   
   
    
   
   
   
   void DeleteList(List L) 
   
   
   
   { 
   
   
   
       Position P,Tmp; 
   
   
   
       P = L->Next; 
   
   
   
       L->Next = NULL; 
   
   
   
       while(P != NULL) 
   
   
   
       { 
   
   
   
           Tmp = P->Next; 
   
   
   
           free(P); 
   
   
   
           P = Tmp; 
   
   
   
       } 
   
   
   
   } 
   
   
   
    
   
   
   
   Position Header(List L) 
   
   
   
   { 
   
   
   
       return L; 
   
   
   
   } 
   
   
   
    
   
   
   
   Position First(List L) 
   
   
   
   { 
   
   
   
       return L->Next; 
   
   
   
   } 
   
   
   
    
   
   
   
   Position Advance(Position P) 
   
   
   
   { 
   
   
   
       return P->Next; 
   
   
   
   } 
   
   
   
    
   
   
   
   ElementType Retrive(Position P) 
   
   
   
   { 
   
   
   
       return P->Element; 
   
   
   
   } 
   
   
   
    
   
   
   
   List CreateList() 
   
   
   
   { 
   
   
   
       int i; 
   
   
   
       Position P,Tmp; 
   
   
   
       List L = malloc(sizeof(struct Node)); 
   
   
   
       P = L; 
   
   
   
       for(i = 0; i < 5; i++) 
   
   
   
       { 
   
   
   
           Tmp = malloc(sizeof(struct Node)); 
   
   
   
           Tmp->Element = i; 
   
   
   
           P->Next = Tmp; 
   
   
   
           P = Tmp;         
   
   
   
       } 
   
   
   
       P->Next = NULL; 
   
   
   
       return L; 
   
   
   
   } 
   
   
   
    
   
   
   
   void TraverseList(List L) 
   
   
   
   { 
   
   
   
       Position P; 
   
   
   
       P = L->Next; 
   
   
   
       while(P != NULL) 
   
   
   
       { 
   
   
   
           printf("%d
",P->Element);   
   
   
   
           P = P->Next; 
   
   
   
       } 
   
   
   
   } 
   
   
   
    
   
   
   
   int main(void) 
   
   
   
   { 
   
   
   
       //     
   
   
   
       List L = CreateList(); 
   
   
   
       //    1        
   
   
   
       Position P = Find(1,L); 
   
   
   
       //   1      8 
   
   
   
       Insert(8,L,P); 
   
   
   
       //    8     
   
   
   
       P = FindPrevious(8,L); 
   
   
   
       //     
   
   
   
       TraverseList(L); 
   
   
   
       return 0; 
   
   
   
   }

2. 일원 N 차 다항식 더하기
두 개의 1 원 다항식 에 대해 그들 에 게 여러 가지 조작 을 해 야 한다 면 흔히 볼 수 있 는 두 가지 사고방식 은 다음 과 같다. (1) 한 개의 다항식 에 대해 가장 높 은 횟수 인 하 이 파 우 더 를 보존 하고 이 다항식 의 대응 횟수 는 각각 0 - 하 이 파 우 더 의 각 계수 의 수조 () 이다.(2) 다항식 중 계수 가 0 이 아 닌 모든 항목 은 그 계수 와 이 항목 의 횟수 를 보존한다.다음은 이 두 가지 사고방식 으로 일원 다항식 덧셈 조작 을 실현 한다.
사고방식 1:
데이터 구조 정의:


  
  
  
  
   
   
   
   typedef struct Poly 
   
   
   
   { 
   
   
   
       int CoeffArray[11]; 
   
   
   
       int HighPower; 
   
   
   
   } *Polynomial;

구현 코드:


  
  
  
  
   
   
   
   #include <stdio.h> 
   
   
   
   #include <stdlib.h> 
   
   
   
    
   
   
   
   typedef struct Poly 
   
   
   
   { 
   
   
   
       int CoeffArray[11]; 
   
   
   
       int HighPower; 
   
   
   
   } *Polynomial; 
   
   
   
    
   
   
   
   void ZeroPolynomial(Polynomial Poly) 
   
   
   
   { 
   
   
   
       int i; 
   
   
   
       for(i = 0; i < 11; i++) 
   
   
   
       { 
   
   
   
           Poly->CoeffArray[i] = 0; 
   
   
   
       } 
   
   
   
       Poly->HighPower = 0; 
   
   
   
   } 
   
   
   
    
   
   
   
   void AddPolynomial(Polynomial Poly1,Polynomial Poly2, Polynomial PolySum) 
   
   
   
   { 
   
   
   
       int i; 
   
   
   
       ZeroPolynomial(PolySum); 
   
   
   
       PolySum->HighPower = Poly1->HighPower > Poly2->HighPower? 
   
   
   
           Poly1->HighPower:Poly2->HighPower; 
   
   
   
       for(i = PolySum->HighPower; i >= 0 ; i--) 
   
   
   
       { 
   
   
   
           PolySum->CoeffArray[i] = Poly1->CoeffArray[i] + Poly2->CoeffArray[i]; 
   
   
   
       } 
   
   
   
   } 
   
   
   
    
   
   
   
   int main(void) 
   
   
   
   { 
   
   
   
       int i,j,k; 
   
   
   
       Polynomial P1,P2,Sum; 
   
   
   
       P1 = malloc(sizeof(struct Poly)); 
   
   
   
       P2 = malloc(sizeof(struct Poly)); 
   
   
   
       Sum = malloc(sizeof(struct Poly)); 
   
   
   
       //    
   
   
   
       ZeroPolynomial(P1); 
   
   
   
       ZeroPolynomial(P2); 
   
   
   
       P1->HighPower = 10; 
   
   
   
       for(i = 10; i >= 0; i--) 
   
   
   
       { 
   
   
   
           P1->CoeffArray[i] = i; 
   
   
   
       } 
   
   
   
        
   
   
   
       P2->HighPower = 8; 
   
   
   
       for(j = 8; j >=0; j--) 
   
   
   
       { 
   
   
   
           P2->CoeffArray[j] = j; 
   
   
   
       } 
   
   
   
       P2->CoeffArray[8] = 8; 
   
   
   
       AddPolynomial(P1,P2,Sum); 
   
   
   
    
   
   
   
       printf("The high power of the Polynomial is %d
",Sum->HighPower); 
   
   
   
       for(k = 0; k <= 10; k++) 
   
   
   
       { 
   
   
   
           printf("The Coeff of power %d is %d
",k,Sum->CoeffArray[k]); 
   
   
   
       } 
   
   
   
    
   
   
   
       return 0; 
   
   
   
   }

사고방식 2:
데이터 구조:


  
  
  
  
   
   
   
   typedef struct PolyNode *PtrToNode; 
   
   
   
    
   
   
   
   //      ，           ； 
   
   
   
   typedef struct PolyNode 
   
   
   
   { 
   
   
   
       int Coeff; 
   
   
   
       int Exponent; 
   
   
   
       PtrToNode Next; 
   
   
   
   } PolyNode;

구현 코드:


  
  
  
  
   
   
   
   #include <stdio.h> 
   
   
   
   #include <stdlib.h> 
   
   
   
    
   
   
   
   typedef struct PolyNode *PtrToNode; 
   
   
   
    
   
   
   
   //      ，           ； 
   
   
   
   typedef struct PolyNode 
   
   
   
   { 
   
   
   
       int Coeff; 
   
   
   
       int Exponent; 
   
   
   
       PtrToNode Next; 
   
   
   
   } PolyNode; 
   
   
   
    
   
   
   
    
   
   
   
   typedef PtrToNode Polynomial; 
   
   
   
    
   
   
   
   /************************************************************ 
   
   
   
   *        : 
   
   
   
   *P、Q              (    ) 
   
   
   
   *Sum               
   
   
   
   * 
   
   
   
   ************************************************************/ 
   
   
   
   void AddPolynomial(Polynomial P,Polynomial Q,Polynomial Sum) 
   
   
   
   { 
   
   
   
       Polynomial PIndex,QIndex,SumIndex; 
   
   
   
       PIndex = P->Next; 
   
   
   
       QIndex = Q->Next; 
   
   
   
       SumIndex = Sum; 
   
   
   
       while(!(PIndex == NULL && QIndex == NULL)) 
   
   
   
       { 
   
   
   
           if(PIndex==NULL) 
   
   
   
           { 
   
   
   
               SumIndex->Next = QIndex; 
   
   
   
               QIndex = QIndex->Next; 
   
   
   
               SumIndex = SumIndex->Next; 
   
   
   
           } 
   
   
   
           else if(QIndex == NULL) 
   
   
   
           { 
   
   
   
               SumIndex->Next = PIndex; 
   
   
   
               PIndex = PIndex->Next; 
   
   
   
               SumIndex = SumIndex->Next; 
   
   
   
           } 
   
   
   
           else 
   
   
   
           { 
   
   
   
               if(PIndex->Exponent > QIndex->Exponent) 
   
   
   
               { 
   
   
   
                   SumIndex->Next = PIndex; 
   
   
   
                   PIndex = PIndex->Next; 
   
   
   
                   SumIndex = SumIndex->Next; 
   
   
   
                   //continue     if       ，  Java 
   
   
   
                   //       
   
   
   
                   continue; 
   
   
   
               } 
   
   
   
               if(PIndex->Exponent == QIndex->Exponent) 
   
   
   
               { 
   
   
   
                   Polynomial PP = malloc(sizeof(struct PolyNode)); 
   
   
   
                   PP->Exponent = PIndex->Exponent; 
   
   
   
                   PP->Coeff = PIndex->Coeff + QIndex->Coeff; 
   
   
   
                   SumIndex->Next = PP; 
   
   
   
                   PIndex = PIndex->Next; 
   
   
   
                   QIndex = QIndex->Next; 
   
   
   
                   SumIndex = SumIndex->Next; 
   
   
   
                   continue; 
   
   
   
               } 
   
   
   
               if(PIndex->Exponent < QIndex->Exponent) 
   
   
   
               { 
   
   
   
                   SumIndex->Next = QIndex; 
   
   
   
                   QIndex = QIndex->Next; 
   
   
   
                   SumIndex = SumIndex->Next; 
   
   
   
                   continue; 
   
   
   
               } 
   
   
   
           } 
   
   
   
       } 
   
   
   
       SumIndex->Next = NULL; 
   
   
   
   } 
   
   
   
    
   
   
   
   /************************************************************ 
   
   
   
   *     (    )  : 
   
   
   
   *P：       
   
   
   
   *************************************************************/ 
   
   
   
   void TraversePolynomial(Polynomial P) 
   
   
   
   { 
   
   
   
       Polynomial Tmp = P->Next; 
   
   
   
       while(Tmp != NULL) 
   
   
   
       { 
   
   
   
           printf("Coeff is %d and Exponent is %d
",Tmp->Coeff,Tmp->Exponent); 
   
   
   
           Tmp = Tmp->Next; 
   
   
   
       } 
   
   
   
   } 
   
   
   
    
   
   
   
    
   
   
   
    
   
   
   
   int main(void) 
   
   
   
   { 
   
   
   
       Polynomial Poly1,Poly2,Poly3,Poly11,Poly22; 
   
   
   
       int i,j; 
   
   
   
       Poly1 = malloc(sizeof(struct PolyNode)); 
   
   
   
       Poly2 = malloc(sizeof(struct PolyNode)); 
   
   
   
       Poly3 = malloc(sizeof(struct PolyNode)); 
   
   
   
       Poly11 = Poly1; 
   
   
   
       Poly22 = Poly2; 
   
   
   
    
   
   
   
       //       ，                  
   
   
   
       for(i = 5;i >= 1;i--) 
   
   
   
       { 
   
   
   
           Polynomial Tmp  = malloc(sizeof(struct PolyNode)); 
   
   
   
           Tmp->Coeff = i; 
   
   
   
           Tmp->Exponent = i; 
   
   
   
           Poly11->Next = Tmp; 
   
   
   
           Poly11 = Poly11->Next; 
   
   
   
       } 
   
   
   
       Poly11->Next = NULL; 
   
   
   
       for(j = 11;j >= 3;j--) 
   
   
   
       { 
   
   
   
           Polynomial Tmp  = malloc(sizeof(struct PolyNode)); 
   
   
   
           Tmp->Coeff = j; 
   
   
   
           Tmp->Exponent = j; 
   
   
   
           Poly22->Next = Tmp; 
   
   
   
           Poly22 = Poly22->Next; 
   
   
   
       } 
   
   
   
       Poly22->Next = NULL; 
   
   
   
       TraversePolynomial(Poly1); 
   
   
   
       printf("*****************************************
"); 
   
   
   
       TraversePolynomial(Poly2); 
   
   
   
       AddPolynomial(Poly1,Poly2,Poly3); 
   
   
   
       printf("*****************************************
"); 
   
   
   
       TraversePolynomial(Poly3); 
   
   
   
       return 0; 
   
   
   
   }

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

하나의 단일 체인 테이블의 순환과 귀속 실현을 반전시키다

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

재 학 데이터 구조 001 ― 링크 기본 조작 과 일원 다항식 을 더 하 다.

좋은 웹페이지 즐겨찾기