02142 ＜ 데이터 구조 서론 ＞ 제3 장 스 택, 대열 및 배열
3.1 스 택 (스 택)
3.1.1 기본 개념
데이터 손실 을 방지 하기 위해 스 택 에 들 어가 기 전에 스 택 만 료 여 부 를 판단 해 야 합 니 다. 스 택 사용 C 정 의 는 다음 과 같 습 니 다.
const int maxsize =6;
typedef struct seqstack {
DataType data[maxsize];
int top;
} seqStk;
maxsize 는 순차 스 택 의 용량 data [maxsize] 스 택 에 있 는 데이터 요 소 를 저장 하 는 배열 top 표지 스 택 의 맨 위 치 를 나타 내 는 변수 이 고 범 위 는 0 에서 maxsize - 1 입 니 다.
int InitStack(SeqStk *stk){
stk->top =0;
return 1;
}
int EmptyStack(SeqStk *stk){
if (stk->top ==0) return 1;
else return 0;
}
int Push(SeqStk *stk, DateType x){
if (stk->top == maxsize-1)
{
error(" "); return 0'}
else{
stk->top++;
stk->data[stk->top] =x;
return 1;
}
}
int Pop(SeqStk *stk){
if (stk->top ==0){
error(" ");
return 0;
}
else{
stk->top--;
return 1;
}
}
DataType GetTop(SeqStk *stk){
if (EmptyStack(stk)) return NULLData;
else return stk->data[stk->top]
}
3.1.3 스 택 의 링크 실현
스 택 의 링크 는 체인 스 택 이 라 고 부 릅 니 다. 체인 스 택 은 앞장 서 는 노드 의 단일 체인 표 로 LS 가 링크 의 끝 점 을 가리 킬 수 있 습 니 다. 첫 번 째 노드 는 바로 스 택 의 끝 점 입 니 다. LS - > next 는 스 택 의 끝 점 을 가리 키 고 끝 점 은 스 택 의 끝 점 입 니 다. 체인 스 택 은 용량 의 크기 를 고려 하지 않 아 도 됩 니 다. C 언어 정 의 는 다음 과 같 습 니 다.
typedef struct node {
DataType data;
struct node *next;
}LkStk;
void InitStack(LkStk *LS){
LS = (LkStk *)malloc(sizeof(LkStk));
LS->next = NULL; //
}
int EmptyStack(LkStk *LS){
if (LS->next==NULL) return 1;
else return 0;
}
void Push(LkStk *LS, DataType x){
LkStk *temp;
temp = (LkStk *)malloc(sizeof(LkStk)); //
temp->data = x; // x
temp->next=LS->next; // next
LS->next = temp; //
}
int Pop(LkStk *LS){
LkStk *temp;
if (EmptyStack(LS)) return 0;
else {
temp = LS->next;
LS->next = temp->next;
free(temp);
return 1;
}
}
여기 서 좀 더 생각해 보 세 요. 왜
LS->next=LS->next->next 이런 방식 으로 스 택 지붕 을 차 스 택 꼭대기 에 가리 키 지 않 습 니까?이 방식 을 사용 하면 원래 스 택 의 정점 이 존재 하고 메모리 공간 을 차지 합 니 다. 이 를 방출 하지 않 았 기 때문에 여기 서 temp 지침 을 도입 합 니 다. 첫 번 째 단 계 는 temp 이 스 택 의 정점 을 가리 키 고 두 번 째 단 계 는 원래 스 택 의 정점 을 두 번 째 스 택 지붕 으로 가리 키 며 세 번 째 단 계 는 temp 을 방출 합 니 다. 5. 스 택 의 정상 요 소 를 가 져 옵 니 다.DataType GetTop(LsStk *LS){
if (EmptyStack(LS)) return NULLData;
else {
return LS->next->data; //
}
}
3.1.4 재 귀
재 귀: 만약 에 하나의 함수 나 데이터 구조의 정의 에서 그 자신 을 응용 하면 이 함수 나 데이터 구 조 는 재 귀 정의 라 고 부 르 고 재 귀 라 고 부 릅 니 다. 재 귀 정 의 는 '순환 정의' 가 될 수 없 으 며 다음 과 같은 두 가지 조건 이 필요 합 니 다.
3.2.1 대열 의 기본 개념
const int maxsize=20;
typedef struct seqqueue{
DataType Data[maxsize]; // ,
int front, rear; // front , rear
} SeqQue;
SeqQue SQ;
data: 1 차원 배열, 저장 대기 열 에 있 는 데이터 요소 front: 지향
rear: 은 왜 선형 표를 사용 하지 않 고 순환 선형 표를 사용 합 니까?참고 p72 쪽,
:
-
void InitQueue(CycQue CQ){
CQ.front = 0;
CQ.rear = 0;
}
-
int EmptyQueue(CycQue CQ){
if (CQ.front == CQ.rear) return 1;
else return 0;
}
-
void EnQueue(CycQue CQ, DataTye x){
if ((CQ.rear+1)%maxsize == CQ.front) {
error(" ");
return 0;
}
else {
CQ.rear = (CQ.rear+1) % maxsize;
CQ.data[CQ.rear] = x;
return 1;
}
}
-
int OutQueue(CycQue CQ){
if (EmptyQueue(CQ)) {
error(" ");
return 0;
}
else{
CQ.front = (CQ.front+1)%maxsize; //
return 1;
}
}
-
DataType GetHead(CycQue CQ){
if (EmptyQueue(CQ) return NULLData;
else{
return CQ.data[(CQ.front+1)%maxsize];
}
}
3.2.3
typedef struct LinkQueueNode{
DataType data;
struct LinkQuequeNode *next;
}LkQueNode;
typedef struct LkQueNode{
LkQueNode *front, *rear;
}LkQue;
LkQue LQ;
-
void InitQueue(LkQue *LQ){
LkQueNode *temp;
temp = (LkQueNode *)malloc(sizeof(LkQueNode));
LQ->front = temp;
LQ->rear = temp;
(LQ->front)->next = NULL;
}
-
int EmptyQueue(LkQue *LQ){
if (LQ.front == LQ.rear) return 1;
else return 0;
}
-
void EnQueue(LkQue *LQ, DataType x){
LkQueNode *temp;
temp = (LkQueNode *).malloc(sizeof(LkQueNode));
temp->data = x;
temp->next = NULL;
(LQ->rear)->next = temp; //
LQ->rear = temp; //
}
-
int OutQueue(LkQue *LQ){
LkQueNode *temp;
if (EmptyQueue(LQ)){
error(" ");
return 0;
}
else{
temp = LQ->front->next; // temp
LQ->front->next = temp->next; // ,
if (temp->next ==NULL);
LQ->rear = LQ->front;// , front rear
free(temp);
return 1;
}
}
-
DataType GetHead(LkQue LQ){
LkQueNode *temp;
if (EmptyQueue(LQ)) return NULLData;
else {
temp = LQ.front->next;
return temp->data; //
}
}
3.3
3.3.1
- , , , . , N N-1 .
- :
- : , ;
- : , ;
3.3.2
, ; , . C , .
.(p82)
loc[i, j] = loc[0,0] + (n*i +j)*k
3.3.3
, , , , , , .
,
a[9,9]
a[4,5] k :
, , ,
, loc[0,0] + 4( 4 )*9( 9 )+5( 5 )
loc[0, 0] 0, a[4, 5] : 41
-
(p82)
N A aij = aji i>=0, j<=n-1, A
:
99
: a[9, 9],
a[2,3] = a[3, 2]
9*(9+1)/2 = 45 ,
: 9*9=81 , a11, a22, a33 , 9 , , (81-9)/2=36 , 9 , 36+9=45 ,
n(N+1)/2,
a[9, 8]
loc[0,0] 0, a[4, 5] (4+1)*4/2 + 5 = 15,
a[5, 4] K ?
, a[5, 4] = a[4, 5], 15 ,
-
(p83)
( ) C , ( ) .
-
M N T , T<=M*N, .
: ((0, 1, 5), (2, 1, -1))
: a[0,1]=5, a[2, 1] = -1, 0 ,
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
02142 ＜ 데이터 구조 서론 ＞ 제2 장 선형 표포 지 셔 닝 Locate (L, x): 선형 표 에서 데이터 요소 값 이 x 와 같은 결점 번 호 를 찾 습 니 다. 예 를 들 어 순서 표 는 9 개의 요소 가 있 고 세 번 째 요소 앞 에 새로운 요 소 를 삽...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
