第02章 基本数据结构及其运算-02顺序表

2.2线性表及其顺序存储结构一、线性表及其运算线性表定义：n（0）个数据元素的有限序列，记作（a1,…ai-1,ai,ai+1,…,an）其中,ai是表中数据元素，n是表长度。特点:同一线性表中元素具有相同特性。相邻数据元素之间存在序偶关系。除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。顺序表定义：将线性表中的元素相继存放在一个连续的存储空间中。存储结构：数组。特点：线性表的顺序存储方式。存取方式：顺序存取顺序存储结构示意图458990674078012345顺序表的存储方式：LOC(ai+1)=LOC(ai)+(i-1)*lLOC(ai)=LOC(a1)+(i-1)*la1a2…ai………an12…i………naa+l…a+(i-1)*l………a+(n-1)*lidle顺序表（SeqList）的类型定义#defineListSize100//最大允许长度typedefintListData;typedefstruct{ListDatadata[listsize];//存储空间基址intlength;//当前元素个数}SeqList;顺序表基本运算初始化voidInitList(SeqList&L){L.data=(ListData*)malloc(ListSize*sizeof(ListData));if(L.data==NULL){printf(“存储分配失败!\n”);exit(1);}L.length=0;}按值查找：找x在表中的位置，若查找成功，返回表项的位置，否则返回-1intFind(SeqList&L,ListDatax){inti=0;while(iL.length&&L.data[i]!=x)i++;if(iL.length)returni;elsereturn-1;}求表的长度intLength(SeqList&L){returnL.length;}提取函数：在表中提取第i个元素的值ListDataGetData(SeqList&L,inti){if(i=0&&iL.length)returnL.data[i];elseprintf(“参数i不合理！\n”);}按值查找：寻找x的后继listdataNext(SeqList&L,ListDatax){inti=Find(L,x);if(i=0&&iL.length)returnl.data[i+1];elsereturnnull;}寻找x的前驱intNext(SeqList&L,ListDatax){inti=Find(L,x);if(i0&&i=L.length)returni-1;elsereturn-1;}插入221)(1)(10)1(011)(11=nnnnnnininnAMN253457164809630123456750插入x25345750164809630123456750i顺序表插入时，平均数据移动次数AMN在各表项插入概率相等时顺序表的插入intInsert(SeqList&L,ListDatax,inti){//在表中第i个位置插入新元素xif(i0||iL.length||L.length==ListSize)return0;//插入不成功else{for(j=L.length;ji;j--)L.data[j]=L.data[j-1];L.data[i]=x;L.length++;return1;//插入成功}}删除102121)(11)(1=ninnnninnAMN253457501648096316删除x2534575048096301234567顺序表删除平均数据移动次数AMN在各表项删除概率相等时顺序表的删除intDelete(SeqList&L,ListDatax){//在表中删除已有元素xinti=Find(L,x);//在表中查找xif(i=0){L.length--;for(intj=i;jL.length;j++)L.data[j]=L.data[j+1];return1;//成功删除}return0;//表中没有x}顺序表的应用:集合的“并”运算voidUnion(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);for(inti=0;im;i++){intx=GetData(B,i);//在B中取一元素intk=Find(A,x);//在A中查找它if(k==-1)//若未找到插入它{Insert(A,x,n);n++;}}}集合的“交”运算voidIntersection(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);inti=0;while(in){intx=GetData(A,i);//在A中取一元素intk=Find(B,x);//在B中查找它if(k==-1){Delete(A,i);n--;}elsei++;//未找到在A中删除它}}二、栈及其应用定义:是限定仅在表尾进行插入或删除操作的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点：后进先出(LIFO)a1topbottoman....进栈出栈栈的主要操作ADTStack{//对象由数据类型为StackData的元素构成intPush(stack*S,StackDatax);//进栈intPop(stack*S,StackData&x);//出栈intGetTop(stack*S,StackData&x);//取栈顶voidInitStack(stack*S);//置空栈intStackEmpty(stack*S);//判栈空否intStackFull(stack*S);//判栈满否}栈的表示和实现顺序栈：栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，指针top指向栈顶元素在顺序栈中的下一个位置，base为栈底指针，指向栈底的位置。base空栈a进栈b进栈aabtopbasetopbasetoptoptopabcdee进栈abcdef进栈溢出abde出栈cbasebasebasetop顺序栈的类型表示:#defineSTACK_SIZE100；typedefstruct{//顺序栈定义intdata[STACK_SIZE];inttop;//栈顶指针}SeqStack；判栈空intStackEmpty(SeqStack*S){if(S.top==0)return1//判栈空,空则返回1elsereturn0;//否则返回0}判栈满intStackFull(SeqStack*S){if(S.Top==STACK_SIZE)return1//判栈满,满则返回1elsereturn0;//否则返回0}顺序栈的基本运算:初始化voidInitStack(SeqStack*S){S-top=0;}入栈intPush(SeqStackS,StackDatax){if(StackFull(S))return-1;//失败else{(S.data[S.top])=x;(S.top)++;Return1}}取栈顶元素intGettop(SeqStackS){if(StackEmpty(S))returnerror;elsereturn(S.data[s.top-1]);}出栈intpop(SeqStackS){//若栈空返回0,否则栈顶元素退出到x并返回1if(StackEmpty(S))returnerror;else{return(S.data[s.top-1]);(S.top)--;}}三、队列定义:只允许在表的一端进行插入，而在另一端删除元素的线性表。在队列中，允许插入的一端叫队尾（rear），允许删除的一端称为对头(front)。特点：先进先出(FIFO)a1，a2，a3，…，an出队列入队列队头队尾队列的主要运算（1）设置一个空队列；（2）插入一个新的队尾元素，称为进队；（3）删除队头元素，称为出队；（4）读取队头元素；2.3.2队列2.3.2.1队列的定义与运算定义：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表。此种结构称为先进先出（FIFO）表。设队列q=(a1,a2,a3,…,an)中，a1是允许删除的一端，称为队头（front），an是允许插入的一端为队尾（rear）。a1,a2,a3,a4,…………an-1,an队列示意图队头队尾先进先出FIFO队列的存储结构（1）顺序存储结构(a)线性队列3210(a)rear=front=-1(队空）e3e4(c)(c)e1,e2出队，e4入队队满rear=4fronte1e2e3(b)rearfront(b)e1,e2,e3入队和栈一样，用顺序结构表示队列是一种简单的方法，通常用一维数组实现，其中MAX表示队列允许的最大容量，在队的两端设置两个整型变量作指针，front为头指针，rear为尾指针。队空时，令rear=front=-1，当有新元素入队时，尾指针加1，当有元素出队时，头指针加1。故在非空队列中，头指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素的位置MAX=4假设MAX=4，当队列处于图（c）状态，rear+1=4时队满，此时不能插入新元素，但实际上队列可用空间没有满，这是一种假溢出现象。解决方法：将队列头尾相连形成一个环。线性队列队满的条件：rear+1=MAX线性队列队空的条件：rear=front3210(a)rear=front=-1(队空）e3e4(c)(c)e1,e2出队，e4入队队满rear=4fronte1e2e3(b)rearfront(b)e1,e2,e3入队MAX=4(b)循环队列rearfront0123(3)队空区别队空与队满的方法：如果队尾加1后等于队头指针即为队满，即少用一个元素空间。将头尾连接成一个环，形成循环队列。e4e3循环队列队空的条件：rear=front(2)全部空间占满fronte3e40123reare5e2循环队列全部空间占满rear=front(b)循环队列rearfront0123(3)队空队满条件：(rear+1)%MAX=front注：实际上为了避免与队空标志冲突，还留有一个空间。将头尾连接成一个环，形成循环队列。e4e3(2)队满fronte3e40123reare5%--取余数运算符。当指针处于MAX-1，下一个位置为“0”，而非MAX。循环队列的类型表示:#definequeue_SIZE100；typedefstruct{QueueDatadata[Queue_SIZE];intfront,rear;}Queue；循环队列中加入一个元素的算法（入队算法）：intEnQueue(QueueQ,QueueDatax){if((q.rear+1)%MAX==q.front)return0;else{q.rear=(q.rear+1)%MAX;Q.data[q.rear]=x;return(1);}}循环队列中删除一个元素的算法：QueueDataDeQueue(QueueQ){if(q.rear==q.front)returnerror;else{q.front=(q.front+1)%MAX;return(q.data[q.front]);}}ana2a1ana3a2Q.frontQ.rear删除一个元素添加一个元素^a1a2anQ.frontQ.rear（2）链式存储结构Q.frontQ.rear队头队尾Q.rear链队列的类型定义e头结点链式队列插入算法:（在队尾加入）StatusEnQueue(LinkQueue&Q,QElemTypee){p=(QueuePtr)malloc(siz