文档介绍：自考数据结构02331重点
第一章概论
:算法+数据结构=程序。算法是对数据运算的描述,而数据结构包括逻辑结构和存储结构。由此可见,程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法,而好的算法在很大程度上取决于描述实际问题的数据结构。
。数据元素是数据的基本单位。一个数据元素可以由若干个数据项组成,数据项是具有独立含义的最小标识单位。数据对象是具有相同性质的数据元素的集合。
,即数据的组织形式。
数据结构一般包括以下三方面内容:数据的逻辑结构、数据的存储结构、数据的运算
①数据的逻辑结构是从逻辑关系上描述数据,与数据元素的存储结构无关,是独立于计算机的。
数据的逻辑结构分类: 线性结构和非线性结构
②数据元素及其关系在计算机内的存储方式,称为数据的存储结构(物理结构)。
数据的存储结构是逻辑结构用计算机语言的实现,它依赖于计算机语言。
③数据的运算。最常用的检索、插入、删除、更新、排序等。
: 顺序存储、链接存储、索引存储、散列存储
(1)顺序存储:通常借助程序设计语言的数组描述。
(2)链接存储:通常借助于程序语言的指针来描述。
(3)索引存储:索引表由若干索引项组成。关键字是能唯一标识一个元素的一个或多个数据项的组合。
(4)散列存储:该方法的基本思想是:根据元素的关键字直接计算出该元素的存储地址。
:输入,0个或多个数据作为输入;输出,产生一个或多个输出;有穷性,算法执行有限步后结束;确定性,每一条指令的含义都明确;可行性,算法是可行的。
算法与程序的区别:程序必须依赖于计算机程序语言,而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。目前常用的描述算法语言有两类:类Pascal和类C。
:算法的"正确性"是首先要考虑的。此外,主要考虑如下三点:
①执行算法所耗费的时间,即时间复杂性;
②执行算法所耗费的存储空间,主要是辅助空间,即空间复杂性;
③算法应易于理解、易于编程,易于调试等,即可读性和可操作性。
以上几点最主要的是时间复杂性,时间复杂度常用渐进时间复杂度表示。
,用一个正整数n表示。
:常数阶0(1)、对数阶0(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、…、k次方阶0(nk)、指数阶0(2n)和阶乘阶0(n!)。
(n)定义为该算法所耗费的存储空间,它是问题规模n的函数,它包括存储算法本身所占的存储空间、算法的输入输出数据所占的存储空间和算法在运行过程中临时占用的存储空间。
第二章线性表
,而运算的具体实现是在存储结构上进行的。
,线性表中任意一个元素都可随机存取,所以顺序表是一种随机存取结构。
:
(1)置空表InitList(L) 构造一个空的线性表L。
(2)求表长ListLength(L)求线性表L中的结点个数,即求表长。
(3)GetNode(L,i) 取线性表L中的第i个元素。
(4)LocateNode(L,x)在L中查找第一个值为x 的元素,并返回该元素在L中的位置。若L中没有元素的值为x ,则返回0值。
(5)InsertList(L,i,x)在线性表L的第i个元素之前插入一个值为x 的新元素,表L的长度加1。
(6)DeleteList(L,i)删除线性表L的第i个元素,删除后表L的长度减1。
:把线性表的数据元素按逻辑次序依次存放在一组地址连续的存储单元里的方法。
顺序表(Sequential List):用顺序存储方法存储的线性表称为顺序表。顺序表是一种随机存取结构,顺序表的特点是逻辑上相邻的结点其物理位置亦相邻。
:
(1)插入:该算法的平均时间复杂度是O(n),即在顺序表上进行插入运算,平均要移动一半结点(n/2)。
(2)删除:顺序表上做删除运算,平均要移动表中约一半的结点(n-1)/2,平均时间复杂度也是O(n)。
。一个单链表可由头指针唯一确定,因此单链表可以用头指针的名字来命名。①生成结点变量的标准函数    p=( ListNode *)malloc(sizeof(ListNode)); //函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放