4.1假设一个线性表包含下列元素：<|2,23,15,5,9>使用Shaffer编写的教材《数据结构与算法分析》的ListADT编写一些C++语句，删除值为15的元素。4.6使用Shaffer编写的教材《数据结构与算法分析》的LList类，给LList类的实现添加一个成员函数，倒置线性表中元素的顺序。对于n个元素的线性表，算法的运行时间应该为Θ(n)。4.18已知Q是一个非空队列，S是一个空栈。仅用栈和队列的ADT函数和一个成员变量X编写一个算法，使得Q中的元素位置倒置。

2022-07-24

4.1假设一个线性表包含下列元素：<|2,23,15,5,9>使用Shaffer编写的教材《数据结构与算法分析》的ListADT编写一些C++语句，删除值为15的元素。4.6使用Shaffer编写的教材《数据结构与算法分析》的LList类，给LList类的实现添加一个成员函数，倒置线性表中元素的顺序。对于n个元素的线性表，算法的运行时间应该为Θ(n)。4.18已知Q是一个非空队列，S是一个空栈。仅用栈和队列的ADT函数和一个成员变量X编写一个算法，使得Q中的元素位置倒置。

答案：

4.1L1.setstart();L1.next();L1.next();val=L1.remove();4.6templatevoidLList::reverse(){//Reverselistcontentsif(head->next==NULL)return;//First,fixfencebypushingitforwardonestepif(fence->next==NULL)fence=head;elsefence=fence->next;//Now,reversethelistlink*temp1=head->next;link*temp2=temp1->next;while(temp2!=NULL){link*temp3=temp2->next;temp2->next=temp1;temp1=temp2;temp2=temp3;}head->next=temp1;}4.18void reverse(Queue& Q, Stack& S) {ELEM X;while (!Q.isEmpty()) {X = Q.dequeue();S.push(X);}while (!S.isEmpty()) {X = S.pop();Q.enqueue(X);}}

举一反三

内容

0
在一个长度为n的顺序表中删除第i(0≤i≤n一1)个元素,需向前移动( )个元素。
1
已知Q是一个非空队列，S是一个空栈。仅用队列和栈的ADT函数和少量工作变量，使用 PASCAl或C语言编写一个算法，将队列Q中的所有元素逆置。的ADT函数有：makeEmpty ( s: stack ) ;//置空栈push ( s :stack ; value:datatype ) ;//新元素value入栈pop ( s : stack ) :datatype;//出栈，返回栈顶值isEmpty ( s :stack ) : Boolean ;//判栈空否队列的ADT函数有:enQueue( q:queue:value:datatype);//元素value进队deoueue (q:queue ) : datatype ;//出队列,返回队头值isEmpty(q:queue ) : boolean ;//判队列空否
2
设顺序线性表中有n个数据元素，删除第i个位置上的数据元素需要移动表中( )个元素。
3
编程：已知Q是一个非空队列，S是一个空栈。编写算法，仅用队列和栈的ADT函数和少量工作变量，将队列Q的所有元素逆置。栈的ADT函数有：void makeEmpty(SqStack s); 置空栈void push(SqStack s,ElemType e); 元素e入栈ElemType pop(SqStack s); 出栈，返回栈顶元素int isEmpty(SqStack s); 判断栈空队列的ADT函数有：void enQueue(Queue q,ElemType e); 元素e入队ElemType deQueue(Queue q); 出队，返回队头元素int isEmpty(Queue q); 判断队空
4
在含有n个元素的顺序存储的线性表中，在任一元素前插入一个元素所需移动元素的平均次数为