数据结构-线性表操作

2025-01-14 技术教程

#include<iostream>//c++头文件usingnamespacestd;#defineLIST_INIT_SIZE20//预定义常量#defineLISTINCREMENT5#defineOK1#defineERROR0typedefintElemType;//定义类型typedefintStatus;typedefstruct//线性表结构体定义{ElemType*elem;intlength;intlistsize;}SqList;StatusInitList_Sq(SqList&L)//创建空的线性表{L.elem=newElemType[LIST_INIT_SIZE];//申请空间L.length=0;//令表中数据长度为零L.listsize=LIST_INIT_SIZE;//将所申请的空间给予元素空间returnOK;}StatusCreateList_Sq(SqList&L,intn)//创建一个线性表{inti;InitList_Sq(L);//创建空表if(n>L.listsize)//保证空间足够{//续开辟空间}L.length=n;cout<<"pleaseinput"<<n<<"numbers:";for(i=0;i<L.length;i++)//输入数据元素cin>>L.elem[i];returnOK;}StatusOutputList_Sq(SqListL)//输出线性表{inti;cout<<"Thelistis:";for(i=0;i<L.length;i++)cout<<L.elem[i]<<"";cout<<endl;returnOK;}StatusListInsert_Sq(SqList&L,inti,ElemTypee)//插入元素（前插法）{intj;if(i<1||i>L.length+1)//（1）判断插入元素下标i的合法性（1---L.length+1）returnERROR;if(L.length>=L.listsize)//判断空间是否够用{//续开辟空间}for(j=L.length-1;j>=i-1;j--)//（2）下标L.length-1----i-1的元素，后移一个位置L.elem[j+1]=L.elem[j];L.elem[i-1]=e;//（3）插入e（下标i-1）L.length++;//（4）数据元素长度加一returnOK;}StatusListDelete_Sq(SqList&L,inti,ElemType&e)//删除元素，并用e返回该数据{int*p,*q;if(i<1||i>L.length)//（1）判断插入元素下标i的合法性（1---L.length+1）returnERROR;p=&(L.elem[i-1]);//（2）取第i个元素的地址，并用e取其中数据e=*p;q=L.elem+L.length-1;//最后（表尾）元素的位置for(++p;p<=q;++p)*(p-1)=*p;//（3）元素依次左移--L.length;//（4）元素长度减一returne;}StatusListLength_Sq(SqList&L)//求元素长度{inti,p=0;for(i=0;i<L.length;i++)if(L.elem[i]!='\0')p=p+1;cout<<"Thelengthis"<<p<<"\n";returnOK;}StatusPriorElem_Sq(SqList&L,intcur_e,ElemType&pre_e)//求第cur_e个数据元素的前驱，用pre_e返回{inti,*p=0;for(i=0;i<L.length;i++){if(cur_e==1)//首个元素无前驱{cout<<"不存在前驱"<<endl;break;}elseif(L.elem[i]==L.elem[cur_e-1]){p=&(L.elem[i-1]);pre_e=*p;cout<<"该数前驱为"<<pre_e<<"\n";}}returnOK;}StatusNextElem_Sq(SqList&L,intcur_e,ElemType&next_e)//求第cur_e个数据元素的后继，用next_e返回{inti,*p=0;for(i=0;i<L.length;i++){if(cur_e==L.length)//最后一个元素无后继{cout<<"不存在后继"<<endl;break;}elseif(L.elem[i]==L.elem[cur_e-1]){p=&(L.elem[i+1]);next_e=*p;cout<<"该数后继为"<<next_e<<"\n";}}returnOK;}StatusGetElem(SqListL,inti,ElemType&e)//获取第i个元素{int*p=0;if(i<1||i>L.length)returnERROR;else{p=&(L.elem[i-1]);e=*p;}returne;}StatusDestroyList(SqList&L)//销毁线性表{free(L.elem);//释放空间L.elem=NULL;L.length=0;L.listsize=0;cout<<"线性表已销毁！"<<endl;returnOK;}Statusequal(SqListL,intc1,intc2)//比较两个元素是否相等{if(L.elem[c1]==L.elem[c2])cout<<"相等"<<endl;elsecout<<"不相等"<<endl;returnOK;}intmain(){SqListL1;ElemTypee;ElemTypepre_e,next_e;CreateList_Sq(L1,5);//创建线性表ListInsert_Sq(L1,3,0);//在第三个元素插入cout<<"插入后的线性表："<<endl;OutputList_Sq(L1);cout<<"删除的元素为"<<ListDelete_Sq(L1,3,e)<<endl;//删除第三个元素OutputList_Sq(L1);cout<<"第三个元素为"<<GetElem(L1,3,e)<<endl;//获取第三个元素PriorElem_Sq(L1,3,pre_e);//求第三个元素的前驱NextElem_Sq(L1,3,next_e);//求第三个元素的后继cout<<"判断第二第三个元素是否相等"<<endl;//判断元素是否相等equal(L1,2,3);ListLength_Sq(L1);//求线性表的长度DestroyList(L1);//销毁线性表return1;}