학 빈 학 데이터 구조 따라 (01) - 준비

데이터 구조 개요
정의.
우 리 는 어떻게 현실 에서 대량의 복잡 한 문 제 를 특정한 데이터 형식 과 특정한 저장 구 조 를 메 인 메모리 (메모리) 에 저장 하고 이 를 바탕 으로 특정한 기능 (예 를 들 어 특정한 요 소 를 찾 고 특정한 요 소 를 삭제 하 며 모든 요 소 를 정렬 하 는 것) 을 실현 하기 위해 해당 하 는 조작 을 수행 하 는 지 하 는 것 을 알고리즘 이 라 고 합 니 다.
특정한 데이터 형식 과 구 조 는 우리 가 소량의 데 이 터 를 저장 하면 배열 (연속) 을 사용 할 수 있다 는 것 을 말한다.만약 대량의 데 이 터 를 저장한다 면 우 리 는 반드시 체인 테이블 을 사용 해 야 한다.만약 에 우리 가 데이터 item 간 의 관 계 를 저장 해 야 한다 면 한 부서 의 상하 관계 와 같이 우 리 는 트 리 로 저장 해 야 한다.만약 에 우리 가 한 도시 의 지 도 를 보존 하려 면 우 리 는 그림 으로 보존 해 야 한다.책: 엄 울 민, 오위 민 (위 알고리즘)  고 일 범 (알고리즘 의 실현)
데이터 구조 = 개체 의 저장 + 개체 관계 의 저장
알고리즘 = 데 이 터 를 저장 하 는 동작
알고리즘
문제 풀이 방법 과 절차
계산법 의 표준 을 평가 하 다.
1. 시간 복잡 도
기계 가 실행 하 는 속도 가 다 르 기 때문에 실행 할 시간 이 아 닌 프로그램 이 실행 할 횟수 입 니 다.
2. 공간 복잡 도
알고리즘 실행 과정 에서 사용 할 최대 메모리
3. 난이도
4. 건장 성
데이터 구조의 위치
데이터 구 조 는 소프트웨어 에서 가장 핵심 적 인 과정 이다.
프로그램 = 데이터 저장 + 데이터 조작 + 컴퓨터 에서 실행 할 수 있 는 언어
예비 지식
포인터
포인터 의 중요성:
복잡 한 데이터 구 조 를 나타 낸다.  빠 른 전송 데이터 로 함수 가 하드웨어 에 직접 접근 할 수 있 는 지 를 되 돌려 줍 니 다.    배열 과 문자열 을 편리 하 게 사용 할 수 있 는 것 은 대상 언어 에서 인용 하 는 것 을 이해 하 는 기초 이다.
지침 은 C 언어의 영혼 이다
정의.
주소.
주 소 는 메모리 셀 의 번호 입 니 다.
0 에서 시 작 된 비 마이너스 정수.
범위: 0 -- FFFFFF [0 - 4G - 1]
포인터:
지침 은 주소, 주 소 는 지침.
포인터 변 수 는 메모리 단위 주 소 를 저장 하 는 변수 입 니 다.
지침 의 본질은 조작 이 제 한 된 비음 정수 이다

int * p; //p      , int *    p      int       
int i = 10;
int j;

p = &i;
*p = i; //     i = i;
j = *p; //     j = i;        ，    p  ，         *p，      p     。
printf("i = %d, j = %d, *p = %d
", i, j, *p);
	 
//p = 10;  //error

분류:
1. 기본 타 입의 포인터
int i=10; int *p = &i; //int * p 와 같 음;p = &i; 이 두 동작 을 자세히 설명 합 니 다. 1) p 는 i 의 주 소 를 저장 합 니 다. 그래서 우 리 는 p 는 i 2), p 와 i 는 완전히 다른 두 변 수 를 가리 키 고 그 중의 임 의 변수의 값 을 수정 하 며 다른 변수의 값 에 영향 을 주지 않 습 니 다. 3), p 는 i 를 가리 키 고 * p 는 i 변수 자체 입 니 다.더욱 형상 적 으로 말 하면 모든 * p 가 나타 난 곳 은 i 로 바 꿀 수 있 고 모든 i 가 나타 난 곳 은 * p 로 바 꿀 수 있 습 니 다. 정리: 1. 어떻게 하나의 포인터 변수 (p 로 가정) 가 특정한 일반 변수 (i 로 가정) 의 주 소 를 저장 하 는 지 우 리 는 'p 가 i 를 가리 키 지만 p 와 i 는 두 개의 서로 다른 변수 입 니 다. p 의 값 을 수정 하면 i 의 값 에 영향 을 주지 않 고 i 의 값 을 수정 하면 p 의 값 에 영향 을 주지 않 습 니 다. 2.* p 등가 i 또는 * p 는 i 와 어디서 든 교환 할 수 있 습 니 다. 3. 포인터 변수 가 일반 변 수 를 가리 키 면 * 포인터 변수 완전히 등가 이 일반 변수 주의: 포인터 변수 도 변수 입 니 다. 메모리 셀 의 내용 을 저장 할 수 없습니다. 메모리 셀 의 주소 만 저장 할 수 있 습 니 다. 일반 변 수 는 추가 할 수 없습니다. * 상수 와 표현 식 전에는 추가 할 수 없습니다.
어떻게 피 변조 함 수 를 통 해 메 인 함수 에서 일반 변수의 값 I 실제 매개 변 수 를 관련 변수 로 하 는 주소 II 형 참 을 이 변수의 유형 으로 하 는 포인터 변수 로 바 꿉 니까?
Ⅲ 호출 함수 에서 통과 *형 삼 변수 이름 의 방식 은 주 함수 관련 변수의 값 을 수정 할 수 있다

void f(int * p) //           *p   ,          ，       p,     int *
{
	*p = 100; //
}


int main(void)
{
	int i = 9;


	f(&i);
	printf("i = %d
", i);


	return 0;
}

2  포인터 와 배열 의 관계
포인터 와 1 차원 배열 이름
1 차원 배열 이름 은 포인터 상수 입 니 다. 1 차원 배열 의 첫 번 째 요소 의 주 소 를 저장 합 니 다. 그것 의 값 은 1 차원 배열 이름 이 가리 키 는 첫 번 째 요 소 를 바 꿀 수 없습니다.
아래 표 와 포인터 의 관계 a [i] < = > * (a + i) 포인터 변수의 이름 이 p 이 라 고 가정 하면 p + i 의 값 은 p + i * (p 가 가리 키 는 변수 가 차지 하 는 바이트 수) 포인터 변수의 연산 포인터 변 수 는 더 할 수 없고 곱 할 수 없습니다. 만약 에 두 포인터 변수 가 같은 배열 에 속 하면 포인터 변 수 를 상쇄 할 수 있 습 니 다.전 제 는 최종 결과 가 포인터 가 가리 키 는 범 위 를 초과 할 수 없다 는 것 이다. p + i 의 값 은 p + i * (p 가 가리 키 는 변수 가 차지 하 는 바이트 수) p - i 의 값 은 p - i * (p 가 가리 키 는 변수 가 차지 하 는 바이트 수) p + + 이다. <==> p+1
p--<==>   p-1

	int a[5] = {1,2,3,4,5};


	//a[3] == *(3+a);


	printf("%p
", a+1);
	printf("%p
", a+2);//        ，    ，          ，        4.
	printf("%d
", *a+3); //*a+3    a[0]+3

예 를 들 어 피 변조 함 수 를 통 해 메 인 함수 중 1 차원 배열 의 내용 을 어떻게 수정 하 는 지 [1 차원 배열 을 어떻게 정의 하 는 지] 두 매개 변 수 는 배열 의 첫 번 째 요 소 를 저장 하 는 지침 변 수 를 저장 합 니 다.
배열 요소 길 이 를 저장 하 는 정형 변수

void Show_Array(int * p, int len)
{
	int i = 0;


	for (i=0; i<len; ++i)
		printf("%d
", p[i]);


	//p[2] = -1;  //p[0] == *p   p[2] == *(p+2) == *(a+2) == a[2]
	//p[i]      a[i]
}


int main(void)
{
	int a[5] = {1,2,3,4,5};
	
	Show_Array(a, 5);  //a   &a[0], &a[0]    int *  


	//printf("%d
", a[2]);


	return 0;
}

	double * p;
	double x = 66.6;

	p = &x;  //x 8     1    8 , 1       

	double arr[3] = {1.1, 2.2, 3.3};
	double * q;

	q = &arr[0];
	printf("%p
", q);  //%p           
	q = &arr[1];
	printf("%p
", q); //      8

함수 로 실제 인삼 의 값 을 수정 하면 int * 형식 이라도 주 소 를 전송 할 수 있 습 니 다.

void f(int ** q);

int main(void)
{
	int i = 9;
	int * p = &i;// int  *p;  p = &i;

	printf("%p
", p);
	f(&p);//  p               ，            ，      ，      。
	printf("%p
", p);

	return 0;
}

void f(int ** q)
{
	*q = (int *)0xFFFFFFFF;
}

구조 체
왜 구조 체 가 나타 나 는가: 복잡 한 데 이 터 를 표시 하기 위해 일반적인 기본 유형 은 요 구 를 만족 시 킬 수 없다.
구조 체 란 무엇 입 니까? 사용자 정의 복합 데이터 형식 입 니 다.
구조 체 를 어떻게 사용 하 는가: 하 나 는 '.' 의 방식 이 고 하 나 는 지침 의 방식 이다.

struct Student
{	
	int sid;
	char name[200];
	int age;
}; //     

int main(void)
{
	struct Student st = {1000, "zhangsan", 20};
	printf("%d  %s  %d
", st.sid, st.name, st.age);

	st.sid = 99;
	//st.name = "lisi";  //error
	strcpy(st.name, "lisi");
	st.age = 22;
	printf("%d  %s  %d
", st.sid, st.name, st.age);

	//printf("%d %s %d
", st);  //error
	return 0;
}

struct Student
{	
	int sid;
	char name[200];
	int age;
}; //     


int main(void)
{
	struct Student st = {1000, "zhangsan", 20};
	//st.sid = 99;  //     


	struct Student * pst;
	pst = &st;
	pst->sid = 99;  //       pst->sid     (*pst).sid   (*pst).sid    st.sid,    pst->sid     st.sid


	return 0;
}

주의사항: 구조 체 는 가감 승제 할 수 없 지만 서로 값 을 부여 할 수 있 습 니 다.
전송 할 때 가장 좋 은 전송 지침: 주소, 변 수 를 전송 하지 않 는 것 이 좋 습 니 다. 변 수 는 많은 바이트 가 필요 할 수 있 기 때문에 지침 은 항상 네 개의 바이트 로 전 송 됩 니 다.

# include <stdio.h>
# include <string.h>

struct Student
{	
	int sid;
	char name[200];
	int age;
}; //     

void f(struct Student * pst);
void g(struct Student st);
void g2(struct Student *pst);

int main(void)
{
	struct Student st;  //   st      

	f(&st);
	g2(&st);

	//printf("%d %s %d
", st.sid, st.name, st.age);

	return 0;
}

//               
void g(struct Student st)
{
	printf("%d %s %d
", st.sid, st.name, st.age);	
}

void g2(struct Student *pst)
{
	printf("%d %s %d
", pst->sid, pst->name, pst->age);	
}

void f(struct Student * pst)
{
	(*pst).sid = 99;
	strcpy(pst->name, "zhangsan");
	pst->age = 22;
}

동적 메모리 할당 및 방출
동적 구조 1 차원 배열 가설 동적 구조 int 형 배열 int * p = (int *) malloc (int len);1. malloc 는 int 형의 인삼 만 있 습 니 다. 시스템 에 분 배 를 요구 하 는 바이트 수 2, malloc 함수 의 기능 은 시스템 len 개의 바이트 의 메모리 공간 을 요청 하 는 것 입 니 다. 분 배 를 요청 하면 첫 번 째 바이트 의 주 소 를 되 돌려 주 고 분배 가 성공 하지 못 하면 NULL 3, malloc 함수 로 돌아 갈 수 있 으 며 첫 번 째 바이트 의 주 소 를 되 돌려 줄 수 있 습 니 다.그래서 우 리 는 이 실제 적 인 의미 가 없 는 첫 번 째 바이트 의 주소 (속칭 건 주소) 를 실제 적 인 의미 가 있 는 주소 로 바 꿔 야 한다. 따라서 malloc 앞 에 (데이터 형식 *) 을 추가 하여 이 실제 적 인 의미 가 없 는 첫 번 째 바이트 의 주 소 를 해당 유형의 주소 로 바 꿔 야 한다.예 를 들 어 int * p = (int *) malloc (50);       시스템 에서 분 배 된 50 바이트 의 첫 번 째 바이트 주 소 를 int * 형 으로 바 꾸 는 것 을 나타 낸다.     주소, 더 정확히 말 하면 첫 번 째 바이트 의 주 소 를 네 바이트 의 주소 로 바 꾸 는 것 입 니 다.     샘플 p 는 첫 번 째 네 개의 바이트, p + 1 은 두 번 째 네 개의 바이트,     p + i 는 i + 1 개의 4 개의 바이트 를 가리킨다.p [0] 가 첫 번 째 원소, p [i] 가 첫 번 째 원소 입 니 다.     i + 1 개 원소 double * p = (double *) malloc (80);       시스템 에서 분 배 된 80 바이트 의 첫 번 째 바이트 주 소 를 double * 형 으로 바 꾸 는 것 을 나타 낸다.     주소, 더 정확히 말 하면 첫 번 째 바이트 의 주 소 를 8 개의 바이트 의 주소 로 바 꾸 는 것 입 니 다.     샘플 p 는 첫 번 째 8 개의 바이트, p + 1 은 두 번 째 8 개의 바이트,     p + i 는 i + 1 개의 8 개의 바이트 를 가리킨다.p [0] 가 첫 번 째 원소, p [i] 가 첫 번 째 원소 입 니 다.     i + 1 개의 요소 free (p) 는 p 자체 가 사용 하 는 메모리 대신 p 가 가리 키 는 메모 리 를 방출 합 니 다.
모듈 1: 선형 구조
연속 저장 소 [배열]
이산 저장 소 [링크]
선형 구조의 두 가지 흔 한 응용 창고
선형 구조의 두 가지 흔 한 응용 2 대기 열
주제: 귀속
1. 1 + 2 + 3 + 4 +... 100 의 합
2. 개 승 구하 기
3. 한 노 타
4. 미로 로
모듈 2: 비 선형 구조
나무.
그림.
모듈 3: 찾기 와 정렬
절반 으로 나누다
정렬:
거품 이 일다
끼어들다
선택 하 다.
빠 른 정렬
정렬
자바 용기 및 데이터 구조 지식 Iterator 인터페이스 Map 해시 표