선형 표 - 순서 표 및 링크

본 고 는 다음 과 같은 내용 을 포함한다.
1. 선형 표 의 소개 와 추상 적 인 ADT
2. 순서 표 및 순서 표 의 실현
3. 링크 와 링크 의 실현
4. 순서 표 와 링크 의 비교
총화
참고서 목록: [미] Clifford A. Shaffer 저
1. 선형 표 의 소개 와 추상 적 인 ADT
1. 선형 표 는 무엇 입 니까?
키워드: 선형, 질서, 유한.
선형 이란 하나의 요소 가 하나의 선 처럼 배출 되 는 원소 이다.흩 어 져 있 거나 한 무더기 씩 쌓 여 있 는 것 이 아니다.
질서 란 표 의 요소 가 작은 것 에서 큰 것 으로 배열 되 거나 큰 것 에서 작은 것 으로 배열 되 는 것 이 아니 라 모든 요소 가 자신의 위치 가 있다 는 것 이다.
이른바 유한 이란 표 중의 원소 개 수 는 무한 다 할 수 없다.
2. 선형 표 는 어떤 속성 과 조작 이 있어 야 합 니까?
속성: 표 머리, 표 꼬리, 길이.
조작: 첨삭 검사
선형 표 에서 가장 중요 한 개념 은 현재 위치 이 고 모든 조작 은 현재 위치 에 대한 조작 이다.
예 를 들 어 getvalue () 는 현재 위치의 값 을 얻 고 insert () 는 현재 위치 에 요 소 를 추가 합 니 다. reove () 는 현재 위치의 요 소 를 제거 합 니 다.
3. 추상 ADT

template
class List {
private:
	void operator = (const List&) {};
	List(const List&);
	
public:
	List() {};
	virtual ~List() {};


	virtual void clear()=0;

	virtual void insert(const E&it)=0;
	virtual void append(const E&it)=0;
	virtual E remove()=0;

	virtual void moveToStart() =0;
	virtual void moveToEnd()=0;
	virtual void pre()=0;
	virtual void next()=0;

	virtual int length()const = 0;
	virtual int currPos()const = 0;
	virtual void moveToPos(int pos) = 0;
	virtual const E& getValue()const {};
};

4. 추상 적 인 ADT 에 대한 설명
상수 참조 매개 변수, 상수 함수, 상수 참조 반환 값
상수 참조 매개 변수:
4. 567913. 상수 인용 은 함수 가 조작 과정 에서 인 용 된 매개 변수의 값 을 바 꾸 지 않도록 확보한다.
상수 함수

virtual void insert(const E&it)=0;
virtual void append(const E&it)=0;

virtual int length()const = 0;
virtual int currPos()const = 0;

일반 구성원 함 수 는 데이터 구성원 을 업데이트 할 수 없습니다. 그 자체 가 읽 기 전용 함수 입 니 다.
한 대상 의 모든 구성원 함 수 는 이 대상 을 가리 키 는 숨겨 진 this 지침 을 되 돌려 줍 니 다. 일반 구성원 함수 에 대해 서 는 항상 this 지침 을 되 돌려 줍 니 다.

	virtual int length()const = 0;
	virtual int currPos()const = 0;

상수 참조 반환 값
4. 567913. 일반 구성원 함수 가 대상 의 인용 을 되 돌려 주 려 면 일반적인 인용 을 되 돌려 야 합 니 다.
다시 말 하면, 만약 상 함수 가 되 돌아 오 는 내용 이 this 대상 의 일부분 이 라면, 상 인용 을 되 돌려 야 한다.
2. 순서 표 및 순서 표 의 실현
1. 순서 표 는 무엇 입 니까?
   순서 표 는 배열 을 통 해 이 루어 지 는 선형 표 이다.
2. 순서 표 는 어떤 속성 을 가 져 야 합 니까?
   max size, length, curr 및 배열 지침
3. 순서 표 의 실현

	virtual int length()const = 0;
	virtual int currPos()const = 0;

3. 링크 와 링크 의 실현
1. 링크 는 무엇 입 니까?
하나의 독립 된 결점 을 사용 하여 실현 하 는 선형 표 는 모든 독립 된 결점 은 현재 결점 의 값 과 다음 요 소 를 가리 키 는 지침 을 포함한다.
링크 는 상대 적 인 위 치 를 강조 한다.
2. 링크 에는 어떤 속성 이 있어 야 합 니까?
length, 머리 를 가리 키 는 머리 지침 head, 현재 결점 을 가리 키 는 지침 curr (실제로 이 지침 은 현재 결점 오른쪽 에 있 는 결점 을 가리 키 며, 뒤에 원인 을 설명 합 니 다)
상수 시간 내 에 꼬리 에 대한 접근 을 실현 하기 위해 서 는 꼬리 점 을 가리 키 는 tail 지침 이 필요 합 니 다.
링크 가 비어 있 을 때 head 를 만 들 수 있 는 요소 가 없습니다. curr tail 은 함 수 를 삽입 하거나 삭제 하 는 데 특별한 처리 코드 가 필요 합 니 다. 오 류 를 간편 하고 줄 이기 위해 서 는
우 리 는 특수 한 머리 결점 을 도입 했다. 이 노드 는 표 두 를 나타 내 고 값 이 없 으 며 지침 은 다음 요 소 를 가리킨다. 링크 가 비어 있 을 때, 시계 끝 에 있 는 포인터 가 NULL 을 가리 키 고 있 습 니 다. 
3. 링크 의 실현

virtual const E& getValue()const {};

#include
#define default size 100
template
class AList {
private:
	E* list;
	int lenght;
	int maxsize;
	int curr;
public:
	AList(int size = defaultsaize){
		maxsize = size;
		length = 0;
		curr = 0;
		list = new E[maxsize];//
	}
	~AList() {
		delete[] list;
	}

	void clear(){
		delete[] list;
		length = curr = 0;
		list = new E[maxsize];
	}

	void moveToStart() {
		curr = 0;
	};

	void moveToEnd() {
		if (length > 0)curr = length - 1;
		else
			curr = 0;
	};

	void pre() {
		if (curr > 0)curr = curr - 1;
	};

	void next() {
		if (curr + 1 < maxsize)curr + curr + 1;
	};

	int insert(const E&item){
		assert(length < maxsize, "    ");
	// curr           
		for (int i = length; i > curr; i--)
			list[i] = list[i - 1];
		list[curr] = item;
		length++;
		return item;
	}

	int remove(){
	// curr         
		assert(curr>=0&&curr= 0 && curr < length, "No element");
		return list[curr];
	}
};

template
  
4. 순서 표 와 링크 의 비교
임의의 위치 에 접근 하면 순서 표 의 시간 은 상수 이 고 링크 는 일정 하지 않다.
임의의 위치 에 요 소 를 삽입 하고 링크 의 시간 은 상수 이 며 선형 표 는 일정 하지 않다.
공간 적 으로 체인 시계의 바늘 은 왕왕 더 많은 공간 을 차지 하지만 체인 시계의 길 이 는 처음부터 고정 하지 않 아 도 편리 하 다.선형 표 는 그 에 게 max size 를 주어 야 하 며, max size 를 초과 한 부분 은 사용 할 수 없다.
총화
선형 표, 링크, 순서 표를 복습 했다.
잊 혀 진 지식: 매개 변수, 일반 구성원 함수, 자주 참조 되 돌아 오 는 값
주의: const 는 항상 왼쪽 에 한정 적 인 역할 을 합 니 다. 자신 이 이미 왼쪽 에 있 지 않 는 한.