데이터 구조 복습 (2) 선형 표 (1) 순서 표
2814 단어 데이터 구조
0.1 선형 표 정의
같은 데이터 형식 을 가 진 n 개의 데이터 요소 의 유한 한 서열 은 일반적으로 L (a1, a2, a3... an) 주의 점 을 나타 낸다.
0.2 선구자 와 후계
첫 번 째 요소 (표 두 요소) 를 제외 하고 모든 요 소 는 하나의 전구 만 있다.마지막 요소 (표 꼬리 요소) 를 제외 하고 모든 요소 가 있 고 하나의 후계 만 있 습 니 다.
0.3 선형 표 의 특징
① 표 에서 요소 의 개 수 는 유한 한 ② 표 에서 요 소 는 선후 순서 가 있 고 논리 적 인 순서 성 을 가 진 ③ 표 에서 요 소 는 모두 데이터 요소 (단독) ④ 표 중의 요소 데이터 유형 이 같다.
1. 순서 표
선형 표 는 논리 구조 유형 으로 서로 다른 물리 구 조 를 통 해 이 루어 지고 순서 표 와 링크 를 얻 을 수 있다.
1.1 순서 표 의 정의
주소 연속 저장 장치 로 선형 표 의 데이터 요 소 를 함께 저장 하여 논리 적 으로 인접 한 데이터 요 소 를 물리 적 위치 에서 도 인접 하 게 합 니 다.
즉, 물리 적 순서 와 논리 적 순서 가 같다 는 것 이다.
구체 적 실현 은 정적 분배 와 동적 분배 로 나 눌 수 있다
2. 실현
2.1 정의
정적 할당: 배열 의 크기 를 미리 확인 합 니 다.
#define MaxSize 50// （ ）
typedef struct{
ElemType data [MaxSize];
int length;
}SqList;
동적 할당: 배열 의 크기 가 변 할 수 있 습 니 다.
#define InitSize 100
typedef struct{
ElemType *data;
int MaxSize,length;
}SeqList;
malloc: 메모리 공간 무료 신청: 메모리 공간 L. data = (ElemType *) data. malloc (size of (ElemType) * InitSize); / /Elemtype
순서 표 특징:
주요: 무 작위 방문, 첫 번 째 주소 와 요소 번 호 를 통 해 실천 O (1) 에서 지정 한 요소 의 저장 밀도 가 높 고 모든 노드 는 데이터 요소 의 논리 적 으로 인접 한 요소 의 물리 적 위치 만 저장 할 수 있 기 때문에 요 소 를 삽입 하고 죽 일 때 많은 요소 의 확장 용량 을 옮 겨 야 하기 때문에 불편 합 니 다.
2.2 초기 화
정적 할당
void InitList(SqList &L){
for(int i =0;i동적 할당
void InitList(SeqList &L){
L.data = (int *)malloc(InitSize*sizeof(int));
// int
L.length = 0;
L.MaxSize=InitSize;
}
//
void IncreaseSize(SeqList &L,int len){
int *p=L.data;
L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
for(int i=0;i2.3 삽입
O (n) 뒤에서 앞으로 삽입
// i
bool ListInsert(SqList 7L,int i,int e){
if(i>L.length+1 || i<1)
return false;
if(L.length>=MaxSize)
return false;
// i i
for(int j =L.length;j>=i;j--){
L.data[j]=L.data[j-1];
}
L.data[i-1]=e;
L.length++;
return true;
}
2.4 삭제
O (n) 이전 뒤로 삭제
//
bool ListDelete(SqList &L,int i,int &e){
if(i>L.length||i<1)
return false;
e = L.data[i-1];
for(int j =i-1;j2.5 찾기
(1) 위치 별로 찾기
O(1)
ElemType SelectList(SeqList &L,int i){
if(i>L.length || i<0)
return 0;
return L.data[i-1];
}
(2) 값 으로 찾기
O(n)
//
int GetByValue(SeqList &L,int e){
for(int i=0;i이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
