데이터 구조: [학습 노트] 02 선형 구조 - 선형 표
38166 단어 데이터 구조
질문
실례: 다항식 f (x) 의 표시.
방법 1 순위 저장 구조 직접 표시
배열 의 각 분량 은 다항식 의 각 항목 에 대응 합 니 다.
a [i]: 항 x ^ i 의 계수 ai.
두 다항식 의 더하기: 두 배열 의 대응 분량 의 더하기.
단점: 다항식 x + x ^ 2000 시 커 다란 공간 낭비 가 있 음 을 나타 낸다.
방법 2 차 저장 구 조 는 0 항 이 아 닌 것 을 나타 낸다.
구조 수조 (2 차원 수조) 로 수조 분량 은 계수 ai, 지수 i 로 구 성 된 구조 로 0 항 이 아 닌 항목 에 대응한다.
메모: 저장 할 때 지수 크기 를 작은 것 에서 큰 것 으로 정렬 하여 뒤의 연산 을 편리 하 게 해 야 합 니 다.
방법 3 링크 구조 저장 비 0 항
링크 에 있 는 모든 노드 는 여러 가지 식 의 비 0 항목 을 저장 하 는데 계수 와 지수 두 개의 데이터 필드 와 하나의 지침 도 메 인 을 포함한다.
coef
expon
link
typedef struct PolyNode *Polynomial;
struct PolyNode {
int coef;
int expon;
Polynomial link;
};
2 선형 표 란 무엇 인가
선형 표 (Linear List): 같은 유형의 데이터 요소 로 질서 있 는 서열 을 구성 하 는 선형 구조
3 선형 표 의 순서 저장
기본 구 조 는 다음 과 같다.
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
int last;
};
struct LNode L;
List PtrL;
3.1 초기 화:
List MakeEmpty()
{
List PtrL;
PtrL = (List)malloc(sizeof(struct LNode));
PtrL -> Last = -1;
return PtrL;
}
3.2 찾기:
int Find(ElementType X, List PtrL)
{
int i = 0;
while (i <= PtrL->Last && PtrL->Data[i] != X)
i++;
if (i > PtrL->Last)
return -1;
else
return i;
}
3.3 삽입:
void Insert(ElementType X, int i, List PtrL)
{
int j;
if (PtrL->Last == MAXSIZE - 1) {
printf('FULL');
return;
}
if (i<1 || i>PtrL->Last + 2) {
printf('No right');
return;
}
for (j = PtrL->Last;j >= i - 1;j--)
PtrL->Data[j + 1] = PtrL->Data[j];
PtrL->Data[i - 1] = X;
PtrL->Last++;
return;
}
3.4 삭제:
void Delete(int i, List PtrL)
{
int j;
if (i<1 || i>PtrL->Last + 1) {
printf("The %d item(s) no exist.", i);
return;
}
for (j = i;j <= PtrL->Last;j++)
PtrL->Data[j - 1] = PtrL->Data[j];
PtrL->Last--;
return;
}
4 선형 표 의 체인 식 저장 실현
기본 구 조 는 다음 과 같다.
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
List Next;
};
struct LNode L;
List PtrL;
4.1 구 표장:
int Length(List PtrL)
{
List p = PtrL;
int j = 0;
while (p) {
p = p->Next;
j++;
}
return j;
}
4.2 찾기:
(1) 번호 로 찾기:
List FindKth(int K, List PtrL)
{
List p = PtrL;
int i = 1;
while (p != NULL && i < K) {
p = p->Next;
i++;
}
if (i == K)
return p;
else
return NULL；
}
(2) 값 으로 찾기:
List Find(ElementType X, List PtrL)
{
List p = PtrL;
while (p != NULL && p->Data != X)
p = p->Next;
return p;
}
4.3 삽입
List Insert(ElementType X, int i, List PtrL)
{
List p, s;
if (i == 1) {
s = (List)malloc(sizeof(struct LNode));
s->Data = X;
s->Next = PtrL;
return s;
}
p = Findkth(i - 1, PtrL);
if (p == NULL) {
printf("Parameter i Error!");
return NULL;
}
else
{
s=(List)malloc(sizeof(struct LNode));
s->Data = X;
s->Next = p->Next;
p->Next = s;
return PtrL;
}
}
4.4 삭제
List Delete(int i, List PtrL)
{
List p, s;
if (i == 1) {
s = PtrL;
if (PtrL != NULL)
PtrL = PtrL->Next;
else
return NULL;
free(s);
return PtrL;
}
p = FindKth(i - 1, PtrL);
if (p = NULL) {
printf("The %d intersection no exist.", i - 1);
return NULL;
}
else if (p->Next == NULL) {
printf("The %d intersection no exist.", i);
return NULL;
}
else {
s = p->Next;
p->Next = s->Next;
free(s);
return PtrL;
}
}
5. 광의 표 와 다 중 링크
5.1 광의 표
예: 이원 다항식 을 어떻게 표시 합 니까?
기본 형식 은 다음 과 같 습 니 다.
typedef struct GNode *GList;
struct GNode {
int Tag;
// ：0 ；1 。
union {
// SubList Data ， 。
ElementType Data;
GList SubList;
}
URegion;
GList Next;
};
5.2 다 중 링크
실례: 행렬 의 표시.
2 차원 배열 로 표시 하면 두 가지 결함 이 있 습 니 다.
[분석] 전형 적 인 다 중 링크 인 십자 링크 로 희소 행렬 을 저장 합 니 다.
#include 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
