线性表

线性表的顺序和实现

获取线性表中第i个元素的内容:

线性表的插入

在线性表的第i个位置上,插入一个元素,考虑的问题:存储空间是否满了?插入位置是否合理?线性表的长度也要增加

首先判断存储空间,满了就不能让他插入,插入就会溢出

时间的复杂度:1.既不考最好的情况,也不考虑最坏的情况,我们考虑平均的情况,

线性表的删除

将线性表L中第i个元素删除:

元素逐个前移,覆盖掉被删除的元素,需要维护元素个数的记录

分析:顺序存储结构表示的线性表,在做插入或删除操作时,平均需要移动大约一半的数据元素.当线性表的数据元素量较大,

并且经常要对其做插入或删除操作时,这一点需要值得考虑.

线性表的链式表示和实现

链式表示:用一组任意的存储单元存储线性表
- 　　存储单元不要求连续:物理结构不反应逻辑结构
- 　　不可以随机存取,但插入和删除方便
- 　　需要两个域:一个表示数据本身,一个表示数据元素间的先后关联.- 一个结点
- 　　结点中表示关联的部分为指针域,内部存放指针或链.n个结点链接成一个链表.

单链表:

为每个元素关联一个链接,表示后继关系.
结点:元素的存储映像,包括数据域和指针域.
与表中n个元素对应的n个结点通过指针链接成一个链表.链表中每个结点只有一个指针域的存储映像,包括数据域和指针域
头指针:指单链表第一个结点的存储位置的指针,整个链表的存取必须从头指针开始
- 　　头指针是指链表指向第一个结点的指针,若链表有头结点,则指向头结点的指针
- 　　头指针具体标识作用,常用头指针冠以链表的名字
- 无论链表是否为空,头指针均不为空.是链表的必要元素
头结点
- 　　头结点是为了操作的统一和方便二设立的,放在第一元素结点之前,其数据域一般无意义
- 头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其他结点的操作就统一
- 　　头结点不一定是链表的必须要素

幻想毫无价值，计划渺如尘埃，目标不可能达到。这一切的一切毫无意义——除非我们付诸行动。