데이터 구조 학습 의 길 - 제2 장: 선형 표 의 순서 표시 와 실현
선언:
제1장 서론 의 워밍업 을 통 해 삼원 조 에 대한 실현 을 통 해 우 리 는 기본적으로 워밍업 을 했 고 이 책의 편성 도 낯 설 지 않 을 것 이다. 그러면 지금 은 제2 장의 학습, 선형 표 에 들 어 갔다.
이 책 은 선형 표, 제2 장 (링크), 제3 장 (스 택 과 대기 열), 제4 장 (꼬치) 을 3 장 으로 설명 했다.
이 를 통 해 선형 표 의 중요성 을 알 수 있다. 이것 은 전체 데이터 구조의 기초 라 고 할 수 있다. 만약 에 선형 표 가 잘 배우 지 못 하면 선형 표 로 연 장 된 나무, 숲, 그림 등 데이터 구조 학 도 어렵 게 될 것 이다.
그렇다면 다음은 선형 구조의 학습 에 들 어가 자.
주:
본 고 는 블 로 거들 본인 의 간단명료 한 견해 만 대표 하고 여러분 의 평론 과 학습 을 환영 하 며 공동으로 좋 은 환경 을 만 들 었 습 니 다.
일부 문제 에 대해 블 로 거들 은 가능 한 한 여러분 을 위해 해답 을 해 드 리 겠 습 니 다. 그러나 질문 이 있 으 면 제때에 대답 하지 않 았 고 다른 열정 적 인 사람들 이 해결 해 주 기 를 바 랍 니 다. 저 는 감격 해 마지 않 습 니 다.
선형 구조
정의.
선형 구 조 는 질서 있 는 데이터 요소 의 집합 이다.
자주 사용 하 는 선형 구 조 는 선형 표, 스 택, 대기 열, 더 블 대기 열, 배열, 꼬치 가 있다.
광의 표 에 관 해 서 는 비 선형 데이터 구조 이다.
흔히 볼 수 있 는 비 선형 구 조 는 2 차원 배열, 다 차원 배열, 광의 표, 나무 (이 진 트 리 등), 그림 이다.
특징.
1. 집합 에 유일한 '첫 번 째 요소' 가 존재 한다.
2. 집합 에 유일한 '마지막 요소' 가 존재 한다.
3. 마지막 요 소 를 제외 하고 다른 데이터 요 소 는 모두 유일한 '후계' 가 있다.
4. 첫 번 째 요 소 를 제외 하고 다른 데이터 요 소 는 모두 유일한 '전구' 가 있다.
데이터 구조 에서 선형 구 조 는 데이터 요소 간 에 '일대일' 의 선형 관계 가 존재 하 는 데이터 구 조 를 말한다.
예 를 들 어 (a1, a2, a3,..., an), a1 은 첫 번 째 요소 이 고 an 은 마지막 요소 이 며 이 집합 은 하나의 선형 구조의 집합 이다.
선형 구조 에 대응 하고 비 선형 구조의 논리 적 특징 은 하나의 결점 요소 가 여러 개의 직접 전구 와 여러 개의 후계 에 대응 할 수 있다 는 것 이다.
선형 표
정의.
선형 표 (순서 표) 는 가장 기본 적 이 고 간단 하 며 가장 자주 사용 하 는 데이터 구조 이다.선형 표 에서 데이터 요소 간 의 관 계 는 일대일 관계 이다. 즉, 첫 번 째 와 마지막 데이터 요 소 를 제외 하고 다른 데이터 요 소 는 모두 첫 번 째 와 끝 이 연결 되 어 있다.선형 표 의 논리 구 조 는 간단 하여 실현 과 조작 에 편리 하 다.따라서 선형 표 라 는 데이터 구 조 는 실제 응용 에서 광범 위 하 게 사용 되 는 데이터 구조 이다.
순서 표 의 순서 표시 와 실현
1. 저장 구조
책 은 매우 엄격 하고 상세 하 게 많은 순서 구조의 저장 방식 이 어떤 상황 인지 말 했다. 사실은 끝까지 말하자면 이 순서 표 는 사실은 배열 과 마찬가지 로 연속 적 인 메모리 에 저장 해 야 하 며 함부로 분포 해 서 는 안 된다 는 것 이다.
//
#define LIST_INT_SIZE 100 //
#define LISTINCREMENT 10 //
typedef struct
{
ElemType *elem; //
int length; //
int listsize; // ( sizeof(ElemType) )
}SqList;2. 빈 테이블 만 들 기
빈 테이블 을 만 들 때, 우선 elem 에 동적 으로 저장 공간 을 분배 해 야 한다
선형 표 의 현재 길 이 를 나타 내 는 length 할당 값 은 0 입 니 다.
선형 표 의 최대 용량 을 나타 내 는 listize 할당 값 은 지정 한 용량 값 입 니 다.
Status InitList(SqList *L)
{
// ：
(*L).elem = (ElemType*)malloc(LIST_INT_SIZE*sizeof(ElemType));
if(!(*L).elem) exit(OVERFLOW); //
(*L).length = 0; // 0
(*L).listsize = LIST_INT_SIZE; //
return OK;
}3. 요소 삽입
하나의 순서 표 에 있어 서 i 번 째 요 소 를 조회 하 는 것 은 매우 간단 하고 방법 은 배열 과 같다.
그러면 하나의 요 소 를 삽입 하 는 데 있어 서 우 리 는 이동 삽입 위치 와 그 후의 요 소 를 통 해 이 루어 져 야 한다.
예 를 들 어 내 가 i 번 째 위치 에 e 를 삽입 하려 면 우 리 는 원래 선형 표 안의 i ~ length - 1 위치의 수 를 모두 한 위 치 를 뒤로 이동 한 다음 에 e 를 i 위치 로 할당 해 야 한다.
Status ListInsert(SqList *L,int i,ElemType e)
{
// ： L ，1≤i≤ListLength(L)+1
// ： L i e，L 1
ElemType *newbase,*p,*q;
if(i<1||i>(*L).length+1) return ERROR; //i
if((*L).length>=(*L).listsize) // ，
{
newbase = (ElemType*)realloc((*L).elem,((*L).length+LISTINCREMENT)*sizeof(ElemType));
if(!newbase) exit(OVERFLOW); //
(*L).elem = newbase; //
(*L).listsize+=LISTINCREMENT; //
}
q = (*L).elem+i-1; //
for(p = (*L).elem+(*L).length-1; p>=q; p--) //
*(p+1) = *p;
*q = e; //
(*L).length++; //
return OK;
}4. 원소 삭제
선형 표 내 요소 의 삭 제 는 삽입 방식 과 유사 합 니 다. 삭 제 된 노드 에 대해 우 리 는 그 후의 요 소 를 모두 한 위치 로 이동 하면 됩 니 다.
Status ListDelete(SqList *L,int i,ElemType *e)
{
// ： L ，1≤i≤ListLength(L)
// ： L i ， e ，L 1
ElemType *newbase,*p,*q;
if(i<1||i>(*L).length+1) return ERROR; //i
q = (*L).elem+i-1; //
*e = *q; // e
p = (*L).elem+(*L).length-1; //
for(; q<p; q++) //
*q = *(q+1);
(*L).length--; //
return OK;
}5. 원소 비교
이것 은 표준 함수 호출 함수 의 쓰기 입 니 다. 그 방법 은 일반적인 데이터 형식의 변수 와 유사 하 며 함수 이름 을 매개 변수 로 합 니 다.
Status LocateElem(SqList L,ElemType e,Status (*compare)(ElemType,ElemType))
{
// ： L ，compare() ( 1, 0)
// ： L 1 e compare() 。 ， 0。
ElemType* p;
int i = 1; //i
p = L.elem; //p
while(i<=L.length && !(*compare)(*p++,e)) //
i++;
if(i<=L.length) return i;
return 0;
}
6. 쌍 표 병합
①. 선형 표 Lb 에 있 지만 La 에 없 는 모든 데이터 요 소 를 La 에 삽입 하고 Lb 순서 표 에 있 는 요 소 를 하나씩 옮 겨 다 니 며 La 에 있 는 요소 와 비교 하고 La 에 포함 되 지 않 으 면 La 표 의 표 끝 에 삽입 합 니 다.
void Union(SqList *La,SqList Lb)
{
// ： Lb La La
ElemType e;
int La_len,Lb_len;
int i;
La_len = (*La).length;
Lb_len = Lb.length;
for(i = 1; i<=Lb.length; i++)
{
GetElem(Lb,i,&e); // Lb i e
if(!LocateElem(*La,e,equal)) // e La
ListInsert(La,++La_len,e);
}
}②.
책 속 의 이 순서 표 의 합병 은 반드시 La 와 Lb 가 원래 질서 가 있 는 전제 에서 선형 시간 으로 같은 질서 있 는 순서 표 Lc 를 합병 해 야 한다.
관건 은 La 와 Lb 의 현재 위치 값 의 크기 를 비교 하고 작은 것 을 선택 하여 Lc 에 넣 는 것 입 니 다.
void MergeList(SqList La,SqList Lb,SqList *Lc)
{
// ： La Lb 。
// ： La Lb Lc,Lc
ElemType *pa,*pa_last,*pb,*pb_last,*pc;
pa = La.elem; //La
pb = Lb.elem; //Lb
(*Lc).length = (*Lc).listsize = La.length+Lb.length; // Lc
pc = (*Lc).elem = (ElemType*)malloc((*Lc).listsize*sizeof(ElemType)); // Lc
if(!(*Lc).elem) exit(OVERFLOW); //
pa_last = La.elem+La.length-1; //La
pb_last = Lb.elem+Lb.length-1; //Lb
while(pa<=pa_last&&pb<=pb_last) //La Lb
{
//
if(*pa<=*pb)
*pc++ = *pa++;
else
*pc++ = *pb++;
}
while(pa<=pa_last) //Lb La
*pc++ = *pa++;
while(pb<=pb_last) //La Lb
*pc++ = *pb++;
}7. 기타 조작
앞에서 소개 한 것 은 모두 책 에서 비교적 상세 하 게 서술 한 몇 가지 실현 작업 이다. 나머지 는 바로 이런 것들 은 비우 기, 길이 측정 등 을 포함 하고 구체 적 으로 실현 하 는 것 도 어렵 지 않다.
Status DestroyList(SqList *L)
{
// ： L 。
// ： L
free((*L).elem); //
(*L).elem = NULL;
(*L).length = 0;
(*L).listsize = 0;
return OK;
}
Status ClearList(SqList *L)
{
// ： L 。
// ： L
(*L).length = 0;
return OK;
}
Status ListEmpty(SqList L)
{
// ： L 。
// ： L ， TRUE， FALSE
return L.length==0;
}
int ListLength(SqList L)
{
// ： L 。
// ： L
return L.length;
}
Status GetElem(SqList L,int i,ElemType *e)
{
// ： L ，1≤i≤ListLength(L)
// ： e L i
if(i<1 || i>L.length) exit(ERROR);
(*e) = *(L.elem+i-1);
return OK;
}
Status PriorElem(SqList L,ElemType cur_e,ElemType *pre_e)
{
// ： L
// ： cur_e L ， ， pre_e ， ，pre_e
ElemType* p = L.elem+1; // ，
int i = 2;
while(i<=L.length && *p!=cur_e) // cur_e
{
i++;
p++;
}
if(i>L.length) return INFEASIBLE; //
*pre_e = *(--p); //
return OK;
}
Status NextElem(SqList L,ElemType cur_e,ElemType *next_e)
{
// ： L
// ： cur_e L ， ， next_e ， ，next_e
ElemType* p = L.elem;
int i = 1;
while(i<L.length && *p!=cur_e) // cur_e
{
i++;
p++;
}
if(i==L.length) return INFEASIBLE; //
*next_e = *(++p); //
return OK;
}
Status ListTraverse(SqList L,void (*vi)(ElemType*))
{
// ： L
// ： L vi()。 vi() ， ,vi() '&'， vi()
ElemType* p = L.elem;
int i;
for(i = 1; i<=L.length; i++)
vi(p++);
printf("
");
return OK;
}8. 구체 적 인 테스트
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
#include <ctype.h>
#include <malloc.h>
#include <limits.h>
#include <stdlib.h>
#include <io.h>
#include <process.h>
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int ElemType;
typedef int Status;
//
#define LIST_INT_SIZE 100 //
#define LISTINCREMENT 10 //
typedef struct
{
ElemType* elem; //
int length; //
int listsize; // ( sizeof(ElemType) )
} SqList;
Status InitList(SqList *L)
{
// ：
(*L).elem = (ElemType*)malloc(LIST_INT_SIZE*sizeof(ElemType));
if(!(*L).elem) exit(OVERFLOW); //
(*L).length = 0; // 0
(*L).listsize = LIST_INT_SIZE; //
return OK;
}
Status DestroyList(SqList *L)
{
// ： L 。
// ： L
free((*L).elem); //
(*L).elem = NULL;
(*L).length = 0;
(*L).listsize = 0;
return OK;
}
Status ClearList(SqList *L)
{
// ： L 。
// ： L
(*L).length = 0;
return OK;
}
Status ListEmpty(SqList L)
{
// ： L 。
// ： L ， TRUE， FALSE
return L.length==0;
}
int ListLength(SqList L)
{
// ： L 。
// ： L
return L.length;
}
Status GetElem(SqList L,int i,ElemType *e)
{
// ： L ，1≤i≤ListLength(L)
// ： e L i
if(i<1 || i>L.length) exit(ERROR);
(*e) = *(L.elem+i-1);
return OK;
}
Status PriorElem(SqList L,ElemType cur_e,ElemType *pre_e)
{
// ： L
// ： cur_e L ， ， pre_e ， ，pre_e
ElemType* p = L.elem+1; // ，
int i = 2;
while(i<=L.length && *p!=cur_e) // cur_e
{
i++;
p++;
}
if(i>L.length) return INFEASIBLE; //
*pre_e = *(--p); //
return OK;
}
Status NextElem(SqList L,ElemType cur_e,ElemType *next_e)
{
// ： L
// ： cur_e L ， ， next_e ， ，next_e
ElemType* p = L.elem;
int i = 1;
while(i<L.length && *p!=cur_e) // cur_e
{
i++;
p++;
}
if(i==L.length) return INFEASIBLE; //
*next_e = *(++p); //
return OK;
}
Status ListTraverse(SqList L,void (*vi)(ElemType*))
{
// ： L
// ： L vi()。 vi() ， ,vi() '&'， vi()
ElemType* p = L.elem;
int i;
for(i = 1; i<=L.length; i++)
vi(p++);
printf("
");
return OK;
}
Status ListInsert(SqList *L,int i,ElemType e)
{
// ： L ，1≤i≤ListLength(L)+1
// ： L i e，L 1
ElemType *newbase,*p,*q;
if(i<1||i>(*L).length+1) return ERROR; //i
if((*L).length>=(*L).listsize) // ，
{
newbase = (ElemType*)realloc((*L).elem,((*L).length+LISTINCREMENT)*sizeof(ElemType));
if(!newbase) exit(OVERFLOW); //
(*L).elem = newbase; //
(*L).listsize+=LISTINCREMENT; //
}
q = (*L).elem+i-1; //
for(p = (*L).elem+(*L).length-1; p>=q; p--) //
*(p+1) = *p;
*q = e; //
(*L).length++; //
return OK;
}
Status ListDelete(SqList *L,int i,ElemType *e)
{
// ： L ，1≤i≤ListLength(L)
// ： L i ， e ，L 1
ElemType *newbase,*p,*q;
if(i<1||i>(*L).length+1) return ERROR; //i
q = (*L).elem+i-1; //
*e = *q; // e
p = (*L).elem+(*L).length-1; //
for(; q<p; q++) //
*q = *(q+1);
(*L).length--; //
return OK;
}
Status comp(ElemType a,ElemType b)
{
// ： a b ， 1， 0
if(a == b*b)
return TRUE;
return FALSE;
}
Status equal(ElemType a,ElemType b)
{
return a==b;
}
void Print(ElemType *e)
{
printf("%d ",*e);
}
Status LocateElem(SqList L,ElemType e,Status (*compare)(ElemType,ElemType))
{
// ： L ，compare() ( 1, 0)
// ： L 1 e compare() 。 ， 0。
ElemType* p;
int i = 1; //i
p = L.elem; //p
while(i<=L.length && !(*compare)(*p++,e)) //
i++;
if(i<=L.length) return i;
return 0;
}
void Union(SqList *La,SqList Lb)
{
// ： Lb La La
ElemType e;
int La_len,Lb_len;
int i;
La_len = (*La).length;
Lb_len = Lb.length;
for(i = 1; i<=Lb.length; i++)
{
GetElem(Lb,i,&e); // Lb i e
if(!LocateElem(*La,e,equal)) // e La
ListInsert(La,++La_len,e);
}
}
void MergeList(SqList La,SqList Lb,SqList *Lc)
{
// ： La Lb 。
// ： La Lb Lc,Lc
ElemType *pa,*pa_last,*pb,*pb_last,*pc;
pa = La.elem; //La
pb = Lb.elem; //Lb
(*Lc).length = (*Lc).listsize = La.length+Lb.length; // Lc
pc = (*Lc).elem = (ElemType*)malloc((*Lc).listsize*sizeof(ElemType)); // Lc
if(!(*Lc).elem) exit(OVERFLOW); //
pa_last = La.elem+La.length-1; //La
pb_last = Lb.elem+Lb.length-1; //Lb
while(pa<=pa_last&&pb<=pb_last) //La Lb
{
//
if(*pa<=*pb)
*pc++ = *pa++;
else
*pc++ = *pb++;
}
while(pa<=pa_last) //Lb La
*pc++ = *pa++;
while(pb<=pb_last) //La Lb
*pc++ = *pb++;
}
int main()
{
SqList L,La,Lb,Lc;
Status i;
ElemType e,e0;
int n,k;
//
i = InitList(&L);
if(i)
printf(" ， length=%d， listsize=%d
",L.length,L.listsize);
else
{
printf("
");
return 0;
}
puts("");
//
printf(" ：");
scanf("%d",&n);
printf(" ：");
for(k = 1; k<=n; k++)
{
scanf("%d",&e);
ListInsert(&L,k,e);
}
printf(" ：");
ListTraverse(L,Print);
//
printf(" ：");
scanf("%d",&n);
ListDelete(&L,n,&e);
printf(" ：%d
",e);
printf(" ：");
ListTraverse(L,Print);
//
printf(" (1~5) ：
");
for(n = 1; n<=5; n++)
{
i = LocateElem(L,n,comp);
if(i)
printf(" %d %d
",i,n);
else
printf(" %d
",n);
}
puts("");
//
InitList(&La);
InitList(&Lb);
for(n = 1; n<=5; n++)
ListInsert(&La,n,n);
for(n = 1; n<=5; n++)
ListInsert(&Lb,n,n*n);
printf(" La ：
");
ListTraverse(La,Print);
printf(" Lb ：
");
ListTraverse(Lb,Print);
MergeList(La,Lb,&Lc);
Union(&La,Lb);
printf("MergeList La,Lb ,Lc ：
");
ListTraverse(Lc,Print);
printf("Union La,Lb ,La ：
");
ListTraverse(La,Print);
//
i = ListEmpty(Lb);
printf("Lb ：%d(1: 0: )
",i);
ClearList(&Lb);
i = ListEmpty(Lb);
printf(" Lb ，Lb ：%d(1: 0: )
",i);
i = ListLength(La);
printf("La ：%d
",i);
GetElem(La,3,&e);
printf("La 3 ：%d
",e);
printf(" La ：
");
for(k = 1; k<=2; k++)
{
GetElem(La,k,&e0);
i = PriorElem(La,e0,&e);
if(i==INFEASIBLE)
printf(" %d
",e0);
else
printf(" %d %d
",e0,e);
}
for(k = ListLength(La)-1; k<=ListLength(La); k++)
{
GetElem(La,k,&e0);
i = NextElem(La,e0,&e);
if(i==INFEASIBLE)
printf(" %d
",e0);
else
printf(" %d %d
",e0,e);
}
i = DestroyList(&La);
if(i)
printf("La
");
return 0;
}
요약:
이 코드 들 을 두 드 리 는 데 많은 노력 을 기 울 였 다. 기본적으로 책의 템 플 릿 에 따라 두 드 렸 지만 이 코드 의 길이 도 쉽게 완성 할 수 있 는 프로젝트 가 아니 라 는 것 을 결정 했다.
이 절 은 주로 순서 표 의 조작 과 실현 을 이 야 기 했 는데 제 블 로 그 를 보고 여러분 께 도움 이 되 었 는 지 모 르 겠 습 니 다.
전체적으로 보면 순서 표 는 선형 표 에서 실현 되 는 것 이 가장 간단 해 야 한다. 왜냐하면 그의 일부 조작 은 배열 과 거의 차이 가 없 기 때문에 일정한 기초 가 되 는 학생 이 있 으 면 배열 에 대해 낯 설 지 않 을 것 이다.
자, 이번 에는 여기까지 입 니 다. 다음 에는 링크 공 부 를 하 겠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
