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.哈希演算法的特點是是使用給定數據構造哈希表，然後在哈希表上進行查找的一種演算法。先給定一個值，然後根據哈希函數求得哈希地址，再根據哈希地址查找到要找的元素。是通過數據元素的存儲地址進行查找的一種演算法。