线性表的顺序储存及运算实现-------------顺序表.doc

/线性表的顺序储存及运算实现-顺序表#include /#include using namespace std;#define MAXSIZE 100#define N 30#define M 40/若是其他的数据类型，直接修改这里就可以了typedef int DataType ;/顺序表的定义typedef struct nodeDataType dataMAXSIZE;int length; /顺序表最后一个单元，表示数据长度 SeqList ;/定义指针，实现信息的回送typedef SeqList* PSeqList;/顺序表基本运算的实现/-/顺序表的初始化PSeqList Init_SeqList() /返回一个指向顺序表的指针，指针为NULL表示分配空间失败PSeqList SeqListPoint=new SeqList;/若分配成功，设置空表，否则返回NULLif(SeqListPoint) SeqListPoint-length=0;return SeqListPoint;else cout分配空间失败！MAXSIZE)cout填充顺序表数据大于最大存放数据，无法完成填充！endl;return NULL;for(int i=0;idatai=dataArrayi;SeqListPoint-length=dataArraySize;return SeqListPoint;else cout分配空间失败！length);else cout表不存在！endl;return -1;/输出顺序表数据元素void PrintData_SeqList(PSeqList SeqListPoint)/入口参数：顺序表指针if(!SeqListPoint)cout表不存在!length=0)cout表中无元素！endl;return ;for(int i=0;ilength;i+)coutdatai ;coutendl;return ;/顺序表的检索(查找)操作int Location_SeqList(PSeqList SeqListPoint ,DataType dataX) /入口参数：要查找的顺序表指针，检索的数据，返回值：-1（表不存在），0（失败）int i;if(!SeqListPoint)cout表不存在！endl;return -1;elsefor(i=0;ilength;i+)if(SeqListPoint-datai=dataX)return (i+1);if(i=SeqListPoint-length)cout查找失败！endl;return 0;/顺序表的插入操作int InsertData_SeqList(PSeqList SeqListPoint,int i , DataType dataX) /入口参数：顺序表指针，插入位置，插入的元素。返回标志1成功，0插入位置不合法，-1溢出，-2表示表不存在if(!SeqListPoint)cout表不存在endl;return -2;if( iMAXSIZE) cout插入位置不合法！length-1;j=i-1;j-)SeqListPoint-dataj+1=SeqListPoint-dataj; / 注意：一定不能是j+，而必须是j+1SeqListPoint-datai-1=dataX;SeqListPoint-length+;if(SeqListPoint-lengthMAXSIZE)cout表满,溢出！endl;return -1;return 1;/顺序表的删除运算int Del_SeqList(PSeqList SeqListPoint,int i) /入口参数：顺序表指针，删除元素的位置。返回参数：1成功，0删除位置不合法，-1表不存在if(!SeqListPoint)cout表不存在！endl;return -1;if(iSeqListPoint-length)cout删除位置不合法！endl;return 0;for(int j=i-1;jlength-1;j+)SeqListPoint-dataj=SeqListPoint-dataj+1; / 注意：一定不能是j+，而必须是j+1 SeqListPoint-length-;return 1;/对顺序表数据元素降序排列int SortDec_SeqList(PSeqList SeqListPoint)/入口参数：顺序表指针，成功返回1，表不存在返回-1。if(!SeqListPoint)cout表不存在！endl;return -1;/用选择法排序for(int i=0;ilength-1;i+)DataType Temp;DataType MAX=SeqListPoint-datai;int iMAX=i;for(int j=i+1;jlength;j+)if(SeqListPoint-datajMAX)MAX=SeqListPoint-dataj;iMAX=j; Temp=SeqListPoint-dataiMAX;SeqListPoint-dataiMAX=SeqListPoint-datai;SeqListPoint-datai=Temp;return 1;/对顺序表数据元素升序排列int SortInc_SeqList(PSeqList SeqListPoint)/入口参数：顺序表指针，成功返回1，表不存在返回-1。if(!SeqListPoint)cout表不存在！endl;return -1;/用选择法排序for(int i=0;ilength-1;i+)DataType Temp;DataType MIN=SeqListPoint-datai;int iMIN=i;for(int j=i+1;jlength;j+)if(SeqListPoint-datajdataj;iMIN=j; Temp=SeqListPoint-dataiMIN;SeqListPoint-dataiMIN=SeqListPoint-datai;SeqListPoint-datai=Temp;return 1;/顺序表应用举例/-/ 1、 将一线性表逆置,有一线性表的顺序表示（a1,a2,a3,.an),设计一算法将该线性表逆置为逆线性表（an,an-1,.a3,a2,a1),要求用/ 最小辅助空间int Reverse_SeqList(PSeqList SeqListPoint)/入口参数：一顺序表指针。返回值：1成功，-1表不存在，0为空表if(!SeqListPoint)cout表不存在!length=0)cout为空表！endl;return 0;for(int i=0;ilength/2);i+) /注意不是length+1/2;DataType Temp;Temp=SeqListPoint-datai;SeqListPoint-datai=SeqListPoint-dataSeqListPoint-length-1-i; /注意是length-1-iSeqListPoint-dataSeqListPoint-length-i-1=Temp;return 1;/ 2. 有顺序表A和B，其元素均按从小到大升序排列，编写一算法将他们合并成一个表C，要求C的元素也是从小到大排列int Merge_SeqList(PSeqList SeqListPointA,PSeqList SeqListPointB,PSeqList SeqListPointC)/入口参数：顺序表A，B,C指针。返回值，-1A或B表不存在，-2C溢出，1成功/算法思想：依次扫描AB，并比较它们的大小，将他们较小值赋值给Cif(!SeqListPointA | !SeqListPointB)coutA或B表不存在！length+SeqListPointB-lengthMAXSIZE)cout溢出！endl;return -2;SortInc_SeqList(SeqListPointA);SortInc_SeqList(SeqListPointB); /应想对他们进行升序排列int i=0,j=0,k=0;/循环比较while(ilength-1&jlength-1)if(SeqListPointA-datai dataj)SeqListPointC-datak+=SeqListPointA-datai+;elseSeqListPointC-datak+=SeqListPointB-dataj+;/将余下的部分直接赋值给表Cwhile(ilength)SeqListPointC-datak+=SeqListPointA-datai+;while(jlength)S