|
#2
寒风中的细雨2011-05-19 23:41
 程序代码：#include <iostream> using namespace std; #define WAY //宏定义表示升序 没有定义则表示降序排序 #undef WAY //const unsigned int SIZE = 20;//最大长度 //typedef int TYPE;//表中元素的类型 class Table { public: typedef int TYPE; Table(); void getInputMsg();//从控制台获取输入信息 void printTableMsg();//打印表中数据 bool insertMsg(TYPE e, size_t index);//把元素e插入到index位置 bool binSearch(TYPE e, size_t &index);//二分查找 找到返回true 否则false private: enum{SIZE=20}; TYPE array[SIZE]; size_t length; }; Table::Table() { length = 0; } void Table::getInputMsg() { #ifdef WAY cout << "按升序"; #else cout << "按降序"; #endif cout << "请输入一个不超过20个数据元素的有序表:" ; for (size_t i=0; i<10; ++i) { cin >> array[i]; length++; } } void Table::printTableMsg() { #ifdef WAY cout << "按升序"; #else cout << "按降序"; #endif cout << "输出数据:"; for (size_t i=0; i<length; ++i) { cout << array[i] << ' '; } cout << endl; } bool Table::insertMsg(TYPE e, size_t index) { if (index > length) { return false; } else { length++; for (size_t i=length; i!=index; --i) { array[i] = array[i-1]; } array[index] = e; return true; } } bool Table::binSearch(TYPE e, size_t &index) { size_t low=0, high=length-1; size_t mid = (low+high)/2; while (low < high) { mid = (low+high)/2; if (array[mid] == e) { index = mid; return true; } else if (array[mid] > e) { #ifdef WAY high--; #else low++; #endif } else if (array[mid] < e) { #ifdef WAY low++; #else high--; #endif } } if (low >= high) { #ifdef WAY index = low; #else if ( high == length-1 ) { high++; } index = high; #endif } return false; } void function(void) { Table table; size_t index; table.getInputMsg(); table.printTableMsg(); if (!table.binSearch(10, index)) { table.insertMsg(10, index); } table.printTableMsg(); } int main(void) { function(); return 0; } |
（一）上机题：
一、从键盘接收一个不超过20个数据元素的有序表。
1、输出该有序表。
2、从键盘接收一个关键字K，采用二分查找的方法在有序表中查找与K相等的元素。若查找成功，返回其位置；若查找失败，须将K插入有序表中(即一趟二分插入排序)。要求在屏幕上输出查找过程中，K与哪些元素进行了比较；且查找失败，须输出新的有序表。
运行不了.........................................................................
#include <stdio.h>
#define MAXL 20
#include<stdlib.h>
//#include <iostream>
#include <stack>
typedef int ElemType;
typedef struct //有序表的结构的定义
{
ElemType data[MAXL];
int length;
}SqList;
//查找的结构定义
typedef int KeyType,InfoType;
typedef struct//
{
KeyType key;
InfoType data;
}NodeType;
typedef NodeType SeqList[MAXL];
void InitList(SqList *&L) //初始化有序表
{
L=(SqList *)malloc(sizeof(SqList));
L->length=0;
}
void CreatList(SqList *&L,ElemType a[],int n) //建立有序表
{
int i;
printf("请输入一个不超过20个数据元素的有序表：\n");
for (i=0;i<10;i++)
{
scanf("%d",&a[i]);
}
L=(SqList * )malloc(sizeof(SqList));
for (i=0;i<10;i++)
L->data[i]=a[i];
L->length=10;
}
int ListLength(SqList *L)//有序表的长度
{
return(L->length);
}
void DisqList(SqList *L) // 输出有序表
{
int i;
//if(ListEmpty(L) ) return;
for (i=0;i<L->length;i++)
printf("有序表为：%c",L->data[i]);
printf("\n");
}
int ListInsert(SqList *&L,ElemType e)//有序表插入查找不匹配的数
{
int i=0,j;
while (i<L->length&& L->data[i]<e) i++;
if (L->data[i]==e) return 0;
for (j=10;j>i;j--)
L->data[j]=L->data[j-1];
L->data[i]=e;
L->length++;
return 1;
}
int BinSearch(SeqList R,int n,KeyType e) //二分查找、返回插入函数
{printf("请输入一个关键字e：\n");
scanf("%d\n",e);
int low=0,high=n-1,mid;
//SqList *&L;
while (low<=high)
{mid=(low+high)/2;
if (R[mid].key==e)
return(mid);
if(R[mid].key>e)
high=mid-1;
//return mid-1;
else
low=mid+1;
//return mid+1;
}
return 1;
//return ListInsert( L, e);
}
int main()
{SqList *&L,R;
ElemType a[MAXL];
KeyType e;
int n;
CreatList(&L,a,n);
DisqList(L);
BinSearch(R,n,e);
if(BinSearch=1)
DisqList(L);
else
{ListInsert( L, e);
DisqList(L);}
return 1;
}