数据结构实验报告(C语言)顺序表查找

数据结构实验报告C语言顺序表查找

计算机科学与技术系

实 验 报 告

专业名称 计算机科学与技术 课程名称 数据结构与算法 项目名称 顺序表查找

班 级

学 号

姓 名

实验日期

格 式 要 求

实验报告注意格式规范，要求在word中编写，文中不要有空行，统一使用A4页面。

页边距：上2.5cm、下2cm、左2.5cm、右2cm。

标题：宋体、四号字、加粗、1.5倍行距。

正文：宋体、小四号字、1.2倍行距。

一、实验目的与要求：

（一）实验目的

1、掌握线性表中元素的前驱、后续的概念。

2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。

3、掌握线性表三种查找的算法。

4、对线性表相应算法的时间复杂度进行分析。

5、理解顺序表数据结构的特点（优缺点）。

（二）实验要求

1．将实验中所要求的每个功能用一个函数实现。

2．每个输入前要有输入提示，每个输出数据都要求有内容说明（如：280和100的和是：380。）。

3．函数名称和变量名称等用英文或英文简写（每个单词第一个字母大写）形式说明。

二、实验方法：（代码）

include "stdafx.h"

#include<stdio.h>

#include<malloc.h>

#define ERROR 0

#define OK 1

#define INIT_SIZE 5 /*初始分配的顺序表长度*/

#define INCREM 5 /*溢出时，顺序表长度的增量*/

typedef int ElemType; /*定义表元素的类型*/

typedef struct Sqlist{

ElemType *slist; /*存储空间的基地址*/ int length; /*顺序表的当前长度*/ int listsize; /*当前分配的存储空间*/

}Sqlist;

int InitList_sq(Sqlist *L);

int CreateList_sq(Sqlist *L,int n);

int ListInsert_sq(Sqlist *L,int i,ElemType e);

int PrintList_sq(Sqlist *L);

int ListDelete_sq(Sqlist *L,int i);

void ListLocate(Sqlist *L,ElemType e);

//初始化顺序表

int InitList_sq(Sqlist *L){

L->slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType)); if(!L->slist) return ERROR;

L->length=0;

L->listsize=INIT_SIZE;

return OK;

}/*InitList*/

//创建顺序表

int CreateList_sq(Sqlist *L,int n){

ElemType e;

int i;

for(i=0;i<n;i++){

printf("input data %d",i+1);

printf(": ");

scanf("%d",&e);

if(!ListInsert_sq(L,i+1,e))

return ERROR;

}

return OK;

}/*CreateList*/

/*输出顺序表中的元素*/

int PrintList_sq(Sqlist *L){

int i;

for(i=1;i<=L->length;i++)

printf("%5d",L->slist[i-1]);

return OK;

}/*PrintList*/

//在顺序表中插入

int ListInsert_sq(Sqlist *L,int i,ElemType e)

{

int k;

if(i<1||i>L->length+1) return ERROR; else {

for(k=L->length-1;k>=i-1;k--) L->slist[k+1]=L->slist[k];

L->slist[i-1]=e; L->length++; return(OK); }

//L->slist[i-1]=e; //L->length++; return OK;

}/*ListInsert*/

/*在顺序表中删除第i个元素*/

int ListDelete_sq(Sqlist *L,int i)

{ int j;

if (L->listsize<0)

{ printf ( "error"); return (0);} else if ( (i<1)||(i >L->length ) )

{ printf ("error"); return (0); } else {

for( j=i; j<=L->length+1; j++) L->slist[ j-1] =L->slist[ j]; L->length-- ;

return (1);

}

}

/*在顺序表中查找指定值元素，返回其序号*/ void ListLocate(Sqlist *L,ElemType e){

int i,z=0;

for(i=0;i<L->length;i++)

if (L->slist[i]==e)

{printf("该数值所在表中序号为：第%d位",i+1); z=1;}

if(z==0)

printf("表中没有该值\n");

}

//主函数

int main(){

Sqlist sl;

int n,i,e;

printf("******** 欢迎来到该界面 ******** \n");

printf("please input n:"); /*输入顺序表的元素个数*/

scanf("%d",&n);

if(n>0)

{ printf("\n1-Create Sqlist:\n");

InitList_sq(&sl);

CreateList_sq(&sl,n);

printf("输入要插入的值得序号和值:"); //顺序表的插入输出

scanf("%d %d",&i,&e); //输入要插入值元素的序号和要插入的值 ListInsert_sq(&sl,i,e);

printf("输出插入后的顺序表："); PrintList_sq(&sl); printf("\n"); //顺序表的删除输出 printf("输入要删除的值元素的序号：");

scanf("%d",&i ); //输入要删除的值元素的序号

ListDelete_sq(&sl,i);

printf("输出删除后的顺序表：\n");

PrintList_sq(&sl); printf("\n"); //顺序表的查找输出

printf("输入要顺序查找的值：");

scanf("%d",&e );

ListLocate(&sl, e); getchar(); }else

printf("ERROR");

return 0;

}

三、实验分析与小结

数据结构实验报告C语言顺序表查找

得分（百分制）

 

第二篇：数据结构实验报告 顺序表

江西理工大学软件学院

计算机类课程实验报告

课程名称：     数据结构       

班    级：                      

姓    名：                      

学    号：                      

江西理工大学软件学院

实验二：顺序表            

   20##年11月10日

一.   实验目的

掌握顺序表的逻辑结构、存储结构、以及操作。

二.   问题描述

线性表是由n(n≥0)个元素（结点）a1, a2, …, an组成的有限序列，其中ai中的i称为该数据元素的位置（序号），n为数据元素的个数（表的长度），当n等于0时称为空表。

按逻辑次序依次把数据元素存放在一组连续的地址存储单元里的线性表称为顺序表。在这里，我们通过C++中的动态数组来实现顺序表的存放，并通过建立顺序表类实现它的各种操作。

三.   实验要求

实现顺序表的三个框架操作：随机生成，用已有顺序表初始化另一个顺序表，输入顺序表。

以及十个基本操作：在第i个元素之前插入元素，判断是否为空，求元素个数，取第i个元素，查找第一个与e满足compare()关系的元素，返回元素的前驱，返回后继，删除第i个元素，把一个顺序表赋值给另一个顺序表，置空顺序表。

四.   实验环境

3323机房

OS：Wxp

C环境：1、TC2.0

        2、VC++ 6.0

五．运行结果

      程序开始界面

框架操作：

1.  随机生成顺序表（元素值为0到99之间的整数）

2. 用已有的顺序表初始化另一个顺序表

3. 输入顺序表

基本操作：

1.  在第i个元素之前插入一个元素

2. 判断顺序表是否为空

3. 求顺序表中元素的个数

4. 取第i个元素

5. 查找第一个与之满足compare()关系的元素序号

6. 返回某元素的前驱

7. 返回某元素的后继

8. 删除第i个元素

9. 把一个顺序表复制给另一个顺序表

10. 把顺序表置空

11.顺序表的运用

六． 实验心得

      熟悉最基本的数据类型——顺序表，同时我们让我们熟练C++的基本操作，模板的使用，以及模块化的设计思想。同时也运用顺序表做一些简单的运用，比如顺序表的并交差运算，学生管理系统等等。

       在这次的实验中，我掌握了很多C++的特性，在运用顺序表时，由于水平的原因，只是把简单的并交差运算写完，我想通过以后的学习，我们能够将其实现学生管理系统。

       在实验中我也遇到很多的问题，输入输出的重载，输出格式的控制等等，在以后的实验中吸取经验和教训，提高自己的水平。

五． 实验代码

       基类：SqList.h

//myhead.h包含自己设定的一些常量和类型

#ifndef MYHEAD_H

#define MYHEAD_H

//#include"D:\数据结构C++\实验2\myhead.h"

#include"D:\Users\fclz\Documents\Visual Studio 2010\Projects\数据结构C++\实验2\myhead.h"

#endif

//顺序表的一些常量说明

#define LIST_MAX_SIZE 100

#define LISTINCERMENT 10

//随机数生成必须

  #define _CRT_RAND_S

  #include <stdlib.h>

  #include <stdio.h>

  #include <limits.h>

//顺序表数据结构的C++类的声明（基类）

template <typename ElemType>

class SqList

{

protected:

   ElemType *elem;

   int listSize;

   int n;

public:

   //构造函数，析构函数，拷贝构造函数的声明

   SqList();

   virtual ~SqList();

   SqList(const SqList<ElemType>& otherL);

   //顺序表的方法

   //有序顺序表的折半查找

   int bin_Search(ElemType key);

   //把顺序表置空

   void clear();

   //删除第i个元素

   Status deleteElem(int i,ElemType& e);

   //取第i个元素

   int getElem(int i,ElemType& e);

   //求顺序表中元素的个数

   int getLength();

   //求顺序表存储空间的大小

   int getListSize();

   //在第i个元素之前插入一个元素

   Status insert(int i,ElemType e);

   //判断顺序表是否为空

   bool isEmpty();

   //查找第1个与e满足compare关系的元素的序号

   int locateElem(ElemType e,Status(*compare)(ElemType,ElemType));

   //返回某个元素的后继

   Status nextElem(ElemType e,ElemType& next_e);

   //重载复制运算符

   SqList<ElemType> operator =(SqList<ElemType> rightL);

   //返回某个元素的前驱

   Status priorElem(ElemType e,ElemType& prior_e);

   //在顺序表中顺序查找某个元素、

   int sequentialSearch(ElemType e);

};

//顺序表的方法

//有序顺序表的折半查找

template <typename ElemType>

int SqList<ElemType>::bin_Search(ElemType key)

{

   int low,mid,high;//查找区域的起始、中间以及最后一个元素的下标

   low=0,high= n-1;

   while(low<=high)

   {

      mid=(low+high)/2;

      if(elem[mid]==key)

        return mid+1;

      else if(elem[mid]<key)

        low=mid+1;

      else high=mid-1;

   }

   return 0;

}

//把顺序表置空

template <typename ElemType>

void SqList<ElemType>::clear()

{

   n=0;

}

//删除第i个元素

template <typename ElemType>

Status SqList<ElemType>::deleteElem(int i,ElemType& e)

{

   if(i<1||i>n) return ERROR;

   e=elem[i-1];

   for(int j=i+1;j<=n;++j)

      elem[j-2]=elem[j-1];

   --n;

   return OK;

}

//取第i个元素

template <typename ElemType>

Status SqList<ElemType>::getElem(int i,ElemType& e)

{

   if(i<1||i>n) return ERROR;

   e=elem[i-1];

   return OK;

}

//求顺序表中元素的个数

template <typename ElemType>

int SqList<ElemType>::getLength()

{

   return n;

}

//取顺序表存储空间的大小

template <typename ElemType>

int SqList<ElemType>::getListSize()

{

   return listSize;

}

//在第i元素之前插入一个元素

template <typename ElemType>

Status SqList<ElemType>::insert(int i,ElemType e)

{

   ElemType *newbase;

   if(i<1||i>n+1)

      return ERROR;

   if(n>=listSize)

   {

      newbase =new ElemType[listSize+LISTINCERMENT];

      assert(newbase!=0);

      for(int j=1;j<n;++j)

        newbase[j-1]=elem[j-1];

      delete[] elem;

      elem = newbase;

      listSize+=LISTINCERMENT;

   }

   for(int j=n;j>=i;--j)

      elem[j]=elem[j-1];

   elem[i-1]=e;

   ++n;

   return OK;

}

//判断顺序表是否为空

template <typename ElemType>

bool SqList<ElemType>::isEmpty()

{

   return n?false:true;

}

//查找第1个与某元素e满足compare()关系元素

template <typename ElemType>

int SqList<ElemType>::locateElem(ElemType e,Status (*compare)(ElemType,ElemType))

{

   int i;

   for(i=1;i<=n&&!(*compare)(elem[i-1],e);++i);

   if(i<=n)

      return i;

   else

      return 0;

}

//返回某个元素的后继

template <typename ElemType>

Status SqList<ElemType>::nextElem(ElemType e,ElemType& next_e)

{

   int i=locateElem(e,equal);

   if(i<1||i==n)

      return ERROR;

   else

      getElem(i+1,next_e);

   return OK;

}

//重载运算符的定义

template <typename ElemType>

SqList<ElemType> SqList<ElemType>::operator=(SqList<ElemType>rightL)

{

   if(this!=&rightL)

   {

      if(listSize<rightL.listSize)

      {

        delete[] elem;

        elem=new ElemType[rightL.listSize];

        assert(elem!=0);

        listSize=rightL.listSize;

      }

      n=rightL.n;

      for(int i=1;i<=n;++i)

        elem[i-1]=rightL.elem[i-1];

   }

   return *this;

}

//返回某个元素的前驱

template <typename ElemType>

Status SqList<ElemType>::priorElem(ElemType e,ElemType& prior_e)

{

   int i=locateElem(e,equal);

   if(i<=1)

      return ERROR;

   else

      getElem(i-1,prior_e);

   return OK;

}

//在顺序表中顺序查找某个元素

template <typename ElemType>

int SqList<ElemType>::sequentialSearch(ElemType key)

{

   for(int i=1;i<n&& key!=elem[i-1];i++);

   if(i<=n)

      return i;

   else

      return 0;

}

//构造函数的实现

template <typename ElemType>

SqList<ElemType>::SqList()

{

   elem =new ElemType[LIST_MAX_SIZE];

   assert(elem!=0);

   listSize=LIST_MAX_SIZE;

   n=0;

}

//析构函数的实现

template <typename ElemType>

SqList<ElemType>::~SqList()

{

   delete[] elem;

}

//拷贝构造函数的实现

template <typename ElemType>

SqList<ElemType>::SqList(const SqList<ElemType>& otherL)

{

   elem=new ElemType[otherL.listSize];

   assert(elem!=0);

   listSize=otherL.listSize;

   n=otherL.n;

   for(int i=1;i<=n;i++)

      elem[i-1]=otherL.elem[i-1];

}

派生类MySqList.h

#ifndef SQLIST_H

#define SQLIST_H

#include"SqList.h"

#endif

#include <iosfwd>

template <typename ElemType>

class MySqList:public SqList<ElemType>

{

public:

   //读输入数据

   void read(istream& in);

   //显示数据

   void display(ostream& out)const;

   //生成随机顺序表

   Status randSql(int n,MySqList<ElemType>& otherS);

};

//派生类的实现

//输入

template <typename ElemType>

void MySqList<ElemType>::read(istream& in)

{

   cout<<"请输入要建立的顺序表的元素个数：";

   cin>>n;

   for(int i=0;i<n;i++)

   {

       //cout<<n<<endl;

      cout<<"请输入顺序表的第"<<i+1<<"个元素：";

      in>>elem[i];

      //n++;

   }

   cout<<endl;

}

template <typename ElemType>

istream& operator >>(istream& in,MySqList<ElemType>& iL)

{

   iL.read(in);

   return in;

}

//输出

template <typename ElemType>

void MySqList<ElemType>::display(ostream& out) const

{

   for(int i=0;i<n;i++)

      out<<"["<<i+1<<"]"<<"\t";

   out<<endl;

   for(int i=0;i<n;i++)

      out<<elem[i]<<"\t";

   out<<endl<<endl;

}

template <typename ElemType>

ostream& /*MySqList<ElemType>::*/operator <<(ostream& out,const MySqList<ElemType>& oL)

{

   oL.display(out);

   return out;

}

//生成随机数顺序表

template <typename ElemType>

Status MySqList<ElemType>::randSql(int n,MySqList<ElemType>& otherS)

{

   errno_t  err;

   unsigned int number;

   int max=100;

   if(n<1||n>otherS.listSize) return ERROR;

   else

   {

      for(int i=0;i<n;i++)

      {

        err = rand_s(&number);

        if (err != 0)

        {

           printf_s("The rand_s function failed!\n");

        }

        otherS.elem[i]=(unsigned int)((double)number /((double) UINT_MAX + 1 ) * 100.0) + 1;            

      }

      otherS.n=n;

   }

   return OK;

}

相关推荐

专栏推荐