数据结构第二章笔记思维笔记模板_ProcessOn思维导图、流程图

线性表的定义和特点

定义：具有相同特性的数据元素的一个有限序列

构成：线性起点、ai的直接前趋、ai、ai的直接后继、线性终点

特点

数据元素个数n为表长

n=0时为空表

非空线性表记作（a1, a2, a3, ..., an）

ai具体含义在不同情况下可以不同

例子

26个英文字母表、12个星座、学生信息表……

稀疏多项式使用线性表存储时要注意（有两个数据项，一个是系数，一个是指数）

顺序储存结构存在的问题

空间分配不灵活

运算的空间复杂度高

总结

线性表中的数据元素可以为简单类型（数字），也可以为复杂类型（既有字符串，也有整数）

涉及实际问题的基本操作具有很大相似性

要先抽象出逻辑结构和基本操作，然后实现存储结构和基本操作

线性表的类型定义

抽象数据类型线性表定义：

基本操作

InitList(&L)

操作结果：构造一个空线性表L

DestroyList(&L)：

初始条件：表须存在

操作结果：销毁一个线性表L

ClearList(&L)

初始条件：表须存在

操作结果：重置一个线性表L，使其变为空表

ListMepty(L)

初始条件：表须存在

判断L是否为空，若空则返回TRUE，否则返回FALSE

ListLength(L)

初始条件：表须存在

操作结果：返回线性表中的数据元素个数

GetElem(L,i,&e)

初始条件：表须存在， i要满足1 <= i <= ListLength(L)

操作结果：用e返回线性表L中第i个数据元素的值

LocateElem(L,e,compare())

初始条件：表须存在

操作结果：返回L中第一个与满足compare()的数据元素的为序，若无符合条件的元素则返回0（compare()是数据元素的判定函数，可理解为是一个判断条件）

PriorElem(L, cur_e, &pre_e)

初始条件：表须存在

操作结果：若cur_e是L的数据元素且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无意义

NextElem(L, cur_e, &next_e)

初始条件：表须存在

操作结果：若cur_e是L的数据元素且不是最后一个，则用next_e返回它的前驱，否则操作失败，next_e无意义

LIstInsert(&L, i, e)

初始条件：表须存在。1 <= i <= ListLength(L) + 1

操作结果：在L的第i个位置之前插入新的数据元素e, L长度加1

ListDelete(&L, i, &e)

初始条件：表须存在，1 <= ListLength(L)

操作结果：删除L的第i个数据元素，并用e返回已经删除的元素的值，L长度减一

ListTraverse(&L, visited())

初始条件：表须存在

操作结果：依次对线性表中的每个元素调用visited(),（遍历一遍线性表，每一个都进行一个相同的操作visited()，可以是修改，输出等等）

总结：以上只是逻辑结构上定义的运算，实现细节在确定存储结构后才考虑

线性表的顺序表示和实现

线性表的顺序存储表示

顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构（地址需连续，若地址不连续——中间存在空的存储单元则其不是一个线性表顺序存储结构）

需要占用一片连续的空间——可以由每个元素需要的存储单元l推算出每个数据元素的存储位置

顺序存储结构是一种随机存取的存储结构

可以用一维数组表示顺序表

线性表长可变

数组长度不可动态定义

可以用一变量表示顺序表的长度属性

线性表定义方式SqList:Sequence List

类C语言有关操作补充

元素类型说明：ElemType可以是int、char、float等类型，length表示顺序表中元素个数

数组的静态分配和动态分配，使用时：L.data = (ElemType*)malloc(sizeof(Elemtype)*MAXSIZE), L.length存放元素个数

动态分配内存

malloc(m)函数：开辟m字节长度的地址空间，返回这段空间的首地址

例：L.data = (ElemType*)malloc(sizeof(Elemtype)*MAXSIZE)，sizeof(ElemType)*MAXSIZE表示出分配的字节长度后，用ElemType*告诉计算机这段空间存放的数据类型是什么，即把这m字节的空间划分成多少块用来存放特定类型的数据

需要加载头文件<stdlib.h>

sizeof(x)函数

free(p)函数

C++中的动态存储分配

new 类型名T （初值列表）

结果值：成功时，T类型的指针，指向新分配的内存；失败时，0

C++中的参数传递

要注意形参与实参的类型、个数、顺序一致

方式

传值（整型、实型、字符型）

传地址

指针变量

形参变化可以影响实参、也可以不影响实参

影响

不影响

数组名

对形参数组所做的任何改变都将反映到实参数组中

引用类型

形参变化实参也发生变化

是相当于对实参进行直接操作，所以当传递的数据量较大时，用此方法比较好

逻辑为序与物理为序相差1

操作算法中用到的预定义常量和类型

结果状态代码

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

typedef int Status Status是函数的类型，值是函数结果状态代码

typedef char ElemType

顺序表基本操作的实现

查找

平均查找长度ASL（Average Search Length）:需要与给定值进行比较的关键字的个数的期望值

假设每个记录查找的概率相等，则ASL=（n+1）/2,时间复杂度为O(n)

插入

平均移动次数为 n/2，时间复杂度为O(n)

向第i个元素之前插入一个新元素时，需要向后移动n+1-i个元素

删除

平均移动次数：（n-1）/2

删除第i个元素，需要向前移动n-i个元素

顺序表（线性表的顺序存储结构）的小结

顺序表的特点

逻辑结构与存储结构一致

访问每个元素所花的时间相等

存取元素的方法为随机存取法

优点

存储密度大

可随机存取表中的任意一个元素

缺点

插入或删除某个元素时，需要移动大量元素

浪费存储空间

数据元素的个数不能自由扩充

线性表的链式表示和实现

与链式存储有关的术语

结点：是数据元素的储存映像，由数据域和指针域组成。

链表：n个结点由指针链组成的一个链表，是线性表的链式存储映像，称为线性表的链式存储结构。

单链表：每个结点上只有一个指针域的链表，又称线性链表

双链表：每个结点上有两个指针域，一个指向前一个，一个指向后一个

循环链表：首尾相接的链表

头指针：指向链表中第一个结点的指针

首元结点：链表中存储第一个数据元素a1的结点

头节点：链表首元结点之前附设的一个结点

空的表示：“^”

关于链表的一些讨论

空表的表示？

无头结点时，头指针为空表示空表

有头结点时，头结点指针域为空表示空表

设置头结点的好处？

便于首元结点的处理

便于空表和非空表的统一处理

头结点的数据域内装什么内容？

可以为空，或者表的属性信息，但不能算入表长

链表的特点

在存储器上的位置任意，逻辑上相邻的元素物理上不一定相邻

访问时只能通过头指针进入链表，因此寻找第一个和最后一个结点所需时间不等——顺序存取法

单链表的定义和表示

定义方式

Lnode表示的是结点、LinkList为指向Lnode的指针类型

定义链表L：LinkList L;

定义节点指针p：LNode *p; ←→LinkList p;

为了统一操作，通常这样定义

单链表基本操作的实现

一些重要操作

p指向头结点：p=L;

p=L->next：p指向首元结点

p=p->next：p指向下一结点

初始化

步骤：生成新结点作为头结点；用头指针L指向头结点；将头结点的指针域置空；

算法描述

判断链表是否为空

思路：判断头结点的指针域是否为空：（if(L->next)）

销毁

思路：从头指针开始，依次释放所有结点

p=L; L=L->next; free(p);

结束条件：L==NULL;

清空

思路：从首元结点开始依次释放所有结点，并将头结点的指针域置空

p=L->next; whlie(p) {q=p->next; free(p); p=q;} ……L->next=NULL;

结束条件：p==NULL; 循环条件：P!=NULL;

求链表表长

思路：从首元结点开始，依次计数所有结点

（首结点不为空的情况下）p=L->next;while(p!=NULL){i++;p=p->next} return i;

取第i个元素的内容

思路：从头指针出发，顺着链域next逐个结点依次搜索，直到到了第i个结点为止（链表不是随机存取结构）；特殊情况：i不合法或者找不到

步骤：从第一个节点开始（p=L->next），计数器j当前值为1；p扫描到下一结点时，计数器j加一；j==i时，返回当前值。

查找

按值查找——获取数据所在的地址

步骤：从第一个节点开始，依次将e和节点内数据相比较；如果找到了，返回其在链表中的“位置”，即第几个元素，或者地址；若没找到则返回NULL或者0

按值查找——获取指定数据的位置序号

插入

步骤：首先找到第i-1个结点的位置p；生成一个数据域为e的新结点s；①新结点的指针域指向第i个结点②第i-1个结点的指针域指向新结点

s->next=p->next; p->next=s;

下图中j从零开始计数是因为p一开始指向的是头结点

删除

步骤：首先找到第i-1个元素的位置p，进而保存要删除的第i个元素的值(可以用q)；令p->next指向第i+1个元素；释放第i个元素结点的空间

p->next = p->next->next;

单链表的查找、插入、删除算法的时间效率分析

查找：O(n);

插入和删除：O(1);(这两个操作都需要借助查找操作，所以总的时间复杂度还是O(n))

对于已知结点的后继结点操作时，时间复杂度为O(1)，而对于前驱结点操作时，时间复杂度为O()

单链表的建立

头插法——每一个新元素插入到首元结点的前面

空表；生成新结点，将读入的数据放到新结点的数据域中；将该新结点插入到首元结点的前面

L = (LinkList)malloc(sizeof(LNode)); //生成头结点

数据的输入顺序和逻辑顺序是相反的：如输入abcde，存放时按edcba存放

该算法的时间复杂度为O(n)

尾插法——每一个新元素插入到最后一个结点的后面

建立空表；建立新结点，p->data=a;p->next=NULL(给新结点赋值)，令尾指针指向这个新结点r->next=p;再将该结点设置为尾结点 r=p；（初始时，尾指针与头指针均指向头结点）

该算法的时间复杂度为O(n)

循环链表

定义：是一种头尾相接的链表，即最后一个结点的指针域指向头结点

优点：从任意结点出发均可以找到其他结点

空表的表示：头结点的指针域指向头结点

注意

进行遍历操作时，终止条件由是否等于NULL变为是否等于头指针

表的操作通常在首位位置上进行

通常使用尾指针来操作

例子：两个循环链表的合并

p存放表头指针；表2首元结点连接到表1尾端；释放表2头结点；修改表2尾指针，使其指向表1头结点p

下列算法时间复杂度为O(1)

双向链表

定义：在单链表的每个结点上再增加一个指向其直接前驱的指针域prior,这样就形成了两个方向不同的链

双向循环链表：头结点的前驱指针指向尾结点；尾结点的后继指针指向头结点

空表的表示：头结点的前驱结点和后继节点都指向自身

对称性：p->next->prior == p == p->prior->next

操作

插入

步骤（x插入到a、b之间）

把b的前驱指针赋给x的前驱指针：s->prior = p->prior;

将x变为a的后继节点：p->prior->next = s;

将b变为x的后继节点：s->next = p;

让b的前驱指针指向x：p->prior = s;

删除

步骤(abc中删除b，p指向b)

让a的后继指针指向c：p->prior->next = p->next

让c的前驱指针指向a：p->next->prior = p->prior

free(p)

该算法的时间复杂度为O(1)

链表与顺序表的比较

链表的优点

空间可以申请和释放

插入与删除时不需要移动元素

链表的缺点

存储密度小：每个指针域需要占用额外的空间（存储密度=结点中数据占用的空间/结点占用的总空间（数据/总空间））

非随机存取结构

单链表、循环链表和双向链表的时间效率比较

线性表的应用

线性表的合并

问题描述：将两个线性表La和Lb合并，合并出的新集合是原来所有集合的一个并集，即相同的元素只能出现一次

步骤：依次取出Lb中的每个元素执行以下操作

在La中寻找该元素

若找到则直接选择Lb中的下一个元素，若找不到，则插入到La的最后

该算法的时间复杂度为O(ListLength(La)*ListLength(Lb))

ListInsert(&La, ++La_len, e); 的含义是：在表La中La_len+1位置处插入e，并且La_len增加1

有序表的合并

问题描述：线性表La和Lb中的元素非递减排列，要求将这两个表合并为一个新表Lc，且Lc中的数据元素仍然按按值非递减有序排列。

步骤

创建一个空表Lc

从La和Lb中获取较小值的结点插入到Lc最后，直至其中一个变为空表

将另一个表的剩余节点插入到表Lc的最后

用顺序表实现

该算法的时间复杂度为：O( ListLength(La) + ListLength(Lb) )

该算法的空间复杂度为：O( ListLength(La) + ListLength(Lb) )

用链表实现

该算法的时间复杂度为O(ListLength(La) + ListLength(Lb))

该算法的空间复杂度为O(1)

案例分析与实现

一元多项式的运算

用顺序表来实现

稀疏多项式的运算

特点：里面有很多系数为零的项

用顺序表来实现：二维数组

步骤

创建一个新数组c

从头遍历a和b，若指数相同，就将对应系数相加，若系数为零就舍去，不为零就在c中添加一个新项

指数若不相同，就把较小的那个复制到c中

一个多项式遍历完毕时，将另一个中剩下的项复制到c中

用链表来实现

思路

定义

初始化

步骤

图书信息管理系统

如果数量大，不常进行修改操作：顺序表

定义

如果数量不大，常常进行修改操作：链表

定义