링크 ux 학습 총화 (데이터 구조)

학습 총화:
Liux 커 널 은 데이터 구조의 지식 을 많이 사용 합 니 다. Liux 는 C 언어 로 작 성 된 것 이지 만 그 안에 많은 내용 이 대상 을 대상 으로 하 는 사상 입 니 다.그래서 데이터 구조의 지식 은 매우 기초 적 이 고 중요 하 다.
데이터 구 조 는 데이터 의 논리 구조 와 저장 구조 와 그 조작 을 말한다.

데이터 의 논리 구조

선형 구조      :1. 선형 표 2. 스 택 3. 대기 열
비 선형 구조   :1. 순차 저장 2. 도형 구조

데이터 의 저장 구조

순차 기억 장치
체인 메모리

데이터 의 연산: 검색, 정렬, 삽입, 삭제, 수정 등

먼저 선형 표를 작성 하 는 작업.나중에 혼자 봐.
순서 저장 구조: (사실 함수 의 반환 값 은 반드시 판단 해 야 합 니 다. 그러면 비교적 완벽 합 니 다. Liux 커 널 의 함 수 는 보통 반환 값 이 있 습 니 다. 일반적인 경우 오류 반환 - 1, 정확 한 것 은 판단 만 한다 면.
0 을 되 돌려 줍 니 다. 그래서 제 가 정의 한 함수 도 이 규칙 에 따라 야 한다 고 생각 합 니 다. 문 구 를 판단 하고 순환 문 뒤에 한 마디 만 있 으 면 {} 을 원 하지 않 는 것 이 좋 습 니 다. Liux 커 널 은 경찰 에 신고 합 니 다.)

#include <stdio.h>

#include <stdlib.h>

#define N 10

typedef int datatype;

typedef struct {

    datatype data[N];

    int last;

}sqlist;

sqlist * create_sqlist()

{

    sqlist *L;

    if((L = (sqlist *)malloc(sizeof(sqlist)))<0)

    {

        printf("malloc error!");

        return NULL;

    }

    L->last = -1;

    return L;

}

int insert(sqlist * L,datatype data,int i)

{

    int j;

    if((L->last >= N-1)||(i < 0)||(i > L->last+1))

        return -1;

    for(j = L->last+1;j>i;j--)

    {

        L->data[j-1] = L->data[j];

    }

    L->last++;

    L->data[i] = data;

    return 0;

}

int isempty(sqlist *L)

{

    return (L->last == -1) ;

}

int delete(sqlist *L,int i)

{

    int j;

    if((L->last == -1)||(i < 0)||(i > L->last))

        return -1;

    for(j = i; j<= L->last; j++)

    {

        L->data[j] = L->data[j+1];

    }

    L->last--;

    L->data[j+1] = 0;

    return 0;

}

int show(sqlist * L)

{

    int i;

    if(L->last ==-1)

    {

        printf("empty!
");

        return -1;

    }

    for(i = 0;i <= L->last;i++)

    {

        printf("data[%d] = %d
",i,L->data[i]);

    }

    return 0;

}

int main(int argc,char * argv[])

{

    int i;

    int ret;

    sqlist * L;

    L = create_sqlist();

    for(i = 0;i<10;i++)

    {

        ret = insert(L,i,i);

        if(ret == -1)

        {

            printf("insert error
");

            return -1;

        }

    }

    ret = show(L);

    if(ret == -1)

    printf("show error
");

    printf("****************
");

    ret = delete(L,4);

    if(ret == -1)

        printf("delete error
");

    ret = show(L);

    if(ret == -1)

        printf("show error
");



    return 0;

}

체인 메모리 구조:
#include #include #include #define N 10typedef int datatype;typedef struct node {
 datatype data; struct node * next;}linknode ,*linklist;
linklist create(){ linklist H; if((H = (linklist)malloc(sizeof(linknode)))==NULL) {  perror("malloc");  exit(-1); } H->next = NULL; printf("create"); return H;}int lenth(linklist H){ int i = 0; while((H->next)!=NULL) {  H = H->next;  i++; } return i;}int insert(linklist H,datatype data , int pos){ int i; linklist q; linklist p = NULL; p = H; if((pos<0)||(pos>lenth(H))) {  printf("insert error");  return -1; } if((q = (linklist)malloc(sizeof(linknode))) == NULL ) {  perror("malloc");  exit(-1); } for(i = 0; i< pos; i++) {  p=p->next; } q->data = data;  q->next = p->next; p->next = q; return 0;}int delete(linklist H,int pos){  int i; linklist p; p = H; if((pos<0)||(pos>lenth(H))) {  printf("delete error");  exit(-1); } for(i = 0;i < pos;i++)  H = H->next;  p = H->next;  H->next = p ->next;  free(p);   return 0;}int relist(linklist H){ linklist p,q; p = H->next; H ->next = NULL; while(p != NULL) {  q = p;  p = p->next;  q ->next = H->next;  H->next = q; }  
 return 0;}int show(linklist H){ linklist p; p = H; while((p->next)!=NULL) {  printf("data =%d",p->data);  p=p->next; } return 0;}int main(int argc,char * argv[]){ int i = 0; int ret; linklist H; H = create(); for(i = 0;i < 10;i++) { ret = insert(H,i,i); if(ret ==-1)  printf("insert error"); } printf("**********create linklist*************"); ret = show(H); if(ret == -1)  printf("show error"); printf("**********delete 3          *********"); ret = delete(H,3); if(ret == -1)  printf("delete error"); ret = show(H); printf("*********reservelist         ********"); ret = relist(H); if(ret == -1)  printf("reservelist error"); show(H); return 0;}
순서 저장 과 체인 저장 의 차이: 1. 논리 적 으로 인접 한 요소 에 순서대로 저장 되 고 그 저장 위치 도 인접 하 다.
2. 데이터 요소 에 대한 접근 을 무 작위 로 저장 하거나 주소 에 따라 접근 합 니 다.
3. 저장 밀도 가 높다
4. 표 의 삽입 과 요소 삭제 시간 이 복잡 하지 않 습 니 다.
5. 삽입 등 조작 연산 시간 이 걸 리 면 요소 의 이동 은 조각 으로 이동 해 야 합 니 다.