数据结构 线性表的应用实验报告
实验报告
课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________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) //实现加法功能。{ //实现两多项式（头指针分别为f1和f2）相加，返回和
多项式f3=f1+f2。
PNode *pa=f1->next,*pb=f2->next,*pc,*f3,*q;
int exp;
float coef;
f3=(PNode *)malloc(sizeof(PNode)); //建立头指针
f3->exp=-1; //对头指针初始化
f3->next=f3;
pc=f3; //将pc指向头指针
while (pa->exp!=-1 || pb->exp!=-1) // 返回头指针时，跳出循环
{
if (pa->exp>pb->exp)
{
exp=pa->exp;
coef=pa->coef;
pa=pa->next;
}
else if (pa->exp
{
exp=pb->exp;
coef=pb->coef;
pb=pb->next;
}
else
{
exp=pa->exp;
coef=pa->coef+pb->coef;
pa=pa->next;
pb=pb->next;
}
if (coef!=0)
{
q=(PNode *)malloc(sizeof(PNode)); //建立新的q指针存放负指数的指针
q->exp=exp;
q->coef=coef; //将q插入链表中
q->next=pc->next;
pc->next=q;
pc=q;
}
}
return f3; //返回
}
实现多项式的显示；
void ShowPloy(PNode *h)
//用if语句判断，当指数为0是，只输出系数；当指数为1时，输出系数和X；当系数为1时，输出X 和指数。
{
h=paixu(h); //整理函数，使之降幂排列
PNode *p=h->next;
if(p==h)
{
printf("表达式为空\n");
return;
}
if(p->coef==1)
printf("x^%d",p->exp); //用if语句判断，若输出x^o和x^1值为0和1 直接输出数据。 else if(p->exp==1)
printf("%gx", p->coef);
else if(p->exp==0)
printf("%g", p->coef);
else
printf("%gx^%d", p->coef, p->exp);
p=p->next;
while (p!=h)
{
if(p->coef>0)
printf("+"); //系数为负，不用输出加号
if(p->coef==1)
printf("x^%d",p->exp);
else if(p->exp==1)
printf("%gx", p->coef);
else if(p->exp==0)
printf("%g", p->coef);
else
printf("%gx^%d", p->coef, p->exp);
p=p->next;
}
printf("\n");
}
主函数
void main()
{
PNode *F1,*F2,*F3;
float x;
F1=CreatPoly();
F2=CreatPoly();
printf("\nf1(x)=");ShowPloy(F1);
printf("\nf2(x)=");ShowPloy(F2);
F3=PolyAdd(F1,F2);
F3=paixu(F3);
printf("\nf1+f2=:");
ShowPloy(F3);
F3=PolySub(F1,F2);
printf("\nf1-f2=:");
ShowPloy(F3);
F3=PolyMult(F1,F2);
printf("\nf1*f2=:");
ShowPloy(F3);
printf("\nx的值为: ");
scanf("%f", &x);
printf("\nf1(x=%.3f)=%.3f\n",x,PolyValue(F1,x) );
}
多项式求值
double PolyValue(PNode *h, float x) {
//编写算法，求以h为头指针的多项式在x点的值并返回该值。
double f=0.0;
//求出f=f(x);
PNode *pa;
h=paixu(h);
pa=h->next;
while(pa->exp!=-1) //使用f+=coef*pow，返回f
{
f+=(pa->coef)*pow(x,pa->exp);
pa=pa->next;
}
return f;
}
多项式相减
PNode * PolySub(PNode *f1,PNode *f2)
{//编写此算法，实现两多项式（头指针分别为f1和f2）相减，返回差多项式f3=f1-f2。
PNode *pa=f1->next,*pb=f2->next,*pc,*f3,*q,*head;
f3=(PNode *)malloc(sizeof(PNode)); //建立头指针
f3->exp=-1; //头指针的初始化
f3->next=f3;
pc=f3; //pc指向头指针,便于操作。
while(pb->exp!=-1) //返回头指针时，跳出循环。
{
q=(PNode *)malloc(sizeof(PNode)); //建立新的q 指针存放负指数的指针
q->coef=pb->coef*(-1);
q->exp=pb->exp; //将q插入链表中
q->next=pc->next;
pc->next=q;
pc=q;
pb=pb->next;
}
head=PolyAdd(f1,f3); //调用加法函数做减法
return head; //返回头指针
}
多项式相乘
PNode * PolyMult(PNode *f1,PNode *f2)
{//实现两多项式（头指针分别为f1和f2）相乘，返回乘积多项式f3=f1*f2。
PNode *pa=f1->next,*pb=f2->next,*pc,*u,*head;
int exp;
float coef;
head=(PNode *)malloc(sizeof(PNode));
head->exp=-1;
head->next=head;
pc=head;
while(pa->exp!=-1) //多项式相乘，录入u指针，查到头指针。
{
while(pb->exp!=-1)
{
coef=pa->coef*pb->coef;
exp=pa->exp+pb->exp;
u=(PNode *)malloc(sizeof(PNode));
u->coef=coef;
u->exp=exp;
u->next=pc->next;
pc->next=u;
pc=u;
pb=pb->next;
}
pb=pb->next;
pa=pa->next;
}
return head; //返回头指针
}
程序运行截图
测试成功~！
程序完整源代码如下：
#include
#include
#include
typedef struct polynode
{ float coef; //系数
int exp; //指数
struct polynode *next; //下一结点指针
} PNode;
PNode * paixu(PNode *f) //将多项式降幂排列
{
PNode *p,*q,*r,*p0,*q0;
p=f->next;
q=p->next;
p0=f;
q0=p;
while(p->exp!=-1) //p为q的前驱，q与p指数指数值进行比较，
{
while(q->exp!=-1) //q为头指针推出循环，q移动一圈
{
if(p->exp>q->exp) //比较，若p大于q则q后移
{
q0=q;
q=q->next;
}
else if(p->exp
{
r=q->next;
q->next=p0->next;
q0->next=r;
p0->next=q;
p=q;
q=r;
}
else if(p->exp==q->exp) //若相等，p的coef 与q 的相加，然后删除q节点，释放q的空间
{
p->coef+=q->coef;
q0->next=q->next;
q=q->next;
}
}
p0=p;
p=p->next;
q=p->next;
q0=p;
}
return f;
}
void ShowPloy(PNode *h)
//用if语句判断，当指数为0是，只输出系数；当指数为1时，输出系数和X；当系数为1时，输出X和指数。
{
h=paixu(h); //整理函数，使之降幂排列
PNode *p=h->next;
if(p==h)
{
printf("表达式为空\n");
return;
}
if(p->coef==1)
printf("x^%d",p->exp); //用if语句判断，若输出x^o和x^1值为0和1 直接输出数据。
else if(p->exp==1)
printf("%gx", p->coef);
else if(p->exp==0)
printf("%g", p->coef);
else
printf("%gx^%d", p->coef, p->exp);
p=p->next;
while (p!=h)
{
if(p->coef>0)
printf("+"); //系数为负，不用输出加号
if(p->coef==1)
printf("x^%d",p->exp);
else if(p->exp==1)
printf("%gx", p->coef);
else if(p->exp==0)
printf("%g", p->coef);
else
printf("%gx^%d", p->coef, p->exp);
p=p->next;
}
printf("\n");
}
PNode * CreatPoly() //建立多项式链表，返回头指针
{
PNode * head, *p, *s;
int i,n;
head=(PNode *)malloc(sizeof(PNode));
head->exp=-1;
p=head;
printf("多项式的项数为: ");
scanf("%d",&n);
for(i=1;i<=n; i++)
{
s=(PNode *)malloc(sizeof(PNode));
printf("请输入多项式第%d项的系数和指数（用逗号隔开）: ",i);
scanf("%g,%d",&s->coef,&s->exp);
p->next=s;
p=s;
}
p->next=head;
return head;
}
void FreePoly(PNode *h)
{
//编写此算法，将以h为头指针的多项式的链表结点逐个释放。
PNode *p,*q;
p=h->next;
while(p->exp)!+-1;
{
q=p->next;
free(p);
p=q;
}
free(h);
return;
}
//Free函数用于销毁链表，最后指向头指针，跳出循环并释放头指针。
PNode * PolyAdd (PNode *f1, PNode *f2) //实现加法功能。{ //实现两多项式（头指针分别为f1和f2）相加，返回和多项式f3=f1+f2。
PNode *pa=f1->next,*pb=f2->next,*pc,*f3,*q;
int exp;
float coef;
f3=(PNode *)malloc(sizeof(PNode)); //建立头指针
f3->exp=-1; //对头指针初始化
f3->next=f3;
pc=f3; //将pc指向头指针
while (pa->exp!=-1 || pb->exp!=-1) // 返回头指针时，跳出循环
{
if (pa->exp>pb->exp)
{
exp=pa->exp;
coef=pa->coef;
pa=pa->next;
}
else if (pa->exp
{
exp=pb->exp;
coef=pb->coef;
pb=pb->next;
}
else
{
exp=pa->exp;
coef=pa->coef+pb->coef;
pa=pa->next;
pb=pb->next;
}
if (coef!=0)
{
q=(PNode *)malloc(sizeof(PNode)); //建立新的q指针存放负指数的指针
q->exp=exp;
q->coef=coef; //将q插入链表中
q->next=pc->next;
pc->next=q;
pc=q;
}
}
return f3; //返回
}
PNode * PolySub(PNode *f1,PNode *f2)
{//编写此算法，实现两多项式（头指针分别为f1和f2）相减，
数据结构实验报告全集
数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include
nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"<
数据结构实验报告格式
《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时）
数据结构试题及答案
数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C ） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ） A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放
该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。 10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与（ A ）的表示等价。 A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为（ C ） for (int i=0;i 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 习题二 一、选择题 1．在一个长度为n的顺序表中删除第i个元素（0＜i 数据结构顺序表的主要代码（LIZHULIN） 1．/***有头结点的单链表的初始化、建立（表头插入、表尾插入）、求长度、插入、删除、输出***/ /***********单链表的初始化、建立、输出*****************/ #include 实验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; 填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/ 实验报告——线性表应用一、实验目的 用单链表储存一元多项式，并实现两个多项式的相加运算。 二、实验内容 1.先创建链表，存储多项式； 2.输出多项式； 3.两个多项式相加； 4.输出多项式。 三、程序代码 #include void print(Polynode*L) { Polynode*p; p=L->next; printf("a="); if(p&&p->coef!=0) printf("%.2f*x^%d",p->coef,p->exp); while(p->next!=NULL) { if((p->next->coef)>0&&p) printf("+"); else printf("-"); p=p->next; printf("%.2f*x^%d",fabs(p->coef),p->exp); } } //多项式相加 void polyadd(Polylist polya,Polylist polyb) { Polynode*p,*q,*tail,*temp; int sum; p=polya->next; q=polyb->next; tail=polya; while (p!=NULL&&q!=NULL) { if(p->exp 北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验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;i 2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList [内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template 第一章概论 一、选择题 1、研究数据结构就是研究（D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作（研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作） 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。（线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素，有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继）（链表、栈、队列、数组、串） A. 图 B. 树 C. 广义表（线性表的推广） D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i 6、算法是（D ）。为了解决某一问题而规定的一个有限长的操作序列 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（B ）和运算等的学科。（关系和操作） A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（ A ）。 i=s=0; while(s 实验报告 课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________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) //实现加法功能。 哈尔滨工业大学计算机科学与技术学院 实验报告 课程名称：数据结构与算法 课程类型：必修 实验项目名称：线性表实验 实验题目：算术表达式求值 班级：0903201 学号：1090320110 姓名：王岳 一、实验目的 二、实验要求及实验环境 三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系） 1．逻辑设计 2．物理设计 四、测试结果 五、系统不足与经验体会 六、附录：源代码（带注释） #include 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 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 计算机系数据结构实验报告（1） 实验目的： 帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的操作和应用作为重点。 问题描述： 1、构造一个空的线性表L。 2、在线性表L的第i个元素之前插入新的元素e； 3、在线性表L中删除第i个元素，并用e返回其值。 实验要求： 1、分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线 性表的基本操作算法。 2、在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行 分析。 算法分析： 由于两种存储结构都用来创建线性结构的数据表，可采用相同的输出模式和整体结构类似的算法，如下： 实验内容和过程： 顺序存储结构线性表程序清单： //顺序存储结构线性表的插入删除 #include int len; //当前元素个数 int listsize; //当前存储最大容量 }SqList; //构造一个空的线性表L int InitList(SqList &L) { =(ElemType *)malloc(LISTSIZE*sizeof(ElemType)); if (! exit(-2); //分配空间失败 =0; =LISTSIZE; } //在顺序线性表L中第i个位置之前插入新的元素e int ListInsert(SqList &L,int i,ElemType e) { if (i<1||i>+1) return -1; //i值不合法 if >= { ElemType *newelem=(ElemType *)realloc,+CREMENTSIZE)*sizeof(ElemType)); //存储空间已满，增加分配 if(!newelem) exit (-2); //分配失败 =newelem; +=CREMENTSIZE; } ElemType *q=&[i-1]) ; for (ElemType *p=&[]);p>=q;--p) *(p+1)=*p; //插入位置及其后的元素后移 *q=e; ++; return 1; } //在顺序线性表L中删除第i个元素，并用e返回其值 int ListDelete(SqList &L,int i,ElemType&e) { if (i<1||i> return -1; //i值不合法数据结构实验报告
数据结构线性表2答案
(完整版)数据结构线性表的主要程序代码
数据结构_实验1_线性表的基本操作
数据结构课后习题及答案
数据结构《线性表的应用》实验报告
数据结构实验一题目一线性表实验报告
数据结构实验报告模板
数据结构试题答案
数据结构线性表的应用实验报告
哈工大 数据结构 实验一 线性表的实验
数据结构习题与答案
数据结构实验线性表及其应用
相关文档
- 数据结构实验报告线性表及其应用
- 数据结构实验报告-实验：1线性表的顺序存储和操作实现
- 数据结构实验指导书(C ) 线性表的操作
- 数据结构_实验1_线性表的基本操作
- 数据结构线性表实验报告
- 数据结构实验报告——线性表顺序存储结构[1]
- [信息与通信]贵州大学数据结构实验1-线性表及应用
- 数据结构实验报告-线性表
- 数据结构实验报告 线性表
- 《数据结构》实验一 线性表及其应用
- 数据结构线性表实验报告
- 数据结构实验_线性表基本操作
- (完整版)数据结构线性表的应用实验报告
- 数据结构实验1
- 数据结构实验C语言实现线性表
- 数据结构实验线性表基本操作
- 数据结构实验-线性表
- 数据结构实验指导(一)
- 数据结构实验线性表及其应用
- 数据结构实验-线性表及其应用