• 数据结构 第2章：线性表

    文章目录

    2.1 线性表的定义和操作

    2.1.1 线性表的基本概念

    1. 线性表：是具有相同数据类型的 n 个数据元素的有限序列。

    2. 特点：

    存在惟一的第一个元素。
    存在惟一的最后一个元素。
    除第一个元素之外，每个元素均只有一个直接前驱。
    除最后一个元素之外，每个元素均只有一个直接后继。

    1. 线性表的存储结构：
      顺序存储结构：顺序表
      链式存储结构：链表

    2.1.2 线性表的基本操作

    1. InitList(&L)：初始化表。构造一个空的线性表 L，并分配内存空间。

    2. DestroyList(&L)：销毁表。并释放线性表 L 占用的内存空间。

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

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

    5. LocateElem(L, e)：按值查找。在表 L 中查找具有给定元素值的元素。

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

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

    8. PrintList(L)：打印表。按顺序输出线性表 L 的所有元素值。

    9. Empty(L)：判断是否为空。若 线性表L 为空表，则返回 true，否则返回 false。

    操作数据结构的思路：创销、增删改查

    2.2. 顺序表

    2.2.1. 顺序表的基本概念

    1. 顺序表：用顺序存储的方式实现线性表。顺序存储，将逻辑上相邻的元素存储在相邻的物理位置上。
    2. 特点：
    1. 随机访问，即可以在 O ( 1 )时间内找到第 i 个元素。
    2. 存储密度高，每个节点只存储数据元素。
    3. 拓展容量不方便（即使使用动态分配的方式实现，拓展长度的时间复杂度也比较高，因为需要把数据复制到新的区域）。
    4. 插入删除操作不方便，需移动大量元素：O ( n )

    2.2.2. 顺序表的实现

    静态实现：

    #define MaxSize 10 // 定义最大长度 

typedef struct {
	int data[MaxSize]; // 使用静态的数组存放数据元素 
	int length; // 顺序表的当前长度 
}SqList;

// 初始化顺序表 
void InitList(SqList &L) {
	L.length = 0; // 顺序表初始长度为0 
}

int main() {
	SqList L; // 声明一个顺序表 
	InitList(L); // 初始化顺序表 
	return 0;
}

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

    动态实现：

    #define InitSize 10 // 顺序表的初始长度

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

// 初始化顺序表 
void InitList(SqList &L) {
	// 用malloc函数申请一片连续的存储空间 
	L.data = (int *)malloc(InitSize * sizeof(int));
	L.length = 0;
	L.MaxSize = InitSize;
}

// 增加动态数组的长度 
void IncreaseSize(SqList &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; // 顺序表最大长度增加len 
	free(p); // 释放原来的内存空间 
}

int main() {
	SeqList L; // 声明一个顺序表 
	InitList(L); // 初始化顺序表 
    ...
	IncreaseSize(L, 5);
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    malloc() 函数的作用：会申请一片存储空间，并返回存储空间第一个位置的地址，也就是该位置的指针。

    2.2.3. 顺序表的基本操作

    1. 插入：
    #define MaxSize 10 // 定义最大长度 

typedef struct {
	int data[MaxSize]; // 用静态的数组存放数据元素 
	int length; // 顺序表的当前长度 
}SqList;

// 在顺序表i位置插入e
bool ListInsert(SqList &L, int i, int e) {
	if (i < 1 || i > L.length+1) // 判断i的范围是否有效 
		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处放入e 
	L.length++; // 长度+1 
	return true;
} 

int main() {
	SqList L;
	InitList(L);
	ListInsert(L, 3, 3);
	return 0; 
} 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    时间复杂度：

    1. 最好时间复杂度：O ( 1 )
    2. 最坏时间复杂度：O ( n )
    3. 平均时间复杂度：O ( n )
    1. 删除：
    #define MaxSize 10

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

// 删除顺序表i位置的数据并存入e
bool ListDelete(SqList &L, int i, int &e) {
	if (i < 1 || i > L.length) // 判断i的范围是否有效
		return false;
	e = L.data[i-1]; // 将被删除的元素赋值给e 
	for (int j = i; j < L.length; j++) //将第i个位置后的元素前移 
		L.data[j-1] = L.data[j];
	L.length--;
	return true; 
}

int main() {
	SqList L;
	InitList(L);
	int e = -1;
	if (ListDelete(L, 3, e))
		printf("已删除第3个元素，删除元素值为%d\n", e);
	else
		printf("位序i不合法，删除失败\n"); 
	return 0; 
} 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    时间复杂度：

    1. 最好时间复杂度：O ( 1 )
    2. 最坏时间复杂度：O ( n )
    3. 平均时间复杂度：O ( n )
    1. 按位查找：
    // 静态分配的按位查找
#define MaxSize 10

typedef struct {
	ElemType data[MaxSize]; 
	int length;
}SqList;

ElemType GetElem(SqList L, int i) {
	return L.data[i-1];
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    // 动态分配的按位查找
#define InitSize 10

typedef struct {
	ElemType *data;
	int MaxSize;
	int length;
}SeqList;

ElemType GetElem(SeqList L, int i) {
	return L.data[i-1];
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    时间复杂度： O ( 1 )

    1. 按值查找：
    #define InitSize 10

typedef struct {
	ElemType *data; 
	int MaxSize;
	int length; 
}SqList;

// 查找第一个元素值为e的元素，并返回其位序 
int LocateElem(SqList L, ElemType e) {
	for (int i = 0; i < L.length; i++)
		if (L.data[i] == e)
			return i+1; // 数组下标为i的元素值等于e，返回其位序i+1 
	return 0; // 没有查找到 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    在《数据结构》考研初试中，手写代码可以直接用“==”，无论 ElemType 是基本数据类型还是结构类型
    时间复杂度：

    1. 最好时间复杂度：O ( 1 ) O(1)O(1)
    2. 最坏时间复杂度：O ( n ) O(n)O(n)
    3. 平均时间复杂度：O ( n ) O(n)O(n)

    2.3 链表

    2.3.1 单链表的基本概念

    在这里插入图片描述

    1. 单链表：用链式存储实现了线性结构。一个结点存储一个数据元素，各结点间的前后关系用一个指针表示。
    2. 特点：
      优点：不要求大片连续空间，改变容量方便。
      缺点：不可随机存取，要耗费一定空间存放指针。
    3. 两种实现方式：
      带头结点，写代码更方便。头结点不存储数据，头结点指向的下一个结点才存放实际数据。
      不带头结点，麻烦。对第一个数据结点与后续数据结点的处理需要用不同的代码逻辑，对空表和非空表的处理需要用不同的代码逻辑。

    2.3.2 单链表的实现

    不带头结点的单链表：

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

//初始化一个空的单链表
bool InitList(LinkList &L){
    L = NULL; //空表，暂时还没有任何结点
    return true;
}

void test(){
    LinkList L;  //声明一个指向单链表的头指针
    //初始化一个空表
    InitList(L);
    ...
}

//判断单链表是否为空
bool Empty(LinkList L){
    return (L==NULL)
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    带头结点的单链表：

    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 = NULL;       //头结点之后暂时还没有结点   
    return true;
}

void test(){     
    LinkList L;  //声明一个指向单链表的头指针 
    //初始化一个空表    
    InitList(L);     
    ...
}
//判断单链表是否为空
bool Empty(LinkList L){  
    if (L->next == NULL) 
        return true;     
    else             
        return false;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    2.3.3 单链表的插入

    1. 按位序插入（带头结点）：
    typedef struct LNode{     
    ElemType data;  
    struct LNode *next;
}LNode, *LinkList;

//在第i个位置插入元素e
bool ListInsert(LinkList &L, int i, ElemType e){       
    if(i<1)         
        return False;   
    LNode *p;           //指针p指向当前扫描到的结点    
    int j=0;            //当前p指向的是第几个结点   
    p = L;              //循环找到第i-1个结点    
    while(p!=NULL && j<i-1){       //如果i>lengh，p最后会等于NULL 
        p = 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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    时间复杂度：

    1. 最好时间复杂度：O ( 1 )
    2. 最坏时间复杂度：O ( n )
    3. 平均时间复杂度：O ( n )
    1. 按位序插入（不带头结点）：
    typedef struct LNode{     
    ElemType data;      
    struct LNode *next;
}LNode, *LinkList;

//在第i个位置插入元素e
bool ListInsert(LinkList &L, int i, ElemType e){   
    //判断i的合法性     
    if(i<1)      
        return false; 
    //需要判断插入的位置是否是第1个     
    if(i==1){              
        LNode *s = (LNode *)malloc(size of(LNode));  
        s->data =e;          
        s->next =L;       
        L=s;          //头指针指向新结点   
        return true;      
    }       
    //i>1的情况与带头结点一样，唯一区别是j的初始值为1   
    LNode *p;       //指针p指向当前扫描到的结点     
    int j=1;        //当前p指向的是第几个结点   
    p = L;          
    //循环找到第i-1个结点    
    while(p!=NULL && j<i-1){     //如果i>lengh，p最后会等于NULL    
        p = 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;        
    return true;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    时间复杂度：

    1. 最好时间复杂度：O ( 1 )
    2. 最坏时间复杂度：O ( n )
    3. 平均时间复杂度：O ( n )

    除非特别声明，否则之后的代码都默认为带头结点！
    3. 指定结点的后插操作：

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

// 在结点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;
}

// 按位序插入的函数中可以直接调用后插操作
bool ListInsert(LinkList &L, int i, ElemType e){  
    if(i<1)            
        return False;
    LNode *p;     
    //指针p指向当前扫描到的结点 
    int j=0;        
    //当前p指向的是第几个结点 
    p = L;       
    //循环找到第i-1个结点   
    while(p!=NULL && j<i-1){ 
        //如果i>lengh, p最后会等于NULL   
        p = p->next;        
        j++;       
    }       
    return InsertNextNode(p, e)
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    时间复杂度：O ( 1 )

    1. 指定结点的前插操作：

    如果传入头指针，就可以循环整个链表找到指定结点p的前驱结点q，再对q进行后插操作；
    如果不传入头指针，可以在指定结点p后插入一个结点s，并交换两个结点所保存的数据，从而变相实现指定结点的前插操作。

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

// 在结点p前插入元素e
bool InsertPriorNode(LNode *p, ElemType e){  
    if(p==NULL)      
        return false;  
    LNode *s = (LNode *)malloc(sizeof(LNode));  
    // 内存不足分配失败       
    if(s==NULL)       
        return false;    
    // 将s插入结点p之后    
    s->next = p->next;   
    p->next = s;       
    // 交换两个结点中的数据  
    s->data = p->data;   
    p->data = e;       
    return true;
}

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

    时间复杂度：O ( 1 )

    2.3.4. 单链表的删除

    1. 按位序删除：
    typedef struct LNode{       
    ElemType data;    
    struct LNode *next;}LNode, *LinkList;

// 删除第i个结点并将其所保存的数据存入e
bool ListDelete(LinkList &L, int i, ElemType &e){      
    if(i<1)             
        return false;     
    LNode *p;       //指针p指向当前扫描到的结点     
    int j=0;        //当前p指向的是第几个结点    
    p = L;         
    //循环找到第i-1个结点     
    while(p!=NULL && j<i-1){   
        //如果i>lengh，p和p的后继结点会等于NULL        
        p = p->next;            
        j++;      
    }       
    if(p==NULL)       
        return false;    
    if(p->next == NULL)        
        return false;    	   
    //令q暂时保存被删除的结点   
    LNode *q = p->next;    
    e = q->data;     
    p->next = q->next;      
    free(q)     
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    时间复杂度：
    最好时间复杂度：O ( 1 )
    最坏时间复杂度：O ( n )
    平均时间复杂度：O ( n )

    1. 删除指定结点：
    1. 如果传入头指针，就可以循环整个链表找到指定结点p的前驱结点q，再对p进行删除操作；
    2. 如果不传入头指针，可以把指定结点p的后继结点q删除，并使结点p保存结点q存储的数据，从而变相实现删除指定结点的操作。但是如果指定结点p没有后继结点，这么做会报错。
    // 删除指定结点p
bool DeleteNode(LNode *p){   
    if(p==NULL)           
        return false;     
    LNode *q = p->next; // 令q指向p的后继结点  
    // 如果p是最后一个结点，则q指向NULL，继续执行就会报错  
    p->data = q->data;  
    p->next = q->next;   
    free(q);    
    return true;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    时间复杂度：O ( 1 )

    2.3.5. 单链表的查找

    1. 按位查找：
    typedef struct LNode{  
    ElemType data;    
    struct LNode *next;
}LNode, *LinkList;

// 查找指定位序i的结点并返回
LNode * GetElem(LinkList L, int i){   
    if(i<0)            
        return NULL;   
    LNode *p;     
    int j=0;     
    p = L;      
    while(p!=NULL && j<i){   
        p = p->next;     
        j++;      
    }        
    return p;
}

// 封装后的插入操作，在第i个位置插入元素e，可以调用查询操作和后插操作
bool ListInsert(LinkList &L, int i, ElemType e){  
    if(i<1)             
        return False;  
    // 找到第i-1个元素     
    LNode *p = GetElem(L, i-1);   
    // 在p结点后插入元素e     
    return InsertNextNode(p, e)
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    时间复杂度：
    最好时间复杂度：O ( 1 )
    最坏时间复杂度：O ( n )
    平均时间复杂度：O ( n )

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


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    时间复杂度：
    最好时间复杂度：O ( 1 )
    最坏时间复杂度：O ( n )
    平均时间复杂度：O ( n )

    1. 计算单链表长度：
    // 计算单链表的长度
int Length(LinkList L){      
    int len=0;       //统计表长  
    LNode *p = L;
    while(p->next != NULL){ 
        p = p->next;      
        len++;       
    }      
    return len;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    时间复杂度：O ( n )

    2.3.6. 单链表的建立

    1. 尾插法建立单链表：
    // 使用尾插法建立单链表L
LinkList List_TailInsert(LinkList &L){   
    int x;			//设ElemType为整型int  
    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指针指向新的表尾结点     
        scanf("%d", &x);       
    }    
    r->next = NULL;                          //尾结点指针置空      
    return L;
}


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

    时间复杂度：O（n）

    1. 头插法建立单链表：
    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;
}


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

    头插法实现链表的逆置：

    // 将链表L中的数据逆置并返回
LNode *Inverse(LNode *L){	
    LNode *p, *q;	  
    p = L->next;     //p指针指向第一个结点	  
    L->next = NULL;  //头结点置空       
    // 依次判断p结点中的数据并采用头插法插到L链表中	
    while (p != NULL){		   
        q = p;		  
        p = p->next;	
        q->next = L->next;  
        L->next = q;	
    }	   
    return L;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    2.3.7. 双链表

    在这里插入图片描述

    1. 双链表的定义：双链表也是链表的一种。双链表的每个数据节点中都有两个指针，分别指向前驱节点和后继结点。
    2. 双链表的实现：
    typedef struct DNode{            //定义双链表结点类型 
    ElemType data;               //数据域    
    struct DNode *prior, *next;  //前驱和后继指针
}DNode, *DLinklist;

    • 1
    • 2
    • 3
    • 4
    1. 双链表的初始化 (带头结点)：
    typedef struct DNode{   
    ElemType data;     
    struct DNode *prior, *next;
}DNode, *DLinklist;

// 初始化双链表
bool InitDLinkList(Dlinklist &L){     
    L = (DNode *)malloc(sizeof(DNode)); 
    if(L==NULL)            
        return false;    
    L->prior = NULL;   //头结点的prior指针永远指向NULL     
    L->next = NULL;    //头结点之后暂时还没有结点，置空   
    return true;
}

void testDLinkList(){  
    DLinklist L;       
    InitDLinkList(L);       
    ...
}

// 判断双链表是否为空
bool Empty(DLinklist L){   
    if(L->next == NULL)   
        return true;      
    else             
        return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    1. 双链表的后插操作：
    typedef struct DNode{     
    ElemType data;       
    struct DNode *prior, *next;
}DNode, *DLinklist;

// 将结点s插入到结点p之后
bool InsertNextDNode(DNode *p, DNode *s){ 
    if(p==NULL || s==NULL)  
        return false;         
    s->next = p->next;      
    // 判断结点p之后是否有后继结点  
    if (p->next != NULL)   
        p->next->prior = s; 
    s->prior = p;   
    p->next = s;     
    return true;
}

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

    双链表的前插操作、按位序插入操作都可以转换成后插操作

    1. 双链表的删除操作：
    // 删除p结点的后继结点
bool DeletNextDNode(DNode *p){   
    if(p==NULL)           
        return false;   
    // 找到p的后继结点q    
    DNode *q =p->next;   
    if(q==NULL)          
        return false;    
    p->next = q->next;   
    if(q->next != NULL) 
        q->next->prior=p;  
    free(q);     
    return true;
}

// 销毁一个双链表
bool DestoryList(DLinklist &L){ 
    // 循环释放各个数据结点   
    while(L->next != NULL){    
        DeletNextDNode(L);      
        free(L);        
        // 头指针置空  
        L=NULL;     
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    1. 双链表的遍历：
    // 删除p结点的后继结点
bool DeletNextDNode(DNode *p){   
    if(p==NULL)           
        return false;   
    // 找到p的后继结点q    
    DNode *q =p->next;   
    if(q==NULL)          
        return false;    
    p->next = q->next;   
    if(q->next != NULL) 
        q->next->prior=p;  
    free(q);     
    return true;
}

// 销毁一个双链表
bool DestoryList(DLinklist &L){ 
    // 循环释放各个数据结点   
    while(L->next != NULL){    
        DeletNextDNode(L);      
        free(L);        
        // 头指针置空  
        L=NULL;     
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。

    2.3.8 循环链表

    在这里插入图片描述

    1. 循环链表的定义： 循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
    2. 循环单链表的实现：
    typedef struct LNode{           
    ElemType data;                  
    struct LNode *next; 
}DNode, *Linklist;

// 初始化循环单链表
bool InitList(LinkList &L){    
    L = (LNode *)malloc(sizeof(LNode));  
    if(L==NULL)             
        return false;    
    // 最后一个结点的next指针指向头结点    
    L->next = L;       
    return true;
}

// 判断循环单链表是否为空
bool Empty(LinkList L){    
    if(L->next == L)       
        return true;    
    else             
        return false;
}

// 判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L, LNode *p){ 
    if(p->next == L)          
        return true;      
    else            
        return false;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    1. 循环双链表的实现：
    typedef struct DNode{            
    ElemType data;           
    struct DNode *prior, *next;  
}DNode, *DLinklist;

// 初始循环双链表
bool InitDLinkList(DLinklist &L){  
    L = (DNode *) malloc(sizeof(DNode));  
    if(L==NULL)            
        return false;    
    // 头结点的prior指针指向最后一个结点，最后一个结点的next指针指向头结点 
    L->prior = L;      
    L->next = L;
}

// 判断循环双链表是否为空
bool Empty(DLinklist L){   
    if(L->next == L)       
        return true;      
    else           
        return false;
}

// 判断结点p是否为循环双链表的表尾结点
bool isTail(DLinklist L, DNode *p){   
    if(p->next == L)        
        return true;     
    else            
        return false;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    1. 循环双链表的插入和删除操作：
    // 将结点s插入到结点p之后
bool InsertNextDNode(DNode *p, DNode *s){  
    s->next = p->next;   
    //循环双链表不用担心p结点的下一个结点为空   
    p->next->prior = s;  
    s->prior = p;     
    p->next = s;
}

// 删除p结点的后继结点
bool DeletNextDNode(DNode *p){  
    // 找到p的后继结点q       
    DNode *q =p->next;        
    //循环双链表不用担心q结点的下一个结点为空  
    p->next = q->next;    
    q->next->prior=p;    
    free(q);      
    return true;
}


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

    2.3.9. 静态链表

    1. 静态链表的定义：用数组的方式实现的链表。分配一整片连续的内存空间，各个结点集中安置，每个结点包括了数据元素和下一个结点的数组下标。
      在这里插入图片描述

    2. 特点：

      • 优点：增、删操作不需要大量移动元素。
      • 缺点：不能随机存取，只能从头结点开始依次往后查找，容量固定不变！

    3. 静态链表的定义：

    #define MaxSize 10        //静态链表的最大长度
struct Node{              //静态链表结构类型的定义  
    ElemType data;        //存储数据元素    
    int next;             //下一个元素的数组下标
};

// 用数组定义多个连续存放的结点
void testSLinkList(){    
    struct Node a[MaxSize];  //数组a作为静态链表, 每一个数组元素的类型都是struct Node    
    ...
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    也可以这么定义：

    #define MaxSize 10        //静态链表的最大长度
typedef struct{           //静态链表结构类型的定义       
    ELemType data;        //存储数据元素     
    int next;             //下一个元素的数组下标
}SLinkList[MaxSize];

void testSLinkList(){      
    SLinkList a;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    第一种是我们更加熟悉的写法，第二种写法则更加侧重于强调 a 是一个静态链表而非数组。

    1. 静态链表的注意点：

      • 初始化静态链表时，需要把a[0]的next设为-1，并将空闲结点的next设置为某个特殊值，比如-2。
      • 按位序查找结点时，从头结点出发挨个往后遍历结点，时间复杂度 O = ( n ) O=(n)O=(n)。
      • 按位序插入结点的步骤：①找到一个空的结点，存入数据元素；②从头结点出发找到位序为 i-1 的结点；③修 改新结点的next 为 -1；④修改 i-1 号结点的next为新结点的下标；

    2.3.10. 顺序表和链表的比较

    1. 逻辑结构：顺序表和链表都属于线性表，都是线性结构。

    2. 存储结构：

      • 顺序表：顺序存储
        优点：支持随机存取，存储密度高。
        缺点：大片连续空间分配不方便，改变容量不方便。

      • 链表：链式存储
        优点：离散的小空间分配方便，改变容量方便。
        缺点：不可随机存取，存储密度低。

    3. 基本操作 - 创建：

      • 顺序表：需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源。
        • 静态分配：静态数组，容量不可改变。
        • 动态分配：动态数组，容量可以改变，但是需要移动大量元素，时间代价高（使用malloc()、free()）。
      • 链表：只需要分配一个头结点或者只声明一个头指针。

    4. 基本操作 - 销毁：

      • 顺序表：修改 Length = 0
        静态分配：静态数组——系统自动回收空间。
        动态分配：动态数组——需要手动free()。
      • 链表：依次删除各个结点 free()。

    5. 基本操作 - 增/删：

      • 顺序表：插入 / 删除元素要将后续元素后移 / 前移；时间复杂度：O ( n ) O(n)O(n)，时间开销主要来自于移动元素。
      • 链表：插入 / 删除元素只需要修改指针；时间复杂度：O ( n ) O(n)O(n)，时间开销主要来自查找目标元素。

    6. 基本操作 - 查找：

      • 顺序表
        • 按位查找：O ( 1 ) O(1)O(1)
        • 按值查找：O ( n ) O(n)O(n)，若表内元素有序，可在 O ( l o g 2 n ) O(log2n)O(log2n) 时间内找到（二分法）
      • 链表：
        • 按位查找：O ( n ) O(n)O(n)
        • 按值查找：O ( n ) O(n)O(n)
  • 相关阅读:
    【TypeScript】中定义变量方式 | 数据类型详解
    回应张逸老师（二）小甜甜和牛夫人？
    基于Ant Design设计语言的WinForm UI界面库
    数据结构(十一) -- 树(三) -- 堆排序
    Unity使用Remote直接在手机上调试游戏
    后端统一处理返回前端日期LocalDateTime格式化去T，Long返回前端损失精度问题
    产品公告 | MemFire Cloud V1内测版即将停止服务
    网站被劫持了怎么办
    QT 字符串操作常用接口函数
    MATLAB的官方网站上其实有很多MATLAB的学习和使用资料(文档、视频都有不少)
  • 原文地址：https://blog.csdn.net/zzzzzyliu/article/details/136660352