아 날로 그 실현 선형 표 - 순서 저장 방식

우 리 는 데이터 의 저장 방식 에서 선형 표 라 는 구조 가 있다 는 것 을 알 고 있다. 무라오족 은 선형 표 일 까?이름 에서 이해 할 수 있 을 거 라 고 믿 습 니 다. 선형 표 는 선 과 같은 성질 의 표 입 니 다.이런 구조 처럼 우리 가 줄 을 서 는 과정 에서 하 나 는 하 나 를 따라 줄 을 서고 하 나 는 선두 에 서고 하 나 는 마무리 가 있다. 그러면 하나의 선 이 그들 을 연결 하 는 것 처럼 선형 표 라 고 할 수 있다!선형 표 에 대해 말하자면 우 리 는 그것 의 두 가지 저장 구 조 를 제기 해 야 한다. 순차 저장 구조 와 체인 저장 구조 ,여기 서 우 리 는 선형 표 의 순서 저장 구조 만 토론 하고 관심 이 있 는 학생 들 은 스스로 체인 저장 구 조 를 연구 할 수 있다.
        선형 표 의 순서 저장 구 조 는 말하자면 자리 잡 는 형식 으로 메모리 하 나 를 차지 한 다음 에 같은 데이터 형식의 데이터 요 소 를 이 공 터 에 순서대로 저장 하 는 것 이다. 이런 특성 이 있 으 면 우 리 는 순서 표를 실현 하면 배열 의 형식 을 사용 할 수 있다!다음 순서 표 에 저 장 된 구조 코드 를 보십시오.
        
#define MAX 100
typedef int DataType;
typedef struct SeqList
{
	DataType Data[MAX];
	int size;
}SeqList,*pSeqList;
       이 간단 한 예 를 통 해 우 리 는 순서 저장 에 세 가지 특성 이 필요 하 다 는 것 을 알 수 있다.
       1. 저장 공간의 시작 위치: 배열 Data;
       2. 선형 표 의 최대 저장 용량: 배열 길이 MAX;
       3. 선형 표 의 현재 길이: size;
       여기 서 우 리 는 데이터 길이 와 선형 표 의 길이 가 무라오족 과 어떤 차이 가 있 는 지 궁금 하 다.다음은 내 가 자세히 말 하 겠 다.
        배열 의 길 이 는 선형 표 저장 공간 을 저장 하 는 길이 로 변 하지 않 습 니 다.선형 표 의 길 이 는 선형 표 에서 데이터 요소 의 개수 이 고 변화 하 는 것 이다.임의의 시간 에 선형 표 의 길 이 는 배열 의 길이 보다 작 아야 한다.
       여기 서 말씀 드 리자 면 여러분 들 은 순서 표 에 대해 어느 정도 알 고 계 시 죠?다음은 순서 표 의 몇 가지 흔 한 기능 을 모 의 해 보 겠 습 니 다.
       SeqList.h
       
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#define MAX 100
typedef int DataType;
typedef struct SeqList
{
	DataType Data[MAX];
	int size;
}SeqList,*pSeqList;
void Print_SeqList(pSeqList pSeq);         //       
void Init_SeqList(pSeqList pSeq);          //   
void Push_Back(pSeqList pSeq,DataType x); //          
void Pop_Back(pSeqList pSeq);             //          
void Push_front(pSeqList pSeq,DataType x);//          
void Pop_front(pSeqList pSeq);            //          
void Insert_SeqList(pSeqList pSeq,int pos,DataType x); //                
void Remove_SeqList(pSeqList pSeq,DataType x);         //       
void RemoveAll_SeqList(pSeqList pSeq,DataType x);      //         
void Sort_SeqList(pSeqList pSeq);                      //      
int Binary_Search(pSeqList pSeq,DataType x);           //    
       text.c
       
#include"SeqList_dyna.h"
void menu()  
{  
    printf("***********************************************
"); printf("*****0.exit**1.Push_Back**2.Pop_Back***********
"); printf("*****3.Push_front*********4.Pop_front**********
"); printf("*****5.Insert_SeqList*****6.Remove_SeqList*****
"); printf("*****7.RemoveAll_SeqList**8.Sort_SeqList*******
"); printf("*****9.Print_SeqList******10. Binary_Search****
"); printf("***********************************************
"); } int main() { int x=0; int input=1; int pos=0; int ret=0; SeqList pSeq; Init_SeqList(&pSeq); while(input) { menu(); printf(" :"); scanf("%d",&input); switch(input) { case 1: printf(" :"); scanf("%d",&x); Push_Back(&pSeq,x); break; case 2: Pop_Back(&pSeq); break; case 3: printf(" :"); scanf("%d",&x); Push_front(&pSeq,x); break; case 4: Pop_front(&pSeq); break; case 5: printf(" :"); scanf("%d",&x); printf(" :"); scanf("%d",&pos); Insert_SeqList(&pSeq,pos,x); break; case 6: printf(" :"); scanf("%d",&x); Remove_SeqList(&pSeq,x); break; case 7: printf(" :"); scanf("%d",&x); RemoveAll_SeqList(&pSeq,x); break; case 8: Sort_SeqList(&pSeq); break; case 9: Print_SeqList(&pSeq); break; case 10: printf(" :"); scanf("%d",&x); ret=Binary_Search(&pSeq,x); if(pSeq.Data[ret] == x) { printf("
"); } else { printf("
"); } case 0: break; default: printf("
"); break; } } system("pause"); return 0; }

       SeqList.c
       
#include"SeqList.h"
void  Print_SeqList(pSeqList pSeq)
{
	int i=0;
	assert(pSeq);
	for(i=0;isize;i++)
	{
		printf("%d ",pSeq->Data[i]);
	}
	printf("
"); } void Init_SeqList(pSeqList pSeq) { pSeq->size=0; memset(pSeq->Data,0,MAX*sizeof(DataType)); } void Push_Back(pSeqList pSeq,DataType x) { assert(pSeq); if(pSeq->size == MAX) { printf("
"); return ; } pSeq->Data[pSeq->size]=x; pSeq->size++; } void Pop_Back(pSeqList pSeq) { assert(pSeq); if(pSeq->size == 0) { printf("
"); return ; } pSeq->size--; } void Push_front(pSeqList pSeq,DataType x) // { int i=0; assert(pSeq); if(pSeq->size == MAX) { printf("
"); return ; } for(i=pSeq->size-1;i>=0;i--) { pSeq->Data[i+1]=pSeq->Data[i]; } pSeq->Data[0]=x; pSeq->size++; } void Pop_front(pSeqList pSeq) { int i=0; assert(pSeq); for(i=0;isize;i++) { pSeq->Data[i]=pSeq->Data[i+1]; } pSeq->size--; } void Insert_SeqList(pSeqList pSeq,int pos,DataType x) // x,pos { int i=0; assert(pSeq); if(pSeq->size == MAX) { printf("
"); return ; } for(i=pSeq->size-1;i>=pos;i--) { pSeq->Data[i+1]=pSeq->Data[i]; } pSeq->Data[pos]=x; pSeq->size++; } void Remove_SeqList(pSeqList pSeq,DataType x) // { int i=0; int ret=0; ret=Binary_Search(pSeq,x); assert(pSeq); if(ret == -1) { printf("
"); return ; } else { for(i=ret;isize;i++) { pSeq->Data[i]=pSeq->Data[i+1]; } } pSeq->size--; printf("
"); } int Find_NUM(pSeqList pSeq ,DataType x) // { int i=0; for(i=0;isize;i++) { if(pSeq->Data[i] == x) return i; } return -1; } void RemoveAll_SeqList(pSeqList pSeq,DataType x) // { int i=0; int j=0; int ret=0; assert(pSeq); while(ret < pSeq->size) { ret=Find_NUM(pSeq,x); if(ret == -1) { printf("
"); return ; } else { for(i=ret;isize;i++) { pSeq->Data[i]=pSeq->Data[i+1]; } } pSeq->size--; ret++; } printf("
"); } void Sort_SeqList(pSeqList pSeq) // { int i=0; int j=0; DataType tmp=0; int flag=0; assert(pSeq); for(i=0;isize-1;i++) { flag=0; // for(j=0;jsize-1-i;j++) { if(pSeq->Data[j] > pSeq->Data[j+1]) // { tmp=pSeq->Data[j]; pSeq->Data[j]=pSeq->Data[j+1]; pSeq->Data[j+1]=tmp; flag=1; } } if(flag == 0) break; } } int Binary_Search(pSeqList pSeq,DataType x) { int left=0; int mid=0; int right=pSeq->size-1; assert(pSeq); Sort_SeqList(pSeq); // while(left < right) { mid=(left+right)/2; if(pSeq->Data[mid] < x) { left=mid; } else if(pSeq->Data[mid] > x) { right=mid; } else { return mid; } } return -1; }
        우 리 는 코드 의 삽입 과 삭제 작업 에서 머리 삽입 이 든 꼬리 삽입 이 든 모두 선형 표 의 현재 길이 크기 만 바 꾸 는 것 을 볼 수 있 습 니 다. 그러나 머리 와 꼬리 가 아 닌 위치 에 삽입 하거나 삭제 하 는 것 이 라면?
        순서 표 의 지정 한 위치 에 지정 한 요 소 를 삽입 합 니 다:
        우 리 는 우리 가 새치기 하 는 행 위 를 비교 할 수 있다.순서 표 의 삽입 은 이것 과 유사 하 다. 여기 서 나 는 다음 과 같은 네 가지 절차 로 요약 한다.
        1. 선형 표 의 길이 가 배열 의 길이 보다 크 거나 같 으 면 순서 표 가 가득 차 서 계속 삽입 할 수 없습니다.
        2. 마지막 위치 부터 두 번 째 pos 위치 로 옮 겨 다 니 며 각각 한 자 리 를 뒤로 옮 깁 니 다.
        3. 삽입 할 요 소 를 위치 pos 에 채 우기;
        4. 시계의 길이 에 1 을 더 합 니 다.
        순서 표 에서 지정 한 요 소 를 삭제 합 니 다:
         마찬가지 로 우 리 는 줄 을 서서 비교 할 수 있다. 만약 한 사람 이 더 이상 줄 을 서서 떠 나 고 싶 지 않다 면, 이때 이 자 리 는 비어 있 지 않 을 까?물론 뒤에 줄 을 서 있 는 사람들 은 모두 이 자리 에서 한 자 리 를 앞으로 옮 길 것 이다. 여기 서 나 는 다음 과 같은 네 가지 절 차 를 정리 했다.
        1. 순서 표 가 비어 있 으 면 무라오족 요 소 를 삭제 할 필요 가 없 지!
        2. 삭제 요 소 를 찾 아 Find 설정NUM 함수 가 이 요소 의 아래 표 시 를 되 돌려 줍 니 다.
        3. 요 소 를 삭제 할 때 부터 마지막 요소 의 위 치 를 옮 겨 다 니 며 한 위 치 를 옮 깁 니 다.
        4. 시계의 길 이 를 1 로 줄인다.
       여기 보시 면 순서 표 삽입 과 삭제 에 대해 더 깊이 알 고 계 시 죠?믿 어도 돼, 자신 을 믿 어!
       마지막 으로 한 마디 로 자신 을 격려 한다. 네가 생각 하기 만 하면 무라오족 이 완성 할 수 없 는 것 이 없다. 화 이 팅!

좋은 웹페이지 즐겨찾기