文档介绍：:..[年][键入文档标题][键入文档副标题]黄薇Microsoft[选取日期]第一章一名词解释数据:是对客观事物的客观表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素:构成数据的基本单位。数据项:数据不可分割的最小单位。数据对象:性质相同的数据元素的集合。数据结构:带结构的数据元素的集合。和互之间存在一种或多种特定关系的数据元素的集合。二数据结构的三个方面:数据的逻辑结构数据的存储结构数据的运算(操作)三抽象数据类型的定义是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型可用(D,S,P)三元组表示。其屮:D是数据对象;S是D上的关系集;P是对D的基本操作集。四算法的概念特性原则概念:解决某一特定问题的具体步骤的描述,是指令的有限序列。五大特性:有穷性,确定性,可行性,有零个或多个输入,有一个或多个输出。四大原则:正确性,可读性,健壮性,高效率和低存储量需求。五算法的时间复杂度•对足够大的n,有以下顺序0(1)<0(log277)<0(刀)<0(nlog277)<0(刀2) < 0(刀3)V0(2") < …< 0{n\)第二章1、顺序线性表与链式线性表的区别对线性表的操作主要有查找,插入和删除三大类。基于时间上的比较查找时,数组是可以随机存取的,因此查找时间复杂度为0(1),对于链表,每次查找都必须从链表的首结点开始,时间复杂度为0(n),因此查找速率上,数组是优于线性表的。插入和删除时,数组必须首先采用顺序查找的方式定位相应的数据元素,接下来还需要移动大量的数据元素,而链表在插入和删除时,仅需要先定位数据元素,然后通过简单的指针修改即可完成。这方面链表是优于数组的。基于空间上的比较数组的存储空间是预先静态分配的,虽然在实现过程中可以动态拓展,但是如果线性表的长度变化范围较大,空间在使用过程中会存在大量的闲置空间。链表的内存主要被分配为两部分,一部分存储数据元素,另一部分则存储指针域,因此在线性表数据元素结构简单,且长度变化不大时,可以考虑使用数组。2、链表的操作(插入、删除)1线性表操作Listlnsert(&L,i,e)在单链表中的实现:0(ListLength(L))有序对aj>改变为va—e>和v©a,->因此,在单链表中第i个结点之前进行插入的基木操作为:找到线性表中第i-1个结点,然后修改其指向后继的指针。2线性表的操作ListDelete(&L,i,&e)在链表中的实现:O(ListLength(L))有序对vai・l,ai>和vai,ai+l>改变为vaiJ,ai+l>在单链表中删除第i个结点的基本操作为:找到线性表中第i-1个结点p,修改其指向后继的指针。3、链式结构实现一元多项式一般情况下的一元稀疏多项式可写成Pn(x)=pixel+p2xe2+—+pmxem其中:pi是指数为ei的项的非零系数,且 OWel<e2<---<em二n可用下列线性表表示:<(Pi/ex),(p2/e2),—,(pm,em))例如:P999(x)=7x3-2x12-8x"9可用线性表((7,3),(・2,12),(・8,999))表示第四章1、栈和队列的特点通常称,栈和队列是限定只能在表的“端点〃进行插入和删除操作的线性表栈:插入和删除操作均在“栈顶〃进行队列:插入和删除操作分别在“队头〃和〃队尾〃进行2、栈的典型应用例一、数制转换例二、括号匹配的检验算法的设计思想:1) 凡出现左括弧,则进栈;2) 凡幽现右括弧,首先检查栈是否空若栈空,则表明该“右括弧〃多余,出错否则和栈顶元素比较,若相匹配,贝胖左括弧出栈〃,否则表明括号不匹配。3) 表达式检验结束时,若栈空,则表明表达式中匹配正确,否则表明“左括弧〃有余,出错。例三、行编辑程序问题思路:嘉作为输入缓冲区,每当从终端了接受一个字符之后先做如下判别:1:若是退格符#,从栈顶删去一个元素,即出栈Pop;2:若是退行符@,输入缓冲区中的内容回退一行字符。3:若不是#或@,即为有效字符,将该字符入栈,即Push;例四、迷宫求解求迷宫路径算法的基本思想是:若当前位置“可通〃,则纳入路径,继续前进;•若当前位置“不可通〃,则后退,换方向继续探索;•若四周“均无通路〃,则将当前位置从路径中删除出去。设定当前位置的初值为入口位置;do{若当前位置可通,则{将当前位置插入栈顶;若该位置是出口位置,则算法结束;否则切换当前位置的东邻方块为新的当前位置;}否则{}}while(栈不空);若栈不空且栈顶位置尚有其他方向未被探索,则设定新的当前位置为:沿顺吋针方向旋转找到的栈顶位置的下一相邻块;若栈不空但栈顶位置的四周均不可通,则{删去栈顶位置;//从路径中