请帮帮我，急！急！急！！！！！！！！！！！(100分)

L

lescape

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-05-31

• #1

这题怎么写:
假设以带头结点的单循环链表作非递减有序线性表的存储结构.请设计一个时间复杂度为O的算法,删除表中所有数值相同的多余元素,并Free结点空间.
例如(7,10,10,21,30,42,42,42,51,70)经算法操作后变为(7,10,21,30,42,51,70)

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-05-31

• #2

伪码如下：
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;

 

来

来如风

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-05-31

• #3

时间复杂度为O：你从头接点遍历到最后就可以了，如果当前的值等于前一个的话就删除此接点

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-05-31

• #4

忘了释放空间：
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;

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-05-31

• #5

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

 

L

lescape

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-05-31

• #6

老大,这是<数据结构>试题,请用C语言回答,好吗?

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-06-01

• #7

p=List;
while (p->next) {
if (p->data==p->next->data) {
q=p->next;
p->next=q->next;
Free(q);
}
else
p=p->next;
}

 

L

lescape

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-06-02

• #8

to LeeChange
非常感谢,

 

L

lescape

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-06-07

• #9

多人接受答案了。