선형 표 의 연속 저장 소 (배열)

1. 데이터 구조 중의 데이터 형식 은?
제 가 정리 한 결과 데이터 구 조 는 현실 생활 에서 의 유형 을 두 가지 로 나 누 었 습 니 다. 하 나 는 선형 구조 (선형 표 라 고도 함) 이 고 다른 하 나 는 비 선형 구조 입 니 다.
2. 선형 구조 와 비 선형 구 조 는 무엇 입 니까?
선형 구 조 는 말 그대로 선 과 같은 구조 로 데이터 요 소 는 논리 적 으로 하나 로 연결 되 어 있 고 현재 의 위 치 를 통 해 다음, 심지어 그 후의 모든 위치의 요 소 를 찾 을 수 있다.
비 선형 구조: 선형 구조 와 반대로 이런 구조 로 저 장 된 데이터 요 소 는 논리 적 으로 연속 되 지 않 는 다. 즉, 현재 위 치 를 통 해 다음 요 소 를 찾 을 수 없다.
3. 선형 구조의 두 가지 분류?
선형 구 조 는 배열 과 링크 로 나 뉜 다.
1. 186. 먼저 배열 은 모두 가 사용 한 적 이 있 을 것 이다. 밑 에 미리 정 의 된 코드 를 많이 포장 하여 사용 할 수 있다.그것 의 구조 도 분명 하 다. 1) 그것 은 논리 적 으로 연속 적 일 뿐만 아니 라 물리 적 으로 도 연속 적 이다. 하 나 는 다음 과 같다. 2) 나 는 배열 을 정의 하고 그 에 게 몇 개의 길이 의 메모리 공간 을 미리 배정 해 야 한다.(정적 저장 소)
2. 1861) 링크 는 논리 적 으로 출시 되 는 연속 적 인 (선형 구 조 를 만족 시 키 는 것) 이지 만 물리 적 으로 연속 적 인 것 이 아니 라 모든 노드 의 지침 을 통 해 다음 요 소 를 찾 을 수 있다.2) 링크 를 정의 하 는 동시에 메모리 공간 을 미리 배정 하지 않 아 도 프로그램 이 실 행 될 때 메모리 (동적 저장) 를 할당 할 수 있 습 니 다.
결론: 만약 에 반 의 인원 수 를 저장 하려 면 각 반 의 인원 이 다 를 수 있 습 니 다. 이 럴 때 배열 로 저장 하면 배열 의 길 이 를 미리 정 해 야 합 니 다. 그러나 반 의 인원 이 다 르 기 때문에 가장 큰 반 수 에 따라 길 이 를 정의 해 야 합 니 다. 그러면 공간 낭 비 를 초래 할 수 있 습 니 다. 이런 미리 분 배 된 길이 의 정적 저장 은 좋 지 않 습 니 다.이 럴 때 링크 (동적 저장) 를 선택 할 수 있 습 니 다.
4. 배열 상용 방법 실현
여기 서 나 는 C 언어 로 이 루어 졌 다.자바 등 도 가능 하지만 사용 하지 않 는 것 이 좋 습 니 다.
/ / 반전 배열 요소
void inversion_arr(pArr arr);
/ / 오름차 순 정렬
void sort_arr(pArr arr);
/ / 지정 한 아래 표 시 된 요 소 를 가 져 옵 니 다.
int get(pArr arr,int pos);
/ / 지정 한 아래 표 시 된 요 소 를 수정 합 니 다.
bool update_arr(pArr arr,int pos,int val);
/ / 지정 한 아래 표 시 된 요 소 를 삭제 합 니 다.
bool delete_arr(pArr arr,int pos,int *val);
/ / 지정 한 아래 에 숫자 를 삽입 합 니 다.
bool insert_arr(pArr arr,int pos,int val);
/ / 배열 요소 추가
bool append_arr(pArr arr,int val);
/ / 배열 초기 화
void init_arr(pArr arr,int len);
/ / 배열 에 대한 정 보 를 표시 합 니 다.
void show_arr(pArr arr);
/ / 배열 이 비어 있 는 지 판단 합 니 다.
bool is_empty(pArr arr);
/ / 배열 이 가득 찼 는 지 판단 합 니 다.
bool is_full(pArr arr);

//               
 #include 
 #include 
 #include  
 typedef struct Arr{
 	int *pBase;
 	int length;
 	int cnt;
 }*pArr; //pArr=struct Arr *
 void inversion_arr(pArr arr);
 void sort_arr(pArr arr);
 int get(pArr arr,int pos);
 bool update_arr(pArr arr,int pos,int val);
 bool delete_arr(pArr arr,int pos,int *val);
 bool insert_arr(pArr arr,int pos,int val);
 bool append_arr(pArr arr,int val);
 void init_arr(pArr arr,int len);
 void show_arr(pArr arr);
 bool is_empty(pArr arr);
 bool is_full(pArr arr);
 int main(){
 	struct Arr arr;
 	int len,delVal;
 	printf("               len=");
 	scanf("%d",&len);
 	init_arr(&arr,len);
 	append_arr(&arr,12);
 	append_arr(&arr,2);
 	append_arr(&arr,3);
 	append_arr(&arr,11);
 	append_arr(&arr,4);
 	append_arr(&arr,19);
 	append_arr(&arr,103);
 	append_arr(&arr,41);
 	append_arr(&arr,9);
 	show_arr(&arr);
 	inversion_arr(&arr);
 	show_arr(&arr);
 //	printf("%d",get(&arr,2));
 	/*
 	if(update_arr(&arr,2,111)){
 		show_arr(&arr);
	 }
	//show_arr(&arr);
 	//insert_arr(&arr,1,18);
 	//bool flag = delete_arr(&arr,1,&delVal);
 	//if(flag){
 		//printf("    ,     %d
",delVal);
	 //}
 	*/
 }

 //      
 void inversion_arr(pArr arr){
 	if(is_empty(arr)){
 		printf("     ,    !
");
 		exit(-1);
	 }
 	int i,j;
 	for(i=0;icnt/2;i++){
 		int temp=arr->pBase[i];
 		arr->pBase[i]=arr->pBase[arr->cnt-1-i];
 		arr->pBase[arr->cnt-1-i]=temp;
	 }
 }

//        
 void sort_arr(pArr arr){
 	int i,j;
 	if(is_empty(arr)){
 		printf("     ,    !
");
 		exit(-1);
	 }
	 for(i=0;icnt;i++){
	 	for(j=i+1;jcnt;j++){
	 		if(arr->pBase[i]>arr->pBase[j])
			 {
		 		int temp=arr->pBase[i];
		 		arr->pBase[i]=arr->pBase[j];
		 		arr->pBase[j]=temp;
		 	 }
		}
	 }
 }

//         ,pos       
 int get(pArr arr,int pos){
 	if(is_empty(arr)){
 		printf("     ,    !");
 		return false;
	 }
	 if(pos<1||pos>arr->cnt){
	 	printf("       ");
	 	return false;
	 }
	 return arr->pBase[pos-1];
 }

//         
bool update_arr(pArr arr,int pos,int val){
 	if(is_empty(arr)){
 		printf("     ,    !
");
 		return false;
	 }
	 if(pos<1||pos>arr->cnt){
	 	printf("       !
");
	 	return false;
	 }
	 arr->pBase[pos-1]=val;
	 return true;
 }

  //         
  bool delete_arr(pArr arr,int pos,int *val){
 	int i;
 	if(is_empty(arr)){
 		printf("    ,     !
");
 		return false;
	 }
	 if(pos<1||pos>arr->cnt){
	 	printf("        !
");
	 	return false;
	 }
	 *val = arr->pBase[pos-1];
	 for(i=pos-1;icnt;i++){
	 	arr->pBase[i-1]=arr->pBase[i];
	 }
	 arr->cnt--;
	 return true;
 }

 //           
 bool insert_arr(pArr arr,int pos,int val){//pos 1  ,          
 	int i;
 	if(is_full(arr)){
 		printf("    ,      !
");
 		return false;
	 }
	 if(pos<1||pos>arr->cnt+1){
	 	printf("         !
");
	 	return false;
	 }
	 for(i=arr->cnt-1;i>=pos-1;i--){
	 	arr->pBase[i+1]=arr->pBase[i];
	 }
	 arr->pBase[pos-1]=val;
	 arr->cnt++;
	 return true;
 }

 //           
 bool append_arr(pArr arr,int val){
 	if(is_full(arr)){
 		printf("    ,      ,    
");
 		return false;
	 }
	 arr->pBase[arr->cnt++]=val;
	 return true;
 }

//          
 void show_arr(pArr arr){
 	int i;
 	if(arr==NULL){
 		printf("        ,    
");
 		exit(-1);
	 }
	 printf("        %d,     %d",arr->length,arr->cnt);
	 if(arr->cnt>0){
	 	printf(",     :");
	 	for(i=0;icnt;i++){
	 		printf("%d,",arr->pBase[i]);
		 }
		 printf("
");
	 }else{
	 	printf(",      
");
	 }
 }

 //     
 void init_arr(pArr arr,int len){
 	arr->pBase = (int *)malloc(sizeof(int)*len);
 	if(arr==NULL){
 		printf("      ,    !
");
 		exit(-1);
	 }
	 arr->length=len;
	 arr->cnt=0;
 } 

 //        
 bool is_empty(pArr arr){
 	if(arr->cnt==0)
 		return true;
 	return false;
 } 

 //       
 bool is_full(pArr arr){
 	if(arr->length==arr->cnt)
 		return true;
 	return false;
 } 

지금까지 배열 의 기본 적 인 방법 은 모두 실현 되 었 다. C 언어 로 이 루어 졌 기 때문에 지침, 동적 메모리 배분 (malloc) 과 C 구조 체 와 관련 되 었 기 때문에 잘 모 르 는 학생 들 은 이런 내용 과 관련 된 자 료 를 먼저 볼 수 있다.잘 못 썼 으 니 잘 부탁드립니다.
구체 적 인 소스 코드 참조:http://download.csdn.net/download/qq_31308883/10141495