(3) 스 택 과 대기 열
11471 단어 데이터 구조
1.1. 창고 의 정의 및 연산:
1. 정의: 스 택 은 한 끝 에서 만 조작 할 수 있 는 선형 표 입 니 다.스 택 의 경우 삽입 과 삭 제 를 허용 하 는 한 끝 을 스 택 지붕 이 라 고 하고 변 하지 않 는 한 끝 을 스 택 바닥 이 라 고 합 니 다.
2. 스 택 에 있 는 요 소 는 '후진 선 출' 의 규칙 에 따라 진행 합 니 다.스 택 에 요소 가 없 을 때 스 택 이 비 었 다 고 합 니 다. 스 택 의 저장 공간 이 다 떨 어 졌 을 때 스 택 이 가득 찼 다 고 합 니 다.
3. 창고 에 대한 기본 작업:
스 택 초기 화: initStack(s);빈 창고 만 들 기;
판단 창고 비 움: emptyStack(s);스 택 이 빈 스 택 인지 아 닌 지 를 판단 합 니 다. 1 로 돌아 가면 0 으로 돌아 가 는 것 이 아 닙 니 다.
입고: pushStack(s，x);창고 의 맨 위 에 원소 x 를 삽입 하여 x 를 새로운 창고 의 맨 위 원소 로 만 들 기;
출고: popStack(s,x);창고 가 비어 있 지 않 은 상황 에서 창고 꼭대기 원 소 를 창고 에서 제거 하고 x 에서 창고 꼭대기 원소 의 값 을 되 돌려 줍 니 다.
스 택 상단 원소: topStack(s,x);창고 가 비어 있 지 않 은 상태 에서 창고 꼭대기 요 소 를 x 에 읽 습 니 다.
1.2. 순서 창고 의 연산 과 실현:
1. 순서 스 택 은 스 택 의 순서 저장 구조 로 연속 적 인 메모리 주 소 를 이용 하여 스 택 밑 에 있 는 요 소 를 저장 합 니 다.
2. 정의 형식:
typedef struct
{
datatype data[MAXSIZE];//
int top;//
}SeqStack;top 지침 은 스 택 의 맨 위 요소 가 스 택 에 있 는 위 치 를 나타 내 고 스 택 밑 에 0 이 라 고 표시 되 어 있 기 때문에 스 택 이 비어 있 을 때 top = - 1;
3. 스 택 만 들 기:
void init_SeqStack(SeqStack **s){
*s=(SeqStack *)malloc(sizeof(SeqStack));
(*s)->top=-1;
}4. 스 택 이 비어 있 는 지 판단
int empty_SeqStack(SeqStack *s){
if(s->top==-1){
return 1;
}else{
return 0;
}
}5. 입고:
void push_SeqStack(SeqStack *s,char c){
if(s->top==MAXSIZE-1){
printf("Stack is full!!");
}else{
s->top++;
s->data[s->top]=c;
}
}6. 출고:
void Pop_SeqStack(SeqStack *s,char *c){
if(s->top==-1){
printf("Stack is empty!!!");
}else{
*c=s->data[s->top];
s->top--;
}
}7. 스 택 꼭대기 요 소 를 가 져 옵 니 다:
void top_SeqStack(SeqStack *s,char *c){
if(s->top==-1){
printf("Stack is empty!!!");
}else{
*c=s->data[s->top];
}
}1.3. 여러 순서 스 택 공유 연속 공간:
1. 스 택 바닥 의 상대 적 인 위치 가 변 하지 않 는 다 는 특징 을 이용 하여 두 순서 스 택 은 1 차원 배열 공간 을 공유 하여 서로 부족 한 부분 을 보완 할 수 있다. 실현 방법 은 두 스 택 의 스 택 바닥 을 각각 1 차원 배열 공간의 양 끝 에 설치 하고 각자 중간 으로 연장 하 는 것 이다.
2. 여러 개의 스 택 이 연속 공간 을 공유 하 는 문제 가 비교적 복잡 하 다. 스 택 상단 지침 을 설치 해 야 하 는 것 을 제외 하고 스 택 밑 지침 도 설치 해 야 한다.
1.4. 체인 스 택:
1.1.4. 정의:
1. 스 택 의 체인 저장 구 조 를 체인 스 택 이 라 고 합 니 다.순서 스 택 에 비해 체인 스 택 은 저장 공간 을 동적 으로 분배 할 수 있 습 니 다.
2. 창고 의 작업 은 모두 창고 꼭대기 에 있 기 때문에 머리 결산 점 을 설정 할 필요 가 없다. 머리 지침 은 창고 꼭대기 지침 이다.
3. 정의 형식: 단일 링크 와 같 음:
typedef struct node{
char data;
struct node *next;
}StackNode;1.4.2. 연산 실현:
1. 빈 창고 설치:
void init_StackNode(StackNode **s){
*s=NULL;
}2. 판단 창고:
int empty_StackNode(StackNode *s){
if(s==NULL)
return 1;
else
return 0;
}3. 입고:
void push_StackNode(StackNode **top,char c){
StackNode *p;
p=(StackNode *)malloc(sizeof(StackNode));
p->data=c;
p->next=*top;
*top=p;
}4. 출고:
void pop_StackNode(StackNode **top,char *c){
StackNode *p;
if(*top==NULL){
puts("stack is empty");
}else{
p=*top;
*c=(*top)->data;
*top=*top->next;
free(p);
}
}2. 창고 와 귀속:
2.1. 귀속:
1. 개념: 한 대상 의 구성 이 자 체 를 포함 하 는 현상 을 재 귀 라 고 한다.
2. 컴퓨터 에서 스 택 을 사용 하여 호출 함수 의 데이터 매개 변수 와 주 소 를 저장 합 니 다. 특히 재 귀 함수;
3. 재 귀 알고리즘 설계 프로그램 에서 만족 해 야 할 조건:
.1. 복잡 한 문 제 를 간단 한 규모 의 작은 문제 로 바 꿀 수 있 고 새로운 문 제 는 원래 문제 의 해법 과 같 거나 비슷 하 며 서로 다른 것 은 처리 하 는 대상 일 뿐 처리 대상 의 변 화 는 규칙 적 이다.
.2. 명확 한 귀속 출구 가 있어 야 한다.
2.2. 재 귀적 호출 과정 분석:
1. 동적 그림 의 방법 을 사용 하여 아 리 는 실 행 된 프로그램 에 대해 설명 하고 주 함수 와 삼촌 의 호출, 실행, 각 단계 의 상태 취소, 그리고 프로그램 실행 기간 의 모든 변수 와 함수 형 삼 의 변화 과정 을 기록 합 니 다.규칙 은 다음 과 같 습 니 다.
.1. 동적 그림 은 주 함수 와 다른 함수 의 호출 관 계 를 세로 로 설명 하고 왼쪽 에서 오른쪽으로 시간 순서에 따라 주 함수 와 다른 함수 중의 각 변수 와 형 참 값 의 변 화 를 기록한다.
.2. 함수 의 형 삼 은 초기 값 을 가 진 부분 변수 로 본다.
.3. 주 함수, 기타 함수 간 에 실 행 된 호출 관계 에 따라 위 에서 아래로 층 을 나 누고 각 층 이 설명 하 는 변 수 는 형 삼 을 포함 하여 이 층 의 첫 번 째 열 에 순서대로 열거 하 며 각 값 의 변화 상황 은 시간 순서에 따라 이 변수 와 대응 하 는 같은 줄 에 기록한다.
2. 재 귀적 인 호출 관 계 는 창고 처럼 먼저 나 간다.
3. 재 귀 알고리즘 을 사용 하여 얻 은 프로그램 구 조 는 간단 하지만 집행 효율 이 낮 고 더 많은 저장 공간 이 필요 합 니 다.
3. 대열
3.1. 정의 및 연산:
1. 스 택 과 마찬가지 로 대기 열 도 제 한 된 선형 표 입 니 다. 대기 열 은 한 끝 에 만 삽입 할 수 있 고 다른 한 끝 에서 삭제 할 수 있 습 니 다. 즉, 조작 은 '선진 선 출' 의 규칙 을 따 릅 니 다.
2. 삽입 할 수 있 는 한 끝 을 팀 끝 (rear) 이 라 고 하고 삭제 할 수 있 는 한 끝 을 팀 머리 (front) 라 고 합 니 다.
3. 대기 열 과 스 택 의 관계: 두 스 택 은 하나의 대기 열 을 구성 할 수 있 습 니 다.
4. 기본 동작:
대기 열 초기 화: initseqQueue (& q), 빈 대기 열 q 생 성;
판단 빈 대기 열: emptyseqQueue (q), 빈 대기 열 여 부 를 판단 합 니 다. 1 을 되 돌려 주지 않 으 면 0 을 되 돌려 줍 니 다.
입단 조작: inSeqQueue(q,x);x 를 파티 끝 에 삽입 하기;
출전 조작: outSeqQueue(q,x);팀 헤드 요 소 를 삭제 하고 x 에서 되 돌려 줍 니 다.
리더 헤드 원소: frontSeqQueue(q,x);팀 헤드 요 소 를 x 에서 되 돌려 줍 니 다.
3.2. 대기 열의 저장 구조 와 연산 의 실현:
3.2.1. 순서 대기 열: 대기 열의 순서 저장 구 조 는 연속 적 인 저장 부 를 이용 하여 대기 열 요 소 를 저장 합 니 다.
1. 정의 형식:
typedef struct{
int data[MAXSIZE];
int rear,front;//
}SeqQueue;2. 규칙:
하면, 만약, 만약... *q=(SeqQueue *)malloc(sizeof(SeqQueue));
이 대기 열의 데이터 영역 은: q - > data [0] ~ q - > data [MaxSize - 1] 입 니 다.
보통 팀 헤드 포인터 q - > front 는 팀 헤드 요소 의 앞 위 치 를 가리 키 며 주의 하 세 요. 앞의 위치 이 고 팀 꼬리 포인터 가 팀 꼬리 요 소 를 가리 키 면 다음 과 같 습 니 다.
.1. 팀 비 움: q - > rear = q - > front;
.2. 팀 가득: q - > rear = MaxSize;
.3. 팀 의 어떤 요소: q - rear - q - > front;
넘 치 는 것 을 고려 하지 않 은 상태 에서 대열 에 들 어가 면 꼬리 바늘 에 1 을 추가 할 수 있 고, 팀 을 나 가면 머리 바늘 에 1 을 추가 할 수 있 지만, 이렇게 하면 '가짜 넘 침' 이 발생 하여 공간 을 낭비 할 수 있다. 가짜 넘 침 을 해결 하 는 방법 은 대열 을 순환 대열 로 바 꾸 는 것 이다.
3.2.2. 순환 대기 열: 순서 대기 열 을 수미 로 연결 하여 원 환 을 구성한다.
1. 순환 대기 열 은 가짜 넘 치 는 문 제 를 해결 할 수 있 지만 이때 판단 팀 의 빈 공간 과 팀 의 빈 공간 은 모두 q - > rear = = q - front 로 변 합 니 다. 이것 은 매우 불편 합 니 다. 따라서 이 문 제 를 해결 하기 위해 취 하 는 방법 은 데이터 요소 의 저장 공간 을 손실 하 는 것 입 니 다. 가득 찬 조건 을 (q - > rear + 1)% MaxSize = = q - > front 로 바 꾸 고 팀 의 빈 조건 은 변 하지 않 습 니 다. q - rear = q - > front;
순환 대기 열의 요소 개 수 는: (q - > rear - q - > front + MaxSize)% MaxSize 입 니 다.
처음 과 끝 이 연결 되 어 있 기 때문에 입 대 는 q - > rear = (q - > rear + 1)% MaxSize, q - > data [q - > rear] = x 로 작 동 합 니 다.
다음 동작: q - > front = (q - > front + 1)% MaxSize; x = q - > data [q - > front];
2. 빈 팀 설치:
void init_SeqQ(SeqQueue **q){
*q=(SeqQueue *)malloc(sizeof(SeqQueue));
*q->rear=0;
*q->front=0;
}3. 입단 (팀 만 료 여 부 를 판단 해 야 함):
void in_SeqQ(SeqQueue *q,int x){
if((q->rear+1)%MAXSIZE==q->front){
puts("Queue is full");
}else{
q->rear=(q->rear+1)%MAXSIZE;
q->data[q->rear]=x;
}
}4. 파티 에 나 가기 (맞 는 지 없 는 지 판단 해 야 함):
void out_SeqQ(SeqQueue **q,int *x){
if(*q->rear==*q->front){
puts("Queue is empty!!!");
}else{
*q->front=(*q->front+1)%MAXSIZE;
*x=*q->data[*q->front];
}
}5. 대기 열 이 비어 있 는 지 판단 하기:
int empty_SeqQ(SeqQueue *q){
if(q->rear==q->front)
return 1;
else
return 0;
}3.2.3. 체인 대기 열: 대기 열의 체인 식 저장 구조, 체인 대기 열 도 표지 팀 의 꼬리 와 팀 헤드 의 지침 이 필요 하 다.
1. 정의 형식:
typedef struct node{
char data;
struct node *next;
}QNode; //
typedef struct{
QNode *rear,*front;
}LQNode; // 2. 빈 대기 열 만 들 기:
void init_LQueue(LQNode **q){
QNode *p;
p=(LQNode *)malloc(sizeof(QNode));
*q=(LQNode *)malloc(sizeof(LQNode));
p->next=NULL;
*q->rear=p;
*q->front=p;
}3. 입대:
void in_LQueue(LQNode *q,char c){
QNode *p;
p=(QNode *)malloc(sizeof(QNode));
p->data=c;
p=NULL;
q->rear->next=p;
q->rear=p;
}4. 대기 열 이 비어 있 는 지 판단 하기:
int empty_LQueue(LQNode *q){
if(q->rear==q->front)
return 1;
else
return 0;
}5. 출전:
void out_LQueue(LQNode *q,char *c){
QNode *p;
if(q->rear==q->front){
puts("Link Queue is empty");
}else{
p=(QNode *)malloc(sizeof(QNode));
p=q->front->next;
q->front->next=p->next;
*c=p->data;
free(p);
if(q->front->next==NULL){ // ，
q->rear=q->front;
}
}
}4. 정리:
1. 스 택 과 선형 표 의 관계:
개인 적 으로 스 택 은 특수 한 선형 표 라 고 생각 합 니 다. 스 택 은 한 끝 에서 만 조작 할 수 있 기 때 문 입 니 다. 개체 에 게 선형 표 와 스 택 은 같은 등급 의 관계 이 고 선형 표 는 배열 이나 지침 으로 구성 할 수 있 습 니 다. 마찬가지 로 스 택 도 배열 이나 지침 으로 구성 할 수 있 습 니 다.
순서대로 저 장 된 선형 표 와 스 택 은 '포인터' 의 하 표 의미 변화 에 해당 한다. 전 자 는 표 의 길 이 를 가리 키 고 후 자 는 스 택 꼭대기 요소 의 하 표를 가리킨다. 체인 식 에 저 장 된 선형 표 와 스 택 에 대해 전 자 는 두 점 과 두 지침 을 설정 해 야 한다. 후 자 는 모두 한 끝 에서 조작 하기 때문에 두 점 을 설정 할 필요 가 없다. 두 지침 은 바로 스 택 꼭대기 지침 이다.
2. 체인 식 으로 저 장 된 대기 열 은 왜 각각 두 개의 데이터 형식 을 사용 합 니까?
형식적 으로 볼 때 대열 은 특수 한 선형 구조 로 스 택 을 정의 하 는 것 처럼 하나의 구조 체 를 사용 할 수 있 지만 이렇게 되면 스 택 과 다 를 것 이 없 기 때문에 대열 의 머리 지침 과 꼬리 지침 을 하나의 구조 체 에 넣 고 각각 대열 의 끝 점 을 가리킨다.
3. 스 택 의 출력 준칙: 출력 시퀀스 에서 임 의 요소 뒤에 이 요소 보다 작고 오름차 (모두 요소 의 번호 에 있어) 의 두 가지 요소 가 나타 나 면 안 됩 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
