数据结构与算法习题及答案

精心整理

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->datanext; //查找第一个值≥maxk的结点 q=pre->next;pre->next=p;//修改指针 while(q!=p) {s=q->next;deleteq;q=s;}//释放结点空间 }//if } (9)已知p指向双向循环链表中的一个结点,其结点结构为data、prior、next三个域,写出算法change(p),交换p所指向的结点和它的前缀结点的顺序。 知道双向循环链表中的一个结点,与前驱交换涉及到四个结点(p结点,前驱结点,前驱的前驱结点,后继结点)六条链。

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

>>灞曞紑鍏ㄦ枃<<
12@gma联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4