数据结构之线性结构和非线性结构.pdfVIP

数据结构之线性结构和⾮线性结构

线性结构：

⼀、概念

1.线性结构作为最常⽤的数据结构，其特点是数据元素之间存在⼀对⼀的线性关系。

2.线性结构拥有两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的，链式存储的线性表称为链表，链

表中的存储元素不⼀定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。

3.线性结构中存在两种操作受限的使⽤场景，即队列和栈。栈的操作只能在线性表的⼀端进⾏，就是我们常说的先进后出（FILO），队列的插⼊操作在线性表的⼀端进⾏

⽽其他操作在线性表的另⼀端进⾏，先进先出（FIFO），由于线性结构存在两种存储结构，因此队列和栈各存在两个实现⽅式。

⼆、部分实现

1.顺序表（顺序存储）

按照我们的习惯，存放东西时，⼀般是找⼀块空间，然后将需要存放的东西依次摆放，这就是顺序存储。计算机中的顺序存储是指在内存中⽤⼀块地址连续的空间

依次存放数据元素，⽤这种⽅式存储的线性表叫顺序表其特点是表中相邻的数据元素在内存中存储位置也相邻，如下图：

1//倒置线性表

2publicvoidReverse()

3{

4Ttmp=default(T);

5

6intlen=GetLength()-1;

7for(inti=0;i=len/2;i++)

8{

9if(i.Equals(len-i))

10{

11break;

12}

13

14tmp=data[i];

15data[i]=data[len-i];

16data[len-i]=tmp;

17}

18}

2.链表（链式存储）

假如我们现在要存放⼀些物品，但是没有⾜够⼤的空间将所有的物品⼀次性放下（电脑中使⽤链式存储不是因为内存不够先事先说明⼀下...，具体原因后续会说

到），同时设定我们因为脑容量很⼩，为了节省空间，只能记住⼀件物品位置。此时我们很机智的找到了解决⽅案：存放物品时每放置⼀件物品就在物品上贴⼀个⼩纸

条，标明下⼀件物品放在那⾥，只记住第⼀件物品的位置，寻找的时候从第⼀件物品开始寻找，通过⼩纸条我们可以找到所有的物品，这就是链式存储。链表实现的时

候不再像线性表⼀样只存储数据即可，还有下⼀个数据元素的地址，因此先定义⼀个节点类(Node)，记录物品信息和下⼀件物品的位置，我们把物品本⾝叫做数据域，

存储下⼀件物品地址信息的⼩纸条称为引⽤域。链表结构⽰意图如下：

寻找物品的时候发现了⼀个问题，我们从⼀件物品找下

⼀件物品的时候很容易，但是如果要找上⼀件物品就得从头开始找，真的很⿇烦。为了解决这个问题我们⼜机智了⼀把，模仿之前的做法，在存放物品的时候多放置⼀

个⼩纸条记录上⼀件物品的位置，这样就可以很快的找到上⼀件物品了。我们把这种⽅式我们称为双向链表，前⾯只放置⼀张⼩纸条的⽅式称为单向链表。

1//倒置单链表

2publicvoidReverse()

3{

4NodeToldHead=Head;

5NodeTtmp;

6Head=null;//清空链表，解除Head跟oldHead之间的相同引⽤

7

8while(oldHead!=null)

9{