C语言从有序递增的顺序表中查找值为x的元素
这里涉及到数据结构中顺序表的实现、删除、插入、查找等知识,请查看:数据结构 -> 线性表
本题代码如下:
问题描述:
线性表(a1, a2, a3, …, an)中元素递增有序且按顺序存储于计算机内。要求设计一算法完成用最少时间在表中查找数值为x的元素,若找到将其与后继元素位置相交换,若找不到将其插入表中并使表中元素仍递增有序。问题解答:
算法思想:顺序存储的线性表递增有序,可以顺序查找,也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”,这里应使用折半查找法。本题代码如下:
void SearchExchangeInsert(ElemType A[], ElemType x){ int low=0, high=n-1; //low和high指向顺序表下界和上界的下标 while(low<=high){ mid = (low+high)/2; //找中间位置 if(A[mid]==x) break; //找到 x,退出 while 循环 else if (A[mid]<x) low = mid+1; //到中点 mid 的右半部去查 else high=mid-1; //到中点mid的左半部去查 } //下面两个if语句只会执行一个 if(A[mid] == x && mid != n-1) { //若最后一个元素与x相等,则不存在与其后继交换的操作 t=A[mid]; A[mid]=A[mid+1]; A[mid+1]=t; } if(low>high) { //查找失败,插入数据元素x for(i=n-1; i>high; i--) A[i+l]=A[i] ; //后移元素 A[i+1]=x; //插入 x } //结束插入 }本题的算法也可以写成三个函数:查找函数、交换后继函数与插入函数。写成三个函数的优点是逻辑清晰、易读。