实验一：线性表的顺序存储结构
课程名称： 数据结构 姓名： 学 号：
班级：
指导教师评定：
一、实验目的：
1. 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现； 2. 以线性表的各种操作（建立、插入、删除等）的实现为重点； 3. 掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；
二、实验内容：
1．输入一组整型数据，建立顺序表。 2．实现该线性表的删除。 3、实现该线性表的插入。 4．实现线性表中数据的显示。 5．实现线性表数据的查找和定位 6、编写一个主函数,调试上述算法。
三、 实验原理、方法和手段
1.根据实验内容编程，上机调试、得出正确的运行程序。 2. 编译运行程序，观察运行情况和输出结果。 3. 写出实验报告（包括源程序和运行结果）。
四、实验条件
运行Visual c++的微机一台
五、实验步骤（程序清单）： （一）、程序代码：
#include
const OVERFLOW = -2; const ERROR = -1; const OK = 1;
const LIST_INIT_SIZE = 100; const LISTINCREMENT =10;
typedef struct SqList{
ElemType *base; int int
length; ListSize;
//线性表的初始存储空间
//线性表的增量空间
}SqList;
void CreatSqList(int n,SqList &L){ }
void display1(SqList L1){
L.length = n; L.ListSize = n+15;
L.base = new ElemType[L.ListSize]; if(!L.base)
cout< cout<<\for(int k=1; k<=L.length; k++) cin>>L.base[k-1]; if(L1.length == 0){ } cout<<\您输入的线性表数据为：\\n\for(int k=0; k < L1.length; k++) cout<<\return; } cout< //定位 Status LocateSqList(SqList L,ElemType x){ } //查找 Status SearchSqlist(SqList L,int x){ } //排序 void bubbleSort1(SqList L){ cout< cout<<\表中数字定位********************\if(L.length == 0) return 0; cout<<\for(int k=0; k if(x == L.base[k]) cout<<\ return -1; //顺序查找 cout< cout<<\线性查找*********************\cout<<\for(int i=0; i < L.length; i++) if(L.base[i] == x) cout<<\ return -1; cout< } cout<<\冒泡排序*************************\cout<<\顺序表的排序结果为：\ bool flag = true; //标记某趟冒泡排序是否有过交换，初始化位true ElemType temp; //从上向下依次比较相邻气泡的重量。若发现轻者在下、重者在上，则交换//二者的位置，经过n-1趟冒泡或某趟冒泡不再有元素交换，则排序完成 for(int i=1; i<=L.length && flag; ++i){ } flag = false; //每趟开始都假设没有元素交换 for(int j=0; j if(L.base[j+1] { //若发现轻者在下、重者在上，则交换二者的位置 } flag = true; //标记已经交换 temp = L.base[j+1]; L.base[j+1] = L.base[j]; L.base[j] = temp; } //二分查找 Status bin_Search(SqList L2,int x){ if(L2.base==NULL || L2.length==0) return -1; int mid=0,low=0,high=L2.length-1,flag=0; while(low <= high){ mid = (low+high)/2; if(L2.base[mid]==x){ flag=1;break; } } } if(L2.base[mid] < x) low = mid+1; else high = mid-1; //没找到 if(flag) return mid; else return -1; //插入 Status ListInsert(SqList &L2,int i,ElemType e){ cout< cout<<\插入**************************\int *p, *q;int newsize;ElemType *newbase; cout<<\请输入您要在第几个元素位置插入元素：\cout<<\请输入您要插入的元素值：\ cout<<\您要在第\个元素位置插入元素\cout<<\插入后排序为：\ //检查插入位置是否合法：1<=i<=n+1,共有n+1个合法位置 if(i<1 || i>L2.length+1) { } //检查数组中是否有空闲的空间存放新元素，如果没有，将 //数组增加ListInCrement个节点 if(L2.length >= L2.ListSize){ newsize = L2.ListSize + LISTINCREMENT; newbase = (ElemType *)realloc(L2.base, newsize*sizeof(ElemType)); return ERROR; cout<<\元素位置超出范围，插入失败\ if(!newbase) exit(OVERFLOW);//扩展失败