数据结构考研分类复习真题 第三章 答案[25]

[题目分析] 双端队列示意图如下（设maxsize =）

用上述一维数组作存储结构把它看作首尾相接的循环队列可以在任一端（end或end）进行插入或删除初始状态end+=end被认为是队空状态end=end被认为是队满状态（左端队列）end指向队尾元素的前一位置end指向（右端队列）队尾元素的后一位置入队时判队满出队（删除）时判队空删除一个元素时首先查找该元素然后从队尾将该元素前的元素依次向后或向前（视end端或end端而异）移动

FUNC add (Qu:deque; var x:datatype;tag ):integer;

//在双端队列Qu中插入元素x若插入成功返回插入元素在Qu中的下标插入失败返回tag=表示在end端插入tag=表示在end端插入

IF Quend=Quend THEN [writeln(队满);return();]

CASE tag OF

: //在end端插入

[Quend:=x; //插入x

Quend:=(Quend) MOD maxsize; //修改end

RETURN(Quend+) MOD maxsize); //返回插入元素的下标

: //在end端插入

[Quend:=x;

Quend:=(Quend+) MOD maxsize;

RETURN(Quend) MOD maxsize);

]

ENDC; //结束CASE语句

ENDF; //结束算法add

FUNC delete (Qu: deque; VAR x:datatype; tag:):integer;

//本算法在双端队列Qu中删除元素xtag=时从end端删除tag=时从end端删除删除成功返回否则返回

IF (Quend+) MOD maxsize=Quend THEN [writeln(队空);return();]

CASE tag OF

: //从end端删除

[i:=(Quend+) MOD maxsize; //i是end端最后插入的元素下标

WHILE(i<>Quend) AND (Quelem[i]<>x) DO

i=(i+) MOD maxsize;//查找被删除元素x的位置

IF (Quelem[i]=x) AND (i<>Quend) THEN

[ j:=i;

WHILE((j+maxsize) MOD maxsize <>Quend) DO

[Quelem[j]:=Quelem[(j+maxsize) MOD maxsize];

j:=(j+maxsize) MOD maxsize;

]//移动元素覆盖达到删除

Quend:=(Quend+) MOD maxsize; //修改end指针

RETURN();

]

ELSE RETURN();

]//结束从end端删除

: //从end端删除

[i:=(Quend+maxsize) MOD maxsize; //i是end端最后插入的元素下标

WHILE(i<>Quend) AND (Quelem[i]<>x) DO

i=(i+maxsize) MOD maxsize;//查找被删除元素x的下标

IF (Quelem[i]=x) AND (i<>Quend) THEN //被删除元素找到

[ j:=i;

WHILE((j+) MOD maxsize <>Quend) DO

[Quelem[j]:=Quelem[(j+) MOD maxsize];

j:=(j+) MOD maxsize;

]//移动元素覆盖达到删除

Quend:=(Quend+maxsize) MOD maxsize; //修改end指针

RETURN();//返回删除成功的信息

]

ELSE RETURN();//删除失败

]//结束在end端删除

ENDC;//结束CASE语句

ENDF;//结束delete

[算法讨论]请注意下标运算(i+) MOD maxsize容易理解考虑到i可能为负的情况所以求下个i时用了(i+maxsize) MOD maxsize

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []