### 一、线性表定义 线性表:零个或多个数据元素的**有限**序列。(零个的时候是空表) 线性表的特性是:除了第一个元素(只有后继)和最后一个元素(只有前驱),每个元素都只有一个前驱和后继。 ### 二、线性表的抽象数据类型 线性表的抽象数据类型定义如下: ![](https://box.kancloud.cn/2016-02-15_56c1368a15c9c.jpg) ![](https://box.kancloud.cn/2016-02-15_56c1368a342e3.jpg) ### 三、线性表的顺序存储结构 线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。 来看线性表顺序存储结构代码: ![](https://box.kancloud.cn/2016-02-15_56c1368a5bcb5.jpg) 发现描述顺序存储结构需要三个属性: 1.储存空间的起始位置:数组data,它的存储位置就是存储空间的存储位置。 2.线性表的最大存储容量:数组长度MaxSize。 3.线性表的当前长度:length。 下面再讨论一下地址的计算方法: ![](https://box.kancloud.cn/2016-02-15_56c1368a7bc1b.jpg) ### 四、顺序存储结构的插入与删除 获得元素的操作: ![](https://box.kancloud.cn/2016-02-15_56c1368a9a9b8.jpg) ![](https://box.kancloud.cn/2016-02-15_56c1368ab331a.jpg) 插入操作: ![](https://box.kancloud.cn/2016-02-15_56c1368ade4d6.jpg) 删除操作: ![](https://box.kancloud.cn/2016-02-15_56c1368b15c4d.jpg) ![](https://box.kancloud.cn/2016-02-15_56c1368b3118c.jpg) 线性表的顺序存储结构的优缺点: 优点:1.无需为表示表中元素之间的逻辑关系而增加额外的存储空间2.可以快速地存取表中任一位置的元素。 缺点:1.插入和删除操作需要移动大量元素2.当线性表长度变化较大时,难以确定存储空间的容量3.造成存储空间的碎片。 ### 五、线性表的链式存储结构 n个节点链结成一个链表,即为线性表的链式存储结构,因为此链表的每一个节点中只包含一个指针域,所以叫做单链表。 ![](https://box.kancloud.cn/2016-02-15_56c1368b52016.jpg) 把链表中第一个节点的存储位置叫做头指针,最后一个节点指针为空。 ![](https://box.kancloud.cn/2016-02-15_56c1368b663c0.jpg) 一般为了方便对链表进行操作,会在单链表的第一个结点前附设一个结点,成为头结点。头结点的**数据域可以不保存任何信息**。 头指针和头结点的异同: **头指针**是指向头结点的指针;头指针具有标识作用,所以常用头指针冠以链表的名字;无论链表是否为空,头指针均不为空。头指针是链表的必要元素。 **头结点**是为了操作的统一和方便而设立的,放在第一个元素的结点之前,其数据域一般无意义(也可以存放链表的长度);有了头结点,对在第一个元素结点前插入结点和删除第一结点,其操作与其他结点的操作就统一了;头结点不一定是链表的必须元素。 ![](https://box.kancloud.cn/2016-02-15_56c1368b800d0.jpg) 结点的概念:结点由存放数据元素的**数据域**存放后继结点的**指针域**组成。 假设P是指向线性表的第i个元素的指针,则该节点aI的数据域我们可以用p->data来表示,p->data的值是一个数据元素,结点aI的指针域可以用p->next来表示,p->next的值是一个指针。如果p->data=ai,那么p->next->data=aI+1。即: ![](https://box.kancloud.cn/2016-02-15_56c1368b93633.jpg) ### 六、单链表的读取 ![](https://box.kancloud.cn/2016-02-15_56c1368ba594e.jpg) ![](https://box.kancloud.cn/2016-02-15_56c1368bc75db.jpg) 由上面程序看出来,获取链表获取第i个元素比较麻烦。 ### 七、单链表的插入与删除 插入结点: ![](https://box.kancloud.cn/2016-02-15_56c1368bedb79.jpg) 删除结点: ![](https://box.kancloud.cn/2016-02-15_56c1368c1f8c4.jpg) 由算法可以看出,插入和删除对于链表来说每次只需要简单地通过赋值移动指针而已,时间复杂度都是O(1),显然,对于插入和删除数据越频繁的操作,单链表的效率优势就越是明显。 ### 八、单链表的整表创建 头插法: ![](https://box.kancloud.cn/2016-02-15_56c1368c41bd5.jpg) ![](https://box.kancloud.cn/2016-02-15_56c1368c56c7c.jpg) 尾插法: ![](https://box.kancloud.cn/2016-02-15_56c1368c7dbbb.jpg) ![](https://box.kancloud.cn/2016-02-15_56c1368c9b92d.jpg) ### 九、单链表的整表删除 ![](https://box.kancloud.cn/2016-02-15_56c1368cc01aa.jpg) 十、单链表结构与顺序存储结构优缺点 ![](https://box.kancloud.cn/2016-02-15_56c1368ce9584.jpg) ### 十一、循环链表 将单链表的终端结点的指针端由空指针改为指向头结点,就使整个单链表形成了一个环,这种头尾相连的单链表称为单循环链表,简称循环链表。 ![](https://box.kancloud.cn/2016-02-15_56c1368d15961.jpg) 下面研究一下循环链表的合并: ![](https://box.kancloud.cn/2016-02-15_56c1368d28052.jpg) 分成4步: 1.p=rearA->next; 2.rearA->next=rearB->next->next; 3.rearB->next=p; 4.free(p). ### 十二、双向链表 双向链表概念:双向链表是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。 ![](https://box.kancloud.cn/2016-02-15_56c1368d4075e.jpg) 双向链表插入操作: ![](https://box.kancloud.cn/2016-02-15_56c1368d5a8fb.jpg) 同样也分成4步: 1.s->prior=p; 2.s->next=p->next; 3.p->next->prior=s; 4.p->next=s. 双向链表的删除操作: ![](https://box.kancloud.cn/2016-02-15_56c1368d6bf4b.jpg) 分成3步: 1.p->prior->next=p->next; 2.p->next->prior=p->prior; 3.free(p). ### 十三、总结 ![](https://box.kancloud.cn/2016-02-15_56c1368d80688.jpg)