文档介绍：算法与数据结构复****br/>:如果对循环队列采用设置运算标志的方式
来区分队列的满和空的状态,试给出对应的各运算实现。
在队列的类定义里加入一个标志位tag。
queue::queue( )
{ count = 0; front = rear = 0; tag=0; }
bool queue::empty( ) const
{
if ( front==rear&&tag==0) return true;
else return false;
}
bool queue::full( )const
{
if ( front==rear&&tag==1) return true;
else return false;
}
error_code queue::append(const elementtype x)
{
if ( full() ) return overflow;
rear = ( rear + 1 ) % maxlen ;
data[rear] = x;
count ++;
tag=1;
return ess;
}
error_code queue::serve()
{
if ( empty() ) return underflow;
front = ( front + 1 ) % maxlen;
count --;
tag=0;
return ess;
}
:如果采用带尾指针的单循环链表作为队列的存储结构,设计算法以实现队列的各运算。
q1
q2
qn
...
队头元素
队尾元素
rear
queue::queue( ){
rear = new node;
rear -> next = rear;
count = 0;
}
bool stack::empty( ) const
{ return rear->next==rear; }
error_code queue::get_front(elementtype &x) const
{ if ( empty() ) return underflow;
x = rear -> next->next -> data;
return ess;
}
error_code queue::append(const elementtype x ){
node* s = new node; s -> data = x;
s->next=rear->next; rear -> next = s; rear = s;
count ++;
return ess;
}
error_code queue::serve(){
if ( empty() )
return underflow;
node* front = rear -> next;
node * u=front->next;
front-> next = u -> next;
delete u;
count --;
if ( front -> next == NULL ) rear = front;
return ess;
}
:递增有序顺序表A、B分别表示一个集合,设计算法
求解A=A-B,并分析其时间性能。
data[ia]<data[ib]: A当前元素不在B中,ia++
data[ia]>data[ib]: A当前元素可能在B中,ib++
data[ia]=data[ib]: 删除A当前元素, ib++;
void subtraction(list &A, list B)
{
int ia,ib,x,y;
ia=ib=1;
while(ia<=()&&ib<=())
{
(ia,x); (ib,y);
if(x<y) ia++;
else if(x>y) ib++;
else
{ (ia); ib++;}
}
}
时间性能:O(|A|+|B|)<br****题2:假设递增有序顺序表A、B分别表示一个集合,设计
算法求解C=A∩B,并分析其时间性能。
data[ia]<data[ib]: A当前元素不在B中,ia++
data[ia]>data[ib]: A当前元素可能在B中,ib++
data[ia]=data[ib]: 将该元素插入C表中 ia++,ib++,ic++
void intersection(list A, list B, list &C)
{
int ia,ib,ic,x,y;
ia=ib=ic=1;
whil