데이터 구조 제2 강: 선형 구조
11167 단어 데이터 구조
1. 선형 표 와 그 실현
하나의 좋 은 문 제 는 체인 표를 도입 하 는 장점 을 편리 하 게 설명 할 수 있다. 그것 은 바로 1 원 다항식 이다. f (x) = a0 + a1x + an - 1xn - 1 + anxn 의 표시 와 연산 (두 다항식 의 더하기 / 상쇄 / 상승 등) 이다. 분명히 우 리 는 배열 을 이용 하여 이 문 제 를 해결 할 수 있다. 두 다항식 의 더하기 는 두 배열 의 대응 분량 을 더 하 는 것 이다.그러나 이것 은 매우 심각 한 문 제 를 도입 했다. 어떻게 다항식 x + 3x 2000 을 표시 합 니까?이렇게 큰 배열 을 열 면 분명히 공간 낭 비 를 초래 할 것 이다.
위 에 남 겨 진 문 제 를 해결 하 는 방법 은 구조 배열 로 지수 크기 에 따라 질서 있 게 저장 하고 모든 배열 요소 로 두 가지 정 보 를 유지 하 는 것 이다. 여러 가지 식 의 계수 와 지수 이다.추가 작업 을 수행 할 때 는 두 개의 다항식 현재 대응 항목 의 지 수 를 처음부터 비교 하면 된다.그러나 문제 가 있 습 니 다. 배열 의 물리 공간 은 연속 적 입 니 다. 만약 에 우리 의 데이터 가 프로그램 이 분배 할 수 있 는 최대 연속 공간 을 초과 하면 잔 구 를 사용 합 니 다. 이것 은 자 연 스 럽 게 우리 의 링크 를 도입 합 니 다.
링크 의 저장 구조, 즉 각 노드 는 계수 와 지수 두 개의 데이터 필드 와 하나의 지침 도 메 인 을 포함한다.
typedef struct PolyNode * Polynomial;
typedef struct PolyNode{
int coef;
int expon;
Polynomial link;
}
다항식 은 문제 가 우리 에 게 준 시사 점 을 나타 낸다.
선형 표 기본 동작 은 다음 과 같 습 니 다.
선형 표 의 순서 저장 실현 (배열 의 연속 저장 공간 순 서 를 이용 하여 선형 표 의 각 요 소 를 저장 합 니 다):
메모리 구조:
typedef struct{
ElementType Data[MAXSIZE];
int Last;
}List;
List L, *PtrL;
i 로 표 시 된 요소 에 접근 하기: L. Data [i] 또는 PtrL - > Data [i]
선형 표 의 길이: L. Last + 1 또는 PtrL - > Last + 1 (Last 는 끝 요소 의 아래 표 시 된 위 치 를 표시 합 니 다)
주요 조작 실현:
List * MakeEmpty()
{
List *PtrL;
PtrL = (List *)malloc(sizeof(List));
PtrL->Last = -1;
return PtrL;
}
int Find(ElementType X, List *PtrL)
{
int i = 0;
while(i <= PtrL->Last && PtrL->Data[i] != X)
i++;
if(i > PtrL->Last)
return -1; // ， -1
else
return i; //
}
void Insert(ElementType X, int i, List *PtrL)
{
int j;
if(PtrL->Last == MAXSIZE-1) // ，
{
printf(" ");
return;
}
if(i < 1 || i > PtrL->Last+2)
{
printf(" ");
return;
}
for(j = PtrL->Last; j >= i-1; j--)
PtrL->Data[j+1] = PtrL->Data[j]; // ai~an
PtrL->Data[i-1] = X; //
PtrL->Last++; // Last
return;
}
void Delete(int i, List *PtrL)
{
int j;
if(i < 1 || i > PtrL->Last+1)
{
printf(" %d ", i);
return;
}
for(j = i; j <= PtrL->Last; j++)
PtrL->Data[j-1] = PtrL->Data[j]; // ai+1~an
PtrL->Last--; // Last
return;
}
선형 표 의 체인 식 저장 실현 (논리 적 으로 인접 한 두 요소 가 물리 적 으로 도 인접 하도록 요구 하지 않 고 '체인' 을 통 해 데이터 요소 간 의 논리 적 관 계 를 구축한다):
메모리 구조:
typedef struct Node{
ElementType Data;
struct Node *Next;
}List;
List L, *PtrL;
주요 조작 실현
int Length(List *PtrL)
{
List *p = PtrL; // p
int j = 0;
while(p)
{
p = p->Next;
j++; // p j
}
return j;
}
List *FindKth(int K, List *PtrL)
{
List *p = PtrL;
int i = 1;
while(p != NULL && i < K)
{
p = p->Next;
i++;
}
if(i == K) // K ，
return p;
else
return NULL; //
}
List *Find(ElementType X, List *PtrL)
{
List *p = PtrL;
while(p != NULL && P->data != X)
p = p->Next;
return p;
}
List *Insert(ElementType X, int i, List *PtrL)
{
List *p, *s;
if(i == 1) //
{
s = (List *)malloc(sizeof(List)); // 、
s->Data = X;
s->Next = PtrL;
return s;
}
p = FindKth(i-1, PtrL); // i-1
if(p == NULL) // i-1 ，
{
printf(" i ");
return NULL;
}
else
{
s = (List *)malloc(sizeof(List)); // 、
s->Data = X;
s->Next = p->Next; // i-1
p->Next = s;
return PtrL;
}
}
List *Delete(int i, List *PtrL)
{
List *p, *s;
if(i == 1) //
{
s = PtrL; // s 1
if(PtrL != NULL)
PtrL = PtrL->Next; //
else
return NULL;
free(s);
return PtrL;
}
p = FindKth(i-1, PtrL); // i-1
if(p == NULL)
{
printf(" %d ", i-1);
return NULL;
}
else if(p->Next == NULL)
{
printf(" %d ", i);
return NULL;
}
else
{
s = p->Next; // s i
p->Next = s->Next; //
free(s); //
return PtrL;
}
}
2. 창고
스 택 에는 멋 진 응용 이 많 습 니 다. 표현 식 의 값 을 구하 고 괄호 가 일치 하 며 함수 호출 과 재 귀 실현, 깊이 우선 검색, 역 추적 알고리즘 이 있 습 니 다.
스 택 의 추상 적 인 데이터 형식 설명
스 택: 일정한 조작 제약 이 있 는 선형 표 는 한 끝 (스 택 꼭대기, Top) 에 만 삽입, 삭제 합 니 다.
데이터 삽입: 스 택 에 들 어가 기 (Push);데이터 삭제: 스 택 나 가기 (Pop);후 입 선 출: List In First Out (LIFO)
기본 동작:
#define MaxSize < >
typedef struct{
ElementType Data[MaxSize];
int Top;
}Stack;
//
void Push(Stack *PtrS, ElementType item)
{
if(PtrS->Top == MaxSize-1)
{
printf(" ");
return;
}
else
{
PtrS->Data[++(PtrS->Top)] = item;
return;
}
}
//
ElementType Pop(Stack *PtrS)
{
if(PtrS->Top == -1)
{
printf(" ");
return ERROR; // ERROR ElementType ，
}
else
return (PtrS->Data[(PtrS->Top)--])
}
[인 스 턴 스] 한 배열 로 두 개의 스 택 을 실현 하 십시오. 배열 공간 을 최대한 이용 하여 배열 이 스 택 에 들 어 갈 공간 만 있 으 면 성공 할 수 있 도록 해 야 합 니 다.
분석: 비교적 똑똑 한 방법 은 이 두 스 택 을 각각 배열 의 양쪽 에서 중간 으로 자라 게 하 는 것 이다.두 창고 의 지붕 지침 이 만 났 을 때, 두 창고 가 모두 꽉 찼 다 는 것 을 나타 낸다.
#define MaxSize < >
struct DStack{
ElementType Data[MaxSize];
int Top1; // 1
int Top2; // 2
}S;
S.Top1 = -1;
S.Top2 = MaxSize;
//
void Push(struct DStack *PtrS, ElementType item, int Tag)
{
// Tag ， 1 2
if(PtrS->Top2 - PtrS->Top1 == 1) //
{
printf(" ");
return;
}
if(Tag == 1) //
PtrS->Data[++(PtrS->Top1)] = item;
else //
PtrS->Data[--(PtrS->Top2)] = item;
}
//
ElementType Pop(struct DStack *PtrS, int Tag)
{
if(Tag == 1)
{
if(PtrS->Top == -1) // 1
{
printf(" 1 ")：
return NULL;
}
else
return PtrS->Data[(PtrS->Top1)--];
}
else
{
if(PtrS->Top2 == MaxSize) // 2
{
printf(" 2 ");
return NULL;
}
else
return PtrS->Data[(PtrS->Top2)++];
}
}
스 택 의 체인 저장 실현:
창고 의 체인 식 저장 구 조 는 사실상 하나의 단일 체인 테이블 로 체인 창고 라 고 부른다.삽입 과 삭제 작업 은 체인 스 택 의 스 택 꼭대기 에서 만 진행 할 수 있 습 니 다.생각해 볼 만 한 문 제 는 창고 꼭대기 지침 이 체인 시계의 어느 쪽 에 있어 야 하 는가?
typedef struct Node{
ElementType Data;
struct Node *Next;
}LinkStack;
LinkStack *Top;
LinkStack *CreateStack()
{
// ，
LinkStack *S;
S = (LinkStack *)malloc(sizeof(struct Node));
S->Next = NULL;
return S;
}
int IsEmpty(LinkStack *S)
{
// S ， 1， 0
return S->Next == NULL;
}
void Push(ELementType item, LinkStack *S)
{
// item S
struct Node *TmpCell;
TmpCell = (LinkStack *)malloc(sizeof(struct Node));
TmpCell->Element = item;
TmpCell->Next = S->Next;
S->Next = TmpCell;
}
ElementType Pop(LinkStack *S)
{
// S
struct Node *FirstCell;
ElementType TopElem;
if(IsEmpty(S))
{
printf(" ");
return NULL;
}
else
{
FirstCell = S->Next;
S->Next = FirstCell->Next;
TopElem = FirstCell->Element;
free(FirstCell);
return TopElem;
}
}
3. 대열
대기 열 (Queue): 일정한 조작 제약 이 있 는 선형 표
삽입 및 삭제 작업: 한 끝 에 만 삽입 할 수 있 고 다른 한 끝 에 만 삭제 할 수 있 습 니 다.
데이터 삽입: 대기 열 에 들 어가 기 (AddQ);데이터 삭제: 대기 열 (DeleteQ) 내 보 내기;먼저 서비스 하기;먼저 나 가기: FIFO
대기 열의 주요 동작:
대기 열의 순서 저장 구 조 는 보통 1 차원 배열 과 하나의 기록 팀 의 머리 요소 위 치 를 기록 하 는 변수 front 와 하나의 기록 팀 의 꼬리 요소 위 치 를 기록 하 는 변수 rear 로 구성 된다.
#define MaxSize < >
typedef struct{
ElementType Data[MaxSize];
int rear;
int front;
}Queue;
//
void AddQ(Queue *PtrQ, ElementType item)
{
if((PtrQ->rear+1) % MaxSize == PtrQ->front)
{
printf(" ");
return;
}
PtrQ->rear = (PtrQ->rear+1) % MaxSize;
PtrQ->Data[PtrQ->rear] = item;
}
//
ElementType DeleteQ(Queue *PtrQ)
{
if(PtrQ->front == PtrQ->rear)
{
printf(" ");
return ERROR;
}
else
{
PtrQ->front = (PtrQ->front+1) % MaxSize;
return PtrQ->Data[PtrQ->front];
}
}
대기 열의 체인 저장 실현:
대기 열의 체인 식 저장 구조 도 하나의 단일 체인 테이블 로 실현 할 수 있다.삽입 과 삭제 작업 은 각각 링크 의 양쪽 에서 진행 합 니 다.생각 할 만 한 문 제 는 대열 지침 front 와 rear 가 각각 링크 의 어느 쪽 을 가 리 켜 야 하 느 냐 는 것 이다.
typedef struct Node{
ElementType Data;
struct Node *Next;
}QNode;
typedef struct{ //
QNode *rear; //
QNode *front; //
}LinkQueue;
LinkQueue *PtrQ;
//
ElementType DeleteQ(LinkQueue *PtrQ)
{
QNode *FrontCell;
ElementType FrontElem;
if(PtrQ->front == NULL)
{
printf(" ");
return ERROR;
}
FrontCell = PtrQ->front;
if(PtrQ->front == PtrQ->rear) //
PtrQ->front = PtrQ->rear = NULL; //
else
PtrQ->front = PtrQ->front->Next;
FrontElem = FrontCell->Data;
free(FrontElem); //
return FrontElem;
}
(본문 완성).
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
