[데이터 구조 초급] 선형 표 순서 표 및 그 실현
1. 선형 표 란 무엇 인가
1. 선형 표 (linear list) 는 n 개의 같은 특성 을 가 진 데이터 요소 의 유한 한 서열 이다.선형 표 는 실제 에서 광범 위 하 게 사용 되 는 데이터 구조 로 흔히 볼 수 있 는 선형 표: 순서 표, 링크, 스 택, 대기 열, 문자열.그러나
선형 표 는 물리 적 으로 저장 할 때 보통 배열 과 체인 구조의 형식 으로 저장 된다. 배열 은 물리 적 으로 나 논리 적 으로 모두 연속 적 이 고 모두 선형 이다.2. 순서 표 란 무엇 인가
순서 표 는 한 단락
의 저장 장치 로 데이터 요 소 를 순서대로 저장 하 는 선형 구조 로 일반적인 상황 에서 배열 로 저장 된다.배열 에서 데이터 의 첨삭 과 수정 을 완성 하 다.순서 표 는 일반적으로 다음 과 같이 나 눌 수 있다. 1. 정적 순서 표: 데 이 터 를 저장 하 는 공간 은 고정 적 이다.문제: 작 아 지면 부족 하고 낭비 공간 을 넓 히 면 현실 에서 실 용적 이지 않다. 2. 동적 순서 표: 데 이 터 를 저장 하 는 공간 은 동태 적 으로 성장 할 수 있 고 현실 사용 에 더욱 잘 적응 할 수 있다.
3. 순서 표 의 실현
(1) SeqList. h 순서 표 각 기능 의 인터페이스 및 함수 에 대한 설명
#include(2) SeqList. c 각 인터페이스 기능 의 실현
#include"SeqList.h"
void CheckCapacity(SeqList* pSl)
{
// ，
if (pSl->size == pSl->capacity)
{
SLDatatype* tmp = (SLDatatype*)realloc(pSl->a, sizeof(SLDatatype)*pSl->capacity * 2);
// ，
if (pSl->a == NULL)
{
printf(" ,
");
exit(-1);
}
pSl->a = tmp;
pSl->capacity *= 2;
}
}
// ；
void SeqListInit(SeqList* pSl)
{
pSl->a = (SLDatatype*)malloc(sizeof(SLDatatype)* 4);
//malloc
if (pSl->a == NULL)
{
printf("malloc fail
");
exit(-1);
}
memset(pSl->a, 0,sizeof(SLDatatype) * 4);
pSl->size = 0;
pSl->capacity = 4;
}
// ；
void SeqListDestory(SeqList* pSl)
{
free(pSl->a);
pSl->a = NULL;
pSl->size = 0;
pSl->capacity = 0;
}
//
void SeqListPrint(SeqList* pSl)
{
for (int i = 0; i < pSl->size; ++i)
{
printf("%d ", pSl->a[i]);
}
printf("
");
}
//
void SeqListPushBack(SeqList* pSl, SLDatatype x)
{
assert(pSl);
CheckCapacity(pSl);
// ， a[size]
pSl->a[pSl->size] = x;
pSl->size++;
}
//
void SeqListPushFront(SeqList* pSl, SLDatatype x)
{
assert(pSl);
CheckCapacity(pSl);
//
int end = pSl->size - 1;
while (end >= 0)
{
pSl->a[end + 1] = pSl->a[end];
--end;
}
//x
pSl->a[0] = x;
pSl->size++;
}
//
void SeqListPopBack(SeqList* pSl)
{
assert(pSl);
// size 0 size-- -1
assert(pSl->size > 0);
pSl->size--;
}
//
void SeqListPopFront(SeqList* pSl)
{
assert(pSl);
assert(pSl->size > 0);
int begin = 1;
//
while (begin < pSl->size)
{
pSl->a[begin - 1] = pSl->a[begin];
++begin;
}
pSl->size--;
}
// , ， ，
SLDatatype SeqListFind(SeqList* pSl, SLDatatype x)
{
assert(pSl);
for (int i = 0; i < pSl->size; ++i)
{
if (pSl->a[i] == x)
{
return i;
}
}
return -1;
}
// pos
void SeqListInsert(SeqList* pSl, int pos, SLDatatype x)
{
assert(pSl);
assert(pos >= 0 && pos < pSl->size);
CheckCapacity(pSl);
int end = pSl->size - 1;
while (end >= pos)
{
pSl->a[end + 1] = pSl->a[end];
--end;
}
pSl->a[pos] = x;
pSl->size++;
}
// pos
void SeqListErase(SeqList* pSl, int pos)
{
assert(pSl);
assert(pos >= 0 && pos < pSl->size);
while (pos < pSl->size - 1)
{
pSl->a[pos] = pSl->a[pos + 1];
++pos;
}
pSl->size--;
}
(3) test. c 는 각종 기능 을 테스트 하 는 데 사용 된다.
#include"SeqList.h"
int main()
{
SeqList Sl;
//
SeqListInit(&Sl);
//
SeqListPushBack(&Sl, 1);
SeqListPushBack(&Sl, 2);
SeqListPushBack(&Sl, 3);
SeqListPushBack(&Sl, 4);
SeqListPushBack(&Sl, 5);
SeqListPrint(&Sl);
//
SeqListPushFront(&Sl, 0);
SeqListPrint(&Sl);
//
SeqListPopBack(&Sl);
SeqListPopBack(&Sl);
SeqListPrint(&Sl);
//
SeqListPopFront(&Sl);
SeqListPrint(&Sl);
SeqListFind(&Sl,1);
SeqListPrint(&Sl);
// pos
SeqListInsert(&Sl, 1, 20);
SeqListPrint(&Sl);
// pos
SeqListErase(&Sl, 0);
SeqListPrint(&Sl);
//
int pos = SeqListFind(&Sl, 3);
if (pos != -1)
{
printf(" 3
");
}
//
int pos1 = SeqListFind(&Sl, 2);
if (pos1 != -1)
{
SeqListErase(&Sl, pos1);
}
SeqListPrint(&Sl);
//
SeqListDestory(&Sl);
return 0;
}
이 순서 표 test. c 는 각 기능 이 정상 적 인지 테스트 하기 위해 서 입 니 다. 최적화 가 필요 하 다 면 스스로 수정 할 수 있 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
하나의 단일 체인 테이블의 순환과 귀속 실현을 반전시키다텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
