繁依Fanyi0

这个屌丝很懒，什么也没留下！

热门标签

2024 王道考研数据结构笔记_王道数据结构笔记

作者：繁依Fanyi0 | 2024-07-30 19:42:35

踩

王道数据结构笔记

第一章绪论

数据：信息的载体。

数据元素：是数据的基本单位。

一个数据元素由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。

数据对象：具有相同性质的数据元素的集合。

数据类型：原子类型、结构类型、抽象数据类型（ADT）。

数据结构：三要素包括逻辑结构、存储结构、数据的运算。

逻辑结构：

分为线性结构（如线性表）和非线性结构（集合、树、图）。

集合：同属一个集合，无其他关系。

线形结构：一对一。

树形结构：一对多。

图状结构或网状结构：多对多。

存储结构：

又称物理结构。主要有顺序存储、链式存储、索引存储、散列存储。

数据的运算：

运算的定义是针对逻辑结构的；运算的实现是针对存储结构的。

程序=算法+数据结构

算法的5个特性：有穷性、确定性、可行性、输入、输出。

好的算法达到的目标：正确性、可读性、健壮性、效率与低存储量需求。

算法效率的度量：时间复杂度和空间复杂度。

多项相加，只保留最高阶的项，且系数变为1.

多项相乘，都保留。

常对幂指阶：O1<Olog2n<On<Onlog2n<On2<On3<O2n<On!<O(nn)

算法原地工作：算法所需的辅助空间为常量，即O(1)。

第二章线性表

第一节线性表的定义和基本操作

线性表的基本操作

InitList(&L) 初始化表。构造一个空的线性表。

Length(L) 求表长。返回线性表L的长度，即L中数据元素的个数。

LocateElem(L,e) 按值查找。在L中查找具有给定关键字值的元素。

GetElem(L,i) 按位查找。获取表L中第i个位置的元素的值。

ListInsert(&L,i,e) 插入操作。在L中的第i个位置插入指定的元素e。

ListDelete(&L,i,&e) 删除操作。删除L中第i个位置上元素，用e返回被删除元素的值。

PrintList(L) 输出操作。顺序输出L中所有元素值。

Empty(L) 判空操作。若L为空表，返回true，否则返回false。

DestoryList(&L) 销毁操作。销毁线性表，并释放所占用的内存空间。

第二节线性表的顺序表示

一、顺序表的定义

1. 静态分配

#define MaxSize 10 //最大长度为10

typedef struct{

ElemType data[MaxSize]; //用静态的数组存放数据元素

int length; //顺序表当前的长度

}SqList;

//初始化一个顺序表

void InitList(SqList &L){

for(int i=0;i<MaxSize;i++)

L.data[i] = 0; //原因：内存含有之前遗留下来脏数据

L.length = 0;

}

2.动态分配

#define InitSize 10 //初始长度

typedef struct{

ElemType *data; //指示动态分配数组的指针，指向整片存储空间的起始地址

int MaxSize; //最大容量

int length; //当前长度

}SeqList;

//申请方法

L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize); // C语言

L.data = new ElemType[InitSize]; // C++

//初始化一个动态分配的顺序表

void InitList(SeqList &L){

L.data = (int *)malloc(sizeof(int)*InitSize); //申请一片空间

L.length = 0; //当前长度初始化为0

L.MaxSize = InitSize;

}

//增加动态数组的长度

void IncreaseSize(SeqList &L,int len){

int *p = L.data; // 使用新指针，暂存旧区域的地址

L.data = (int *)malloc((L.MaxSize+len)*sizeof(int)); // 申请新的更大的内存

for(int i=0;i<L.length;i++) // 将数据复制到新内存中

L.data[i] = p[i];

L.MaxSize = L.MaxSize+len; // 更新最大容量

free(p); // 释放原来的内存空间

}

// 本质：将结构体中的data指针进行更换。（换成一片更大的内存，再把数据复制过来）

二、顺序表的基本操作

1.插入

//在L中的第i个位置插入指定的元素e。

bool ListInsert(SqList &L,int i,ElemType e){ // i:第i个位置合法范围 1---length

if(i<1||i>L.length+1) // 插入位置非法

return false;

if（L.length>=MaxSize) // 数组已满

return false;

for(int j=L.length;j>=i;j--) // 注意：length表示长度与实际数组下标相差1

L.data[j] = L.data[j-1];

L.data[i-1] = e;

L.length++;

return true;

}

2.删除

//删除L中第i个位置上元素，用e返回被删除元素的值。

bool ListDelete(SqList &L,int i,ElemType &e){

if(i<1||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;

}

// 实际位序 1 2 3 4 5 6 7 8 length = 8

// 数组下标 0 1 2 3 4 5 6 7 8 9 10

// eg: 删除 i=2 3~8(下标2~7)左移1个

3.按位查找

GetElem(L,i) 按位查找操作。获取表L中第i个位置的元素的值。时间复杂度O(1)

ElemType GetElem(SqList L,int i){

if(i<1||i>L.length)

return -1;

return L.data[i-1];

}

// 数组指针也可以使用[]访问数组中的数据，系统会根据ElemType的类型的大小，自动计算。

// 即data是一个int型的指针，存放一片区域的首地址2000

// 则data[0]为2000 ~ 2000+4B data[1]为2000+4B ~ 2000+8B

// 因此之前用malloc申请内存空间的时候，必须用(int *)进行强制转换。

// 补充：两个结构体不能直接用==进行判断，需要对其中的分量分别尽心判断。

4.按值查找

LocateElem(L,e) 按值查找操作。在表L中查找具有给定关键字值的元素。

//在顺序表L中查找第一个元素值等于e的元素，并返回其位序。

int LocateElem(SeqList L,ElemType e){

for(int i=0;i<L.length;i++)

if(L.data[i]==e)

return i+1;

return 0;

}

三、顺序表完整操作

#include <stdio.h>

#include <stdlib.h>

// #include <iostream>

// using namespace std;

#define InitSize 10

typedef struct {

int *data;

int MaxSize;

int length;

}SeqList;

bool InitList(SeqList &L){

L.data = (int *)malloc(sizeof(int)*InitSize);

if(L.data == NULL)

return false;

for(int i=0;i<InitSize;i++)

L.data[i] = 0;

L.length = 0;

L.MaxSize = InitSize;

return true;

}

bool IncreaseSize(SeqList &L,int len){

int *p = L.data;

L.data = (int *)malloc(sizeof(int)*(L.MaxSize+len));

if(L.data == NULL)

return false;

L.MaxSize += len;

for(int i=0;i<L.length;i++)

L.data[i] = p[i];

free(p);

}

int Length(SeqList &L){

return L.length;

}

int LocateElem(SeqList L,int e){

for(int i=0;i<L.length;i++)

if(L.data[i]==e)

return i+1;

return -1;

}

int GetElem(SeqList L,int i){

if(i<1 || i>L.length)

return false;

return L.data[i-1];

}

bool ListInsert(SeqList &L,int i,int e){

if(i<1 || i>L.length+1) // i>L.length+1 --> 插入后导致线性表不连续

return false;

if(i >= L.MaxSize)

return false;

// 1 2 3 i i+1

// 0 1 2 ··· i-1 i ··· length-1 length

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(SeqList &L,int i,int &e){

if(i<1 || i>L.length)

return false;

e = L.data[i-1];

for(int j=i-1;j<=L.length-1;j++) // 写法不唯一

L.data[j] = L.data[j+1];

L.length--;

return true;

}

void DestroyList(SeqList &L){

free(L.data);

L.data = NULL;

L.length = 0;

L.MaxSize = 0;

}

void PrintList(SeqList L){

for(int i=0;i<L.length;i++)

printf("data[%d]=%d\t",i,L.data[i]);

// cout << "data[" << i << "]=" << L.data[i] << "\t";

}

int main(){

SeqList L; InitList(L); IncreaseSize(L,10);

ListInsert(L,1,11); ListInsert(L,2,22);

ListInsert(L,3,33); ListInsert(L,4,44);

int e = 666; e = LocateElem(L,33);

printf("元素33所在的位序为: %d\n",e);

e = GetElem(L,3); printf("位序为3的元素为: %d\n",e);

ListDelete(L,2,e); PrintList(L);

DestroyList(L);

return 0;

}

第三节单链表

单链表的定义和初始化

定义

struct LNode{

ElemType data; //每个结点存放一个数据元素

struct LNode *next; //指针指向下一个结点

};

struct LNode *p=(struct LNode *)malloc(sizeof(struct LNode));

// 可以使用typedef定义别名，简化名称

typedef struct LNode{

ElemType data;

struct LNode *next;

}LNode,*LinkList;

//typedef struct LNode LNode;

//typedef struct LNode *LinkList;

//两者等价，不同的地方使用合适的名字，可读性更强

LNode* L; //强调这是一个结点

LinkList L; //强调这是一个单链表

LNode* GetElem(LinkList L,int i){ //按序号查找结点值

int j=1;

LNode *p=L->next;

if(i==0)

return L;

if(i<1)

return NULL;

while(p!=NULL&&j<i){

p=p->next;

j++

}

return p;

}

初始化

（1）不带头结点单链表的初始化

bool InitList(LinkList &L){

L=NULL; //空表，没有任何结点，防止内存中的脏数据

return true;

}

判断不带头节点的单链表是否为空

bool Empty(LinkList L){

return (L==NULL);

}

（2）带头结点的单链表的初始化

bool InitList(LinkList &L){

L=(LNode *)malloc(sizeof(LNode)); // 分配一个头结点

if(L==NULL) // 内存不足，分配失败

return false;

L->next=NULL; // 头结点之后暂时还没有结点，next指针置空

return true;

}

带头结点的单链表判空

bool Empty(LinkList L){

return (L->next==NULL);

}

单链表的基本操作

1. 单链表的插入

（1）按位序插入（带头结点）

ListInsert(&L,i,e) //插入操作。在表L中的第i个位置上插入指定元素e。

//找到第i-1个结点，将新结点插入其后。

//在第i个位置插入元素e（带头结点） //头结点视为第0个位置

bool ListInsert(LinkList &L,int i,ElemType e){

if(i<1) // 位序不合法

return false;

int j = 0;

LNode *p = L;

while(p!=NULL && j<i-1){ // 找到第i-1个结点

p = p->next;

j++;

}

if(p==NULL) // 不存在第i-1个结点

return false;

LNode *s = (LNode *)malloc(sizeof(LNode));

s->data = e;

s->next = p->next;

p->next = s;

return true;

}

（2）按位序插入（不带头结点）

//在第i个位置插入元素e（不带头结点）

bool ListInsert2(LinkList &L,int i,ElemType e){

if(i<1)

return false;

else if(i==1){

L = (LNode *)malloc(sizeof(LNode));

if(L==NULL)

return false;

L->data = e;

L->next = NULL;

return true;

}else{

int j = 1;

LNode *p = L;

while(p!=NULL && j<i-1){

p=p->next;

j++;

}

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;

}

（3）指定结点的后插操作

//后插操作：在p结点之后插入元素e

bool InsertNextNode(LNode *p,ElemType 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;

}

//可以将之前的在第i个位置插入元素e（带头结点）使用InsertNextNode这个函数进行封装

bool ListInsert(LinkList &L,int i,ElemType e){

if(i<1)

retuen false;

LNode *p;

int j=0;

p=L;

while(p!=NULL&&j<i-1){

p=p->next;

j++;

}

return InsertNextNode(p,e);

}

（4）指定结点的前插操作

//前插操作：在p结点之前插入元素e

bool InsertPriorNode(LNode *p,ElemType e) //只能看到后面的，看不到前面的

传入头指针就能解决这个问题，本质上是寻找p的前驱结点，对前驱结点进行后插

bool InsertPriorNode(LinkList L,LNode *p,ElemType e)

// 传入头指针：

bool InsertPriorNode(LinkList L,LNode *p,ElemType e){

if(L==NULL || p==NULL)

return false;

LNode *r = L;

while(r->next!=p && r!=NULL)

r = r->next;

if(r==NULL)

return false;

LNode *s =(LNode*)malloc(sizeof(LNode));

s->data = e;

r->next = s;

s->next = p;

return true;

}

另外一种解决方法

// 偷天换日：在p后面插入一个新结点，把p中的数据赋给新结点，把元素e赋给p

bool InsertPriorNode(LNode *p,ElemType 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;

}

// 在p结点之前插入一个结点s

// 偷天换日：在p后面插入一个新结点s，互换两个结点的数据

bool InsertPriorNode(LNode *p,LNode *s){

if(p==NULL || s==NULL)

return false;

s->next = p->next;

p->next = s;

ElemType temp = s->data;

s->data = p->data;

p->data = temp;

return true;

}

单链表的删除

（1）按照位序删除

ListDelete(&L,i,&e) //删除操作。删除表L中第i个位置的元素，并用e返回被删除的元素值。

// 按照位序删除（带头结点）

bool ListDelete(LinkList &L,int i,ElemType &e){

if(i<1 || L==NULL)

return false;

int j = 0;

LNode *r = L;

while(r!=NULL && j<i-1){ // 找第i-1个结点

r = r->next;

j++;

}

if(r==NULL || r->next==NULL) // 第i-1个结点不存在 || 删除的恰好是表长+1的情况

return false;

LNode *temp = r->next;

e = temp->data;

r->next = temp->next;

free(temp);

return ture;

}

// 按照位序删除（不带头结点）

bool ListDelete2(LinkList &L,int i,ElemType &e){

if(i<1 || L==NULL)

return false;

else if(i==1){

e = L->data;

LNode *temp = L;

L = L->next;

free(temp);

return true;

}else{

int j = 1;

LNode *r = L;

while(r!=NULL && j<i-1){

r = r->next;

j++;

}

if(r==NULL || r->next==NULL) // 第i-1个结点不存在 || 删除的恰好是表长+1的情况

return false;

LNode *temp = r->next;

e = temp->data;

r->next = temp->next;

free(temp);

return ture;

}

（2）指定结点的删除

//删除指定结点p

bool DeleteNode(LNode *p)

同样存在没办法找到前驱结点的问题，使用同样的方法：

方法1：传入头指针，循环寻找p的前驱结点

方法2：偷天换日

// 传入头指针，找前驱结点

bool DeleteNode(LinkList L,LNode *p){

if(L==NULL || p==NULL)

return false;

LNode *r = L;

while(r!=NULL && r->next!=p)

r = r->next;

if(r==NULL)

return false;

r->next = p->next;

free(p);

return true;

}

// 偷天换日把p节点后面一个结点q的值移到p内，转换为q的删除

bool DeleteNode(LNode *p){

if(p==NULL)

return false;

LNode *r = p->next;

p->next = r->next;

p->data = r->data;

free(r);

return true;

}

//此方法存在的问题：如果p刚好是最后一个结点，p->next->data就会出错了。

单链表的查找

GetElem(L,i) 按位查找。获取表L中第i个位置元素的值。

LocateElem(L,e) 按值查找。在表L中查找具有给定关键字值的元素。

（1）GetElem(L,i) 按位查找

//按位查找，返回第i个元素（带头结点）

LNode* GetElem(LinkList L,int i){

if(i<0)

return NULL;

int j = 0;

LNode *p = L;

while(p!=NULL && j<i){

p = p->next;

j++;

}

return p;

}

// 和之前插入删除的一部分代码相同，只需把i-1改成i （删除是找前驱结点，所以是i-1）

// 边界情况：

i<0 return NULL

i=0 while(0<0) p不动 return p (p=L)

i过大 p=NULL return p (p=NULL)

第二种写法

//按位查找，返回第i个元素（带头结点）

LNode* GetElem(LinkList L,int i){

if(i<0)

return NULL;

else if(i==1)

return L;

else{

int j = 1;

LNode *p = L->next;

while(p!=NULL && j<i){

p = p->next;

j++;

}

return p;

}

之前按位插入，按位删除都可以使用这个封装好的函数

//将if(i<1) return false;后面的到if(p==NULL)前面的替换成下面这个

LNode *p=GetElem(L,i-1); //找到第i-1个结点

同样，按位插入后面的也可用封装好的InsertNextNode替换

//在第i个位置后面插入元素e

bool ListInsert(LinkList &L,int i,ElemType e){

if(i<1)

return false;

LNode *p=GetElem(L,i-1);

return InsertNextNode(p,e);

}

问题：为什么InsertNextNode要对p判空？

// bool InsertNextNode (LNode *p,ElemType e){

// if(p==NULL)

// return false;

因为在上面封装好的例子中，如果i的范围不合法，比如过大，GetElem()会返回一个NULL，此时如果传给InsertNextNode，会出错。

（2）LocateElem(L,e) 按值查找

//按值查找，找到数据域==e的结点

LNode* LocateElem(LinkList L,ElemType e){

LNode *p = L->next;

while(p!=NULL && p->data!=e)

p = p->next;

return p;

}

（3）求表的长度

计算单链表中数据结点（不含头结点）的个数，需要从第一个结点看是顺序依次访问表中的每个结点。算法的时间复杂度为O（n）。

int Length(LinkList L){

int len = 0;

LNode *p =L;

while(p->next!=NULL){

p = p->next;

len++;

}

return len;

} //注意：此处是p->next!=NULL。如果改为p!=NULL，p指向最后一个结点的首地址时，下面还会再执行一次才退出，len会多1

4.单链表的建立（尾插法、头插法）

（1）尾插法建立单链表

//如果调用按位插入，会从表头遍历，每次插入一个元素，链表长度+1，遍历的次数会越来越多O(n^2)

//可以用一个指针指向尾部，每次插入使用尾插法

// 尾插法建立单链表

LinkList List_TailInsert(LinkList &L){

L = (LNode*)malloc(sizeof(LNode));

L->next = NULL;

LNode *tail = L; // tail相当于一个游标，始终指向表尾

LNode *s;

int x;

scanf("%d",&x);

while(x!=9999){

s = (LNode*)malloc(sizeof(LNode));

s->data = x;

s->next = tail->next;

tail->next = s;

tail = s;

scanf("%d",&x);

}

tail->next = NULL;

return L;

}

（2）头插法建立单链表

//可以理解为对指定结点（头结点）的后插操作

// 头插法建立单链表

LinkList List_HeadInsert(LinkList &L){

L = (LNode*)malloc(sizeof(LNode));

L->next = NULL;

LNode *s;

int x;

scanf("%d",&x);

while(x!=9999){

s = (LNode*)malloc(sizeof(LNode));

s->data = x;

s->next = L->next;

L->next = s;

scanf("%d",&x);

}

return L;

}

头插法重要应用：可以实现链表的逆置

// 链表逆置

LinkList *Inverse(LNode *L){

LNode *r = L->next;

L->next = NULL;

LNode *temp;

while(r!=NULL){

temp = r;

r = r->next;

temp->next = L->next;

L->next = temp;

}

return L;

}

第四节双链表

在单链表中，找到一个节点的前驱节点比较困难。

双链表是在单链表的基础上再增加一个指针域prior用来指向前驱节点。

1.双链表的定义

typedef struct DNode{

ElemType data;

struct DNode *prior,*next;

}DNode,*DLinklist;

//DNode *和DLinklist是等价的，一个强调结点，一个强调是链表

2.双链表的初始化

//带头节点的双链表的初始化

bool InitDLinkList(DLinkList &L){

L = (DNode*)malloc(sizeof(DNode));

if(L==NULL)

return false;

L->prior = NULL;

L->next = NULL;

return false;

}

3.双链表判空

//判断双链表是否为空（带头结点）

L->next==NULL

4.双链表的插入

//在p结点之后插入s结点

s->next=p->next;

p->next->prior=s;

s->prior=p;

p->next=s;

存在的问题：如果p是最后一个结点，p->next->prior就会出现问题。

解决：

bool InsertNextDNode(DNode *p,DNode *s){

if(p==NULL || s==NULL)

return false;

s->next = p->next;

if(p->next!=NULL) // 如果p有后继结点，才更改p的后继结点的前向指针

p->next->prior = s;

s->prior = p;

p->next = s;

return true;

}

//这里其实是后插操作，可以由此来实现按位序插入

//按位序插入：从头节点开始，找到某个位序的前驱结点，进行后插操作

//前插操作：可以找到给定结点的前驱结点，对它执行后插操作

5.双链表的删除

//删除p的后继结点

p->next=q->next;

q->next->prior=p;

free(p);

存在问题：p的后继是否存在？p的后继的后继是否存在？

// 删除p的后继结点q p--q

bool DeleteNextDNode(DNode *p){

DNode *q = p->next;

if(p==NULL || q==NULL) // p指针为空 || p指针所指的结点没有后继

return false;

p->next = q->next;

if(q->next!=NULL) // q结点有后继结点，才修改它的后继结点的前向指针

q->next->prior = p;

free(q);

return true;

}

6.销毁双链表

//销毁双链表

void DestoryList(DLinkList &L){

while(L->next!=NULL)

DeleteNextDNode(L);

free(L);

L = NULL;

}

7.双链表的遍历

//后向遍历

while(p!=NULL){

p=p->next;

}

//前向遍历

while(p!=NULL){

p=p->prior;

}

//前向遍历,跳过头结点

while(p->prior!=NULL){

p=p->prior;

}

双链表不可以随机存取，按位查找、按值查找都只能用遍历的方式实现。时间复杂度O(n)

第五节循环链表

循环单链表

单链表：表尾结点的next指针指向NULL

循环单链表：表尾结点的next指针指回头结点

typedef struct LNode{

Elemtype data;

struct LNode *next;

}LNode,*LinkList;

//初始化一个循环单链表

bool InitList(LinkList &L){

L=(LNode *)malloc(sizeof(LNode));

if(L==NULL)

return false;

L->next=L; //头节点next指针指向头节点

return false;

}

//判断循环单链表是否为空

L->next == L

//判断结点p是否为循环单链表的表尾结点

p->next==L

单链表：从一个结点出发只能找到后续的各个结点。

循环单链表：从一个结点出发可以找到其他任何一个节点。

//删除单链表的一个结点时，如果只传入要删除的结点，删除时必然要修改其前驱节点的next指针，普通的单链表无法找到前驱。循环单链表，可以顺着一条链，找到其前驱结点。

循环单链表中，只设置尾指针效率更高，因为很多对链表的操作都是在头部或尾部。

从头节点找到尾部，时间复杂度O(n)；从尾部找到头部，时间复杂度O(1)。

循环双链表

表头结点的prior指向表尾结点，表尾结点的next指向头结点，形成了两条闭环。

//初始化空的循环双链表

bool InitDLinkList(DLinklist &L){

L=(DNode*)malloc(sizeof(DNode)); //分配一个头结点

if(L==NULL)

return false;

L->prior=L; //头结点的头指针指向自身

L->next=L; //头结点的尾指针指向自身

return false;

}

//判断循环双链表是否为空

L->next==L

//判断结点p是否为循环双链表的表尾结点

p->next==L

//在p结点之后插入s结点

bool InsertNextNode(DNode *p,DNode *s){

s->next=p->next;

p->next->prior=s;

s->prior=p;

p->next=s;

}//在普通的双链表中，如果p是最后一个结点，p->next->prior相当于NULL->prior会出现问题，而循环双链表中恰好不存在此问题

//双链表的删除 -- 删除p的后继节点q

p->next=p->next;

q->next-prior=p;

free(p);

//同样的，此段代码如果在普通双链表中要删除的是最后一个节点就会出现问题

在循环链表中，关键在于判断一个节点p是否是表尾/表头结点，它是实现前向/后向遍历的核心。

第六节静态链表

单链表：各个结点离散分布在内存中。每个结点都存放数据元素和指向下一个结点的指针。

静态链表：

分配一片连续的内存空间，结点集中安置。每个结点存放数据元素和下个结点的下标（游标）。游标充当了指针的作用，游标为-1表示已经到达表尾。

若每个数据元素4B、每个游标4B（每个结点共8B），起始地址设为addr。则数组下标为2的结点的存放首地址为addr+8*2，该结点的地址范围是addr+8*2 ~ addr+8*3。

静态链表的定义

#define MaxSize 10

struct Node{

ElemType data;

int next;

};

struct Node a[MaxSize]; //数组a作为静态链表

//相当于创建了一个数组，数组里面的元素是结构体Node这种类型

另一种写法（两者完全等价）//上面的写法看起来更像一个数组，下面的写法看起来更像链表

#define MaxSize 10

struct Node{

ElemType data;

int next;

}SLinkList[MaxSize];

SLinkList a; //相当于声明了一个大小为10的数组，数组的每一个元素是一个struct

初始化一个静态链表

a[0].next=-1; //游标为-1表示已经到达表尾

空结点的处理：

对结点中“下个结点的下标”进行标记，例如next设为-2或其他值。

查找

从头结点出发挨个往后遍历节点，找到某个位序的结点时间复杂度为O(n)

//数组下标反映的是物理上的顺序，游标反应的是逻辑顺序

插入位序为i的节点

1）先找到一个空的节点，存入数据。 //初始化时可将空结点标记一下，例如把next设为-2

2）从头结点出发找到位序为i-1的结点。

3）修改新节点的next。

4）修改i-1结点的next。

删除某个结点

1）从头结点出发找到要删除结点的前驱结点。

2）修改前驱节点的游标，将其改为当前要删除结点的“下个结点的下标”(next)。

3）将要删除结点的next设为-2。

静态链表的优缺点：

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

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

第七节顺序表和链表的比较

（1）逻辑结构：都属于线性表，都是线性结构。

（2）存储结构：

顺序表：

顺序存储，各个元素大小相等，只需要知道起始地址，就能找到第i个元素，支持随机存取。

只需要存储数据本身，存储密度高。但是，大片连续空间分配不方便，改变容量不方便。

链表：

结点离散存放，空间分配方便，改变容量方便。

不可随机存取。存储密度低。

（3）基本操作：

创销增删改查销毁考察不多，改就是在查的基础上赋值

1）创：

顺序表：

预分配大片空间。分配过小，之后不方便扩展。分配过大，浪费内存资源。

静态分配：静态数组，容量不可改变。

动态分配：动态数组（malloc，free）容量可改变，但是移动大量元素，时间代价高。

链表：

只需分配头结点（也可只声明一个头指针，不要头结点），之后方便拓展

2）销：

顺序表：

修改length=0

静态分配：静态数组，系统自动回收

动态分配：动态数组（malloc、free）手动free malloc申请的内存在堆区，系统不会自动回收，malloc和free应该成对出现

链表：

依次删除各个结点（free）

3）增、删：

顺序表：

相邻有序，插入/删除元素要将后续元素都后移/前移。时间复杂度O(n)，主要源于移动元素

链表：

插入/删除只需要修改指针。时间复杂度O(n)，主要来源于查找目标元素

//虽然都是O(n)，但若数据元素很大，移动的时间代价会很高，相较而言，查找元素的时间代价更低

4）查：

顺序表：

按位查找O(1)

按值查找O(n) 若元素有序，可利用一些算法，如折半算法，可达到O(log_2 n)。

链表：

按位查找O(n) 按值查找O(n)

若表长难以估计，经常要增加、删除元素。 --->链表

若表长可预估，查询（搜索）操作较大。 --->顺序表

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/905142

2024 王道考研 数据结构 笔记_王道数据结构笔记

第一章 绪论

第二章 线性表

第一节 线性表的定义和基本操作

线性表的基本操作

第二节 线性表的顺序表示

一、顺序表的定义

1. 静态分配

2.动态分配

二、顺序表的基本操作

1.插入

2.删除

3.按位查找

4.按值查找

三、顺序表完整操作

第三节 单链表

（1）不带头结点单链表的初始化

（2）带头结点的单链表的初始化

1. 单链表的插入

（1）按位序插入（带头结点）

（2）按位序插入（不带头结点）

（3）指定结点的后插操作

（4）指定结点的前插操作

（1）按照位序删除

（2）指定结点的删除

（1）GetElem(L,i) 按位查找

（2）LocateElem(L,e) 按值查找

（3）求表的长度

4.单链表的建立（尾插法、头插法）

（1）尾插法建立单链表

（2）头插法建立单链表

第四节 双链表

1.双链表的定义

2.双链表的初始化

3.双链表判空

4.双链表的插入

5.双链表的删除

6.销毁双链表

7.双链表的遍历

第五节 循环链表

第六节 静态链表

第七节 顺序表和链表的比较

2024 王道考研数据结构笔记_王道数据结构笔记

第一章绪论

第二章线性表

第一节线性表的定义和基本操作

第二节线性表的顺序表示

第三节单链表

第四节双链表

第五节循环链表

第六节静态链表

第七节顺序表和链表的比较