自学考试数据结构02331(2014整理)简析.doc

自考数据结构重点（2014整理） 第一章 概论 1.瑞士计算机科学家沃思提出：算法+数据结构=程序。算法是对数据运算的描述，而数据结构包括逻辑结构和存储结构。由此可见，程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。 2.数据是信息的载体数据元素是数据的基本单位一个数据元素可以由若干个数据项组成数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括以下三方面内容：数据的逻辑结构数据的存储结构数据的运算数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的数据元素及其关系在计算机存储，称为数据的存储结构数据的存储结构是逻辑结构用计算机语言的实现它依赖于计算机语言。数据的运算最常用的检索、插入、删除、更新、排序等1）顺序存储：通常借助程序设计语言的数组描述。 （2）链接存储：通常借助于程序语言的指针来描述。 （3）（4）算法个或多个作为输入输出产生一个或多个算法算法正确是首先要考虑的。此外，主要考虑如下三点： 执行算法所耗费的时间； 执行算法所耗费的存储空间，主要辅助空间； 算法应易于理解易于，易于调试等。算法求解问题的输入量称为问题的规模,用一个整数表示。常见的时间复杂度按数量级递增排列依次为：常数0(1)、对数阶0(log2n)、线阶0(n)、线对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、…、k次方阶0(nk)、指数阶0(2n)0(n!)。一个算法的空间复杂度S(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 ，则返回。5)InsertList（L，i，x）在线性表L的第i个插入一个值为x 的新，表L的长度加1。6)DeleteList（L，i）删除线性表L的第i个，删除后表L的长度减1。顺序存储方法把线性表的按逻辑次序依次存放在一组地址连续的存储单元里的方法。顺序表（Sequential List）用顺序存储方法存储的线性表称为顺序表是一种随机存取结构顺序表的特点是逻辑上相邻的结点其物理位置亦相邻。顺序表上实现的基本运算算法时间复杂度是(n)，即在顺序表上进行插入运算，平均要移动一半结点。顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是(n)。链式存储单链表。生成结点变量的标准函数??? 　p=( ListNode *)malloc(sizeof(ListNode))； //函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中释放结点变量空间的标准函数 free(p)；//释放p所指的结点变量空间结点分量的访问 ?方法二：p-﹥data和p-﹥next指针变量p和结点变量*p的关系 指针变量p的值——结点地址 结点变量*p的值——结点内容建立单链表（1） 头插法建表=(ListNode *)malloc(sizeof(ListNode));①//生成新结点????????????? -data=ch;??② //将读入的数据放入新结点的数据域中????????????? -next=head;③????????????? head=p;④ （2） 尾插法建表=(ListNode *)malloc(sizeof(ListNode)); ①//生成新结点????????????? -data=ch;??② //将读入的数据放入新结点的数据域中?????????? if (head=NULL)?????????????? head=p;//新结点插入空表?????????? else?????????????? r-next=p;③//将新结点插到*r之后????????????? r=p;④//尾指针指向新表尾（3） 尾插法建带头结点的单链表头结点及作用头结点是在链表的开始结点之前附加一个结点。它具有两个优点:?? 　由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理;?? 　无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。 头结点数据域的阴影表示该部分不存储信息。在有的应用中可用于存放表长等附加信息。r=head;??? //?尾指针初值也指向头结点????????? w