线性表的一些基本操作

这里只介绍以下操作 1----初始化 2----销毁线性表 3----清空线性表 4----判断线性表是否为空 5----求线性表长度 6----获取线性表中指定位置的元素 7----获取线性表元素的位置 8----求前驱 9----求后继 10----在线性表指定位置插入元素 11----删除线性表指定位置的元素 12----显示线性表 13----合并两个非递减有序的线性表 ----------------------------------------------------------------------------------------------------- 线性表的难点在于建造结构体以及插入和删除时的元素移动 因为查找是线性表的一大优点嘛

#include<bits/stdc++.h>//万能C++头文件 #include<malloc.h>//malloc函数用来申请空间 #include<cstdio>//引用C头文件以便使用printf和scanf函数 #define OK 1; #define ERROR 0; #define LIST_INIT_SIZE 100//存储空间的初始分配量 #define LISTINCREMENT 10//存储空间的分配增量 typedef int ElemType; typedef int Status;//类型重定义 using namespace std; typedef struct{//定义结构体 ElemType *elem;//存储空间基址 int length;//当前长度 int sizelist;//当前存储容量 }SqList;//重命名为SqList方便下文引用 SqList L,La,Lb,Lc;//建立L表，La,Lb,Lc用来合并线性表 Status InitList(SqList &L)//初始化线性表 { L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));//开辟数组空间 if(!L.elem) exit(OVERFLOW);//存储分配失败 L.length=0;//空表的初始长度肯定是0啊 L.sizelist=LISTINCREMENT;//表初始容量 return OK; } Status DestroyList(SqList &L)//销毁线性表 { free(L.elem);//释放空间 L.elem=NULL; L.length=0; L.sizelist=0;//销毁语句 return OK; } Status ClearList(SqList &L)//清空线性表 { L.length=0;//这里只清空，就把长度归零就行了 return OK; } Status EmptyList(SqList &L) { if(!L.length)//(!L.length)等价于(L.length==0) return 1;//如果L.length == 0,说明表为空，返回1 else return 0;//为0时表非空，返回0 } Status LocateElem(SqList &L,int e,int &loc)//获取指定元素的位置 &loc这里用来存元素位置 { for(int i=1;i<=L.length;i++)//遍历线性表 { if(L.elem[i]==e)//如果找到元素， { loc=i;//把元素位置赋值给loc return OK;//返回OK，证明元素已找到 } else if(i==L.length)//如果找到最后(i==L.length)还是没有返回OK，就是没找到 return ERROR;//返回ERROR，证明线性表里没有这个元素 } } Status GetElem(SqList &L,int &e,int i)//获取指定位置的元素 { if(i>=1 && i<=L.length)//判断输入的位置是否非法（if里面是位置不非法) { e=L.elem[i];//把该位置的元素赋值给e return OK;//正常退出 } return ERROR;//输入位置非法，返回ERROR } Status InsertList(SqList &L,int i,int e)//在指定位置插入元素 { if(i<1 || i>L.length+1)//判断位置是否非法 return ERROR;//非法则退出 if(L.length>=L.sizelist)//当前存储空间已满，增加分配 { ElemType *base;//声明一个新基址 base=(ElemType *)realloc(L.elem,(L.sizelist+LISTINCREMENT) * sizeof(ElemType));//用realloc重新申请空间 if(!base) exit(OVERFLOW); //存储分配失败异常退出 L.elem=base;//新基址 L.sizelist+=LISTINCREMENT;//增加存储容量 } ElemType *insert, *p;//定义两个指针，insert代表要插入元素的位置，p用来将后面的元素（包括insert处的元素）都后移一位 insert=&L.elem[i]; for(p=L.elem+L.length;p>=insert;p--) *(p+1)=*p; *insert=e;//将要插入的元素e赋值到insert位置 L.length++;//线性表长度+1 return OK; } Status DeleteList(SqList &L,int i)//删除指定位置元素 { if(i<1 || i>L.length)//判断输入位置是否合法 return ERROR; ElemType *aim, *p;//定义两个指针，aim代表要删除元素的位置，p代表元素最后一个元素位置 p=L.elem+L.length; aim=&L.elem[i]; for(aim=aim+1;aim<=p;aim++) *(aim-1)=*aim;//将aim后面的元素都前移一个单位，覆盖掉aim处的元素 L.length--;//线性表长度-1 return OK; } Status ShowList(SqList &L)//显示线性表 { for(int i=1;i<=L.length;i++)//遍历线性表，逐个输出 cout<<L.elem[i]<<' '; cout<<endl; return OK; } Status MergeList(SqList &La,SqList &Lb,SqList &Lc)//合并线性表 { InitList(Lc);//初始化Lc表 int i=1,j=1,k=1;//i表示La的第一个元素，j是Lb的首位，k是Lc的首位 while((i<=La.length) && (j<=Lb.length))//遍历，直到La，Lb中的其中一个元素用完 { if(La.elem[i]<=Lb.elem[j])//比较La的i位和Lb的j位 { if(La.elem[i]!=Lc.elem[k-1])//判断Lc中是否已经有该元素，即查重操作 InsertList(Lc,k,La.elem[i]),k++;//若没有，将La的i位元素插入到Lc中，k++ i++;//La中的i操作完，后移一位 } else { if(Lb.elem[j]!=Lc.elem[k-1]) InsertList(Lc,k,Lb.elem[j]),k++; j++; } } while(i<=La.length )//若La中还剩余元素 { if(La.elem[i]!=Lc.elem[k-1])//查重一下直接插入 InsertList(Lc,k,La.elem[i]),k++; i++;//i后移 } while(j<=Lb.length) { if(Lb.elem[j]!=Lc.elem[k-1]) InsertList(Lc,k,Lb.elem[j]),k++; j++; } return 0; } int main() { int n=1;//n不为0用来跑指令输入的while语句，并判断表是否初始化或者已销毁 int i,e;//i代表位置，e代表元素 cout<<"---- Henu-敖丙-实验二"<<endl; cout<<"1----初始化一个线性表"<<endl; cout<<"2----销毁线性表"<<endl; cout<<"3----清空线性表"<<endl; cout<<"4----判断线性表是否为空"<<endl; cout<<"5----求线性表长度"<<endl; cout<<"6----获取线性表中指定位置的元素"<<endl; cout<<"7----获取线性表元素的位置"<<endl; cout<<"8----求前驱"<<endl; cout<<"9----求后继"<<endl; cout<<"10----在线性表指定位置插入元素"<<endl; cout<<"11----删除线性表指定位置的元素"<<endl; cout<<"12----显示线性表"<<endl; cout<<"13----合并两个非递减有序的线性表"<<endl; cout<<"退出，输入一个负数"<<endl<<endl; while(n)//n不为0，进入while循环 { int s;//用s来跳转指令 cout<<"请输入操作代码:"; cin>>s; if(n==1 && s>1 && s<13)//如果用户输入s在[1,12]，且表没有初始化，提示 cout<<"请先初始化线性表"<<endl; else if(n==3 && s>1 && s<13)//如果用户输入s在[1,12]，且表已销毁，提示 cout<<"表已经销毁不存在,请先初始化"<<endl; else switch(s) { case 1: n=2;//将n=2，代表表已初始化 InitList(L); printf("线性表初始化成功\n"); break; case 2: n=3;//将n=3，代表表已销毁 DestroyList(L); printf("线性表已销毁\n"); break; case 3: ClearList(L); printf("线性表已清空\n"); break; case 4: if(!EmptyList(L)) printf("线性表非空\n"); else printf("线性表为空\n"); break; case 5: printf("线性表的长度为%d\n",L.length);//这里没有引用函数，直接输出L.length不香吗 break; case 6: printf("输入指定位置查找元素："); scanf("%d",&i); if(GetElem(L,e,i))//如果函数返回的是OK，说明位置没有输错，查询元素 printf("第%d个位置上的元素是%d\n",i,e); else//这种情况是函数返回了ERROR printf("位置输入错误\n"); break; case 7: printf("输入元素查找位置："); scanf("%d",&e); if(LocateElem(L,e,i))//OK printf("%d在第%d个位置上\n",e,i); else//ERROR printf("元素不存在\n"); break; case 8://求前驱后继没有另写函数，感觉直接在这里调用两个已写的函数更方便 printf("输入元素求前驱："); scanf("%d",&e); if(!LocateElem(L,e,i))//调用查找指定元素的位置函数 printf("元素不存在\n"); else if(i==1)//如果位置是1,提示 printf("第一个元素没有前驱\n"); else { GetElem(L,e,i-1);//调用查找指定位置的元素函数，因为是求前驱，查找第i-1位 printf("前驱是%d\n",e); } break; case 9://查后继，同理前驱 printf("输入元素求后继："); scanf("%d",&e); if(!LocateElem(L,e,i)) printf("元素不存在\n"); else if(i==L.length) printf("最后一个元素没有后继\n"); else { GetElem(L,e,i+1); printf("后继是%d\n",e); } break; case 10: printf("输入要插入的位置及数字，用空格隔开\n"); scanf("%d %d",&i,&e); if(InsertList(L,i,e)) printf("插入成功\n"); else printf("插入失败\n"); break; case 11: printf("输入要删除的位置\n"); scanf("%d",&i); if(DeleteList(L,i))//OK printf("元素删除成功\n"); else//ERROR printf("位置输入错误\n"); break; case 12: printf("线性表为:\n"); ShowList(L); break; case 13: InitList(La);//初始化La InitList(Lb);//初始化Lb int na,nb;//na，nb代表La，Lb中元素个数 printf("请输入La中的元素个数\n"); scanf("%d",&na); printf("请输入La中的元素\n"); for(int k=1;k<=na;k++) {scanf("%d",&e); InsertList(La,k,e);}//插入到La printf("请输入Lb中的元素个数\n"); scanf("%d",&nb); printf("请输入Lb中的元素\n"); for(int k=1;k<=nb;k++) {scanf("%d",&e); InsertList(Lb,k,e);}//插入到Lb MergeList(La,Lb,Lc);//调用合并函数 printf("合并后的线性表为:\n"); ShowList(Lc);//合并后调用显示线性表函数，Look Look break; default: if(s<0)//如果输入的指令是负数，将n==0，这样就不满足while循环条件，循环退出 { n=0; cout<<"程序退出成功，欢迎下次使用"<<endl; break; }//若输入的s是其他数，即0和>13的数，提示输入有误 else cout<<"您输入的指令错误，请重新输入"<<endl; } } }

因为老师要求提示语不能写在自定义函数内，所以加工后就是这样子了。 （ 线性表存储元素是从L.elem[1]开始存的，L.elem[0]没有用到，，这样后面的插入删除以及合并语句就不显得那么复杂了，方便初学者理解） 如果看完有一…理解，麻烦点个赞呗(^▽)