算法与数据结构c语言集合与字典

第一章数据结构与算法1.1 算法1．1．1算法：是指解题方案的准确而完整的描述。

规定了解决某类问题所需的操作语句以及执行顺序使其能通过有限的指令语句，在一定时间内解决问题算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。

算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。

1．算法特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限的步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。

2．算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构通常，计算机可以以执行的基本操作是以指令的形式描述的。

一个计算机系统能执行的所有指令的集合，称为计算机系统的指令系统。

（1）计算机系统中的基本运算和操作包括：算术运算+ - * /逻辑运算not and or关系运算< > ! =数据传输赋值输入与输出（2）算法的控制结构：顺序结构、选择结构、循环结构。

3．算法基本设计方法：列举法（列举所有解决方案）归纳法（特殊→一般）递推（已知→未知）递归（逐层分解）减半递推“减半”是指将问题的规模减半，而问题的性质不为，所谓“递推”是指重复“减半”的过程回溯法找出一个解决问题的线索，然后沿着这个线索逐步多次“探、试”1．1．2算法复杂度算法时间复杂度和算法空间复杂度（一个算法所要付出的代价）是衡理算法好坏的。

1．算法时间复杂度算法时间复杂度是指执行算法所需要的计算工作量。

（既算法的运算次数）含义：算法执行过程中所需要的基本运算次数影响计算工作量的主要因素：一、基本运算次数二、问题与规模2．算法空间复杂度是指执行这个算法所需要的内存空间。

一个算法所用的内存空间包括：1、算法程序所占的空间2、输入的初始数据所占的存储空间3、算法执行过程中的额外空间1.2 数据结构的基本基本概念数据：在计算机科学中指所有能输入到计算机中的并被计算机程序处理的符号的总称数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

第一部分公共基础部分知识归纳第一章数据结构与算法算法---是一组严谨地定义运算顺序的规则算法的基本要素---一是对数据对象的运算和操作，二是算法的控制结构算法设计基本方法---列举法、归纳法、递推、递归、减半递推算法的复杂度---包括时间复杂度和空间复杂度时间复杂度---执行算法所需的计算工作量空间复杂度---执行算法所需的内存空间数据结构---相互有关联的数据元素的集合。

如春、夏、秋、冬；18、11、35、23、16。

；父亲、儿子、女儿等都是数据元素。

前件---数据元素之间的关系，如父亲是儿子和女儿的前件后件---如儿子是父亲的后件结构---指数据元素之间的前后件关系数据的逻辑结构—是指反映数据元素之间逻辑关系，而与它们在计算机中的存储位置无关数据的存储结构（物理结构）---数据的逻辑结构在计算机存储空间中的存放形式，数据元素在计算机存储空间的位置关系可能与逻辑关系不同。

根据数据结构中各数据元素之间前后件关系的复杂程度，可将数据结构分两类---线性结构与非线性结构线性结构（线性表）---满足下列两个条件（1）有且只有一个根结点（2）每一个结点最多有一个前件和后件。

则称该数据结构为线性结构，否则为非线性结构。

线性表是最简单、最常用的一种数据结构，其数据元素之间的相对位置是线性的，其存储方式为顺序存储的，如数组栈---是限定在一端进行插入与删除的线性表，一端封闭，另一端开口，其操作原则是“先进后出”，栈的运算有入栈、退栈、读栈顶元素队列---是指在一端进行插入（称为队尾）而在另一端进行删除（称为队头）的线性表，其操作规则是“先进先出”，其运算有入队和退队。

树---是一种简单的非线性结构，而且是层次结构，是倒立的大树，有根结点、父结点、子结点、叶子结点。

根结点在第一层，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度，树的最大层次称为树的深度。

二叉树---（1）非空二叉树只有一个根结点（2）每一个结点最多有两棵子树（左子树和右子树），其存储结构为链式。

第1章概论习题参考答案一、基础知识题1.简述下列概念数据，数据元素，数据类型，数据结构，逻辑结构，存储结构，算法。

【解答】数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。

数据元素是数据的基本单位。

在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。

数据类型是对数据的取值范围、数据元素之间的结构以及允许施加操作的一种总体描述。

每一种计算机程序设计语言都定义有自己的数据类型。

“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。

作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。

而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。

数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。

数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则依赖于存储结构。

数据结构在计算机中的表示称为物理结构，又称存储结构。

是逻辑结构在存储器中的映像，包括数据元素的表示和关系的表示。

逻辑结构与计算机无关。

算法是对特定问题求解步骤的一种描述，是指令的有限序列。

其中每一条指令表示一个或多个操作。

一个算法应该具有下列特性：有穷性、确定性、可行性、输入和输出。

2.数据的逻辑结构分哪几种，为什么说逻辑结构是数据组织的主要方面？【解答】数据的逻辑结构分为线性结构和非线性结构。

（也可以分为集合、线性结构、树形结构和图形即网状结构）。

逻辑结构是数据组织的某种“本质性”的东西：（1）逻辑结构与数据元素本身的形式、内容无关。

（2）逻辑结构与数据元素的相对位置无关。

（3）逻辑结构与所含数据元素的个数无关。

算法与数据结构（山东联盟）知到章节测试答案智慧树2023年最新烟台大学绪论单元测试1.数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的____和运算等的学科。

参考答案:关系2.算法的描述形式包括参考答案:自然语言;N-S图;流程图 ;类程序设计语言3.算法的特征包括有穷性、确定性、可行性和输入输出。

参考答案:对4.对算法的描述包括程序形式和描述形式。

参考答案:对5.描述形式是算法的最终形式参考答案:错6.“数据结构”是介于( )、( )和( )三者之间的一门核心课程。

参考答案:计算机软件;数学;计算机硬件7.著名计算机科学家沃思教授提出的公式：程序 = ( ) + ( )，也说明了数据结构的重要性。

参考答案:数据结构;算法8.描述非数值计算问题的数学模型不再是数学方程，而是数据结构( )。

参考答案:表;集合;树;图9.数据结构是一门研究( )程序设计问题中计算机的( )以及它们之间的( )和( )等的学科。

参考答案:操作;非数值计算;操作对象;关系10.顺序存储结构: 借助元素在存储器中的( )来表示数据元素间的逻辑关系。

参考答案:相对位置第一章测试1.（）是一种最简单的线性结构。

参考答案:线性表2.（）线性表的数据元素可以由所描述对象的各种特征的数据项组成。

参考答案:链式存储3.已知单向链表中指针p指向结点A，( ）表示删除A的后继结点（若存在）的链操作（不考虑回收）。

参考答案:p—>next=p—>next—>next4.已知last指向单向简单链表的尾结点，将s所指结点加在表尾，不正确的操作是____。

参考答案:s->next=NULL, last->next=s, s=last;5.已知h是指向单向加头链表的首指针，删除表头结点的操作是_____。

参考答案:p=h->next,h->next=p->next;free(p);6.有N个元素组成的线性表，我们说此线性表的长度为（）参考答案:n7.对线性表中的数据元素进行（）和（）等操作，实现表的长度的增长或缩短。

1.基本数据结构与算法1.1算法算法：是指解题方案的准确而完整的描述。

特征包括：（1）可行性；（2）确定性，（3）有穷性，（4）拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。

指令系统：一个计算机系统能执行的所有指令的集合。

基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。

算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。

算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

算法空间复杂度是指执行这个算法所需要的内存空间。

数据的存储结构有顺序、链接、索引等。

线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。

1.3线性表及其顺序存储结构非空线性表的结构特征：（1）且只有一个根结点a1，它无前件；（2）有且只有一个终端结点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。

结点个数n称为线性表的长度，当n=0时，称为空表。

线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素的所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

顺序表的运算：插入、删除。

1.4栈和队列a）栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。

栈按照“先进后出"（FILO）或“后进先出"（LIFO）组织数据，栈具有记忆作用。

用top表示栈顶位置，用bottom表示栈底。

栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。

b）队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。

算法与数据结构C语⾔版课后习题答案（机械⼯业出版社）第3,4章习题参考答案第3章栈和队列⼀、基础知识题3.1有五个数依次进栈：1，2，3，4，5。

在各种出栈的序列中，以3，4先出的序列有哪⼏个。

（３在４之前出栈）。

【解答】34215 ，34251，345213.2铁路进⾏列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序为：1，2，3，4，5，6，那么是否能够得到435612， 325641， 154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到(即写出"进栈"或"出栈"的序列)。

【解答】输⼊序列为123456，不能得出435612和154623。

不能得到435612的理由是，输出序列最后两元素是12，前⾯4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能让栈底元素1在栈顶元素2之前出栈。

不能得到154623的理由类似，当栈中元素只剩23，且3在栈顶，2不可能先于3出栈。

得到325641的过程如下：1 2 3顺序⼊栈，32出栈，得到部分输出序列32；然后45⼊栈，5出栈，部分输出序列变为325；接着6⼊栈并退栈，部分输出序列变为3256；最后41退栈，得最终结果325641。

得到135426的过程如下：1⼊栈并出栈，得到部分输出序列1；然后2和3⼊栈，3出栈，部分输出序列变为13；接着4和5⼊栈，5，4和2依次出栈，部分输出序列变为13542；最后6⼊栈并退栈，得最终结果135426。

3.3若⽤⼀个⼤⼩为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除⼀个元素，再加⼊两个元素后，rear和front的值分别为多少？【解答】2和43.4设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，⼀个元素出栈后即进队列Q，若6个元素出队的序列是e3，e5，e4，e6，e2，e1，则栈S的容量⾄少应该是多少？【解答】43.5循环队列的优点是什么，如何判断“空”和“满”。

数据结构与算法分析c语言描述中文答案【篇一：数据结构(c语言版)课后习题答案完整版】选择题：ccbdca6．试分析下面各程序段的时间复杂度。

（1）o（1）（2）o（m*n）（3）o（n2）（4）o（log3n）（5）因为x++共执行了n-1+n-2+??＋1= n(n-1)/2，所以执行时间为o（n2）（6）o(n)第2章线性表1．选择题babadbcabdcddac 2．算法设计题（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

elemtype max (linklist l ){if(l-next==null) return null;pmax=l-next; //假定第一个结点中数据具有最大值 p=l-next-next; while(p != null ){//如果下一个结点存在if(p-data pmax-data) pmax=p;p=p-next; }return pmax-data;（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。

void inverse(linklist l) { // 逆置带头结点的单链表 l p=l-next; l-next=null; while ( p) {q=p-next; // q指向*p的后继p-next=l-next;l-next=p; // *p插入在头结点之后p = q; }}（10）已知长度为n的线性表a采用顺序存储结构，请写一时间复杂度为o(n)、空间复杂度为o(1)的算法，该算法删除线性表中所有值为item的数据元素。

[题目分析] 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移）。

本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。

因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。

1. 现在有一个已排序的字典，请改写二分法检索算法，使之当排序码key在字典中重复出现时算法能找出第一个key出现的元素下标（用*position来保存）。

保持算法时间代价为O(log n)。

【答】思路一般的二分法检索算法只要找出关键码key在字典中的一个下标。

在比较的过程中，一旦发现相等，记录下当前下标mid就符合要求。

程序如下：数据结构字典采用6.1.4节中的顺序表示法。

typedef int KeyType;typedef int DataType;二分法检索算法int binarySearch(SeqDictionary * pdic, KeyType key, int * position) {int low, mid, high;low = 0;high = pdic->n - 1;while (low <= high){mid = (low + high) / 2;if (pdic->element[mid].key = = key) {*position = mid;return TRUE;}elseif (pdic->element[mid].key > key)high = mid - 1;elselow = mid + 1;}*position = low;return FALSE;}改写后的算法想要找出关键码key在字典中第一次出现的下标。

在比较中，如果遇到相等（key与pdic->element[mid].key相等），则需要分情形讨论。

（1）如果当前下标mid等于0，或者key与pdic->element[mid-1].key不等，那么mid 一定是key第一次出现的下标，返回mid即可。

（2）如果情形（1）不成立，那么mid一定大于等于key第一次出现的下标，需要在low 和mid-1之间继续进行搜索，找出key第一次出现的下标。