数据结构实验报告——线性表顺序存储结构[1]

实验报告

课程名称：数据结构实验名称：线性表的顺序存储结构

班级：学生姓名：学号：

指导教师评定：签名:

题目：有两张非递减有序的线性学生表A，B，采用顺序存储结构，两张表合并用c表存，要求C仍为非递减有序的，并删除C中值相同的表。

一、需求分析

⒈本演示程序根据已有的6位学生的信息，实现两张表的合并及删除值相同元素的操作，不需要用户

重新输入学生的信息。

⒉在演示过程序中，用户敲击键盘，即可观看演示结果。

⒊程序执行的命令包括：

（1）构造线性表A （2）构造线性表B （3）求两张表的并（4）删除C中值相同的元素

二、概要设计

⒈为实现上述算法，需要线性表的抽象数据类型：

ADT Stack {

数据对象：D={a

i :|a

i

∈ElemSet,i=1…n,n≥0}

数据关系：R1={

i-1,a

i

>|a

i-1

,a

i

∈D,i=2,…n≥0}

基本操作:

init(list *L)

操作结果：构造一个空的线性表L。

ListLength(List *L)

初始条件：线性表L已经存在

操作结果：返回L中数据元素的个数。

GetElem(List L, int i, ElemType *e)

初始条件：线性表L已经存在，1≤i≤ListLength(&L)

操作结果：用e返回L中第i个数据元素的值。

EqualList(ElemType *e1,ElemType *e2)

初始条件：数据元素e1,e2存在

操作结果：以e1,e2中的姓名项作为判定e1,e2是否相等的依据。

Less_EquaList(ElemType *e1,ElemType *e2)

初始条件：数据元素e1,e2存在

操作结果：以e1,e2中的姓名项(为字符串)的≤来判定e1,e2是否有≤的关系。

LocateElem(List *La,ElemType e,int type)

初始条件：线性表La已经存在

操作结果：判断La中是否有与e相同的元素。

MergeList(List *La,List *Lb,List *Lc)

初始条件：非递减线性表La，Lb已经存在

操作结果：合并La，Lb得到Lc，Lc仍按非递减有序排列。

UnionList(List *La ,List *Lb)

初始条件：线性表La，Lb已经存在

操作结果：将所有在Lb而不在La中的元素插入到La中表尾的位置。

PrintList(List L)

初始条件：线性表L已经存在

操作结果：打印出表L。

ListInsert(List *L, int i, struct STU e)

初始条件：线性表L已经存在，1≤i≤ListLength(&L)+1

操作结果：在表L中第i个位置前插入元素e，L的长度加1。

}ADT List

2. 本程序有三个模块：

⑴主程序模块

void main(){

初始化；

{

接受命令；

显示结果；

｝

｝

⑵线性表单元模块：实现线性表抽象数据类型；

⑶结点结构单元模块：定义线性表中的结点结构。

三、详细设计

⒈元素类型，结点类型

struct STU{

char name[20]; //学生名字、学号、年龄、分数

char stuno[10];

int age;

int score;

};

typedef struct STU ElemType; //元素类型

struct LIST{

ElemType *elem;

int length; //表的长度、大小

int listsize;

};

typedef struct LIST list; //结点类型

2.对抽象数据类型中的部分基本操作的伪码算法如下：

int init(List *L)

{

L→elem=(ElemType *)malloc(sizeof(ElemType)*LIST_INIT_SIZE);

If(!L→elem) exit (OVERFLOW);

L→length=0;

L→listsize= LIST_INIT_SIZE;

Return OK;

}//初始化表

int ListLength(List *L)

{

return L→length;

}//返回表长

void GetElem(List L, int i, ElemType *e)

{

*e=L.elem[i];

} //返回元素

int locateElem(List *La, ElemType e, int type)

{

int I;

switch(type) //确定元素在表中的位置

{

case EQVAL;

for(i=0;i

if(EqualList(&La→elem[i],&e))

return 1;break;

default;

break;

}

return 0;

}

void MergeList(List *La, List *Lb, List *Lc)

{ //将两个表合并成Lc ElemType *pa,*pb,*pc,*pa_last,*pb_last;

Pa=La→elem;pb=Lb→elem;

Lc→Listsize=Lc→length=La→length+Lb→length;

Pc=Lc→elem==(ElemType *)malloc(Lc→listsize*sizeof(ElemType));

if (!Lc→elem) exit(OVERFLOW);

pa_last=La→elem+La→length-1;

pb_last=Lb→elem+Lb→length-1;

while (pa<=pa_last&&pb<=pb_last)

{

if (Less_EqualList(pa,pb)) *pc++=*pa++;

else *pc++=*pb++;

}

while (pa<=pa_last) *pc++=*pa++;

while (pb<=pb_last) *pc++=*pb++;

}

void UnionList(List *La, List *Lb)

{

La_len=ListLength(La);Lb_len=ListLength(Lb);

For(i=0;i

{

GetElem(*Lb,i,&e);

If (!LocateElem(La,e,EQUAL))

ListInsert(La,++La_len,e);

}

}

int ListInset(List *L,int i,struct STU e)

{ //将元素插入表Ｌ中if(i<1||i>L→length+1) return ERROR;

q=&(L→elem[i-1]);

for(p=L→elem[L→length-1];p>=q;p--)

*(p+1)=*p;

*q=e;

++(L→length);

return OK;

}//ListInsert Before i

3.主函数和其他函数的伪码算法

void main()

{

Initialization();//初始化

ReadCommand(cmd);//读入一个操作符

MakeList(La);printList(La);//产生并打印La

MakeList(Lb);printList(Lb);// 产生并打印Lb

OperateList(La,Lb);

}

void Initialization()

{//系统初始化

clrscr();

}

int ReadCommand(cmd)//任意键入一个字符

{

cmd=getch();

return 1;

}

void MakeList(La)

{

ListInsert(&La,i,e);

}

void OperateList(La,Lb)

{

MergeList(&La,&Lb,&Lc);

UnionList(&La,&Lb);

}

4 函数调用关系

main

Initialization MakeList OperateList ReadCommand printList

UnionList MergeList

Less_EqualList

Init ListInsert LocateElem

EqualList

四、调试分析

⒈刚开始输入时，漏掉了一些变量参数的标记"&"，有的则错加了"&"，使得程序运行出来的结果不正

确，使调试程序时费时不少。

⒉程序采用逐个输入的方法创建La,Lb,在元素较多时，会使得程序很庞大，不利于检查错误等。

⒊算法的时空分析

各操作的算法时间复杂度比较合理

init,ListLength,GetElem,EqualList,Less_EqualList为O(1)

LocateElem,ListInsert,printList为O(n),UnionList为O(mn),MergeList为O(n)。

4.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路清晰，使调试也较顺利，

各模块有较好的可重用性。

五、用户手册

⒈本程序的运行环境为windows xp操作系统，执行文件为Exp1Prb1.c；

⒉进入演示程序后，完成编译，连接（即同时按下Ctrl F9）进入演示界面，用户键入任一符号，都

能看完整个演示过程。

六、测试结果

(1)同时键入Ctrl F9，演示为：

-----------------List Demo is running--------------

First is InsertList function

name stuno age score

stu1 100001 80 1000

stu3 100002 80 1000

(2)键入任意字符，演示为：

name stuno age score

stu1 100001 80 1000

stu3 100002 80 1000

stu5 100003 80 1000

List A length now is 3.

(3)键入任意字符，演示为：

name stuno age score

stu2 100001 80 1000

stu4 100002 80 1000

stu6 100001 80 1000

List B length now is 3.

(4)键入任意字符，演示为：

name stuno age score

stu1 100001 80 1000

stu2 100001 80 1000

stu3 100002 80 1000

stu4 100002 80 1000

stu5 100003 80 1000

stu6 100001 80 1000

Second is UnionList function.

Now union List A and List B...

name stuno age score

stu1 100001 80 1000

stu2 100002 80 1000

stu3 100003 80 1000

stu4 100001 80 1000

stu5 100002 80 1000

stu6 100001 80 1000

List A length now is 6.

(5) 键入任意字符，退出演示界面，回到编辑状态。

七、附录：题一源程序

//------头文件

#include

#include

#include

//符号常量

#define ERROR O

#define OK 1

#define EQUAL 1

#define OVERFLOW -1

#define LIST_INIT_SIZE 100//线性表存储空间的初始分配量

#define LISTINCREMENT 10//线性表存储空间的分配增量

//类型声明

struct STU{//定义学生结构体类型，包括姓名，学号，年龄，成绩char name[20];

char stuno[10];

int age;

int score;

}stu[50];

typedef struct STU ElemType;//用ElemType代替学生

struct LIST

{//定义表LIST为结构体类型

ElemType *elem;//存储空间基址

int length;//当前长度

int listsize;//当前分配的存储容量

};

typedef struct LIST List;//用list代表结构体LIST

int init(List *L)

{//构造一个空的线性表

L→elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));

If (!L→elem) exit(OVERFLOW);// 存储分配失败

L→length=0;//空表长度为0

L→listsize=LIST_INIT_SIZE;//初始存储容量

Return ok;

}

int ListLength(List *L)

{//求表L的长度

return L→length;

}

void GetElem(List L, int i, ElemType *e)

{

*e=L.elem[i];

}

int EqualList(ElemType *e1,ElemType *e2)

{//以元素e1,e2中的姓名项是否相等作为判定e1,e2是否相等的标准if (strcmp(e1→name,e2→name)==0)

return 1;

else

return 0;

}

int Less_EqualList(ElemType *e1,ElemType *e2)

{//以姓名（字符串）的≤作为判定e1≤e2的标准

if (strcmp(e1→name,e2→name)<=0)

return 1;

else

return 0;

}

int LocateElem(List *La,ElemType e,int type)

{//判断La中是否有与e符合关系type的元素

int i;

suitch(type)

{

case EQUAL;

for(i=0;i

if (EqualList(&La→elem[i],&e))

return 1;

break;

default;break;

}

return 0;

}

void MergeList(List *La,List *Lb,List *Lc)

{//合并表La,Lb,用Lc存储。已知La,Lb元素值按非递减排列，Lc中值也按非递减排列ElemType *pa,*pb,*pc,*pa_last,*pb_last;

pa=La→elem;pb=Lb→elem;

Lc→listsize=Lc→length=La→length+Lb→length;

Pc=Lc→elem=(ElemType *)malloc(Lc→listsize*sizeof(ElemType));

if (!Lc→elem) exit(OVERFLOW);//存储分配失败

pa_last=La→elem+La→length-1;

pb_last=Lb→elem+Lb→length-1;

while(pa<=pa_last&&pb<=pb_last)

{//合并，Lc元素按非递减排列

if (Less_EqualList(pa,pb)) *pc++=*pa++;

else *pc++=*pb++;

}

while (pa<=pa_last) *pc++=*pa++ //插入La的剩余元素

while (pb<=pb_last) *pc++=*pb++ //插入Lb的剩余元素

}

void UnionList(List *La ,List *Lb)

{//将所有在Lb中而不在La中的元素插入到La中

int La_len,Lb_len;

int i;

ElemType e;

La_len=Listlength(La);Lb_len=Listlength(Lb);//求线性表长度

for(i=0;i

{

GetElem(*Lb,I,&e);

If (!LocateElem(La,e,EQUAL))

ListInsert(La,++La_len,e);

}

}

int printlist(List L)

{//输入表L

int i;

printf("name stuno age score\n");

for (i=0;i

printf("%-cos%s\t%d\t%d\n",L.elem[i].name,L.elem[i].stuno,L.elem[i].age,L.elem[i].sco re);

printf("\n");

}

int ListInsert(List *L,int i,struct STU e)

{//在表L中第i位上插入e

struct STU *p,*q;

if (*i<1||i>L→length+1) return ERROR;//i值不合法

q=&(L→elem[i-1]);

for(p=&L→elem[L→length-1];p>=q;--p)

*(p+1)=*p;

*q=e;

++L→length;

return ok;

}

main

{

struct STU e;//定义结构体变量e

List La,Lb,Lc;//定义结构体变量，即表La,Lb,Lc

Clrscr();

Printf("\n\n--------List Demo is running ----------\n\n");

Printf("First is InsertList function.\n");

init(&La);//创建一个新表La

strcpy(https://www.wendangku.net/doc/9a11797978.html,,"stu1");

strcpy(e.stuno,"100001");

e.age=80;

e.score=1000;

ListInsert(&La,1,e);//在La的第1位上插入stu1的数据元素

strcpy(https://www.wendangku.net/doc/9a11797978.html,,"stu3");

strcpy(e.stuno,"100002");

e.age=80;

e.score=1000;

ListInsert(&La,2,e);//在La的第2位上插入stu3的数据元素

Printlist(La);//输出La

Printf("List A length now is %d.\n\n",La.length);

Getch();

strcpy(https://www.wendangku.net/doc/9a11797978.html,,"stu5");

strcpy(e.stuno,"100003");

e.age=80;

e.score=1000;

ListInsert(&La,3,e);//在表La的第3位上插入stu5的数据表

printlist(La);//输出表La

printf("List A length now is %d.\n\n",La.length);

getch();

init(&Lb);//创建一张新表Lb

strcpy(https://www.wendangku.net/doc/9a11797978.html,,"stu2");

strcpy(e.stuno,"100001");

e.age=80;

e.score=1000;

ListInsert(&Lb,1,e);//在表Lb的第1位上插入stu2的数据

strcpy(https://www.wendangku.net/doc/9a11797978.html,,"stu4");

strcpy(e.stuno,"100002");

e.age=80;

e.score=1000;

ListInsert(&Lb,2,e);// 在表Lb的第2位上插入stu4的数据

strcpy(https://www.wendangku.net/doc/9a11797978.html,,"stu6");

strcpy(e.stuno,"100001");

e.age=80;

e.score=1000;

ListInsert(&Lb,3,e);// 在表Lb的第3位上插入stu6的数据

printlist(Lb);//输出表Lb

printf("List B length now is %d.\n\n",Lb.length);

getch();

MergeList(&La,&Lb,&Lc);//合并表La,Lb,用表Lc存储（非递减有序）Printlist(Lc);//输出表Lc

getch();

printf("Second is UnionList function.\n");

printf("Now Union List A and List B---\n");

UnionLIst(&La,&Lb);//合并La,Lb，并删除值相同的元素，用La存储Printlist(La);//输出La

Printf("List A length now is %d.\n\n",La.length);

getch();

}

实验一.顺序表验证实验

线性表 实验一顺序表操作验证 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;

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

北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验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++;

(完整版)数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 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 始终指向生成的单链表的最后一个节点

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

数据结构实验报告图实验

图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10;

template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif MGraph.cpp

#include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) {

实验报告一顺序表的操作

《数据结构》实验报告一 系别：班级： 学号：姓名： 日期：指导教师： 一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 从键盘输入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;

线性表的顺序储存结构

交通大学《算法与数据结构》课程 实验报告 班级：计算机科学与技术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.熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。 2.通过编程、上机调试，进一步理解线性表的基本概念，东运用C语言实现线性表基本操作。 3.熟练掌握线性表的综合应用问题。 【实验内容】 1、一个线性表有n个元素（n-MAXSIZE.MAXSIZE指线性表的最大长度），且递增有。现有一元素x要插入到线性表的适当位置上，并保持线性表原有的顺序不变。设计程序实现。要求：采用顺序存储表示实现；采用链式存储表示方法实现：比较两种方法的优劣。 2.从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。 要求： ①指定的值x由键盘输入； ②程序能处理空链表的情况。 3.设有头结点的单链表，编程对表中的任意值只保留一个结点，删除其余值相同的结点。 要求： ①该算法用函数（非主函数)实现； ②在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。LinkedList Exchange（LinkedList HEAD,p) //HEAD是单链表头结点的指针，p是链表中的一个结点。本算法将p所指结点与其后 继结点交换。 （q=head->next；//q是工作指针，指向链表中当前待处理结点。 pre=head；//pre是前驱结点指针，指向q的前驱。 while（q'=null &&q1=p)(pre=q；q=q->next；]/未到p结点，后移指针。 if（p->next==null)printf(“p无后继结点\n”）；/p是链表中最后一个结点，无后继。 else/处理p和后继结点交换 （q=p->next；//暂存p的后继。 pre->next=q://p前驱结点的后继指向p的后继。 p->next=q->next；//p的后继指向原p后继的后继。 q->next=p：//原p后继的后继指针指向p。} }//算法结束。 4.已知非空单链表第一个结点由head指出，请写一算法，交换p所指结点与其下一个结点在链表中的位置。 要求：

数据结构图的遍历实验报告

实验项目名称：图的遍历 一、实验目的 应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。 二、实验容 问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。 三、实验仪器与设备 计算机，Code::Blocks。 四、实验原理 用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。 五、实验程序及结果 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include #include #include #include

typedef struct ArCell{ int adj; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,char* v) { int c = -1,i; for(i=0;ivexnum;i++) if(strcmp(v,G->vexs[i].name)==0) { c=i; break;} return c;} MGraph * CreatUDN(MGraph *G)//初始化图，接受用户输入{ int i,j,k,w; char v1[20],v2[20]; printf("请输入图的顶点数,弧数:"); scanf("%d%d",&G->vexnum,&G->arcnum);

实验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．实验过程中遇到的问题、解决方法及心得体会。

数据结构实验报告图实验

邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph（DataType a[], int n, int e）; ~MGraph（）{ void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; }

int vertexNum, arcNum; }; #endif MGraph.cpp #include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: " cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } }

实验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．收获

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

#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;

实验一.顺序表验证实验

实验一顺序表操作验证 一、实验目的 ⑴掌握线性表的顺序存储结构； ⑵验证顺序表及其基本操作的实现； ⑶掌握数据结构及算法的程序实现的基本方法。 二、实验内容 ⑴建立含有若干个元素的顺序表； ⑵对已建立的顺序表实现插入、删除、查找等基本操作。 三、设计与编码 (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;

顺序存储结构线性表基本操作 纯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

数据结构线性表的应用实验报告

实验报告 课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________PC机___________________ 系别_____电子信息与通信学院___ 专业________ ___ 班级/学号______ __ 学生姓名______ ___________ 实验日期_______________________ 成绩_______________________ 指导教师_______________________

实验一.线性表的应用 1.实验目的：掌握线性链表的存储、运算及应用。利用链 表实现一元多项式计算。 2.实验内容： 1)编写函数，实现用链表结构建立多项式； 2)编写函数，实现多项式的加法运算； 3)编写函数，实现多项式的显示； 4)测试：编写主函数，它定义并建立两个多项式，显示 两个多项式，然后将它们相加并显示结果。变换测试用的多项式，检查程序的执行结果。 选做内容：修改程序，选择实现以下功能： 5)多项式求值：编写一个函数，根据给定的x值计算并 返回多项式f(x)的值。测试该函数（从终端输入一个x的值，调用该函数并显示返回结果）。 6)多项式相减：编写一个函数，求两个多项式相减的多 项式。 7)多项式相乘：编写一个函数，求两个多项式的乘积多 项式。 3.算法说明： 1)多项式的建立、显示和相加算法见讲义。可修改显示 函数，使输出的多项式更符合表达规范。

2)多项式减法：同次项的系数相减（缺项的系数是0）。 例如a(x)=-5x2+2x+3，b(x)= -4x3+3x，则a(x)-b(x) =4x3-5x2-x+3。提示：a(x)-b(x) = a(x)+(-b(x))。 3)多项式乘法：两个多项式的相乘是“系数相乘，指数 相加”。算法思想是用一个多项式中的各项分别与另 一个多项式相乘，形成多个多项式，再将它们累加在 一起。例如，a(x)=-5x2+2x+3，b(x)=-4x3+3x，则 a(x)*b(x) = (-4x3)*(-5x2+2x+3)+(3x)*(-5x2+2x+3) = (20x5-8x4-12x3) + (-15x3+6x2+9x) = 20x5-8x4-27x3+6x2+9x。 4.实验步骤： 根据实验报告的要求，我对文件夹里的C文件进行了丰 富和修改，步骤如下： 链表结构建立多项式： typedef struct polynode { float coef; //系数 int exp; //指数 struct polynode *next; //下一结点指针 } PNode; 编写函数，实现多项式的加法运算； PNode * PolyAdd (PNode *f1, PNode *f2) //实现加法功能。

数据结构实验报告无向图

《数据结构》实验报告 ◎实验题目: 无向图的建立与遍历 ◎实验目的：掌握无向图的邻接链表存储，熟悉无向图的广度与深度优先遍历。 ◎实验内容：对一个无向图以邻接链表存储，分别以深度、广度优先非递归遍历输出。 一、需求分析 1.本演示程序中，输入的形式为无向图的邻接链表形式，首先输入该无向图的顶点数和边数，接着输入顶点信息，再输入每个边的顶点对应序号。 2.该无向图以深度、广度优先遍历输出。 3.本程序可以实现无向图的邻接链表存储，并以深度、广度优先非递归遍历输出。 4.程序执行的命令包括：（1）建立一个无向图的邻接链表存储（2）以深度优先遍历输出（3）以广度优先遍历输出（4）结束 5.测试数据： 顶点数和边数：6,5 顶点信息：a b c d e f 边的顶点对应序号： 0,1 0,2 0,3 2,4 3,4 深度优先遍历输出： a d e c b f 广度优先遍历输出： a d c b e f 二概要设计 为了实现上述操作，应以邻接链表为存储结构。 1.基本操作： void createalgraph(algraph &g) 创建无向图的邻接链表存储 void dfstraverseal(algraph &g,int v)

以深度优先遍历输出 void bfstraverseal(algraph &g,int v) 以广度优先遍历输出 2.本程序包含四个模块： （1）主程序模块 （2）无向图的邻接链表存储模块 （3）深度优先遍历输出模块 （4）广度优先遍历输出模块 3.模块调用图： 三详细设计 1.元素类型，结点类型和指针类型：typedef struct node { int adjvex; struct node *next; }edgenode; typedef struct vnode { char vertex; edgenode *firstedge; }vertxnode; typedef vertxnode Adjlist[maxvernum]; typedef struct { Adjlist adjlist; int n,e; }algraph; edgenode *s; edgenode *stack[maxvernum],*p; 2.每个模块的分析： （1）主程序模块 int main()

实验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)) {