当前位置:文档之家› 数据结构线性链表

数据结构线性链表

数据结构线性链表
数据结构线性链表

数学与计算科学学院实验报告

实验项目名称线性表的链式表示和实现

所属课程名称数据结构A

实验类型验证型

实验日期2013年5月8日

班级信管1101班

学号

姓名

成绩

分析:i、p都没有定义,导致程序运行出错。

更正:在程序的第24行之前加入语句int i;LinkList p;。最后经改正错误后,程序能够正常运行。

【实验小结】(收获体会)

通过这次实验,我收获很大。首先,算法转换成C语句时的变量定义问题我需要继续加强学习;其次,关于主函数的编写,可以参照线性表的顺序结构来编写。总之,感觉自己对数据结构越来越有兴趣。

三、指导教师评语及成绩:

评语

评语等级

优良中

不及格

1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强附录1:源程序

附录2:实验报告填写说明

1.实验项目名称:要求与实验教学大纲一致。

2.实验目的:目的要明确,要抓住重点,符合实验教学大纲要求。

3.实验原理:简要说明本实验项目所涉及的理论知识。

4.实验环境:实验用的软、硬件环境。

5.实验方案(思路、步骤和方法等):这是实验报告极其重要的内容。概括整个实验过程。

对于验证性实验,要写明依据何种原理、操作方法进行实验,要写明需要经过哪几个步骤来实现其操作。对于设计性和综合性实验,在上述内容基础上还应该画出流程图、设计思路和设计方法,再配以相应的文字说明。对于创新性实验,还应注明其创新点、特色。

6.实验过程(实验中涉及的记录、数据、分析):写明具体实验方案的具体实施步骤,包括实验过程中的记录、数据和相应的分析。

7.实验结论(结果):根据实验过程中得到的结果,做出结论。

8.实验小结:本次实验心得体会、思考和建议。

9.指导教师评语及成绩:指导教师依据学生的实际报告内容,给出本次实验报告的评价。

C语言数据结构线性表的基本操作实验报告

实验一线性表的基本操作 一、实验目的与基本要求 1.掌握数据结构中的一些基本概念。数据、数据项、数据元素、数据类型和数据结构,以及它们之间的关系。 2.了解数据的逻辑结构和数据的存储结构之间的区别与联系;数据的运算与数据的逻辑结构的关系。 3.掌握顺序表和链表的基本操作:插入、删除、查找以及表的合并等运算。4.掌握运用C语言上机调试线性表的基本方法。 二、实验条件 1.硬件:一台微机 2.软件:操作系统和C语言系统 三、实验方法 确定存储结构后,上机调试实现线性表的基本运算。 四、实验内容 1.建立顺序表,基本操作包括:初始化,建立一个顺序存储的链表,输出顺序表,判断是否为空,取表中第i个元素,定位函数(返回第一个与x相等的元素位置),插入,删除。 2.建立单链表,基本操作包括:初始化,建立一个链式存储的链表,输出顺序表,判断是否为空,取表中第i个元素,定位函数(返回第一个与x相等的元素位置),插入,删除。 3.假设有两个按数据元素值非递减有序排列的线性表A和B,均以顺序表作为存储结构。编写算法将A表和B表归并成一个按元素值非递增有序(允许值相同)排列的线性表C。(可以利用将B中元素插入A中,或新建C表)4.假设有两个按数据元素值非递减有序排列的线性表A和B,均以单链表作为存储结构。编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序,允许值相同)排列的线性表C。 五、附源程序及算法程序流程图 1.源程序 (1)源程序(实验要求1和3) #include #include #include #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct arr {

数据结构试题及答案

数据结构试题 一、单选题 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_线性表的基本操作

实验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;

数据结构线性表2答案

习题二 一、选择题 1.在一个长度为n的顺序表中删除第i个元素(0<i

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

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

数据结构课后习题及答案

填空题(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; 求串长*/

数据结构线性表单链表实验报告

数据结构实验报告 班级姓名同组者/ 成绩 日期2020.3.25指导教师 实验名称线性表及其应用 一、实验目的: 1、深刻理解线性表的逻辑特性及其顺序、链式存储方式的特点。 2、熟练掌握线性表的常用操作(建立、插入、删除、遍历等)在顺序、链式存储上的实现。 3、加深对C/C++、Java等编程语言的相关知识点的理解(如结构体/类、指针/引用、函数/方法、 引用参数等)。 二、实验内容: 1、 题目 根据给定的整型数组,以尾插法建立一个单链表,并实现以下操作: ①查找:输入一个欲查找的整数,找到则显示第一个相匹配的整数在单链表中所处的位置,若不存在,则显示提示信息。 ②删除:输入一个欲删除的整数e,若存在则在单链表中删除第一个值为e的元素。 ③插入:输入一个欲插入位置i和欲插入元素e,将e插入到第i个整数之前(注意i的合法性)。 源码 #include #include typedef int Elemtype; typedef int Status; typedef struct node// 定义存储节点 { int data;// 数据域 struct node *next;// 结构体指针 } *linklist,node;//结构体变量,结构体名称 linklist creat (int n)//创建单链表

{ linklist head,r,p;// 定义头指针r,p,指针 int x,i; head=(node *)malloc(sizeof(node));// 生成头结点 r=head;//r指向头结点 printf(" 输入数字:\n"); for(i=n;i>0;i--)//for循环用于生成第一个节点并读入数据{ scanf("%d",&x); p=(node *)malloc(sizeof(node)); p->data=x;//读入第一个节点的数据 r->next=p;//把第一个节点连在头结点的后面 r=p;//循环以便于生成第二个节点 } r->next=0;//生成链表后的断开符 return head;// 返回头指针 } void output (linklist head) //输出链表 { linklist p; p=head->next; do { printf("%3d",p->data); p=p->next; } while(p);

数据结构线性表实验报告

《数据结构》实验报告 专业: 学号: 姓名: 实验二线性表 【实验目的】 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所指结点与其下一个结点在链表中的位置。 要求:

数据结构试题答案

第一章概论 一、选择题 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

数据结构线性表答案

第一章线性表 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结点既不是

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

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

数据结构习题与答案

第 1 章绪论 课后习题讲解 1. 填空 ⑴()是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵()是数据的最小单位,()是讨论数据结构时涉及的最小数据单位。 【解答】数据项,数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲,数据结构主要分为()、()、()和()。 【解答】集合,线性结构,树结构,图结构 ⑷数据的存储结构主要有()和()两种基本方法,不论哪种存储结构,都要存储两方面的内容:()和()。 【解答】顺序存储结构,链接存储结构,数据元素,数据元素之间的关系 ⑸算法具有五个特性,分别是()、()、()、()、()。 【解答】有零个或多个输入,有一个或多个输出,有穷性,确定性,可行性 ⑹算法的描述方法通常有()、()、()和()四种,其中,()被称为算法语言。 【解答】自然语言,程序设计语言,流程图,伪代码,伪代码 ⑺在一般情况下,一个算法的时间复杂度是()的函数。 【解答】问题规模 ⑻设待处理问题的规模为n,若一个算法的时间复杂度为一个常数,则表示成数量级的形式为(),若为n*log25n,则表示成数量级的形式为()。 【解答】Ο(1),Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度,需要将低次幂去掉,将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由()表示的,链接存储结构中的数据元素之间的逻辑关系是由()表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C,D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素,其逻辑关系由存储位置(即元素在数组中的下标)表示;链接存储结构中一个数据元素对应链表中的一个结点,元素之间的逻辑关系由结点中的指针表示。

数据结构8581线性链表逆置

#include #include #define ERROR 0 #define OK 1 #define ElemType int typedef struct LNode { int data; struct LNode *next; } LNode,*LinkList; int CreateLink_LA(LinkList &L,int n) { LinkList p,q; int i; ElemType e; L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; q = (LinkList)malloc(sizeof(LNode)); q = L; for (i=0; inext=NULL; q->next=p; p->data=e; q=p; } return OK; } int LoadLink_L1(LinkList &L) { LinkList p=L->next; if(p==NULL)printf("The List is empty!"); else { printf("The List is:"); while(p!=NULL) { printf("%d ",p->data); p=p->next; }

} printf("\n"); return OK; } int LoadLink_L2(LinkList &L) { LinkList p=L->next,t,q; q=p; if(p==NULL)printf("The List is empty!"); else { printf("The turned List is:"); while(p->next!=NULL) { t=p; p=p->next; } printf("%d ",p->data); while(q!=NULL) { p=L->next; while(p->next!=NULL) { if(p->next==t) { printf("%d ",t->data); t=p; break; } p=p->next; } q=q->next; } printf("%d ",L->next->data); } printf("\n"); return OK; } int main() { LinkList T1;

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

实验报告 课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________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;

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

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

关键算法分析 1.头插法 a、伪代码实现:在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中 b、代码实现: Linklist::Linklist(int a[],int n)

堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)取链表长度函数 a、伪代码实现:判断该链表是否为空链表,如果是,输出长度0 如果不是空链表,新建立一个temp指针,初始化整形数n为0 将temp指针指向头结点 判断temp指针指向的结点的next域是否为空,如果不是,n加一,否 则return n 使temp指针逐个后移,重复d操作,直到temp指针指向的结点的next 域为0,返回n b 、代码实现 void Linklist::Getlength()Linklist(); cout<

数据结构C语言实现线性表插入键、交换、倒置

课题一的具体实验内容 1、构造元素类型为整型的线性表,将以下元素插入分别插入线性表: <34 56 20 9 15 5> 2、查找表中是否存在元素20,实现元素20与元素9的交换; 3、按照课题要求编写函数,实现线性表元素<34 56 9 20 15 5>的倒置,即倒置后的表应为< 5 15 20 9 56 34 >。 #include #include #define NULL 0 struct node { int num; struct node *next; }; void main() { int i; struct node *L,*s,*p,*h,*q,*k; L=(node*)malloc(sizeof(struct node)); //L->num=NULL; p=L; printf("请输入\n"); for(i=0;i<6;i++) { s=(node*)malloc(sizeof(struct node)); scanf("%d",&s->num); p->next=s; p=s; } p->next=NULL; //以上为链表的建立和输入 //以下为元素的交换 p=L; while(p->next->num!=20) p=p->next; h=p->next; p->next=p->next->next; h->next=p->next->next; p->next->next=h; p->next->next->next=h->next;

//free(h); //以下为链表的输出 p=L->next; printf("交换后输出\n"); while(p!=NULL) { printf("%d\n",p->num); p=p->next; } //以下为链表的倒置 p=L; while(p->next->next!=NULL) p=p->next; q=p->next; q->next=p; p->next=NULL; p=L; for(i=0;i<4;i++) {while(p->next->next!=NULL) p=p->next; k=p->next; k->next=p; p->next=NULL; p=L; } L->next=q; //倒置后链表的输出 p=L->next; printf("倒置后输出\n"); while(p!=NULL) { printf("%d ",p->num); p=p->next; } }

算法与数据结构 线性表答案

第2章 线性表 一、判断题 1 线性关系的逻辑结构与存储结构总是一致的。 解:错。单链表的逻辑结构与存储结构有可能是不一致的,有可能两个相邻结点的存储地址并不是相邻的。 2 每种数据结构都包括插入、删除和查找这三种基本运算。 解:错。散列结构无插入与删除运算;栈没有查找,查找须配有另一个栈。 3 线性表中的每个结点最多只有一个前驱和一个后继。 解:对。线性表的定义为:表中任意一个元素至多有一个前驱,至多有一后继。 4 线性的数据结构既可以顺序存储,也可以链接存储;非线性的数据结构则只能链接存储。 解:错。对于非线性的数据结构,若对它的数据规定某种次序之后,也可以顺序存储。如,树的前、中、后序遍历之后的存储,一个前驱可能对应多个后继。 5 顺序存储方式只能用于存储线性结构。 解:错。非线性结构也可采用顺序存储。 6 多维数组是向量的推广。 解:对。多维向量的存储方式实际上与一维向量是一致的。 7 设串s 的长度为n ,则s 的子串个数最多为n (n+1)/2。 解:错。s 的长度为n ,故它含有n 个字符,它的子串应包括:1个字符的子串,2个字符的子串,…,n 个字符的子串;这些子串的个数分别为 121)11(321-=-+=++++n n n n n n n C C C C 8 单链表从任何一个结点出发,都能访问到所有结点。 解:错。单链表仅能从头结点出发去访问所有结点,不能访问前驱。 9 线性表的长度是线性表所占用的存储空间的大小。 解:错。线性表所占用的存储空间大小为:每个结点所占用的存储字节数乘以线性表的长度。 10 双循环链表中,任意一结点的后继指针均指向其逻辑后继。 解:错。任意结点的后继结点包含有两个指针llink 和rlink ,只有rlink 指向其逻辑后继,而llink 指向其逻辑前驱。 11 数据结构、数据元素、数据项在计算机中的映象(或表示)分别称为存储结构、结点、数据域。 解:对。 12 线性表的顺序存储结构优于链式存储结构。 解:错。各有优缺点。 顺序存储结构的优点是: (1)存储效率高。(2)可随机访问任意结点,存取速度快。 顺序存储结构的缺点是: (1)插入与删除操作麻烦。(2)顺序表的长度扩充麻烦。 链式存储结构的优点是: (1)插入与删除方便。(2)顺序表的长度可任意(动态分配内存)。 链式存储结构的缺点是: (1)存储效率低。(2)对结点的访问不方便。

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