数据结构线性表的链式表示和实现的实习报告
数学与计算科学学院实验报告
实验项目名称线性表的链式表示与实现
所属课程名称数据结构
实验类型验证型
实验日期
班级
学号
姓名
成绩
2.调试第一次显示错误如下：
原因：由于没有头文件及宏定义以及自定义，因此导致许多错误，可能还有许多错误没有显示
3. 将以下语句编入VC++6.0中
#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int Status;
4.调试第二次显示错误如下：
原因：由于算法中许多变量没有定义，因此有许多错误5. 将以下语句加入算法中：
int i;
LinkList p;（加入创建链表的算法中）
LinkList p;
int j;（加入查找元素的算法中）
LinkList p,s;
int j;(加入插入元素的算法中)
LinkList p,q;
int j;（加入删除元素的算法中）
6.调试第三次显示没有错误：
7. 现在开始编写主函数：
（1）先编写调用创建链表的函数的主函数：
如下：
void main()
{
LinkList L;
int i,n;
scanf("%d",&n);
CreateList_L(L,n);
for(i=n;i>0;--i)
printf("%d ",L->data);
printf("\n");
}
调试显示为：
运行显示为：
产生了随机数说明for循环语句那里编写错误因此修改为：
LinkList p;
for(p=L->next;p!=NULL;p=p->next)
printf("%d ",p->data);
调试显示为：
运行显示为：
这次正确了那么继续编写下面的其他主函数，形成的总的主函数为：void main()
{
LinkList L,p;
int i,n;
scanf("%d",&n);
CreateList_L(L,n);
for(p=L->next;p!=NULL;p=p->next)
printf("%d ",p->data);
printf("\n");
ElemType e;
scanf("%d", &i);
GetElem_L(L, i, e);
printf("%d\n",e);
scanf("%d",&i);
scanf("%d",&e);
ListInsert_L(L, i, e);
for(p=L->next;p!=NULL;p=p->next)
printf("%d ",p->data);
printf("\n");
scanf("%d", &i);
ListDelete_L(L,i,e);
printf("%d\n",e);
for(p=L->next;p!=NULL;p=p->next)
printf("%d ",p->data);
printf("\n");
}
8.调试第四次显示为：
9.运行显示结果为：
10. 但运行后的界面显得很单调；要是忘记下一个算法是什么就容易输入出错，也不适合大众使用；因此为了将程序优化，所以在主函数中增加以下输入输出语句和条件语句；为了让程序更加严谨，因此还加入一些循环语句以及条件语句，那么主函数语句变为：
main()
{
LinkList L,p;
int i,n,x,y,z;
ElemType e;
printf("请输入您想构建的链式表的元素个数:\n");
scanf("%d",&n);
printf("请输入您想构建的链式表:\n");
CreateList_L(L,n);
printf("您构建的链式表是:\n");
for(p=L->next;p!=NULL;p=p->next)
printf("%d ",p->data);
printf("\n");
printf("请输入您想查找的元素是第几个元素:\n");
scanf("%d", &i);
for(x=2;(i<=0||i>n)&&x>=0;--x)
{
switch(x)
{
case 2:printf("输入的数字错误,还有两次重新输入符合要求的数字的机会:\n");break;
case 1:printf("输入的数字错误,还有一次重新输入符合要求的数字的机会:\n");break;
case 0:printf("输入的数字错误,您的输入机会已经用完\n");return ERROR;
printf("%d ",p->data);
printf("\n");
return 0;
}
11.调试第五次显示为：、
12.运行后结果显示为：
这样那么程序就完整了，清晰明了，用户运行的时候也易知道自己要输入什么了
【实验结论】（结果）
数据结构试题及答案
数据结构试题 一、单选题 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 浙江大学城市学院实验报告 课程名称数据结构基础 实验项目名称实验五线性表的链式表示和实现 学生姓名吴奇专业班级信管1204 学号31201403 实验成绩指导老师（签名）日期 一.实验目的和要求 1、掌握线性表的链式存储结构； 2、掌握单链表、循环单链表的一些基本操作实现函数。 二.实验内容 1、设线性表采用带表头附加结点的单链表存储结构，请编写线性表各基本操作的实现函数，把它们存放在头文件LinkList.h中，同时建立一个验证操作实现的主函数文件test2_2.cpp。编译并调试程序，直到正确运行。 2、选做：编写一个函数void MergeList(LNode *&La, LNode *&Lb, LNode *&Lc) ，实现将两个带表头附加结点的有序单链表La和Lb合并成一个新的带表头附加结点的有序单链表Lc的功能，要求利用原存储空间。请把该函数添加到头文件LinkList.h中，并在主文件test2_2.cpp中添加相应语句进行测试。 3、填写实验报告，实验报告文件取名为report5.doc。 4、上传实验报告文件report5.doc、源程序文件test2_2.cpp及LinkList.h 到Ftp服务器上自己的文件夹下。 三. 函数的功能说明及算法思路 void initlist(lnode *&hl) 初始化链表 { hl=new lnode; 新建头节点 if(!hl){ cout<<"储存分配失败，按任意键退出系统!!"< 习题二 一、选择题 1．在一个长度为n的顺序表中删除第i个元素（0＜i 第一章线性表 2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。 解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。 2.2 填空题。 解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。 (2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。 (3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。 (4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。 2.3 在什么情况下用顺序表比链表好？ 解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。 2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。 解： 2.5 画出执行下列各行语句后各指针及链表的示意图。 L=(LinkList)malloc(sizeof(LNode)); P=L; for(i=1;i<=4;i++){ P->next=(LinkList)malloc(sizeof(LNode)); P=P->next; P->data=i*2-1; } P->next=NULL; for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2); for(i=1;i<=3;i++) Del_LinkList(L,i); 解： 2.6 已知L是无表头结点的单链表，且P结点既不是 填空题（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; 求串长*/ 重庆交通大学 《算法与数据结构》课程 实验报告 班级：计算机科学与技术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();//输出 数据结构实验线性表的链式表示和实现（源代码） #include getchar(); p->next=NULL; q->next=p; q=p; i++; } system("cls"); return head; } struct node* clearlist(node *head) { head=NULL; return head; } status destroylist(node *head) { head=NULL; free(head); return OK; } statuslistempty(node *head) { if(head==NULL) return OK; else return ERROR; } statuslistlength(node *head) { inti=0; node *p; p=head->next; while(1) { i++; if(p->next==NULL) break; p=p->next; } 数据结构实验一顺序表的实现 班级学号分数 一、实验目的： 1.熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现； 2.以线性表的各种操作的实现为重点； 3.通过本次学习帮助学生加深C语言的使用，掌握算法分析方法并对已经设计 出的算法进行分析，给出相应的结果。 二、实验要求： 编写实验程序，上机运行本程序，保存程序的运行结果，结合程序进行分析并写出实验报告。 三、实验容及分析： 1.顺序表的建立 建立一个含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 程序如下： 头文件SqList.h的容如下： #include if(!L->elem) return(OVERFLOW); L->length=0; L->listsize=LIST_INIT_SIZE; return OK; } Status CreatList_Sq(SqList *L,int n) { int i; printf("输入%d个整数:\n",n); for(i=0;i 第一章概论 一、选择题 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 南昌航空大学实验报告 课程名称：数据结构实验名称：实验二线性表的链式存储结构 班级：学生姓名：冯华华学号：11046213 指导教师评定： XXX 签名: XXX 一、问题描述 1单链表的实现与操作。 2设计一个程序求出约瑟夫环的出列顺序。约瑟夫问题的一种描述是：编号为1，2，…， n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整 数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。 报m的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1 报数，如此下去，直到所有人全部出列为止。例如，n=7,7个人的密码依次为： 3,1,7,2,4,8,4,m的初值取6，则正确的出列顺序应为6,1,4,7,2,3,5。要求使用单向循环 链表模拟此出列过程。 二、程序分析 约瑟夫环的大小是变化的，因此相应的结点也是变化的，使用链式存储结构可以动态的 生成其中的结点，出列操作也非常简单。用单向循环链表模拟其出列顺序比较合适。 用结构指针描述每个人： struct Joseph {int num;/*环中某个人的序号*/ int secret;/环中某个人的密码*/ struct Joseph *next;/指向其下一个的指针*/}; 1）初始化约瑟夫环： 调用函数struct Joseph *creat()生成初始约瑟夫环。在该函数中使用head 指向 表头。输入序号为0时结束，指针p1指向的最后结束序号为0的结点没有加入到 链表中，p2 指向最后一个序号为非0 的结点（最后一个结点）。 2）报数出列： 调用函数voil sort(struct Joseph * head,int m)，使用条件p1->next!=p1判断 单向链表非空，使用两个指针变量p1和p2，语句p2=p1;p1=p1->next;移动指针， 计算结点数（报数）；结点p1出列时直接使用语句：p2->next=p1->next，取出该 结点中的密码作为新的循环终值。 三、调试过程及实验结果 最后程序运行结果如下所示： 输入数据：数据格式为序号，密码 输入0，0为结束 1，3↙<回车> 2，1↙<回车> 数据结构顺序表的主要代码（LIZHULIN） 1．/***有头结点的单链表的初始化、建立（表头插入、表尾插入）、求长度、插入、删除、输出***/ /***********单链表的初始化、建立、输出*****************/ #include 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 1.实验目的 掌握线性表的链式存储结构设计与基本操作的实现。 2.实验内容与要求 ⑴定义线性表的链式存储表示； ⑵基于所设计的存储结构实现线性表的基本操作； ⑶编写一个主程序对所实现的线性表进行测试； ⑷线性表的应用：①设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用线性表L3代表集合C；②设线性表L1和L2中的数据元素为整数，且均已按值非递减有序排列，试设计算法对L1和L2进行合并，用线性表L3保存合并结果，要求L3中的数据元素也按值非递减有序排列。 ⑸设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式相加；④执行两个多项式相减； 3.数据结构设计 逻辑结构：线性结构 存储结构：链式存储结构 4.算法设计 #include 实验报告三线性表的链式存储 班级：姓名：学号：专业： 一、实验目的： （1）掌握单链表的基本操作的实现方法。 （2）掌握循环单链表的基本操作实现。 （3）掌握两有序链表的归并操作算法。 二、实验内容：（请采用模板类及模板函数实现） 1、线性表链式存储结构及基本操作算法实现 [实现提示] （同时可参见教材p64-p73页的ADT描述及算法实现及ppt）函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。 所加载的库函数或常量定义： （1）单链表存储结构类的定义： （2）初始化带头结点空单链表构造函数实现 输入：无 前置条件：无 动作：初始化一个带头结点的空链表 输出：无 后置条件：头指针指向头结点。 （３）利用数组初始化带头结点的单链表构造函数实现 输入：已存储数据的数组及数组中元素的个数 前置条件：无 动作：利用头插或尾插法创建带头结点的单链表 输出：无 后置条件：头指针指向头结点，且数组中的元素为链表中各结点的数据成员。 （４）在带头结点单链表的第i个位置前插入元素e算法 输入：插入位置i，待插入元素e 前置条件：i的值要合法 动作：在带头结点的单链表中第i个位置之前插入元素e 输出：无 后置条件：单链表中增加了一个结点 （５）在带头结点单链表中删除第i个元素算法 输入：删除第i个结点，待存放删除结点值变量e 前置条件：单链表不空，i的值要合法 动作：在带头结点的单链表中删除第i个结点，并返回该结点的值（由e传出）。 输出：无 后置条件：单链表中减少了一个结点 （６）遍历单链表元素算法 输入：无 前置条件：单链表不空 动作：遍历输出单链表中的各元素。 输出：无 后置条件：无 （７）求单链表表长算法。 输入：无 前置条件：无 动作：求单链表中元素个数。 输出：返回元素个数 后置条件：无 （８）判单链表表空算法 输入：无 前置条件：无 动作：判表是否为空。 输出：为空时返回１，不为空时返回0 后置条件：无 （９）获得单链表中第i个结点的值算法 输入：无 前置条件：i不空，i合法 动作：找到第i个结点。 输出：返回第i个结点的元素值。 后置条件：无 (10)删除链表中所有结点算法（这里不是析构函数，但功能相同）输入：无 前置条件：单链表存在 动作：清除单链表中所有的结点。 输出：无 后置条件：头指针指向空 第2章线性表 1．选择题 （1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。 A．110 B．108 C．100 D．120 答案：B 解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。 （2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。 A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B．在第i个结点后插入一个新结点（1≤i≤n） C．删除第i个结点（1≤i≤n） D．将n个结点从小到大排序 答案：A 解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。 （3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。 A．8 B．63.5 C．63 D．7 答案：B 解释：平均要移动的元素个数为：n/2。 （4）链接存储的存储结构所占存储空间（）。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值 C．只有一部分，存储表示结点间关系的指针 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数 答案：A （5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。 A．必须是连续的B．部分地址必须是连续的 C．一定是不连续的D．连续或不连续都可以 答案：D （6）线性表Ｌ在（）情况下适用于使用链式结构实现。 A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入 C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂 答案：B 实验报告 课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________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.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3; 经济学院 实验报告 学院: 专业: 计算机 班级: 学号: 姓名: 信息工程学院计算机实验中心制 实验题目：线性表的链式存储结构和实现 实验室：机房4 设备编号： 09 完成日期： 2012.04.09 一、实验容 1.会定义线性表的链式存储结构。 2.熟悉对单链表的一些基本操作(建表、插入、删除等)和具体的函数定义。 二、实验目的 掌握链式存储结构的特点，掌握并实现单链表的常用的基本算法。 三、实验的容及完成情况 1. 需求分析 (1)线性表的抽象数据类型ADT的描述及实现。 本实验实现使用Visual c++6.0实现线性表链式存储结构的表示及操作。具体实现要求： (2)完成对线性表链式存储结构的表示和实现。 (3)实现对单链表的创建。 (4)实现对单链表的插入和删除操作。 2．概要设计 抽象数据类型线性表的定义：ADT LIST{ 抽象对象：D=｛ai|ai<-Elemset,i=1,2,…,n,n>=0｝ 数据关系：R1=｛线性表的链式表示与实现
数据结构线性表2答案
数据结构线性表答案
数据结构课后习题及答案
线性表的顺序储存结构
(数据结构)线性表的链式表示和实现(源代码)
数据结构实验一顺序表的实现
数据结构试题答案
实验二 线性表的链式存储结构
数据结构线性表的主要程序代码
数据结构习题与答案
数据结构线性表的链式存储结构
实验3 线性表的链式存储
数据结构 线性表 课后答案
数据结构线性表的应用实验报告
数据结构作业及答案
线性表的链式存储结构和实现