데이터 구조 (1) 선형 표, 스 택 과 대기 열
3153 단어 본과 총화
선형 표 의 순서 표시 와 실현
선형 표 의 순 서 는 한 그룹의 주소 로 연속 적 인 저장 공간 으로 선형 표를 한 번 에 저장 하 는 데이터 요 소 를 말한다.(연속 공간, 정적 링크)
순차 기억 장치
일반적으로 데이터 구조 중의 순서 저장 구 조 를 배열 로 묘사한다.정 의 는 다음 과 같 습 니 다.
typedef struct{
ElemType *elem; // ;
int legth; // ;
int listsize; // ;
}SqList;
1. 구조 선형 표
구조 공 선형 표, 선형 표 초기 화.
status InitList_Sq(SqList &L){
L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem) exit(OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return ok;
}
2. 삽입
선형 표 의 i - 1 원소 와 i 원소 사이 에 원소 b 를 삽입 합 니 다.선형 표 는 (a1, a2...............................................................................원소 b 를 삽입 한 후, 뒤에 ai 를 an 원소 순서 로 이동 합 니 다.
3. 삭제
삽입 과 비슷 합 니 다. 요 소 를 삭제 한 후 다음 요소 순서 로 위 치 를 이동 합 니 다.
선형 표 사슬 식 표시
선형 링크
선형 표 의 단일 체인 표 저장 구조
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
1. 간단 한 삭제, 삽입
2. 역방향 으로 링크 만 들 기
이전에 만난 요 소 는 모두 정방 향 입력 이 었 습 니 다. 만약 지금 역방향 으로 입력 한 데 이 터 를 준다 면.예 를 들 어 예전 에 1, 2, 3, 4 를 제시 하여 정방 향 링크 를 만 들 었 다.현재 4, 3, 2, 1 을 제시 하고 1, 2, 3, 4 순서의 체인 테이블 을 만들어 야 한다.이렇게 하려 면 역방향 으로 링크 를 만 들 고 마지막 으로 머리 를 만들어 야 한다.
3. 링크 의 병합
만약 에 두 개의 링크 가 질서 가 있다 면 n 의 시간 복잡 도 에서 제자리 에서 합병 할 수 있다.
정적 링크
정적 링크 의 저장 구 조 는 다음 과 같다.
typedef struct {
ElemType data;
int cur;
}component,SLinkList[MAXSIZE];
모든 링크 는 2 차원 의 배열 로 볼 수 있 고 모든 요 소 는 물리 적 으로 인접 하지만 논리 적 으로 반드시 인접 한 것 은 아니다.이것 이 바로 순서 표 와 의 차이 이다.그래서 모든 요소 의 논리 적 위 치 를 저장 해 야 합 니 다.
순환 링크
그것 의 특징 은 표 의 마지막 노드 의 지침 역 이 머리 결점 을 가리 키 고 전체 체인 표 가 하나의 고 리 를 형성 하 는 것 이다.
양 방향 링크
일원 다항식 의 표시 및 더하기
창고 와 대열
창고.
순서 스 택 은 한 그룹의 주소 연속 저장 부 를 이용 하여 스 택 밑 에서 스 택 꼭대기 까지 의 요 소 를 순서대로 저장 하 는 동시에 포인터 top 을 설치 하여 스 택 꼭대기 요소 가 순서 스 택 에 있 는 위 치 를 표시 합 니 다.
디지털 변환
예 를 들 어 (1348) 10 = (2504) 8
void conversion(){
InitStack();
scanf("%d", &N);
while(N){
push(N%8);
N /= 8;
}
while(!StackEmpty()){
Pop(S,e);
printf("%d",e);
}
}`
괄호 일치 검사
미궁
bfs 너비 검색, 일반 대기 열 사용
표현 식 값 구하 기
예 를 들 어 다음 표현 식 의 값 을 구하 십시오: 4 + 2 * 3 - 10 / 5
산술 사 칙 연산 의 규칙: 1. 먼저 곱 하기, 후 가감 2. 왼쪽 에서 오른쪽으로 계산 하기 3. 먼저 괄호 안, 후 괄호 외.
알고리즘 은 다음 과 같 습 니 다.
대열
일반 대기 열
연속 저장 공간 사용 가능
체인 큐
링크 가 실 현 된 대기 열.
순환 대기 열
빈 대기 열 을 초기 화 할 때 front = rear = 0, 새로운 대기 열 꼬리 요 소 를 삽입 할 때마다 꼬리 포인터 가 1 증가 하고, 대기 열 머리 요 소 를 삭제 할 때마다 머리 포인터 가 1 이 있 습 니 다.(rear + 1)% MAXQSIZE = front 이면 대기 열 이 가득 찼 음 을 표시 합 니 다.
좋은 웹페이지 즐겨찾기
