顺序表的基本操作.docx
- 文档编号:15196366
- 上传时间:2023-07-02
- 格式:DOCX
- 页数:44
- 大小:24.61KB
顺序表的基本操作.docx
《顺序表的基本操作.docx》由会员分享,可在线阅读,更多相关《顺序表的基本操作.docx(44页珍藏版)》请在冰点文库上搜索。
顺序表的基本操作
顺序表的基本操作
/*sqList.h文件*/
#defineLIST_INIT_SIZE50/*初始分配的顺序表长度*/
#defineINCREM10/*溢出时,顺序表长度的增量*/
#defineOVERFLOW1
#defineOK0
#defineERROR-1
typedefintElemType;/*定义表元素的类型*/
typedefstructSqList{
ElemType*elem;/*存储空间的基地址*/
intlength;/*顺序表的当前长度*/
intlistsize;/*当前分配的存储空间*/
}SqList;
/*sqListOp.h文件*/
#include"Sqlist.h"
intInitList_sq(SqList&L);//顺序表创建函数定义
voidFreeList_sq(SqList&L);//顺序表销毁函数定义
intListInsert_sq(SqList&L,inti,ElemTypee);//在顺序表的位置i插入元素e
voidPrintList_sq(SqList&L);//遍历并输出顺序表所有元素
intListDelete_sq(SqList&L,inti,ElemType&e);//删除顺序表第i个元素的
boolListEmpty(SqList&L);//判断顺序表是否为空
intLocateElem_sq(SqListL,ElemTypee);//在顺序表里查找出第1个与e相等的数据元素位置
//已知线性表La和Lb的元素按值非递减排列
//归并后的La和Lb得到新的顺序线性表Lc,Lc的元素也是按值非递减排列
voidMergeList_sq(SqListLa,SqListLb,SqList&Lc);
/*sqListOp.cpp文件*/
#include
#include
#include
#include"sqlistOp.h"
//创建顺序表
intInitList_sq(SqList&L){
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!
L.elem)exit(OVERFLOW);/*初始化失败,返回0*/
L.length=0;/*置空表长度为0*/
L.listsize=LIST_INIT_SIZE;/*置初始空间容量*/
returnOK;/*初始化成功,返回1*/
}/*InitList*/
//销毁顺序表
voidFreeList_sq(SqList&L){
if(L.elem)
free(L.elem);
printf("完成链表内存销毁\n");
}
//在顺序表的第i个位置之前插入新元素
intListInsert_sq(SqList&L,inti,ElemTypee){
intk;
if(i<1||i>L.length+1)returnERROR;/*插入位置不合法*/
if(L.length>=L.listsize){/*存储空间满,重新分配空间*/
L.elem=(ElemType*)realloc(L.elem,(LIST_INIT_SIZE+INCREM)*sizeof(ElemType));
if(!
L.elem)returnOVERFLOW;/*存储分配失败*/
L.listsize+=INCREM;/*修改存储空间大小*/
}
for(k=L.length-1;k>=i-1;k--){/*插入位置之后元素后移*/
L.elem[k+1]=L.elem[k];
}
L.elem[i-1]=e;/*插入元素*/
L.length++;/*顺序表长度加1*/
returnOK;
}/*ListInsert*/
//遍历并输出顺序表所有元素
voidPrintList_sq(SqList&L){
if(!
L.elem)
return;
inti=0;
for(i=0;i printf("第[%d]元素=[%d]\n",i,L.elem[i]); } //删除顺序表第i个位置的元素 intListDelete_sq(SqList&L,inti,ElemType&e){ intk; if(i<1||i>L.length)returnERROR;/*删除位置不合法*/ e=L.elem[i-1]; for(k=i-1;k L.elem[k]=L.elem[k+1]; L.length--;/*顺序表长度减1*/ returnOK; } //在顺序表里查找出第1个与e相等的数据元素位置 intLocateElem_sq(SqListL,ElemTypee){ inti=0; while(i<=L.length){ if(L.elem[i]==e) break; else i++; } if(i<=L.length)returni; return-1; } //已知线性表La和Lb的元素按值非递减排列 //归并后的La和Lb得到新的顺序线性表Lc,Lc的元素也是按值非递减排列 voidMergeList_sq(SqListLa,SqListLb,SqList&Lc){ ElemType*pa=La.elem; ElemType*pb=Lb.elem; Lc.listsize=Lc.length=La.length+Lb.length; if(! Lc.elem)exit(OVERFLOW);//存储分配失败 inti=0,j=0;//书上合并的算法采用指针方式,这里采用简单点的方法 intk=0;//i指向La的当前位置,j指向Lb当前位置,k指向Lc当前位置 while(i if(La.elem[i] Lc.elem[k]=La.elem[i]; i++; } else{ Lc.elem[k]=Lb.elem[j]; j++; } k++; } while(i while(j }//MergeList_sq boolListEmpty(SqList&L){//判断顺序表是否为空 if(L.length>0) return1; else return0; } /*main.cpp文件*/ #include #include #include"sqlistOp.h" voidmain(){ SqListL; printf("准备创建顺序表\n"); if(OK! =InitList_sq(L)){ printf("顺序表创建出错\n"); } if(ListEmpty(L)) printf("表不为空\n"); else printf("表为空\n"); inti=0; for(i=1;i<=20;i++) ListInsert_sq(L,i,2*i); printf("准备遍历并输出顺序表\n"); PrintList_sq(L); getchar(); printf("在第10个位置插入值为99的元素后再遍历输出顺序表\n"); ListInsert_sq(L,10,99); PrintList_sq(L); getchar(); printf("删除第10个元素后再遍历输出顺序表\n"); ElemTypee; ListDelete_sq(L,10,e); PrintList_sq(L); printf("删除的数据元素值=%d\n",e); getchar(); printf("查找出一个数据元素的在顺序表中的位置\n"); i=LocateElem_sq(L,20); if(-1==i) printf("顺序表不包含这个数据元素\n"); else printf("元素在顺序表的位置=%d\n",i); printf("创建另一个顺序表\n"); SqListLb; if(OK! =InitList_sq(Lb)){ printf("顺序表创建出错\n"); } for(i=1;i<=10;i++) ListInsert_sq(Lb,i,2*i-1); printf("准备遍历并输出顺序表\n"); PrintList_sq(Lb); SqListLc; if(OK! =InitList_sq(Lc)){ printf("顺序表创建出错\n"); } printf("将两个顺序表合并打印合并后的顺序表\n"); MergeList_sq(L,Lb,Lc); PrintList_sq(Lc); printf("准备销毁顺序表\n"); FreeList_sq(L); FreeList_sq(Lb); FreeList_sq(Lc); getchar(); } //单链表的操作 /*linkList.h文件*/ #defineINIT_SIZE50/*初始分配的顺序表长度*/ #defineINCREM10/*溢出时,顺序表长度的增量*/ enumStatus{ OK, ERROR }; typedefintElemType;/*定义表元素的类型*/ typedefstructLNode{ ElemTypedata;/*结点的数据域*/ structLNode*next;/*结点的指针域*/ }LNode,*LinkList; /*linkListOp.h文件*/ #include"linkList.h" LinkListInitList_L();//创建单链表头结点 voidCreateList_L(LinkList&L,intn);//创建单链表头结点和n个元素结点 StatusListInsert_L(LinkList&L,inti,ElemTypee);//在单链表的第i个位置之前插入新元素x voidPrintList_L(LinkListL);//遍历并输出单链表所有元素 StatusListDelete_L(LinkList&L,inti,ElemType&e);//删除单链表第i个位置的元素 StatusGetElem_L(LinkListL,inti,ElemType&e);//获取单链表第i个位置的元素 intLocateElem_L(LinkListL,ElemTypee);//查找出第1个与e相等的数据元素位置 voidListConvert_L(LinkList&L);//单链表翻转 voidFreeList_L(LinkListL);//销毁单链表 /*linkListOp.cpp文件*/ #include #include #include"linklistOp.h" //初始化线性单表,即创建一个头结点 LinkListInitList_L(){ LinkListH=(LinkList)malloc(sizeof(LNode));/*申请一个头结点*/ if(! H)returnNULL;/*申请失败*/ H->next=NULL;/*头结点的指针域置空*/ returnH; } //创建n个结点的单链表,包括所有链表节点 voidCreateList_L(LinkList&L,intn){ //逆位序输入n个元素的值,建立带表头结点的单链表L L=(LinkList)malloc(sizeof(LNode)); L->next=NULL;//建立一个带头结点的单链表 for(inti=n;i>0;i--){ LinkListp=(LinkList)malloc(sizeof(LNode));//生成新结点 p->data=2*i;//输入元素值 p->next=L->next;//插入到表头 L->next=p; } } //在顺序表里查找出第1个与e相等的数据元素位置 intLocateElem_L(LinkListL,ElemTypee){ inti=1; LinkListp=L->next; while(p){ if(p->data==e) break; else{ p=p->next; i++; } } if(p)returni; return0; } //销毁单链表表 voidFreeList_L(LinkListL){ LinkListp=L; while(p){ L=L->next; free(p); p=L; } } //在单链表的第i个位置之前插入新元素 StatusListInsert_L(LinkList&L,inti,ElemTypee){ LinkListp=L; intj=0; while(p&&j p=p->next; ++j; } if(! p||j>i)returnERROR; LinkLists=(LinkList)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; returnOK; } //遍历并输出单链表所有元素 voidPrintList_L(LinkListL){ inti=0; LinkListp=L->next; while(p){ printf("第[%d]元素=[%d]\n",i++,p->data); p=p->next; } } //获取单链表第i个位置的元素 StatusGetElem_L(LinkListL,inti,ElemType&e){ //L为带头结点的单链表的头指针 //当第i个元素存在,其值赋给e并返回OK,否则饭否ERROR LinkListp=L->next; intj=1; while(p&&j p=p->next; ++j; } if(! p)returnERROR;//第i个元素不存在 e=p->data; returnOK; } //删除单链表第i个位置的元素,并由e返回其值 StatusListDelete_L(LinkList&L,inti,ElemType&e){ LinkListp=L; intj=0; while(p->next&&j p=p->next; ++j; } if(! p->next||j>i-1)returnERROR;//删除位置不合理 LinkListq=p->next; p->next=q->next; e=q->data; free(q); returnOK; } //单链表翻转,不增加额外的存储空间 voidListConvert_L(LinkList&L) { LinkListp,q; p=L->next; L->next=NULL; while(p){ q=p; p=p->next; q->next=L->next; L->next=q; } } /*main.cpp文件*/ #include #include #include"linklistOp.h" voidmain(){ printf("准备创建单链表\n"); LinkListL; CreateList_L(L,20); printf("准备遍历并输出单链表\n"); PrintList_L(L); getchar(); printf("在第10个位置插入值为99的元素后再遍历输出单链表\n"); ListInsert_L(L,10,99); PrintList_L(L); getchar(); printf("删除第10个元素后再遍历输出单链表\n"); ElemTypee; ListDelete_L(L,10,e); PrintList_L(L); printf("删除的元素值=%d\n",e); getchar(); printf("获取第10个元素\n"); GetElem_L(L,10,e); printf("获取到的元素值e=%d\n",e); getchar(); printf("查找数据元素14在单链表的位置\n"); intidx=LocateElem_L(L,14); printf("14在单链表的位置=%d\n",idx); getchar(); printf("单链表翻转操作\n"); ListConvert_L(L); PrintList_L(L); getchar(); printf("单链表翻转操作\n"); ListConvert_L(L); PrintList_L(L); getchar(); printf("准备销毁单链表\n"); FreeList_L(L); getchar(); } /*sqStack.h文件*/ #defineINIT_SIZE100 #defineINCREMENT10 //typedefintElemType; typedefcharElemType; typedefstructSqStack{ ElemType*base; ElemType*top; intstacksize; }SqStack; enumStatus{ OK, ERROR, OVERFLOW }; /*sqStackOp.h文件*/ #include"sqStack.h" StatusInitStack(SqStack&S); StatusGetTop(SqStackS,ElemType&e); StatusPush(SqStack&S,ElemTypee); StatusPop(SqStack&S,ElemType&e); boolStackEmpty(SqStack&S); /*sqStackOp.cpp文件*/ #include #include #include"sqStackOp.h" StatusInitStack(SqStack&S){ //构造一个空的栈 S.base=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType)); if(! S.base)exit(OVERFLOW);//存储分配失败 S.top=S.base; S.stacksize=INIT_SIZE; returnOK; }//InitStack StatusGetTop(SqStackS,ElemType&e){ //若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR if(S.top==S.base)returnERROR; e=*(S.top-1); returnOK; }//GetTop StatusPush(SqStack&S,ElemTypee){ //插入元素e为新的栈顶元素 if(S.top-S.base>=S.stacksize){//栈满,追加存储空间 S.base=(ElemType*)realloc(S.base,(S.stacksize+INCREMENT)*sizeof(ElemType)); if(! S.base)exit(OVERFLOW);//存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=INCREMENT; } *S.top++=e; returnOK; }//Push StatusPop(SqStack&S,ElemType&e){ //若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR if(S.top==S.base)returnERROR; e=*(--S.top); returnOK; }//Push //判断栈是否为空 boolStackEmpty(SqStack&S){ if(S.top==S.base) returntrue; else returnfalse; } /*main.cpp文件*/ #include #include #include"sqStackOp.h" voidmain() { printf("Hellowstack\n"); SqStackS;//定义顺序栈S if(OK! =InitStack(S)){ printf("顺序栈初始化出错,退出....\n"); exit(-1); } Push(S,1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 顺序 基本 操作