B.ch2.顺序表

2.2.1顺序表——线性表的顺序存储1、顺序表的定义用一组连续的存储单元（地址连续）依次存放线性表的各个数据元素。即利用数组技术存放元素。•假设线性表的每个元素需占用d个存储单元，则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：LOC(ai+1)=LOC(ai)+d•线性表的第i个数据元素ai的存储位置为LOC(ai)=LOC(a1)+(i-1)×d•LOC(a1)通常称作线性表的起始位置或基地址0x0012f7900x0012f7940x0012f798…2、顺序表的结点地址计算顺序表存储结构示意图a1a2……aiai+1……an地址内容元素在数组中的下标0i-11n-1空闲区idLOC(a1)LOC(a1)+dLOC(a1)+(i-1)dLOC(a1)+(n-1)dLOC(a1)+(MAX-1)dMAX-1一个一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是9８，则Ｍ[３]的第一个字节的地址是113例1因此：LOC(M[3])=98+5×3=113解：地址计算通式为：LOC(ai)=LOC(a0)+L*i3、顺序表数据类型的定义(1)定义数组的体积(最多允许的元素个数)#defineMAX100(2)数据元素类型定义为datatype如：处理学生信息typedefstruct{intn;charname[20];ints;}datatype;如：处理inttypedefintdatatype;3、顺序表数据类型的定义(3)顺序表的类型定义typedefstruct{datatypedata[MAX];/*存放线性表元素的数组*/intlast;/*表示data中实际存放元素个数*/}Seqlist;/*顺序表的数据类型Seqlist*/(4)顺序表变量的定义Seqlistl;/*l为顺序表变量*/Seqlist*lp;/*lp为顺序表指针变量*/结构体变量ldata(数组)last(变量)l.data[i]l.last结构指针lpdata(数组)last(变量)lp-data[i]lp-last2.2.2顺序表基本运算及效率分析•即定义相应运算的C语言函数。•定义函数要确定：–函数名–形参–返回值输入、输出输出1)初始化——建立一个空表空表的表长为0，使顺序表变量中的last为0。函数形参：须初始化顺序表的地址返回值：无算法实现：voidInitlist(Seqlist*lp){lp-last=0;}2)查找在一个已知的顺序表中，查找给定值的元素，找到后返回元素的下标值，没找到返回-1。函数形参：指定顺序表的地址被找元素值返回值：若找到——下标值若未找到——-1共last个元素01……last-1……intLocate(Seqlist*lp,datatypex){inti;for(i=0;ilp-last;i++)if(lp-data[i]==x)returni;return-1;}若datatype是结构类型，不能用“==”直接整体比较，应逐一比较结构中每个成员算法实现：3)插入在顺序表位序为i（1=i=last+1)的位置插入一个新的数据元素x。使长度为last的顺序表变为长度为last+1的顺序表。元素插入位置(1~last+1)a1aialast0…i-1…last-1lastx从表尾开始到下标i-1的元素依次向后移一位DEMO返回值：无（void）插入算法实现：函数形参：指定顺序表的地址插入元素值，插入的位置（1~last+1）intInsert(Seqlist*lp,datatypex,inti){intj;if(lp-last=MAX){printf(\n\tOVERFLOW\n);return(0);}elseif((i1)||(ilp-last+1)){printf(\n\twrongposition\n);return(0);}else{for(j=lp-last-1;j=i-1;j--)lp-data[j+1]=lp-data[j];lp-data[i-1]=x;lp-last=lp-last+1;return(1);}}a1a2…ai…an…移动n-i+1次插入位置移动次数1n最坏O(n)2n-1……n1n+10最好O(1)in-i+1插入算法分析：可能的插入位置为i=1,2,…,n+1共n+1个位置按等概率考虑,则插入概率：pi=1/(n+1)平均移动次数：22)1(11nnnn1111)1(11)1(niniiIinninPE•顺序表插入算法平均约需移动一半元素。4)删除在顺序表中删除位序为i（1=i=last)的元素。使长度为last的顺序表变为长度为last-1的顺序表。删除元素位置(1~last)a1aialast0…i-1…last-1last删除从下标i开始到表尾的元素依次向前移一位DEMOintDelete(Seqlist*lp,inti){intj;if(i1||ilp-last){printf(\n\twrongposition\n);return0;}for(j=i-1;j=lp-last;j++)lp-data[j]=lp-data[j+1];lp-last--;}返回值：无（void）删除算法实现：函数形参：指定顺序表的地址删除元素的位置（下标：1~last）a1a2…ai-1ai…an…移动n-i次删除位置移动次数1n-1最坏O(n)2n-2……n-11n0最好O(1)in-i删除算法分析：可能的删除位置为i=1,2,…,n共n个位置按等概率考虑,则删除概率：pi=1/n平均移动次数：•顺序表删除算法平均约需移动一半元素。niniiIinninPE11)(1)(212)11nnnn（•小结：顺序表插入、删除算法平均约需移动一半结点，当n很大时，算法的效率较低。5)建立顺序表结点类型：typedefstruct{intnum;/*学生学号*/charname[20];/*学生姓名*/intscore;/*成绩*/}datatype;建表要求：按输入顺序依次建表,输入学号为负时结束函数形参：被建顺序表地址返回值：无运算实现：voidCreate(Sqlist*lp)/*建立学生结点顺序表*/{datatype2e;inti=0;/*i为计结点个数变量*/while(1){printf(\nEnternewstudent:);scanf(%d,&e.num);if(e.num0)break;/*若学号值为负结束*/getchar();/*跳过输入学号后的回车换行*/gets(e.name);/*e.name已是地址,前不要加&符*/scanf(%d,&e.score);lp-data[i]=e;i++;}lp-last=i;/*表长就是结点数*/}优点：(1)逻辑结构上相邻的数据元素，其物理位置也相邻。(2)可方便地进行随机存取任一元素——O(1)。缺点：(1)插入和删除平均须移动一半元素——O(n)，效率低。(2)存储分配只能预先进行（静态），不易扩充。过大浪费过小溢出顺序表的优、缺点：应用举例•设元素类型：typedefstruct{intnum;/*学号*/charname[20];/*姓名*/intscore;/*成绩*/}datatype;•要求：合并两个升序(依成绩)顺序表为一个升序的顺序表•算法实现：voidMerge(Seqlist*la,Seqlist*lb,Seqlist*lc){inti,j,k;i=j=k=0;while(ila-last&&jlb-last)/*la和lb表都未取完元素*/if(la-data[i].score=lb-data[j].score)lc-data[k++]=la-data[i++];elselc-data[k++]=lb-data[j++];while(ila-last)/*la表未取完元素*/lc-data[k++]=la-data[i++];while(jla-last)/*lb表未取完元素*/lc-data[k++]=lb-data[j++];lc-last=la-last+lb-last;}顺序表上机题：建一学生信息(学号、姓名、成绩)顺序表，根据成绩及格和不及格分成两个表，并分别打印输出。