线性表算法总结PPT课件.pptx

文档介绍：
例二：删除有序表中相同的数据元素
void Delete_Equale(SqList La)
{
i=0;j=1；
while (j<)
{
if ([i]!=[j]){
i=i+1;
[i]=[j];
}
j=j+1;
}
=i++
}
分析:顺序表中每删除一个数据元素,被删元素后的元素都要依次向前移动一个位置, 浪费大量的时间.
可以每做一次删除,只做标记,最后一次将剩余元素移动到位
试做此算法－－懒惰删除
另给出一巧妙算法
第1页/共43页

例二：删除有序表中相同的数据元素
void Delete_Equale(LinkList L)
{
pre=L->next;p=pre->next；
while (p!=NULL)
{
if (pre->data!=p->data){
pre=p;p=p->next;
}
else{
u=p; p=p->next;
pre->next=p; free(u);
}
}
第2页/共43页

例三：线性表的就地逆置
void reverse(SqList LA){//使用两个控制变量
ElemType t;
for(i=0,j=-1;i<j;i++,j--)
{
t=[i]; [i]= [j]; [j]=t;
}
}
void reverse(SqList &LA){//使用一个控制变量
ElemType t; n=;
for(i=0;i<=(n-1)/2;i++)
{
t=[i]; [i]= [n-i-1];[n-i-1]=t;
}
}
第3页/共43页
a1
a2
a3

L
L
p

succ
a1

p
succ
a2
p
succ
a3
p
思路一：
1）标志后继结点；
2）修改指针（将*p插入在头结点之后）；
3）重置结点*p（p重新指向原表中后继）；

（1）带头结点单链表
第4页/共43页
void inverse(LinkList L) {
// 逆置带头结点的单链表 L
p=L->next; L->next=NULL;
while ( p) {
succ=p->next; // succ指向*p的后继
p->next=L->next;
L->next=p; // *p插入在头结点之后
p = succ;
}
}
第5页/共43页
void inverse(LinkList L) {
p=L->next; pre=NULL;
while ( p) {
succ=p->next; // succ指向*p的后继
p->next=pre; pre=p;
p = succ;}
L->next=pre;
}
思考：不带头结点单链表逆置？带头结点单循环链表逆置
思路二:直接修改结点的指针域,指向原来链表上其直接前驱结点
第6页/共43页