线性表逆置(顺序表)实验报告

数据结构实验一顺序表实验报告
数据结构是计算机科学中的一门基础课程，在学习数据结构的过程中，顺序表是我们必须深入了解和掌握的重要数据结构之一。

在实验一中，我们对顺序表进行了一系列的操作，实现了增删改查等基本操作。

我们先来介绍一下顺序表的基本概念。

顺序表是将线性表中的数据存储在一段连续的存储空间中的数据结构，其查找效率高，但插入和删除操作效率较低。

顺序表需要预先分配一定的存储空间，当存储空间不足时需要进行动态扩容，即重新申请更大的存储空间并将原有数据复制到新的存储空间中。

在实验中，我们首先学习了顺序表的实现方式，包括顺序表的结构体定义、创建顺序表、插入元素、删除元素、修改元素以及查询元素等基本操作。

我们通过 C 语言来实现了这些操作，并将其封装成一个顺序表的 API，使其更加易于使用和维护。

在实验过程中，我们还发现顺序表中数据的存储顺序非常重要，因为顺序表中元素的存储顺序与元素的下标是一一对应的，如果存储的顺序错误，可能会导致元素的下标与我们想象中的不一致，从而造成一些意想不到的结果。

总的来说，实验一帮助我们更深入地了解了顺序表的实现方式和基本操作，同时也挖掘出了一些潜在问题，这对于我们今后的学习和实践都起到了很大的帮助。

实验1：线性表（顺序表的实现）一、实验项目名称顺序表基本操作的实现二、实验目的掌握线性表的基本操作在顺序存储结构上的实现。

三、实验基本原理顺序表是由地址连续的的向量实现的，便于实现随机访问。

顺序表进行插入和删除运算时，平均需要移动表中大约一半的数据元素，容量难以扩充四、主要仪器设备及耗材Window 11、Dev-C++5.11五、实验步骤1.导入库和一些预定义:2.定义顺序表:3.初始化:4.插入元素:5.查询元素：6.删除元素:7.销毁顺序表:8.清空顺序表:9.顺序表长度:10.判空:11.定位满足大小关系的元素(默认小于):12.查询前驱:13.查询后继:14.输出顺序表15.归并顺序表16.写测试程序以及主函数对顺序表的每一个操作写一个测试函数，然后在主函数用while+switch-case的方式实现一个带菜单的简易测试程序，代码见“实验完整代码”。

实验完整代码:#include <bits/stdc++.h>using namespace std;#define error 0#define overflow -2#define initSize 100#define addSize 10#define compareTo <=typedef int ElemType;struct List{ElemType *elem;int len;int listsize;}L;void init(List &L){L.elem = (ElemType *) malloc(initSize * sizeof(ElemType)); if(!L.elem){cout << "分配内存失败！";exit(overflow);}L.len = 0;L.listsize = initSize;}void destroy(List &L){free(L.elem);L.len = L.listsize = 0;}void clear(List &L){L.len = 0;}bool empty(List L){if(L.len == 0) return true;else return false;}int length(List L){return L.len;}ElemType getElem(List L,int i){if(i < 1 || i > L.len + 1){cout << "下标越界！";exit(error);}return L.elem[i - 1];}bool compare(ElemType a,ElemType b) {return a compareTo b;}int locateElem(List L,ElemType e) {for(int i = 0;i < L.len;i++){if(compare(L.elem[i],e))return i;}return -1;}int check1(List L,ElemType e){int idx = -1;for(int i = 0;i < L.len;i++)if(L.elem[i] == e)idx = i;return idx;}bool check2(List L,ElemType e){int idx = -1;for(int i = L.len - 1;i >= 0;i--)if(L.elem[i] == e)idx = i;return idx;}int priorElem(List L,ElemType cur_e,ElemType pre_e[]) {int idx = check1(L,cur_e);if(idx == 0 || idx == -1){string str = "";str = idx == 0 ? "无前驱结点" : "不存在该元素";cout << str;exit(error);}int cnt = 0;for(int i = 1;i < L.len;i++){if(L.elem[i] == cur_e){pre_e[cnt ++] = L.elem[i - 1];}}return cnt;}int nextElem(List L,ElemType cur_e,ElemType next_e[]){int idx = check2(L,cur_e);if(idx == L.len - 1 || idx == - 1){string str = "";str = idx == -1 ? "不存在该元素" : "无后驱结点";cout << str;exit(error);}int cnt = 0;for(int i = 0;i < L.len - 1;i++){if(L.elem[i] == cur_e){next_e[cnt ++] = L.elem[i + 1];}}return cnt;}void insert(List &L,int i,ElemType e){if(i < 1 || i > L.len + 1){cout << "下标越界！";exit(error);}if(L.len >= L.listsize){ElemType *newbase = (ElemType *)realloc(L.elem,(L.listsize + addSize) * sizeof(ElemType));if(!newbase){cout << "内存分配失败！";exit(overflow);}L.elem = newbase;L.listsize += addSize;for(int j = L.len;j > i - 1;j--)L.elem[j] = L.elem[j - 1];L.elem[i - 1] = e;L.len ++;}void deleteList(List &L,int i,ElemType &e){if(i < 1 || i > L.len + 1){cout << "下标越界！";exit(error);}e = L.elem[i - 1];for(int j = i - 1;j < L.len;j++)L.elem[j] = L.elem[j + 1];L.len --;}void merge(List L,List L2,List &L3){L3.elem = (ElemType *)malloc((L.len + L2.len) * sizeof(ElemType)); L3.len = L.len + L2.len;L3.listsize = initSize;if(!L3.elem){cout << "内存分配异常";exit(overflow);}int i = 0,j = 0,k = 0;while(i < L.len && j < L2.len){if(L.elem[i] <= L2.elem[j])L3.elem[k ++] = L.elem[i ++];else L3.elem[k ++] = L2.elem[j ++];}while(i < L.len)L3.elem[k ++] = L.elem[i ++];while(j < L2.len)L3.elem[k ++] = L2.elem[j ++];}bool visit(List L){if(L.len == 0) return false;for(int i = 0;i < L.len;i++)cout << L.elem[i] << " ";cout << endl;return true;}void listTraverse(List L){if(!visit(L)) return;}void partion(List *L){int a[100000],b[100000],len3 = 0,len2 = 0; memset(a,0,sizeof a);memset(b,0,sizeof b);for(int i = 0;i < L->len;i++){if(L->elem[i] % 2 == 0)b[len2 ++] = L->elem[i];elsea[len3 ++] = L->elem[i];}for(int i = 0;i < len3;i++)L->elem[i] = a[i];for(int i = 0,j = len3;i < len2;i++,j++) L->elem[j] = b[i];cout << "输出顺序表:" << endl;for(int i = 0;i < L->len;i++)cout << L->elem[i] << " ";cout << endl;}//以下是测试函数------------------------------------void test1(List &list){init(list);cout << "初始化完成!" << endl;}void test2(List &list){if(list.listsize == 0)cout << "线性表不存在!" << endl;else{int len;ElemType num;cout << "选择插入的元素数量：" << endl;cin >> len;cout << "依次输入要插入的元素：" << endl;for(int i = 1;i <= len;i++){cin >> num;insert(list,i,num);}cout << "操作成功！" << endl;}}void test3(){if(L.listsize == 0)cout << "线性表不存在!" << endl;else{cout << "请输入要返回的元素的下标" << endl;int idx;cin >> idx;cout << "线性表中第" << idx << "个元素是：" << getElem(L,idx) << endl;}}void test4(){if(L.listsize == 0)cout << "线性表不存在!" << endl;else{int idx;ElemType num;cout << "请输入要删除的元素在线性表的位置" << endl;cin >> idx;deleteList(L,idx,num);cout << "操作成功！" << endl << "被删除的元素是：" << num << endl; }}void test5(){if(L.listsize == 0)cout << "线性表不存在!" << endl;else{destroy(L);cout << "线性表已被销毁" << endl;}}void test6(){if(L.listsize == 0)cout << "线性表不存在!" << endl;else{clear(L);cout << "线性表已被清空" << endl;}}void test7(){if(L.listsize == 0)cout << "线性表不存在!" << endl;else cout << "线性表的长度现在是：" << length(L) << endl;}void test8(){if(L.listsize == 0)cout << "线性表不存在!" << endl;else if(empty(L))cout << "线性表现在为空" << endl;else cout << "线性表现在非空" << endl;}void test9(){if(L.listsize == 0)cout << "线性表不存在!" << endl;else{ElemType num;cout << "请输入待判定的元素:" << endl;cin >> num;cout << "第一个与目标元素满足大小关系的元素的位置：" << locateElem(L,num) << endl;}}void test10(){if(L.listsize == 0)cout << "线性表不存在!" << endl;else{ElemType num,num2[initSize / 2];cout << "请输入参照元素:" << endl;cin >> num;int len = priorElem(L,num,num2);cout << num << "的前驱为：" << endl;for(int i = 0;i < len;i++)cout << num2[i] << " ";cout << endl;}}void test11(){if(L.listsize == 0)cout << "线性表不存在!" << endl;else{ElemType num,num2[initSize / 2];cout << "请输入参照元素:" << endl;cin >> num;int len = nextElem(L,num,num2);cout << num << "的后继为：" << endl;for(int i = 0;i < len;i++)cout << num2[i] << " ";cout << endl;}}void test12(List list){if(L.listsize == 0)cout << "线性表不存在!" << endl;else{cout << "输出线性表所有元素:" << endl;listTraverse(list);}}void test13(){if(L.listsize == 0)cout << "初始线性表不存在!" << endl; else{List L2,L3;cout << "初始化一个新线性表" << endl;test1(L2);test2(L2);cout << "归并两个线性表" << endl;merge(L,L2,L3);cout << "归并成功!" << endl;cout << "输出合并后的线性表" << endl;listTraverse(L3);}}void test14(){partion(&L);cout << "奇偶数分区成功!" << endl;}int main(){std::ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int op = 0;while(op != 15){cout << "-----------------menu--------------------" << endl;cout << "--------------1：初始化------------------" << endl;cout << "--------------2：插入元素----------------" << endl;cout << "--------------3：查询元素----------------" << endl;cout << "--------------4：删除元素----------------" << endl;cout << "--------------5：销毁线性表--------------" << endl;cout << "--------------6：清空线性表--------------" << endl;cout << "--------------7：线性表长度--------------" << endl;cout << "--------------8：线性表是否为空----------" << endl;cout << "--------------9：定位满足大小关系的元素--" << endl;cout << "--------------10：查询前驱---------------" << endl;cout << "--------------11：查询后继---------------" << endl;cout << "--------------12：输出线性表-------------" << endl;cout << "--------------13：归并线性表-------------" << endl;cout << "--------------14：奇偶分区---------------" << endl;cout << "--------------15: 退出测试程序-----------" << endl;cout << "请输入指令编号:" << endl; if(!(cin >> op)){cin.clear();cin.ignore(INT_MAX,'\n');cout << "请输入整数!" << endl;continue;}switch(op){case 1:test1(L);break;case 2:test2(L);break;case 3:test3();break;case 4:test4();break;case 5:test5();break;case 6:test6();break;case 7:test7();break;case 8:test8();break;case 9:test9();break;case 10:test10();break;case 11:test11();break;case 12:test12(L);break;case 13:test13();break;case 14:test14();break;case 15:cout << "测试结束！" << endl;default:cout << "请输入正确的指令编号！" << endl;}}return 0;}六、实验数据及处理结果1.初始化:2.插入元素3.查询元素（返回的是数组下标，下标从0开始）4.删除元素（位置从1开始）5.销毁顺序表6.清空顺序表7.顺序表长度（销毁或清空操作前）8.判空（销毁或清空操作前）9.定位满足大小关系的元素（销毁或清空操作前）说明：这里默认找第一个小于目标元素的位置且下标从0开始，当前顺序表的数据为:1 4 2 510.前驱（销毁或清空操作前）11.后继（销毁或清空操作前）12.输出顺序表（销毁或清空操作前）13.归并顺序表（销毁或清空操作前）七、思考讨论题或体会或对改进实验的建议通过本次实验，我掌握了定义线性表的顺序存储类型，加深了对顺序存储结构的理解，进一步巩固和理解了顺序表的基本操作，如建立、查找、插入和删除等。

顺序表设计实验报告
顺序表是一种常见的线性表数据结构，它是将记录按一定的关系放入线性排列的存储空间，使其可以通过位置关系查找任意一个记录的结构。

本次实验的目的是熟悉顺序表的基本操作，通过编写程序实现对顺序表增加元素操作、删
除元素操作、查找元素操作、遍历元素操作等操作的实现。

在设计实现通用顺序表的程序时，可以将顺序表定义为模板表类，方便使用者可以将任何类型的变量定义为顺序表，无需重新编程。

并且在实现顺序表操作时，需要考虑到内存的分配和释放，以及某些特殊条
件下的处理，可以从中体会到C++程序中艰巨的任务实现。

实验总体来说是非常有趣的，从中学习到了C++实现顺序表操作的基本原理和常见问题的处理方案，以及须注意的一些特殊条件，同时也有助于培养对于面向对象编程的思维。

总之，本次实验是一次宝贵的学习经历，不仅让我加深了对于顺序表的理解，也提高了自己的编程能力，实现了艰苦的任务。

实验报告实验项目名称实验一线性表的操作所属课程名称数据结构实验类型验证实验实验日期2010-11-19院系数学与信息科学学院实验一线性表的操作一．实验目的1、掌握用上机调试线性表的基本方法；2、掌握线性表的基本操作，插入、删除、查找，以及线性表合并等简单操作在顺序存储结构上的运算。

二．实验环境硬件：计算机、256M以上内存，40G以上硬盘；软件：Windows XP , C++三．实验内容线性表基本操作的实现：构造一空线性表，将线性表置空，对线性表进行判空，求线性表的长度，查询线性表的第i个数据元素的值，查询要查询元素的上个元素的值，查询要查询元素的下个元素的值，删除线性表中的某个元素，将某元素插入线性表，对线性表进行查访并返回一特定的值。

给出两个线性表将其合并成一个线性表，销毁线性表。

四．实验步骤1、本实验的程序及头文件如下：SqlistMain.cpp#include"iostream.h"#include"stdio.h"#include"malloc.h"#include"stdlib.h"#include"SqListOperation.h"#include"function.h"#include "SqList.h"void main(){SqList L1,L2,L3;SqList *La=&L1,*Lb=&L2,*Lc=&L3;ElemType e;int m;InitList_Sq(La);InitList_Sq(Lb);cout<<"请输入线性表a"<<endl;EnterList_Sq(La);cout<<"输出线性表a"<<endl;PrintSqList(La);cout<<"输出线性表a长:"<<ListLength(La)<<endl;cout<<"验线性表a是否空表(空为1,不空为0):"<<ListEmpty(La)<<endl;cout<<"输入查询线性表a中元素的位置:";cin>>m;cout<<"输出线性表a中第m个元素:"<<GetElem(La,m)<<endl;cout<<"输入要查询元素的上个元素:";cin>>m;cout<<"输出性表a中第m个元素上个元素:"<<PriorElem(La,m)<<endl;cout<<"输入要查询元素的下个元素:";cin>>m;cout<<"输出线性表a中第m个元素下个元素:"<<NextElem(La,m)<<endl;cout<<"输入插入元素e及其位置m:";cin>>m>>e;ListInsert_Sq(La,e,m);cout<<"输出插入元素后的线性表a:"<<endl;PrintSqList(La);cout<<"输入删除元素位置m:";cin>>m;cout<<"除线性表a中第"<<m<<"个元素并输出其值:"<<ListDelete_Sq(La,m)<<endl;cout<<"输出删除元素后的线性表a:"<<endl;PrintSqList(La);cout<<"输入线性表b"<<endl;EnterList_Sq(Lb);cout<<"输出线性表b"<<endl;PrintSqList(Lb);cout<<"给线性表La按递增排序并输出:"<<endl;Sort_Increase(La);PrintSqList(La);cout<<"给线性表La按递增排序并输出:"<<endl;Sort_Increase(Lb);PrintSqList(Lb);cout<<"把线性表a和线性表b按非递减排列归并到线性表c,并输出线性表c:"<<endl;MergeList(La,Lb,Lc);PrintSqList(Lc);cout<<"删除线性表Lc"<<endl;ClearList(Lc);DestroyList(Lc);cout<<"输出删除线性表Lc后的表长:"<<ListLength(Lc)<<endl;}Function.hStatus InitList_Sq(SqList *L);Status DestroyList(SqList *L);Status ClearList(SqList *L);Status ListEmpty(SqList *L);int ListLength(SqList *L);Status GetElem(SqList *L,int i,ElemType *e);ElemType GetElem(SqList *L,int i);int LocateElem(SqList *L,ElemType e,Status (*compare)(ElemType a,ElemType e));Status PriorElem(SqList *L,ElemType cur_e,ElemType *pre_e);ElemType PriorElem(SqList *L,ElemType cur_e);Status NextElem(SqList *L,ElemType cur_e,ElemType *next_e);ElemType NextElem(SqList *L,ElemType cur_e);Status ListInsert_Sq(SqList *L,int i,ElemType e);Status ListDelete_Sq(SqList *L,int i,ElemType *e);ElemType ListDelete_Sq(SqList *L,int i);void PrintSqList(SqList *L);Status ListTraverse(SqList *L,Status (*visit)(ElemType *a));Status EnterList_Sq(SqList *L);Status compare(ElemType a,ElemType e);Status visit(ElemType *a);Status Union(SqList *La,SqList *Lb);Status MergeList(SqList *La,SqList *Lb,SqList *Lc);//Status MergeList_Sq(SqList *La,SqList *Lb,SqList *Lc);Status Sort_Increase(SqList *L);Status Sort_Reduce(SqList *L);SqlistOperation.h#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define OK 1#define ERROR 0#define TURE 1#define FALSE 0#define OVERFLOW 0#define INFEASIBLE 0typedef int Status;typedef int ElemType;typedef struct{ElemType *elem;int length;int listsize;}SqList;const int n=10;Sqlist.h//初始条件：已申明线性表类型为SqListStatus InitList_Sq(SqList *L){//构造一个空的顺序表L->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L->elem) exit(ERROR);//存储分配失败L->length=0;//空表长度为零L->listsize=LIST_INIT_SIZE;//初始存储容量return OK;}//InitList_SqStatus EnterList_Sq(SqList *L){//初始条件：已存在空的顺序表//操作结果：给顺序表输入元素，并记录元素个数int i,m;ElemType *newbase;cout<<"输入所需输入线性表元素的个数"<<endl;cin>>m;newbase=(ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(Ele mType));if(!newbase) exit(OVERFLOW);//存储分配失败L->elem=newbase;//新基址L->listsize+=LISTINCREMENT;//增加存储容量cout<<"依次输入所需元素:"<<endl;for(i=0;i<m;i++){cin>>L->elem[i];L->length++;}return OK;}Status DestroyList(SqList *L){//初始条件：顺序线性表L已存在。

顺序表实验报告顺序表是一种线性数据结构，它以连续的存储空间来存储数据元素，通过元素在数组中的相对位置来表示数据元素之间的逻辑关系。

在这个实验中，我们使用顺序表的实现来进行实验。

首先我们先了解一下顺序表的结构。

顺序表由两部分组成：表头和表体。

表头包含顺序表的一些基本信息，如顺序表的长度和当前表体的容量；表体是一个一维数组，用来存储数据元素。

在这个实验中，我们主要实现顺序表的插入操作和删除操作。

插入操作是指将一个新的数据元素插入到顺序表的某个位置；删除操作是指在顺序表中删除某个位置的数据元素。

实验步骤如下：1. 首先，我们需要定义一个顺序表的数据结构，包含表头和表体。

表头中需要有顺序表的长度和当前表体的容量，表体是一个一维数组。

2. 接下来，我们实现插入操作。

插入操作需要输入要插入的数据元素和插入的位置。

我们首先需要判断插入的位置是否合法，即位置在顺序表的范围内。

如果位置不合法，就返回插入失败。

如果位置合法，我们需要判断当前表体的容量是否已满。

如果已满，我们需要重新分配更大的内存空间来存储数据。

然后我们将插入位置后面的数据元素依次往后移动一位，给新的数据元素腾出位置。

最后，我们将要插入的数据元素放入指定位置处，并更新顺序表的长度。

3. 然后，我们实现删除操作。

删除操作需要输入要删除的位置。

首先我们需要判断删除的位置是否合法。

如果位置不合法，就返回删除失败。

如果位置合法，我们需要将删除位置后面的数据元素依次往前移动一位。

最后，我们更新顺序表的长度即可。

4. 最后，我们编写测试用例来检验我们实现的代码是否正确。

我们可以对插入和删除进行多次操作，然后查看顺序表的状态是否符合预期。

通过这个实验，我们可以更加深入地理解顺序表的原理和实现细节。

顺序表的插入和删除操作是非常常见的操作，掌握了这些操作，我们就能更加灵活地应用顺序表来解决实际问题。

同时，这个实验也锻炼了我们的编程能力和调试能力，提高了我们的代码质量和效率。

软件工程系实验报告Array课程名称：数据结构实验项目名称：线性表实验时间： 2012-3-5班级：姓名：学号：实验目的:掌握：1、顺序表的存储结构2、顺序表的应用操作熟悉：顺序表的一些基本操作和具体函数的定义。

了解：了解顺序表的结构特点及相关概念和顺序表的作用。

实验环境:C与C++程序设计学习与实验系统实验内容及要求：1.编写算法，实现顺序表的就地逆置，即利用原空间进行逆置。

实验过程（实验结果截图及其分析）：(一)顺序表的动态分配顺序存储结构#define chushiliang 100//线性表存储空间的初始分配量#define zhengliang 10//线性表存储空间的分配增量//建线性表typedef struct{int* elem;//存储空间基址int length;//当前长度int listsize;//当前分配的存储容量}sqlist;（二）顺序表的初始化//初始化int inintlist_sq(sqlist * L){L->elem=(int*)malloc(chushiliang*sizeof(int));if(!L->elem)return 1;//表示存储分配失败L->length=0;//空表长度为0L->listsize=chushiliang;//初始存储容量}（三）顺序表的打印函数void Print_list(sqlist L){int i;printf("\n打印的长度=%d \n",L.length);for(i=1;i<=L.length;i++){printf("\n第%d数=%d\n ",i,L.elem[i-1]);}}（四）顺序表的逆置函数/*逆置函数*/void Inverse(sqlist L){int i,t;for(i=0;i<L.length/2;i++){ //进行交换t=*(L.elem+i);*(L.elem+i)=*(L.elem+L.length-i-1);*(L.elem+L.length-i-1)=t;}printf("表逆置成功!!!\n");}（五）逆置结果（我输入100，200，300）实验心得：通过这次实验，让我更加明白了顺序表的存储结构。

说明每个实验题目含有一个main函数和一些函数, 与实验题目相关的基本运算的函数定义和main函数定义的代码在附录以及对应的文件夹中给出, 供上机实验参考使用。

对于每个题目, 只需要根据题目要求设计算法, 补充函数定义, 然后对程序进行编译、调试。

实验一线性表一、实验目的1．熟悉线性表的顺序和链式存储结构2．掌握线性表的基本运算3．能够利用线性表的基本运算完成线性表应用的运算二、实验内容设有一个线性表E={e1, e2, …, en-1, en}, 设计一个算法, 将线性表逆置, 即使元素排列次序颠倒过来, 成为逆线性表E’={ en , en-1 , …, e2 , e1 }, 要求逆线性表占用原线性表空间, 并且用顺序表和单链表两种方法表示, 分别用两个程序来完成。

（文件夹: 顺序表逆置、单链表逆置）已知由不具有头结点的单链表表示的线性表中, 含有三类字符的数据元素（字母、数字和其他字符）, 试编写算法构造三个以循环链表表示的线性表, 使每个表中只含有同一类的字符, 且利用原表中的结点空间, 头结点可另辟空间。

（文件夹: 分解单链表）实验二栈和队列一、实验目的1．熟悉栈和队列的顺序和链式存储结构2．掌握栈和队列的基本运算3．能够利用栈和队列的基本运算完成栈和队列应用的运算二、实验内容1．设单链表中存放有n个字符, 试编写算法, 判断该字符串是否有中心对称的关系, 例如xyzzyx是中心对称的字符串。

（提示: 将单链表中的一半字符先依次进栈, 然后依次出栈与单链表中的另一半字符进行比较。

）（文件夹: 判字符串中心对称）假设以数组sequ[m]存放循环队列的元素, 同时设变量rear和quelen 分别指示循环队列中队空的条件：sq->quelen==0；队满的条件：sq->quelen==m。

（文件夹：循环队列）实验三串一、实验目的1．熟悉串的顺序存储结构2．掌握串的基本运算及应用二、实验内容1. 串采用顺序存储结构, 编写朴素模式匹配算法, 查找在串中是否存在给定的子串。

顺序表的实现及应用实验报告序言顺序表是一种基本的线性数据结构，它采用物理上的连续存储结构，在数据元素的存储空间上也是连续的。

本文将阐述顺序表的实现及应用实验报告。

实验目的掌握顺序表的定义、实现及其应用。

实验内容1. 顺序表的定义顺序表是一种线性表的存储方法，它把线性表中的元素按其逻辑顺序依次存储在一段连续的存储区域中，也就是一维数组。

顺序表既可以用于存储静态数据，也可以用于存储动态数据。

2. 顺序表的实现顺序表的实现需要用到一维数组，当创建顺序表时，先要确定它的最大长度，然后根据长度创建相应大小的一维数组，接着插入数据时，依次将数据插入到数组中，需要注意的是，数组是从0开始储存的，而不是从1开始。

以下是顺序表的实现代码示例：```python# 设定最大长度为10MAX_SIZE = 10class SeqList:def __init__(self):self.seq = [None] * MAX_SIZEdef insert(self, index, value):# 检查是否超出最大长度，或者下标越界if index < 0 or index > MAX_SIZE or index >= len(self.seq): raise IndexError# 移动数组，腾出位置for i in range(MAX_SIZE - 1, index - 1, -1):self.seq[i] = self.seq[i - 1]# 插入数据self.seq[index] = valuedef pop(self, index):# 检查下标合法性if index < 0 or index >= len(self.seq):raise IndexError# 移动数组，删除数据for i in range(index, MAX_SIZE - 1):self.seq[i] = self.seq[i + 1]# 最后一位设为None，释放空间self.seq[-1] = Nonedef __repr__(self):return str(self.seq)```3. 顺序表的应用顺序表可以用于很多场景，比如存储学生成绩、成绩排名、图书管理等，以下是一个简单的例子：存储学生成绩并排序```pythonseq = SeqList()seq.insert(0, 89)seq.insert(1, 92)seq.insert(2, 76)seq.insert(3, 68)seq.insert(4, 100)print(seq)```输出：`[89, 92, 76, 68, 100, None, None, None, None, None]` 对学生成绩进行排序：```pythonseq.seq.sort(reverse=True)print(seq)```输出：`[100, 92, 89, 76, 68, None, None, None, None, None]` 结论通过本次实验，我们掌握了顺序表的定义、实现及其应用，顺序表在大多数情况下提供了比较高效的数据访问，因此在实际开发中非常有用。

《线性表的顺序存储》实验报告1.需解决的的问题利用顺序表，设计一组输入数据。

2.数据结构的定义typedefstruct{ElemType *elem;int length;intlistsize;}SqList;3.程序的结构图4.函数的功能1）初始化一个空顺序表voidInitSqList(SqList *L){L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L->elem) exit(OVERFLOW);L->length=0;L->listsize=LIST_INIT_SIZE;}2）输入元素voidPushSqList(SqList *L){inti;printf("input the length of the list:");scanf("%d",&L->length);printf("input the sqlist:");for(i=0;i<L->length;i++){printf("input the %dth number:",i+1);scanf("%d",&L->elem);}}3）在指定位置插入一个指定的元素voidInsertSqList(SqList *L,inti,ElemType x){ElemType *newbase;intn,m;if(i<1||i>L->length+1){printf("ERROR!");}if(L->length>=L->listsize){newbase=(ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase) exit(OVERFLOW);L->elem=newbase;L->listsize+=LISTINCREMENT;}else{for(n=L->length;n>=i;n--){++L->length;L->elem[n]=L->elem[n-1];}L->elem[i-1]=x;printf("the list is:");for(m=0;m<L->length+1;n++)printf("%d",L->elem[n]);}}4）删除指定位置的元素voidDelSqList(SqList *L,inti){ElemType *p,*q;ElemType x;int n;if(i<1||i>L->length)printf("ERROR!");p=&(L->elem[i-1]);x=*p;for(q=p;q<&(L->elem[L->length-1]);q++)*q=*(q+1);L->length--;printf("the element which is delete is %d",x);printf("the list is:");for(n=0;n<L->length-1;n++)printf("%d",L->elem[n]);}5）将顺序表中所有的元素颠倒voidChangeoverSqList(SqList *L){SqList S;inti,j;if(L->length==L->listsize)S.elem=(ElemType*)malloc(L->length*sizeof(ElemType));if(!S.elem) exit(OVERFLOW);else{for(i=0;i<L->length;i++)S.elem[i]=L->elem[L->length-i-1];for(i=0;i<L->length;i++)L->elem[i]=S.elem[i];}printf("the list is:");for(j=0;j<L->length;i++)printf("%d",L->elem[i]);}6）按顺序输出表中元素voidPrintSqList(SqList *L){inti;for(i=0;i<L->length;i++)printf("%d ",L->elem[i]);}7）摧毁顺序表voidDestroySqList(SqList *L){if(L->elem) free(L->elem);}8）清空顺序表voidClearSqList(SqList *L){L->length=0;}9）查找指定位置的元素，并返回该元素的值intGetElem(SqList *L,inti){ElemType x;if(i<1||i>L->length+1) {printf("ERROR!");}else{x=L->elem[i-1];printf("the elem is %d",x);}}5.输入/输出数据1）创建一个顺序表，先输入表长度，然后输入数据2）选择菜单，进行不同操作选‘1’，在指定位置插入指定元素选‘2’，删除指定位置的元素选‘3’，颠倒顺序表中元素的顺序选‘4’，按顺序输出表中的元素选‘5’，摧毁顺序表选‘6’，清空线性表选‘7’，输出当前顺序表的长度选‘8’，输出指定位置的元素选‘9’，退出该程序6.总结这个实验让我更好的掌握了在线性表的顺序存储中如何初始化，如何进行输入输出的处理，以及各种常用功能是怎样实现的。