C语言动态顺序表实例代码怎么编写
导读:本文共6676字符,通常情况下阅读需要22分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要: 顺序表概念: 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构。一般情况下用数组存储。在数组上完成数据的增删查改。代码解析:一.准备工作1.首先对一些头文件的引用和创建一个结构体,结构体包含一个数组,size表示该数组目前有多少个元素,capacity表示目前数组能存多少个元素。例如:#include<stdio.h>#incl... ...
目录
(为您整理了一些要点),点击可以直达。顺序表概念:
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构。一般情况下用数组存储。在数组上完成数据的增删查改。
代码解析:
一.准备工作
1.首先对一些头文件的引用和创建一个结构体,结构体包含一个数组,size表示该数组目前有多少个元素,capacity表示目前数组能存多少个元素。例如:
#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<assert.h>typedefintDataType;typedefstructSeqList{ DataType*a; intsize; intcapacity;}SL;
2.创建一个顺序表
SLsl;
二、顺序表的基本操作
1.顺序表的初始化函数
注意这里的参数得是指针,形参是实参的一份临时拷贝,所以得把地址传给函数才能改变值。
voidSeqListInit(SL*sl){ sl->a=NULL; sl->size=0; sl->capacity=0;}
2.尾插函数(在尾部插入数据)
写尾插函数之前我们得先判断一下数组空间是否够。例如下面的例子。
所以我们要先检查空间是否满了,满了就扩容
将这个判断空间函数命名为 void CheckSpace(SL* sl) (这是动态顺序表区别于静态顺序表最主要的部分)
voidCheckSpace(SL*sl){ if(sl->size==sl->capacity) { //因为capacity一开始等于0,所以先给capacity一个值 intnewcapacity=sl->capacity==0?4:sl->capacity*2; DataType*tmp=(DataType*)realloc(sl->a,sizeof(DataType)*newcapacity); if(tmp==NULL) { printf("开辟失败\n"); exit(-1); } else { sl->capacity=newcapacity; sl->a=tmp; } }}
尾插函数:
voidSeqListPushBack(SL*sl,DataTypex){CheckSpace(sl); sl->a[sl->size]=x; sl->size++;}
3.头插函数(在数组头部插入数据)
voidSeqListPushFront(SL*sl,DataTypex){ //因为插入的时候都要检查空间是不是满了,满了就扩容 CheckSpace(sl); for(intend=sl->size-1;end>=0;end--) { sl->a[end+1]=sl->a[end]; } sl->a[0]=x; sl->size++;}
挪数据对应着for循环的代码,最后再给数组的第一个位置赋值。别忘了对size+1.
4.尾删函数
如果size等于0了就说明顺序表中没有数据了,所以
voidSeqListPopBack(SL*sl){ assert(sl->size>0); sl->size--;}
5.头删函数
从第二个数据开始整体往前挪以为就可以了。(要从前面开始挪):
voidSeqListPopFront(SL*sl){ for(inti=1;i<sl->size;i++) { sl->a[i-1]=sl->a[i]; } sl->size--;}
6.在第pos的位置插入数据
首先pos不能小于现有的数据个数。
第二判断空间,满了就扩容。
第三:从第pos个位置的数据开始(这里第pos个位置的数据在数组中的下标是pos-1)将后面的数据整体往后挪一位。
第四:再这个位置赋值,别忘了对size++;
voidSeqListInsert(SL*sl,intpos,DataTypex){ //查看空间 assert(pos<=sl->size); CheckSpace(sl); for(intend=sl->size-1;end>=pos-1;end--)//这里不能用sl->size-- { sl->a[end+1]=sl->a[end]; } sl->a[pos-1]=x; sl->size++;}
7.删除第pos个位置的数据
首先pos不能小于现有数据个数
第二:将从第pos个位置的数据开始到最后一个数据往前挪一位
第三:对size--
voidSeqListErase(SL*sl,intpos){ assert(pos<=sl->size); for(inti=pos;i<sl->size;i++) { sl->a[i-1]=sl->a[i]; } sl->size--;}
8.修改第pos个位置的数据
一:pos不能小于现有数据个数
二:赋值。第pos个位置的数据在数组中下标是pos-1。(因为数组下表从0开始)
voidSeqListModify(SL*sl,intpos,DataTypex){ assert(pos<=sl->size); sl->a[pos-1]=x;}
9.查找函数。
遍历一遍看是否有这个数据,有就返回数据是第几个元素。(这里我不是返回该数据在数组中的下标,我是返回 下标+1)
这里我没有考虑如果有两个一样的数据的情况。
intSeqListFind(SL*sl,DataTypex){ for(inti=0;i<sl->size;i++) { if(sl->a[i]==x) { i++; printf("在第%d个位置\n",i); returni; } } printf("没有此数据\n"); return-1;}
10.销毁函数
释放sl->a之后要对它置空,因为指针free之后,free函数只是把指针指向的内存空间释放了,即内存中存储的值,但是并没有将指针的值赋为NULL,指针仍然指向这块内存。
voidSeqListDestory(SL*sl){ free(sl->a); sl->a=NULL; sl->size=0; sl->capacity=0;}
11.打印函数
voidSeqListPrint(SL*sl){ for(inti=0;i<sl->size;i++) { printf("%d",sl->a[i]); } printf("\n");}
三、总代码:
菜单写的比较简单。
#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<assert.h>typedefintDataType;typedefstructSeqList{ DataType*a; intsize; intcapacity;}SL;voidSeqListInit(SL*sl){ sl->a=NULL; sl->size=0; sl->capacity=0;}voidSeqListPrint(SL*sl){ for(inti=0;i<sl->size;i++) { printf("%d",sl->a[i]); } printf("\n");}voidCheckSpace(SL*sl){ if(sl->size==sl->capacity) { //因为capacity一开始等于0,所以先给capacity一个值 intnewcapacity=sl->capacity==0?4:sl->capacity*2; DataType*tmp=(DataType*)realloc(sl->a,sizeof(DataType)*newcapacity); if(tmp==NULL) { printf("开辟失败\n"); exit(-1); } else { sl->capacity=newcapacity; sl->a=tmp; } }}voidSeqListPushBack(SL*sl,DataTypex){ //看空间是不是满了,满了就扩容 //if(sl->size==sl->capacity) //{ // //因为capacity一开始等于0,所以先给capacity一个值 // intnewcapacity=sl->capacity==0?4:sl->capacity*2; // DataType*tmp=(DataType*)realloc(sl->a,sizeof(DataType)*newcapacity); // if(tmp==NULL) // { // printf("开辟失败\n"); // exit(-1); // } // else // { // sl->a=tmp; // } //} //封装成一个函数 CheckSpace(sl); sl->a[sl->size]=x; sl->size++;}voidSeqListPushFront(SL*sl,DataTypex){ //因为插入的时候都要检查空间是不是满了,满了就扩容 CheckSpace(sl); for(intend=sl->size-1;end>=0;end--) { sl->a[end+1]=sl->a[end]; } sl->a[0]=x; sl->size++;}voidSeqListPopBack(SL*sl){ assert(sl->size>0); sl->size--;}voidSeqListPopFront(SL*sl){ for(inti=1;i<sl->size;i++) { sl->a[i-1]=sl->a[i]; } sl->size--;}voidSeqListInsert(SL*sl,intpos,DataTypex){ //查看空间 assert(pos<=sl->size); CheckSpace(sl); for(intend=sl->size-1;end>=pos-1;end--)//这里不能用sl->size-- { sl->a[end+1]=sl->a[end]; } sl->a[pos-1]=x; sl->size++;}voidSeqListErase(SL*sl,intpos){ assert(pos<=sl->size); for(inti=pos;i<sl->size;i++) { sl->a[i-1]=sl->a[i]; } sl->size--;}voidSeqListModify(SL*sl,intpos,DataTypex){ assert(pos<=sl->size); sl->a[pos-1]=x;}intSeqListFind(SL*sl,DataTypex){ for(inti=0;i<sl->size;i++) { if(sl->a[i]==x) { i++; printf("在第%d个位置\n",i); returni; } } printf("没有此数据\n"); return-1;}voidSeqListDestory(SL*sl){ free(sl->a); sl->a=NULL; sl->size=0; sl->capacity=0;}voidmenu(){ printf("******************************\n"); printf("***1.尾插数据2.头插数据***\n"); printf("***3.在第pos个位置插入数据***\n"); printf("***4.尾删数据5.头删数据***\n"); printf("***6.在第pos个位置删除数据***\n"); printf("***7.修改第pos个位置的数据***\n"); printf("***8.查找数据9.打印数据***\n"); printf("**********-1.退出***********\n"); printf("******************************\n");}intmain(){ SLsl; SeqListInit(&sl); intoption=0; intx=0; intpos=1; while(option!=-1) { menu(); scanf("%d",&option); switch(option) { case1: printf("请输入要插入的数据,以-1结束:\n"); do { scanf("%d",&x); if(x!=-1) { SeqListPushBack(&sl,x); } }while(x!=-1); break; case2: printf("请输入要插入的数据,以-1结束:\n"); do { scanf("%d",&x); if(x!=-1) { SeqListPushFront(&sl,x); } }while(x!=-1); break; case3: printf("请输入要插入的数据,要从第几个插入,以非正正数结束\n"); do { scanf("%d",&x); scanf("%d",&pos); if(pos>=0) { SeqListInsert(&sl,pos,x); } }while(pos>=0); break; case4: SeqListPopBack(&sl); break; case5: SeqListPopFront(&sl); break; case6: printf("请输入要删除第几个位置的数据,以非正正数结束\n"); do { scanf("%d",&pos); if(pos>0) { SeqListErase(&sl,pos); } }while(pos>0); break; case7: printf("请输入要修改的数据,要修改第几个数据,以非正整数结束\n"); do { scanf("%d",&x); scanf("%d",&pos); if(pos>0) { SeqListInsert(&sl,pos,x); } }while(pos>0); break; case8: printf("请输入需要查找的数据\n"); scanf("%d",&x); SeqListFind(&sl,x); break; case9: SeqListPrint(&sl); break; case-1: printf("退出\n"); break; default: printf("输入错误,请重新输入\n"); } } SeqListDestory(&sl); return0;}
</div> <div class="zixun-tj-product adv-bottom"></div> </div> </div> <div class="prve-next-news">
C语言动态顺序表实例代码怎么编写的详细内容,希望对您有所帮助,信息来源于网络。