데이터 구조 공유
데이터: 객관 적 인 사물 을 묘사 하 는 기호 로 컴퓨터 에서 조작 할 수 있 는 대상 으로 컴퓨터 에 의 해 식별 되 고 컴퓨터 에 입력 하여 처리 할 수 있 는 기호 집합 이다.balabala 이것 은 모두 개념 입 니 다. 모두 가 잊 었 는 지 괜 찮 습 니 다. 어쨌든 이번 공유 와 이 개념 도 모든 새 와 관계 가 있 습 니 다.
그러나 어떤 개념 은 여전히 아버 지 를 속 이 는 것 은 소 용이 없 지만, 어떤 사람들 은 그래도 관심 을 가 져 야 한다.
논리 구조
집합 구조
선형 구조
나무 구조
도형 구조
물리 구조
순차 기억 구조
체인 메모리 구조
Q1: ok 그러면 논리 구조 에서 모든 요소 의 대응 관 계 는 뭐라고 생각 합 니까?
Q2: 순서 저장 구조 와 체인 저장 구조의 차 이 를 생각해 보 세 요.
데이터 구조 가 가장 기본 적 이 고 가장 기본 적 인 것 은 바로 이 점 이다.
그렇다면 데이터 구 조 는 알고리즘 이라는 것 과 관련 이 있 을 것 이다.
알고리즘 의 개념 은 말씀 드 리 지 않 겠 습 니 다. 알고리즘 의 시간 복잡 도와 공간 복잡 도 를 말씀 드 리 겠 습 니 다.
기본적으로 우 리 는 알고리즘 의 시간 복잡 도 를 복잡 도 라 고 부른다
시간 복잡 도, 우 리 는 큰 O 단계 로 표시 합 니 다.
지금 예 를 하나 들 어 볼 게 요.
만약 내 가 지금 0 에서 n 까지 의 알고리즘 을 설계 하 라 고 요구한다 면
두 가지 방법 이 있어 요.
int sumSilly(int n) {
int sum = 0; //1
for(int i =0; i <= n; ++ i) { //n +1
sum += i //n
}
return sum /1
}
int sumSmart(int n) {
int sum = n * (n + 1) / 2; //1
return sum // 1
}
void main() {
int result1 = sumSilly(100)
int result2 = sumSmart(100)
}
지금 저희 가 두 가지 방법 을 계산 해 보도 록 하 겠 습 니 다.
silly： 1+（n+1）+n +1 = 2n + 3
smart: 1+1 = 2
분명 한 것 은 모두 가 두 번 째 방법 이 좋다 고 생각 합 니 다. 큰 O 단계 가 나 오 면 하 나 는 O (n) 이 고 하 나 는 O (1) 입 니 다. 우 리 는 큰 O 로 밀 면 상수 의 버 림 을 합 니 다. n 이 무한대 일 때 상수 가 결과 에 미 치 는 영향 이 매우 작 기 때 문 입 니 다.
여러분 은 선형 단계 O (1), 대수 단계 O (log n), 지수 단계 O (n ^ m) 와 같은 알고리즘 을 쓸 수 있 습 니까?
시간 복잡 도의 크기 관 계 는 o 안의 그 크기 관계 와 관계 가 있다 (전제 n 이 매우 크다)
아래 n 은 변수 이 고 m 는 상수 (n 이 크다)
1 < logn < n < nlogn < n^m < m^n < n! < n^n
잡담 끝 났 습 니 다. 다음.
선형 표 는 두 가지 가 있 습 니 다. 순서 표 와 링크 가 있 습 니 다. 대응 하 는 것 은 바로 순서 저장 과 체인 저장 입 니 다. 일부 파트너 들 이 궁금 해 할 수 있 습 니 다. 정적 링크 가 어디 갔 는 지 정적 링크 는 특수 한 것 이지 만 링크 라 고 할 수 있 습 니 다. 저 는 길이 가 고정된 링크 라 고 생각 합 니 다.내 가 말 한 길 이 는 최대 길이 다.
링크 안에 순환 링크, 싱글 링크, 양 방향 링크 가 있 습 니 다.그러면 싱글 체인 시트 의 정의
typedef struct Node {
ElemType data;
struct Node* next；
} Node，*DuLinkList；
p 를 s 에 삽입 한 후:
p.next = s.next;
s.next = p;
p 뒤의 노드 s 삭제
p.next = s.next
free(s)
Q3: 양 방향 링크 는 노드 p 를 어떻게 삭제 하고 노드 p 를 s 뒤에 삽입 합 니까?양 방향 링크 의 정 의 는 다음 과 같다.
typedef struct DulNode {
ElemType data;
struct DulNode* prior;
struct DulNode* next；
}DulNode，*DuLinkList；
창고 와 대열
창고.
창고 에 있 는 이 물건 은 먼저 들 어간 후에 나 온 것 이 니 누구나 다 알 고 있 겠 지 요? 그럼 시험 을 보 겠 습 니 다.
1，2，3
123，213，321，132，231，312
표 끝 에 만 삽입 하고 삭제 할 수 있 습 니 다. 구조 정 의 는 다음 과 같 습 니 다.
typedef struct {
SelemType data[MAXSIZE];
int top;
}SqStack;
삽입 조작
status Push(SqStack *s,SelemType e) {
if (s->top == MAXSIZE -1) {
return error;
}
s->top ++;
s->data[s->top] = e;
return ok;
}
삭제 작업
status Pop(SqStack *s,SelemType e) {
if (s->top == -1) {
return error;
}
*e = s->data[s->top];
s->top--;
return ok;
}
창고 의 공간 은 사전에 정 해진 것 이기 때문에 작 으 면 확충 해 야 하고, 사전에 전 화 를 했 는 지 밝 히 면 낭비 된다.
다 들 어 렸 을 때 38 선 기억 나 세 요?
이 38 선, 우리 가 컴퓨터 로 생각 하 는 것 은 바로 두 창고 가 공간 을 공유 하 는 것 이다. 그러면 우 리 는 정 의 를 살 펴 보 자.
typedef struct {
SelemType data[MAXSIZE];
int top1;
int top2;
}SqStack;
삽입 조작
status Push(SqStack *s,SelemType e,int stacNumber) {
if (s->top1 + 1 == s->top2) {
return error;
}
if (stackNumber == 1){
s->data[++s->top1] = e
} else if (stackNumber == 2) {
s->data[--s->top2] = e
}
return ok;
}
삭제 작업
status Pop(SqStack *s,SelemType e,int stacNumber) {
if (stackNumber == 1) {
if (s->top1 == -1) {
return error;
}
*e = s->data[s->top1 --];
}
if (stackNumber == 2) {
if (s->top2 == MAXSIZE) {
return error;
}
*e = s->data[s->top2 ++];
}
return ok;
}
창고 의 응용 --- 귀속, 귀속 은 말 해 야 한다
피 보 나치 수열
토끼 가 태 어 난 지 두 달 후에 아 이 를 낳 을 수 있다 면 토끼 가 익 으 면 매달 한 쌍 의 토끼 를 낳 을 수 있다. 토끼 가 죽지 않 는 다 고 가정 하면 n 개 월 에 몇 쌍 의 토끼 가 있 을 수 있 기 를 바란다.
1
1
2
3
5
8
이 수열 의 법칙 은 무엇 입 니까?앞의 두 항목 의 합 은 세 번 째 항목 과 같다.
int fbi(int i) {
if (i < 2) {
return i ==0 ? 0 : 1;
}
return fbi(i -1) + fbi (i - 2);
}
Q4. 한 노 타 최 적 화 된 알고리즘 의 실현?
var hanoi = function (disc, src, aux, dst) {
if (disc > 0) {
hanoi(disc - 1, src, dst, aux);
document.writeln('Move disc ' + disc + ' from ' + src + ' to ' + dst);
hanoi(disc - 1, aux, src, dst);
}
}
창고 의 응용 - 접미사 표현 식
9 + (3 - 1) * 3 + 10 / 2 정 답 은 얼마 입 니까
·
·
·
·
·
·
·
·
그러나 나 는 계산 한 결 과 를 알 고 싶 지 않다. 나 는 단지 이 접미사 표현 식 을 어떻게 하 는 지 알려 줄 뿐이다.
9 3 1 - 3 * 10 2 / +
그리고 이제 컴퓨터 를 어떻게 계산 하 는 지 보 겠 습 니 다.
대열
먼저 들 어가 고 먼저 나 와.
순환 대기 열 말 하기
typedef struct {
QelemType data[MAXSIZE];
int front;
int rear;
}SqQueue;
대기 열 이 비어 있 을 때 우 리 는
q->front = q->rear;
그럼 꽉 찼 을 때 는 요?
(q->rear + 1)%MAXSIZE = q->front
그러면 입 대 를 하고 나 오 면 되 겠 네요.
status en(SqQueue *q.QelemType e) {
if ((q->rear + 1)%MAXSIZE == q->front) {
return error;
}
q->data[q->rear] = e;
q->rear = (q->rear + 1) % MAXSIZE;
return ok;
}
status de(SqQueue *q.QelemType e) {
if (q->front == q->rear) {
return error;
}
*e = q->data[q->front];
q->front = (q->front+1)%MAXSIZE
return ok
}
나무.
이 진 트 리
이 진 트 리 는 몇 가지 성질 이 있어 서 시험 이 든 면접 이 든 모두 볼 수 있다.
이 진 트 리 의 i 층 에는 최대 몇 개의 노드 가 있다.
깊이 가 k 인 이 진 트 리 는 최대 몇 개의 노드 가 있다.
n 개의 노드 를 가 진 이 진 트 리 의 깊이 는?【log2n】 + 1
만약 n 개 노드 의 완전 이 진 트 리 라면 i = 1 이것 은 노드 와
i > 1 그러면 그의 부모 노드 는 i / 2 이다.
2i > n 왼쪽 노드 가 없 으 면 왼쪽 노드 입 니 다.
2i + 1 > n 오른쪽 노드 가 없 으 면 오른쪽 노드 입 니 다.
임의의 이 진 트 리 T 에 대해 터미널 노드 수가 n0 이 고 도가 2 인 노드 수가 n2 이면 n = n2 + 1
이 진 트 리 의 옮 겨 다 니 는 방법
앞 순 서 를 편력 하 다.
먼저 루트 노드 에 접근 한 후 왼쪽 트 리 에 접근 한 다음 오른쪽 트 리 에 접근 합 니 다.
void PreOrderTraverse(BiTree t) {
if (t == null) {
return;
}
printf("%c",t->data);
PreOrderTraverse(t->lchild)
PreOrderTraverse(t->rchild)
}
중간 순서 로 옮 겨 다 닌 다.
먼저 왼쪽 트 리 를 방문 한 다음, 그 다음 에 오른쪽 트 리 를 따라 가세 요.
void InOrderTraverse(BiTree t) {
if (t == null) {
return;
}
InOrderTraverse(t->lchild);
printf("%c",t->data);
InOrderTraverse(t->rchild);
}
뒤 순 서 를 옮 겨 다 닌 다.
왼쪽, 오른쪽, 오른쪽.
void PostOrderTraverse(BiTree t) {
if (t == null) {
return;
}
PostOrderTraverse(t->lchild);
PostOrderTraverse(t->rchild);
printf("%c",t->data);
}
차례차례 편력 하 다
따라 와. 왼쪽 에서 오른쪽으로.
Q5. 앞의 순 서 는 ABCDEF 이 고 중간 순 서 는 CBAEDF 이 며 이 진 트 리 는 무엇 입 니까?
트 리 를 이 진 트 리 로 변환
1、 。
2、 。
3、 。 ，
숲 두 갈래 나무
1、
2、 ，
이 진 트 리
두 갈래 나무 가 숲 을 돌다.
호 프 만 나무
가중 경로 가 가장 작은 이 진 트 리 가 호 프 만 트 리 입 니 다.
0-59 5%
60-69 15%
70-79 40%
80-89 30%
90-100 10%
호 프 만 나 무 를 계산 해 보 세 요.
호 프 만 코딩
BADCADFEED
A27
B8
C15
D15
E30
F5
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
