当前位置:文档之家› 实验二 线性表的顺序存储

实验二 线性表的顺序存储

实验二 线性表的顺序存储
实验二 线性表的顺序存储

实验报告二线性表的顺序存储班级:姓名:学号:专业:

一、实验目的:

(1)掌握顺序表的基本操作的实现方法。

(2)应用顺序表的基本算法实现集合A=AUB算法。

(3)应用顺序表的基本算法实现两有序顺序表的归并算法。

二、实验内容:

1、线性表顺序存储结构的基本操作算法实现(要求采用类模板实现)

[实现提示] (同时可参见教材p5822-p60页算法、ppt)函数、类名称等可自定义,部分变量请加上学号后3位。

库函数载和常量定义:(代码)

#include

#include

const int MaxSize=100;

(1)顺序表存储结构的定义(类的声明):(代码)

template //定义模板类SeqList

class SeqList

{

public:

SeqList( ); //无参构造函数

SeqList(datatype a[ ], int n); //有参构造函数

~SeqList(); //析构函数为空

int Length(); //求线性表的长度

datatype Get(int i); //按位查找,取线性表的第i个元素

int Locate(datatype item); //查找元素item

void Insert(int i, datatype item); //在第i个位置插入元素item

datatype Delete(int i); //删除线性表的第i个元素

void display(); //遍历线性表,按序号依次输出各元素

private:

datatype data[MaxSize]; //存放数据元素的数组

int length; //线性表的长度

};

(2)初始化顺序表算法实现(不带参数的构造函数)

/*

*输入:无

*前置条件:顺序表不存在

*功能:构建一个顺序表

*输出:无

*后置条件:表长为0

*/

实现代码:

template

SeqList:: SeqList( )

{

length=0;

}

(3)顺序表的建立算法(带参数的构造函数)

/*

*输入:顺序表信息的数组形式a[],顺序表长度n

*前置条件:顺序表不存在

*功能:将数组a[]中元素建为长度为n的顺序表

*输出:无

*后置条件:构建一个顺序表

*/

实现代码:

template

SeqList:: SeqList(datatype a[], int n) {

if (n>MaxSize) throw "数组元素个数不合法";

for (int i=0; i

data[i]=a[i];

length=n;

}

(4)在顺序表的第i个位置前插入元素e算法

/*

*输入:插入元素e,插入位置i

*前置条件:顺序表存在,i要合法

*功能:将元素e插入到顺序表中位置i处

*输出:无

*后置条件:顺序表插入新元素,表长加1

*/

实现代码:

template

void SeqList::Insert(int i, datatype item) {

int j;

if (length>=MaxSize) throw “溢出";

if (i<1 || i>length+1) throw “i不合法!";

for (j=length; j>=i; j--)

data[j]=data[j-1];

data[i-1]=item;

length++;

}

(5)删除线性表中第i个元素算法

/*

*输入:要删除元素位置i

*前置条件:顺序表存在,i要合法

*功能:删除顺序表中位置为i的元素

*输出:无

*后置条件:顺序表册除了一个元素,表长减1

*/

实现代码:

template

datatype SeqList::Delete(int i)

{

int item,j;

if (length==0) throw “表为空,无法删除元素!";

//或者 if (length==0) return NULL;

if (i<1 || i>length) throw “i不合法!";

//或者 if (length==0) return NULL;

item=data[i-1];//获得要删除的元素值

for (j=i; j

data[j-1]=data[j]; //注意数组下标从0记 length--;

return item;

}

(6)遍历线性表元素算法

/*

*输入:无

*前置条件:顺序表存在

*功能:顺序表遍历

*输出:输出所有元素

*后置条件:无

*/

实现代码:

template

void SeqList::display(int i)

{

int item;

for(i=1;i<=length,i++)

item=data[i];

return item;

}

(7)获得线性表长度算法

/*

*输入:无

*前置条件:顺序表存在

*功能:输出顺序表长度

*输出:顺序表长度

*后置条件:无

*/

实现代码:

template

datatype SeqList::Length(int i)

{

return length;

}

(8)在顺序线性表中查找e值,返回该元素的位序算法/*

*输入:查询元素值e

*前置条件:顺序表存在

*功能:按值查找值的元素并输出位置

*输出:查询元素的位置

*后置条件:无

*/

实现代码:

template

int SeqList::Locate(datatype item) {

for (int i=0; i

if (data[i]==item)

return i+1 ;

//下标为i的元素等于item,返回其序号i+1 return 0; //查找失败

}

(9)获得顺序线性表第i个元素的值

/*

*输入:查询元素位置i

*前置条件:顺序表存在,i要合法

*功能:按位查找位置为i的元素并输出值

*输出:查询元素的值

*后置条件:无

*/

实现代码:

template

datatype SeqList::Get(int i)

{

if (i<1 && i>length) throw "i不合法!";

else return data[i-1];

}

(10)判表空算法

/*

*输入:无

*前置条件:无

*功能:判表是否为空

*输出:为空返回1,不为空返回0

*后置条件:无

*/

实现代码:

SeqList:: ~SeqList( )

{

if(length=0) return 1;

return 0;

}

(11)求直接前驱结点算法

/*

*输入:要查找的元素e,待存放前驱结点值e1

*前置条件:无

*功能:查找该元素的所在位置,获得其前驱所在位置。*输出:返回其前驱结点的位序。

*后置条件:e1值为前驱结点的值

*/

实现代码:

(12)求直接后继结点算法

/*

*输入:要查找的元素e,待存放后继结点值e1

*前置条件:无

*功能:查找该元素的所在位置,获得其后继所在位置。*输出:返回其后继结点的位序。

*后置条件:e1值为后继结点的值

实现代码:

上机实现以上基本操作,写出main()程序:

要求对每个算法都加以测试,判断是否正确;并测试不同类型数据的操作。

粘贴测试数据及运行结果:

2、用以上基本操作算法,实现A=AUB算法。(利用函数模板实现)

/*

*输入:集合A,集合B

*前置条件:无

*功能:实现A=AUB

*输出:无

*后置条件:A中添加了B中的元素。

*/

实现代码:

粘贴测试数据及运行结果:

3、对以上顺序表类中的基本操作算法适当加以补充,实现向一个有序的(非递减)的顺序表中插入数据元素e算法。

/*

*输入:插入元素e

*前置条件:顺序表已有序

*功能:将元素e插入到顺序表中适当的位置,使顺序表依然有序

*输出:无

*后置条件:有序顺序表插入了新元素,且表长加1。

*/

实现代码:

粘贴测试数据及运行结果:

4、算法实现:La,Lb为非递减的有序线性表,将其归并为Lc,该线性表仍有序(未考虑相同时删除一重复值)(利用函数类板实现)

MergeList:

/*

*输入:有序线性表La,有序线性表Lb

*前置条件:顺序表已有序

*功能:将两线性表归并,不去掉相同元素

*输出:返回一个新的有序线性表Lc

*后置条件:无

*/

实现代码:

粘贴测试数据及运行结果:

选做题:

1、在第2题的基础上考虑实现A=AU(B-A)。

2、在第4题的基础上考虑删除重复值(即相同值只取一个)的算法实现。

3、如何用算法实现将线性表循环右移k位。(m=k%L.length,每次取最后一个元素,插入到第1个位置,做m次)

三、心得体会:(含上机中所遇问题的解决办法,所使用到的编程技巧、创新点及编程

的心得)

实验一.顺序表验证实验

线性表 实验一顺序表操作验证 1. 实验目的 ⑴掌握线性表的顺序存储结构; ⑵验证顺序表及其基本操作的实现; ⑶掌握数据结构及算法的程序实现的基本方法。 2. 实验内容 ⑴建立含有若干个元素的顺序表; ⑵对已建立的顺序表实现插入、删除、查找等基本操作。 3. 实现提示 首先定义顺序表的数据类型——顺序表类SeqList,包括题目要求的插入、删除、查找等基本操作,为便于查看操作结果,设计一个输出函数依次输出顺序表的元素。 const int MaxSize=10; template //定义模板类SeqList class SeqList { public: SeqList( ){length=0;} //无参构造函数 SeqList(T a[ ], int n);//有参构造函数 void Insert(int i, T x); //在线性表中第i个位置插入值为x的元素 T Delete(int i); //删除线性表的第i个元素 int Locate(T x ); //按值查找,求线性表中值为x的元素序号 void PrintList( ); //遍历线性表,按序号依次输出各元素 private: T data[MaxSize]; //存放数据元素的数组 int length; //线性表的长度 }; 其次,建立含有n个数据元素的顺序表,即设计构造函数。算法如下: 最后,对建立的顺序表设计插入、删除、查找等基本操作的算法。

顺序表 ⑴插入算法 ⑵删除算法 ⑶查找算法

线性表班级:_________ 学号:_____________ 姓名:___________ 成绩:_________ 实验一顺序表操作验证 一、实验目的 二、实验内容 三、设计与编码 a)本实验用到的理论知识 实验用到的理论知识,实现理论与实践相结合。总结尽量简明扼要,并与本次实验密切相关。 b)算法设计 对本次实验内容设计c++类定义,设计算法完成每个成员函数。 c)编码 将算法转化为c++程序,设计主函数完成对各成员函数的调用。 四、运行与调试 a)在调试程序的过程中遇到什么问题,是如何解决的? b)设计了哪些设计数据?测试结果是什么? c)程序运行的结果如何? 五、实验小结 说明:1.实验报告用A4纸打印。 2.实验标题用黑体小三加粗。 3.每节标题用黑体小四加粗。 4.正文用宋体五号字。

线性表顺序存储结构上的基本运算

实验项目名称:线性表的顺序存储结构上的基本运算 (所属课程:数据结构--用C语言描述) 院系:计算机科学与信息工程学院专业班级:网络工程 姓名:000000 学号:0000000000 实验日期:2016.10.20 实验地点:A-06 406 合作者:指导教师:孙高飞 本实验项目成绩:教师签字:日期: (以下为实验报告正文) 一、实验目的 本次实验的目的掌握顺序表的存储结构形式及其描述和基本运算的实现;掌握动 态链表结构及相关算法设计 实验要求:输入和验证程序例题。正确调试程序,记录程序运行结果。完成实验报 告。 二、实验条件 Windows7系统的电脑,vc++6.0软件,书本《数据结构--用c语言描述》 三、实验内容 3.1 根据41页代码,用c语言定义线性表的顺序存储结构。 3.2 根据42页算法2.1实现顺序表的按内容查找。 3.3 根据43页算法2.2实现顺序表的插入运算。 3.4 根据45页算法2.3实现顺序表的删除运算。 四、实验步骤 3.2实验步骤 (1)编写头文件,创建ElemType。 (2)根据根据41页代码,“用c语言定义线性表的顺序存储结构”定义顺序表。

(3)根据42页算法2.1实现顺序表的按内容查找,创建Locate函数。 (4)创建main函数,输入SeqList L的数据元素。 (5)输入要查找的数据元素的值,调用Locate函数,输出结果。 3.3实验步骤 (1)编写头文件,创建ElemType。 (2)根据41页代码,“用c语言定义线性表的顺序存储结构”定义顺序表。 (3)根据43页算法2.2实现顺序表的插入运算,创建InsList函数。 (4)创建printList函数,逐项输出顺序表内的元素及顺序表元素的个数。 (5)创建main函数,输入插入的元素和其位置,调用printLinst函数输出顺序表,调用IntList函数,再次调用printLinst函数输出顺序表。 3.4实验步骤 (1)编写头文件,创建ElemType。 (2)根据根据41页代码,“用c语言定义线性表的顺序存储结构”定义顺序表。 (3)根据45页算法2.3实现顺序表的删除运算,创建DelList函数。 (4)创建printList函数,逐项输出顺序表内的元素及顺序表元素的个数。 (5)创建main函数,输入删除元素的位置,调用printLinst函数输出顺序表,调用DelList函数,再次调用printLinst函数输出顺序表。 五、实验结果 (1)实验3.2顺序表的按内容查找 # include typedef int Elemtype; typedef struct{ Elemtype elem[100]; int last; }SeqList; int Locate(SeqList L,Elemtype e){ int i; i=0;

数据结构实验报告 实验一 线性表链式存储运算的算法实现

昆明理工大学信息工程与自动化学院学生实验报告 (201 —201 学年第一学期) 课程名称:数据结构开课实验室:年月日年级、专业、班学号姓名成绩 实验项目名称线性表链式存储运算的算法实现指导教师 教 师 评语教师签名: 年月日 一.实验内容: 线性表链式存储运算的算法实现,实现链表的建立、链表的数据插入、链表的数据删除、链表的数据输出。 二.实验目的: 1.掌握线性表链式存储结构的C语言描述及运算算法的实现; 2.分析算法的空间复杂度和插入和删除的时间复杂度; 3.总结比较线性表顺序存储存储与链式存储的各自特点。 三.主要程序代码分析: LinkList creatListR1() //用尾插入法建立带头结点的单链表 { char *ch=new char(); LinkList head=(LinkList)malloc(sizeof(ListNode)); //生成头结点*head ListNode *s,*r,*pp; r=head; //尾指针初值指向头结点 r->next=NULL; scanf("%s",ch); //读入第一个结点的值 while(strcmp(ch,"#")!=0) { //输入#结束

pp=LocateNode(head,ch); if(pp==NULL) { s=(ListNode *)malloc(sizeof(ListNode)); //生成新的结点*s strcpy(s->data,ch); r->next=s; //新结点插入表尾 r=s; //尾指针r指向新的表尾 r->next=NULL; } scanf("%s",ch); //读入下一个结点的值 } return head; //返回表头指针 } int Insert(ListNode *head) //链表的插入 { ListNode *in,*p,*q; int wh; in=(ListNode *)malloc(sizeof(ListNode));in->next=NULL; //生成新结点p=(ListNode *)malloc(sizeof(ListNode));p->next=NULL; q=(ListNode *)malloc(sizeof(ListNode));q->next=NULL; scanf("%s",in->data); //输入插入的数据 scanf("%d",&wh); //输入插入数据的位置 for(p=head;wh>0;p=p->next,wh--); q=p->next; p->next=in; in->next=q; } void DeleteList(LinkList head,char *key) //链表的删除 { ListNode *p,*r,*q=head; p=LocateNode(head,key); //按key值查找结点的 if(p==NULL) exit(0); //若没有找到结点,退出 while(q->next!=p) //p为要删除的结点,q为p的前结点q=q->next; r=q->next; q->next=r->next; free(r); //释放结点*r } 四.程序运行结果:

线性表练习题(答案)

第2章线性表 一选择题 下列程序段的时间复杂度为( C )。 for( int i=1;i<=n;i++) for( int j=1;j<= m; j++) A[i][j] = i*j ; A. O(m2) B. O(n2) C. O(m*n) D. (m+n) 下面关于线性表的叙述中,错误的是哪一个?(B ) A.线性表采用顺序存储,必须占用一片连续的存储单元。 B.线性表采用顺序存储,便于进行插入和删除操作。 C.线性表采用链接存储,不必占用一片连续的存储单元。 D.线性表采用链接存储,便于插入和删除操作。 线性表是具有n个( C )的有限序列(n>0)。 A.表元素B.字符C.数据元素D.数据项 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用( A )存储方式最节省时间。 A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用( D )存储方式最节省运算时间。 A.单链表B.仅有头指针的单循环链表 C.双链表D.仅有尾指针的单循环链表 设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用( D )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用( D )存储方式最节省运算时间。 A.单链表B.双链表C.单循环链表D.带头结点的双循环链表 链表不具有的特点是( B ) A.插入、删除不需要移动元素B.可随机访问任一元素 C.不必事先估计存储空间D.所需空间与线性长度成正比 下面的叙述不正确的是(B,C ) A.线性表在链式存储时,查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时,查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时,查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时,查找第i个元素的时间同i的值无关 若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为( C )(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 对于顺序存储的线性表,访问结点和增加、删除结点的时间复杂度为(C )。 A.O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 线性表(a1,a2,…,an)以链接方式存储时,访问第i位置元素的时间复杂性为( C )A.O(i)B.O(1)C.O(n)D.O(i-1) 循环链表H的尾结点P的特点是(A )。 A.P->next=H B.P->next= H->next C.P=H D.P=H->next 完成在双循环链表结点p之后插入s的操作是(D );

3线性表及其顺序存储结构

1.3线性表及其顺序存储结构 1.线性表的基本概念 线性表是由n个数据元素组成的一个有限序列,表中的每一个数据元素,除了每一个外,有且只有一个前件,除了最后一个外,有且只有一个后件。即线性表或是一个空表。 显然线性表是一种线性结构,数据元素在线性表中的位置只取决于它们自己的序号,即数据元素之间的相对位置是线性的。 非空线性表有如下一些结构特征: (1)有且只有一个根结点,它无前件; (2)有且只有一个根结点,它无后件; (3)除了根结点与终端结点外,其他所有结点有且只有一个前件,也只有且只有一个后件。 2.线性表的存储结构 线性表的顺序存储结构具有以下两个特征: (1)线性表中所有元素所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 由此可以看出,在线性表的顺序存储结构中,其前件和后件两个元素在存储空间中是紧邻的,且其前件元素一定存储在后件元素的前面。 在程序设计语言中,通常定义一个一维数组来表示线性表的顺序存储看见。因为程序设计语言中的一维数组与计算机中的实际的存储空间结构是类似的,这就便于用程序设计语言对线性表进行各种运算处理。 在线性表的顺序存储结构中,可以对线性表进行各种处理。主要的运算有如下几种: (1)在线性表的指定位置处加入一个新的元素; (2)在线性表中删除指定的元素; (3)在线性表中查找某个特定的元素; (4)对线性表中的元素进行整序; (5)按要求将一个线性表分解成多个线性表; (6)按要求将多个线性表合并成一个线性表; (7)复制一个线性表; (8)逆转一个线性表等。 3.顺序表的插入运算 设长度为n的线性表为 (a1,a2,a3,a4,…,ai, …,an) 现要在线性表的第i个元素ai之前插入一个新元素b,插入后得到长度为n+1的线性表为 (a1,a2,a3,a4,…,aj,aj+1, …,an,an+1) 则插入前后的两线性表中的元素满足如下关系: a j0

线性表ADT的顺序存储与链式存储实验报告

实验报告 题目:完成线性表ADT的顺序存储和链式存储方式的实现 一、需求分析 1、本演示程序中,线性表的数据元素类型限定为整型 2、演示程序以用户和计算机的对话方式执行,即在计算机的终端上显示“提 示信息”之后由用户在键盘上键入演示程序规定的运算命令,相应的输出 结果显示在后面。 3、程序的执行命令包括: 创建、撤销、清空、插入、修改、删除、定位等线性表ADT各项基本操作二、概要设计 为实现上述功能,我们给出线性表的抽象数据类型定义,具体的有单向链,双向 链,顺序表等,同时对于上述功能的实现还采用有/无头结点两种方式来实现 1.线性表的抽象数据类型定义为 ADT List{ 数据对象:D={a i|a i∈ElemSet,i=1,2,…,n,n≥0} 数据关系:R1={|ai-1,ai∈D,i=2,…,n} 基本操作: InitList(&L) 操作结果:构造一个空的线性表L DestroyList(&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无定义。

线性表的顺序存储结构定义和基本操作算法实现

/************线性表的顺序存储结构定义和基本操作算法实现************/ #include "stdio.h" /***********************线性表的顺序存储结构定义*******************/ #define MAX 11 /*线性表可能达到的最大长度值*/ typedef int datatype; typedef struct {datatype data[MAX]; int last;}list; /************************1.线性表的初始化***************************/ void init(list *lp) {lp->last=0;} /************************2.求线性表的长度***************************/ int length(list *lp) { return (lp->last);} /***************3.插入运算,在表第i个位置插入一个值为x的新元素******/ void insert(list *lp,int i,datatype x) { int j; if(lp->last==MAX-1) printf("Overflow!\n"); /*表已满*/ else if(i<1||i>lp->last+1) printf("Error!\n"); /*插入位置错误*/ else {for(j=lp->last;j>=i;j--) lp->data[j+1]=lp->data[j]; /*数据元素后移*/ lp->data[i]=x; /*插入x */ lp->last++; /*表长度加1*/ } } /***************4.删除运算,在表中删除第i个数据元素***************/ void delete(list *lp,int i) { int j; if(i<1||i>lp->last) /*检查空表及删除位置的合法性*/ printf("The %dth element is not exist!",i); /*不存在第i个元素*/ else {for(j=i+1;j<=lp->last;j++) lp->data[j-1]=lp->data[j]; /*向前移动元素*/ lp->last--; /*表长度减1 */ } } /*****************5.查找运算,在表中查找x数据元素*****************/ int locate(list *lp,datatype x) { int i=lp->last; while(i>0 && lp->data[i]!=x)i--; return i;

实验报告一顺序表的操作

《数据结构》实验报告一 系别:班级: 学号:姓名: 日期:指导教师: 一、上机实验的问题和要求: 顺序表的查找、插入与删除。设计算法,实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求: 从键盘输入10个整数,产生顺序表,并输入结点值。 从键盘输入1个整数,在顺序表中查找该结点的位置。若找到,输出结点的位置;若找不到,则显示“找不到”。 从键盘输入2个整数,一个表示欲插入的位置i,另一个表示欲插入的数值x,将x插入在对应位置上,输出顺序表所有结点值,观察输出结果。 从键盘输入1个整数,表示欲删除结点的位置,输出顺序表所有结点值,观察输出结果。二、程序设计的基本思想,原理和算法描述: (包括程序的结构,数据结构,输入/输出设计,符号名说明等) 三、源程序及注释:

#include <> /*顺序表的定义:*/ #define ListSize 100 /*表空间大小可根据实际需要而定,这里假设为100*/ typedef int DataType; /*DataType可以是任何相应的数据类型如int, float或char*/ typedef struct { DataType data[ListSize]; /*向量data用于存放表结点*/ int length; /*当前的表长度*/ }SeqList; /*子函数的声明*/ void CreateList(SeqList * L,int n); /*创建顺序表函数*/ int LocateList(SeqList L,DataType x); /*查找顺序表*/ void InsertList(SeqList * L,DataType x,int i); /*在顺序表中插入结点x*/ void DeleteList(SeqList * L,int i);/*在顺序表中删除第i个结点*/ void PrintList(SeqList L,int n); /*打印顺序表中前n个结点*/ void main() { SeqList L; int n=10,x,i; /*欲建立的顺序表长度*/ =0;

数据结构实验线性表的顺序存储结构

南昌航空大学实验报告 课程名称:数据结构实验名称:实验一线性表的链式存储结构班级:080611 学生姓名:冯武明学号:16 指导教师评定:XXX 签名: XXX 题目:设计并实现以下算法:给出用单链表存储多项式的结构,利用后接法生成多项式的单链表结构,实现两个多项式相加的运算,并就地逆置相加后的多项式链式。 一、需求分析 ⒈先构造两个多项式链表,实现两个多项式的和及删除值为零元素的操作,不同用户输入 的多项式不同。 ⒉在演示过程序中,用户需敲击键盘输入值,即可观看结果。 ⒊程序执行的命令包括: (1)构造多项式链表A (2)构造多项式链表B (3)求两张链表的和(4)删除值为零元素,即不创建链表。 二、概要设计 ⒈为实现上述算法,需要线性表的抽象数据类型: ADT Stack { 数据对象:D={a i:|a i∈ElemSet,i=1…n,n≥0} 数据关系:R1={|a i-1,a i∈D,i=2,…n≥0} 基本操作: init(linklist *L) 操作结果: destroylist(List *L) clearlist(List *L) 初始条件:线性表L已经存在,1≤i≤ListLength(&L) 操作结果:用e返回L中第i个数据元素的值。 insfirst(link h,link s) 初始条件:数据元素e1,e2存在 操作结果:以e1,e2中的姓名项作为判定e1,e2是否相等的依据。 delfirst(link h,link *q) 初始条件:数据元素e1,e2存在 操作结果:以e1,e2中的姓名项(为字符串)的≤来判定e1,e2是否有 ≤的关系。

实验1顺序表和链表基本操作(给学生)

实验一、二:线性表的应用 班级学号姓名 一、实验预备知识 1 复习C++中编写函数的相关内容。 2 复习如何用主函数将多个函数连在一起构成一个C++完整程序。 二、实验目的 1 掌握线性表的顺序和链式存储结构 2 熟练运用线性表在顺序存储方式下的初始化、创建、输出、插入和删除运算 3 熟练运用线性表在链式存储方式下的创建、输出、插入和删除运算 三、实验要求 1 编写初始化并创建线性表和输出线性表的算法。 2 编写对线性表插入和删除运算算法,要判断位置的合法性和溢出问题。 3 编写一个主函数,将上面函数连在一起,构成一个完整的程序。 4将实验源程序调试并运行,写出输入、输出结果,并对结果进行分析。 四、实验步骤 顺序表实验内容: 1.给定的线性表为L=(12,25,7,42,19,38),元素由键盘输入。 2.初始化并建立顺序表。 3.编写顺序表输出算法。(内存中开辟的单元数为8) 4.依次插入3,21,15三个数,分别插入在第4,6和2位置,每插入一次都要输出一次顺序表。 5.删除第5,第3和第12个位置上的元素,每删除一个元素都要输出一次顺序表。 单链表实验内容: 1.给定的线性表为L=(12,25,7,42,19,38),元素由键盘输入。 2.建立一个带表头结点的单链表(前插入法和尾插入法都可以)。 3.编写单链表输出算法。 4.依次插入3,21,15三个数,分别插入在第4,6和12位置,每插入一次都要输出一次单链表。 5.删除第5,第3和第12个位置上的元素,每删除一个元素都要输出一次单链表。 五、实验结果 1.给出程序清单及输入/输出结果。 2.实验过程中遇到的问题、解决方法及心得体会。

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

实验一:线性表逆置(顺序表)实验报告 (一)问题的描述: 实现顺序表的逆置算法 (二)数据结构的设计: 顺序表是线性表的顺序存储形式,因此设计如下数据类型表示线性表: typedef struct { ElemType *elem; /* 存储空间基址*/ int length; /* 当前长度*/ int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */ }SqList; (三)函数功能、参数说明及概要设计: 1.函数Status InitList(SqList *L) 功能说明:实现顺序表L的初始化 算法设计:为顺序表分配一块大小为LIST_INIT_SIZE的储存空间 2.函数int ListLength(SqList L) 功能说明:返回顺序表L长度 算法设计:返回顺序表中的length变量 3.函数Status ListInsert(SqList *L,int i,ElemType e) 功能说明:将元素e插入到顺序表L中的第i个节点 算法设计:判断顺序表是否已满,已满则加空间,未满则继续,将元素e插入到第i个元素之前,并将后面的元素依次往后移 4.函数Status ListTraverse(SqList L,void(*vi)(ElemType*)) 功能说明:依次对L的每个数据元素调用函数vi() 算法设计:依次对L的每个数据元素调用函数vi() 5.函数void Exchange(SqList *L) 功能说明:实现顺序表L的逆置 算法设计:用for循环将顺序表L中的第i个元素依次与第(i+length)个元素交换6.函数void print(ElemType *c) 功能说明:打印元素c 算法设计:打印元素c 2. (四)具体程序的实现

线性表的顺序存储结构定义和基本操作算法实现

#include "" /***********************线性表的顺序存储结构定义*******************/ #define MAX 11 /*线性表可能达到的最大长度值*/ typedef int datatype; typedef struct {datatype data[MAX]; int last;}list; /************************1.线性表的初始化***************************/ void init(list *lp) {lp->last=0;} /************************2.求线性表的长度***************************/ int length(list *lp) { return (lp->last);} /***************3.插入运算,在表第i个位置插入一个值为 x的新元素******/ void insert(list *lp,int i,datatype x) { int j; if(lp->last==MAX-1) printf("Overflow!\n"); /*表已满*/ else if(i<1||i>lp->last+1) printf("Error!\n"); /*插入位置错误*/ else {for(j=lp->last;j>=i;j--) lp->data[j+1]=lp->data[j]; /*数据元素后移*/ lp->data[i]=x; /*插入x */ lp->last++; /*表长度加1*/ } } /***************4.删除运算,在表中删除第i个数据元素***************/ void delete(list *lp,int i) { int j; if(i<1||i>lp->last) /*检查空表及删除位置的合法性*/ printf("The %dth element is not exist!",i); /*不存在第i个元素*/ else {for(j=i+1;j<=lp->last;j++) lp->data[j-1]=lp->data[j]; /*向前移动元素*/ lp->last--; /*表长度减1 */ } } /*****************5.查找运算,在表中查找x数据元素*****************/ int locate(list *lp,datatype x) { int i=lp->last; while(i>0 && lp->data[i]!=x)i--; return i; }

实验1顺序表和链表基本操作(学生)

实验一线性表运算的实现 班级学号姓名 一、实验预备知识 1.复习C中函数的相关内容。 2.复习如何用主函数将多个函数连在一起构成一个C完整程序。 3.复习多文件结构。 二、实验目的 1.掌握线性表的顺序和链式存储结构 2.熟练运用线性表在顺序存储方式下的初始化、创建、输出、插入和删除运算 3.熟练运用线性表在链式存储方式下的创建、输出、插入和删除运算 三、实验要求 1.编写初始化并创建线性表和输出线性表的算法。 2.编写对线性表插入和删除运算算法,要判断位置的合法性和溢出问题。 3.编写有序表的插入和删除运算算法。 4.编写一个主函数,将上面函数连在一起,构成一个完整的程序。 5.将实验源程序调试并运行,写出输入、输出结果,并对结果进行分析。 四、实验内容 顺序表实验内容: 1.给定的线性表为L=(12,25,7,42,19,38),元素由键盘输入。 2.初始化并建立顺序表。(开辟的存储空间大小为8) 3.编写顺序表输出算法。 4.依次插入3,21,15三个数,分别插入在第4,6和2位置,每插入一次都要输出一次顺序表。 5.删除第5,第3和第12个位置上的元素,每删除一个元素都要输出一次顺序表。 6.编写一个排序算法,对线性表中元素从小到大排列。 7.向有序表分别插入20和50,插入后表仍然有序。(修改开辟的存储空间大小为15) 单链表实验内容: 1.给定的线性表为L=(12,25,7,42,19,38),元素由键盘输入。 2.建立一个带表头结点的单链表(前插入法和尾插入法都可以)。 3.编写单链表输出算法。 4.依次插入3,21,15三个数,分别插入在第4,6和12位置,每插入一次都要输出一次单链表。 5.删除第5,第3和第12个位置上的元素,每删除一个元素都要输出一次单链表。 6.编写一个排序算法,对线性表中元素从小到大排列。 7.分别删除值为25和42的元素,删除后表仍然有序。 五、实验结果 给出程序清单及输入/输出结果 六、总结 1.实验过程中遇到的问题及解决方法 2.收获

线性表的顺序储存结构

交通大学《算法与数据结构》课程 实验报告 班级:计算机科学与技术2014级2班 实验项目名称:线性表的顺序储存结构 实验项目性质: 实验所属课程:算法与数据结构 实验室(中心): B01407 指导教师:鲁云平 实验完成时间:2016 年 3 月21 日

一、实验目的 1、实现线性表的顺序存储结构 2、熟悉C++程序的基本结构,掌握程序中的头文件、实现文件和主文件之 间的相互关系及各自的作用 3、熟悉顺序表的基本操作方式,掌握顺序表相关操作的具体实现 二、实验容及要求 对顺序存储的线性表进行一些基本操作。主要包括: (1)插入:操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入 (2)删除:操作方式可分为删除指定元素、删除指定位置的元素等,尝试实现逻辑删除操作。 (3)显示数据 (4)查找:查询指定的元素(可根据某个数据成员完成查询操作) (5)定位操作:定位指定元素的序号 (6)更新:修改指定元素的数据 (7)数据文件的读写操作等。 其它操作可根据具体需要自行补充。 要求线性表采用类的定义,数据对象的类型自行定义。 三、实验设备及软件 VC6.0 四、设计方案

㈠题目 线性表的顺序存储结构 ㈡设计的主要思路 1、新建SeqList.h头文件,定义SeqList模板类 2、设计类数据成员,包括:T *data(用于存放数组)、int maxSize (最大可容表项的项数)、int last(当前已存表项的最后位置) 3、设计类成员函数,主要包括: int search(T& x)const;//搜索x在表中位置,函数返回表项序号 int Locate(int i)const;//定位第i个表项,函数返回表项序号 bool getData(int i,T& x)const;//去第i个表项的值 void setData(int i,T& x)//用x修改第i个表项的值 bool Insert(int i,T& x);//插入x在第i个表项之后 bool Remove(int i,T& x); //删除第i个表项,通过x返回表项的值 bool IsEmpty();//判表空否,空则返回true;否则返回false bool IsFull();//判表满否,满则返回true;否则返回false void input(); //输入 void output();//输出 void ofile();/存储在文件中 void ifile();//读取文件并显示 ㈢主要功能 1、建立新表 2、对表进行插入(指定元素前、后以及指定位置插入)、删除(指定 元素删除及指定位置删除)、修改等操作 3、显示当前操作表的全部容 4、存储在文件中 5、从文件中读取表 五、主要代码 ㈠SeqList.h中的主要代码: 1、类成员声明部分: protected: T *data; //存放数组 int maxSize; //最大可容纳表项

《数据结构》实验一 线性表及其应用

实验一线性表及其应用 一、实验目的 1.熟悉C语言的上机环境,进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21,23,14,5,56,17,31},然后在第i个位置插入元素68。 3.建立一个带头结点的单链表,结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示 1.由于C语言的数组类型也有随机存取的特点,一维数组的机内表示就是顺序结构。因此,可用C语言的一维数组实现线性表的顺序存储。 在此,我们利用C语言的结构体类型定义顺序表: #define MAXSIZE 1024 typedef int elemtype; /* 线性表中存放整型元素*/ typedef struct { elemtype vec[MAXSIZE]; int len; /* 顺序表的长度*/ }sequenlist; 将此结构定义放在一个头文件sqlist.h里,可避免在后面的参考程序中代码重复书写,另外在该头文件里给出顺序表的建立及常量的定义。 2. 注意如何取到第i个元素,在插入过程中注意溢出情况以及数组的下标与位序(顺序表中元素的次序)的区别。 3.单链表的结点结构除数据域外,还含有一个指针域。用C语言描述结点结构如下: typedef int elemtype; typedef struct node

顺序存储结构的线性表

顺序存储结构的线性表 线性表是最常用且比较简单的一种结构,它是由有限个数据元素组成的有序集合,每个数据元素有一个数据项或者含多个数据项。例如26个英文字母表(A,B,……Z)是一个线性表,表中每一个数据元素由单个字母组成数据项。又如表5.0.1也是一个线性表,表中含八个数据元素,每一个数据元素由n个选手在该项目的竞赛成绩组成。 线性表具有如下结构特征: (1)均匀性。即同一线性表的名数据元素的数据类型一致且数据项相同。 (2)有序性。表中数据元素之间的相对位置是线性的,即存在性一的“第一个”和“最后一个”数据元素。除第一个 和最后一个外,其他元素前面均只有一个数据元素(直接前趋)和后面均只有一个数据元素(直接后继)。 按照表中数据元素的存储方式分顺序存储结构和链式存储结构两类线性表。 1、序存储结构 顺序存储结构是指用一组地址连续的存储单元依次线性表的元素,通常用数组实现。数组的物理实现是一块连续的存储空间,它是按首址(表中第1个元素的地址)+位移来访问每一个元素。 设 loc(a[i])-----A数组中元素i的内存地址(c<=i<=d);

loc(b[i,j])----Bo数组中(i,j)元素的内存地址 (c1<=I<=d1,c2<=j<=d2); loc(a[i])=loc(a[c])+(i-c)*la,la-------atype类型的长度; loc(b[i,j]=loc(b[c1,c2])+((d2-c2+1)*(i-c1)+(j-c2))*lb,lb----atype 类型长度; 一维数组按照下标递增的顺序访问表中元素; a[c]->a[c+1]->……->a[d] 二维数按照先行后列的顺序访问表中元素: b[c1,c2]->b[c1,c+1]->……b[c1,d2]->……>b[i-1,d2]->b[i,c2]-> ……->b[d1,d2-1]->b[d1,d2] 在数组中,数据元素的下标间接反映了数据据元素的存储地址。而计算机内存是随机存储取的装置,所以在数组中存取一个数据元素只要通过下标计算它的存储地址就行了,数组中任意一个元素的存取时间都相等。从这个意义上讲,数组的存储存储结构是一个随机存取的结构。 问题是,虽然数组的顺序分配结构比较简单,便于随机访问数组中的任一元素。但如果数组要保持线性表的特征的话(由下标指明元素间的有序性),其增删操作的效率比较低。特别,当数组很大时,插入与删除运算颇为费时。因此,比较小的数组或元素不常变(很少进行插入与删除运算)的数组可用作线性表,而对于大的线性表或元素经常变动的线性表,可以采链式存储结构。 2、链式存储结构

实验一.顺序表验证实验

实验一顺序表操作验证 一、实验目的 ⑴掌握线性表的顺序存储结构; ⑵验证顺序表及其基本操作的实现; ⑶掌握数据结构及算法的程序实现的基本方法。 二、实验内容 ⑴建立含有若干个元素的顺序表; ⑵对已建立的顺序表实现插入、删除、查找等基本操作。 三、设计与编码 (a)本实验用到的理论知识 首先定义顺序表的数据类型——顺序表类SeqList,包括题目要求的插入、删除、查找等基本操作,为便于查看操作结果,设计一个输出函数依次输出顺序表的元素。 (b)算法设计 const int MaxSize=10; template //定义模板类SeqList class SeqList { public: SeqList( ){length=0;} //无参构造函数 SeqList(T a[ ], int n);//有参构造函数 void Insert(int i, T x); //在线性表中第i个位置插入值为x的元素 T Delete(int i); //删除线性表的第i个元素 int Locate(T x ); //按值查找,求线性表中值为x的元素序号 void PrintList( ); //遍历线性表,按序号依次输出各元素 private: T data[MaxSize]; //存放数据元素的数组 int length; //线性表的长度 }; 其次,建立含有n个数据元素的顺序表,即设计构造函数。算法如下:

最后,对建立的顺序表设计插入、删除、查找等基本操作的算法。 ⑴插入算法 ⑵删除算法 ⑶查找算法 (c)编码 #include #include using namespace std;

数据结构实验一顺序表

数据结构实验一 1、实验目的 ?掌握线性表的逻辑特征 ?掌握线性表顺序存储结构的特点,熟练掌握顺序表的基本运算 2、实验内容: 建立顺序表,完成顺序表的基本操作:初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、查找元素、判线性表是否为空; 1.问题描述:利用顺序表,设计一组输入数据(假定为一组整数),能够对顺序表进行如下操作: ?创建一个新的顺序表,实现动态空间分配的初始化; ?根据顺序表结点的位置插入一个新结点(位置插入),也可以根据给定的值进行插入(值插入),形成有序顺序表; ?根据顺序表结点的位置删除一个结点(位置删除),也可以根据给定的值删除对应的第一个结点,或者删除指定值的所有结点(值删除); ?利用最少的空间实现顺序表元素的逆转; ?实现顺序表的各个元素的输出; ?彻底销毁顺序线性表,回收所分配的空间; ?对顺序线性表的所有元素删除,置为空表; ?返回其数据元素个数; ?按序号查找,根据顺序表的特点,可以随机存取,直接可以定位于第i 个结点,查找该元素的值,对查找结果进行返回; ?按值查找,根据给定数据元素的值,只能顺序比较,查找该元素的位置,对查找结果进行返回; ?判断顺序表中是否有元素存在,对判断结果进行返回; .编写主程序,实现对各不同的算法调用。 2.实现要求: ?“初始化算法”的操作结果:构造一个空的顺序线性表。对顺序表的空间进行动态管理,实现动态分配、回收和增加存储空间; ?“位置插入算法”的初始条件:顺序线性表L 已存在,给定的元素位置为i,且1≤i≤ListLength(L)+1 ; 操作结果:在L 中第i 个位置之前插入新的数据元素e,L 的长度加1; ?“位置删除算法”的初始条件:顺序线性表L 已存在,1≤i≤ListLength(L) ; 操作结果:删除L 的第i 个数据元素,并用e 返回其值,L 的长度减1 ; ?“逆转算法”的初始条件:顺序线性表L 已存在; 操作结果:依次对L 的每个数据元素进行交换,为了使用最少的额外空间,对顺序表的元素进行交换; ?“输出算法”的初始条件:顺序线性表L 已存在; 操作结果:依次对L 的每个数据元素进行输出; ?“销毁算法”初始条件:顺序线性表L 已存在;

实验1 顺序表的操作

实验1 顺序表的操作 一、实验要求 1 建立顺序表 2 顺序表的长度并输出顺序表 3 插入元素的位置和元素 4 删除值为x的元素 5 顺序表倒置 6 将顺序表按升序排序 7 将两个顺序有序表A和B合并为一个有序表C 二、源代码 DS.h #include #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 typedef int Status; SqList.h #ifndef SQLIST_H_INCLUDED #define SQLIST_H_INCLUDED #include "DS.h" typedef int ElemType; typedef struct { ElemType *elem; int length; int listsize; }SqList; void menu(); Status InitList_Sq(SqList &L, int n);/*初始化顺序表*/ Status CreateList_Sq(SqList &L);/*建立顺序表*/

void PrintList_Sq(SqList L);/*输出顺序表*/ Status DeleteList_Sq(SqList &L,int i,ElemType &e);/*删除第i个元素*/ Status DeleteListX_Sq(SqList &L,ElemType x);/*删除值为x的元素*/ Status AdjustList_Sq(SqList &L);/*奇数排在偶数之前*/ Status OrderList_sq(SqList &L, int n);/*插入法生成递增有序表*/ void MergeList_Sq(SqList La, SqList Lb, SqList &Lc );/*两个非递减有序表A和B,并把它们合并成一个非递减有序表C*/ #endif // SQLIST_H_INCLUDED SqList.cpp #include "SqList.h" void menu() { printf("\t\t\t 顺序表基本操作\n\n"); printf("\t\t\t1.建立顺序表\n"); printf("\t\t\t2.遍历顺序表\n"); printf("\t\t\t3.删除第i 个元素\n"); printf("\t\t\t4.删除值为x 的元素\n"); printf("\t\t\t5.奇数排在偶数之前\n"); printf("\t\t\t6.插入法生成递增有序表\n"); printf("\t\t\t7.两个非递减有序表La和Lb合并成非递减有序表Lc\n"); printf("\t\t\t0.退出\n\n"); } /*初始化顺序表*/ Status InitList_Sq(SqList &L, int n) { L.elem=(ElemType*)malloc(n*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=n; return OK; } /*建立顺序表*/ Status CreateList_Sq(SqList &L) { int n, i; printf("请输入顺序表长度:"); scanf("%d", &n); if(InitList_Sq(L, n)) {

相关主题
相关文档 最新文档