数据结构学习笔记（线性表）

　　1.基础概念：

　　*数据（（数据对象（数据元素（数据项）））------包含关系。　

　　*数据结构是互相之间存在一种或多种特定关系的数据元素的集合。

　　*逻辑结构：集合机构，线性结构，树形结构，图形结构。

　　*物理结构：顺序储存结果、链接储存结构。

　　2.算法效率问题：

　　*判断一个算法的效率时，函数中的常熟和其他次要项常常可以忽略，而更应该关注主项（最高次项）的阶数。 最高次项的指数大的，函数随着n的增长，结果也会变得增长特别快。

　　*常数项：不管这个常数是多少，我们都计作O(1)。

　　*单纯的分支结构（不包含在循环结构中），其时间复杂度也是O(1)。

　　*推导大O阶（时间复杂度）方法： 　　a.用常数1取代运行时间中的所有加法常数。 　   b.在修改后运行次数函数中，只保留最高阶项。 　　c.如果最高阶项存在且不是1，则去除与这个项相乘的常熟，得到的结果就是大O阶。

　　*对算法的分析，一般在没有特殊说明的情况下，都是指最坏时间复杂度。

　　*当不用限定词地使用“复杂度”时，通常都是指时间复杂度。

　　*算法的定义：算法是解决特定问题求解步骤的描述，在计算机中为指令的有限程序列，而且每条指令表示一个或者多个操作。 　　*算法的特性：有穷性、确定性、可行性、输入、输出。 　　*算法的设计的要求：正确性、可读性、健壮性、高效率和低储存量的要求。 　　*算法的度量方法：事后统计方法（不科学、不准确）、事后分析估算方法。

　　3.线性表

　　线性表：零个或多个数据元素的有限序列。 　　首先它是一个序列，元素之间是有顺序的，其次，线性表是有限的。

　　在任意时刻，线性表的长度应该小于等于数组的长度。

　　一些操作：

　　ADT 线性表（List) 　　Data 　　线性表的数据对象集合为{a1,a2,......,an}，每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一　个元素an外，每一个元素有且只有一个直接后置元素。数据元素之间的关系是一对一的关系。 　　Operation 　　InitList(*L): 初始化操作，建立一个空的线性表L。 　　ListEmpty(L): 若线性表为空，返回true，否则返回false。 　　ClearList(*L): 将线性表清空。 　　GetElem(L,i,*e) 将线性表L中的第i个位置元素值返回给e。 　　LocateElem(L,e): 在线性表L中查找与给定值e相等的元素，如果查找成功，返回钙元素在表中序号表示成功；否则，返回0表示失败。 　　ListInsert(*L,i,e): 在线性表L中的第i给位置插入新元素e. 　　ListDelete(*L, i, *e): 删除线性表L中第i个位置元素，并用e返回其值。 　　ListLength(L): 返回线性表L的元素个数。 　　endADT

　　4.顺序存储结构：

　　顺序存储结构需要三个属性： 　　a.存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。 　　b.线性表的最大存储容量：数组长度MAXSIZE。 　　c.线性表的当前长度：length。

　　线性表顺序存储结构 　　优点：*无须为表示表中元素之间的逻辑关系而增加额外的存储空间 　　*可以快速地存取表中任一位置的元素 　　缺点：*插入和删除操作需要移动大量元素 　　*当线性表长度变化较大时，难以确定存储空间的容量 　　*造成存储空间的“碎片”

　　线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O[1]；而插入或者删除时，时间复杂度都是O[n]。这说明，它比较适合元素个数不太变化，而更多存取数据的应用。

　　插入算法ListInsert(*L, i, e)的思路： 　　*如果插入位置不合理，抛出异常； 　　*如果线性表长度大于等于数组长度，则抛出异常或动态增加容量； 　　*从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置； 　　将要插入元素填入位置i处； 　　*表长加1。 　　删除算法ListDelete(*L, i, *e)的思路； 　　*如果删除位置不合理，抛出异常； 　　*取出删除元素； 　　*从删除元素位置开始遍历到最后一个元素，分别将它们都向前移动一个位置； 　　*表长减1。

　　5.头指针与头结点：

　　头指针： 　　*头指正是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针 　　*头指针是具有标识作用，所以常用头指针冠以链表的名字 　　*无论链表是否为空，头指针均不为空。头指针是链表的必要元素。 　　头结点： 　　*头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度） 　　*有了头结点，对在第一元素结点前和删除第一结点，其操作与其它结点的操作就统一了 　　*头结点不一定是链表必须要素。

　　6.单链表：

　　malloc函数：向系统申请分配指定size个字节的内存空间。返回类型是 void* 类型。

　　对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。

　　获得单链表第i个数据的算法GetElem(L,i,*e)思路： 　　*声明一个结点P指向链表第一个结点，初始化j从1开始； 　　*当j<i时，就遍历链表，让P的指针向后移动，不断指向下一结点，j累加1； 　　*若到链表末尾P为空，则说明第i个元素不存在； 　　*否则查找成果，返回结点P的数据。

　　单链表第i个数据插入结点的算法思路： 　　*.声明一结点P指向链表第一个结点，初始化j从1开始； 　　*.当j<i时，就遍历链表，让P的指针向后移动，不断指向下一结点，j累加1； 　　*.若到链表末尾P为空，则说明第i个元素不存在； 　　*.否则查找成功，在系统中生成一个空结点s; 　　*.将数据元素e赋值给s->data; 　　*.单链表的插入标准语句s->next=p->next; p->next=s; 　　*.返回成功。

　　单链表第i个数据删除结点的算法思路：

　　*声明一结点p指向链表第一个结点，初始化j从1开始； 　　*当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1； 　　*若到链表末尾p为空，则说明第i个元素不存在； 　　*否则查找成功。将欲删除的结点p->nest赋给去q； 　　*单链表的删除标准语句p->next=q->next； 　　*将q结点中的数据赋值给e，作为返回； 　　*释放q结点； 　　*返回成功。

　　单链表整表创建的算法思路： 　　*声明一结点p和计数器变量i； 　　*初始化一空链表L； 　　*让L的头结点的指针指向NULL，即建立一个带头结点的单链表； 　　*循环： 　　*生成一新节点赋值给p； 　　*随机生成一数字赋值给p的数据域p->data; 　　*将p插入到头结点与前一新节点之间。

　　单链表整表删除的算法思路： 　　*声明一结点p和q； 　　*将第一个结点赋值给p； 　　*循环： 　　*将下一个结点赋值给q； 　　*释放p； 　　*将q赋值给p。

　　7.顺序存储结构与单链表的区别：

　　单链表结构与顺序存储结构优缺点 　　存储分配方式： 　　*顺序存储结构用一段连续的存储单元一次存储线性表的数据元素 　　*单链表采用链式存储单元存放线性表的元素 　　时间性能 　　*顺序存储结构O(1)、单链表O(n); 　　*插入和删除：顺序存储结构需要平均异动表长一半的元素，时间为O(n); 单链表在线处某位置的指针后，插入和删除时间仅为O(1)。 　　空间性能： 　　*顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢 　　*单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。

　　总结： 　　*若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。 　　*当线性表中的元素个数变化较大或者根本不知道有多大时，最后用单链表结构，这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，用顺序存储结构效率会高很多。

　　8.静态链表优缺点：

　　*优点：在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。 　　*缺点：没有解决连续存储分配带来的表长难以确定的问题；失去了顺序存储结构随机存取的特性。 　　总结：静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法。

　　9.循环链表：将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

并不是说，循环链表一定要头结点。

　　10.双向列表：双向列表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。

　　/*线性表的双向链表存储结构*/ 　　typedef struct DulNode 　　{ 　　ElemType data; 　　struct DulNode *prior; /*直接前驱指针*/ 　　struct DulNode *next; /*直接后继指针*/ 　　}DulNode, *DuLinkList; 　　双向列表在插入和删除时，需要更改两个指针变量。

　　插入： 　　s->prior = p; /*把p赋给s的前驱*/ 　　s->next = p->next; /*把p->next赋给s的后继*/ 　　p->next->prior = s; /*把s赋值给p->next的前驱*/ 　　p->next = s; /*把s赋给p的后继*/ 　　顺序是先搞定s的前驱和后继，再搞定后结点的前驱，最后解决前结点的后继。

　　删除： 　　p->prior->next = p->next; /*把p->next赋值给p->prior的后继*/ 　　p->next->prior = p->prior; /*把p->prior赋值给p->next的前驱*/

　　11.总结：

　　线性表分为顺序存储结构和链式存储结构，其中链式存储结构包括：单链表、静态链表、循环链表和双向链表这四种。