아 날로 그 실현 선형 표 - 순서 저장 방식
선형 표 의 순서 저장 구 조 는 말하자면 자리 잡 는 형식 으로 메모리 하 나 를 차지 한 다음 에 같은 데이터 형식의 데이터 요 소 를 이 공 터 에 순서대로 저장 하 는 것 이다. 이런 특성 이 있 으 면 우 리 는 순서 표를 실현 하면 배열 의 형식 을 사용 할 수 있다!다음 순서 표 에 저 장 된 구조 코드 를 보십시오.
#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 로 줄인다.
여기 보시 면 순서 표 삽입 과 삭제 에 대해 더 깊이 알 고 계 시 죠?믿 어도 돼, 자신 을 믿 어!
마지막 으로 한 마디 로 자신 을 격려 한다. 네가 생각 하기 만 하면 무라오족 이 완성 할 수 없 는 것 이 없다. 화 이 팅!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.