데이터 구조 배열 과 문자열

지식 요점:
직렬 의 기본 개념, 직렬 의 저장 구조 와 관련 된 조작 알고리즘;
배열 의 저장 구 조 는 순서대로 저장 되 는 상황 에서 배열 요소 와 저장 장치 의 대응 관계 이다.
희소 행렬 의 저장 구조 와 특징 및 기본 조작.
문자열 일치 알고리즘 (예: KMP 알고리즘).
문자열 의 정의: 하나 이상 의 문자 로 구 성 된 유한 서열;내부 문자 의 개 수 는 문자열 의 길이 라 고 하고 문자 의 개 수 는 0 인 것 을 빈 문자열 이 라 고 합 니 다.
꼬치 비교: 1) 길이 가 같 습 니 다.      2) 대응 하 는 위치의 원소 도 같다.
중점 문자열 의 패턴 일치 알고리즘:
1. 폭력 일치 알고리즘 (BF):
특징: 메 인 문자열 과 패턴 문자열 의 지침 이 일치 하지 않 을 때 역 추적 현상 이 발생 합 니 다 (메 인 문자열 은 지난번 일치 하 는 위치의 다음 위치 로 돌아 가 고 패턴 문자열 은 시작 위치 로 돌아 갑 니 다).

int BF(char a[],char b[]){
    int i=0,j=0;
    while(i=strlen(b)){
        return i-strlen(b);//            
    }
    return -1;//    
}

알고리즘 시간 복잡 도: 시간 복잡 도 는 O (mn) 이 고 일반적인 상황 에서 O (m + n) 는 선형 단계 이다.
2. KMP 알고리즘 (next 배열 의 계산 에 중점 을 두 고 파악):
특징: 메 인 스 트 링 포인터 가 역 추적 현상 이 발생 하지 않 고 모델 스 트 링 포인터 가 역 추적 되 지 않 습 니 다.
☆ ☆ ☆ next 배열 의 풀이 와 KMP 알고리즘 코드

void getnext(char b[]){          //next     
	int i=0,j=-1;
	next[0]=-1;                  //   next[0]=-1
	while(i=strlen(b)){
		return i-strlen(b);      //           
	}
	return -1;                   //    
}

알고리즘 해석: (패턴 문자열 의 최대 이동 을 실현 하고 중복 되 는 비교 횟수 를 줄 입 니 다) S 주 문자열, T 는 패턴 문자열 입 니 다.
메 인 문자열 의 i 번 째 문자 와 패턴 문자열 의 j 번 째 문자 가 어 울 리 지 않 는 다 고 가정 하면 패턴 문자열 의 j 는 k 위치 로 돌아 가 메 인 문자열 의 i 번 째 위치 와 비교 해 야 합 니 다.
0 - k 에는 반드시 k - 1 문자 가 메 인 문자열 의 i 위 이전의 k - 1 문자 와 일치 합 니 다. 즉, S [i - k + 1, i - 1] = T [1, k - 1]
j 에서 짝 짓 기 가 발생 하면 앞으로 의 k - 1 비트 도 메 인 문자열 과 일치 합 니 다. 즉, S [i - k + 1, i - 1] = T [i - j + 1, j - 1]
상기 두 가지 식 을 통 해 알 수 있 듯 이 패턴 문자열 이 돌아 온 위치 k 는 메 인 문자열 과 무관 하 며 각각 길이 가 같은 접두사 문자열 과 접두사 문자열 (길 이 는 k - 1) 이 고 패턴 문자열 이 돌아 갈 것 입 니 다.
의 위치 k 는 이 문자열 의 길이 + 1 (즉, 최대 접두사 와 접두사 의 공공 문자열 길이 에 1) 입 니 다.
예 를 들 어:                                      초기 화: next [1] = 0; /고정 요구
j
1
2
3
4
5
6
7
8
패턴 문자열
a
b
a
a
b
c
a
c
next[j]
0
1
1
2
2
3
1
2
next 배열 의 첫 번 째 위치 0; /고정 요구
제 2 위   접두사 와 접미사 가 없 는 공공 하위 문자열 의 길 이 는 0 이 고 next [2] = 1 입 니 다.
삼 위   접두사 와 접미사 가 없 는 공공 하위 문자열 의 길 이 는 0 이 고 next [3] = 1 입 니 다.
네 번 째   접두사 와 접미사 가 있 는 공통 하위 문자열 a, 길이 가 1 이면 next [4] = 2;
다섯 째   접두사 와 접미사 가 있 는 공통 하위 문자열 a, 길이 가 1 이면 next [5] = 2;
제6 위   접두사 와 접미사 가 있 는 공공 하위 문자열 ab, 길이 가 2 이면 next [6] = 3;
제7 위   접두사 와 접미사 가 없 는 공공 하위 문자열 의 길 이 는 0 이 고 next [7] = 1 입 니 다.
여덟 번 째   접두사 와 접미사 가 있 는 공통 하위 문자열 a, 길이 가 1 이면 next [8] = 2;
요약: next 배열 의 구 해 는 이 위치 에 있 는 문자열 중 가장 긴 일치 하 는 앞 뒤 문자열 을 찾 는 것 입 니 다. 그 길 이 는 하 나 를 더 하면 이 위치 next 배열 의 값 입 니 다.
3. 최 적 화 된 KMP 알고리즘 (next 배열 수정, 중복 일치 방지):
특징: 메 인 스 트 링 포인터 가 역 추적 현상 이 발생 하지 않 고 모델 스 트 링 포인터 가 역 추적 되 어 KML 알고리즘 에서 최적화 처 리 를 했다.
j
1
2
3
4
5
패턴 문자열
a
a
a
a
b
next[j]
0
1
2
3
4
nextval[j]
0
0
0
0
4
next 배열 에 대한 설명 이 같 습 니 다.2 - 4 위치 에서 반복 적 으로 일치 하 는 현상 이 발생 한 것 을 발 견 했 습 니 다. 즉, 2 - 4 에서 임의의 넘 침 일치 에 실 패 했 습 니 다. next 배열 은 모두 이전 위치 로 돌 아 왔 습 니 다.
그러나 이론 적 으로 최초의 위치 로 돌아 가 다시 비교 하 는 것 이 가장 좋 고 과정 에서 여러 차례 중복 비교 가 생 겼 다.
다음 위치 요소 가 이 위치 요소 와 같다 면 이 위치 next 배열 의 값 은 이전 위치의 next 배열 의 값 과 같 고, 반대로 일반 next 배열 의 값 을 따른다.
구 해 방식.
☆ ☆ ☆ nextval 배열 의 풀이

void getnextval(char b[]){
	int i=0,j=-1;
	next[0]=-1;
	while(i

배열 의 저장 구조 (일반적으로 고정 크기 의 메모리 공간 을 신청 하고 삽입 하거나 삭제 하지 않 습 니 다)
모든 데이터 요소 가 L 개의 저장 부 를 차지한다 고 가정 하면 2 차원 배열 A [0. m - 1, 0. n - 1] 에서 임의의 요소 의 저장 위 치 는?
Loc[a(i,j)]=Loc[a(0,0)]+(n*i+j)*L；(셀 수 - 1) 공간 크기 에 시작 주 소 를 곱 하기)
3. 특수 행렬 의 압축 문제 (삼각 행렬, 희소 행렬, 대칭 행렬)
1. 대칭 행렬 (행렬 은 행렬 의 전환 과 같다) 대응 요소 a (i, j) = a (j, i)
모든 요 소 를 저장 하려 면 n * n 개의 저장 장치 가 필요 하지만 성질 에 따라 절반 만 저장 하고 나머지 절반 은 성질 에 따라 내 놓 을 수 있 으 며 n * n 개의 저장 부 를 압축 할 수 있 습 니 다.
n * (n + 1) / 2 개의 저장 장치 에서;
2 차원 매트릭스 (i, j) 와 1 차원 배열 아래 표 k 의 대응 관 계 는 (아래 표 는 모두 0 부터) 이다.
열 우선 기준: k = i (i - 1) / 2 + j - 1 (i > = j);하 삼각형
줄 우선 기준: k = j (j - 1) / 2 + i - 1  （i
2. 삼각 행렬
상 삼각형 행렬: (i - 1) (2n - i + 2) / 2 + j - i; (j < = i), 상 삼각형
하 삼각형 행렬: k = i (i - 1) / 2 + j - 1 (i > = j), 하 삼각형;
3. 희소 행렬 (원소 개수 가 매우 적다): 흔히 볼 수 있 는 대각 행렬, 3 대각 행렬 이 있다.
주: 행렬 의 사용 상과 그림 의 알고리즘 은 서로 고찰 하고 행렬 에서 요소 가 배열 에 대응 하 는 위 치 를 계산 하 는 것 은 줄 이나 열의 우선 액세스 순서 에 따라 이 요소 가 행렬 에 있 는 몇 번 째 위치 에서 1 을 빼 면 이 요소 가 1 차원 배열 에 대응 하 는 위치 k 이다.
4. 광의 표 (비중 점)
정의: 선형 표 의 홍 보 는 광의 표, 요소 등 을 액세스 할 수 있 습 니 다.
A = () 빈 표, 즉 표 의 요 소 를 0 으로 정의 합 니 다. 특수 한 C = () 이 광의 표 는 빈 표 가 아니 라 길이 가 1 입 니 다.
B = (e) 는 단원 자 표 로 정의 하고 길 이 는 1 이다.
E = (a, E) 는 무한 귀속 표 로 길이 가 2 이다.
광의 표 의 특징 (결론)
1) 광의 표 의 요 소 는 하위 표 일 수 있다.
2) 광의 표 는 기이 한 광의 표 에 의 해 공유 된다.
3) 광의 표 는 재 귀 표 일 수 있다.
광의 표 의 조작: 표 헤드 getHead: 비 공 광의 표 의 첫 번 째 요 소 를 가 져 옵 니 다 (표 일 수도 있 고 단원 자 일 수도 있 습 니 다)
                          표 끝 getRear: 비 공 광의 표 의 첫 번 째 요 소 를 제거 하고 나머지 부분 (반드시 광의 표)
                          광의 표 의 깊이 Deap: 최대 서브 표 깊이 + 1;
                          광의 표 의 길이 Length: 광의 표 에서 요소 의 개수;