数据结构与算法设计

一、算法。

1、算法是对特定问题的解决步骤，任何算法都必须通过一定的数据结构才能实现；不同的数据结构将对同一算法的运行效率产生影响；算法不等于程序，程序也不是算法。

2、计算的复杂度：算法的计算量的大小；算法的复杂度分为时间复杂度和空间复杂度。

3、算法的时间复杂度：算法重复执行的次数n，记作：t(n)=o(f(n))；算法的时间复杂度取决于问题的规模和带处理数据的初态。

4、算法的空间复杂度：算法所需存储空间。

5、算法的5个特性：有零个或多个输入、有一个或多个输出、可执行性、确定性和有穷性。

6、从逻辑上分类，数据结构可以分为：顺序结构和链式结构。

7、数据的最小单位：数据项；数据的基本单位：数据元素。

8、健壮的算法不会因为非法的输入数据而出现莫名的状态。

9、数据的物理结构是指数据结构在计算机内的实际存储形式，包括数据元素的表示和数据元素关系的表示。

10、数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。

11、线性表是n个相同类型的数据元素的有限序列，当n>0时出第一个元素无前驱，最后一个元素无后继之外，其余的每一个元素都有一个直接的前驱和后继，数据元素之间是一一对应关系。线性表中元素的个数n为其长度，为0时线性表为空表。

12、数据元素也称记录，含大量类型相同记录的线性表成为文件（或称数据对象）

13、线性表的特点：同一性（同类元素组成），有穷性（有限个），有序性（序偶关系）。矩阵、数组、字符串、堆栈和队列都符合线性条件。

14、线性表的基本存储结构：顺序存储结构、链式存储结构。

15、。这种线性表称为顺序表。

16、顺序表的特点：关系线性化，节点顺序存在。

17、顺序表的基本运算：查找操作，插入操作，删除操作，合并操作。

18、查找操作：1.按序号查找：

getdata(l,i) 查找线性表l中的第i个元素。 2.按内容查找：

locate(l,e)**性表l中查找与给定值e相等的元素；查找运算可以采用顺序查找法实现，即从第一个元素开始依次讲元素与e进行比较，若相等则查找成功，返回该元素在表中的符号，若e与表中所有的元素都不相等则查找失败，返回-1.

19、插入操作：在表的第i个位置前插入一个新元素e，使长度为n的线性表变为长度为n+1的线性表，由于节点的物理结构必须与节点的逻辑结构顺序保持一致，因此当插入一个元素后节点的位置就要移动，当插入在最后一个元素之后则不需要移动。e(ins)=n/2

20、删除操作：在表的第i个位置的元素删去，使长度为n的线性表变为长度为n-1的线性表。由于节点的物理结构必须与节点的逻辑结构顺序保持一致，因此当删除一个元素后节点的位置就要移动，当删除最后一个元素之后则不需要移动。

e(del)=n-1/2

21、在顺序表中插入好人删除一个数据元素时，主要时间耗费在移动数据元素上，做一次插入和删除平均需要移动表中一半元素，当n较大时算法的效率较低。

22、合并操作：指有两个顺序表la和lb，其元素为非递减有序排列，编写一个算法，将他们合并成一个顺序表lc，并要求此顺序表也为非递减有序排列。

23、线性列表的优点：无需为表示节点的逻辑关系而额外增加存储空间；方便的随机存取任意一个元素。缺点：插入和删除操作不方便；存储分配只能预先进行静态分配。

24、线性链表：采用链式存储结构的线性表。可分为单链表，循环链表和双链表，也可分为：动态链表和静态链表。

25、链表与顺序表的区别：顺序表是用地址连续的存储单元来存放结点，链表是任意存储单元。可连续，可不连续，也可是零散分布的；顺序表中结点的逻辑顺序和物理顺序是一致的，链表的逻辑顺序和物理顺序不一定是一致的，但必须有一个结点结构（数据域和指针域：

数据域存放当前的数据元素，指针域存放下一个数据所在的存储单元）。

26、单链表：线性链表通过每个节点的指针域将线性表的n个结点按其逻辑顺序连接在一起，且每个结点只有一个next指针域。头指针标志着整个链表的开始，整个单个链表的操作必须从头指针开始。

27、单链表的操作：初始化单链表，建立单链表，查找，求单链表的长度，插入操作，删除操作。

28、建立单链表：方法：头插法、尾插法。

对于头插法：从一个空表开始，每次读入数据，生成新结点，讲读入数据存放到新结点的数据域中，再将新结点插入到当前链表的表头结点之后，直至读入结束标志为止。头插法得到的单链表的逻辑顺序和输入元素顺序相反，亦称逆序建表法。

29、查找：分为按序号查找和按值查找：对于按序号查找，从链表的头指针出发，顺链域next逐个节点往下搜查。

知道搜索到这个结点的序号为止。（因为每个结点的存储为止都放在前一个结点的指针next域中，故不能直接查找）；对于按值查找：是指在单链表中查找值等于e的结点，查找应从单链表的头指针开始指向的头结点出发，顺链域next逐个将结点的值与定值e作比较，返回搜查结果。

30、求长度：单链表的长度就是从头到尾遍历的过程统计计数。方法：

从“头”开始“数”，用指针p依次指向各个结点，病附设计数器j计数，一直“数”到最后一个结点，从而得到单链表的长度。注：若为空表，则p的初值为null，算法中while循环未执行，j为0；若为非空表，则循环次数为表长度n，则算法的时间复杂度为o（n）.