2019 왕도 의 - 선형 표
5808 단어 왕도
1. 선형 표 의 정의
선형 표 는 같은 데이터 형식의 n (n > = 0) 개 데이터 요 소 를 가 진 유한 한 서열 이다.그 중에서 n 은 표 길이 이 고 n = 0 일 때 이 선형 표 는 빈 표 이다.L 로 선형 표를 명명 하면 일반적으로 다음 과 같이 표시 합 니 다.
L=(a1,a2,a3...ai,ai+1...an)
그 중에서 a1 은 유일한 첫 번 째 데이터 요소 이 고 표 두 요소 라 고도 부른다.an 은 유일한 마지막 데이터 요소 로 표 미 요소 라 고도 부른다.첫 번 째 요 소 를 제외 하고 모든 요 소 는 하나의 직접적인 선구자 만 있다.마지막 요 소 를 제외 하고 모든 요 소 는 하나의 직접 후계 만 있다.이상 은 선형 표 의 논리 적 특성 이다. 이런 선형 질서 있 는 논리 구 조 는 바로 선형 표 이름 의 유래 이다.
표 의 나무 에 한계 가 있다.
표 에서 요 소 는 논리 적 인 순서 성 을 가지 고 서열 에서 각 요소 의 정렬 은 선후 순서 가 있다.
표 의 요 소 는 모두 데이터 요소 이 고 모든 요 소 는 하나의 요소 입 니 다.
표 에 있 는 요소 의 데이터 형식 이 모두 같 습 니 다.이것 은 모든 요소 가 같은 크기 의 공간 을 차지 하고 있다 는 것 을 의미한다.
표 중의 요 소 는 추상 성 을 가지 고 있다.원소 간 의 논리 적 관계 만 논의 하고 원소 가 어떤 내용 을 표시 하 는 지 는 고려 하지 않 는 다 는 것 이다.
주의: 선형 표 는 일종 의 논리 구조 로 원소 간 의 일대일 의 인접 관 계 를 나타 낸다.순서 표 와 링크 는 저장 구 조 를 말 하 는데 이들 은 서로 다른 차원 의 개념 에 속 하기 때문에 헷 갈 리 지 마라.
2. 선형 표 의 기본 조작
하나의 데이터 구조의 기본 조작 은 가장 핵심 적 이 고 기본 적 인 조작 을 가리킨다.다른 비교적 복잡 한 조작 은 그 기본 조작 을 호출 하여 실현 할 수 있다.선형 표 의 주요 조작 은 다음 과 같다.
InitList(&L) : 。 。
Length(L) : 。 L ， L 。
LocateElem(L,e): 。 L 。
GetElem(L,i): 。 L i 。
ListInsert(&L,i,e): 。 L i e。
ListDelete(&L,i,&e): 。 L i ， e 。
PrintList(L): 。 L 。
Empty(L) : 。 L ， true, false.주의: 기본 작업 의 실현 은 어떤 저장 구 조 를 사용 하 느 냐 에 달 려 있 고 저장 구조 가 다 르 며 알고리즘 의 실현 도 다르다.
선형 표 의 정 의 는 유한 한 서열 이 고 논리 적 인 관 계 를 가진다.
집합 중의 한 요 소 는 앞 뒤 구동 관계 가 없 기 때문에 선형 표 가 아니다.
인접 표 는 저장 구조 이 고 선형 표 는 논리 구조 이다.
2. 선형 표 의 순서 표시
1. 선형 표 의 순서 저장 은 순서 표 라 고도 부른다.그것 은 선형 표 의 데이터 요 소 를 순서대로 저장 하 는 주소 연속 저장 장치 이다.
선형 표 L 저장 의 시작 위 치 를 LOC (A) 로 가정 하고 sizeof (ElemType) 는 모든 데이터 요소 가 저장 공간 을 차지 하 는 크기 입 니 다.
선형 표 의 요소 유형 을 ElemType 이 라 고 가정 하고 선형 표 의 순서 저장 유형 은 다음 과 같다.
#define MaxSize 50 //
typedef struct{
ElemType data[MaxSize]; //
int length; //
}SqList; // 1 차원 배열 은 정적 으로 분 배 될 수도 있 고 동적 으로 분 배 될 수도 있다.정적 분 배 를 할 때 배열 의 크기 와 공간 이 고정 되 어 있 기 때문에 공간 이 가득 차 면 새로운 데 이 터 를 추가 하면 넘 쳐 프로그램 이 무 너 집 니 다.
한편, 동적 분 배 를 할 때 배열 을 저장 하 는 공간 은 프로그램 이 실행 하 는 과정 에서 동적 저장 배분 문 구 를 통 해 분 배 된 것 이다. 데이터 공간 이 가득 차 면 더 큰 저장 공간 을 만들어 원래 의 저장 공간 을 교체 할 수 있다.저장 소 배열 공간 을 확장 하 는 목적 을 달성 할 수 있다.
#define InitSize 100 //
typedef struct{
ElemType *data; //
int MaxSize,length; //
}SeqList; // c 의 초기 동적 할당 문:
L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);C + + 의 초기 동적 할당 문 구 는 다음 과 같 습 니 다.
L.data = new ElemType[InitSize];주의: 동적 분 배 는 체인 식 저장 이 아니 라 순서 저장 구조 에 속 합 니 다. 그 물리 구 조 는 변화 가 없고 랜 덤 저장 방식 입 니 다. 분 배 된 공간 크기 는 실행 할 때 결정 할 수 있 습 니 다.
2. 순서 표 기본 작업 의 실현
(1) 삽입 동작
순서 표 L 의 제 i (1 < = i < = L. length + 1) 개 위치 에 새 요소 e 를 삽입 합 니 다.i 의 입력 이 합 법 적 이지 않 으 면 false 로 돌아 가 삽입 에 실 패 했 음 을 표시 합 니 다.그렇지 않 으 면 순서 표 의 i 번 째 요소 와 그 후의 모든 요 소 를 오른쪽으로 한 칸 이동 시 키 고 빈 위 치 를 비 워 새로운 요소 e 를 삽입 합 니 다. 순서 표 의 길 이 를 1 증가 시 키 고 삽입 에 성공 하면 true 로 돌아 갑 니 다. (C + 참조 참조 참조 참조 참조 참조 참조 참조 참조)
bool ListInsert(SqList &L, int i, ElemType e){
if(L.length >= MaxSize) //
return false;
if(1<=i && i <= L.length + 1){
for(int j = L.length;j >= i;j-- )
L.data[j] = L.data[j - 1];
L.data[i-1] = e; // i i-1， i e，
L.length++;
return true;
}else{
return false;
}
} 가장 좋 은 상황: 표 끝 에 i = n + 1 을 삽입 하고 요소 후 이동 문 구 는 실행 되 지 않 으 며 시간 복잡 도 는 O (1) 입 니 다.
최 악의 경우: 표 머리 에 삽입 (즉 i = 1) 하고 요소 후 이동 문 구 는 n 회 실행 되 며 시간 복잡 도 는 O (n) 입 니 다.
평균 상황: pi (pi = 1 / (n + 1) 가 i 번 째 위치 에 노드 를 삽입 할 확률 이 라 고 가정 하면 길이 가 n 인 선형 표 에 노드 를 삽입 할 때 필요 한 이동 노드 의 평균 횟수 는 n / 2 이다.
(2) 삭제 작업
순서 표 L 의 i (1 < = i < = l. length) 개 위치의 요 소 를 삭제 하고 true 를 성공 적 으로 되 돌려 주 며 삭 제 된 요 소 를 인용 변수 e 로 되 돌려 줍 니 다. 그렇지 않 으 면 false 로 되 돌려 줍 니 다.
bool ListDelete(SqList & L, int i, ElemType &e){
if(1 > i || L.length < i)
return false;
e = L.data[i-1];
for(int j = i;j 가장 좋 은 상황 은 팀 의 꼬리 요 소 를 삭제 하고 이동 할 필요 가 없 으 며 시간 복잡 도 는 O (1) 입 니 다.
최 악의 경우, 헤더 요 소 를 삭제 하려 면 n - 1 회 이동 해 야 합 니 다. 시간 복잡 도 는 O (n) 입 니 다.
평균 상황: 필요 한 이동 노드 의 평균 횟수 는: (n - 1) / 2 이다. O(n)
(3) 값 으로 찾기
순서 표 L 에서 첫 번 째 요소 값 이 e 인 요 소 를 찾 고 그 위 치 를 되 돌려 줍 니 다.
int LocatElem(SqList L,ElemType e){
for(int i = 0;i < L.length;i++){
if(L.data[i] == e)
return i+1;
}
return 0; //
} 가장 좋 은 것: 표 머리 에서 한 번 만 비교 하면 시간 복잡 도 는 O (1) 이다.
최 악: 끝 에 있 거나 존재 하지 않 습 니 다. n 회, O (n) 입 니 다.
평균 n + 1 / 2
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
2019 왕도 의 - 선형 표선형 표 는 같은 데이터 형식의 n (n > = 0) 개 데이터 요 소 를 가 진 유한 한 서열 이다.그 중에서 n 은 표 길이 이 고 n = 0 일 때 이 선형 표 는 빈 표 이다.L 로 선형 표를 명명 하면 일반...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
