《数据结构》实验报告模板附实例实验一线性表的基本操作实现.doc

《数据结构》-实验报告1-CAL-FENGHAI.-(YICAI)-Company One1xxx 实验报告一、实验目的1.熟悉上机环境，进一步掌握语言的结构特点。

2.掌握线性表的顺序存储结构的定义及实现。

3.掌握线性表的链式存储结构——单链表的定义及实现。

4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。

5.掌握线性表在链式存储结构——单链表中的各种基本操作。

二、实验内容1.顺序线性表的建立、插入及删除。

2.链式线性表的建立、插入及删除。

三、实验步骤1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。

2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。

3.建立一个带头结点的单链表，结点的值域为整型数据。

要求将用户输入的数据按尾插入法来建立相应单链表。

四、程序主要语句及作用1)程序1的主要代码(附简要注释)#include<iostream>using namespace std;#define MAXSIZE 1024//#define OVERFLOW 0//#define NULL 0#define OK 1#define MAXSIZE 1024typedef int elemtype; /* 线性表中存放整型元素 */typedef struct //结构定义头文件sqlist.h{ elemtype vec[MAXSIZE];int len; /* 顺序表的长度 */}sqlist;int initlist(sqlist *L,int k){ int i;printf("Input the list:");for( i=0;i<k;i++)scanf("%d", &L->vec[i]);//cin>>L->vec[i];同效,注意输入时地址"&"return OK;}// 以下是整个源程序：#include"sqlist.h"int main(){ int i,n;sqlist *L,a; //定义表的变量printf("\n Input the length of the list L:\n");scanf("%d",&n);L=&a; //指针引用,如果去掉L=&a语句，会出现什么结果？L->len=n; //将长度传给leninitlist(L,n);printf("Output the list and its length:\n");for(i=0;i<n;i++)printf("%d ", L->vec[i]);printf("\nThis sqlist's length is %d", L->len);system("pause");return 0;}2)程序2的主要代码(附简要注释)/*顺序表的插入利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}然后在第i个位置插入元素68。

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

《数据结构》实验报告模板(附实例)---实验一线性表的基本操作实现实验一线性表的基本操作实现及其应用一、实验目的1、熟练掌握线性表的基本操作在两种存储结构上的实现，其中以熟悉各种链表的操作为重点。

2、巩固高级语言程序设计方法与技术，会用线性链表解决简单的实际问题。

二、实验内容√ 1、单链表的表示与操作实现 ( * )2、约瑟夫环问题3、Dr.Kong的艺术品三、实验要求1、按照数据结构实验任务书，提前做好实验预习与准备工作。

2、加“*”题目必做，其他题目任选；多选者并且保质保量完成适当加分。

3、严格按照数据结构实验报告模板和规范，及时完成实验报告。

四、实验步骤（说明：依据实验内容分别说明实验程序中用到的数据类型的定义、主程序的流程以及每个操作（成员函数）的伪码算法、函数实现、程序编码、调试与分析、总结、附流程图与主要代码）㈠、数据结构与核心算法的设计描述（程序中每个模块或函数应加注释，说明函数功能、入口及出口参数）1、单链表的结点类型定义/* 定义DataType为int类型 */typedef int DataType;/* 单链表的结点类型 */typedef struct LNode{ DataType data;struct LNode *next;}LNode,*LinkedList;2、初始化单链表LinkedList LinkedListInit( ){ // 每个模块或函数应加注释，说明函数功能、入口及出口参数 }3、清空单链表void LinkedListClear(LinkedList L){// 每个模块或函数应加注释，说明函数功能、入口及出口参数}4、检查单链表是否为空int LinkedListEmpty(LinkedList L){ …. }5、遍历单链表void LinkedListTraverse(LinkedList L){….}6、求单链表的长度int LinkedListLength(LinkedList L){ …. }7、从单链表表中查找元素LinkedList LinkedListGet(LinkedList L,int i){ //L是带头结点的链表的头指针，返回第 i 个元素 }8、从单链表表中查找与给定元素值相同的元素在链表中的位置LinkedList LinkedListLocate(LinkedList L, DataType x){ …… }9、向单链表中插入元素void LinkedListInsert(LinkedList L,int i,DataType x) { // L 为带头结点的单链表的头指针，本算法// 在链表中第i 个结点之前插入新的元素 x}10、从单链表中删除元素void LinkedListDel(LinkedList L,DataType x){ // 删除以 L 为头指针的单链表中第 i 个结点 }11、用尾插法建立单链表LinkedList LinkedListCreat( ){ …… }㈡、函数调用及主函数设计（可用函数的调用关系图说明）㈢程序调试及运行结果分析㈣实验总结五、主要算法流程图及程序清单1、主要算法流程图：2、程序清单（程序过长，可附主要部分）说明：以后每次实验报告均按此格式书写。

1、实验目的本实验旨在通过实际操作和代码编写，掌握数据结构的基本概念、常用算法和数据结构的应用能力。

2、实验内容2.1 实验一、线性表的基本操作2.1.1 实验介绍在本实验中，我们将实现线性表的基本操作，包括初始化线性表、插入元素、删除元素、查找元素等。

通过这些基本操作的实现，我们可以加深对线性表的理解。

2.1.2 实验步骤步骤一、初始化线性表步骤二、插入元素步骤三、删除元素步骤四、查找元素2.2 实验二、栈的应用——括号匹配2.2.1 实验介绍在本实验中，我们将使用栈来实现括号匹配。

通过这个应用实例，我们可以更好地理解栈的特性和应用场景。

2.2.2 实验步骤步骤一、括号匹配算法的实现步骤二、测试括号匹配算法3、实验结果与分析3.1 实验一结果分析3.1.1 初始化线性表的效率分析3.1.2 插入操作的效率分析3.1.3 删除操作的效率分析3.1.4 查找操作的效率分析3.2 实验二结果分析3.2.1 括号匹配算法的验证3.2.2 算法的时间复杂度分析3.2.3 算法的空间复杂度分析4、实验总结通过本次实验，我们进一步了解了数据结构的基本概念和应用。

我们通过实际操作和代码编写，加深了对线性表和栈的理解，并且掌握了相关算法的实现和分析方法。

5、附件本实验报告涉及的附件包括：- 代码实现文件- 实验数据统计表格6、法律名词及注释在本文档中，涉及的法律名词和注释包括：- 数据结构：指在计算机科学中，我们用来组织和存储数据的方式或格式。

- 线性表：是最基本、最简单、也是最常用的一种数据结构。

线性表中的数据元素之间是一对一的关系。

- 栈：是一种特殊的线性表，它的插入和删除操作只能在同一端进行。

后进先出（Last In First Out，LIFO）是栈的特性之一。

- 括号匹配：是指检查一个字符串中的所有括号是否匹配完整的过程。

学《数据结构》课程实验报告实验名称：线性表基本操作的实现实验室(中心)：学生信息：专业班级：指导教师：实验完成时间： 2016实验一线性表基本操作的实现一、实验目的1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。

2.掌握线性表的顺序存储结构的定义及C语言实现。

3.掌握线性表的链式存储结构——单链表的定义及C语言实现。

4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。

5.掌握线性表在链式存储结构——单链表中的各种基本操作。

二、实验内容及要求1.顺序线性表的建立、插入、删除及合并。

2.链式线性表的建立、插入、删除及连接。

三、实验设备及软件计算机、Microsoft Visual C++ 6.0软件四、设计方案（算法设计）㈠采用的数据结构本程序顺序表的数据逻辑结构为线性结构，存储结构为顺序存储；链表的数据逻辑结构依然为线性结构，存储结构为链式结构。

㈡设计的主要思路1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度，顺序表的长度和元素由用户输入；2.利用前面建立的顺序表，对顺序表进行插入、删除及合并操作；3.建立一个带头结点的单链表，结点的值域为整型数据，链表的元素由用户输入；4.对前面建立的链表进行插入、删除及连个链表的连接操作；㈢算法描述1、顺序表void Init(sqlist &);//初始化顺序表BOOL Inse(sqlist &,int,char); //在线性表中插入元素BOOL del(sqlist&,int,char &); //在线性表中删除元素int Loc(sqlist,char); //在线性表中定位元素void print(sqlist); //输出顺序表void combine( sqlist & , sqlist & , sqlist &);//两个线性表的合并2、链表void CreaL(LinkList &,int); //生成一个单链表BOOL LInsert(LinkList &,int,char); //在单链表中插入一个元素BOOL LDele(LinkList &,int,char &); //在单链表中删除一个元素BOOL LFind_key(LinkList,char,int &); //按关键字查找一个元素BOOL LFind_order(LinkList,char &,int); //按序号查找一个元素void LPrint(LinkList); //显示单链表所有元素void LUnion(LinkList &,LinkList &,LinkList &,int); //两个链表的连接五、程序代码1、顺序表#include <stdio.h>#include <conio.h>#define Max 116enum BOOL{False,True};typedef struct{char elem[Max]; //线性表int last; //last指示当前线性表的长度}sqlist;void Init(sqlist &);BOOL Inse(sqlist &,int,char); //在线性表中插入元素BOOL del(sqlist&,int,char &); //在线性表中删除元素int Loc(sqlist,char); //在线性表中定位元素void print(sqlist);void combine( sqlist & , sqlist & , sqlist &);void main(){sqlist L1;sqlist L2;sqlist L3;int loc,S=1;char j,ch;BOOL temp;printf("本程序用来实现顺序结构的线性表。

数据结构..实验报告线性表的基本操作数据结构实验报告线性表的基本操作1.引言本实验报告旨在介绍线性表的基本操作。

线性表是一种常见的数据结构，它是一组有限元素的有序集合，其中每个元素之间存在一个特定的顺序关系。

线性表的操作包括插入、删除、查找等，这些操作对于有效地管理和利用数据非常重要。

2.实验目的本实验的目的是通过实践理解线性表的基本操作，包括初始化、插入、删除、查找等。

通过编写相应的代码，加深对线性表的理解，并掌握相应的编程技巧。

3.实验内容3.1 初始化线性表初始化线性表是指创建一个空的线性表，为后续的操作做准备。

初始化线性表的方法有多种，如顺序表和链表等。

下面以顺序表为例进行说明。

顺序表的初始化包括定义表头指针和设置表的长度等操作。

3.2 插入元素插入元素是指将一个新的元素插入到线性表的指定位置。

插入元素有两种情况：插入到表的开头和插入到表的中间。

插入元素的操作包括移动其他元素的位置以腾出空间，并将新的元素插入到指定位置。

3.3 删除元素删除元素是指将线性表中的某个元素删除。

删除元素有两种情况：删除表的开头元素和删除表的中间元素。

删除元素的操作包括将被删除元素的前一个元素与后一个元素进行连接，断开被删除元素与表的联系。

3.4 查找元素查找元素是指在线性表中寻找指定的元素。

查找元素的方法有多种，如遍历线性表、二分查找等。

查找元素的操作包括比较目标元素与线性表中的元素进行匹配，直到找到目标元素或遍历完整个线性表。

4.实验步骤4.1 初始化线性表根据线性表的类型选择相应的初始化方法，如创建一个空的顺序表并设置表的长度。

4.2 插入元素输入要插入的元素值和插入的位置，判断插入的位置是否合法。

如果合法，移动其他元素的位置以腾出空间，将新的元素插入到指定位置。

如果不合法，输出插入位置非法的提示信息。

4.3 删除元素输入要删除的元素值，判断元素是否在线性表中。

如果在，则找到目标元素的前一个元素和后一个元素，进行连接删除操作。

数据结构--实验报告线性表的基本操作数据结构--实验报告线性表的基本操作一、引言本实验报告旨在通过实际操作，掌握线性表的基本操作，包括初始化、插入、删除、查找等。

线性表是最基本的数据结构之一，对于理解和应用其他数据结构具有重要的作用。

二、实验目的1·了解线性表的定义和基本特性。

2·掌握线性表的初始化操作。

3·掌握线性表的插入和删除操作。

4·掌握线性表的查找操作。

5·通过实验巩固和加深对线性表的理解。

三、线性表的基本操作1·初始化线性表线性表的初始化是将一个线性表变量设置为空表的过程。

具体步骤如下：（1）创建一个线性表的数据结构，包括表头指针和数据元素的存储空间。

（2）将表头指针指向一个空的数据元素。

2·插入元素插入元素是向线性表中指定位置插入一个元素的操作。

具体步骤如下：（1）判断线性表是否已满，如果已满则无法插入元素。

（2）判断插入位置是否合法，如果不合法则无法插入元素。

（3）将插入位置及其后面的元素都向后移动一个位置。

（4）将待插入的元素放入插入位置。

3·删除元素删除元素是从线性表中删除指定位置的元素的操作。

具体步骤如下：（1）判断线性表是否为空，如果为空则无法删除元素。

（2）判断删除位置是否合法，如果不合法则无法删除元素。

（3）将删除位置后面的元素都向前移动一个位置。

（4）删除最后一个元素。

4·查找元素查找元素是在线性表中查找指定元素值的操作。

具体步骤如下：（1）从线性表的第一个元素开始，逐个比较每个元素的值，直到找到目标元素或遍历完整个线性表。

（2）如果找到目标元素，则返回该元素的位置。

（3）如果未找到目标元素，则返回找不到的信息。

四、实验步骤1·初始化线性表（1）定义线性表的数据结构，包括表头指针和数据元素的存储空间。

（2）将表头指针指向一个空的数据元素。

2·插入元素（1）判断线性表是否已满。

数据结构--实验报告线性表的基本操作数据结构实验报告[引言]在本次实验中,我们将学习线性表的基本操作,包括插入、删除、查找等。

通过实践操作,加深对线性表的理解和掌握。

[实验目的]1．学习线性表的基本概念和操作。

2.熟悉线性表的插入、删除和查找等基本操作。

3.掌握线性表的实现方式及其相应的算法。

［实验内容]１.线性表的定义与表示1．1 线性表的定义1.2 线性表的顺序存储结构１.3 线性表的链式存储结构2.线性表的基本操作２．１初始化线性表2.２判断线性表是否为空2.3 插入操作２.3.1 在指定位置插入元素2.3.2 在表尾插入元素2．4 删除操作2．4.1 删除指定位置的元素2．４．2 删除指定值的元素2．5 查找操作2.5.1 按位置查找元素2．5.2 按值查找元素２．6 修改操作2．６．１修改指定位置的元素 2.6.2 修改指定值的元素2.7 清空线性表2．8 销毁线性表[实验步骤]1.初始化线性表1.1 创建一个空的线性表对象１.2 初始化线性表的容量和长度2.插入操作2.１在指定位置插入元素2.1.1 检查插入位置的合法性2.1.2 将插入位置后的元素依次后移2.1．３在指定位置插入新元素2.2 在表尾插入元素２.2．1 将表尾指针后移2.2.2 在表尾插入新元素３.删除操作3.1 删除指定位置的元素３.1.1 检查删除位置的合法性3.１．2 将删除位置后的元素依次前移3.1.3 修改线性表的长度3.2 删除指定值的元素3.2.1 查找指定值的元素位置3.２.２调用删除指定位置的元素操作4.查找操作４.1 按位置查找元素4．1．1 检查查找位置的合法性4.1.2 返回指定位置的元素4.2 按值查找元素4.2．1 从头到尾依次查找元素4.2．2 返回第一个匹配到的元素5.修改操作5.１修改指定位置的元素５.１.1 检查修改位置的合法性5.1.２修改指定位置的元素值5.２修改指定值的元素5.2．1 查找指定值的元素位置5．２．２调用修改指定位置的元素操作6.清空线性表6．1 设置线性表长度为07.销毁线性表７.1 释放线性表的内存空间[实验结果]使用线性表进行各种基本操作的测试,并记录操作的结果和运行时间。

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

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

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

我们选择使用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.实验目的1.掌握线性表的插入和删除操作。

2.理解线性表的查找和修改元素的方法。

3.熟悉线性表的基本操作在算法中的应用。

3.实验环境本实验使用编程语言/软件名称作为开发环境，具体要求如下：________●操作系统：________操作系统名称和版本●编程语言：________编程语言名称和版本4.实验步骤4.1 初始化线性表在程序中创建一个空的线性表，用于存储元素。

实现方法：________具体的初始化方法和代码示例 4.2 插入元素在线性表中指定位置插入一个新元素。

实现方法：________具体的插入元素方法和代码示例 4.3 删除元素删除线性表中指定位置的元素。

实现方法：________具体的删除元素方法和代码示例 4.4 查找元素在线性表中查找指定元素的位置。

实现方法：________具体的查找元素方法和代码示例 4.5 修改元素修改线性表中指定位置的元素值。

实现方法：________具体的修改元素方法和代码示例5.实验结果在完成上述步骤后，我们得到了一个可以进行插入、删除、查找和修改元素的线性表。

具体操作结果如下：________●插入元素操作结果：________插入元素的具体操作结果●删除元素操作结果：________删除元素的具体操作结果●查找元素操作结果：________查找元素的具体操作结果●修改元素操作结果：________修改元素的具体操作结果6.实验总结通过本次实验，我们深入理解了线性表的基本操作，并且掌握了这些操作的实现方法。

线性表在实际应用中十分常见，熟练掌握线性表的操作对于开发高效的算法和数据结构具有重要意义。

1.实验目的本实验的目的是通过实际操作、设计和分析数据结构的基本概念和算法，提高学生对数据结构的理解和应用能力。

2.实验背景在计算机科学与技术领域，数据结构是一种组织和存储数据的方式，它可以提高数据的访问效率和操作速度。

了解和熟练掌握数据结构的概念、原理和应用，对于计算机相关专业学生来说至关重要。

3.实验内容3.1 实验一：线性表的操作3.1.1 实验目标了解线性表的基本概念和操作，并能够编写对应的代码。

3.1.2 实验步骤a.实现线性表的基本操作，包括插入、删除、查找等。

b.分析并比较不同线性表实现方式的优缺点。

c.进行相关实验并记录结果。

3.1.3 实验结论通过本次实验，我加深了对线性表的理解，并了解了不同实现方式的差异。

3.2 实验二：栈和队列的应用3.2.1 实验目标了解栈和队列的基本概念和应用，掌握它们的各种操作。

3.2.2 实验步骤a.实现栈和队列的基本操作，如入栈、出栈、入队、出队等。

b.进行相关实验，验证栈和队列的应用场景。

3.2.3 实验结论通过本次实验，我深入了解了栈和队列的应用，并通过实验验证了它们的有效性。

4.实验结果与分析在实验过程中，我们通过对数据结构的操作和应用，得出了一系列实验结果并进行了相关分析。

这些结果对我们理解和应用数据结构起到了重要的作用。

5.实验总结与体会通过完成本次实验，我对数据结构的相关概念和应用有了更加深入的了解。

同时，在实验中我不仅掌握了相应的编程技巧，还培养了解决问题的能力和团队合作精神。

6.附件本文档附上了实验过程中所使用的代码、实验结果截图等相关附件，供参考和进一步研究使用。

7.法律名词及注释在本文档中涉及的法律名词及其注释如下：●版权：指作为文学、艺术和科学的创作成果的智力财产权。

●专利：指发明者对新发明所拥有的独占权。

●商标：指用于区别商品和服务来源的标识符，如商标、服务标志等。

数据结构_实验1_线性表的基本操作在计算机科学中，数据结构是组织和存储数据的方式，以便能够高效地进行访问、修改和操作。

线性表是一种常见且基础的数据结构，它就像是一个有序的元素队列。

在本次实验 1 中，我们将深入探索线性表的基本操作，理解其背后的原理和实现方式。

线性表可以分为顺序表和链表两种常见的实现方式。

顺序表是将元素存储在连续的内存空间中，而链表则是通过节点之间的链接来存储元素。

首先，让我们来看看顺序表的基本操作。

顺序表的优点是可以通过下标直接访问元素，时间复杂度为 O(1)。

比如，如果我们要获取顺序表中第 5 个元素的值，只需要通过下标 4 就可以快速得到。

但在插入和删除元素时，情况就变得复杂一些。

如果要在顺序表的中间插入一个元素，就需要将插入位置后面的元素依次向后移动，以腾出空间插入新元素。

这一操作的时间复杂度为 O(n)，其中 n 是顺序表的长度。

同样，删除中间的元素时，也需要将后面的元素依次向前移动。

接下来，我们再聊聊链表。

链表中的每个节点包含数据域和指针域。

指针域用于指向下一个节点，从而形成链表的链接结构。

在链表中进行插入和删除操作相对简单，只需要修改相关节点的指针即可，时间复杂度通常为 O(1)。

然而，要访问链表中的特定元素，就需要从链表的头节点开始，沿着指针依次遍历，直到找到目标节点，其时间复杂度为 O(n)。

在实验中，我们实现了线性表的创建操作。

对于顺序表，我们首先确定其初始容量，然后分配相应的连续内存空间。

对于链表，我们创建一个头节点，并初始化其指针域为 NULL。

接着是元素的插入操作。

在顺序表中，如果插入位置合法且还有剩余空间，我们将插入位置后面的元素向后移动，然后将新元素插入指定位置。

在链表中，我们根据插入位置找到前一个节点，然后创建新节点并修改指针链接。

元素的删除操作也是重点之一。

对于顺序表，删除指定位置的元素后，将后面的元素依次向前移动。

而在链表中，找到要删除节点的前一个节点，修改指针跳过要删除的节点。

《数据结构》实验报告一数据结构实验报告一引言：数据结构是计算机科学中非常重要的一门课程，它研究数据的组织方式和操作方法，为解决实际问题提供了基础。

本实验报告将介绍我在学习《数据结构》课程中进行的第一次实验，主要涉及线性表的顺序存储结构和链式存储结构的实现与比较。

一、实验目的本次实验的目的是通过编写代码实现线性表的顺序存储结构和链式存储结构，并对两种存储结构进行比较，分析它们的优缺点。

二、实验内容1. 线性表的顺序存储结构实现顺序存储结构是将线性表的元素按照其逻辑次序依次存放在一组连续的存储单元中。

我通过定义一个具有固定大小的数组，利用数组下标来表示元素的逻辑次序，实现了线性表的顺序存储结构。

2. 线性表的链式存储结构实现链式存储结构是通过指针将线性表的元素存储在不连续的存储单元中，每个元素包含一个数据域和一个指针域，指针域指向下一个元素。

我定义了一个节点结构体，通过创建节点之间的指针关系，实现了线性表的链式存储结构。

三、实验结果与分析1. 顺序存储结构的优点：a. 存储密度高，不需要额外的指针域，节省存储空间；b. 随机访问元素方便，时间复杂度为O(1)。

2. 顺序存储结构的缺点：a. 插入和删除元素时需要移动其他元素，时间复杂度为O(n)；b. 存储空间固定，容量不易扩展。

3. 链式存储结构的优点：a. 插入和删除元素时只需改变指针域，时间复杂度为O(1)；b. 存储空间可以动态分配，容量易于扩展。

4. 链式存储结构的缺点：a. 存储密度低，需要额外的指针域，占用更多的存储空间；b. 随机访问元素不方便，时间复杂度为O(n)。

通过对比分析，我们可以根据实际需求选择适合的存储结构。

如果需要频繁进行插入和删除操作，链式存储结构更为合适；如果需要频繁进行随机访问操作，顺序存储结构更为合适。

四、实验总结通过本次实验，我深入理解了线性表的顺序存储结构和链式存储结构的实现原理和优缺点。

在实际编程中，根据不同的需求选择合适的存储结构非常重要。

数据结构实验报告实验名称: 实验一线性表学生姓名:班级:班内序号:学号:1．日期: 2013年11月7日2．实验要求①实验目的:➢通过选择下面四个题目之一进行实现, 掌握如下内容:➢熟悉C++语言的基本编程方法, 掌握集成编译环境的调试方法➢学习指针、模板类、异常处理的使用➢掌握线性表的操作的实现方法➢学习使用线性表解决实际问题的能力②实验要求:1、线性表存储结构（五选一）:2、带头结点的单链表3、不带头结点的单链表4、循环链表5、双链表6、静态链表1、线性表的基本功能:2、构造: 使用头插法、尾插法两种方法3、插入: 要求建立的链表按照关键字从小到大有序4、删除5、查找6、获取链表长度7、销毁其他: 可自行定义编写测试main()函数测试线性表的正确性。

③代码要求:➢ 1.必须要有异常处理, 比如删除空链表时需要抛出异常；➢2、保持良好的编程的风格:➢代码段与段之间要有空行和缩近➢标识符名称应该与其代表的意义一致➢函数名之前应该添加注释说明该函数的功能➢关键代码应说明其功能2.程序分析2.1 存储结构存储结构为单链表, 示意图:2.2 关键算法分析（1）关键算法:（2）头插法每次插入元素都从单链表的第一个结点位置插入, 先前插入的结点随着新结点插入而不断后移。

执行过程:在堆中建立新结点: Node*s=new Node;②将a[i]写入到新结点的数据域: s->data=a[i];③修改新结点的指针域: s->next=front->next；（3）④修改头结点的指针域, 将新结点加入到链表中：front->next=s;（4）尾插法每次新插入的元素都在单链表的表尾。

通常尾插法需要一个指针变量保存终端结点的地址, 成为尾指针, 设为r。

每插入一个结点后, r指向新插入的终端结点。

步骤：在堆中建立新结点: Node*s=new Node;②将a[i]写入到新结点的数据域: s->data=a[i];③将新结点加入到链表中: r->next=s;（5）④修改尾指针: r=s；（6）按位查找获取单链表第i个位置上的元素其结点地址。

数据结构实验报告--实验一、线性表的实现线性表是常用的数据结构之一，其中最常用的是顺序存储结构。

本实验使用C语言实现了顺序存储结构的线性表。

首先，定义了一个结构体来表示线性表：```#define MAXSIZE 100 //线性表最大长度typedef struct {int data[MAXSIZE]; //存放线性表元素int length; //线性表当前长度} SqList; //线性表类型定义```其中，data数组存放线性表元素，length表示线性表当前长度。

接着，定义了三个基本操作：1. 初始化线性表```void InitList(SqList *L) {L->length = 0;}```2. 插入元素```bool ListInsert(SqList *L, int i, int e) {if (i < 1 || i > L->length + 1) { //插入位置不合法}if (L->length >= MAXSIZE) { //线性表已满return false;}for (int j = L->length; j >= i; j--) { //将第i个位置之后的所有元素后移一位L->data[j] = L->data[j - 1];}L->data[i - 1] = e; //将元素e插入到第i个位置L->length++; //线性表长度加1return true;}```3. 删除元素以上三个操作就是线性表的基本操作，通过这三个操作就能完成线性表的所有操作。

实验二、栈和队列的实现2.1 栈的实现栈是一种后进先出(Last In First Out)的数据结构。

我们可以用线性表来实现栈，只需要对线性表的插入和删除操作进行限制就行了。

具体实现如下：void InitStack(Stack *S) {S->top = -1; //初始化栈顶指针}bool Push(Stack *S, int e) {if (S->top == STACK_SIZE - 1) { //栈已满，无法插入元素}S->top++; //栈顶指针加1S->data[S->top] = e; //插入元素e到栈顶return true;}以上代码实现了栈的初始化、入栈和出栈操作。

实验目的实验内容和要求源代码顺序表的代码单链表的代码测试结果顺序表的测试结果单链表的测试结果五、心得体会实验一线性表的基本操作及其应用一、实验目的1.帮助读者复习C++语言程序设计中的知识。

2.熟悉线性表的逻辑结构。

3.熟悉线性表的基本运算在两种存储结构上的实现。

4.掌握顺序表的存储结构形式及其描述和基本运算的实现。

5.熟练掌握动态链表结构及有关算法的设计二、实验内容题目一: 顺序表的基本操作[问题描述]实现顺序表的建立、求长度, 取元素、修改元素、插入、删除等顺序表的基本操作。

[基本要求]（1）依次从键盘读入数据, 建立带头结点的顺序表；（2）输出顺序表中的数据元素（3）求顺序表的长度；（4）根据指定条件能够取元素和修改元素；（5）实现在指定位置插入和删除元素的功能。

（6）根据算法, 将两个有序的顺序表合并成一个有序顺序表。

[测试数据] 由学生任意指定。

题目二: 单链表的基本操作[问题描述]实现带头结点的单链表的建立、求长度, 取元素、修改元素、插入、删除等单链表的基本操作。

[基本要求]（1）依次从键盘读入数据, 建立带头结点的单链表；（2）输出单链表中的数据元素（3）求单链表的长度；（4）根据指定条件能够取元素和修改元素；（5）实现在指定位置插入和删除元素的功能。

（6）根据算法, 将两个有序的单链表合并成一个有序单链表。

[测试数据]由学生任意指定。

三、源代码顺序表的基本操作#include<iostream>using namespace std;#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int ElemType;#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct { //结构体ElemType *elem;int length;int listsize;}SqList;SqList Lx;Status InitList_Sq(SqList &L) //分配空间{ L.elem=new ElemType[LIST_INIT_SIZE];if(!L.elem)exit(OVERFLOW);L.length =0;L.listsize=LIST_INIT_SIZE;return OK;}Status ListInsert(SqList &L,int i,ElemType e) //插入新元素{ int *q,*p;ElemType *newbase;if(i<1 || i>L.length+1) return ERROR;if(L.length>=L.listsize){ newbase=new ElemType[L.listsize+LISTINCREMENT];if(!newbase) exit(OVERFLOW);L.elem=newbase;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;}Status Listlength(SqList L) //长度{ int *p=L.elem; //判断线形表是否存在while(p){ return (L.length); }}Status GetElem(SqList L, int i,ElemType &e) //取元素{ if(i<1 || i>L.length)return ERROR;else{ e=L.elem[i-1];return e;}}void MergeList(SqList La,SqList Lb,SqList &Lc) //合并{ ElemType ai,bj;InitList_Sq(Lc);int i=1,j=1,k=0;int La_len,Lb_len;La_len=Listlength(La);Lb_len=Listlength(Lb);while((i<=La_len)&&(j<=Lb_len)){ GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ ListInsert(Lc,++k,ai);++i; }else{ ListInsert(Lc,++k,bj);++j; }}while(i<=La_len){ GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){ GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}void show(SqList L,int i) //显示{ int j;ElemType k;cout<<"顺序表显示如下:"<<endl;for(j=0;j<i-1;j++){ k=L.elem[j];cout<<k<<"->"; }if(j==i-1 && i>0){ k=L.elem[j]; cout<<k; }cout<<endl;}void create(SqList &L,int n) //输入元素{ int e;for(int i=0;i<n;i++){ cin>>e;L.elem[i]=e;L.length=i+1; }}Status ListDelete_Sq(SqList &L,int i,ElemType &e) //删除{ ElemType *p, *q;if(i<1 || i>L.length) return ERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p<=q;++p) *(p-1)=*p;--L.length;return OK;}Status Listxiugei(SqList &L,int i,ElemType &e) //修改{ if(i<1 || i>L.length)return ERROR;else{ L.elem[i-1]=e;return OK; }}void shuru(SqList &L1) //顺序表的创建{ int a;InitList_Sq(L1);cout<<"请输入顺序表的长度: ";cin>>a;cout<<"请输入顺序表的元素(共"<<a<<"个)"<<endl;create(L1,a);show(L1,a);}void chaxun(SqList &L1) //取第i个位置的元素{ int j;ElemType e1;cout<<"请选择所要取出元素的位置:";cin>>j;while(j<0||j>Listlength(L1)){ cout<<"输入有误, 请重新输入"<<endl;cout<<"请选择所要取出元素的位置:";cin>>j; }GetElem(L1,j,e1);cout<<"取出的元素为:"<<e1<<endl; }void xiugai(SqList &L1) //修改第i个位置的元素{ int a;int j; ElemType e1;a=L1.length;cout<<"请选择所要修改元素的位置:";cin>>j;while(j<0||j>Listlength(L1)){ cout<<"输入有误, 请重新输入"<<endl;cout<<"请选择所要修改元素的位置:";cin>>j; }cout<<"要修改成的元素:";cin>>e1;Listxiugei(L1,j,e1);cout<<"修改后的顺序表数据:"<<endl;show(L1,a);}void shanchu(SqList &L1) //删除顺序表里的元素{ int a;int j; ElemType e1;a=L1.length;cout<<"请选择所要删除元素的位置:";cin>>j;while(j<0||j>Listlength(L1)){ cout<<"输入有误, 请重新输入"<<endl;cout<<"请选择所要删除元素的位置:";cin>>j; }ListDelete_Sq(L1,j,e1);cout<<"修改后的顺序表数据:"<<endl;show(L1,a-1);}void charu(SqList &L1) //插入元素到顺序表里{ int a; int j; ElemType e1;a=L1.length;cout<<"请选择所要插入元素的位置:";cin>>j;while(j<0||j>Listlength(L1)){ cout<<"输入有误, 请重新输入"<<endl;cout<<"请选择所要插入元素的位置:";cin>>j; }cout<<"要插入的元素:";cin>>e1;ListInsert(L1,j,e1);cout<<"修改后的顺序表数据:"<<endl;show(L1,a+1);}void hebing(SqList &L3) //合并两个顺序表{ SqList L1,L2;int a,b;InitList_Sq(L1); InitList_Sq(L2);cout<<"请输入第一个有序表的长度: "; cin>>a;cout<<"请输入第一个有序表的元素(共"<<a<<"个)"<<endl;create(L1,a);show(L1,a);cout<<"请输入第二个有序表的长度: "; cin>>b;cout<<"请输入第二个有序表的元素(共"<<b<<"个)"<<endl;create(L2,b);show(L2,b);MergeList(L1,L2,L3);cout<<"合并后的有序表如下: "; show(L3,a+b);}void main() //主菜单{ int choice;for(;;){ cout<<" 顺序表的基本操作"<<endl;cout<<" 1.顺序表的创建"<<endl;cout<<" 2.顺序表的显示"<<endl;cout<<" 3.顺序表的长度"<<endl;cout<<" 4.取第i个位置的元素"<<endl;cout<<" 5.修改第i个位置的元素"<<endl;cout<<" 6.插入元素到顺序表里"<<endl;cout<<" 7.删除顺序表里的元素"<<endl;cout<<" 8.合并两个顺序表"<<endl;cout<<" 9.退出系统"<<endl;cout<<"请选择: ";cin>>choice;switch(choice){ case 1: shuru(Lx);break;case 2: show(Lx,Lx.length);break;case 3: cout<<"顺序表的长度:"<<Listlength(Lx)<<endl;break;case 4: chaxun(Lx);break;case 5: xiugai(Lx);break;case 6: charu(Lx);break;case 7: shanchu(Lx);break;case 8: hebing(Lx);break;case 9: cout<<"退出系统!"<<endl;exit(0);break;default : cout<<"输入有误, 请重新选择"<<endl;break; } }}单链表的基本操作#include<iostream>using namespace std;#define true 1#define false 0#define ok 1#define error 0#define overflow -2typedef int Status;typedef int ElemType;typedef struct LNode //存储结构{ ElemType data;struct LNode *next;}LNode,*LinkList;void CreateList(LinkList &L,int n) //尾插法创建单链表{ LinkList p;L=new LNode;L->next=NULL; //建立一个带头结点的单链表LinkList q=L; //使q指向表尾for(int i=1;i<=n;i++){ p=new LNode;cin>>p->data;p->next=NULL;q->next=p;q=p; }}Status GetElem(LinkList L,int i,ElemType &e)//取第i个元素{ LinkList p=L->next;int j=1;while(p&&j<i){ p=p->next;++j; }if(!p||j>i) return error; //第i个元素不存在e=p->data;return ok;}Status LinkInsert(LinkList &L,int i,ElemType e) //插入{ LinkList p=L;int j=0;while(p&&j<i-1){ p=p->next;++j; } //寻找第i-1个结点if(!p||j>i-1)return error; //i小于1或者大于表长加1 LinkList s=new LNode; //生成新结点s->data=e;s->next=p->next; //插入L中p->next=s;return ok;}Status ListDelete(LinkList &L,int i,ElemType &e) // 删除{ LinkList p=L;LinkList q;int j=0;while(p->next&&j<i-1){ //寻找第i个结点, 并令p指向其前驱p=p->next;++j; }if(!(p->next)||j>i-1) return error; //删除位置不合理q=p->next;p->next=q->next; //删除并释放结点e=q->data;delete(q);return ok;}void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){ //合并两个顺序链表LinkList pa,pc,pb;pa=La->next;pb=Lb->next;Lc=pc=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;delete(Lb);}void show(LinkList L) //显示{ LinkList p;p=L->next;while(p){ cout<<p->data<<"-->";p=p->next; }cout<<endl;}int Length(LinkList L,int i) //表长{ i=0;LinkList p=L->next;while(p){ ++i;p=p->next; }return i;}void xiugai(LinkList L) //修改{ int i,j=1;ElemType k;ElemType e,m;LinkList p=L->next;cout<<"请输入要修改的元素位置(0<i<length):";cin>>i;GetElem(L,i,e);cout<<"该位置的元素:"<<e<<endl;cout<<"修改后的元素值:";cin>>k;while(p&&j<i){ p=p->next;++j; }m=p->data;p->data=k;cout<<"修改后的单链表显示如下:"<<endl;show(L);}void hebing() //合并两个单链表{ int a,b;LinkList La,Lb,Lc;cout<<"请输入第一个有序链表的长度:"<<endl;cin>>a;cout<<"请输入第一个有序链表的元素共（"<<a<<"个）: "<<endl;CreateList(La,a);show(La);cout<<"请输入第二个有序链表的长度:"<<endl;cin>>b;cout<<"请输入第二个有序链表的元素共（"<<b<<"个）: "<<endl;CreateList(Lb,b);show (Lb);MergeList(La,Lb,Lc);cout<<"合并后的有序链表如下: "<<endl;show(Lc);}void main() //主函数{ int select;int x;ElemType y;LinkList list;for(;;){ cout<<" 单链表的基本操作"<<endl;cout<<" 1.单链表的创建"<<endl;cout<<" 2.单链表的显示"<<endl;cout<<" 3.单链表的长度"<<endl;cout<<" 4.取第i个位置的元素"<<endl;cout<<" 5.修改第i个位置的元素"<<endl;cout<<" 6.插入元素到单链表里"<<endl;cout<<" 7.删除单链表里的元素"<<endl;cout<<" 8.合并两个单链表"<<endl;cout<<" 9.退出系统"<<endl;cout<<"请选择:";cin>>select;switch(select){ case 1:cout<<"请输入单链表的长度:"<<endl;cin>>x;cout<<"请输入"<<x<<"个元素"<<endl;CreateList(list,x);break;case 2: cout<<"单链表显示如下:"<<endl;show(list);break;case 3: int s;cout<<"单链表的长度为:"<<Length(list,s)<<endl;break;case 4: cout<<"请选择所要取出元素的位置:";cin>>x;while(x<0||x>Length(list,s)){ cout<<"输入有误, 请重新输入"<<endl;cout<<"请选择所要取出元素的位置:";cin>>x; }GetElem(list,x,y);cout<<"该位置的元素为:"<<y<<endl;break;case 5: xiugai(list); break;case 6: cout<<"请选择要插入的位置:"; cin>>x;while(x<0||x>Length(list,s)){ cout<<"输入有误, 请重新输入"<<endl;cout<<"请选择所要插入元素的位置:";cin>>x; }cout<<"要插入的元素值:";cin>>y;LinkInsert( list,x,y);cout<<"插入后单链表显示如下:"<<endl;show(list);break;case 7: cout<<"请选择要删除的位置:"; cin>>x;while(x<0||x>Length(list,s)){ cout<<"输入有误, 请重新输入"<<endl;cout<<"请选择所要删除元素的位置:";cin>>x; }ListDelete(list,x,y);cout<<"要删除的元素值:"<<y<<endl;cout<<"删除后的单链表显示如下:"<<endl;show(list);break;case 8: hebing();break;case 9: exit(0);break;default : cout<<"输入有误, 请重新输入"<<endl;break;}}}四、测试结果顺序表的测试结果单链表的测试结果五、心得体会当听到老师说写数据结构实验报告时, 我有点惊讶, 才学了不到一个月, 就要写实验报告。

《数据结构》实验报告实验题目：线性表的操作实验目的：1.掌握上机调试线性表的基本方法；2.掌握线性表的一些基本操作；实验内容：将两个有序链表合并为一个有序链表一、需求分析1.实验程序中先创建两个有序链表，演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入两个链表中的相应数据。

2.将两个链表合并时可按数据从大到小或从小到大合并，用户根据提示可选择一种排序方式。

3.程序执行命令包括：（1）构造链表；（2）输入数据；（3）合并两个链表，根据用户需求选择一种排序方式；（4）将合并结果输出；（5）结束4.测试数据：链表1数据为：2，4，6，7，10链表2数据为：1，3，5，6，7，12按从小到达合并为：1，2，3，4，5，6，6，7，7，10，12；按从大到小合并为：12，10，7，7，6，6，5，4，3，2，1；二、概要设计1.基本操作Linklist creat （）操作结果：构造一个链表，并输入数据，返回头节点指针。

void print(Linklist head)初始条件：链表已存在；操作结果：将链表输出。

void MergeList_1(Linklist La,Linklist Lb)初始条件：有序线性链表La 和Lb 已存在；操作结果：将La 和Lb 两个链表按从小到大的顺序合并。

void MergeList_2(Linklist La,Linklist Lb)初始条件：有序线性链表La 和Lb 已存在；操作结果：将La 和Lb 两个链表按从大到小的顺序合并。

2.本程序包括四个模块：（1）主程序模块；（2）链表数据输入模块；（3）链表合并模块；（4）链表输出模块；三、详细设计1.元素类型，节点类型，指针类型主程序模块 数据输入 按从小到大合并两链表 按从大到小合并两链表 将新链表输出 将新链表输出typedef struct LNode //定义节点{int data;struct LNode *next;}LNode,* Linklist;2.每个模块的分析（1）主函数模块int main(){Linklist head1,head2;int i;printf("请输入链表1数据（由小到大，输入0表示输入结束）：\n");head1=creat(); //创建链表1，将头结点指针返回为head1printf("请输入链表2数据（由小到大，输入0表示输入结束）：\n");head2=creat();printf("请选择排序方式（输入1则从小到达合并，输入其它整数则按从大到小合并）：");scanf("%d",&i); //创建链表2，将头结点指针返回为head2if(i==1) //选择两种排序方式，如果输入1，则合并后按从小到大输出；输入其它数，合成链表按从大到小输出{printf("按小到大将两表合并得：\n");MergeList1(head1,head2); //将创建好的两表的头结点地址head1，head2作为函数参数}else{ printf("按从大到小将两表合并得：\n");MergeList2(head1,head2); //将创建好的两表的头结点地址head1，head2作为函数参数}return 0;}（2）数据输入创建链表模块Linklist creat() //创建链表函数，并将创建链表的头结点指针返回{Linklist head,p,s;int z=1,x;head=(LNode *) malloc(sizeof(LNode));p=head;while(z){scanf("%d",&x);if(x!=0) //输入0表示链表数据输入结束{s=(LNode *)malloc(sizeof(LNode));s->data=x;p->next=s;s->next=NULL;p=s;}elsez=0;}return(head);}（3）合并链表模块，两个函数分别表示两种排序方式，将链表合并后直接在函数中调用链表输出函数void print(Linklist head)将链表输出void MergeList_1(Linklist La,Linklist Lb)//已知链表La和Lb元素都按从小到大排列，将La和Lb合并成新链表，其中元素也按从小到大排列{Linklist pa,pb,pc,Lc;pa = La->next; pb = Lb->next;Lc = pc = La; //把La的头节点作为新建链表Lc的头结点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; //插入剩余段print(Lc); //将链表Lc输出}void MergeList_2(Linklist La,Linklist Lb)//已知链表La和Lb的元素都按从小到大排列，合并La和Lb得到新链表，其中元素按照从大到小的顺序排列{Linklist pa,qa,pb,qb,Lc; //设指针qa,qb,分别作为pa,pb的前驱的指针pa=La->next;pb=Lb->next;Lc=La;Lc->next=NULL;while(pa&&pb){if(pa->data<=pb->data){qa=pa;pa=pa->next;qa->next=Lc->next;Lc->next=qa;}else{qb=pb;pb=pb->next;qb->next=Lc->next;Lc->next=qb;}}while(pa) //如果pa不为空，则将La链的剩余段倒叙插入到头节点的后面{qa=pa;pa=pa->next;qa->next=Lc->next;Lc->next=qa;}while(pb) //如果pb不为空，则将Lb链的剩余段倒叙插入到头结点的后面{qb=pb;pb=pb->next;qb->next=Lc->next;Lc->next=qb;}print(Lc); //将新合成的链表Lc输出}(4)链表输出模块，实现最终链表的输出void print(Linklist head) //链表输出函数，将链表输出{LNode *p;p=head->next;if(head!=NULL)do{printf("%d ",p->data);p=p->next;} while (p);printf("\n");四、程序使用说明及测试结果1.程序使用说明（1）本程序的运行环境为VC6.0；（2）进入演示程序后显示提示信息：请输入链表1数据（由小到大，输入0表示输入结束）：按要求输入数据请输入链表2数据（由小到大，输入0表示输入结束）：按要求输入数据请选择排序方式（输入1则从小到达合并，输入其它整数则按从大到小合并）：输入数据选择合并方式2.测试结果对链表1输入数据2，4，6，7，10，0对链表2输入数据1，3，5，6，7，12，0输入数据选择排序方式：如果输入：1 输出结果为：1，2，3，4，5，6，6，7，7，10，12如果输入：3（整数非1）输出结果为：12，10，7，7，6，6，5，4，3，2，13.调试中遇到的错误分析第一次运行时有问题，看以看出它的排序方式是对的，但是输出是多出前面一个很大的数，可能是输出函数void print(Linklist head)有问题，检查程序：此处逻辑出错，直接将p指针指向head，然后就将p->data输出，因此第一个数是头指针head所对应节点的值，所以可将p=head;改为p=head->next;这样p就指向第一个节点。