선형 표 의 배열 실현

선형 표 는 기본 적 인 데이터 구조 입 니 다. 우 리 는 이 데이터 구 조 를 작성 하려 면 몇 가지 기본 적 인 기능 을 실현 해 야 합 니 다.

새 선형 표

선형 표 에 요 소 를 삽입 합 니 다

선형 표 의 특정한 요 소 를 삭제 합 니 다

어떤 원 소 를 찾 아 라

짧 은 판정 만 료 여부

길이 변경

출력 선형 표

그리고 '고급' 기능 도 있 습 니 다.

두 선형 표 의 합병

선형 표 의 범위 내 요 소 를 삭제 합 니 다

선형 표 류

class List
{
private:
	int *list;
	int size;     //    
	int MAXSIZE;  //       
public:
	List(int ms = 0);//     
	void InsertList(int item, int rc);// rc     item
	void DeleteList1(int item);//    item   
	void DeleteList2(int rc);//     rc   
	void DeleteList3(int x, int y);//      x y     
	int FindList(int item);//    item   ，      
	void OutputList();//     
	bool IsFull() { return size == MAXSIZE; }//  
	void ChanegLenth(int size);//         size
	List & operator + (List &a);//  +，       
	int ReturnSize() { return size; }
	int ReturnElement(int i) { return list[i]; }
	//  --  
};

기본 적 인 정 보 는 모두 주석 안에 있다.
새 선형 표 함수
새 선형 표 함 수 는 여기 서 선형 표 류 의 구조 함수 입 니 다. 매개 변수 ms 를 입력 하여 선형 표 의 길 이 를 초기 화 해 야 합 니 다.

List::List(int ms)
{//ms      
	list = new int[ms];
	size = 0;
	MAXSIZE = ms;
}

new 함 수 를 이용 하여 ms 길이 의 int 형 배열 을 만 들 고 배열 의 주 소 를 list (구성원 변수) 에 부여 합 니 다.
함수 찾기
뒤의 일부 함 수 는 내부 에서 이 함 수 를 호출 해 야 하기 때문에 이 함 수 를 찾 으 려 면 매개 변수 item 을 입력 해 야 합 니 다. item 의 위 치 를 되 돌려 줍 니 다.

int List::FindList(int item)
{//item      
	for (int i = 0; i < size; i++)
	{
		if (list[i] == item)
			return i;
	}

	return -1;//    
}

만약 에 되 돌아 오 는 것 이 - 1 이라는 것 을 발견 하면 이 함수 가 이미 알 고 있 는 문제 가 없다 는 것 을 설명 합 니 다. 값 이 item 인 첫 번 째 요소 만 찾 을 수 있 고 뒤의 값 이 item 인 요 소 는 찾 을 수 없습니다. 해결 방법 이 있다 면 저 에 게 알려 주 십시오.
길이 함수 변경
길 이 를 바 꾸 는 사 고 는 new 길이 가 새로운 길이 의 배열 로 원 배열 의 데 이 터 를 하나씩 복사 하 는 것 입 니 다.사실 malloc 와 realloc 의 조합 도 사용 할 수 있 습 니 다. 한 명 씩 복사 하지 않 아 도 됩 니 다.

void List::ChanegLenth(int size)
{//size        ，         
	int *NewList = new int[size];
	int Lenth = this->size < size ? this->size : size;
	for (int i = 0; i < Lenth; i++)
	{
		NewList[i] = list[i];
	}
	this->MAXSIZE = size;
	delete[] list;
	list = NewList;
}

Lenth 의 값 은 신 구 길이 의 크기 에 달 려 있 습 니 다. 새 주소 가 작 으 면 배열 의 일부분 만 복사 합 니 다. 과거 에는 이전 배열 delete 를 삭제 하고 새 주 소 를 부여 해 야 합 니 다.
삽입 함수
삽입 함수 가 삽입 할 요소 값 item 과 삽입 할 위치 rc 를 입력 하면 item 을 rc 의 위치 에 삽입 할 수 있 습 니 다.

void List::InsertList(int item, int rc)
{//item      ，rc      ，！！！！       ，   1  ！！！！！
	if (IsFull())
		ChanegLenth(MAXSIZE + ADD_SIZE);

	for (int i = size; i > rc - 1; i--)
	{
		list[i] = list[i - 1];
	}

	list[rc - 1] = item;
	size++;
}

삽입 한 마지막 크기 에 하 나 를 추가 하 는 것 을 잊 지 마 세 요.
함수 삭제
클래스 의 정 의 를 통 해 알 수 있 듯 이 삭제 함 수 는 두 가지 버 전이 있 습 니 다.

위 치 를 입력 하고 삭제

원소 값 을 입력 하고 삭제

선형 표 의 삭 제 는 삭제 위치 에서 시작 하여 모두 한 자 리 를 앞으로 이동 하면 삭제 할 요 소 를 채 울 수 있 습 니 다.
위 치 를 입력 하고 삭제

void List::DeleteList2(int rc)
{//rc        ，！！！！！  ！！！！！
	for (int i = rc; i < size - 1; i++)
	{
		list[i] = list[i + 1];
	}
	size--;
}

요소 값 을 입력 하고 삭제 하 는 방법 은 앞의 함수 에 기반 하여 먼저 호출 하여 위 치 를 찾 은 다음 에 위의 입력 위치의 삭제 함 수 를 호출 하면 완 료 됩 니 다.

void List::DeleteList1(int item)
{//item        
	int location = FindList(item);
	if (location != -1)
	{
		DeleteList2(location + 1);
	}
	else
	{
		throw "       ";
	}
}

여기에 throw 를 추가 하여 요소 가 존재 하지 않 을 때 이상 을 던 질 수 있 습 니 다.
출력 함수
출력 함 수 는 순환 을 이용 하여 출력 선형 표를 옮 겨 다 니 는 요소 입 니 다.

void List::OutputList()
{
	cout << "         :" << endl;
	for (int i = 0; i < size; i++)
	{
		cout << list[i] << "\t";
	}
	cout << endl << endl;
}

만 료 여 부 를 판단 하 는 함수
빈 칸 을 판정 하 는 것 은 구성원 변수 size 를 이용 하 는 것 이다. size 가 MAXSIZE 와 같다 면 선형 표 가 꽉 찼 다 는 것 을 의미한다.
함수 가 매우 짧 기 때문에 내 연 함 수 를 사용 하 였 다.

bool IsFull() { return size == MAXSIZE; }
//     

일정 범위 의 요소 삭제

void List::DeleteList3(int x, int y)
{//x   ，y  ，      x y  ！！！！！！x y     ！！！！
	if (x < y && y <= size)
	{
		for (int i = x - 1; i < y - 1 && i < size - 1; i++)
			{
				list[i] = list[i + y - x + 1];
			}
			size = size - (y - x + 1);
	}
	else
	{
		throw "       ";
	}
}

x 에서 y 사이 에는 모두 x - y + 1 길이 의 요소 가 있 습 니 다. 이 범 위 를 삭제 하려 면 뒤의 같은 범위 의 요 소 를 함께 앞으로 이동 시 켜 야 합 니 다. 두 가지 가능성 이 있 습 니 다.

y 이후 x 에서 y 구간 을 채 울 수 있 는 길이 가 충분 하 다

y 이후 x 에서 y 구간 을 채 울 수 있 는 충분 한 길이 가 없어 선형 표 의 꼬리

를 미리 만 났 다.
이 두 가지 상황 의 판단 은 for 순환 의 판단 에 쓰 여 있다.

 i < y - 1 && i < size - 1

선형 표 미 를 미리 만나면 두 번 째 조건 을 만족 시 키 지 못 하고 순환 을 끝 냅 니 다. 충분 한 길이 가 있 으 면 두 번 째 판단 을 촉발 하지 않 습 니 다. x - y + 1 개의 요 소 를 이동 한 후에 첫 번 째 조건 을 촉발 하여 순환 을 끝 냅 니 다.
선형 표 의 병합

List & List::operator + (List &a)
{//     ，   +   
	List t(5);
	int size_1 = this->size;
	int size_2 = a.ReturnSize();

	int Element = 0;
	
	int i = 0;
	int j = 0;

	for (; i < size_1, j < size_2;)
	{
		if (list[i] < a.ReturnElement(j))
		{
			Element = list[i];
			i++;
		}
		else
		{
			Element = a.ReturnElement(j);
			j++;
		}
		if (i + j == 1 || t.ReturnElement(t.ReturnSize() - 1) != Element)
			t.InsertList(Element,t.ReturnSize() + 1);
	}

	return t;
}

이 함 수 는 선형 표 의 질서 가 필요 합 니 다!!연산 자 를 이용 하여 다시 불 러 올 수 있 습 니 다. + 번 호 를 직접 사용 하면 두 개의 선형 표를 합 칠 수 있 습 니 다.
먼저 선형 표를 만 들 고 합병 후의 선형 표를 저장 하 는 데 사용 합 니 다. 길 이 는 5 (이것 은 마음대로 쓰 는 것 이 고 임 의적 으로 합 법 적 인 길 이 는 모두 가능 합 니 다) 이 며 두 개의 선형 표를 동시에 옮 겨 다 닙 니 다. 여기 서 제 가 설정 한 질 서 는 오름차 입 니 다. 먼저 두 개의 선형 표 의 첫 번 째 를 비교 하고 가장 작은 하 나 를 새로운 선형 표 의 첫 번 째 에 넣 습 니 다. i 나 j 를 1 추가 합 니 다.이 순환 을 마지막 으로 새 선형 표를 되 돌려 줍 니 다.
함수 호출

int main()
{
	List a(5); //       
	cout << "       0-49" << endl;
	for (int i = 0; i < 50; i++)
	{
		a.InsertList(i, i + 1);
	}//      
	a.OutputList(); //  

	cout << "      10，20，30   ：" << endl;
	a.DeleteList1(10);
	a.DeleteList1(20);
	a.DeleteList1(30);
	a.OutputList(); //  

	cout << "     25   " << endl;
	a.DeleteList2(25);
	a.OutputList();

	List b(a); //       ，       

	cout << "     5-20     ，  5 20" << endl;
	a.DeleteList3(5, 20);
	a.OutputList();//  


	cout << "        " << endl;
	List c = a + b;
	c.OutputList();//  

	return 0;
}

위의 각종 함 수 를 간단하게 호출 하여, 비교적 간단 하 므 로, 일일이 설명 하지 않 겠 다.
환영 오류:)