搜档网
当前位置:搜档网 › 数据结构实验一线性表的顺序存储结构

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

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

实验一:线性表的顺序存储结构实验学时:2

实验类型:验证

一、实验目的:

1. 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现;

2. 以线性表的各种操作(建立、插入、删除等)的实现为重点;

3. 掌握线性表的动态分配顺序存储结构的定义和基本操作的实现;

二、实验内容:

1.输入一组整型数据,建立顺序表。

2.实现该线性表的删除。

3、实现该线性表的插入。

4.实现线性表中数据的显示。

5.实现线性表数据的查找和定位

5、编写一个主函数,调试上述算法。

三、实验原理、方法和手段

1.根据实验内容编程,上机调试、得出正确的运行程序。

2. 编译运行程序,观察运行情况和输出结果。

3. 写出实验报告(包括源程序和运行结果)。

四、实验条件

运行Visual c++的微机一台

五、实验步骤(程序清单):

(一)、程序代码:

#include"stdafx.h"

#include

using namespace std;

typedef int elemtype;

struct list

{

elemtype *p;

int size;

int maxsize;

};

void buildlist(list &a,int b)/*建立顺序表*/

{

if(b<=0)

{

cout<<"数据有误" <

}

a.p=new elemtype[b];

if(a.p==NULL)

{

cout<<"动态可分配的空间用完,退出运行!"<

}

a.size=0;

a.maxsize=b;

}

void clearlist(list &a)/*清空线性表*/

{

if(a.p!=NULL)

{

delete []a.p;

a.p=NULL;

}

a.maxsize =0;

a.size=0;

}

bool insertlist(list &a,int pos,elemtype b)/*向线性表中按给定的位置插入一个元素*/ {

int i;

if(pos<=0||pos-1>a.size)

{

cout<<"位置无效" <

return false;

}

if(a.maxsize<=a.size)

{

a.p=(elemtype*)realloc(a.p,2*a.maxsize *sizeof(b));

a.maxsize=2*a.maxsize;

}

for( i=a.size;i>=pos;i--)

a.p[i]=a.p[i-1];

a.p[i]=b;

a.size++;

return true;

}

bool deletelist(list &a,int pos)/*向线性表中按给定的位置删除一个元素*/

{

if(a.size==0)

{

cout<<"线性表为空,删除无效!"<

return false;

}

if(pos<=0||pos>a.size)

{

cout<<"位置无效" <

return false;

}

for(int i=pos-1;i

a.p[i]=a.p[i+1];

a.size--;

if(float(a.size)10)

{

a.p=(elemtype*)realloc(a.p,a.maxsize*0.5*sizeof(*(a.p)));

a.maxsize=a.maxsize*0.5;

}

return true;

}

bool getlist(list a,int pos,elemtype &item)/*得到线性表中指定位置的元素*/

{

if(pos<=0||pos>a.size)

{

cout<<"位置无效" <

return false;

}

item=a.p[pos-1];

return true;

}

int findlist(list a,elemtype b)/*从线性表中查找具有给定值的第个元素*/

{

for(int i=0;i

if(a.p[i]==b)

return i+1;

return 0;

}

void display(list a)/*线性表中数据的显示*/

{

cout<<"顺序表元素个数为:"<

for(int i=0;i

cout<

cout<

}

void main()

{

list L;

int i=10;

int pos;

elemtype a,b,c;

buildlist(L,5);

for(int j=0;j<10;j++)

{

insertlist(L,j+1,i);

i--;

}

display(L);cout<

cout<<"一、插入操作:"<

cout<<"位置:";cin>>pos;

cout<<"数据:";cin>>a;

if(insertlist(L,pos,a))

cout<<"插入成功"<

else

cout<<"插入失败"<

display(L);cout<

cout<<"二、删除操作:"<

cout<<"位置:";cin>>pos;

if(deletelist(L,pos))

cout<<"删除成功"<

else

cout<<"删除失败"<

display(L);cout<

cout<<"三、定位操作:"<

cout<<"位置:";cin>>pos;

if(getlist(L,pos,b))

cout<<"该位置数据为"<

else

cout<<"定位失败"<

cout<<"四、查找操作:"<

cout<<"数据:";cin>>c;

if(findlist(L,c))

cout<<"线性表中第一个等于该数据的位置为"<

else

cout<<"线性表中没有等于该数据的元素"<

clearlist(L);

}

(二)、程序运行结果

六、实验分析与总结:

通过本次实验,我发现了自己身上很多的不足:1.不知道什么时候才需要将函数的返回类型弄成bool类型;2.在编写函数体的时候,对排除非法情况考虑不周;3.对申请、追加及删除动态空间的语法不熟悉;4.没有思路对算法进行优化,例如,不知道怎样将所申请的动态空间适当缩小或放大。findlist函数存在缺陷:给定一个数据,不能得到线性表中所有与这个数据相等的元素的位置。

此次实验,我基本达到了实验的目的,进一步熟悉了相关知识点。但是,做出此次实验花费了太多的时间,在下一次实验之前应做好相关准备,提高实验效率。

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

实验项目名称:线性表的顺序存储结构上的基本运算 (所属课程:数据结构--用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;

数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1.实验目的 (1)掌握使用Visual C++ 6.0上机调试程序的基本方法; (2)掌握线性表的基本操作:初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2.实验要求 (1)认真阅读和掌握和本实验相关的教材内容。 (2)认真阅读和掌握本章相关内容的程序。 (3)上机运行程序。 (4)保存和打印出程序的运行结果,并结合程序进行分析。 (5)按照你对线性表的操作需要,重新改写主程序并运行,打印出文件清单和运行结果 实验代码: 1)头文件模块 #include iostream.h>//头文件 #include//库头文件-----动态分配内存空间 typedef int elemtype;//定义数据域的类型 typedef struct linknode//定义结点类型 { elemtype data;//定义数据域 struct linknode *next;//定义结点指针 }nodetype; 2)创建单链表

nodetype *create()//建立单链表,由用户输入各结点data域之值,//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"<> d; if(d==0) break;//以0表示输入结束 if(i==1)//建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));//表示指针h h->data=d;h->next=NULL;t=h;//h是头指针 } else//建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t始终指向生成的单链表的最后一个节点

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

昆明理工大学信息工程与自动化学院学生实验报告 (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 } 四.程序运行结果:

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无定义。

线性表的顺序储存结构

重庆交通大学《算法与数据结构》课程 实验报告 班级:计算机科学与技术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_线性表的基本操作

实验1 线性表的基本操作 一、需求分析 目的: 掌握线性表运算与存储概念,并对线性表进行基本操作。 1.初始化线性表; 2.向链表中特定位置插入数据; 3.删除链表中特定的数据; 4.查找链表中的容; 5.销毁单链表释放空间; 二、概要设计 ●基础题 主要函数: 初始化线性表InitList(List* L,int ms) 向顺序表指定位置插入元素InsertList(List* L,int item,int rc)删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2(List* L,int rc) 查找顺序表中的元素 FindList(List L,int item) 输出顺序表元素OutputList(List L) 实验步骤: 1,初始化顺序表 2,调用插入函数 3,在顺序表中查找指定的元素 4,在顺序表中删除指定的元素 5,在顺序表中删除指定位置的元素 6,遍历并输出顺序表 ●提高题

要求以较高的效率实现删除线性表中元素值在x到y(x和y自定义)之间的所有元素 方法: 按顺序取出元素并与x、y比较,若小于x且大于y,则存进新表中。 编程实现将两个有序的线性表进行合并,要求同样的数据元素只出现一次。 方法: 分别按顺序取出L1,L2的元素并进行比较,若相等则将L1元素放进L中,否则将L 1,L2元素按顺序放进L。 本程序主要包含7个函数 主函数main() 初始化线性表InitList(List* L,int ms) 向顺序表指定位置插入元素InsertList(List* L,int item,int rc)删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2(List* L,int rc) 查找顺序表中的元素 FindList(List L,int item) 输出顺序表元素OutputList(List L) 提高题的程序 void Combine(List* L1,List* L2,List* L) void DeleteList3(List* L,int x,int y) 二、详细设计 初始化线性表InitList(List* L,int ms) void InitList(List* L,int ms) { L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); L->size=0; L->MAXSIZE=LIST_INIT_SIZE;

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

南昌航空大学实验报告 课程名称:数据结构实验名称:实验一线性表的链式存储结构班级: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是否有 ≤的关系。

线性表的顺序储存结构

交通大学《算法与数据结构》课程 实验报告 班级:计算机科学与技术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; //最大可容纳表项

线性表的顺序存储结构和实现

石家庄经济学院 实验报告 学院: 专业: 计算机 班级: 学号: 姓名: 信息工程学院计算机实验中心制

实验题目:线性表的顺序存储结构和实现 实验室:机房4 设备编号:10 完成日期:2012年03月25号 一、实验内容 1.熟悉C 语言的上机环境,掌握C 语言的基本结构。 2.会定义线性表的顺序存储结构。 3.熟悉对顺序表的一些基本操作(建表、插入、删除等)和具体的函数定义。 二、实验目的 掌握顺序存储结构的特点,了解、掌握并实现顺序表的常用的基本算法。 三、实验的内容及完成情况 1. 需求分析 (1)线性表的抽象数据类型ADT的描述及实现。 本实验实现使用Visual c++6.0实现线性表顺序存储结构的表示及操作。具体实现要求: (2)完成对线性表顺序存储结构的表示和实现。 (3)实现对线性表的建立和初始化。 (4)实现对线性表插入和删除部分元素。 2.概要设计 抽象数据类型线性表的定义: ADT LIST{ 抽象对象:D={ai|ai<-Elemset,i=1,2,…,n,n>=0} 数据关系:R1={

数据结构实验一题目一线性表实验报告

北京邮电大学电信工程学院 数据结构实验报告 实验名称:实验1——线性表 学生姓名: 班级: 班内序号: 学号: 日期: 1.实验要求 1、实验目的:熟悉C++语言的基本编程方法,掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容: 题目1: 线性表的基本功能: 1、构造:使用头插法、尾插法两种方法 2、插入:要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他:可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 带头结点的单链表

2.2 关键算法分析 1.头插法 a、伪代码实现:在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中b、代码实现: Linklist::Linklist(int a[],int n)//头插法 {front=new Node; front->next=NULL; for(int i=n-1;i>=0;i--) {Node*s=new Node; s->data=a[i]; s->next=front->next; front->next=s; } } 2、尾插法

a、伪代码实现:a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)//尾插法 {front=new Node; Node*r=front; for(int i=0;idata=a[i]; r->next=s; r=s; } r->next=NULL; } 时间复杂度:O(n) 3、按位查找 a、伪代码实现: 初始化工作指针p和计数器j,p指向第一个结点,j=1 循环以下操作,直到p为空或者j等于1 b1:p指向下一个结点 b2:j加1 若p为空,说明第i个元素不存在,抛出异常 否则,说明p指向的元素就是所查找的元素,返回元素地址 b、代码实现 Node* Linklist::Get(int i)//得到指向第i个数的指针 {Node*p=front->next; int j=1; while(p&&j!=i)//p非空且j不等于i,指针后移 {p=p->next; j++;

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

实验一:线性表逆置(顺序表)实验报告 (一)问题的描述: 实现顺序表的逆置算法 (二)数据结构的设计: 顺序表是线性表的顺序存储形式,因此设计如下数据类型表示线性表: 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. (四)具体程序的实现

哈工大 数据结构 实验一 线性表的实验

哈尔滨工业大学计算机科学与技术学院 实验报告 课程名称:数据结构与算法 课程类型:必修 实验项目名称:线性表实验 实验题目:算术表达式求值 班级:0903201 学号:1090320110 姓名:王岳

一、实验目的 二、实验要求及实验环境 三、设计思想(本程序中的用到的所有数据类型的定义,主程序的流程图及各程序模块之间的调用关系) 1.逻辑设计 2.物理设计 四、测试结果 五、系统不足与经验体会 六、附录:源代码(带注释) #include using namespace std; template class stack{ private: elementtype ss[512]; int top; public: stack() { this -> top =0; } void null() { this -> top =0; } bool empty() { if (this -> top ==0) return true; else return false; } elementtype pop() { if (this -> empty()) printf("error:empty!!!\n");

else { this -> top--; return this -> ss[this -> top + 1]; } } void push(elementtype x) { if (this -> top == 511) printf("error:full!!!\n"); else { this -> top++; this -> ss[this -> top] = x; } } }; void change(int &i,int &j,double *a,char *input,stack &s){//change front to back char o,p; bool fu=true; while(true){ o=cin.peek(); if((o<'('||o>'9')&&o!='\n') {o=getchar();fu=false; continue;} else if(o>='0'&&o<='9') {scanf("%lf",&a[i]); input[j]=i+'0';i++;j++; } else if(o=='(') {o=getchar();s.push(o);fu=true;continue;} else if(o==')') { o=getchar(); for(;!s.empty();){ input[j]=s.pop();j++; if(input[j-1]=='(') {j--;break;} } } else if(o=='*'||o=='/'){ o=getchar(); for(;!s.empty();){ p=s.pop(); if(p=='*'||p=='/') {input[j]=p;j++;} else {s.push(p);break;} } s.push(o); } else if(o=='+'||o=='-'){ o=getchar(); if(fu) {a[i]=0;input[j]=i+'0';i++;j++;} for(;!s.empty();){ p=s.pop(); if(p!='(') {input[j]=p;j++;} else {s.push(p);break;}

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

实验一线性表及其应用 一、实验目的 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

线性表顺序存储实现、插入、删除操作

#include #include #define list_init_size 100 #define listincrement 10 #define ok 1 #define overflow -1 #define elemtype int #define error -1 elemtype *q; elemtype *p; typedef struct{ elemtype *elem; int length; int listsize; }sqlist; int initlist_sq(sqlist &l)//线性表动态分配存储结构// { l.elem=(elemtype*)malloc(list_init_size*sizeof(elemtype)); if(!l.elem) { cout<<"the list have no space"<>m;

顺序存储结构线性表基本操作 纯C语言实现

/////////////////////////////////////////////////////////// //--------------------------------------------------------- // 顺序存储结构线性表基本操作纯C语言实现 // // a simple example of Sq_List by C language // // by wangweinoo1[PG] //--------------------------------------------------------- /////////////////////////////////////////////////////////// #include #include //以下为函数运行结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define LIST_INIT_SIZE 5 //线性表存储空间的初始分配量 #define LISTINCREMENT 1 //线性表存储空间分配增量 typedef int Status; //函数类型,其值为为函数结果状态代码 typedef int ElemType; //假设数据元素为整型 typedef struct { ElemType*elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量 }Sqlist; //实现线性表的顺序存储结构的类型定义 static Sqlist L;//为了引用方便,定义为全局变量 static ElemType element; /////////////////////////////////////// //函数名:InitList() //参数:SqList L

数据结构实验一 实验报告

班级::学号: 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义; 2、掌握线性表的基本操作,如建立、查找、插入和删除等。 二、实验容 定义一个包含学生信息(学号,,成绩)的顺序表和链表(二选一),使其具有如下功能: (1) 根据指定学生个数,逐个输入学生信息; (2) 逐个显示学生表中所有学生的相关信息; (3) 根据进行查找,返回此学生的学号和成绩; (4) 根据指定的位置可返回相应的学生信息(学号,,成绩); (5) 给定一个学生信息,插入到表中指定的位置; (6) 删除指定位置的学生记录; (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include #include #include #include #define OK 1 #define ERROR 0 #define OVERFLOW -2

typedef int Status; // 定义函数返回值类型 typedef struct { char num[10]; // 学号 char name[20]; // double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK;

数据结构实验一顺序表

数据结构实验一 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 已存在;

相关主题