【数据结构】线性表(包括有序表)在顺序表和链表上的插入、删除、逆置操作算法

Question

线性表(包括有序表)在顺序表和链表上的插入、删除、逆置操作算法
Java版

Answer 1

1）初始化指针p和q，分别指向链表中相邻的两个元素；

2）当p->next不为空时，做如下处理：
①若相邻两元素不相等时，p和q都向后推一步；
②否则，当相邻元素相等时，删除多余元素。
【算法源代码】
void Delete_Equal(LinkList *L)
{ p=(*L)->next;q=p->next; /*p和q指向相邻的两个元素*/
　while(p->next)
　　{ if(p->data!=q->data) /*若相邻两元素不相等时，p和q都向后推一步*/
　　　　{ p=p->next; q=p->next; }
　　　　else
　　　　{ while(q->data==p->data) /*当相邻元素相等时删除多余元素*/
　　　　　　　　　{ r=q;
　　　　　　　　　　　q=q->next;
　　　　　　　　　　　free(r);
　　　　　　　　　}
　　　　　　　　p->next=q;p=q;q=p->next;
　　　　}/*else*/
　　}/*while*/
}/*Delete_Equal */
试设计一个算法，对带头结点的单链表实现就地逆置。

【算法分析】
1）空表或长度为1的表，不做任何处理；
2）表长大于2时，做如下处理：
①首先将整个链表一分为二，即从链表的第一元素结点处断开；
②逐个地把剩余链表的当前元素q插入到链表的头部。
【算法源代码】
void LinkList_reverse(LinkList L)
{ if(!L->next||!L->next->next) return;
　p=L->next; q=p->next; s=q->next; p->next=NULL; /*从链表的第一元素结点处断开*/
　while(s->next)
　　{q->next=p;p=q;
　　　q=s;s=s->next; /*把L的元素逐个插入新表表头*/
　　}
　q->next=p;　　s->next=q;L->next=s;
}/*LinkList_reverse*/