下载文档原格式
实验二线性表的链式存储和操作（有序表的合并）1.目的用链表（LinkList）类型实现书上算法2.1和2.2，了解线性表及在计算机中的两类不同的存储结构；熟练掌握线性表的查找、插入和删除等算法并灵活运用这些算法。
2.要求用C语言编写程序，其中Lb={2,4,6,8,10} La={1,2,3,4,5},①算法2.1执行后，得到的new La = 1,2,3,4,5,6,8,10②修改Lb=2,6,8,9,11,15,20，并利用新生成的La，得到合并后的Lc，Lc= 1,2,2,3,4,5,6,6,8,8,9,10,11,15,203、预习要求：1、复习书上第20页的例2-1和例2-2；2、复习算法2.3，理解如何构造线性表；3、复习算法2.12，理解算法的执行步骤和含义；4、算法设计#include <stdio.h>#include <stdlib.h>#include <malloc.h># define TRUE 1# define ERROR 0# define OK 1# define OVERFLOW -2# define FALSE 0void main(){LinkList La,Lb,Lc;CreatList_L(La,4);CreatList_L(Lb,7);MergeList_L(La, Lb, Lc);}5.小结线性表是软件设计中最基础的数据结构。
用顺序方法存储的线性表称为顺序表，当线性表中很少做插入和删除操作，线性表的长度变化不大，易于事先确定其大小时，可以采用顺序表作为存储结构。
用链接方法存储的线性表称为线性链表，当线性表的长度变化较大，难以估计其存储规模，另外对线性表频繁进行插入和删除操作时，则采用链表作为存储结构可能会更好一些。
在实际应用中应该考虑以下因素：（１）应有利于运算的实现；（２）应有利于数据的特性；（３）应有利于软件环境。
第2章线性表线性表是一种最基本、最常用的数据结构，它有两种存储结构——顺序表和链表。
本章主要介绍线性表的定义、表示和基本运算的实现。
重点讨论了线性表的存储结构，以及在顺序、链式两种存储结构上基本运算的实现。
重点提示：●线性表的逻辑结构特征●线性表的顺序存储和链式存储两种存储结构的特点●在两种存储结构下基本操作的实现2-1 重点难点指导2-1-1 相关术语1．线性表线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为：(a1,a2,…,a n)，其中n为表长，n=0时称为空表。
要点：一种逻辑结构，其数据元素属于相同数据类型，之间的关系是线性关系。
2．顺序表顺序存储的线性表。
要点：按线性表中的元素的逻辑顺序依次存放在地址连续的存储单元里，其存储特点：用物理上的相邻实现逻辑上的相邻。
3．链表用链表存储的线性表。
要点：链表是通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，对每个结点的地址是否连续没有要求。
4．单链表每个结点除了数据域外还有一个指向其后继的指针域。
要点：通常将每个元素的值和其直接后继的地址作为一个结点，通过每个结点中指向后继结点的指针表示线性表的逻辑结构。
5．头指针要点：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。
如链表H，链表L等，表示链表中第一个结点的地址存放在指针变量H、L中。
通常用头指针来惟一标识一个链表。
6．头结点要点：附加在第一个元素结点之前的一个结点，头指针指向头结点。
当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点；为空表时，该指针域为空。
7．头结点的作用要点：其作用有两个，一是使对空表和非空表的处理得到统一；二是在链表的第一个位置上的操作和在其他位置上的操作一致，无需特殊处理。
2-1-2 线性表的顺序存储1．顺序表顺序存储的线性表称为顺序表。
其特点是：用一组地址连续的存储单元来依次存放线性表的数据元素，因此数据元素的逻辑顺序和物理次序一致（这是顺序存储的核心所在）。
实验报告题目：完成线性表ADT的顺序存储和链式存储方式的实现一、需求分析1、本演示程序中，线性表的数据元素类型限定为整型2、演示程序以用户和计算机的对话方式执行，即在计算机的终端上显示“提示信息”之后由用户在键盘上键入演示程序规定的运算命令，相应的输出结果显示在后面。
3、程序的执行命令包括：创建、撤销、清空、插入、修改、删除、定位等线性表ADT各项基本操作二、概要设计为实现上述功能，我们给出线性表的抽象数据类型定义，具体的有单向链，双向链，顺序表等，同时对于上述功能的实现还采用有/无头结点两种方式来实现1.线性表的抽象数据类型定义为ADT List{数据对象：D={a i|a i∈ElemSet，i=1,2,…,n,n≥0}数据关系：R1={<a i-1,a i>|ai-1,ai∈D，i=2,…,n}基本操作：InitList(&L)操作结果：构造一个空的线性表LDestroyList(&L)初始条件：线性表L已存在。
操作结果：销毁线性表L。
ClearList(&L)初始条件：线性表L已存在。
操作结果：将L重置为空表。
ListEmpty(L)初始条件：线性表L已存在。
操作结果：若L为空表，则返回TRUE，否则返回FALSE。
ListLength(L)初始条件：线性表L已存在。
操作结果：返回L中的i个数据元素的值。
GetElem(L,i,&e)初始条件:线性表L已存在，1≤i≤ListLength（L）。
操作结果：用e返回L中第i个数据元素的值。
LocateElem（L,e,compare()）初始条件：线性表L已存在，compare()是数据元素判定函数操作结果：返回L中第一个与e满足compare()的数据元素的位序。
若这样的数据元素不存在，则返回值为0.PriorElem（L,cur_e,&pre_e）初始条件：线性表已存在操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
一、实验目的：1. 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；2. 以线性表的各种操作（建立、插入、删除等）的实现为重点；3. 掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；二、实验内容：1．输入一组整型数据，建立顺序表。
2．实现该线性表的删除。
3、实现该线性表的插入。
4．实现线形表中数据的显示。
5．实现线性表数据的查找和定位5、编写一个主函数,调试上述算法。
三、实验原理、方法和手段1.根据实验内容编程，上机调试、得出正确的运行程序。
2. 编译运行程序，观察运行情况和输出结果。
3. 写出实验报告（包括源程序和运行结果）。
四、实验条件运行Visual stadio 2010的微机一台五、实验步骤（程序清单）：// 实验一.cpp : 定义控制台应用程序的入口点。
//#include"stdafx.h"#include<iostream>#include<string.h>#include<stdlib.h>using namespace std;typedef int ElemType;struct List{ElemType *list;int size;int MaxSize;};void InitList(List &L,int n) //初始化线性表{L.MaxSize =n+5;L.list=new ElemType [L.MaxSize];if(L.list==NULL){ cout<<"动态可分配的存储空间已用完,退出运行!"<<endl;exit(1);}L.size=0;}void InputList(List &L) //输入元素{L.size =L.MaxSize-5;for(int i=0;i<L.size;i++){cout<<"请输入第"<<i+1<<"个元素:"<<endl;cin>>L.list[i];}}void FindList(List &L) //查找位置{if(L.size==0){cout<<"线性表为空，查找失败！"<<endl;return;}else{int item;Find:cout<<"请输入要查找的元素：";cin>>item;int i;for(i=0;i<L.size;i++)if(L.list[i]==item){item=L.list[i];cout<<"查找成功！您所查找的数据"<<item<<" 在第"<<i+1<<"个位置"<<endl;break;}if(i>=L.size){cout<<"您所查找的数据不存在！"<<endl;Find2:cout<<"是否继续查找？（y/n）:";char c[100];cin>>c;if(strlen(c)==1){if(c[0]=='y')goto Find;else if(c[0]!='y'&&c[0]!='n'){cout<<"您输入的操作无效！";goto Find2;}else return;}else{cout<<"您输入的操作无效！请重新选择：";goto Find2;}}}}void DisplayList(List &L) //按位置查找元素{if(L.size ==0){cout<<"线性表为空，查找失败！"<<endl;return;}else{int pos;Display:cout<<"请输入您要查找元素的位置：";cin>>pos;if(pos<1||pos>L.size){cout<<"您输入的位置无效！"<<endl;Display2:cout<<"是否继续按位置查找？（y/n）:";char c[100];cin>>c;if(strlen(c)==1){if(c[0]=='y')goto Display;else if(c[0]!='y'&&c[0]!='n'){cout<<"您输入的操作不合法！";goto Display2;}else return;}else{cout<<"您输入的操作不合法！";goto Display2;}}elsecout<<"您要查找的第 "<<pos<<" 个数据为 "<<L.list[pos-1]<<endl;}}void ClearList(List &L) //清空线性表{if(L.list!=NULL){ delete [ ]L.list;L.list=NULL;}L.MaxSize=0;L.size=0;cout<<"清空成功！"<<endl;}void InsertList(List &L) //插入一个元素{if(L.size==0){cout<<"线性表为空，插入失败！"<<endl;return;}else{Insert:cout<<"请选择要插入的方式：按有序插入请输入0 按位置插入请输入位置值：";int pos;cin>>pos;cout<<"请输入要插入的元素：";ElemType item;cin>>item;if(pos<-1||pos>L.size+1){cout<<"位置值无效！"<<endl;Insert2:cout<<"是否继续插入？(y/n):";char c[100];cin>>c;if(strlen(c)==1){if(c[0]=='y')goto Insert;else if(c[0]!='y'&&c[0]!='n'){cout<<"您输入的操作无效！";goto Insert2;}else return;}else{cout<<"您输入的操作无效！";goto Insert2;}}int i;if(pos==0){ for(i=0;i<L.size;i++)if(item<L.list[i]) break;pos=i+1;}else if(pos==-1) pos=L.size+1;if(L.size==L.MaxSize){int k=sizeof(ElemType);L.list=(ElemType*)realloc(L.list,2*L.MaxSize*k);if(L.list==NULL){cout<<"动态可分配的存储空间已用完,退出运行!"<<endl;exit(1);}L.MaxSize=2*L.MaxSize;}for(i=L.size-1;i>=pos-1;i--)L.list[i+1]=L.list[i];L.list[pos-1]=item;L.size++;cout<<"插入成功！"<<endl;}}void DisplayAllList(List &L) //显示线性表数据{if(L.size ==0)cout<<"线性表不存在，请先创建！"<<endl;else{cout<<"Size="<<L.size<<" MaxSize="<<L.MaxSize<<endl;for(int i=0;i<L.size;i++)cout<<L.list[i]<<" ";cout<<endl;}}void DeleteList(List &L) //删除一个元素{if(L.size==0){cout<<"线性表为空,删除无效!"<<endl;return;}Delete:cout<<"请选择要删除的方式：删除指定元素请输入0 按位置删除请输入位置值：";int pos;cin>>pos;ElemType item;if(pos<0||pos>L.size){cout<<"位置值无效!"<<endl;Delete2:cout<<"是否继续删除？(y/n):";char c[100];cin>>c;if(strlen(c)==1){if(c[0]=='y')goto Delete;else if(c[0]!='y'&&c[0]!='n'){cout<<"您输入的操作不合法！";goto Delete2;}return;}else{cout<<"您输入的操作不合法！";goto Delete2;}}int i;if (pos==0){cout<<"按查找删除，请输入要删除的元素：";cin>>item;for(i=0;i<L.size;i++ )if(item==L.list[i]) break;if(i==L.size){cout<<"按查找删除，没有找到您要删除的元素！ "<<endl; Delete3:cout<<"是否继续按查找删除？(y/n):";char c[100];cin>>c;if(strlen(c)==1){if(c[0]=='y')goto Delete;else if(c[0]!='y'&&c[0]!='n'){cout<<"您输入的操作不合法！";goto Delete3;}else return;}else{cout<<"您输入的操作不合法！";goto Delete3;}}pos=i+1;}else if(pos==-1)pos=L.size;item=L.list[pos-1];cout<<"您要删除的元素 "<<L.list[pos-1]<<"已删除成功！"<<endl;for(i=pos;i<L.size ;i++)L.list[i-1]=L.list [i];L.size--;if(float(L.size)/L.MaxSize<0.4&&L.MaxSize>10){int k=sizeof(ElemType);L.list=(ElemType*)realloc(L.list,L.MaxSize*k/2);L.MaxSize=L.MaxSize/2;}}void menu(){List t;InitList(t,0);menu:cout<<"欢迎进入线性表管理系统："<<endl;cout<<" 1. 创建一个线性表"<<endl;cout<<" 2. 查找元素位置"<<endl;cout<<" 3. 按位置查找元素"<<endl;cout<<" 4. 插入一个元素"<<endl;cout<<" 5. 删除一个元素"<<endl;cout<<" 6. 清空该线性表"<<endl;cout<<" 7. 显示该线性表"<<endl;cout<<" 0. 退出系统"<<endl;menu2:cout<<"请输入你想要执行的操作：";char n[100];cin>>n;if(strlen(n)==1){if(n[0]<'0' || n[0]>'7'){cout<<"您输入的操作不合法，请重新选择！"<<endl;goto menu2;}}else{cout<<"您输入的操作不合法，请重新选择！"<<endl;goto menu2;}switch(n[0]){case'1':cout<<"请输入您所创建线性表元素的个数：";int m;cin>>m;InitList(t,m);InputList(t);cout<<endl;goto menu;case'2':FindList(t);cout<<endl;goto menu;case'3':DisplayList(t);cout<<endl;goto menu;case'4':InsertList(t);cout<<endl;goto menu;case'5':DeleteList(t);cout<<endl;goto menu;case'6':ClearList(t);cout<<endl;goto menu;case'7':DisplayAllList(t);cout<<endl;goto menu;case'0':break;default:cout<<"您输入的操作有误，请重新输入：";goto menu2;}}int _tmain(int argc, _TCHAR* argv[]){menu();}六、调试及运行：1.在未创建一个线性表前，选择其它操作会提示“线性表为空，操作打败”的提示，如图2.选择操作【1】.创建一个线性表，并输入11，22，33，44.如图3.选择操作【7】，显示线性表，便于查找元素位置。
贵州大学实验报告#include<iostream>using namespace std;typedef int Elemtype;struct LNode{Elemtype data;LNode *next;};void BuildLNode(LNode *&hl)/*建立带头结点单链表*/{hl=new LNode;hl->data=NULL;hl->next=NULL;}void ClearList(LNode *&hl)/*清空线性表*/ {LNode *p=hl;LNode *q;while(p!=NULL){q=p->next;delete p;p=q;}hl=NULL;}bool InsertList(LNode *&hl,Elemtype item,int pos)/*在线性表中插入一个元素*/{if(pos<-1){cout<<"位置无效"<<endl;return false;}if(pos==-1||pos==0)pos=1;LNode *p;int i=1;p=hl;while(p!=NULL&&i<pos){p=p->next;i++;}if(p==NULL){cout<<"位置无效"<<endl;return false;}LNode *q;q=new LNode;q->data=item;q->next=p->next;p->next=q;return true;}bool DeleteList(LNode *&hl,int pos)/*删除线性表中的一个元素*/{if(pos<-1){cout<<"位置无效"<<endl;return false;}if(pos==-1||pos==0)pos=1;LNode *p=hl,*q;int i=1;while(p->next!=NULL&&i<pos){p=p->next;i++;}if(p->next==NULL){cout<<"位置无效或该链表为空"<<endl;return false;}q=p->next;p->next=q->next;delete q;return true;}bool GetList(LNode *p,Elemtype &item,int pos)/*线性表中数据的定位*/{if(pos<-1){cout<<"位置无效"<<endl;return false;}if(pos==-1||pos==0)pos=1;int i=0;while(p!=NULL&&i<pos){p=p->next;i++;}if(p==NULL){cout<<"位置无效"<<endl;return false;}item=p->data;return true;}int FindList(LNode *p,Elemtype item)/*线性表中数据的查找*/{int i=0;while(p!=NULL){if(p->data==item)break;i++;p=p->next;}if(p==NULL){cout<<"找不到该元素"<<endl;return 0;}return i;}void DisplayList(LNode *hl)/*显示线性表中所有数据*/{if(hl==NULL){cout<<"该表为空"<<endl;}LNode *p=hl->next;while(p!=NULL){cout<<p->data<<" ";p=p->next;}} void main(){LNode *head;BuildLNode(head);int pos;Elemtype data;for(int i=0;i<10;i++)InsertList(head,2*i+1,i+1);DisplayList(head);cout<<endl;cout<<"一、插入操作"<<endl;cout<<"位置：";cin>>pos;cout<<"数据：";cin>>data;if(InsertList(head,data,pos))cout<<"插入成功"<<endl;elsecout<<"插入失败"<<endl;DisplayList(head);cout<<endl<<endl;cout<<"二、删除操作"<<endl;cout<<"位置：";cin>>pos;if(DeleteList(head,pos))cout<<"删除成功"<<endl;elsecout<<"删除失败"<<endl;DisplayList(head);cout<<endl<<endl;cout<<"三、定位操作："<<endl;cout<<"位置：";cin>>pos;if(GetList(head,data,pos))cout<<"该位置数据为"<<data<<endl;elsecout<<"定位失败"<<endl;cout<<"四、查找操作："<<endl;cout<<"数据：";cin>>data;if(FindList(head,data))cout<<"线性表中第一个等于该数据的位置为"<<FindList(head,data)<<endl;elsecout<<"查找失败"<<endl;ClearList(head);}。
实验二线性表的链式存储
一、实验目的
1.掌握线性表的链式存储结构。
2.能熟练地利用链式存储结构实现线性表的基本操作。
3.能熟练地掌握链式存储结构中算法的实现。
二、实验内容
1.分别用头插法和尾插法建立带头结点的单链表。
2.实现单链表上的插入、删除、修改、查找、计数、输出等基本操作。
3.解决约瑟夫问题：假设有n个人按1、2、3、…、n的顺序围成一圈，现在，从第s个人开始按1、2、3、…、m的顺序报数，数到m的人出圈，接着从出圈的下一个人开始重复此过程，直到所有人出圈为止。
试用循环链表解决这个问题。
三、算法描述
1.第1题、第2题的算法提示
先定义单链表的数据类型，然后将头插法和尾插法、插入、删除、修改、查找、计数、输出等基本操作都定义成单独的子函数形式，最后在主函数中调用，并将每一种操作前后的结果输出，以查看每一种操作的效果。
2.第3题的算法提示
首先将n个人的信息建立成一个单循环链表，链表中的每个结点信息就是每个人的编号（1～n）。
然后利用循环找到出圈人位置的结
点，输出该结点的信息，再在链表中删除该结点，接着从删除的结点的后面重复此步骤，直到链表中剩下一个结点时停止循环，再把链表中的最后一个结点删除。
实验报告的要求与实验一相同。
说明每个实验题目含有一个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. 串采用顺序存储结构, 编写朴素模式匹配算法, 查找在串中是否存在给定的子串。
线性表实验报告一、实验目的本次实验的主要目的是深入理解线性表的基本概念和操作，通过实际编程实现线性表的存储和基本运算，掌握线性表在数据结构中的应用，提高对数据结构的理解和编程能力。
二、实验环境本次实验使用的编程语言为C+＋，开发工具为Visual Studio 2019。
三、实验原理线性表是一种最基本、最简单的数据结构，它是由 n（n≥0）个数据元素组成的有限序列。
在这个序列中，每个数据元素的位置是按照其逻辑顺序排列的。
线性表有两种存储结构：顺序存储结构和链式存储结构。
顺序存储结构是用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的两个元素在物理位置上也相邻。
其优点是可以随机访问表中的任意元素，时间复杂度为 O(1)；缺点是插入和删除操作需要移动大量元素，时间复杂度为 O(n)。
链式存储结构是通过指针将各个数据元素链接起来，每个数据元素由数据域和指针域组成。
其优点是插入和删除操作不需要移动大量元素，时间复杂度为 O(1)；缺点是不能随机访问表中的元素，需要从头指针开始遍历，时间复杂度为 O(n)。
四、实验内容本次实验实现了顺序表和链表的基本操作，包括创建、插入、删除、查找、遍历等。
1、顺序表的实现定义顺序表的结构体，包括数据存储数组和表的长度。
实现顺序表的初始化函数，将表的长度初始化为 0。
实现顺序表的插入函数，在指定位置插入元素，如果插入位置非法或表已满，则返回错误。
实现顺序表的删除函数，删除指定位置的元素，如果删除位置非法，则返回错误。
实现顺序表的查找函数，查找指定元素，如果找到则返回元素的位置，否则返回－1。
实现顺序表的遍历函数，输出表中的所有元素。
2、链表的实现定义链表的结构体，包括数据域和指向下一个节点的指针域。
实现链表的创建函数，创建一个空链表。
实现链表的插入函数，在指定位置插入元素，如果插入位置非法，则返回错误。
实现链表的删除函数，删除指定位置的元素，如果删除位置非法，则返回错误。
