有序表
#include"SL_List.h"
int main()
{
int k;
double a[5] = { 1.5, 5.5, 2.5, 4.5, 3.5 };
double b[7] = { 1.0, 7.5, 2.5, 4.5, 5.0, 4.5, 6.5 };
SL_List
s1.insert_SL_List(a[k]);
for (k = 0; k < 7; k++) //依次插入有序表s2的元素
s2.insert_SL_List(b[k]);
cout << "输出有序表对象s1:" << endl;
s1.prt_SL_List(); //输出有序表对象s1
cout << "输出有序表对象s2:" << endl;
s2.prt_SL_List(); //输出有序表对象s2
SL_List
s3 = s1 + s2; //有序表合并
cout << "输出合并后的有序表对象s3:" << endl;
s3.prt_SL_List(); //输出合并后的有序表对象s3
s3.delete_SL_List(a[0]); //在有序表s3中删除1.5
s3.delete_SL_List(b[0]); //在有序表s3中删除1.0
s3.delete_SL_List(123.0); //在有序表s3中删除123.0
cout << "输出删除后的有序表对象s3:" << endl;
s3.prt_SL_List(); //输出合并后的有序表对象s3
return 0;
}
//SL_List.h
#include
using namespace std;
template
class SL_List//顺序有续表类
{private: //数据成员
int mm; //存储空间容量
int nn; //有序表长度
T *v; //有序表存储空间首地址
public: //成员函数
SL_List(){ mm = 0; nn = 0; return; } //只定义对象名
SL_List(int); //顺序有序表初始化（指定存储空间容量）
int search_SL_List(T); //顺序有序表查找
int insert_SL_List(T); //顺序有序表插入
int delete_SL_List(T); //顺序有序表删除
void prt_SL_List(); //顺序输出有序表中的元素与有序表长度
friend SL_List operator+(SL_List &, SL_List &);//有序表合并};
//顺序有序表初始化
template
SL_List
{
mm = m; //存储空间容量
v = new T{mm};//动态申请存储空间
nn = 0; //有序表长度
return;
}
//顺序有序表查找
template
int SL_List
{
int i, j, k;
i = 1; j = nn;
while (i <= j)
{
k = (i + j) / 2; //中间元素下标
if (v[k - 1] == x) return(k - 1); //找到返回
if (v[k - 1] > x) j = k - 1; //取前半部
else i = k + 1; //取后半部
}
return(-1); //找不到返回
}
//顺序有序表的插入
template
int SL_Lidt
{
int k;
if (nn == mm) //存储空间已满
{
cout << "上溢" << endl; return(-1);
}
k = nn - 1;
while (v[k]>x) //从最后一个元素到被删元素之间的元素均后移{ v[k + 1] = v[k]; k = k - 1; }
v[k + 1] = x; //进行插入
nn = nn + 1; //长度增一
return(1); //成功插入返回
}
//顺序有序表的删除
template
int SL_List
{
int i, k;
k = search_SL_List(x); //查找删除元素的位置
if (k >= 0) //表中有这个元素
{
for (i = k; i < nn - 1; i++)
v[i] = v[i + 1]; //被删元素到最后一个元素之间的元素均前移nn = nn - 1; //长度减一
}
else//表中没有这个元素
cout << "没有这个元素" << endl;
return(k); //返回删除是否成功标志
}
//顺序输出有序表中的元素与顺序表的长度
template
void SL_List
{
int i;
cout << "nn=" << nn << endl; //输出长度
for (i = 0; i < nn; i++) //依次输出元素
cout << v[i] << endl;
return;
}
//有序表合并（运算符+重载为友元函数）
template
SL_List
{
int k = 0, i = 0, j = 0;
SL_List
s.v = new T[s1.nn + s2.nn]; //动态申请存储空间
while ((i < s1.nn) && (j < s2.nn))
{
if (s1.v[i] <= s2.v[j]) //复制有序表s1的元素
{
s.v[k] = s1.v[i]; i = i + 1;
}
else//复制有序表s2的元素
{
s.v[k] = s2.v[j]; j = j + 1
}
k = k + 1;
}
if (i == s1.nn) //复制有序表s2中剩余的元素for (i = j; i < s2.nn; i++)
{
s.v[k] = s2.v[i]; k = k + 1;
}
else//复制有序表s1中剩余的元素
for（j = i; j < s1.nn;j++ ）
{ s.v[k] = s1.v[j]; k = k + 1; } s.mm = s1.mm + s2.mm;
s.nn = s1.nn + s2.nn;
return(s);
}
数据结构实验 顺序表
信息学院 数据结构实验报告 学号：姓名：班级： 课程名称：数据结构实验名称：编写一个程序，实现对顺序表的如下操作： 1）初始化 2）创建一个顺序表（表长度至少为10）3）输出所创建的顺序表 4）键盘输入插入位置和插入元素，完成对表中插入元素的运算 5）键盘输入删除位置，实现对删除算法的调用，并输出被删除元素的值 6）创建两张有序表，实现这两张有序表的合并，并输出合并后的有序表。 实验性质：√①综合性实验②设计性实验③验证性实验实验时间：试验地点：机房 本实验所用设备：pc及C++6.0
【数据结构】： #define Maxsize 100 typedef int ElemType; typedef struct {ElemType elem[Maxsize]; int last; }SqeList;//建立顺序表; 【算法思想】： 通过基本算法熟悉数据结构。 创建表，运用增删改查实现表的操作后， 合并两表。 【算法描述】： void InitList(SqeList *L){printf("表已初始化!\n");L->last=-1;} void CreateForm(SqeList *L1){ InitList(L1); int i,n; printf("请输入要建表中的数组元素的个数，且不超过100：\n"); scanf("%d",&n); printf("你将输入的元素：\n"); for(i=0;i
二叉排序树 折半查找 顺序查找 数据结构
二叉排序树 #include "c1.h" #include "stdio.h" #include "stdlib.h" typedef int KeyType; typedef struct node{ KeyType key; struct node *lchild,*rchild; }BiTNode,*BiTree; void InsertBST(BiTree &bst,KeyType key) { BiTNode *t; if(bst==NULL) { t=(BiTree)malloc(sizeof(BiTNode)); t->key=key; t->lchild=NULL; t->rchild=NULL; bst=t; } else if(key
} BiTree SearchBST(BiTree bst,KeyType key) { if(!bst) return NULL; else if(bst->key==key) return bst; else if(key
C语言 顺序查找和折半查找
C语言顺序查找、折半查找#include
voidcreat_LIST(linkqueue *LIST) { char x; linkqueue *p,*s; s=LIST; while((x=getchar())!='#') { p=(linkqueue *)malloc(sizeof(linkqueue)); p->data=x; p->next=NULL; s->next=p; s=p; } printf("您创建的列表是："); print_LIST(LIST); } voidshunxu(linkqueue *LIST) { int i=0,k=1; printf("输入您要查找的元素:"); getchar(); temp=getchar(); linkqueue *p; p=LIST->next; for(;p!=NULL;p=p->next) { i++; if(p->data==temp) {printf("####顺序查找####\n您要查找的元素在第%d位,比较了%d次\n",i,i); k=0;break;} } if(k) printf("####顺序查找####\n您要查找的元素不存在。\n"); } voidzheban(linkqueue *LIST) { intlen=len_LIST(LIST); linkqueue *s; s=LIST->next; int a[100]; for(int i=0;i 有序顺序表的二分查找的递归算法。 #include int data; l.elem=(ElemType *)malloc(l.length*sizeof( ElemType)); if(!l.elem)exit(overflow); cout<<"请输入顺序表的长度: "; cin>>len; l.length=len; cout<<"请输入顺序表的数据:"< 实验1、2：线性表的应用参考代码 一、实验预备知识 1．复习C中编写函数的相关内容。 2．复习如何用主函数将多个函数连在一起构成一个C完整程序。 二、实验目的 1．掌握线性表的顺序和链式存储结构 2．熟练运用线性表在顺序存储方式下的初始化、创建、输出、插入和删除运算 3．熟练运用线性表在链式存储方式下的创建、输出、插入和删除运算 三、实验要求 1．编写初始化并创建线性表和输出线性表的算法。 2．编写对线性表插入和删除运算算法，要判断位置的合法性和溢出问题。 3．编写有序表的插入和删除运算算法。 4．编写一个主函数，将上面函数连在一起，构成一个完整的程序。 5．将实验源程序调试并运行，写出输入、输出结果，并对结果进行分析。 四、实验内容 顺序表实验内容： 1．给定的线性表为L=（12，25，7，42，19，38），元素由键盘输入。 2．初始化并建立顺序表。（开辟的存储空间大小为8） 3．编写顺序表输出算法。 4．依次插入3、21、15、99四个数，分别插入在第1、8、4和12位置，每插入一次都要输出一次顺序表。 5．删除第1，第9和第12个位置上的元素，每删除一个元素都要输出一次顺序表。 6．编写一个排序算法，对线性表中元素从小到大排列。 7．向有序表分别插入20和50，插入后表仍然有序。（修改开辟的存储空间大小为15） 单链表实验内容： 1．给定的线性表为L=（12，25，7，42，19，38），元素由键盘输入。 2．建立一个带表头结点的单链表（前插入法和尾插入法均可）。 3．编写单链表输出算法。 4．依次插入3、21、15、99四个数，分别插入在第1、8、4和12位置，每插入一次都要输出一次单链表。 5．删除第1，第9和第12个位置上的元素，每删除一个元素都要输出一次单链表。 6．编写一个排序算法，对链表中元素从小到大排列。 7．向有序链表分别插入20和50，插入后表仍然有序。 五、实验结果 顺序表源程序： #include 顺序表的按值插入 #include temp=a[i]; } else { cout<<"原顺序表元素无序"< return t+1; } void SeqList::Print() { for(int i=0;i 实验有序表合并姓名：窦晓磊班级：软件工程142 学号：1413032042 试验时间：2015.10.11 1.问题描述 把两个有序表归并为一个有序表。 2.数据结构设计 链表结点的结构为： Typedef struct Node{ T data; Node *next; }; 3.算法设计 （1）表的输入和输出。 设计一个输入输出函数Node *CreateList()。 Step1:设计指针。 Node *q, //工作指针，存储head *Head, //头指针 *p; //工作指针，存储数据 int size, //用于存储有序表元素的个数 n; //元素的输入 Step2:利用指针进行输入。 q=Head=new Node; //建立头结点 利用循环输入 for(int i=1;i<=n;i++) { p=new Node; //建立结点 cin>>n; //输入元素 p->data=n; //将输入的元素赋值给链表 Head->next=p; //尾指针后移 Head=p; //指向下一个结点 Head=p; } Head->next=NULL; //设置尾指针 Head=q; Step3:输出。 for(p=Head->next;p!=NULL;p=p->next) cout< 南昌大学实验报告 学生姓名：李木子学号：专业班级：软工实验类型：□验证□综合□设计□创新实验日期：实验成绩： 一、实验项目名称 两个有序顺序表的结合 二、实验目的 顺序表的创建 .实现顺序表的追加 .实现顺序表的显示 .两顺序表的合并 三、实验基本原理 四、主要仪器设备及耗材 电脑， 五、实验步骤 ******************************************* * 顺序表的创建 * * .实现顺序表的追加 * * .实现顺序表的显示 * * .两顺序表的合并 * ******************************************* <> <> ; ************************************ * 顺序表结构体的定义 * ************************************ { []; ; }; ************************************ * 函数声明 * ************************************ (*); (*); (); (); (*); (*); (***); ************************************ * 顺序表的初始化函数 * ************************************ (*) { >; } ************************************ * 顺序表的追加函数 * ************************************ (*) { (>) { ("\顺序表是满的!"); (); } >[>]; >>; } 算法设计与分析各种查找算法的性能测试 目录 摘要 (3) 第一章：简介（Introduction） (4) 1.1 算法背景 (4) 第二章：算法定义（Algorithm Specification） (4) 2.1 数据结构 (4) 2.2顺序查找法的伪代码 (5) 2.3 二分查找（递归）法的伪代码 (5) 2.4 二分查找（非递归）法的伪代码 (6) 第三章：测试结果（Testing Results） (8) 3.1 测试案例表 (8) 3.2 散点图 (9) 第四章：分析和讨论 (11) 4.1 顺序查找 (11) 4.1.1 基本原理 (11) 4.2.2 时间复杂度分析 (11) 4.2.3优缺点 (11) 4.2.4该进的方法 (12) 4.2 二分查找（递归与非递归） (12) 4.2.1 基本原理 (12) 4.2.2 时间复杂度分析 (13) 4.2.3优缺点 (13) 4.2.4 改进的方法 (13) 附录：源代码（基于C语言的） (15) 声明 ................................................................................................................ 错误！未定义书签。 摘要 在计算机许多应用领域中，查找操作都是十分重要的研究技术。查找效率的好坏直接影响应用软件的性能，而查找算法又分静态查找和动态查找。 我们设置待查找表的元素为整数，用不同的测试数据做测试比较，长度取固定的三种，对象由随机数生成，无需人工干预来选择或者输入数据。比较的指标为关键字的查找次数。经过比较可以看到，当规模不断增加时，各种算法之间的差别是很大的。这三种查找方法中，顺序查找是一次从序列开始从头到尾逐个检查，是最简单的查找方法，但比较次数最多，虽说二分查找的效率比顺序查找高，但二分查找只适用于有序表，且限于顺序存储结构。 关键字：顺序查找、二分查找（递归与非递归） 实验五查找的应用 一、实验目的： 1、掌握各种查找方法及适用场合，并能在解决实际问题时灵活应用。 2、增强上机编程调试能力。 二、问题描述 1.分别利用顺序查找和折半查找方法完成查找。 有序表（3,4,5,7,24,30,42,54,63,72,87,95） 输入示例： 请输入查找元素：52 输出示例： 顺序查找： 第一次比较元素95 第二次比较元素87 …….. 查找成功，i=**/查找失败 折半查找： 第一次比较元素30 第二次比较元素63 ….. 2.利用序列（12,7,17,11,16,2,13,9,21,4）建立二叉排序树，并完成指定元素的查 询。 输入输出示例同题1的要求。 三、数据结构设计（选用的数据逻辑结构和存储结构实现形式说明） （1）逻辑结构设计 顺序查找和折半查找采用线性表的结构，二叉排序树的查找则是建立一棵二叉树，采用的非线性逻辑结构。 （2）存储结构设计 采用顺序存储的结构，开辟一块空间用于存放元素。 （3）存储结构形式说明 分别建立查找关键字，顺序表数据和二叉树数据的结构体进行存储数据 四、算法设计 （1）算法列表（说明各个函数的名称，作用，完成什么操作） 序号 名称 函数表示符 操作说明 1 顺序查找 Search_Seq 在顺序表中顺序查找关键字的数据元素 2 折半查找 Search_Bin 在顺序表中折半查找关键字的数据元素 3 初始化 Init 对顺序表进行初始化，并输入元素 4 树初始化 CreateBST 创建一棵二叉排序树 5 插入 InsertBST 将输入元素插入到二叉排序树中 6 查找 SearchBST 在根指针所指二叉排序树中递归查找关键字 数据元素 （2）各函数间调用关系（画出函数之间调用关系） typedef struct { ElemType *R; int length; }SSTable; typedef struct BSTNode{ Elem data; //结点数据域 BSTNode *lchild,*rchild; //左右孩子指针 }BSTNode,*BSTree; typedef struct Elem{ int key; }Elem; typedef struct { int key;//关键字域 }ElemType; 实验题目：有序顺序表的合并 一、实验目的 掌握顺序表的基本操作 理解并分析算法的时间复杂度 二、实验内容 实现两个有序（从小到大）顺序表合并成为一个有序顺序表，合并后的结果放在第一个顺序表中（假设这两个有序顺序表中没有相同的元素）。 三、设计与编码 1、基本思想 大体上的方法与“有序顺序表的插入”方法类似。创建两个数组，实现两个有序顺序表。需定义第二个表长length2，逐个将第二个顺序表中的数据与第一个数据表中的数据对比大小，并按大小顺序排列、合并，生成第三个表。最后输出。 2、编码 #include return length; } void SeqList::Insert(int b[],int length2) { int j,h,i=0; for( j=0;j 数据结构实验报告-顺序表的创建、遍历及有序合并操作二、实验内容与步骤 实现顺序表的创建、遍历及有序合并操作，基本数据结构定义如下： typedef int ElemType; #define MAXSIZE 100 #define FALSE 0 #define TRUE 1 typedef struct {ElemType data[MAXSIZE]; int length; }seqlist; 创建顺序表，遍历顺序表 #include #define TRUE 1 typedef int ElemType; //用户自定义数据元素类型 // 顺序表结构体的定义 typedef struct { ElemType *elem; //顺序表的基地址 int length; //顺序表的当前长度 int listsize; //预设空间容量 }SqList; //线性表的顺序存储结构 SqList* InitList() //创建空的顺序表 { SqList* L = (SqList*)malloc(sizeof(SqList));//定义顺序表L if(!L) { printf("空间划分失败，程序退出\n"); return NULL; } L->elem=(ElemType *)malloc(MAXSIZE*sizeof(ElemType)); if(!L->elem) { printf("空间划分失败，程序退出\n"); 一、实验目的 1、掌握顺序查找和二分查找方法的基本思想及其实现技术 2、了解顺序查找和二分查找方法的优缺点和适用范围 二、实验内容（任务、要求或步骤等） 【问题描述】实现在有n个元素的顺序表上的顺序查找和二分查找。 【基本要求】 （1）编写一个创建函数，建立并输出一个有n个元素的顺序表，数据元素为整型。顺序表长度和顺序表的各数据元素由键盘输入。 （2）编写函数实现在有n个元素的顺序表上的顺序查找。 （3）编写函数实现在有n个元素的递增有序的顺序表上的二分查找。 （4）提供菜单，供用户选择要执行的操作，根据用户选择调用相应函数实现顺序查找和二分查找 三：源程序 二分查找如下 #include s.elem[0] = key; // “哨兵” for (i=s.length; s.elem[i]!=key; --i); return i; // 找不到时，i为0 } void main () {ssTable s; int x, pos; CreatssTable(s); cout<<"请输入要查找的值"; cin>>x; pos=SeqSearch(s,x); if(pos>0)cout< 1.问题描述 设计一个两个顺序表合的程序。根据用户输入的两个顺序表将其合并后并输出；例如：输入：1 2 3和2 3 5合并后得到：1 2 2 3 3 5；输入：1 3 6 9和2 4 7 8得到1 2 3 4 6 7 8 9 2.设计要求 输入的顺序表非递减，输出的顺序表也要非递减 3.数据结构 本课程设计采用顺序表作为实现该问题的数据结构。结构体中含有数组指针和数组长度具体定义如下： typedef struct{ DataType *elem; int length;//顺序表长度 }Seqlist; 4.分析与实现 程序执行包括：构造顺序表，实现顺序表相加； （1）包含必要的头文件 #include 实验目的及要求： 了解和掌握链表的特点； 掌握链表基本操作的实现； 掌握两个有序链表合并的算法 要求完成链表的初始化、插入、有序表合并、显示操作的实现。实验设备环境及要求： PC机一台，内存要求128M以上，VC++6.0集成开发环境。 实验内容与步骤： 1、在VC++6.0环境中新建一个工程和C++文件； 2、实现链表初始化、插入、有序合并算法，代码如下： #include LinkList p=L->next; if(!p) printf("此链表为空！"); while(p){ printf("%d",p->data); p=p->next; } printf("\n"); } void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){ LinkList pa=La->next; LinkList pb=Lb->next; LinkList pc=Lc=La; while(pa&&pb){ if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next; } else{ pc->next=pb;pc=pb;pb=pb->next; } } pc->next=pa?pa:pb; free(Lb); } void main(){ LinkList La,Lb,Lc; InitList_L(La); InitList_L(Lb); InitList_L(Lc); ListInsert_L(La,1,2); ListInsert_L(La,2,3); ListInsert_L(La,3,5); Disp_L(La); ListInsert_L(Lb,1,1); ListInsert_L(Lb,2,4); ListInsert_L(Lb,3,6); ListInsert_L(Lb,4,7); Disp_L(Lb); MergeList_L(La,Lb,Lc); printf("合并之后的链表为:\n"); Disp_L(Lc); }实验指导与数据处理： 上机实验报告 实验课题：实现对有序数据集合的顺序查找和二分查找，并展示出查找过程 设计思路： 我们可以采用数组有序的保存所有数据，这样便于将数据的有序性和其索引的有序性统一起来，同时也便于查找数据。需要声明的是，我们不使用零下标的项，这样做是为了在顺序查找中优化传统顺序查找算法，具体原因后面会有详细介绍。为此，我们可以设计一个类，私有变量声明为该数组和数组的长度。由于集合中的数据类型未知，所以该类为模板类。 对于公有成员，我们创建六个成员函数，除了构造函数和析构函数，其他四个函数分别用来获取外界传入的数组长度、获取外界传入的数组数据、对数据实现顺序查找、对数据实现二分查找。 这里，我们只重点介绍顺序查找函数和二分查找函数。 对于顺序查找，我们对传统的顺序查找方法进行优化，避开每次对数据索引是否越界进行判断这一步骤。具体做法是：将所查找的元素保存在零下标的项中(这也是零下标闲置的原因)，然后按照下标顺序从后向前依次遍历匹配所查找元 素与数组元素。若两者相等，展示出该数组元素，并将其下标值反馈给客户；若两者不相等，展示出该元素，进行下一轮匹配。若最终标记下标达到零下标处，说明未查找到所要查找的元素，则客户反馈该信息。 优化后的顺序查找算法比传统的顺序查找算法减少一半的步骤，原因在于每次无须判断标记下标是否越界，这是该算法优化后的优点。它的缺点是没有利用到数据集合有序这一性质，且查找效率低。 对于二分查找，我们声明三个整型变量low、high和mid 依次标记查找域的上界下标、下界下标和中值下标，其中mid=(low+high)/2。我们在开始的时候将low初始化为1(上文中提到过，我们是从下表为1的位置开始存储数据)，将high初始化为len(数组长度)，并由此初始化mid的值。对于任意一次查找，将索引为mid的值与所查找的值进行比较。若两者相等，则将该元素的索引值反馈给客户；若所查找的值比索引为mid的值小，则将high的值变为mid-1，进行下一轮的查找；若所查找的值比索引为mid的值大，则将low 的值变为mid+1，进行下一轮查找。若最终low>high，则表明未查找到所要查找的值，将此信息反馈给客户。 该算法是一种效率很高的算法，因为它充分利用到数据集合的有序性，这一优点在数据规模较大时体现的更明显。 第九章 查找 9.1 若对大小均为n 的有序顺序表和无序顺序表分别进行顺序查找，试在下列三种情况下分别讨论两者在等概率时平均查找长度是否相同？ （1）查找不成功，即表中没有关键字等于给的值K 的记录； （2）查找成功，且表中只有一个关键字等于给定值K 的记录； （3）查找成功，且表中有若干关键字等于给定值K 的记录，要求找出所有这些记录。 答：(1)相同，有序n+1; 无序n+1 (2)相同，有序12n +；无序12 n + (3)不相同，对于有序表，找到了第一个与K 相同的元素后，只要再找到与K 不同的元素，即可停止查找；对于无序表，则要一直查找到最后一个元素。 9.3 画出对长度为13的有序表进行折半查找的判定树，并分别求其等概率时查找成功和查找不成功的ASL 。 答：查找成功：141(11223446)1313 ASL = ?+?+?+?= 查找失败：2615*3*414147ASL =+=（P220:查找不成功的过程就是走了一条从根节点到外部节点的路径，和给定值进行比较的关键字个数等于该路径上内部结点个数） 注：在折半查找判定树中，查找不成功时的比较次数即是查找相应外结点时与内结点的比较次数。整个判定树代表的有序表在查找失败时的平均查找长度即为查找每个外结点的比较次数之和除以外结点的个数。例如，长度为10的有序表在查找失败时的平均查找长度为： ASL=(3×5+4×6)/11=39/11 第二次作业 9.4已知如下所示长度为12的表 (Jan, Feb, Mar, Apr, May, Jun, July, Aug, Sep, Oct, Nov, Dec)每个元素的查找概率分别为（0.1，0.25，0.05，0.13，0.01，0.06，0.11，0.07，0.02，0.03，0.1，0.07） （1）1n i i i ASL PC ==∑，Pi 为查找表中第i 个记录的概率，11n i i P ==∑ ASL=0.1+0.25*2+3*0.05+4*0.13+5*0.01+6*0.06+7*0.11+8*0.07+9*0.02+10*0.03+11*0.1+12*0.07=5.43 或者 ASL=12*0.1+11*0.25+10*0.05+9*0.13+8*0.01+7*0.06+6*0.11+5*0.07+4*0.02+3*0.03+0.1*2+0.07=7.57 实验一顺序表的设计与实现 一．实验目的 1．进一步熟悉VC环境，会在其中编写调试运行c++代码，并理解多文件项目的组织，为以后的实验编程做准备。 2．掌握在VC环境中进行代码的调试 3．掌握顺序表的设计过程，并能通过一实例对设计的顺序表进行测试。 二、实验内容 1．顺序表的设计（Sqlist.h）：设计头文件sqlist.h，其内容如下： ①类型设计 ②基本操作的设计（包括初始化、求数据元素个数、插入、删除、取数据元素等） （补充完整） #define LIST_INIT_SIZE 10 #define LIST_INCREMENT 2 //线性表的动态分配顺序存储结构 struct SqList { ElemType *elem; int length; int listsize; }; //顺序表的初始化 void InitList(SqList &L) { //动态分配存储空间，并将分配到的存储空间的首地址保持在顺序表的elem项中 L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); //将顺序表的长度初始化为0 L.length=0; //将顺序表的容量初始化为分配的空间数 L.listsize=LIST_INIT_SIZE; } //在线性表的第i个位置上插入数据元素e Status ListInsert(SqList &L,int i,ElemType e) { ElemType *newbase,*q,*p; //判断插入的位置是否合理，不合理则返回错误信息 if(i<1||i>L.length+1) return ERROR; //判断是否有足够的空间插入元素，空间不够则增补空间 if(L.length==L.listsize) { newbase=(ElemType*)realloc(L.elem,(L.listsize+LIST_INCREMENT)*sizeof(ElemType )); if(!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=LIST_INCREMENT; } //插入数据元素（先将第i个元素及其后所有元素后移一个位置） q=L.elem+i-1; for(p=L.elem+L.length-1;p>=q;--p) *(p+1)=*p; //将元素e插入到第i个位置 *q=e; //线性表的长度增加1 ++L.length; return OK; } //删除线性表中第i个数据元素 Status ListDelete(SqList &L,int i,ElemType &e) { ElemType *p,*q; //判断删除的元素是否存在，不存在则返回错误信息 if(i<1||i>L.length) return ERROR; //将第i+1个元素及其后所有元素前移一个位置，实现元素的删除 p=L.elem+i-1; e=*p; q=L.elem+L.length-1; for(++p;p<=q;++p)有序顺序表的二分查找的递归算法
实验1-2顺序表和链表基本操作_参考答案
顺序表的按值插入
数据结构实验报告 有序表合并
数据结构实验两个有序顺序表的合并
各种查找算法的性能比较测试(顺序查找、二分查找)
数据结构——查找,顺序查找,折半查找
有序顺序表的合并
数据结构实验报告-顺序表的创建、遍历及有序合并操作
C++源程序顺序查找与二分查找
有序顺序表合并
实验报告03-两个有序链表的合并
二分查找和顺序查找
若对大小均为n的有序顺序表和无序顺序表分别进行顺序查
实验一-顺序表的设计与实现