C语言实现顺序表
顺序表是C语言中一种基本的结构,可以存储各种基本类型的数据,而且不但可以存储基本类型的数据,也可以存储一种结构。所以顺序表是一种在学C的过程中必须掌握的结构,通过学习整理,下面来实现一下:
首先,先要想好用什么实现,一般实现最基本的顺序表的话直接用数组实现,我们在这用一个结构体来封装这个顺序表(封装这一概念是在C++中最常用的概念)
#defineARRAY_EMPTY-2#defineARRAY_FULL-1#defineMAX_SIZE10000typedefintDatatype;typedefstructSeqlist{Datatypearray[MAX_SIZE];size_tsize;}Seqlist;
对于无法确定数组大小,我们可以用宏来表示。
把大体结构搭建好了之后,就可以思考一个顺序表应该具有的功能,头插,尾插,定点插入,排序等等都是一些最基本的功能:
voidPrintSeqlist(Seqlist*pSeq);voidInitSeqlist(Seqlist*pSeq);voidPushBack(Seqlist*pSeq,Datatypex);voidPushFront(Seqlist*pSeq,Datatypex);voidPopBack(Seqlist*pSeq);voidPopFront(Seqlist*pSeq);voidInsert(Seqlist*pSeq,size_tpos,Datatypex);intFind(Seqlist*pSeq,size_tpos,Datatypex);voidErase(Seqlist*pSeq,size_tpos);intRemove(Seqlist*pSeq,Datatypex);intRemoveall(Seqlist*pSeq,Datatypex);voidBubblesort(Seqlist*pSeq);voidSelectsort(Seqlist*pSeq);intBinarySearch(Seqlist*pSeq,Datatypex);
下面就是一些关键函数的实现:
voidPrintSeqlist(Seqlist*pSeq)//输出顺序表{assert(pSeq);size_ti=0;if(pSeq->size<=0){printf("Arrayisempty\n");return;}elseif(pSeq->size>=MAX_SIZE){printf("Arrayisfull\n");}for(;i<pSeq->size;++i){printf("%-4d",pSeq->array[i]);}}voidInitSeqlist(Seqlist*pSeq)//初始化顺序表{pSeq->size=0;//printf("Initializationiscomplete\n");}voidPushBack(Seqlist*pSeq,Datatypex)//后插入{assert(pSeq);if(pSeq->size>=MAX_SIZE){printf("Arrayisfull,insertthefailure\n");return;}pSeq->array[pSeq->size]=x;pSeq->size++;}voidPushFront(Seqlist*pSeq,Datatypex)//前插入{assert(pSeq);size_ti=0;if(pSeq->size>=MAX_SIZE){printf("Arrayisfull,insertthefailure\n");return;}for(i=pSeq->size;i>0;--i){pSeq->array[i]=pSeq->array[i-1];}pSeq->array[0]=x;pSeq->size++;}voidPopBack(Seqlist*pSeq)//后删除{assert(pSeq);if(pSeq->size<=0){printf("Arrayisempty,popbackiseeror\n");return;}pSeq->array[pSeq->size-1]=0;pSeq->size--;}voidPopFront(Seqlist*pSeq)//前删除{assert(pSeq);size_ti=0;if(pSeq->size<=0){printf("Arrayisempty,popbackiseeror\n");return;}for(i=1;i<pSeq->size;i++){pSeq->array[i-1]=pSeq->array[i];}pSeq->size--;}voidInsert(Seqlist*pSeq,size_tpos,Datatypex)//定点删除{assert(pSeq);size_ti=0;if(pSeq->size>=MAX_SIZE){printf("Arrayisfull,insertthefailure\n");return;}for(i=pSeq->size;i>pos;i--){pSeq->array[i]=pSeq->array[i-1];}pSeq->array[pos]=x;pSeq->size++;}intFind(Seqlist*pSeq,size_tpos,Datatypex)//查找数据{assert(pSeq);size_ti=0;if(pSeq->size<=0){printf("Arrayisempty,eraseerror\n");returnARRAY_EMPTY;}if(pos<0||pos>=MAX_SIZE){printf("Begantofindthepositionerror\n");return-1;}for(i=pos;i<pSeq->size;i++){if(pSeq->array[i]==x){returni;}}return-2;}voidErase(Seqlist*pSeq,size_tpos)//删除特定数据{assert(pSeq);size_ti=0;if(pSeq->size<=0){printf("Arrayisempty,eraseerror\n");return;}if(pos<0||pos>=MAX_SIZE){printf("Begantofindthepositionerror\n");return;}for(i=pos;i<pSeq->size;i++){pSeq->array[i]=pSeq->array[i+1];}pSeq->size--;}intRemove(Seqlist*pSeq,Datatypex){assert(pSeq);size_ti=0;if(pSeq->size<=0){printf("Arrayisempt,removeerror\n");returnARRAY_EMPTY;}for(;i<pSeq->size;i++){if(pSeq->array[i]==x){size_tj=i+1;for(;j<pSeq->size;j++){pSeq->array[j-1]=pSeq->array[j];}pSeq->size--;return0;}}return-1;}intRemoveall(Seqlist*pSeq,Datatypex){assert(pSeq);size_ti=0;intflag=0;if(pSeq->size<=0){printf("Arrayisempt,removeerror\n");returnARRAY_EMPTY;}for(;i<pSeq->size;i++){if(pSeq->array[i]==x){size_tj=i+1;for(;j<pSeq->size;j++){pSeq->array[j-1]=pSeq->array[j];}pSeq->size--;flag++;if(pSeq->size<=0)//如果顺序表的元素为空就不能再删除了,返回{return0;}else{i--;}}}if(flag>0)return0;elsereturn-1;}voidBubblesort(Seqlist*pSeq)//冒泡排序{assert(pSeq);size_ti=0;for(;i<pSeq->size;i++){size_tj=0;for(;j<pSeq->size-i-1;j++){if(pSeq->array[j]>pSeq->array[j+1]){inttmp=pSeq->array[j];pSeq->array[j]=pSeq->array[j+1];pSeq->array[j+1]=tmp;}}}}voidSelectsort(Seqlist*pSeq)//选择排序{assert(pSeq);size_ti=0;for(;i<pSeq->size;i++){intflag=pSeq->array[i];size_tj=i;for(;j<pSeq->size;j++){if(pSeq->array[j]<flag){inttmp=pSeq->array[j];pSeq->array[j]=flag;flag=tmp;}}pSeq->array[i]=flag;}}intBinarySearch(Seqlist*pSeq,Datatypex)//二分查找{assert(pSeq);size_tleft=0;size_tright=pSeq->size-1;while(left<=right){size_tmid=left+(right-left)/2;if(x>pSeq->array[mid]){left=mid+1;}elseif(x<pSeq->array[mid]){right=mid-1;}elseif(x==pSeq->array[mid]){return(int)mid;}}return-1;}
这只是最基本的顺序表,只能够存储基本类型的数据,如果想要存储结构体或者string之类的数据的话会涉及C++的深浅拷贝问题,而且用一个数组来存未知大小的数据结构的话是做不到的。
本人的博客后面会更新顺序表的一些优化写法,希望对朋友微小的帮助。
声明:本站所有文章资源内容,如无特殊说明或标注,均为采集网络资源。如若本站内容侵犯了原著者的合法权益,可联系本站删除。