请帮帮我,急!急!急!!!!!!!!!!!(100分)

  • 主题发起人 主题发起人 lescape
  • 开始时间 开始时间
L

lescape

Unregistered / Unconfirmed
GUEST, unregistred user!
这题怎么写:
假设以带头结点的单循环链表作非递减有序线性表的存储结构.请设计一个时间复杂度为O(n)的算法,删除表中所有数值相同的多余元素,并Free结点空间.
例如(7,10,10,21,30,42,42,42,51,70)经算法操作后变为(7,10,21,30,42,51,70)
 
伪码如下:
p:=List;
if p<>nil then
begin
q:=p^.next;
while q<>nildo
begin
if p^.data=q^.data then
begin
q:=q^.next;
if q=nil then
p^.next:=q
end
else
begin
p^.next:=q;
p:=q;
q:=q^.next
end
end
end;
 
时间复杂度为O(n):你从头接点遍历到最后就可以了,如果当前的值等于前一个的话就删除此接点
 
忘了释放空间:
p:=List;
if p<>nil then
begin
q:=p^.next;
while q<>nildo
begin
if p^.data=q^.data then
begin
r:=q;
q:=q^.next;
Free(r);
if q=nil then
p^.next:=q
end
else
begin
p^.next:=q;
p:=q;
q:=q^.next
end
end
end;
 
p:=List;
while p^.next<>nildo
begin
if p^.data=p^.next^.data then
begin
q:=p^.next;
p^.next:=q^.next;
free(q)
end
else
p:=p^.next
end
 
老大,这是<数据结构>试题,请用C语言回答,好吗?
 
p=List;
while (p->next) {
if (p->data==p->next->data) {
q=p->next;
p->next=q->next;
Free(q);
}
else
p=p->next;
}
 
to LeeChange
非常感谢,
 
多人接受答案了。
 
后退
顶部