선형 표 의 순서 표
4160 단어 데이터 구조+알고리즘
선형 표 의 정 의 는 N 개 (N > = 0) 노드 나 표 항목 으로 구성 되 는데 그 는 유한 수열 이 고 인접 관 계 는 1: 1 이 며 두 가지 가 있다. 질서 와 무질서 이다.
선형 표 는 서로 다른 데이터 유형 을 가 질 수 있다. 예 를 들 어 광의 표, 광의 표 에서 요소 자체 가 특정한 구 조 를 가지 고 선형 표 에 속 하 며 선형 표 의 보급 이다.
선형 표 는 두 가지 저장 방식 이 있 는데 그것 이 바로 순서 저장 과 체인 저장 이다. 배열 을 바탕 으로 하 는, 체인 테이블 을 바탕 으로 하 는, 산열 표시 가 있다.
순서 표 는 배열 의 순 서 를 바탕 으로 저장 되 며, 그 순서 로 한 번 방문 하거나 무 작위 로 접근 할 수 있 으 며, 각 표 항목 의 저장 공간 은 같 습 니 다.
주의: 표 의 시작 요 소 는 1 에서 시작 되 고 배열 은 0 에서 시작 되 며 m 번 째 표 항목 은 배열 m - 1 개 에 대응 합 니 다.
저장 소 는 정적 저장 소 와 동적 저장 소로 나 뉘 는데 동적 저장 소 는 저장 공간 을 확장 하여 유연성 을 높 일 수 있다
Search, Locate, getDatas 라 는 몇 가지 함수 정의 에서 상 함수 const 입 니 다. const 구성원 함수 가 실 행 될 때 비 const 구성원 함 수 를 호출 할 수 없 기 때문에 함수 가 대상 의 함수 값 을 바 꿀 수 없 음 을 나타 냅 니 다.
선형 표 의 각 상용 함수 표시
1. 함수 검색, X 와 같은 값 이 있 으 면 표 형 몇 번 째 요 소 를 되 돌려 줍 니 다.
int SeqList::search(T& x)const{
for(int i=0;i<=last;i++)
if(data[i] == x) return i+1;
return 0;
} 2. 함 수 를 삽입 하여 X 를 i (0 < = i < = last + 1) 개 표 항목 에 삽입 합 니 다. 첫 번 째 앞 에 꽂 으 면 마지막 뒤에 꽂 을 수 있 기 때문에 0 부터 last + 1 까지 끝 납 니 다.
bool SeqList::Insert(int i ,T& x){
if(last == maxSize-1) return false; // ，
if(i<0 || i>last+1) return false; //i ，
for(int j = last;j>=i;j--)
data[j+1] = data[j]; // ， i
data[i] = x; //
last++;
return true;
} 마지막 부터 시작 해서 옮 겨 서 이 루어 지 는 방향 을 사용 합 니 다. 이 방향 은 바 꿀 수 없습니다. 앞에서 시작 할 수 없습니다. 아래 는 이것 입 니 다.
잘못된 예, 주의 하 세 요. 잘못된 것 입 니 다.
bool SeqList::Insert(int i ,T& x){
if(last == maxSize-1) return false; // ，
if(i<0 || i>last+1) return false; //i ，
for(int j = i;j 3. 함 수 를 삭제 합 니 다. 값 은 X 의 삭제 와 같 습 니 다.
bool SeqList::Remove(int i ,T& x){
if(last == -1) return false; // ，
if(i<1 || i>last+1) return false; //i ，
for(int j = i;j<=last;j++)
data[j-1] = data[j]; //
last--;
return true;
} 이것 은 앞에서 부터 입 니 다. 순 서 는 변 하지 않 습 니 다. 뒤에서 앞으로 밀 면 데이터 가 지 워 집 니 다. 모두 data [last] 입 니 다.
3.2 X 인 모든 요소 삭제
void deleteValue(SeqList& L,DataType x){
int i,k=0; // X
for(i=0;i3.3 표 의 중복 요소 삭제
int deleteSame(SeqList& L){
int i,k=1;
if(L.n == 0) return 0;
for(i=1;i삽입 과 삭제 전에 표 가 빈 표 나 가득 찬 표 인지, 데이터 i 가 합 리 적 인지 판단 해 야 합 니 다.
순서 표 검색 알고리즘 의 시간 대 가 는 데이터 비교 횟수 평가 이 고 삽입 과 삭 제 는 순환 내 데이터 이동 횟수 에 의 해 결정 된다.
검색 알고리즘 최 악의 경우 n + 1 회 비교 (마지막 검색 i > last, 데이터 비교 없 음), 평균 횟수 n + 1 / 2
삽입 시 평균 데이터 이동 횟수 는 n / 2 이 고 삭제 시 n - 1 / 2 회 입 니 다.
순서 표 찾기 시간 복잡 도 는 O (1) 이 고 삽입 과 삭제 의 복잡 도 는 O (n) 로 삽입 과 삭 제 를 하 는 시간 대가 가 상대 적 으로 높다.
순서 표 의 응용
두 순서 표를 집합 으로 보고 '교차' 를 실현 할 수 있다.
void union(SeqList& LA,SeqList& LB){ //
int n = LA.Length(),m = LB.Length(),i,k,x;
for(i=1;i<=m;i++)
LB.getData(i,x); // B
k = LA.Search(x); // A
if(k == 0) LA.Insert(n,x);n++; // x A
}
void intersection(SeqList& LA,SeqList& LB){ //
int n = LA.Length(),m = LB.Length(),i=1,k,x;
while(i<=n){
LA.getData(i,x); // A
k = LB.Search(x); // B
if(k == 0) LA.Remove(i,x);n--; // x
}
} 좋은 웹페이지 즐겨찾기
