데이터 구조 빠 른 회고 - 시작 선형 표

6 월 이 되다.일자 리 를 찾기 시작 하 는 리듬, IT 분야 의 지식 비축 이 심각하게 부족 하고 계획 을 세우 고 블 로 그 를 업데이트 하 며 자신의 준비 과정 을 기록 합 니 다.
1. 데이터 구조 15 일
2. 상용 알고리즘 (정렬, 동적 기획, 욕심 등) 30 일
3. 데이터 마 이 닝 알고리즘 15 일
4. 모 바 일, 웹 엔 드 개발 입문 15 일
5. 운영 체제 10 일
모두 85 일 이 었 다. 그 때 는 9 월 에 가 까 워 서 일자 리 를 찾 는 붐 을 만 날 수 있 었 다.
 
데이터 구 조 는 무엇 입 니까?데이터 구조 용도?
일반적으로 컴퓨터 로 한 문 제 를 해결 할 때 다음 과 같은 절 차 를 거 쳐 야 한다. 문 제 를 분석 하고 수학 모델 을 추상 화 하 며 수학 모델 을 디자인 하 는 알고리즘, 쓰기 프로그램, 테스트 를 통 해 최종 결 과 를 얻 을 수 있다.
비수 치형 수학 모델 을 해결 하기 위해 서 는 표, 나무, 그림 과 같은 데이터 구 조 를 사용 해 야 한다. 데이터 구 조 는 비수 치 계산 프로그램의 대상 을 더욱 잘 표현 하고 조작 하 는 데 도움 을 줄 수 있다.
정의: 데이터 구 조 는 서로 한 가지 또는 여러 가지 특정한 관계 가 존재 하 는 데이터 요소 의 집합 이다.
 
데이터 요소 간 의 관계 특징 에 따라 다음 과 같은 네 가지 기본 구조 로 나 뉜 다. 집합, 선형 구조 (링크), 나무 구조, 도형 구조 이다.
데이터 요소 가 컴퓨터 에서 의 저장 방식 에 따라 다음 과 같은 두 가지 구조 로 나 뉜 다. 순서 저장 구조 와 체인 저장 구조 이다.
 
본 편 은 주로 첫 번 째 데이터 구조 인 선형 표 선형 표 는 n 개의 데이터 요소 로 구 성 된 유한 한 서열 을 소개 한다.데이터 요소 의 내용 은 가 변 적 이다.
 
선형 표 의 순서 표시 및 실현:
순서 표 시 는 주소 연속 저장 소 를 사용 하여 선형 표를 순서대로 저장 하 는 데이터 요 소 를 말한다.

 1 //           
 2 #define OVERFLOW -2
 3 #define OK 1
 4 #define ERROR 0
 5 #define LIST_INIT_SIZE 100
 6 #define LISTINCREMENT 10 //               
 7 
 8 typedef int ElemType;  9 typedef int Status;  10 
 11 typedef struct
 12 {  13         ElemType *elem;//        
 14         int length;    //    
 15         int listsize;//     
 16 }SqList;  17 
 18 //      
 19 Status InitList_Sq(SqList &L)  20 {  21         L.elem = (ElemType*) malloc (LIST_INIT_SIZE * sizeof(ElemType));  22         if(!L.elem)  23  exit(OVERFLOW);  24         L.length = 0;  25         L.listsize = LIST_INIT_SIZE;  26         return OK;  27 }  28 
 29 //     
 30 void CreateList(SqList &L, int len)  31 {  32         if(len > LIST_INIT_SIZE)   //            ，      
 33  {  34                 L.elem = (ElemType*) realloc (L.elem, len*sizeof(ElemType));  35                 L.listsize = len;  36  }  37         printf("        : 
");  38         for(int i = 0; i < len; i++)  39                 scanf("%d", &L.elem[i]);  40         L.length = len;  41         printf("       :
");  42         for(int i = 0; i < len; i++)  43                 printf("%d ", L.elem[i]);  44         printf("
      %d    。
",L.length);  45 }  46 
 47 //   L  i           e
 48 Status ListInsert_Sq(SqList &L, int i, ElemType e)  49 {  50     if(i > L.length+1 || i<1)  51         return ERROR;  52     if(i > L.listsize)  53  {  54         newBase = (ElemType*)realloc(L.elem, (L.listsize+LISTINCREMENT）*sizeof（ElemType);  55         if(!newBase)  56  exit(OVERFLOW);  57         L.elem = newBase;  58         L.listsize += LISTINCREMENT;  59  }  60     ElemType *q,*p;  61     q = &(L.elem[i-1]);  62     for(p = &(L.elem[L.length-1]); p > q; --p)  63         *(p+1) = *p;  64     *q = e;  65     ++L.length;  66     return OK;  67 }  68 
 69 //     L  i   
 70 Status ListInsert_Sq(SqList &L, int i, ElemType& e)  71 {  72     if(i > L.length || i<1)  73         return ERROR;  74 
 75     ElemType *q,*p;  76     q = &(L.elem[i-1]);  77     e = *q;  78     p = &(L.elem[L.length-1]);  79     for(;  q < p ; ++p)  80         *q = *(q+1);  81 
 82     --L.length;  83     return OK;  84 }  85 //         
 86 ElemType GetElem(SqList &L, int i)  87 {  88         ElemType *e;  89         if(!L.elem || i > L.length || i < 1)  90  exit (ERROR);  91         e = L.elem+i-1;  92         return *e;  93 }  94 
 95 
 96 //      ，   ，             
 97 int LocateElem(SqList &L, ElemType e)  98 {  99         int i; 100         if(!L.elem) 101  exit (ERROR); 102         for(i = 0; i < L.length; i++) 103                 if(e == L.elem[i]) 104                         return i+1; 105         return 0; 106 }

 
선형 표 의 체인 표시 및 실현:
링크: 선형 표 의 데이터 요 소 를 주소 임 의 저장 장치 로 저장 합 니 다.결점 (데이터 요소 나 데이터 요 소 를 나타 내 는 이미지) = 요소 (데이터 요소 의 이미지) + 포인터 (후계 요소 저장 위 치 를 표시 합 니 다).
 

 1 typedef  struct LNode {  2     ElemType      data;  //     
 3     struct LNode   *next;  //     
 4 } LNode, *LinkList;  5 
 6 //   ，                
 7 Status InitList(LinkList &L){  8      L=(LinkList)malloc(sizeof(LNode)); //         
 9      L->next=NULL;  //            （           ）   
10      return OK; 11 } 12 
13 //   ，L            ，  e     i    
14 Status GetElem_L(LinkList L, int i, ElemType &e) { 15     ElemType* p= L->next; 16     int j = 1; 17 　　while (p && j<i) { 18 　　    p = p->next;  ++j; 19  } 20     if ( !p || j>i ) //   i        
21         return ERROR; 22     e = p->data;                 //     i     
23     return OK; 24 } 25 
26 //  i         e
27 Status ListInsert_L(LinkList L, int i, ElemType e) { 28      // L              ，
29      LinkList p = L; 30      int j = 0; 31      while (p && j < i-1) { 32             p = p->next;  ++j; //     i-1     
33  } 34       if (!p || j > i-1) 35          return ERROR;      // i         1 
36       s = (LinkList) malloc ( sizeof (LNode));  //       
37       s->data = e; 38       s->next = p->next;      p->next = s; 39       return OK; 40  } 41 Status ListDelete_L(LinkList L, int i, ElemType &e) { 42 //     L     (    )       i     
43     LinkList p = L; 44     int j = 0; 45     while(p && j < i-1) 46  { 47         p = p->next; 48         j++; 49  } 50     
51     if(!(p->next) || j >=i) 52         return ERROR; 53         
54     LinkList q = p->next; 55     p->next = q->next; 56     e = q->data; free(q); 57     return OK; 58 } 59 
60 void ClearList(&L) { 61    //              
62     while (L->next) { 63         p=L->next;    L->next=p->next; 64  free（p）; 65  } 66 } 67 
68 //    
69 void CreateList_L(LinkList &L, int n) { 70        //      n      ，           
71        L = (LinkList) malloc (sizeof (LNode)); 72        L->next = NULL;    //               
73        for (i = n; i > 0; --i) { 74          p = (LinkList) malloc (sizeof (LNode)); 75          scanf(&p->data);    //       
76          p->next = L->next; L->next = p;  //    
77  } 78 } // CreateList_L