线性表的概念:

一个线性表是由n个具有相同特性的数据元素的有限序列.(这里面有三个关键词,必须同时满足这3个条件才算是线性表)

线性表的特点:

1)元素个数有限

2)元素具有逻辑上的顺序性,在序列中各元素排序有先后次序

3)元素都是数据元素,每个元素都是单个元素

4)元素的数据类型都相同,每个元素都占有大小相同的存储空间

5)元素具有抽象性(仅讨论元素间的逻辑关系,而不考虑元素表示什么内容)

线性表是一种逻辑结构,表示在元素之间一对一的相邻关系,顺序表和链表是指存储结构,两者属于不同层面的概念.

线性表的位序是从1开始,而数组元素的下标是从0开始

线性表的顺序表示-----顺序表

顺序表:是用一组地址连续的存储单元依次存储线性表中的数据元素.使逻辑上相邻和2个元素物理位置上也相邻.

顺序表的特点

1)随机访问

2)存储密度高.每个结点只存储数据元素

3)插入和删除需要移动大量的元素.

4)拓展容量不方便

5)顺序表容易实现,任何高级语言都有数组类型,链表的操作是基于指针的.

6)静态分配时,装满就不能再扩充,加入新的元素会出现内存溢出.因此需要预先分配.太大容易闲置浪费,太小容易溢出.

动态分配虽然可以扩充,但需要移动大量元素,操作效率低.内存中没有更大块的内存空间会导致分配失败.

顺序表适用于表长可以估计,不需要经常增删

静态链表是用数组实现的也叫游标实现法

线性表的链式表示---链式表

不需要在逻辑上相邻的在物理上也相邻,不需要移动元素值需要修改指针就行.每个链表的结点除了存放自身的信息以外还需要存放一个指向后继的指针(数据域和指针域),所以要是删除整个链表的时候就需要注意了,如果直接把指向下一个的指针删掉就找不到下一个该删谁了

单链表

解决了:顺序表需要大量连续空间的问题.

带来了:附加指针域会带来较大的空间开销,元素离散分布不能达到随机存取.

循环单链表

和单链表的区别就是,最后的结点不是空,而是指向了头结点

双链表

解决了:单链表只有一个指向后继的指针

循环双链表

双链表的前驱指针还要指向尾结点

概念区分

字符:也可以认为字符构成数据项

数据项:一个数据元素由若干个数据项组成

数据元素:组成数据对象的基本单位

数据对象:性质相同的数据元素的集合

举个例子:做表格的时候,张三,男 ,汉族等等为数据项.张三的所有信息加起来一条就是数据元素.所有人的数据元素就是数据对象.