1. 用c++编程顺序表的查找
既然是由小到大，那么应该要的是二分查找了
#include<iostream>
using namespace std;
int n,m;
int a[100001];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
cin>>m;
for(int i=1;i<=m;i++)
{
int xx;
cin>>xx;
int l=1,r=n;
while(l<r)
{
int mid=l+r>>1;
if(a[mid]==xx)
{
cout<<mid<<endl;
break;
}
if(a[mid]>xx) r=mid-1;
else l=mid+1;
}
cout<<"No Found!";
}
}
我这里没有办法进行测试，但是应该没有问题的，如果有bug就追问，我会尽快修改
2. 要求能实现顺序表的三种查找算法：顺序查找，二分查找，散列查找（通过菜单实现）
你有学过数据结构没有？
你看一下，看了有哪不懂的可以问我！
我再帮你解答，你这一下让我写程序，我没时间写啊！
//我暂时就给你写了二分查找的，其它的过两天给你，我没时间写啊，一直都有课
#include<iostream>
using namespace std;
const int size =5;
//*****
bool find(int num[],int first,int length,int value)
{
if(first < length || length > 0){
if(value == num[(first+length)/2]) return true;
else if( value < num[(first+length)/2]) {find(num,first,(first+length)/2 - 1, value);}
else {find(num,(first+length)/2+1,length, value);}
}
else{
return false;
}
}
//****
int _tmain(int argc, _TCHAR* argv[])
{
int num[size],first=0,length=size,i,value;
cout<<"Input the num : \n";
for(i=0;i<size;++i)
cin>>num[i];
cout<<"The searched number: ";
cin>>value;
if( !find(num,first,length,value) )
cout<<"No found;\n";
else
cout<<"Yes found the number\n";
return 0;
}
// 散列表的！
#include <iostream>
using namespace std;
int HashSearch1(int ht[ ], int m, int k)
{
int j=k%m;
if (ht[j]==k)
return j; //没有发生冲突，比较一次查找成功
int i=(j+1) % m;
while (i!=j)
{
if (ht[i]==k)
return i; //发生冲突，比较若干次查找成功
i=(i+1) % m; //向后探测一个位置
}
if (i==j)
throw "溢出";
else
ht[i]=k; //查找不成功时插入
}
void main()
{
int s[11]={11,0,0,47,0,0,0,7,29,8,0};
cout<<"散列表中的元素有:\n";
for(int i=0;i<11;i++)
{
cout<<s[i]<<" ";
}
cout<<"\n"<<"执行查找操作,结果为:\n"; //查找操作
cout<<HashSearch1(s,11,8)<<endl;
}
我想顺序查找不用我写了吧，你那同学学数据结构的顺序查找都不会吗？
3. 编写无序顺序表顺序查找、有序顺序表顺序查找、二分查找算法。用c语言。高分急求！
int IdxSerch(SeqList A[],IdxType index[],int b,KeyType k,int n) {
//分块查找关键字为k的记录，索引表为
index[0..b-1]
int low=0,high=b-1,mid,i;
int s=n/b; //每块记录个数
while(low<=high)
{
//在索引表中进行二分查找，找到的位置放在low中
mid=(low+high)/2;
if(index[mid].key<k) low=mid+1；
else high=mid-1;
}
if(low<b)
{
//在顺序表中顺序查找
for(i=index[low].link;i<=index[low].link+s-1 && i<n;i++)
if(A[i].key==k) return i;
return -1;
}
return -1;
}
typedef struct node
{
KeyType key;
//结点中的关键字
struct node *lchild,*rchild; //左、右孩子指针
}BsTree;
BsTree *BstSeareh(BsTree *BST,KeyType k ,BsTree **parent)
{
BsTree *p=BST,*q=NULL; //p指向根结点，q指向*p的双亲
while(p!=NULL)
{
if(k==p->key)
{ //查找成功
*parent=q;
return (p);
}
q=p;
if(k<p->key) p=p->lchild；
//在左子树中查找
else p=p->rchild; //在右子树中查找
}
*parent=q;
return (p);
//查找失败，返回空
}
4. 顺序查找算法
#include <stdio.h>
#include <stdlib.h>
#define MAX_LENGTH 100
typedef int KeyType;
typedef struct {
KeyType *elem;
int length;
}SSTable; //顺序表的存储结构
/*
此算法比第二个算法多了一个判定i是否出界的流程，对于查找数目较少的情况，
二者查找时间相差不大，对于存在大量数据时，该算法的主要查找时间消耗再判
定是否出界上，所以第二个算法明显比第一个算法好，唯一增加的就是一个“哨兵”
数据。
int Search_Seq(SSTable ST, KeyType key){
int i;
for(i=1; i<=ST.length && ST.elem[i] != key; i++ )
;
if(i<=ST.length)
return i;
else
return 0;
}
*/
int Search_Seq(SSTable ST, KeyType key){
int i;
ST.elem[0] = key; //“哨兵”，如果顺序表中不存在要查找的数据的话，则查找指针必定指向该哨兵
for(i = ST.length; ST.elem[i] != key; i--)
;
return i; //找到的话，则i != 0,否则i = 0
}
void main()
{
int i, key;
SSTable T;
T.elem = (KeyType *)malloc(sizeof(KeyType));
printf("How Many Entries Do You Want input\n");
scanf("%d", &T.length);
for(i=1; i<=T.length; i++){
printf("Please input the %dth entries \n", i);
scanf("%d", &T.elem[i]);
}
for (i=1; i<=T.length; i++)
printf("%5d",T.elem[i]); //显示已经输入的所有数据
printf("\nPlease input the data you want to search\n");
scanf("%d", &key);
i = Search_Seq(T,key);
printf("the search data is locate the %dth(0 indicate can not find)\n",i);
}
5. 数据结构与算法中如何利用顺序表实现按值查找
直接循环表,按值查找.找到就退出.
平均O(N)时间复杂度.
6. 顺序表的顺序查找和二分查找
顺序查找,二分查找和哈希查找算法,它们各自的特点是：
1.对比顺序查找的特点就是从表的第一个元素开始一个一个向下查找，如果有和目标一致的元素，查找成功;如果到最后一个元素仍没有目标元素，则查找失败。
2.二分查找的特点就是从表中间开始查找目标元素。如果找到一致元素，则查找成功。如果中间元素比目标元素小，则仍用二分查找方法查找表的后半部分(表是递增排列的)，反之中间元素比目标元素大，则查找表的前半部分。
3.哈希算法的特点是是使用给定数据构造哈希表，然后在哈希表上进行查找的一种算法。先给定一个值，然后根据哈希函数求得哈希地址，再根据哈希地址查找到要找的元素。是通过数据元素的存储地址进行查找的一种算法。