데이터 구조 - 선형 표 의 정적 / 동적 분배 와 순서 / 체인 저장

10177 단어
선형 표 - 엄 위 민 판 데이터 구조 c 언어 실현 - 담 호 강 판 c 언어
데이터 요소 가 컴퓨터 에 저장 되 는 것 은 순서 저장 과 체인 저장 으로 나 뉜 다.
순서 저장: 요소 가 메모리 에 있 는 상대 적 인 위 치 를 통 해 데이터 요소 간 의 논리 적 관 계 를 나타 낸다.
체인 저장: 지시 요소 저장 주소 의 지침 을 통 해 데이터 요소 간 의 논리 적 관 계 를 나타 낸다.
ps: 담 호 강 판 c 언어 는 8.8 메모리 의 동적 배분 과 정적 배분 과 관련된다.
동적 분배: 데이터 저장 용량 이 고정 되 지 않 음 (담 호 강: 8.8P 285 동적 분 배 는 필요 할 때 수시로 열 리 고 필요 하지 않 을 때 수시로 방출)
구 글 검색 동적 분배 의 연속 저장 소: (64 페이지) 프로 그래 밍 언어 를 통 해 제공 하 는 동적 저장 기능 을 통 해 지 정 된 크기 의 연속 공간 을 신청 합 니 다.
정적 분배: 데이터 저장 용량 고정
구 글 검색 정적 분배 의 연속 저장 소: (64 페이지) 프로 그래 밍 언어 가 제공 하 는 구조 류 데이터 유형 - 배열 (순서 표)
ps: 엄 위 민 판 장 절 은 순서 표 와 링크 의 실현 으로 나 뉘 는데 동태 적 으로 분 배 된 순서 저장 만 있 고 정태 적 으로 분 배 된 순서 저장 이 없다. 그러나 저 는 코드 실현 은 순서 표 와 선형 표 의 실현 에 국한 되 지 않 을 뿐만 아니 라 네 가지 로 나 누 어야 한다 고 생각 합 니 다. 동태 적 으로 분 배 된 순서 저장, 정태 적 으로 분 배 된 순서 저장, 동태 적 으로 분 배 된 체인 저장,정적 분배 의 체인 식 저장 소 이 고 순서 표 와 체인 표 의 구분 은 순서 저장 소 와 체인 식 저장 소의 구분 과 같 지 않 기 때문에 본 편 은 정적 분배 와 동적 분 배 를 바탕 으로 하 는 순서 저장 소 와 체인 식 저장 소 를 소개 한다.
선형 표 는 동적 분 배 를 바탕 으로 하 는 순서 저장 구조 인 엄 위 민 (사본 원문 p22)
(실현 방법: 구조 체 구성원 표 열 은 포인터 와 동적 으로 배열 을 엽 니 다)https://www.cnblogs.com/Romi/archive/2012/01/07/2315788.html
1. 순서 표 구조
순서 표 구조 전에 다음 과 같은 매크로 정의 와 변 수 를 교체 하여 코드 의 이 해 를 편리 하 게 합 니 다.
1 2 3 4 5 6 7 8 9 10 11 12 13 #define TRUE 1 #define FALSE 0 #define OK 1 #define ok 1 #define ERROR 0 #define error 0 #define INFEASIBLE -1   #define LIST_INIT_SIZE 100; #define LISTINCREMENT 10;   typedef   int   ElemType; typedef   int   Status;
구조 체 로 하나의 순서 표를 구성 하고 순서 표 의 주소, 길이, 저장 용량 의 표 시 를 정의 하 며 코드 는 다음 과 같다.
1 2 3 4 5 typedef   struct {      ElemType *elem;   // ,      int   length;       // ( )      int   listsize;     // }SqList;
 
2. 순서 표 초기 화
다음은 이 순서 표를 초기 화하 고 순서 표 에 미리 정 의 된 크기 의 배열 공간 을 분배 하 며 현재 순서 표 의 길 이 를 0 으로 설정 합 니 다. 만약 에 요소 의 개수 가 분 배 된 저장 용량 보다 크 면 용량 을 확장 합 니 다 (초기 화 시 확장 하지 않 고 순서 표 사용 중 필요 에 따라 용량 을 확장 합 니 다).코드 는 다음 과 같 습 니 다:
1 2 3 4 5 6 7 8 9 10 11 12 Status InitList(SqList *L) {      (*L).elem=(ElemType*) malloc (100* sizeof (ElemType));      // LIST_INIT_SIZE, 100, realloc ?      if ((*L).elem==NULL)      {          exit (OVERFLOW);      }      (*L).length=0;      (*L).listsize=LIST_INIT_SIZE;      return   ok; }
선형 표 는 정적 분 배 를 바탕 으로 하 는 순서 저장 구조 -
(실현 방법 1: 구조 체 구성원 표 열 은 정적 배열 로) 참고 만 합 니 다.https://www.cnblogs.com/newwy/archive/2010/10/10/1847449.html
https://blog.csdn.net/zwj1452267376/article/details/85011271
정적 할당 메모리:
const int Maxsize = 100;//표 의 최대 길 이 를 정의 합 니 다.  //ElemType 은 저장 요소 의 형식 type: def struct {를 표시 합 니 다.    ElemType data [MaxSize]; / 순서 표 의 요소      int length; / 순서 표 의 현재 길이  }Sqlist; 
(실현 방법 2: 엄 위 민 (정태 링크 는 원문 p31 참조) 분쟁 처리:https://ask.csdn.net/questions/274643?ops_request_misc=%7B%22request_id%22%3A%22158195017719725256734898%22%2C%22scm%22%3A%2220140713.130063897..%22%7D&request_id=158195017719725256734898&biz_id=4&utm_source=distribute.pc_search_result.none-task
StaticLinkList.h
#ifndef _STATIC_LINK_LIST_H_ #define _STATIC_LINK_LIST_H_ #define MAXSIZE 100
typedef enum {ERROR,OK}Status;
typedef struct{     int cur;     int data; }StaticLinkList[MAXSIZE];
선형 표 는 동적 분 배 를 바탕 으로 하 는 체인 식 저장 구조 인 엄 위 민 (사본 원문 p28)
(실현 방법 1: 구조 체 구성원 을 지침 으로 정의)
  • / / - 선형 표 의 단일 체인 표 저장 구조 -
  • typedef struct LNode {/ 사용자 정의 데이터 형식
  • ElemType data; / 데이터 필드
  • struct LNode * next; / 포인터 영역
  • } LNode, *LinkList ;

  • (실현 방법 2: 구조 체 구성원 을 지침 으로 정의)https://www.cnblogs.com/choon/p/3915706.html
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #define _CRT_SECURE_NO_DEPRECATE #define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1 #include #include /* , , , 。*/ struct   Student {      int   No; //      struct   Student *next; }; int   main() {      struct   Student *p1, *p2, *head;      int   n = 0;  //      head = NULL;      p1 = ( struct   Student *) malloc ( sizeof ( struct   Student));      printf ( " 1
    "
    );      scanf ( "%d" , &p1->No);      p2 = p1;  // ,p1 p2 1      while   (p1->No != 0)      {          n++;          if   (n == 1)          {              head = p1;          }          else          {              p2->next = p1;          }          p2 = p1; //p2          printf ( " , 0 :
    "
    );          p1 = ( struct   Student *) malloc ( sizeof ( struct   Student));          scanf ( "%d" , &p1->No);      };      p2->next = NULL; // ,p2->next NULL        //      struct   Student *p;      p = head;      while   (p != NULL)      {          printf ( "%d," , p->No);          p = p -> next;      }      printf ( "
    "
    );        system ( "pause" ); }
    선형 표 는 정적 분 배 를 바탕 으로 하 는 체인 식 저장 구조 인 담 호 강 (p310)
    (실현 방법: 구조 체 구성원 을 지침 으로 한다)
    https://www.cnblogs.com/choon/p/3915706.html
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #define _CRT_SECURE_NO_DEPRECATE #define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1 #include #include /* , , , “ ”。*/ struct   Student {      int   num;      float   score;      struct   Student *next; }; int   main() {      struct   Student stu1, stu2, stu3, *head, *p;      stu1.num = 1001; stu1.score = 80;  // stu1 num score      stu2.num = 1002; stu2.score = 85;  // stu2 num score      stu3.num = 1003; stu3.score = 90;  // stu3 num score        head = &stu1;       // 1 stu1      stu1.next = &stu2;  // stu2 stu1 next      stu2.next = &stu3;  // stu3 stu2 next      stu3.next = NULL;   //stu3 , next , NULL      p = head;           // p 1        //      do {          printf ( "%d,%f
    "
    , p->num, p->score);  // p          p = p->next;                          // p      while   (p != NULL);                      // p next NULL,        system ( "pause" ); }
     
     
     
     
     

    좋은 웹페이지 즐겨찾기