【数据结构——表】_数据结构表格

第二章

线性表

注意：数据结构的三要素：逻辑结构，数据的运算，存储结构(物理结构)，但是当存储的结构不同的时候，就会出现运算的实现方式不同

1. 线性表的定义

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，其中n为表长，当n=0的时候线性表就是一个空表，若用L命名线性表，则一般表示为L=(a1,a2,…an)

• 相同数据类型：每个数据的所占的空间的一样大

• 线性表是一个有限的有一定顺序的序列

• ai是线性表的“第i个”元素线性表中的位序

• a1是表头元素，an是表尾元素，除了第一个元素之外，每个元素有且仅有一个直接前驱，除了最后一个元素之外，每个元素有且仅有一个直接后驱

• 位序是从1开始的

2. 线性表的基本操作

#include <stdio.h>

void test(int x)
{
    x = 1024;
    printf("test函数内部 x = %d\n",x);
}

int main()
{
    int x = 1;
    printf("调用test前 x = %d\n",x);
    test(x);
    printf("调用test后 x = %d\n",x);
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

顺序表

1. 顺序表的定义(顺序存储)

用顺序存储的方式实现线性表顺序存储，把逻辑上相邻的元素在物理结构上也相邻的存储单元中，元素之间的关系有存储单元的邻接关系来体现

2. 顺序表的实现

顺序表的特点：

• 随机访问：即可以在O(1)时间内找到第i个元素

• 存储密度高：每个节点只存储数据元素

• 拓展容量不方便：即便采用动态的分配方式实现，但是拓展长度的时间复杂度也比较高

• 插入删除操作不方便，需要移动大量的元素

3. 顺序表的插入和删除
   
   
   

4. 顺序表的按位查找和按值查找

如果进行结构类型的比较：

C语言中，结构体的比较不能直接用==，需要一次进行对比各个分量来判断两个结构体是否相等，或者就是定义一个函数进行一个包装，方便以后进行调用

顺序表的优点：可以随机存取，存储密度高，缺点：要求大量的连续空间。改变容量不方便

单链表

1. 单链表的定义

单链表就是通过链式存储的实现线性结构，一个结点存储一个数据元素，各结点间先后关系用一个指针表示，内个结点除了存放数据元素之外，还要存储指向下一个结点的指针，单链表的优点：不要求大片的连续空间，方便改变容量，缺点就是：不可以随机存放，需要消耗一定的空间来存放指针。

2. 单链表的代码实现

不带头结点，写代码会更加的麻烦，对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑对空表和非空表的处理需要用不同的代码逻辑，但是带头结点写代码就很方便，头结点时不存放数据的，只是为了操作方便在头结点的下一个结点才会开始存放数据。

• 不带头结点的单链表
  

• 带头结点的单链表

3. 单链表的插入和删除

单链表具有局限性，无法进行逆向检索，有的时候不太方便

• 单链表的按位序插入

• 指定结点的后插操作

• 指定结点的前插操作

• 单链表的按位序删除

4. 按位按值查找
   

5. 单链表的建立
   

头插法的重要应用就是对链表进行逆序

双链表

1. 双链表的初始化
   

2. 双链表的插入
   
   

3. 双链表的删除
   

4. 双链表的遍历

循环链表

1. 循环单链表

单链表就是表尾结点的next指针指向NULL，但是循环单链表就是表尾的结点的next指针指回头结点，单链表：从一个结点除法只能找到后续的各个结点，但是循环单链表：从一个结点除法可以找到其他任何一个结点

在进行从头部找到尾部的操作时，如果L指向的时头部，此时的时间复杂度就是O(n),但是L指向的时尾部的时候，此时的时间复杂度就是O(1)

大多时候都是对链表的头部和尾部进行操作，当让L指向表尾元素的时候，在进行插入，删除的时候就需要修改L的指向，因为不知道是否是对尾部进行插入还是删除

2. 循环双链表

双链表就是表头结点的prior指向NULL，表尾结点的next指向NULL，但是循环双链表就是表头结点的prior指向表尾结点，表尾结点的next指向头结点

静态链表

静态链表就是用数组的形式实现链表，优点：增删操作不用移动大量的元素，缺点：不能随机存放，只能从头结点开始依次往后查找，容量固定不可变

应用场景:不支持指针的低级语言，数据元素数量固定不变的场景(如操作系统的文件分配表FAT)

顺序表和链表的比较

1. 逻辑结构：二者都属于线性表，都是线性结构，各个元素之间也都是一对一的关系

2. 存储结构：顺序表的优点：支持随机存放，存储密度高，缺点：大片连续的空间分配不方便，改变容量不方便；链表的优点：离散的小空间分配方便，改变容量方便，缺点：不可以随机存放，存储密度低，除了存储数据之外，还需要花费一定的空间进行存放指针，所以存储密度就比较低

3. 基本操作：(创销，增删改查)

• 创

(1)顺序表：需要预分配大片的连续空间，若分配空间过小，则之后不方便拓展容量，若分配空间过大，则浪费内存资源
(2)链表：只需要分配一个头结点，也可以不要头结点，值声明一个头指针，之后也就方便扩展
(3)静态分配：静态数组，容量不可以改变
动态分配：动态数组，容量可以改变，但是需要一定大量的元素，时间代价高

• 销

(1)静态分配：静态数组，系统自动回收空间
(2)动态分配：动态数组，需要手动进行销毁malloc,free
malloc和free必须成对的出现

• 增删

(1)顺序表：插入删除元素都需要进行后续元素都后移或者前移，时间复杂度O(n),时间开销主要来自于移动元素，若数据元素很大，则移动的时间代价就很高
(2)链表：插入删除元素只需要修改指针即可，时间复杂度O(n),时间开销只要来自于查找目标元素，但是查找元素的时间代价更低

• 查找

(1)顺序表：按位查找O(1),按值查找O(n),若表内元素有序，可O(log2n)时间内找到
(2)链表：按位查找和按值查找都是O(n);

问题：请描述顺序表和链表，实现线性表时，用什么比较好？

(1)顺序表和链表的逻辑结构都是线性结构，都属于线性表。
(2)但是二者的存储结构不同，顺序表采用顺序存储，顺序存储的优点就是可以随机存放，存储密度高，缺点就是需要大片连续空间的分配不方便，改变容量不方便，然而链表采用的是链式存储，链式存储的优点就是离散的小空间分配方便，改变容量方便，缺点就是不可以随机存放，并且由于分配的空间不仅需要存放数据元素，还需要有一定的空间来存放指针，所以存储密度低。
(3)由于采用不同的存储方式来实现，因此基本操作的实现效率也不同，当初始化…;当删除一个数据元素时…;…