数据结构_线性表的顺序表示与实现

第1讲线性表本章主要掌握如下内容：线性表的定义和基本操作，线性表的实现,线性表的顺序存储结构及链式存储结构，线性表的应用。

知识点分析（一）线性表的定义和基本操作1．线性表基本概念1）定义：是由相同类型的结点组成的有限序列。

如：由n个结点组成的线性表（a1, a2, …, a n）a1是最前结点，a n是最后结点。

结点也称为数据元素或者记录。

2）线性表的长度：线性表中结点的个数称为其长度。

长度为0的线性表称为空表。

3）结点之间的关系：设线性表记为（a1,a2,…a i-1 , a i, a i+1 ,…a n），称a i-1是a i的直接前驱结点．．．．（简称前驱），a i+1是a i的直接后继结点．．．．（简称后继）。

4）线性表的性质：①线性表结点间的相对位置是固定．．的，结点间的关系由结点在表中的位置确定。

②如果两个线性表有相同的数据结点，但它们的结点顺序不一致，该两个线性表也是不相等的。

注意：线性表中结点的类型可以是任何数据（包括简单类型和复杂类型），即结点可以有多个成分，其中能唯一标识表元的成分称为关键字（key），或简称键。

以后的讨论都只考虑键，而忽略其它成分，这样有利于把握主要问题，便于理解。

『经典例题解析』线性表的特点是每个元素都有一个前驱和一个后继。

( )【答案】错误。

【解析】线性表的第一个数据元素没有前驱，最后一个元素没有后继。

其余的所有元素都有一个前驱和后继。

2．线性表的抽象数据类型线性表是一个相当灵活的数据结构，其长度可以根据需要增加或减少。

从操作上讲，用户不仅可以对线性表的数据元素进行访问操作，还可以进行插入、删除、定位等操作。

1）线性表的基本操作假设线性表L有数据对象 D＝{ai | ai∈ElemSet，i=1,2,3,…,n，n>=0},数据元素之间的关系R＝{<ai-1,ai>|ai-1,ai∈D,i=1,2,…,n},则线性表L的基本操作如下所示：●InitList(&L)：其作用是构造一个长度为0的线性表（空线性表）；●DestoryList(&L)：其作用是销毁当前的线性表L；●ClearList(&L)：清空线性表L，使之成为空表；●ListLength(L)：返回线性表L的长度，即线性表中数据元素的个数；●ListEmpty(L) ：判断线性表L是否为空表，是则返回True，否则返回False；●GetElem(L,i,&e)：将线性表L中第i个数据元素的值返回到变量e中；●LocateELem(L,e,compare( )) ：判断线性表L中是否存在与e满足compare（）条件的数据元素，有则返回第一个数据元素；●PriorElem(L,cur_e,&pri_e)：返回线性表L中数据元素cur_e的前驱结点；●NextElem(L,cur_e,&next_e)：返回线性表L中数据元素cur_e的后继结点；●ListInsert(&L,i,e)：向线性表L的第i个位置之前插入一个数据元素，其值为e；●ListDelete(&L,i,&e)：删除线性表L的第i个数据元素，并将该数据元素的值返回到e中；●ListTraverse(L,visit())：遍历线性表中的每个数据元素。

实验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.归并顺序表（销毁或清空操作前）七、思考讨论题或体会或对改进实验的建议通过本次实验，我掌握了定义线性表的顺序存储类型，加深了对顺序存储结构的理解，进一步巩固和理解了顺序表的基本操作，如建立、查找、插入和删除等。

数据结构实验报告线性表数据结构实验报告：线性表引言：数据结构是计算机科学中的重要概念，它涉及到如何组织和存储数据，以及如何有效地操作和管理这些数据。

线性表是数据结构中最基本的一种，它是一种有序的数据元素集合，其中的元素之间存在着一对一的关系。

一、线性表的定义和特点线性表是由n个数据元素组成的有限序列，其中n为表的长度。

这些数据元素可以是相同类型的，也可以是不同类型的。

线性表中的数据元素按照一定的顺序排列，并且每个数据元素都有唯一的前驱和后继。

线性表的特点有以下几个方面：1. 数据元素之间是一对一的关系，即每个数据元素只有一个直接前驱和一个直接后继。

2. 线性表中的元素是有序的，每个元素都有一个确定的位置。

3. 线性表的长度是有限的，它的长度可以是0，也可以是任意正整数。

二、线性表的实现方式线性表可以使用不同的数据结构来实现，常见的实现方式有数组和链表。

1. 数组实现线性表：数组是一种连续存储的数据结构，它可以用来存储线性表中的元素。

数组的优点是可以快速访问任意位置的元素，但是插入和删除操作需要移动其他元素，效率较低。

2. 链表实现线性表：链表是一种非连续存储的数据结构，它通过指针将线性表中的元素链接起来。

链表的优点是插入和删除操作简单高效，但是访问任意位置的元素需要遍历链表，效率较低。

三、线性表的基本操作线性表的基本操作包括插入、删除、查找和修改等。

1. 插入操作：插入操作用于向线性表中插入一个新元素。

具体步骤是先将插入位置后面的元素依次后移，然后将新元素插入到指定位置。

2. 删除操作：删除操作用于从线性表中删除一个元素。

具体步骤是先将删除位置后面的元素依次前移，然后将最后一个元素删除。

3. 查找操作：查找操作用于在线性表中查找指定元素。

具体步骤是从线性表的第一个元素开始逐个比较，直到找到匹配的元素或者到达线性表的末尾。

4. 修改操作：修改操作用于修改线性表中的某个元素的值。

具体步骤是先查找到要修改的元素，然后将其值更新为新值。

数据结构线性表实验报告数据结构线性表实验报告实验目的：本次实验主要是为了学习和掌握线性表的基本操作和实现方式。

通过实验，我们可以加深对线性表的理解，并能够熟悉线性表的基本操作。

实验设备与环境：本次实验所需的设备包括计算机和编程环境。

我们选择使用C语言来实现线性表的操作，并在Visual Studio Code编程软件中进行编写和调试。

实验内容：1.线性表的定义和基本操作1.1 线性表的定义：线性表是一种有序的数据结构，其中的元素按照一定的顺序存储，可以插入、删除和访问元素。

1.2 线性表的基本操作：1.2.1 初始化线性表：创建一个空的线性表。

1.2.2 判断线性表是否为空：判断线性表是否不含有任何元素。

1.2.3 获取线性表的长度：返回线性表中元素的个数。

1.2.4 在线性表的指定位置插入元素：在线性表的第i个位置插入元素x，原第i个及其之后的元素依次后移。

1.2.5 删除线性表中指定位置的元素：删除线性表中第i个位置的元素，原第i+1个及其之后的元素依次前移。

1.2.6 获取线性表中指定位置的元素：返回线性表中第i个位置的元素的值。

1.2.7 清空线性表：将线性表中的元素全部删除，使其变为空表。

2.线性表的顺序存储结构实现2.1 线性表的顺序存储结构：使用数组来实现线性表的存储方式。

2.2 线性表的顺序存储结构的基本操作：2.2.1 初始化线性表：创建一个指定长度的数组，并将数组中的每个元素初始化为空值。

2.2.2 判断线性表是否为空：判断线性表的长度是否为0。

2.2.3 获取线性表的长度：返回线性表数组的长度。

2.2.4 在线性表的指定位置插入元素：将要插入的元素放入指定位置，并将原位置及其之后的元素依次后移。

2.2.5 删除线性表中指定位置的元素：将指定位置的元素删除，并将原位置之后的元素依次前移。

2.2.6 获取线性表中指定位置的元素：返回指定位置的元素的值。

2.2.7 清空线性表：将线性表数组中的每个元素赋空值。

《算法与数据结构》课程实验报告一、实验目的1、实现线性表的顺序存储结构。

2、熟悉C++程序的基本结构，掌握程序中的头文件、实现文件和主文件之间的相互关系及各自的作用。

3、熟悉顺序表的基本操作方式,掌握顺序表相关操作的具体实现。

二、实验内容及要求对顺序存储的线性表进行一些基本操作。

主要包括：（1）插入：操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入。

（2）删除：操作方式可分为删除指定元素、删除指定位置的元素等，尝试实现逻辑删除操作。

（3）显示数据。

（4）查找：查询指定的元素（可根据某个数据成员完成查询操作）。

（5）定位操作：定位指定元素的序号。

（6）更新：修改指定元素的数据。

（7）数据文件的读写操作等。

其它操作可根据具体需要自行补充。

要求线性表采用类的定义,数据对象的类型自行定义。

三、系统分析（1）数据方面：能够实现多种数据类型顺序表的创建，并进行操作，不同的数据类型数据使用不同的文本文件保存。

（2）功能方面：能够实现线性表的一些基本操作，主要包括：1.计算表最大可以容纳表项个数以及当前表的当前长度。

2.能够进行添加操作，在已有的数据文件中进行数据的添加。

3.能够进行搜索操作，返回搜索项在表中表项序号4.能够进行定位操作，定位到表中合理位置。

5.能够进行取值操作，根据用户需求取出表中某项的值。

6.能够进行修改操作，在用户选择修改项后将重新输入内容修改到对应位置。

7.能够进行插入操作，在用户选择合理位置并输入插入内容后即可。

8.能够进行删除操作，用户根据选择表中项数删除对应数据。

9.能够进行判断表空或表满。

四、系统设计（1）设计的主要思路根据实验要求，首先将顺序表模板类完成，并将需要实现的功能代码完善，在写实现各个功能的菜单并将模板类实例化为简单数据类型最后进行调试，由于还需使得顺序表能够存储自定义的学生类类型数据，故根据要求写出Student类，并将之前所写得模板类用学生类数据类型实例化，再进行调试。

数据结构实验报告-实验⼀顺序表、单链表基本操作的实现实验⼀顺序表、单链表基本操作的实现l 实验⽬的1、顺序表（1）掌握线性表的基本运算。

（2）掌握顺序存储的概念，学会对顺序存储数据结构进⾏操作。

（3）加深对顺序存储数据结构的理解，逐步培养解决实际问题的编程能⼒。

l 实验内容1、顺序表1、编写线性表基本操作函数：（1）InitList(LIST *L,int ms)初始化线性表；（2）InsertList(LIST *L,int item,int rc)向线性表的指定位置插⼊元素；（3）DeleteList1(LIST *L,int item)删除指定元素值的线性表记录；（4）DeleteList2(LIST *L,int rc)删除指定位置的线性表记录；（5）FindList(LIST *L,int item)查找线性表的元素；（6）OutputList(LIST *L)输出线性表元素；2、调⽤上述函数实现下列操作：（1）初始化线性表；（2）调⽤插⼊函数建⽴⼀个线性表；（3）在线性表中寻找指定的元素；（4）在线性表中删除指定值的元素；（5）在线性表中删除指定位置的元素；（6）遍历并输出线性表；l 实验结果1、顺序表（1）流程图（2）程序运⾏主要结果截图（3）程序源代码#include<stdio.h>#include<stdlib.h>#include<malloc.h>struct LinearList/*定义线性表结构*/{int *list; /*存线性表元素*/int size; /*存线性表长度*/int Maxsize; /*存list数组元素的个数*/};typedef struct LinearList LIST;void InitList(LIST *L,int ms)/*初始化线性表*/{if((L->list=(int*)malloc(ms*sizeof(int)))==NULL){printf("内存申请错误");exit(1);}L->size=0;L->Maxsize=ms;}int InsertList(LIST *L,int item,int rc)/*item记录值；rc插⼊位置*/ {int i;if(L->size==L->Maxsize)/*线性表已满*/return -1;if(rc<0)rc=0;if(rc>L->size)rc=L->size;for(i=L->size-1;i>=rc;i--)/*将线性表元素后移*/L->list[i+=1]=L->list[i];L->list[rc]=item;L->size++;return0;}void OutputList(LIST *L)/*输出线性表元素*/{int i;printf("%d",L->list[i]);printf("\n");}int FindList(LIST *L,int item)/*查找线性元素，返回值>=0为元素的位置，返回-1为没找到*/ {int i;for(i=0;i<L->size;i++)if(item==L->list[i])return i;return -1;}int DeleteList1(LIST *L,int item)/*删除指定元素值得线性表记录，返回值为>=0为删除成功*/ {int i,n;for(i=0;i<L->size;i++)if(item==L->list[i])break;if(i<L->size){for(n=i;n<L->size-1;n++)L->list[n]=L->list[n+1];L->size--;return i;}return -1;}int DeleteList2(LIST *L,int rc)/*删除指定位置的线性表记录*/{int i,n;if(rc<0||rc>=L->size)return -1;for(n=rc;n<L->size-1;n++)L->list[n]=L->list[n+1];L->size--;return0;}int main(){LIST LL;int i,r;printf("list addr=%p\tsize=%d\tMaxsize=%d\n",LL.list,LL.size,LL.Maxsize);printf("list addr=%p\tsize=%d\tMaxsize=%d\n",LL.list,LL.list,LL.Maxsize);while(1){printf("请输⼊元素值，输⼊0结束插⼊操作:");fflush(stdin);/*清空标准输⼊缓冲区*/scanf("%d",&i);if(i==0)break;printf("请输⼊插⼊位置：");scanf("%d",&r);InsertList(&LL,i,r-1);printf("线性表为：");OutputList(&LL);}while(1){printf("请输⼊查找元素值，输⼊0结束查找操作：");fflush(stdin);/*清空标准输⼊缓冲区*/scanf("%d ",&i);if(i==0)break;r=FindList(&LL,i);if(r<0)printf("没有找到\n");elseprintf("有符合条件的元素，位置为：%d\n",r+1);}while(1){printf("请输⼊删除元素值，输⼊0结束查找操作：");fflush(stdin);/*清楚标准缓存区*/scanf("%d",&i);if(i==0)break;r=DeleteList1(&LL,i);if(i<0)printf("没有找到\n");else{printf("有符合条件的元素，位置为：%d\n线性表为：",r+1);OutputList(&LL);}while(1){printf("请输⼊删除元素位置，输⼊0结束查找操作：");fflush(stdin);/*清楚标准输⼊缓冲区*/scanf("%d",&r);if(r==0)break;i=DeleteList2(&LL,r-1);if(i<0)printf("位置越界\n");else{printf("线性表为：");OutputList(&LL);}}}链表基本操作l 实验⽬的2、链表（1）掌握链表的概念，学会对链表进⾏操作。

实验1: 顺序表的操作实验一、实验名称和性质二、实验目的1．掌握线性表的顺序存储结构的表示和实现方法。

2．掌握顺序表基本操作的算法实现。

3．了解顺序表的应用。

三、实验内容1．建立顺序表。

2．在顺序表上实现插入、删除和查找操作（验证性内容）。

3．删除有序顺序表中的重复元素（设计性内容）。

四、实验的软硬件环境要求硬件环境要求：PC机（单机）使用的软件名称、版本号：Windows环境下的VC++6.0五、知识准备前期要求熟练掌握了C语言的编程规则、方法和顺序表的基本操作算法。

六、验证性实验1．实验要求编程实现如下功能：（1）根据输入顺序表的长度n和各个数据元素值建立一个顺序表，并输出顺序表中各元素值，观察输入的内容与输出的内容是否一致。

（2）在顺序表的第i个元素之前插入一个值为x的元素，并输出插入后的顺序表中各元素值。

（3）删除顺序表中第i个元素，并输出删除后的顺序表中各元素值。

（4）在顺序表中查找值为e的数据元素，如果查找成功，则显示“查找成功”和该元素在顺序表中的位置，否则显示“查找失败”。

2. 实验相关原理线性表的顺序存储结构称为顺序表，顺序表的存储结构描述为：#define MAXLEN 30 /*线性表的最大长度*/typedef struct{Elemtype elem[MAXLEN]; /*顺序表中存放元素的数组，其中elemtype为抽象数据类型，在程序具体实现时可以用任意类型代替*/int length; /*顺序表的长度，即元素个数*/}Sqlist; /*顺序表的类型*/【核心算法提示】（1）顺序表插入操作的基本步骤：要在顺序表中的第i个数据元素之前插入一个数据元素x,首先要判断插入位置i是否合法，假设线性表的表长为n，则i的合法值范围：1≤i ≤n+1，若是合法位置，就再判断顺序表是否满，如果满，则增加空间或结束操作，如果不满，则将第i个数据元素及其之后的所有数据元素都后移一个位置，此时第i个位置已经腾空，再将待插入的数据元素x插入到该位置上，最后将线性表的表长增加1。

数据结构——线性表（顺序实现） 好好学习基础知识，出⼈头地就靠它了，内外兼修。

（好吧，我现在内外都不⾏）写这篇⽂章的⽬的就是为了，巩固刚学完的线性表，个⼈能⼒有限，若有不当之处，望指出。

线性表 好了，扯完了，说正事： 1、定义 线性表是⼀种及其常⽤的并且最简单的⼀种数据结构。

简单来说，线性表就是集合⾥的元素的有限排列。

（在这⾥我把集合定义为具有相同属性的元素，会有些狭义） 在线性表中数据元素之间的关系是⼀对⼀的关系，即除了第⼀个和最后⼀个数据元素之外，其它数据元素都是⾸尾相接的（注意，这句话只适⽤⼤部分线性表，⽽不是全部。

⽐如，循环链表逻辑层次上也是⼀种线性表（存储层次上属于链式存储），但是把最后⼀个数据元素的尾指针指向了⾸位结点）[] 怎么说呢，毕竟数据结构毕竟是逻辑结构，逻辑上符合线性结构的特征即可，存储结构能实现就⾏。

线性表的很重要！很重要！很重要！后⾯的栈，队列，串等都是基于线性表的基础上实现的，所以说⼀定要学好线性表 2、线性表的特点： 对于任意的的⾮空线性表或者线性结构有： 1、存在唯⼀⼀个被称为 ”第⼀个“的元素 2、存在唯⼀⼀个被称为 ”最后⼀个“的元素 3、出第⼀个元素之外，每⼀个元素都存在⼀个后继 4、除最后⼀个元素之外，每⼀个元素都存在⼀个前驱 3、基本操作 1、Create（*L）创建空表 2、InitEmpty（*L）初始化 3、getLength（*L）获取长度 4、Insert（*L）插⼊元素 5、Remove（*L）移除元素 6、IsEmpty（*L）空表检测 7、IsFulled（*L）表满检测（顺序表常⽤，链式表基本不⽤） 8、Delete（*L）删除表 9、getElemt（*L）获取元素 10、Traverse（*L）遍历输出所有元素 11、Clear（*L）清除所有元素 4 、实现 好了最⿇烦的事情开始了，数据结构在计算机上的的映射。

众所周知，线性表有两种实现⽅法，⼀种是顺序表，另⼀种是链式表，这两种结构实现最⼤的不同在于前者逻辑关系⽆需存储空间，⽽后者则需要⽤额外的空间（顺便记录⼀下，指针⼤⼩只由环境有关（严格意义上说和CPU的位数有关）本篇只实现顺序结构）。

实验报告
课程名称数据结构
实验项目线性表的实现及应用
实验仪器PC机一台
学院_____ 专业
班级/学号
姓名
实验日期
成绩
指导教师
北京信息科技大学
信息管理学院
（数据结构课程上机）实验报告
3.
1.实验名称、实验目的、实验内容、实验要求由教师确定，实验前由教师事先填好，然后作为实验报告模
版供学生使用；
2.实验准备由学生在实验或上机之前填写，教师应该在实验前检查；
3.实验过程由学生记录实验的过程，包括操作过程、遇到哪些问题以及如何解决等；
4.实验总结由学生在实验后填写，总结本次实验的收获、未解决的问题以及体会和建议等；
5.源程序、代码、具体语句等，若表格空间不足时可作为附录另外附页。

数据结构实验课教案数据结构教案实验一：线性表的顺序表示与实现实验学时：2学时一．实验目的：1．掌握线性表的顺序存储结构；2．掌握在顺序表上进行的插入、删除、查找、修改等操作。

二．实验内容：1．分别建立顺序表，并输入初始数据；2．对顺序表分别编写插入、删除、查找、修改等函数。

三．实验重点：顺序表的建立及操作。

四．实验要求：1．用C语言编写程序源代码；2．要分别完成建立、插入、删除、查找、修改五种功能。

3．源程序必须编译调试成功，独立完成。

五．实验器材：一个装有C语言编译环境的计算机。

六．实验步骤：顺序表：1．定义头文件和顺序表的存储结构类型等 #define ok 1 #define error 0 #define overflow 0 #define null 0 #include #include #define list_init_size 100 #define listincrement 10 typedef int elemtype; typedef int status; typedef struct{ elemtype *elem; int length; int listsize; }sqlist;1 2．编写构造空顺序表的函数status listinit(sqlist *l) { l->elem=(elemtype *)malloc(list_init_size*sizeof(elemtype)); if(!l->elem)return overflow; l->length=0; l->listsize=list_init_size; return ok; }3．编写对顺序表进行插入操作的函数： status listinsert(sqlist *l,int i,elemtype e) { elemtype *newbase,*q,*p; if(ilistlength(*l)+1)return error; if(l->length==l->listsize){ newbase=(elemtype *)realloc(l->elem,(l->listsize+listincrement)*sizeof(elemtype));if(!newbase)return overflow;l->listsize+=listincrement;} q=&(l->elem[i-1]); for(p=&(l->elem[l->length])-1;p>=q;--p)*(p+1)=*p; *q=e; ++l->length; return ok; }4．编写对顺序表进行删除操作的函数：status listdelete(sqlist *l,int i,elemtype *e) { elemtype *p,*q; if(il->length)return error; p=&(l->elem[i-1]); *e=*p; q=l->elem+l->length-1; for(++p;p*(p-1)=*p; --l->length;2 return ok; }5．编写对顺序表进行查找操作的函数： status getelem(sqlist l,int i,elemtype *e) { if(ilistlength(l)) return error; *e=[i-1]; return ok; }6．编写对顺序表进行修改操作的函数： status locateelem(sqlist l,elemtype e) { int i; for(i=0;iif([i]==e)return i+1; return 0; } 7．编写实现两个线性表的归并操作的函数 void mergelist(sqlist la,sqlist lb,sqlist *lc) { int i,j,k; intla_len,lb_len; elemtype ai,bj; i=j=1; k=0; listinit(lc); la_len=listlength(la); lb_len=listlength(lb); while(i{listinsert(lc,++k,ai);++i;} else{listinsert(lc,++k,bj);++j;} } while(iwhile(j{ getelem(lb,j++,&bj); listinsert(lc,++k,bj);} }8．销毁线性表、清空线性表、判空、求表长等 status destroylist(sqlist *l) { if(l->elem) free(l->elem),l->elem=null; return ok; }status clearlist(sqlist *l) { l->length=0; return ok; }status listempty(sqlist l) { return(==0); }status listlength(sqlist l) { return ; }9．打印线性表4 void print(sqlist l) { int i; printf(\”\\nlist: \”); for(i=0;i10．编写主函数 void main() { int i; int n; elemtype a; sqlist l,la,lb,lc; clrscr(); listinit(&l); listinit(&la); listinit(&lb);printf(\”please input list number\”); scanf(\”%d\”,&n); printf(\”\\n\”); for(i=0;iscanf(\”%d\”,&a);listinsert(&l,i+1,a); } print(l); printf(\”\\nlist length:%d\”,listlength(l));getelem(l,4,&a); printf(\”\\ngetelem(l,4,&a),%d\”,a);listdelete(&l,3,&a); printf(\”\\nlistdelete(&l,3,&a),%d\”,a); print(l);printf(\”\\ninput list la\”);for(i=0;iscanf(\”%d\”,&a);listinsert(&la,i+1,a); } printf(\”\\ninput list lb\”);5 for(i=0;iscanf(\”%d\”,&a);listinsert(&lb,i+1,a); } mergelist(la,lb,&lc); print(la);print(lb);print(lc); }6实验二：链表实验学时：2学时一．实验目的：11．掌握单、双向链表的存储结构；12．掌握在单、双向链表上进行的插入、删除、查找、修改等操作。

数据结构实验报告1线性表的顺序存储结构一、实验目的本次实验的主要目的是深入理解线性表的顺序存储结构，并通过编程实现其基本操作，包括创建线性表、插入元素、删除元素、查找元素以及输出线性表等。

通过实际操作，掌握顺序存储结构的特点和优势，同时也了解其在不同情况下的性能表现。

二、实验环境本次实验使用的编程语言为C+＋，编译环境为Visual Studio 2019。

三、实验原理1、线性表的定义线性表是由 n（n≥0）个数据元素组成的有限序列。

在顺序存储结构中，线性表的元素存储在一块连续的存储空间中，通过数组来实现。

2、顺序存储结构的特点存储密度高，无需额外的指针来表示元素之间的关系。

可以随机访问表中的任意元素，时间复杂度为 O(1)。

插入和删除操作需要移动大量元素，平均时间复杂度为 O(n)。

四、实验内容及步骤1、定义线性表的数据结构｀｀｀cppdefine MAX_SIZE 100 ／／定义线性表的最大长度typedef struct ｛int dataMAX_SIZE; ／／存储线性表元素的数组int length; ／／线性表的当前长度｝ SeqList;｀｀｀2、初始化线性表｀｀｀cppvoid InitList(SeqList L) ｛L>length ＝ 0; ／／初始时线性表长度为 0｝｀｀｀3、判断线性表是否为空｀｀｀cppbool ListEmpty(SeqList L) ｛return （Llength ＝＝ 0)；｝｀｀｀4、求线性表的长度｀｀｀cppint ListLength(SeqList L) ｛return Llength;｝｀｀｀5、按位查找操作｀｀｀cppint GetElem(SeqList L, int i) ｛if （i ＜ 1 ｜｜ i ＞ Llength) ｛printf(＂查找位置不合法!＼n"）；return －1;｝return Ldatai 1;｝｀｀｀6、按值查找操作｀｀｀cppint LocateElem(SeqList L, int e) ｛for （int i ＝ 0; i ＜ Llength; i+＋）｛if （Ldatai ＝＝ e) ｛return i ＋ 1;｝｝return 0; ／／未找到返回 0｝｀｀｀7、插入操作｀｀｀cppbool ListInsert(SeqList L, int i, int e) ｛if （L>length ＝＝ MAX_SIZE) ｛／／表已满printf(＂表已满，无法插入!＼n"）；return false;｝if （i ＜ 1 ｜｜ i ＞ L>length ＋ 1) ｛／／插入位置不合法printf(＂插入位置不合法!＼n"）；return false;｝for （int j ＝ L>length; j ＞＝ i; j) ｛／／移动元素L>dataj ＝ L>dataj 1;｝L>datai 1 ＝ e; ／／插入元素L>length+＋；／／表长加 1return true;｝｀｀｀8、删除操作｀｀｀cppbool ListDelete(SeqList L, int i) ｛if （L>length ＝＝ 0) ｛／／表为空printf(＂表为空，无法删除!＼n"）；return false;｝if （i ＜ 1 ｜｜ i ＞ L>length) ｛／／删除位置不合法printf(＂删除位置不合法!＼n"）；return false;｝for （int j ＝ i; j ＜ L>length; j+＋）｛／／移动元素L>dataj 1 ＝ L>dataj;｝L>length; ／／表长减 1return true;｝｀｀｀9、输出线性表｀｀｀cppvoid PrintList(SeqList L) ｛for （int i ＝ 0; i ＜ Llength; i+＋）｛printf(＂％d ＂， Ldatai)；｝printf(＂＼n"）；｝｀｀｀10、测试用例｀｀｀cppint main(）｛SeqList L;InitList(＆L)；ListInsert(＆L, 1, 10)；ListInsert(＆L, 2, 20)；ListInsert(＆L, 3, 30)；ListInsert(＆L, 4, 40)；ListInsert(＆L, 5, 50)；printf(＂线性表的长度为：％d\n"， ListLength(L)）；printf(＂查找第 3 个元素：％d\n"， GetElem(L, 3)）；int loc ＝ LocateElem(L, 30)；if （loc) ｛printf(＂元素 30 的位置为：％d\n"， loc)；｝ else ｛printf(＂未找到元素 30\n"）；｝ListDelete(＆L, 3)；printf(＂删除第 3 个元素后的线性表：＂）；PrintList(L)；return 0;｝｀｀｀五、实验结果及分析1、实验结果成功创建并初始化了线性表。

824-计算机基础考试大纲计算机基础包括数据结构、计算机网络两部分内容，每部分内容各占1/2。

I 数据结构课程基本要求：数据结构是在计算机科学中是一门综合性的专业基础课。

课程主要内容包括线性表、栈和队列、串、数组和广义表、树和二叉树、图、内排序、文件管理和外排序等。

考试的具体要求包括：1. 全面系统地掌握队列、堆、栈、树、图等基本数据结构，深刻理解和熟练掌握课程中的典型算法；2. 提高对各种数据结构与算法的程序设计能力，提高对数据结构与算法的实际运用能力。

考试内容：1. 线性表1.1. 线性表的类型定义1.2. 线性表的顺序表示与实现1.3. 线性表的链式表示与实现2. 栈和队列2.1. 栈的定义与实现2.2. 栈与递归的实现2.3. 队列的定义与实现3. 串3.1. 串的定义与实现3.2. 串的模式匹配算法4. 数组和广义表4.1. 数组的定义与实现4.2. 矩阵的压缩存储4.3. 广义表的定义与实现4.4. 广义表的递归算法5. 树和二叉树5.1. 树的定义和基本术语5.2. 二叉树的定义、性质和存储结构5.3. 遍历二叉树和线索二叉树5.4. 树和森林5.5. 赫夫曼树及其应用5.6. 回溯法与树的遍历6. 图6.1. 图的定义和术语6.2. 图的存储结构6.3. 图的遍历6.4. 最短路径7. 动态存储管理7.1. 边界标识法7.2. 伙伴系统7.3. 存储紧缩8. 查找8.1. 静态查找表8.2. 动态查找表8.3. 哈希表9. 内部排序9.1. 内部排序算法，插入排序、快速排序、选择排序、归并排序和基数排序等9.2. 内部排序算法的比较10. 外部排序10.1. 外存信息的存取10.2. 多路平衡归并的实现10.3. 选择排序10.4. 最佳归并树11. 文件11.1. 有关文件的基本概念11.2. 顺序文件与索引文件11.3. 直接存取文件（散列文件）11.4. 多关键字文件参考书目：1.《数据结构（C语言版）》作者：严蔚敏，吴伟民出版社：清华大学出版社ISBN：97873020236852.《数据结构与算法》作者：张铭，王腾蛟，赵海燕出版社：高等教育出版社ISBN：9787040239614II 计算机网络课程基本要求1.掌握计算机网络的基本概念、基本原理和基本方法。