当前位置:编程学习 > C/C++ >>

填写顺序表(只要C++)

题目要求:

一、顺序表操作
    1、显示
    2、插入
    3、查找(显示比较次数)
    4、删除(显示移动次数)
    5、排序(普通、快速,显示比较次数、移动次数)
    6、折半查找(显示比较次数)
    7、编程实现一个顺序表的就地逆置,即利用原表的存储空间将顺序表逆置。

提高题:

    8*、要求以较高的效率实现删除顺序表中元素值在x到y(x和y自定)之间的所有元素。
[解题思路]  在顺序表中设置两个初值为0的下标变量i和j,其中,i为比较元素的下标,j为赋值元素的下标。依次取顺序表中下标为i的元素与x和y比较,假若是x到y之外的元素,则赋值给下标为j的元素。这种算法比删除一个元素后立即移动其后面的元素的效率高得多。
    9*、编程实现将两个有序的顺序表进行合并,要求同样的数据元素只出现一次。
[解题思路]  由于两个顺序表中的元素呈有序排列,在进行合并的时候,依次比较,哪个顺序表的元素值小,就先将这个元素复制到新的顺序表中,若两个元素相等,则复制一个即可,这样一直到其中的一个顺序表结束,然后将剩余的顺序表复制到新的顺序表中即可。
   10*、有序插入(显示比较次数、移动次数),
       屏幕提示后,从键盘输入一个元素值,在经过排序的线性表中插入这个元素;
       屏幕显示比较次数和移动次数,应有溢出判断和报告。
 

 

源代码填写:

/*
 源文件名:P1.cpp
 功能:静态线性表操作
*/
#include <iostream.h>
#include <iomanip.h>
#include <conio.h>
#include <stdio.h>
#include <process.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

const max=10000;

struct SqList
{
 int elem[max];         //存放元素的数组
 int length;            //当前长度
};

void init(SqList &list);
void display(SqList &list);
void insert(SqList &list);
void search(SqList &list);
void del(SqList &list);
void 易做图Sort(SqList &list);
void quickSort(SqList &list);
void binarySearch(SqList &list);

SqList list;

void main()
{
 char choice;

 while (1)
 {
  system("cls");
  cout << "\n\n\n\n";
  cout << "\t\t            静态线性表操作  \n";
  cout << "\t\t======================================";
  cout << "\n\n";
  cout << "\t\t             1:初始化      \n";
  cout << "\t\t             2:显示        \n";
  cout << "\t\t             3:单个插入    \n";
  cout << "\t\t             4:查找        \n";
  cout << "\t\t             5:删除        \n";
  cout << "\t\t             6:简单排序    \n";
  cout << "\t\t             7:快速排序    \n";
  cout << "\t\t             8:折半查找    \n";
  cout << "\n";
  cout << "\t\t             0:退出        \n";
  cout << "\n";
  cout << "\t\t请选择:" << flush;

  choice = getch();
  system("cls");
  
  switch(choice)
  {
   case '1':
    init(list);
    break;
   case '2':
    display(list);
    break;
   case '3':
    insert(list);
    break;
   case '4':
    search(list);
    break;
   case '5':
    del(list);
    break;
   case '6':
    易做图Sort(list);
    break;
   case '7':
    quickSort(list);
    break;
   case '8':
    binarySearch(list);
    break;
   case '0':
    exit(0);
  }
 }
}

 

//屏幕提示后,从键盘输入线性表长度和随机数种子,生成指定长度的线性表list
void init(SqList &list)
{
 int i;
 while (1)
 {
     cout << "输入元素个数(0-" << max << "):" << flush;
  cin >> list.length;
  if (list.length >= 0 && list.length <= max)
   break;
  cout << endl;
 }
 while (1)
 {
     cout << "输入随机数种子(0-32767):" << flush;
  cin >> i;
  if (i >= 0 && i <= 32767)
   break;
  cout << endl;
 }
 srand(i);  //指定随机数种子,相同的种子将产生相同的数据序列
 rand();

 for (i = 0; i < list.length; i++)
 {
  list.elem[i] = rand() % 10000;
 }
 for (i = list.length; i < max; i++)
  list.elem[i] = 0;
}

//在屏幕上依次显示线性表list中的元素个数和全部元素
//格式应便于观察
//如果需要指定输出的宽度,可以使用 cout << setw(W) << X ,其中 X 是输出的数值,W 是占据的列数
void display(SqList &list)
{
 
}

//屏幕提示后,从键盘输入一个元素值,然后把这个新元素插到线性表list的末尾
//应有溢出判断和报告
void insert(SqList &list)
{
}

//屏幕提示后,从键盘输入一个元素值,在线性表list中搜索这个元素
//屏幕显示搜索结果和搜索过程中的比较次数
void search(SqList &list)
{

}

//屏幕提示后,从键盘输入一个元素值,在线性表list中删除这个元素
//屏幕显示删除成功与否的信息,并显示比较次数和移动次数
void del(SqList &list)
{

}

//对线性表list进行简单排序
//屏幕显示比较次数和移动次数
void 易做图Sort(SqList &list)
{

}

//对线性表list进行快速排序
//屏幕显示比较次数和移动次数
void quickSort(SqList &list)
{

}

//屏幕提示后,从键盘输入一个元素值,对经过排序的线性表list进行折半查找
//屏幕显示查找结果,并显示比较次数
void binarySearch(SqList &list)
{

}


 

 

答案:#include <iostream.h>
#include <iomanip.h>
#include <conio.h>
#include <stdio.h>
#include <process.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
static int cnt=0,cnt1=0;
const max=10000;

struct SqList
{
 int elem[max];         //存放元素的数组
 int length;            //当前长度
};

void init(SqList &list);
void display(SqList &list);
void insert(SqList &list);
void search(SqList &list);
void del(SqList &list);
void 易做图Sort(SqList &list);
void quickSort(SqList &list,int,int);
void quicksort_cnt(void);
void binarySearch(SqList &list);  
int Partion(SqList &list,int ,int );

SqList list;

void main()
{
 char choice;

 while (1)
 {
  system("cls");
  cout << "\n\n\n\n";
  cout << "\t\t            静态线性表操作  \n";
  cout << "\t\t======================================";
  cout << "\n\n";
  cout << "\t\t             1:初始化      \n";
  cout << "\t\t             2:显示        \n";
  cout << "\t\t             3:单个插入    \n";
  cout << "\t\t             4:查找        \n";
  cout << "\t\t             5:删除        \n";
  cout << "\t\t             6:简单排序    \n";
  cout << "\t\t             7:快速排序    \n";
  cout << "\t\t             8:折半查找    \n";
  cout << "\n";
  cout << "\t\t             0:退出        \n";
  cout << "\n";
  cout << "\t\t请选择:" << flush;

  choice = getch();
  system("cls");
 
  switch(choice)
  {
   case '1':
    init(list);
    break;
   case '2':
    display(list);
    break;
   case '3':
    insert(list);
    break;
   case '4':
    search(list);
    break;
   case '5':
    del(list);
    break;
   case '6':
    易做图Sort(list);
    break;
   case '7':
    quickSort(list,0,list.length-1);
 quicksort_cnt();
    break;
   case '8':
    quickSort(list,0,list.length-1);
    binarySearch(list);
    break;
   case '0':
    exit(0);
  }
 }
}

 

//屏幕提示后,从键盘输入线性表长度和随机数种子,生成指定长度的线性表list
void init(SqList &list)
{
 int i;
 while (1)
 {
     cout << "输入元素个数(0-" << max << "):" << flush;
  cin >> list.length;
  if (list.length >= 0 && list.length <= max)
   break;
  cout << endl;
 }
 while (1)
 {
     cout << "输入随机数种子(0-32767):" << flush;
  cin >> i;
  if (i >= 0 && i <= 32767)
   break;
  cout << endl;
 }
 srand(i);  //指定随机数种子,相同的种子将产生相同的数据序列
 rand();

 for (i = 0; i < list.length; i++)
 {
  list.elem[i] = rand() % 10000;
 }
 for (i = list.length; i < max; i++)
  list.elem[i] = 0;
}

//在屏幕上依次显示线性表list中的元素个数和全部元素
//格式应便于观察
//如果需要指定输出的宽度,可以使用 cout << setw(W) << X ,其中 X 是输出的数值,W 是占据的列数
void display(SqList &list)
{
 cout<<"共有"<<list.length<<"个元素"<<"分别是:";
 for(int i=0;i<list.length;i++)
  cout<<list.elem[i]<<",";
}

//屏幕提示后,从键盘输入一个元素值,然后把这个新元素插到线性表list的末尾
//应有溢出判断和报告
void insert(SqList &list)
{
 cout<<"请输入要插入的值:"<<endl;
 int elem;
 cin>>elem;
 if(list.length>=0 && list.length<=max)
 {
  list.elem[list.length]=elem;
  list.length++;
 }
 else
  cout<<"插入失败"<<endl;
}

//屏幕提示后,从键盘输入一个元素值,在线性表list中搜索这个元素
//屏幕显示搜索结果和搜索过程中的比较次数
void search(SqList &list)
{
 binarySearch(list);
}

//屏幕提示后,从键盘输入一个元素值,在线性表list中删除这个元素
//屏幕显示删除成功与否的信息,并显示比较次数和移动次数
void del(SqList &list)   //快速查找删除
{
 quickSort(list,0,list.length-1);
 int i,j,mid,low,high,e;
 int t,cnt=0;
 low=0;
 high=list.length-1;
 cout<<"请输入需删除的元素值"<<'\n';
 cin>>e;
 mid=(low+high)/2;
    for(i=0;i<list.length;i++)
 {
  while(low<=high && list.elem[mid]!=e)
  {
   mid=(low+high)/2;
   if(list.elem[mid]>e)
   {
    high=mid-1;
    cnt++;
   }
   else if(list.elem[mid]<e)
   {
    low=mid+1;
    cnt++;
   }
  }
  if(list.elem[mid]==e)
  {
   t=list.elem[mid];
   list.elem[mid]=0;
            quickSort(list,0,list.length-1);
   cout<<"元素"<<t<<"删除成功"<<'\n';
   cout<<"共比较删除"<<cnt<<"次";
   list.length--;
   break;
  }
   if(i>=list.length-1)
     cout<<"没有此元素"<<'\n';
 }
}

//对线性表list进行简单排序
//屏幕显示比较次数和移动次数
void 易做图Sort(SqList &list)
{
 int temp;
 int cnt=0,cnt1=0;
 for(int i=0;i<list.length-1;i++)
 {
  cnt++;
  for(int j=i+1;j<list.length;j++)
  {
   cnt++;
   if(list.elem[i]>list.elem[j])
   {
    temp=list.elem[i];
    list.elem[i]=list.elem[j];
    list.elem[j]=temp;
    cnt1+=3;
   }
  }
 }
 cout<<"共比较了"<&l

上一个:C++题目 速度快 在线等
下一个:关于 C++的 若干问题

CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,