祝桥建设网站,深圳东门步行街在哪个区,深圳建设项目信息网,搜索引擎优化seo怎么做第二章 线性表
2.1 线性表的定义
2.1.1 线性表的基本概念
线性表是具有相同数据类型的n(n0)个数据元素的有限序列#xff0c;其中n为表长#xff0c;当n0时线性表是一个空表。若用L命名线性表#xff0c;则其一般表示为#xff1a; L(a1,a2,...,ai,ai1,...,an)L(a_1…第二章 线性表
2.1 线性表的定义
2.1.1 线性表的基本概念
线性表是具有相同数据类型的n(n0)个数据元素的有限序列其中n为表长当n0时线性表是一个空表。若用L命名线性表则其一般表示为 L(a1,a2,...,ai,ai1,...,an)L(a_1,a_2,...,a_i,a_{i1},...,a_n) L(a1,a2,...,ai,ai1,...,an)
几个概念
aia_iai是线性表中的“第i个”元素线性表中的位序 注意位序从1开始数组下标从0开始
a1a_1a1是表头元素ana_nan是表尾元素
除第一个元素外每个元素有且仅有一个直接前驱除最后一个元素外每个元素有且仅有一个直接后继
2.1.2 线性表的基本操作
InitList(L): 初始化表。构造一个空的线性表L分配内存空间。——从无到有
DestroyList(L): 销毁操作。销毁线性表并释放线性表L所占用的内存空间。——从有到无
ListInsert(L,i,e): 插入操作。在表L中的第i个位置上插入指定元素e。——增
ListDelete(L,i,e): 删除操作。删除表L中第i个位置的元素并用e返回删除元素的值。——删
LocateElem(L,e): 按值查找操作。在表L中查找具有给定关键字值的元素。——查改之前也要查
GetElem(L,i): 按位查找操作。获取表L中第i个位置的元素的值。
其他常用操作
Length(L): 求表长。返回线性表的长度即L中数据元素的个数。
PrintList(L): 输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L): 判空操作。若L为空表则返回true否则返回false。
Tips:
① 对数据的操作记忆思路——创销、增删改查
② C语言函数的定义——返回值类型函数名参数1类型,参数2类型,…
③ 实际开发中可根据实际需求定义其他的基本操作
④ 函数名和参数的形式、命名都可改变
⑤ 什么时候要传入引用 对参数的修改结果需要“带回来”
2.2 顺序表的定义
2.2.1. 顺序表的基本概念
线性表的顺序存储又称 顺序表 。它是用一组地址连续的存储单元依次存储线性表中的数据元素从而使得**逻辑上相邻的两个元素在物理上也相邻。**顺序表的特点是 表中元素的逻辑顺序与其物理顺序相同。
特点
随机访问即可以在 O(1) 时间内找到第 i 个元素。 顺序表最大的特点是随机访问可通过首地址和元素序号在O(1)的时间复杂度内找到指定的元素因为顺序表是连续存放的。 存储密度高每个节点只存储数据元素。 拓展容量不方便即便采用动态分配的方式实现拓展长度的时间复杂度也比较高因为需要把数据复制到新的区域。 插入删除操作不方便需移动大量元素O(n) 2.2.2. 顺序表的实现
静态实现
// 顺序表实现静态分配
#define MaxSize 10#include stdio.h
#include stdlib.htypedef struct {int data[MaxSize];int length;
} SqList;void InitList(SqList L) {L.length 0;
}int main() {SqList L;InitList(L);for (int i 0; i MaxSize; i) {printf(data[%d]%d\n, i, L.data[i]);}printf(%d, L.length);return 0;
}Q如果“数组”存满了怎么办 A可以放弃治疗顺序表的表长刚开始确定后就无法更改存储空间是静态的 动态实现
//顺序表实现动态分配
#define InitSize 10 // 初始化顺序表的长度#include stdio.h
#include stdlib.htypedef struct {int *data; // 声明动态分配数组的指针int MaxSize; // 最大长度int length; // 当前长度
} SeqList;// 初始化顺序表
void InitList(SeqList L) {// 用malloc函数申请一片连续的存储空间L.data (int *) malloc(sizeof(int) * InitSize);L.length 0;L.MaxSize InitSize;
}// 增加动态数组的长度本质上是将数据从旧的区域复制到新区域
void IncreaseSize(SeqList L, int len) {// 使p指针和data指向同一目标int *p L.data;L.data (int *) malloc(sizeof(int) * (L.MaxSize len)); // 申请一块新的连续空间用于存放新表并将data指针指向新区域for (int i 0; i L.length; i) {L.data[i] p[i]; //将数据复制到新区域}L.MaxSize len;free(p); //释放原区域的内存空间
}// 打印顺序表
void printList(SeqList L) {for (int i 0; i L.length; i) {printf(%d, , L.data[i]);}
}int main() {SeqList L;InitList(L);printf(增加前顺序表的长度%d \n, L.MaxSize);printList(L);IncreaseSize(L, 5);printf(增加后顺序表的长度%d \n, L.MaxSize);return 0;
}malloc() 函数的作用会申请一片存储空间并返回存储空间第一个位置的地址也就是该位置的指针。 2.2.3. 顺序表的基本操作
插入
ListInsert(L,i,e): 插入操作。在表L中的第i个位置位序上插入指定元素e。
// 将元素e插入到顺序表L的第i个位置
bool ListInsert(SqList L, int i, int e) {if (i 1 || i L.length 1)return false;if (L.length MaxSize)return false;for (int j L.length; j i; j--) { // 将第i个元素及之后的元素后移L.data[j] L.data[j - 1];}L.data[i - 1] e; // 在位置i处插入元素eL.length;return true;
}最好时间复杂度O(1)插入在表尾 最坏时间复杂度O(n)插入在表头 平均时间复杂度O(n) 删除
ListDelete(L,i,e): 删除操作。删除表L中第i个位置的元素并用e返回删除元素的值。
bool ListDelete(SqList L, int i, int e) {if (i 1 || i L.length) { //判断i的范围是否有效return false;}e L.data[i - 1];for (int j i; j L.length; j) { //将第i个位置后的元素前移L.data[j - 1] L.data[j];}L.length--;return true;
}最好时间复杂度O(1)删除表尾元素 最坏时间复杂度O(n)删除表头元素 平均时间复杂度O(n) 查找
按位查找GetElem(L,i): 按位查找操作。获取表L中第i个位置的元素的值。
// 按位查找
int getElemByLoc(SqList L, int i) {return L.data[i - 1];
}时间复杂度O(1) 由于顺序表的各个数据元素在内存中连续存放因此可以根据起始地址和数据元素大小立即找到第i个元素——“随机存取”特性。
按值查找LocateElem(L,e): 按值查找操作。在表L中查找具有给定关键字值的元素。
int getElemByValue(SqList L, int value) {for (int i 0; i L.length; i) {if (L.data[i] value) {return i 1; //返回其位序}}return 0;
}注意C语言中结构体的比较不能直接用“”需要依次对比各个分量来判断两个结构体是否相等 最好时间复杂度O(1)目标元素在表头 最坏时间复杂度O(n)目标元素在表尾 平均时间复杂度O(n) 2.3 链表
2.3.1 单链表 单链表用链式存储实现了线性结构。一个结点存储一个数据元素各结点间的前后关系用一个指针表示。特点 优点不要求大片连续空间改变容量方便。插入和删除操作不需要移动大量元素缺点不可随机存取要耗费一定空间存放指针。 两种实现方式 带头结点写代码更方便。头结点不存储数据头结点指向的下一个结点才存放实际数据。L-next NULL)不带头结点麻烦。对第一个数据结点与后续数据结点的处理需要用不同的代码逻辑对空表和非空表的处理需要用不同的代码逻辑。(L NULL)
用代码定义一个单链表中结点类型的描述如下
//用代码定义一个单链表
typedef struct LNode { //定义单链表结点类型int data; //每个结点存放一个数据元素struct LNode* next; //由于指针域中的指针要指向的也是一个节点因此要声明为 LNode 类型
} LNode, *LinkList; //这里的*LinkList强调元素是一个单链表.LNode强调元素是一个节点。本质上是同一个结构体单链表的元素离散分布在各个存储空间中是非随机存取的存储结构不能直接找到表中每个特定的结点。查找结点时需要从头往后依次遍历。
2.3.2 单链表的基本操作
1、单链表的初始化
// 不带头结点
bool InitList(LinkList L) {L NULL; // 空表不含任何结点return true;
}// 带头结点
bool InitListWithHeadNode(LinkList L) {L (LNode *) malloc(sizeof(LNode)); // 分配一个头结点if (L NULL) { // 内存不足分配失败return false;}L-next NULL; // 头结点之后暂时还没有结点return true;
}2、头插法建立单链表 头插法的一个重要应用单链表的逆置 // 头插法建立单链表
LinkList List_HeadInsert(LinkList L) {LNode *s;int x;L (LinkList) malloc(sizeof(LNode));L-next NULL;cout 请输入结点的值输入9999结束 endl;cin x;while (x ! 9999) {s (LNode *) malloc(sizeof(LNode)); // 创建新结点s-data x;s-next L-next;L-next s;cin x;}return L;
}3、尾插法建立单链表 // 尾插法建立单链表
LinkList List_TailInsert(LinkList L) {int x;L (LinkList) malloc(sizeof(LNode));LNode *s;LNode *r L; // 尾指针cout 请输入结点的值输入9999结束 endl;cin x;while (x ! 9999) {s (LNode *) malloc(sizeof(LNode));s-data x;r-next s;r s;cin x;}r-next NULL;return L;
}头插法、尾插法核心就是初始化操作、指定结点的后插操作 尾插法注意设置一个指向表尾结点的指针 头插法的重要应用链表的逆置 动手试一试给你一个LinkList L 如何逆置 4、按位查找结点
在单链表中从第一个结点出发顺指针next 域逐个往下搜索直到找到第i个结点为止,否则返回最后一个结点指针域NULL。
// 从单链表中查找指定位序的结点并返回
LNode *getElem(LinkList L, int i) {if (i 0) {return NULL;}LNode *p;int j 0; // 定义一个j指针标记下标p L; // p指针用来标记第i个结点while (p ! NULL j i) { // pNULL 超出表长,返回空值 ji 超出所查询元素的下标p p-next;j; // j指针后移}return p;
}5、按值查找结点
从单链表的第一个结点开始由前往后依次比较表中各结点数据域的值若某结点数据域的值等于给定值e则返回该结点的指针;若整个单链表中没有这样的结点则返回NULL。
LNode *LocateElem(LinkList L, int value){LNode *p L-next;while(p!NULL p-data ! value){p p-next;}return p;
}6、头插法插入元素
插入结点操作将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性然后找到待插入位置的前驱结点即第i-1个结点再在其后插入新结点。
算法首先调用按序号查找算法GetElem(L,i-1)查找第i-1个结点。假设返回的第i-1个结点为p然后令新结点s的指针域指向p 的后继结点再令结点p 的指针域指向新插入的结点*s。 // 在第i个元素前插入元素value
bool ListInsert(LinkList L, int i, int e) {if (i 1)return false;LNode *p; //指针p指向当前扫描到的结点int j 0; //当前p指向的是第几个结点p L; //循环找到第i-1个结点while (p ! NULL j i - 1) { //如果ilenghp最后会等于NULLp p-next;j;}//p值为NULL说明i值不合法if (p NULL)return false;//在第i-1个结点后插入新结点LNode *s (LNode *) malloc(sizeof(LNode));s-data e;s-next p-next;p-next s;//将结点s连到p后return true;
}7、删除结点
删除结点操作是将单链表的第i个结点删除。先检查删除位置的合法性,后查找表中第i-1个结点即被删结点的前驱结点再将其删除。 // 删除第i个结点并将其所保存的数据存入value
bool ListDelete(LinkList L, int i, int value) {if (i 1)return false;LNode *p; //指针p指向当前扫描到的结点int j 0; //当前p指向的是第几个结点p L;//循环找到第i-1个结点while (p ! NULL j i - 1) {//如果ilenghp和p的后继结点会等于NULLp p-next;j;}if (p NULL)return false;if (p-next NULL)return false;//令q暂时保存被删除的结点LNode *q p-next;value q-data;p-next q-next;free(q);return true;
}2.3.3 双链表
单链表结点中只有一个指向其后继的指针使得单链表只能从头结点依次顺序地向后遍历。要访问某个节点的前驱结点插入、删除操作时只能从头开始遍历访问后继节点的时间复杂度为O(1)访问前驱结点的时间复杂度为O(n)。 为了解决如上问题引入了双链表双链表结点中有两个指针prior和next分别指向其前驱结点和后继结点。 单链表无法逆向检索有时候不太方便 双链表可进可退存储密度更低一丢丢 双链表的类型描述如下
typedef struct DNode {int data; // 数据域struct DNode *prior, *next; // 前驱和后继指针
}DNode, *DLinkList;1、双链表的初始化
bool InitDLinkList(DLinkList L) {L (DNode *) malloc(sizeof(DNode));//DLinkList强调是个双链表DNode *强调是个结点if (L NULL) {return false;}L-prior NULL; // 头结点的前驱指针永远指向NULLL-next NULL; // 后继指针暂时为空return true;
}2、双链表的后插操作 // 将节点s插入到结点p之后
bool InsertNextDNode(DNode *p, DNode *s) {if (p NULL || s NULL) { //非法参数return false;}s-next p-next; // 将p的后继赋给s的后继// 判断p之后是否还有前驱节点if (p-next ! NULL) {p-next-prior s;}s-prior p;p-next s;return true;
}双链表的前插操作、按位序插入操作都可以转换成后插操作 3、双链表的删除操作 // 删除p结点的后继结点
bool DeleteNextDNode(DNode *p) {if (p NULL) {return false;}// 找到p的后继结点qDNode *q p-next;if (q NULL) {return false;}p-next q-next; // 将q的后继赋给p的后继if (q-next ! NULL) { // 若q的后继结点不为空q-next-prior p; // 将p赋给q的后继节点的前驱节点}free(q); // 释放qreturn true;
}// 销毁一个双链表
bool DestoryList(DLinkList L) {// 循环释放各个数据结点while (L-next ! NULL) {DeleteNextDNode(L);free(L);// 头指针置空L NULL;}
}双链表不可随机存取按位查找、按值查找操作都只能用遍历的方式实现。时间复杂度O(n). //后向遍历
while(p!NULL){//对结点p做相应处理pp-next;
}//前向遍历
while(p!NULL){//对结点p做相应处理pp-prior;
}//前向遍历(跳过头结点)
while(p-prior!NULL){//对结点p做相应处理pp-prior;
}2.3.4 循环链表
循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点整个链表形成一个环。 循环单链表
循环双链表
代码定义循环链表
//循环单链表的定义
typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;//循环双链表的定义
typedef struct DNode{ElemType data;struct DNode *prior,*next;
}DNode,*DLinkList;1、循环单链表的初始化
bool InitList(LinkList L){L(LNode *)malloc(sizeof(LNode)); //分配一个头结点if(LNULL)return false; //内存不足分配失败L-nextL; //头结点next指向头结点return true;
}
//判断循环单链表是否为空
if (L-next L){return true;
} else {return false;
}
//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L,LNode *p){if(p-nextL)return true;elsereturn false;
}单链表从一个结点出发只能找到后续的各个结点 循环单链表从一个结点出发可以找到其他任何一个结点 2、循环双链表的初始化 双链表表头结点的prior指向NULL表尾结点的next指向NULL 循环双链表表头结点的prior指向表尾结点表尾结点的next指向表头结点 //初始化空的循环双链表
bool InitDLinkList(DLinklist L){L(DNode *)malloc(sizeof(DNode));if(LNULL)return false;L-priorL;L-nextL;return true;
}
//判断循环双链表是否为空
bool Empty(DLinklist L){if(L-nextL)return true;elsereturn false;
}
//判断结点p是否为循环双链表的表尾结点
bool isTail(DLinkList L,LNode *p){if(p-nextL)return true;elsereturn false;
}2.3.5 静态链表
单链表各个结点在内存中星罗棋布、散落天涯。
静态链表用数组的方式实现的链表。分配一整片连续的内存空间各个结点集中安置每个结点包括了数据元素和下一个结点的数组下标游标。
每个数据元素4B每个游标4B每个结点共8B设起始地址为addre1e_1e1的存放地址为 addr8*2 0号结点充当”头结点“游标充当”指针“游标为-1表示已经到达表尾
**优点**增、删操作不需要大量移动元素。**缺点**不能随机存取只能从头结点开始依次往后查找容量固定不可变适用场景①不支持指针的低级语言②数据元素数量固定不变
定义1
#define MaxSize 10 //静态链表的最大长度
struct Node{ //静态链表结构类型的定义 ElemType data; //存储数据元素 int next; //下一个元素的数组下标
};
void testSLinkList(){struct Node a[MaxSize]; //数组a作为静态链表//后续代码...
}定义2
#define MaxSize 10 //静态链表的最大长度
typedef struct{ //静态链表结构类型的定义 ELemType data; //存储数据元素 int next; //下一个元素的数组下标
}SLinkList[MaxSize]; //用SLinkList定义一个长度为MaxSize的Node型数组void testSLinkList(){ SLinkList a;//后续代码...
}第一种是我们更加熟悉的写法第二种写法则更加侧重于强调 a 是一个静态链表而非数组。 静态链表实现基本操作的注意点
初始化静态链表时需要把a[0]的next设为-1并将空闲结点next设置为某个特殊值比如-2.按位序查找结点时从头结点出发按个往后遍历结点时间复杂度O(n).按位序插入结点步骤①找到一个空的结点存入数据元素②从头结点出发找到位序为i-1的结点③修改新节点的next为-1④修改i-1号结点的next为新结点的下标
2.4 顺序表vs链表
顺序表链表逻辑结构属于线性表都是线性结构属于线性表都是线性结构存储结构顺序存储优点支持随机存取存储密度高缺点大片连续空间分配不方便改变容量不方便链式存储优点离散的小空间分配方便改变容量方便缺点不可随机存取存储密度低基本操作——创建需要预分配大片连续空间。若分配空间过小则之后不方便拓展容量若分配空间过大则浪费内存资源。静态分配静态数组容量不可改变。动态分配动态数组容量可以改变但是需要移动大量元素时间代价高使用malloc()、free()。只需要分配一个头结点或者只声明一个头指针。基本操作——销毁修改 Length 0 静态分配静态数组——系统自动回收空间。 动态分配动态数组——需要手动free()。依次删除各个结点 free()。基本操作——增删插入 / 删除元素要将后续元素后移 / 前移时间复杂度O(n)时间开销主要来自于移动元素。若数据元素很大则移动的时间代价很高插入/删除元素只需要修改指针时间复杂度O(n)时间开销主要来自查找目标元素。查找元素的时间代价更低基本操作——查找按位查找O(1) 按值查找O(n)若表内元素有序可在O(log2n) 时间内找到二分法按位查找O(n)按值查找O(n)
