数据结构考研分类复习真题 第二章 答案[31]

．[题目分析] 知道双向循环链表中的一个结点与前驱交换涉及到四个结点(p结点前驱结点前驱的前驱结点后继结点)六条链

void Exchange(LinkedList p)∥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结束

．[题目分析] 顺序存储的线性表递增有序可以顺序查找也可折半查找题目要求用最少的时间在表中查找数值为x的元素这里应使用折半查找方法

void SearchExchangeInsert(ElemType a[];ElemType x)∥a是具有n个元素的递增有序线性表顺序存储本算法在表中查找数值为x的元素如查到则与其后继交换位置;如查不到则插入表中且使表仍递增有序

{ low=;high=n;∥low和high指向线性表下界和上界的下标

while(low<=high)

{mid=(low+high)/;∥找中间位置

if(a[mid]==x) break;∥找到x退出while循环

else if (a[mid] <x) low=mid+;∥到中点mid的右半去查

else high=mid;∥到中点mid的左部去查

}

if(a[mid]==x && mid!=n)∥若最后一个元素与x相等则不存在与其后继交换的操作

{t=a[mid];a[mid]=a[mid+];a[mid+]=t;}∥数值x与其后继元素位置交换

if(low>high)∥查找失败插入数据元素x

{for(i=n;i>high;i) a[i+]=a[i];∥后移元素

a[i+]=x;∥插入x

}∥结束插入

}∥结束本算法

[算法讨论] 首先是线性表的描述算法中使用一维数组a表示线性表未使用包含数据元素的一维数组和指示线性表长度的结构体若使用结构体对元素的引用应使用aelem[i]另外元素类型就假定是ElemType未指明具体类型其次C中一维数组下标从开始若说有n个元素的一维数组其最后一个元素的下标应是n第三本算法可以写成三个函数查找函数交换后继函数与插入函数写成三个函数显得逻辑清晰易读

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []