精心整理
ElemTypeMax(LinkListL){
if(L->next==NULL)returnNULL;
pmax=L->next;//假定第一个结点中数据具有最大值 p=L->next->next;
while(p!=NULL){//如果下一个结点存在 if(p->data>pmax->data)pmax=p; p=p->next; }
returnpmax->data;
(7)设计一个算法,通过遍历一趟,将链表中所有结点的链接方向逆转,仍利用原表的存储空间。 voidinverse(LinkList&L){ //逆置带头结点的单链表L p=L->next;L->next=NULL; while(p){ q=p->next;//q指向*p的后继 p->next=L->next; L->next=p;//*p插入在头结点之后 p=q; } } (8)设计一个算法,删除递增有序链表中值大于mink且小于maxk的所有元素(mink和maxk是给定的两个参数,其值可以和表中的元素相同,也可以不同)。 voiddelete(LinkList&L,intmink,intmaxk){ p=L->next;//首元结点 while(p&&p->data<=mink) {pre=p;p=p->next;}//查找第一个值>mink的结点 if(p){ while(p&&p->data
voidExchange(LinkedListp)
∥p是双向循环链表中的一个结点,本算法将p所指结点与其前驱结点交换。 {q=p->llink;
q->llink->rlink=p;∥p的前驱的前驱之后继为p p->llink=q->llink;∥p的前驱指向其前驱的前驱。 q->rlink=p->rlink;∥p的前驱的后继为p的后继。 q->llink=p;∥p与其前驱交换
p->rlink->llink=q;∥p的后继的前驱指向原p的前驱 精心整理
精心整理
p->rlink=q;∥p的后继指向其原来的前驱 }∥算法exchange结束。 (10)已知长度为n的线性表A采用顺序存储结构,请写一时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除线性表中所有值为item的数据元素。
[题目分析]在顺序存储的线性表上删除元素,通常要涉及到一系列元素的移动(删第i个元素,第i+1至第n个元素要依次前移)。本题要求删除线性表中所有值为item的数据元素,并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针(i=1,j=n),从两端向中间移动,凡遇到值item的数据元素时,直接将右端元素左移至值为item的数据元素位置。
voidDelete(ElemTypeA[],intn)
∥A是有n个元素的一维数组,本算法删除A中所有值为item的元素。 {i=1;j=n;∥设置数组低、高端指针(下标)。 while(i