1
/*
源文件名：P1.cpp
功能：顺序表操作
*/
#include <conio.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <iostream>
#define max 10000
struct SqList
{
int data[max]; //存放元素的数组
int length; //当前长度
};
void init(SqList &list);
void display(SqList &list);
void insert(SqList &list,int,int);
void search(SqList &list,int);
void del(SqList &list,int);
void simpleSort(SqList &list);
void binarySearch(SqList &list,int);
void nzlist(SqList &list);
SqList list;
int main()
{
char choice;
int key;
while (1)
{
system("cls");
printf(" 学号: **** 姓名：*** \n ");
printf("\n\n\n\n");
printf("\t\t 顺序表操作 \n");
printf("\t\t======================================");
printf("\n\n");
printf("\t\t 1：初始化 \n");
printf("\t\t 2：显示 \n");
printf("\t\t 3：单个插入 \n");
printf("\t\t 4：查找 \n");
printf("\t\t 5：删除 \n");
printf("\t\t 6：简单选择排序 \n");
printf("\t\t 7：折半查找 \n");
printf("\t\t 8：逆置线性表 \n");
printf("\n");
printf("\t\t 0：退出 \n");
printf("\n");
printf("\t\t请选择：");
choice = getch();
system("cls");
switch(choice)
{
case '1':
void init(SqList &list);
break;
case '2':
void display(SqList &list);
break;
case '3':
int wz; //在wz出插入key
void insert(SqList &list,int,int);
break;
case '4':
printf("输入你要查找到值(数字)\n" );
scanf("%d",&key);
void search(SqList &list,int);
break;
case '5':
printf("输入你要删除的值(数字)\n" );
scanf("%d",&key);
void del(SqList &list,int);
break;
case '6':
void simpleSort(SqList &list);
break;
case '7':
printf("输入你要二分查找的值(数字)\n" );
scanf("%d",&key);
void binarySearch(SqList &list,int);
break;
case '8':
void nzlist(SqList &list);
break;
case '0':
exit(0);
}
}
return 0;
}
//屏幕提示后，从键盘输入线性表长度和随机数种子，生成指定长度的线性表list
void init(SqList &list)
{
int i;
while (1)
{
printf("输入元素个数（0 － %d ）：\n",max);
scanf("%d",&list.length);
if (list.length >= 0 && list.length <= max)
break;
printf("\n");
}
while (1)
{
printf("输入随机数种子（0－32767）：\n");
scanf("%d",&i);
if (i >= 0 && i <= 32767)
break;
printf("\n");
}
srand(i); //指定随机数种子，相同的种子将产生相同的数据序列
rand();
for (i = 0; i < list.length; i++)
{
list.data[i] = rand() % 10000;
}
for (i = list.length; i < max; i++)
list.data[i] = 0;
}
// 注意：部分算法的函数定义如下，其他需自行不全
//1.在屏幕上依次显示线性表list中的元素个数和全部元素
void display(SqList &list)
{int i;
for(i=0;i<list.length;i++)
{printf("[%5d]= %6d\n",(i+1),list.data[i]);}
puts("press 1 to continue");
while(scanf("%d",&i )!=1);
}
//2.屏幕提示后，从键盘输入需要插入的位置wz和元素值key
void insert(SqList &list,int wz,int key)
{
SqList *L;
printf("输入要插入元素的位置:\n");
scanf("%d",&wz);
printf("输入要插入的数据元素的值:\n");
scanf("%d",&key);
if(wz<1||wz>L->length+1){
printf("输入的位置不在范围内！\n");
}
wz--;
int j;
for (j=L->length;j>wz;j--)
list.data[j]=list.data[j-1];
list.data[wz]=key;
L->length++;
puts("press 1 to continue");
while(scanf("%d",&wz )!=1);
}
//3.屏幕提示后，在线性表list中搜索这个元素key，若存在该元素，则给出位置信息，
// 否则，显示“不存在此数！”
//屏幕显示搜索结果和搜索过程中的比较次数
void search(SqList &list,int key)
{
int i;
int flag=0;
for(i=0;i<list.length;i++){
if(list.data[i]==key)break;
flag++;
}
if( (i==list.length)&&(list.data[i]!=key)) printf("不存在此数！\n" );
else printf("[%5d]= %6d\n",(i+1),list.data[i]);
printf("查找次数:%d\n",flag );
puts("press 1 to continue");
while(scanf("%d",&i )!=1);
}
//4.屏幕提示后，在线性表list中删除这个元素key，并显示相关信息
//屏幕显示删除成功与否的信息，并显示比较次数和移动次数
void del(SqList &list,int key)
{
int i;
int flag=0;
for(i=0;i<list.length;i++){
if(list.data[i]==key)break;
flag++;
}
if( (i==list.length)&&(list.data[i]!=key)) printf("不存在此数！\n" );//查找
else {
printf("[%5d]= %6d\n",(i+1),list.data[i]);
for(i=0;(i+1)<list.length;i++){
list.data[i]=list.data[i+1];
}
list.length--;
printf("删除成功!\n" );
}
puts("press 1 to continue");
while(scanf("%d",&i )!=1);
}
//5.编程实现一个顺序表的就地逆置，即利用原表的存储空间将顺序表逆置。
void nzlist(SqList &list)
{
int i;
for(i=0;i<list.length/2;i++){
list.data[i] += list.data[list.length-i-1];//i是总和
list.data[list.length-i-1] = list.data[i]-list.data[list.length-i-1];//尾部变成原来的i
list.data[i] -= list.data[list.length-i-1];//头部变成原来的list.data[list.length-i-1]
}
for(i=0;i<20;i++)
printf("就地逆置完成！ ");
}
//其他函数实现，请自行补充
//6.简单选择排序
void simpleSort(SqList &list)
{
int i,j,times=0,swaps=0,t;
printf("排序如下:\n" );
for(i=0;i<list.length;i++)
{for(j=i;j<list.length;j++){
times++;
if(list.data[i]>list.data[j]){
swaps++;
t=list.data[i];
list.data[i]=list.data[j];
list.data[j]=t;
}
}}
printf("比较次数:%d\n移动次数:%d",times,swaps );
puts("press 1 to continue");
while(scanf("%d",&i )!=1);
}
//7.折半查找
void binarySearch(SqList &list,int key)
{
int times=0;
int mid,low=0,high=list.length-1;
while(low<=high){
times++;
if(list.data[low]==key){
printf("[%d]%d,查找次数为:%d",low,list.data[low],times );
break;}
if(list.data[high]==key){
printf("[%d]%d,查找次数为:%d",high,list.data[high],times );
break;
}
mid=(low+high)/2;
if(list.data[mid]==key){
printf("[%d]%d,查找次数为:%d",mid,list.data[mid],times );
break;
}
if(list.data[mid]>key)high=mid-1;
if(list.data[mid]<key)low=mid+1;
}
if(low>high)printf("没有找到,查找次数为:%d\n",times );
int i;
puts("press 1 to continue");
while(scanf("%d",&i )!=1);
}
