【数据结构】24王道考研笔记——线性表

线性表

定义和基本操作

线性表的定义：线性表时具有相同数据类型的n（n>=0）个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。

L=(a1,a2,a3…,an) a1为表头元素，an为表尾元素，除第一个元素外，每个元素有且仅有一个直接前驱，除最后一个元素，每个元素有且仅有一个直接后继。

特点：

1. 元素个数有限
2. 元素具有逻辑上的顺序性，表中元素有其先后次序
3. 元素都是数据元素，每个元素都是单个元素
4. 元素数据类型相同，占有相同大小的存储空间
5. 元素具有抽象性

线性表是一种逻辑结构，表示元素之间一对一的相邻关系，顺序表和链表是指存储结构。

线性表基本操作：

总结：

顺序表

线性表的顺序存储称为顺序表，使用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。i为ai在线性表中的位序，元素的逻辑顺序与其物理顺序相同。

线性表的顺序存储结构是一种随机存储的存储结构。

顺序表的特点：

1. 随机访问，可以在O（1）时间内找到第i个元素 data[i-1]
2. 存储密度高，每个结点智存初数据元素
3. 拓展容量不方便（即使采用动态分配，拓展长度时间复杂度仍较高）
4. 插入、删除操作不方便，需要移动大量元素

静态顺序表

一维数组可以静态分配也可以动态分配，静态分配时，数组大小和空间事先固定，不可变。而动态顺序表则不需要为线性表一次性划分所有空间。

结构体：

#define MaxSize 50typedef struct {int data[MaxSize];int length;
} SqList;

初始化：

//初始化
void InitList(SqList& L) {for (int i = 0; i < MaxSize; i++) {L.data[i] = 0;//将所有元素的初始值默认设置为0//这一步其实可以省略，但是省略之后，有可能受到内存中"脏数据"的影响}L.length = 0;
}

判空：

//判断是否为空
bool Empty(SqList L) {return (L.length == 0);
}

插入：

//插入
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--) {L.data[j] = L.data[j - 1];}L.data[i - 1] = e;L.length++;return true;
}

删除：

//删除
bool ListDelete(SqList& L, int i, int& e) {//判断i的位置是否合法if (i < 0 || i > L.length) {return false;}//取出将要被删除的数e = L.data[i - 1];//将其后的数据前移for (int j = i; j <= L.length; j++) {L.data[j - 1] = L.data[j];}//线性表长度减一L.length--;return true;
}

查找：

//查找
//按位查找
int GetElem(SqList L, int i) {//判断是否越界if (i < 0 || i > L.length)return -1;return L.data[i - 1];
}
//按值查找
int LocateElem(SqList L, int e) {//循环出查找for (int i = 0; i < L.length; i++) {if (L.data[i] == e)return i + 1; //返回位序}return -1;
}

改值：

//先查找后改值
//由此分为两种方式，先按位查找后改值；或先按值查找后改值
//先按值查找后改值
bool LocateChangeElem(SqList& L, int e, int em) {//按值查找得到位序int bitOrder = LocateElem(L, e);//改值if (bitOrder != -1) {L.data[bitOrder] = em;return true;}else {return false;}
}//先按位序查找后改值
bool getChangeElem(SqList& L, int i, int em) {//给的位序,首先判断i是否合法if (i < 0 || i >= L.length)return false;//由于是用数组实现的方式，可以直接利用i查找L.data[i] = em;return true;}

打印：

//打印整个顺序表
void PrintSqList(SqList L) {//循环打印printf("开始打印顺序表\n");for (int i = 0; i < L.length; i++) {printf("Data[%d]==%d\n", i, L.data[i]);}printf("打印结束！\n");
}

动态顺序表

一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储空间的目的。

结构体：

#define InitSize 100
typedef struct {int* data; //指示动态分配数组的指针int MaxSize;//顺序表的最大容量int length;//顺序表当前的长度
} SeqList;

初始化：

//初始化
bool InitList(SeqList& L) {//用 malloc 函数申请一片连续的存储空间L.data = (int*)malloc(InitSize * sizeof(int));if (L.data == NULL)return false;//(int *) 是指针的强制类型转换L.length = 0;L.MaxSize = InitSize;return true;
}

判空：

//判空
bool Empty(SeqList L) {return (L.length == 0);
}

判满：

//判满
bool Full(SeqList L) {return (L.length >= L.MaxSize);
}

扩展空间：

//扩展空间
void IncreaseSize(SeqList& L, int len) {int* p = L.data;L.data = (int*)malloc((InitSize + len) * sizeof(int));for (int i = 0; i < L.length; i++) {L.data[i] = p[i];}L.MaxSize = L.MaxSize + len;free(p);//malloc 函数用于申请内存空间；free 函数用于释放内存空间；
}

插入：

//插入
bool ListInsert(SeqList& L, int i, int e) {//判断插入的位置是否合法，if (i < 1 || i > L.length + 1)return false;//判断表是否存满了
//    if (L.length>=L.MaxSize)
//        return fals;if (Full(L))return false;//后面的元素后移for (int j = L.length; j >= i; j--) {L.data[j] = L.data[j - 1];}L.data[i - 1] = e;L.length++;return true;
}

按位查找：

//按位查找
int GetElem(SeqList L, int i) {//判断是否越界if (i < 0 || i > L.length)return -1;return L.data[i - 1];
}

按值查找：

//按值查找
int LocateElem(SeqList L, int e) {//循环出查找for (int i = 0; i < L.length; i++) {if (L.data[i] == e)return i + 1; //返回位序}return -1;
}

删除：

//删除
bool ListDelete(SeqList& L, int i, int& e) {//判断i的位置是否合法if (i < 0 || i > L.length) {return false;}//取出将要被删除的数e = L.data[i - 1];//将其后的数据前移for (int j = i; j <= L.length; j++) {L.data[j - 1] = L.data[j];}//线性表长度减一L.length--;return true;
}

销毁：

//销毁
//由于动态分配方式使用malloc申请的内存空间，故需要使用free函数手动释放空间！
void DestroySqList(SeqList& L) {free(L.data);L.data = NULL;L.length = 0;
}

打印：

//打印整个顺序表
void PrintSqList(SeqList L) {if (L.data == NULL || L.length == 0)printf("这是一个空表！");else {//循环打印printf("开始打印顺序表\n");for (int i = 0; i < L.length; i++) {printf("Data[%d]==%d\n", i, L.data[i]);}printf("打印结束！\n");}
}

总结：

链表

单链表

线性表的链式存储称为单链表，它指通过一组任意的存储单元来存储线性表中的数据元素。每个链表结点存放元素自身的信息外，还需要存放一个指向其后继的指针。

结构体：

//结构体
typedef struct LNode {int data;struct LNode* next;
} LNode, * LinkList;
//等价于
//struct LNode{
//    int data;
//    struct LNode *next;
//};
//
//typedef struct LNode LNode;
//typedef struct LNode *LinkList;

LinkList强调为单链表 LNode*强调为结点，两者等价

不带头结点：

初始化：

//初始化
bool InitList(LinkList& L) {L = NULL;//空表暂时没有任何数据return true;
}

判空：

//判断是否为空
bool Empty(LinkList L) {return (L == NULL);
}
//等价于
//bool Empty1(LinkList L){
//    if (L==NULL)
//        return true;
//    else
//        return false;
//}

插入：

//在指定位置插入元素
bool ListInsert(LinkList& L, int i, int e) {if (i < 1)return false;//判断位序i是否合法//不带头节点时，插入位置正好为表头时，得单独处理if (i = 1) {LNode* s = (LNode*)malloc(sizeof(LNode));s->data = e;s->next = L;L = s;return true;}LNode* p;//指针指向当前扫面到的节点int j = 0;//记录p指向的节点的位序p = L;//L指向头节点，从头开始while (p != NULL && j < i - 1) {//循环扫描p = p->next;j++;}if (p == NULL) //i值超过来表长，不合法return false;LNode* s = (LNode*)malloc(sizeof(LNode));s->data = e;//下面的顺序不可交换s->next = p->next;p->next = s;return true;
}

带头结点：

初始化：

//初试化(带有头节点)
bool InitList(LinkList& L) {L = (LNode*)malloc(sizeof(LNode));//分配一个头节点if (L == NULL)return false;//头节点分配失败，可能是内存不足L->next = NULL;//头节点之后暂时没有节点，头节点也不存放数据return true;
}

判空：

//判空
bool Empty(LinkList L) {return (L->next == NULL);
}

打印链表：

void PrintList(LinkList L) {//循环打印整个链表LNode* p = L->next;//扫描指针int j = 0;if (p == NULL)printf("这是一个空表\n");while (p != NULL) {printf("LinkList[%d]=%d\n", j, p->data);p = p->next;j++;}
}

按位插入：

//按位插入
bool ListInsert(LinkList& L, int i, int e) {if (i < 1)return false;//判断位序i是否合法LNode* p;//指针指向当前扫面到的节点int j = 0;//记录p指向的节点的位序p = L;//L指向头节点，从头开始while (p != NULL && j < i - 1) {//循环扫描p = p->next;j++;}if (p == NULL) //i值超过来表长，不合法return false;LNode* s = (LNode*)malloc(sizeof(LNode));s->data = e;//下面的顺序不可交换s->next = p->next;p->next = s; //将结点s连到p之后return true;
}

后插操作：（包含于之前的插入操作之中）

//指定节点的后插操作
bool InsertNextNode(LNode* p, int e) {if (p == NULL)return false;//判断指定节点是否存在LNode* s = (LNode*)malloc(sizeof(LNode));if (s == NULL)return false;//分配内存失败s->data = e;s->next = p->next;p->next = s;return true;
}

前插操作：由于难以获得前一个链表元素信息，所以先完成后插，再交换两者数据实现前插

//指定节点的前插操作
//先完成后插，再交换数据以实现前插
bool InsertPriorNode(LNode* p, int e) {if (p == NULL)return false;LNode* s = (LNode*)malloc(sizeof(LNode));if (s == NULL)return false;s->next = p->next;p->next = s;s->data = p->data;p->data = e;return true;
}

按指定位序删除并返回值：

//按指定位序删除节点并返回其值
bool ListDelete(LinkList& L, int i, int& e) {if (i < 1)return false;LNode* p;int j = 0;p = L;while (p != NULL && j < i - 1) {p = p->next;j++;}LNode* q = p->next;e = q->data;p->next = q->next;free(q);return true;
}

删除指定节点：若p为最后一个元素，则存在问题，只能通过从头结点开始顺序找到其前序节点的方法来进行删除。

//删除指定节点
bool DeleteNode(LNode* p) {if (p == NULL){return false;}LNode* q = p->next;//令q指向*p的后续结点p->data = p->next->data;//和后续结点交换数据域p->next = q->next;//将*q结点从链中“断开”free(q);//释放后续结点的存储空间return true;
}

按值查找：

//按值查找
LNode* LocateElem(LinkList L, int e)
{LNode* p = L->next;//从第1个结点开始查找数据域为e的结点while (p != NULL && p->data != e){p = p->next;}return p;//找到后返回该结点指针，否则返回NULL；
}

按位查找：

//按位查找
LNode* GetElem(LinkList L, int i)
{if (i < 0){return NULL;}LNode* p;//指针p指向当前扫描到的结点int j = 0;//当前p指向的是第几个结点p = L;//L指向头结点，头结点是第0个结点（不存数据）while (p != NULL && j < i){p = p->next;j++;}return p;
}

求表长：

//求表长
int Lnegth(LinkList L)
{int len = 0;//统计表长LNode* p = L;while (p->next != NULL){p = p->next;len++;}return len;
}

尾插法建表：设置一个表尾指针，方便直接在队尾进行尾插操作

//尾插法建立单链表（正向建立单链表）
LinkList List_TailInsert(LinkList& L)
{int x;L = (LinkList)malloc(sizeof(LNode));//建立头结点LNode* s, * r = L;//r为表尾指针，方便尾插scanf("%d", &x);//输入结点的值while (x != 9999)//输入9999表示结束{s = (LNode*)malloc(sizeof(LNode));s->data = x;r->next = s;r = s;//r指向新的表尾结点，永远保持r指向最后一个结点，避免重复操作scanf("%d", &x);}r->next = NULL;return L;
}

头插法建立单链表(不断对头结点进行尾插操作）

//头插法建立单链表(不断对头结点进行尾插操作）
LinkList List_HeadInsert(LinkList& L)//逆向建立单链表
{LNode* s;int x;L = (LinkList)malloc(sizeof(LNode));//创建头结点L->next = NULL;//初始为空链表scanf("%d", &x);//输入结点的值while (x != 9999)//输入9999表示结束{s = (LNode*)malloc(sizeof(LNode));//创建新结点s->data = x;s->next = L->next;L->next = s;//将新结点插入表中，L为头指针scanf("%d", &x);}return L;
}

双链表

在单链表的基础上加入prior前驱指针，使得插入、删除操作的时间复杂度变为O（1）（可以很方便地找到前驱）

结构体：

typedef struct DNode {int data;//数据域struct DNode* prior, * next;//前指针和后指针
} DNode, * DLinkList;

初始化：

//初始化
bool InitDLinkList(DLinkList& L) {L = (DNode*)malloc(sizeof(DNode));//分配一个头节点if (L == NULL)return false;L->prior == NULL;//头节点前后指针都指向空L->next == NULL;return true;
}

判空：

//判空
bool Empty(DLinkList L) {return (L->next == NULL);
}

后插：

//指定节点的后插操作
bool InsertNextElem(DNode* p, DNode* s) {s->next = p->next;if (p->next != NULL){p->next->prior = s;//防止出现p后面没有后继结点的情况}s->prior = p;p->next = s;
}

删除p后继结点：

//删除P节点的后继节点
bool DeleteNextNode(DNode* p) {if (p == NULL)return false;//p节点为空DNode* q = p->next;if (q == NULL)return false;//P节点没有后继p->next = q->next;if (q->next != NULL)//q不是最后一个节点q->next->prior = p;free(q);//手动释放内存空间return true;
}

销毁整个表：

//销毁整个表
bool DestroyList(DLinkList& L) {//循环删除并释放每个节点while (L->next != NULL)DeleteNextNode(L);free(L);//释放头节点L = NULL;//头指针指向NULL
}

循环链表

循环链表的最后一个指针不是NULL而是改为指向头结点。

循环单链表：

结构体：

typedef struct LNode {int data;struct LNode* next;
}LNode, * LinkList;

初始化：

//初始化一个循环单链表
bool InitRLinkList(LinkList& L) {L = (LNode*)malloc(sizeof(LNode));//分配一个头节点if (L == NULL)return false;//内存不足，分配失败；L->next = L;//头节点nex指向头节点，以此形成循环链表return true;
}

判空：

bool Empty(LinkList L)
{if (L->next == L)return true;elsereturn false;
}

判尾：

//判断P是不是表尾指针
bool IsTail(LinkList L, LNode* p) {return (p->next == L);
}

循环双链表：

结构体：

typedef struct DNode {int data;struct DNode* prior, * next;
}DNode, * DLinkList;

初始化：

//初始化
bool InitRDLinkList(DLinkList& L) {L = (DNode*)malloc(sizeof(DNode));//分配头节点if (L == NULL)return false;L->prior = L;L->next = L;//循环抱住自己return true;
}

判尾：

//判断节点p是不是循环双链表的表尾节点
bool iTail(DLinkList L, DNode* p) {return (p->next == L);
}

插入：

//在p节点之后插入s节点
bool InsertNextDNode(DNode* p, DNode* s) {s->next = p->next;p->next->prior = s;s->prior = p;p->next = s;return true;
}

删除：

//删除操作
bool DeleteNextDNode(DLinkList& L, DNode* p) {DNode* q = p->next;p->next = q->next;q->next->prior = p;free(q);return true;
}

静态链表

静态链表借助数组来描述线性表的线性存储结构，这里的指针next记录的是结点的相对地址（数组下标），又称游标，和顺序表一样，静态链表也要预先分配一块连续的内存空间。

静态链表以next==-1作为结束标志，插入、删除操作与动态链表的相同，只需要修改指针，而不需要移动元素。

结构体：

//第一种定义方法
struct Node0 {int data;//存储数据元素int next;//下一个元素的数组下标
};
typedef struct Node SLinkList[MaxSize];//第二种定义方法
typedef struct Node {int data;int next;
}SLinkList[MaxSize];

优点：增删操作不需要大量移动元素

缺点：不能随机存取，只能从头结点开始一次往后查找：容量固定不可变

顺序表链表比较

逻辑结构：

都属于线性表，都是线性结构。

采用顺序存储时，逻辑上相邻的元素，物理存储位置也相邻，采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，逻辑关系通过指针链接表示。

存储结构：

基本操作：

总结：

主要参考：王道考研课程
后续会持续更新考研408部分的学习笔记，欢迎关注。
github仓库（含所有相关源码）：408数据结构笔记