《 큰소리 데이터 구 조 》 를 읽다.
30660 단어 데이터 구조
1. 데이터 구조의 분류
논리 구조 에 따라 집합 구조: 데이터 요소 간 에는 아무런 관계 가 없다.선형 구조: 데이터 요소 간 의 일대일 관계;트 리 구조: 데이터 요소 간 은 한 쌍 이 많은 관계 입 니 다.도형 구조: 데이터 요소 간 은 다 중 관계 이다.
물리 구조 에 따라 데이터 의 논리 구조 가 컴퓨터 에 저장 되 는 형식 으로 나 뉜 다. 순서 저장 구조: 데이터 요 소 는 연속 적 인 주소 공간 에 저장 된다.체인 식 저장 구조: 데이터 요 소 는 임의의 저장 공간 에 두 고 체인 (보통 포인터) 을 통 해 연결 합 니 다.
2. 대 O 단계 로 올 리 는 방법:
1) 운행 시간의 모든 덧셈 상 수 를 상수 1 로 대체한다.2) 수 정 된 운행 횟수 함수 중 최고 단계 만 유지 합 니 다.3) 최고 단계 항목 이 1 이 아 닌 경우 이 곱 하기 상수 제거.
상용 시간 복잡 도의 크기 관계: O (1) < O (logn) < O (n) < O (nlogn) < O (n2) < O (n3) < O (2n) < O (n!) < O (nn)
3. 컴퓨터 가 사 칙 연산 을 어떻게 계산 하 는 지 (이 책 108 페이지)
접미사 표현 식 접미사 표현 식: 9 + (3 - 1) * 3 + 10 / 2 -- > 9 3 1 - 3 * + 102 / + 접미사 표현 식 의 계산 규칙: 왼쪽 에서 오른쪽으로 표현 식 의 모든 숫자 와 기 호 를 옮 겨 다 니 며 숫자 를 만나면 스 택 에 들 어가 고 기 호 를 만나면 스 택 꼭대기 에 있 는 두 개의 숫자 를 스 택 에서 꺼 내 연산 하고 운송 결 과 를 스 택 에 들 어가 최종 결 과 를 얻 을 때 까지 합 니 다.접미사 표현 식 을 접미사 표현 식 으로 변환 하 는 변환 규칙: 접미사 표현 식 의 모든 숫자 와 기 호 를 왼쪽 에서 오른쪽으로 옮 겨 다 니 며 숫자 라면 출력 합 니 다. 즉 접미사 표현 식 의 일부분 이 됩 니 다.만약 에 기호 라면 스 택 꼭대기 기호 와 의 우선 순 위 를 판단 하고 오른쪽 괄호 나 우선 순위 가 스 택 꼭대기 기호 (곱 하기 우선 가감) 보다 낮 으 면 스 택 꼭대기 요 소 를 순서대로 스 택 에서 나 와 출력 하고 현재 기 호 를 스 택 에 넣 어 최종 출력 접미사 표현 식 까지 합 니 다.
4. 이 진 트 리
1) 이 진 트 리 의 이 진 트 리 링크 의 노드 구조 정의
/* */
typedef struct BiTNode
{
TElemType data; /* */
struct BiTNode *lchild, *rchild; /* */
} BiTNode, *BiTree2) 앞 순 서 를 옮 겨 다 닌 다
옮 겨 다 니 기 규칙 은: 이 진 트 리 가 비어 있 으 면 빈 동작 으로 돌아 갑 니 다.그렇지 않 으 면 먼저 뿌리 노드 에 접근 한 다음 에 앞 순 서 는 왼쪽 트 리 를 옮 겨 다 니 고 앞 순 서 는 오른쪽 트 리 를 옮 겨 다 닌 다.코드 는 다음 과 같 습 니 다:
/* */
void PreOrderTraverse (BiTree T)
{
if (T == NULL)
return;
printf("%c,", T->data); /* ， */
PreOrderTraverse(T->lchild); /* */
PreOrderTraverse(T->rchild); /* */
}3) 중간 순서 로 옮 겨 다 니 기
옮 겨 다 니 는 규칙 은 이 진 트 리 가 비어 있 으 면 빈 동작 으로 돌아 가 는 것 입 니 다. 그렇지 않 으 면 결점 부터 시작 합 니 다.코드 는 다음 과 같 습 니 다:
/* */
void InOrderTraverse (BiTree T)
{
if (T == NULL)
return;
InOrderTraverse(T->lchild); /* */
printf("%c,", T->data); /* ， */
InOrderTraverse(T->rchild); /* */
}4) 후 순 옮 겨 다 니 기
옮 겨 다 니 는 규칙 은 이 진 트 리 가 비어 있 으 면 빈 동작 으로 되 돌아 가 는 것 입 니 다. 그렇지 않 으 면 왼쪽 에서 오른쪽으로 먼저 잎 을 낸 후에 점 을 찍 는 방식 으로 좌우 하위 트 리 를 옮 겨 다 니 며 마지막 으로 뿌리 노드 에 접근 합 니 다.코드 는 다음 과 같 습 니 다:
/* */
void PostOrderTraverse (BiTree T)
{
if (T == NULL)
return;
PostOrderTraverse (T->lchild); /* */
PostOrderTraverse (T->rchild); /* */
printf("%c,", T->data); /* ， */
}5. 순서 표 찾기
간단 한 알고리즘 코드 는 다음 과 같 습 니 다.
/* ，a ，n ， key */
int Sequential_Search (int *a, int n, int key)
{
int i;
for (i=1; i<=n; i++) /* i 1 ， 0 */
{
if (a[i] == key)
return i;
}
return 0;
}상기 코드 는 완벽 하지 않 습 니 다. 매번 순환 할 때마다 i 가 경 계 를 넘 었 는 지 판단 해 야 하기 때 문 입 니 다. 아래 코드 는 보초병 을 설정 하여 최적화 시 켜 야 합 니 다. 코드 는 다음 과 같 습 니 다.
/* */
int Sequential_Search2 (int *a, int n, int key)
{
int i;
a[0] = key; /* a[0] ， “ ” */
i = n;
while (a[i] != key)
i--;
return i;
}상기 코드 는 '보초병' 을 배열 의 첫 번 째 위치 에 놓 았 습 니 다. 물론 배열 의 끝 에 놓 을 수도 있 습 니 다. 이때 i 는 0 부터 시작 하여 while 순환 에서 i + + 로 데 이 터 를 이동 할 수 있 습 니 다.이런 기 교 는 총 데이터 가 비교적 많 을 때 효율 이 매우 높 아 질 것 이다.
6. 순서 표 찾기
1) 반절 찾기 (이분 찾기) 코드 는 다음 과 같다.
/* */
int Binary_Search(int *a, int n, int key)
{
int low, high, mid;
low=1; /* */
high=n;
while(low<=high)
{
mid = (low+high)/2; /* */
if ( key < a[mid] ) /* */
high = mid - 1;
else if ( key > a[mid] ) /* */
low = mid + 1;
else
return mid; /* mid */
}
return 0;
}
2) 플러그 인 찾기
반 으로 접어 서 그 반 으로 된 문장 을 찾 으 면 다음 문장 으로 바 꾸 면 됩 니 다.
mid = low + (high - low) * (key - a[low]) / (a[high] - a[low]); /* */메모: 플러그 인 검색 은 검색 할 키워드 key 와 검색 표 의 최대 최소 기록 키 워드 를 비교 한 검색 방법 입 니 다.표 의 길이 가 비교적 크 고 키워드 의 분포 가 고 른 검색 표 에 있어 플러그 인 검색 알고리즘 의 평균 성능 은 절반 으로 찾 는 것 보다 훨씬 좋다.
3) 피 보 나치 찾기 코드 는 다음 과 같다.
/* */
/* F = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... ...} ; */
/* */
int Fibonaci_Search(int *a, int n, int key)
{
int low, high, mid, i, k;
low = 1;
high = n;
k = 0;
while (n > F[k] - 1) /* n */
k++;
for (i=n; i<F[k]-1; i++) /* */
a[i] = a[n];
while(low <= high)
{
mid = low + F[k-1] - 1; /* */
if (key < a[mid])
{
high = mid -1;
k = k - 1; /* */
}
else if (key > a[mid])
{
low = mid + 1;
k = k - 2; /* */
}
else
{
if (mid <= n)
return mid;
else
return n; /* mid>n ， n */
}
}
return 0;
}피 보 나 치 는 검색 표 의 오른쪽 에 있 는 찾기 에 적합 한 기록 을 찾 으 면 왼쪽 데 이 터 는 판단 할 필요 가 없다.
[총 결] 절반 으로 찾 는 것 은 덧셈 과 나눗셈 연산 을 하 는 것 이다.플러그 인 찾기 는 복잡 한 사 칙 연산 을 하 는 것 입 니 다.피 보 나 치 는 간단 한 덧셈 연산 만 하고 대량의 데 이 터 를 찾 는 과정 에서 이런 미세한 차 이 는 최종 검색 효율 에 영향 을 줄 수 있다.
7. 이 진 트 리
1) 이 진 트 리 의 속성:
4. 567917. 만약 에 그의 왼쪽 나무 가 비어 있 지 않 으 면 왼쪽 나무 에 있 는 모든 노드 의 값 은 그의 뿌리 노드 의 값 보다 작다
4. 567917. 만약 에 그의 오른쪽 나무 가 비어 있 지 않 으 면 오른쪽 나무 에 있 는 모든 노드 의 값 은 그의 뿌리 노드 의 값 보다 크다
4. 567917. 그의 왼쪽, 오른쪽 나무 도 각각 이 진 트 리 이다
2) 두 갈래 정렬 트 리 찾기 동작
이 진 트 리 의 구 조 는 다음 과 같다.
typedef struct BiTNode
{
int data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;찾기 알고리즘 코드 는 다음 과 같 습 니 다:
/* T key */
/* f T ， NULL */
/* ， p ， TRUE */
/* p FALSE */
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{
if (!T) /* */
{
*p = f;
return FALSE;
}
else if (key == T->data) /* */
{
*p = T;
return TRUE;
}
else if (key < T->data)
return SearchBST(T->lchild, key, T, p);
else
return SearchBST(T->rchild, key, T, p);
}3) 두 갈래 정렬 트 리 의 삽입 동작
코드 는 다음 과 같 습 니 다:
/* T key ， */
/* key FALSE， FALSE */
Status InsertBST (BiTree *T, int key)
{
BiTree p, s;
if (!SearchBST(*T, key, NULL, &p)) /* */
{
s = (BiTree)malloc(sizeof(BiTNode));
s->data = key;
s->lchild = s->rchild = NULL;
if (!p)
*T = s;
else if (key < p->data)
p->lchild = s;
else
p->rchild = s;
return TRUE;
}
else
return FALSE; /* ， */
}4) 두 갈래 정렬 트 리 의 삭제 작업
결산 점 을 삭제 하려 면 세 가지 상황 으로 나 누 어야 합 니 다.
4. 567917. 잎 노드: 직접 삭제 하면 되 고 다른 결점 의 구 조 는 영향 을 받 지 않 습 니 다
4. 567917. 왼쪽 이나 오른쪽 나무의 결점 만 있 습 니 다. 결점 을 삭제 한 후에 왼쪽 나무 나 오른쪽 나 무 를 모두 결점 을 삭제 하 는 위치 로 이동 하면 됩 니 다
4. 567917. 좌우 서브 트 리 에 있 는 결점: 삭제 해 야 할 결점 p 의 직접 전구 (또는 직접 후계) s 를 찾 아 s 로 노드 p 를 교체 한 다음 에 이 결점 s 를 삭제 합 니 다
코드 는 다음 과 같 습 니 다:
/* T key ， ， */
/* TRUE； FALSE */
Status DeleteBST (BiTree *T, int key)
{
if (!*T)
return FALSE;
else
{
if (key == (*T)->data)
return Delete(T);
else if (key < (*T)->data)
return DeleteBST(&(*T)->lchild, key);
else
return DeleteBST(&(*T)->rchild, key);
}
}상기 코드 중의 Delete 함수 의 코드 는 다음 과 같다.
/* p， */
Status Delete(BiTree *p)
{
BiTree q,s;
if ( (*p)->rchild == NULL) /* */
{
q = *p;
*p = (*p)->lchild;
free(q);
}
else if ((*p)->lchild == NULL) /* */
{
q = *p;
*p = (*p)->rchild;
free(q);
}
else
{
q = *p;
s = (*p)->lchild; /* ， （ ） */
while (s->rchild)
{
q = s;
s = s->rchild;
}
(*p)->data = s->data; /* s */
if (q != *p)
q->rchild = s->lchild; /* q */
else
q->lchild = s->rchild; /* q */
free(s);
}
return 0;
}8. 빠 른 정렬
기본 사상: 한 번 의 순 서 를 통 해 대기 기록 을 독립 된 두 부분 으로 나 누 었 는데 그 중에서 일부 기록 의 키 워드 는 모두 다른 부분 에 기 록 된 키워드 보다 작 으 면 이 두 부분 기록 에 대해 계속 순 서 를 매 겨 서 실제 서열 이 질서 있 는 목적 을 달성 할 수 있다.코드 는 다음 과 같 습 니 다:
1 /* L */
2 void QuickSort (SqList *L)
3 {
4 QSort(L, 1, L->Length);
5 }QSort 함수 의 구현 은 다음 과 같 습 니 다.
/* L L->r[low...high] */
void Qsort (SqList *L, int low, int high)
{
int pivot;
if (low < high)
{
pivot = Partition(L, low, high); /* L->r[low...high] ， */
QSort(L, low, pivot-1); /* */
QSort(L, pivot+1, high); /* */
}
}Partition 함수 가 해 야 할 일 은 키 워드 를 선택 하여 한 위치 에 놓 아서 왼쪽 의 값 이 그것 보다 작고 오른쪽 값 이 그것 보다 크다 는 것 이다.그 실현 은 다음 과 같다.
1 /* L ， ， */
2 /* （ ） （ ） */
3 int Partition (SqList *L, int low, int high)
4 {
5 int pivotkey;
6 pivotkey = L->r[low]; /* */
7 while (low < high)
8 {
9 while (low < high && L->r[high] > = pivotkey)
10 high--;
11 swap(L, low, high); /* */
12 while (low < high && L-r[low] <= pivotkey)
13 low++;
14 swap(L, low, high); /* */
15 }
16
17 return low; /* */
18 }[총 결]: 빠 른 정렬 알고리즘 은 관건 은 추축 값 의 선택 에 있다. 추축 값 의 선택 을 최적화 하기 위해 세 가지 로 중 법 을 취 할 수 있다. 즉, 세 가지 키 워드 를 먼저 정렬 하고 중간 수 를 이른바 추축 이 라 고 하 는데 보통 왼쪽, 오른쪽 과 중간 세 개의 수 를 취한 다.
본문
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
