《基本数据结构及其运算-02顺序表.ppt》由会员分享，可在线阅读，更多相关《基本数据结构及其运算-02顺序表.ppt（37页珍藏版）》请在金锄头文库上搜索。
1、2.2线性表及其顺序存储结构一、线性表及其运算一、线性表及其运算线性表线性表定义：定义： n n（ 0 0）个数据元素的有限序列，记作个数据元素的有限序列，记作（a1, ai-1, ai, ai+1, an） 其中其中,ai 是表中数据元素，是表中数据元素，n 是表长度。是表长度。特点特点: n同一线性表中元素具有相同特性。同一线性表中元素具有相同特性。n相邻数据元素之间存在序偶关系。相邻数据元素之间存在序偶关系。n除第一个元素外，其他每一个元素有一个且仅除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。有一个直接前驱。n除最后一个元素外，其他每一个元素有除最后一个元素外，其他每一个元素
2、有一个且仅有一个直接后继。一个且仅有一个直接后继。顺序表顺序表定义：定义：将线性表中的元素相继存放在一将线性表中的元素相继存放在一个连续的存储空间中。个连续的存储空间中。 存储结构：存储结构：数组。数组。特点：特点：线性表的顺序存储方式。线性表的顺序存储方式。存取方式：随机存取方式：随机存取存取顺序存储结构示意图顺序存储结构示意图45 89 90 67 40 78 0 1 2 3 4 5 顺序表的存储方式：顺序表的存储方式：LOC(a i+1) = LOC( a 1 )+(i-1)*lLOC(a i) = LOC(a1)+(i-1)*l a1 a2 a i an 1 2 i n a a+l a
3、+(i-1)*l a+(n-1)*l idle顺序表（顺序表（SeqList）的类型定义的类型定义#define ListSize 100 /最大允许长度最大允许长度typedef int ListData; typedef struct ListData datalistsize; /存储空间基址存储空间基址 int length; /当前元素个数当前元素个数SeqList; 顺序表基本运算顺序表基本运算n初始化初始化 void InitList ( SeqList & L ) L.data = ( ListData * ) malloc (sizeof ( SEQList ) ); if
4、( L.data = NULL ) printf ( “存储分配失败存储分配失败!n” ); exit (1); L.length = 0; 按值查找按值查找：找找x x在表中的位置，若查找成功，在表中的位置，若查找成功，返回表项的位置，否则返回返回表项的位置，否则返回-1-1 int Find ( SeqList L, ListData x ) int i = 0; while ( i L.length & L.datai != x ) i+; if ( i = 0 & i =0 & i 0 & i L.length ) return l.datai-11;else return nulln
5、ull; 插入插入25 34 57 16 48 09 63 0 1 2 3 4 5 6 750插入 x25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 750i顺序表插入时，平均数据移动次数顺序表插入时，平均数据移动次数AMN在各表项在各表项插入概率相等时插入概率相等时顺序表的插入顺序表的插入 int Insert ( SeqList &L, ListData x, int i ) /在表中第在表中第 i 个位置插入新元素个位置插入新元素 x if (i L.length | L.length = ListSize) return 0; /插入不成功插入不成功 els
6、e for ( j = L.length; j i; j- ) L.dataj = L.dataj - -1; L.datai = x; L.length+; return 1; /插入成功插入成功 删除删除25 34 57 50 16 48 09 63 16删除 x25 34 57 50 48 09 63 0 1 2 3 4 5 6 7顺序表删除平均数据移动次数顺序表删除平均数据移动次数AMN在各表项在各表项删除概率相等时删除概率相等时顺序表的删除顺序表的删除 int Delete ( SeqList &L, ListData x ) /在表中删除已有元素在表中删除已有元素 x int i
7、= Find (L, x); /在表中查找在表中查找 x if ( i = 0 ) L.length - ; for ( int j = i; j L.length; j+ ) L.dataj = L.dataj+1; return 1; /成功删除成功删除 return 0; /表中没有表中没有 x 顺序表的应用顺序表的应用:集合的集合的“并并”运算运算void Union ( SeqList &A, SeqList &B ) int n = Length ( A ); int m = Length ( B ); for ( int i = 0; i m; i+ ) int x = GetD
8、ata ( B, i ); /在在B中取一元素中取一元素 int k = Find (A, x); /在在A中查找它中查找它 if ( k = - -1 ) /若未找到插入它若未找到插入它 Insert ( A, x, n ); n+; 集合的集合的“交交”运算运算 void Intersection ( SeqList &A, SeqList &B ) int n = Length ( A ); int m = Length ( B ); int i = 0; while ( i -top = 0 ; 入栈入栈int Push (SeqStack S, StackData x) if (St
9、ackFull (S) )return 0; /失败失败 else (S.dataS.top)=x; (S.top)+;Return 1取栈顶元素取栈顶元素int Gettop (SeqStack S) if ( StackEmpty(S) ) return error; else return (S.datas.datas.top-1);出栈出栈int pop (SeqStack S )/若栈空返回若栈空返回0, 否则栈顶元素退出到否则栈顶元素退出到x并返回并返回1if ( StackEmpty(S) ) return error; else return (S.datas.datas.to
10、p-1);( (S. .top) -;三、队列三、队列定义定义:只允许在表的一端进行插入，而在只允许在表的一端进行插入，而在另一端删除元素的线性表。另一端删除元素的线性表。在队列中，允许插入的一端叫队尾在队列中，允许插入的一端叫队尾（rear），允许删除的一端称为对头允许删除的一端称为对头(front)。特点：特点：先进先出先进先出 (FIFO) a1 ，a2， a3，an出队列出队列入队列入队列队队头头队队尾尾队列的主要运算队列的主要运算（1）设置一个空队列；（）设置一个空队列；（2）插入一个新的队尾元素，称为进队；）插入一个新的队尾元素，称为进队；（3）删除队头元素，称为出队；（）删除队头
11、元素，称为出队；（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)线性队列线
12、性队列 3 2 1 0 (a)rear=front= -1(队空）队空） e3 e4 (c)(c)e1,e2出队，出队，e4入队入队 队队 满满rear =4front e1 e2 e3 (b)rearfront(b)e1,e2,e3入队入队和和栈栈一一样样，用用顺顺序序结结构构表表示示队队列列是是一一种种简简单单的的方方法法，通通常常用用一一维维数数组组实实现现，其其中中MAX表表示示队队列列允允许许的的最最大大容容量量，在在队队的的两两端端设设置置两两个个整整型型变变量量作作指指针针，front为为头头指指针针，rear为为尾尾指针。指针。队空时，队空时， 令令rear=front= -1
13、，当有当有新元素入队时，尾指针加新元素入队时，尾指针加1，当有元，当有元素出队时，头指针加素出队时，头指针加1。故在非空队。故在非空队列中，列中，头指针头指针始终指向始终指向队头元素前一队头元素前一个位置个位置，而，而尾指针尾指针始终指向始终指向队尾元素队尾元素的位置的位置 MAX=4假设假设MAX=4，当队列处于图（，当队列处于图（c）状态，）状态，rear+1=4时队满，时队满，此时不能插入新元素，但实际上队列可用空间没有满，这是此时不能插入新元素，但实际上队列可用空间没有满，这是一种假溢出现象。解决方法：将队列头尾相连形成一个环。一种假溢出现象。解决方法：将队列头尾相连形成一个环。线性队
14、列队满的条件：线性队列队满的条件： rear + 1 = MAX线性队列队空的条件：线性队列队空的条件： rear = front 3 2 1 0 (a)rear=front= -1(队空）队空） e3 e4 (c)(c)e1,e2出队，出队，e4入队入队 队队 满满rear =4front e1 e2 e3 (b)rearfront(b)e1,e2,e3入队入队 MAX=4(b) 循环队列循环队列 rear front 0 1 2 3(3) 队空队空区别队空与队满的方法：如果区别队空与队满的方法：如果队尾加队尾加1后等于队头指针即为队后等于队头指针即为队满，即少用一个元素空间。满，即少用一个
15、元素空间。将将头头尾尾连连接接成成一一个个环环，形形成成循循环环队列。队列。 rear(1)一般情况一般情况 front 0 1 2 3e4e3循环队列队空的条件：循环队列队空的条件： rear=front (2) 全部空间占满全部空间占满 front e3 e4 0 1 2 3 reare5e2循环队列全部空间占满循环队列全部空间占满 rear=front(b) 循环队列循环队列 rear front 0 1 2 3(3) 队空队空队满条件队满条件：(rear+1)%MAX=front注：实际上为了避免与队空标注：实际上为了避免与队空标志冲突，还留有一个空间。志冲突，还留有一个空间。将将头头
16、尾尾连连接接成成一一个个环环，形形成成循循环环队列。队列。 rear(1)一般情况一般情况 front 0 1 2 3e4e3 (2) 队满队满 front e3 e4 0 1 2 3 reare5%-取余数运算符。取余数运算符。当指针处于当指针处于MAX-1，下一个位置为下一个位置为“0”，而非，而非MAX。循环队列的循环队列的类型表示类型表示:#define queue_SIZE 100；typedef struct QueueData dataQueue_SIZE; int front,rear; Queue；循环队列中加入一个元素的算法（入队算法）：循环队列中加入一个元素的算法（入队算
17、法）： int EnQueue(Queue Q, QueueData x) if(q.rear+1)%MAX= =q.front) return 0; else q.rear=(q.rear+1)%MAX; Q.dataq.rear=x; return(1); 循环队列中删除一个元素的算法：循环队列中删除一个元素的算法：QueueData DeQueue(Queue Q) if(q.rear= =q.front) return error; else q.front=(q.front+1)%MAX; return(q.dataq.front); an a2 a1 an a3 a2 Q.fron
18、tQ.rear 删删 除除 一个元素一个元素 添加添加 一个元素一个元素 a1 a2 anQ.frontQ.rear （2） 链式存储结构链式存储结构Q.frontQ.rear队头队尾Q.rear链队列的类型定义链队列的类型定义 e头结点链式队列插入算法链式队列插入算法: （在队尾加入）Status EnQueue(LinkQueue &Q,QElemType e) p=(QueuePtr)malloc(sizeof(Qnode); if(!p) exit(OVERFLOW); p-data=e; p-next=NULL; Q.rear-next=p;Q.rear=p; Return OK;删除一个元素的算法：删除一个元素的算法：/ 在队头删除Status DeQueue(LinkQueue &Q, QElemType &e)if(Q.front=Q.rear)return ERROR; /队空队空p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p) Q.rear=Q.front; /队列为空时队尾指针需队列为空时队尾指针需重新赋值重新赋值free(p);Return OK;
