数据结构(二)线性表

作者: AdRainty | 来源:发表于2021-08-19 00:13 被阅读0次

2.1 线性表的定义

线性表是具有相同数据类型的n (n>0）个数据元素的有限序列，其中n为表长，当n =0时线性表是一个空表。若用L命名线性表，则其一般表示为
$L=\left(a_{1}, a_{2}, \ldots, a_{i}, a_{i+1}, \ldots, a_{n}\right)$
式中， $a_1$ 是唯一的“第一个”数据元素，又称表头元素； $a_n$ 是唯一的“最后一个”数据元素，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱;除最后一个元素外，每个元素有且仅有一个直接后继。

线性表.png

线性表的特点如下：

表中元素的个数有限
表中元素具有逻辑上的顺序性，表中元素有其先后次序
表中元素都是数据元素，每个元素都是单个元素
表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间
表中元素具有抽象性，即仅讨论元素之间的逻辑关系，而不考虑元素究竟表示什么内容

2.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的长度，即L中数据元素的个数。
PrintList(L):输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L):判空操作。若L为空表，则返回true，否则返回false。

2.3 线性表的数据表示

2.3.1 顺序表的定义

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理上也相邻，元素之间的关系由存储单元的邻接关系来体现。

其优点是可随机存取，存储密度高，缺点是要求大片的连续空间，改变容量不方便

假设线性表 $L$ 存储的起始位置为 $LOC(A)$ ， $sizeof(ElemType)$ 是每个数据元素所占用的存储空间的大小，则

数组下标	顺序表	内存地址
$0$	$a_1$	$LOC(A)$
$1$	$a_2$	$LOC(A)+sizeof(ElemType)$
$\cdots$	$\cdots$	$\cdots$
$i-1$	$a_i$	$LOC(A)+(i-1)×sizeof(ElemType)$
$\cdots$	$\cdots$	$\cdots$
$MaxSize-1$	$MaxSize$	$LOC(A)+(MaxSize-1)×sizeof(ElemType)$

2.3.2 顺序表的实现

2.3.2.1 静态分配

在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据就会产生溢出，进而导致程序崩溃。

假设线性表的数据元素一类型为ElemType，则线性分配代码如下所示：

#include<stdio.h>
#define MaxSize 10
typedef struct{
    int data[MaxSize];
    int length;
}SqList; 

void InitList(SqList &L){
    for(int i=0;i<MaxSize;i++){
        L.data[i]=0;
    }
    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]);
    }
    return 0;
}

2.3.2.2 动态分配

在动态分配时，存储数组的空间时在程序执行过程中通过动态存储分配语句分配的，一旦数据空间沾满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的，而不需要为线性表一次性地划分所有空间。

#include <stdlib.h>
#include <stdio.h>
#define Initsize 10     //默认的最大长度
typedef struct{
    int *data ;     //指示动态分配数组的指针
    int MaxSize;    //顺序表的最大容量
    int length;     //顺序表的当前长度
}SeqList;

void InitList(SeqList &L){
    //用malloc函数申请一片连续的存储空间
    L.data=(int *)malloc(Initsize*sizeof(int));
    L.length=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;        //顺序表最大长度增加len
    free(p);                        //释放原来的内存空间
}

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

其中C的初始动态分配语句为

L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize)

C++的初始动态分配语句为

L.data = new ElemType[InitSize]

2.3.2.3 顺序表的特点:

①随机访问，即可以在O(1)时间内找到第i个元素。

②存储密度高，每个节点只存储数据元素

③拓展容量不方便(即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高)

④插入、删除操作不方便，需要移动大量元素

2.3.3 顺序表上的基本操作的实现

2.3.3.1 插入操作

在顺序表 $L$ 的第 $i(1\le i\le L.length+1)$ 个位置插入新元素 $e$ 。若 $i$ 的输入不合法，则返回false，表示插入失败；否则，将第 $i$ 个元素及其后的所有元素依次往后移动一个位置，腾出一个空位置插入新元素 $e$ ，顺序表的长度增加1，插入成功，返回True

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;
}

插入操作的时间复杂度

最好情况：在表尾插入(即 $i=n+1$ )，元素后移语句将不执行，时间复杂度为 $O(1)$
最坏情况：在表头插入(即 $i=1$ ),元素后移语句将执行n次，时间复杂度为 $O(n)$
平均情况：假设新元素插入到任何一个位置的概率相同，即 $i=1,2,\cdots,length+1$ 的概率都是 $\frac{1} {n+1}$ ，平均循环次数为

$np+(n-1)p+(n-2)p+\cdots+1*p=\frac{n(n+1)}{2}\frac{1}{n+1}=\frac{n}{2}$$

因此，线性表插入算法的平均时间复杂度为 $O(n)$

2.3.3.2 删除操作

删除顺序表 $L$ 的第 $i(1\le i\le L.length)$ 个位置的元素，用引用变量 $e$ 返回。若 $i$ 的输入不合法，则返回false；否则，将被删除元素赋值给引用变量 $e$ ，并将第 $i$ 个元素及其后的所有元素依次往前移动一个位置，顺序表的长度减少，返回True

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--;             //线性表的长度-1
    return true;
}

删除操作的时间复杂度

最好情况：删除表尾元素(即 $i=n$ )，无需移动元素，时间复杂度为 $O(1)$
最坏情况：删除表头元素(即 $i=1$ )，需移动除表头元素外的所有元素，时间复杂度为 $O(n)$
平均情况：假设删除任何一个元素的概率相同，即 $i=1,2,\cdots,length$ 的概率都是 $\frac{1} {n}$ ，平均循环次数为

$(n-1)p+(n-2)p+\cdots+1*p=\frac{n(n+1)}{2}\frac{1}{n}=\frac{n-1}{2}$

因此，线性表插入算法的平均时间复杂度为 $O(n)$

2.3.3.3 按位查找

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

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

时间复杂度： $O(1)$

“随机存取”特性:由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素

2.3.3.4 按值查找

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

int LocateElem(SeqList L,ElemType e){
    int i;
    for(i=0;i<L.length;i++){
        if(L.data[i]==e)
            return i+1;
        return 0;
    }
}

按值查找的时间复杂度

最好情况：查找的元素就在表头，循环一次，时间复杂度为 $O(1)$
最坏情况：目标元素在表尾，循环n次，时间复杂度为 $O(n)$
平均情况：假设目标元素出现在任何一个位置的概率相同，都是 $\frac{1}{n}$ ，平均循环次数

$1*\frac{1}{n}+2*\frac{1}{n}+3*\frac{1}{n}+\cdots+n*\frac{1}{n}=\frac{n(n+1)}{2}\frac{1}{n}=\frac{n+1}{2}$

时间复杂度为 $O(n)$

2.4 线性表的链式表示

2.4.1 单链表的定义

线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的存储元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需要存放一个指向后继的指针。

单链表.png

其优点是不要求大片的连续空间，改变容量方便。缺点是不可随机存取，要耗费一定的空间存放指针

单链表结点类型描述如下：

struct LNode{
    ElemType data;          //每个结点存放一个数据元素
    struct LNode *next;     //指针指向下一个结点
// typedef struct LNode LNode;
// typedef struct LNode *LinkList;
}LNode, *LinkList;

创建新结点的代码如下：

// 增加一个新的结点：在内存中申请一个结点所需空间，并用指针p指向这个结点
struct LNode *p = (struct LNode *) malloc(sizeof(struct LNode));

2.4.2 单链表的实现

通常用头指针来标识一个单链表，如单链表L，头指针为NULL时表示一个空表，此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头节点。头节点的数据域可以不设任何信息，也可以记录表长等信息。头节点的指针域指向线性表的第一个元素的结点。

2.4.2.1 不带头节点的单链表

typedef struct LNode{
    ElemType data;          //每个结点存放一个数据元素
    struct LNode *next;     //指针指向下一个结点
}LNode, *LinkList;

// 初始化一个空的单链表
bool InitList(LinkList &L){
    L=NULL;
    return true;
}

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

void test(){
    LinkList L;             //声明一个指向单链表的指针
    InitList(L);
}

2.4.2.2 带头结点的单链表

typedef struct LNode{
    ElemType data;          //每个结点存放一个数据元素
    struct LNode *next;     //指针指向下一个结点
}LNode, *LinkList;

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

// 初始化一个空的单链表(带头结点)
bool InitList(LinkList &L){
    L=(LNode *) malloc(sizeof(LNode));      //分配一个头结点
    if (L==NULL)        //内存不足，分配失败
        return false;
    L->next = NULL;     //头结点之后暂时还没有结点
    return true;
}

引入头结点后，可以带来两个优点：

由于第一个数据结点的位置被存放在头结点的指针域中，因此链表的第一个位置上的操作和在表的其他位置上的操作一致，无需进行特殊处理
无论链表是否为空，其头指针都指向头结点的非空指针(空表中头结点的指针域为空)，因此空表和非空表的处理也就得到了统一

2.4.3 单链表上基本操作的实现

2.4.3.1 按位序插入

2.4.3.1.1 带头结点

ListInsert(&L,i,e):插入操作，在表L中的第i个位置插入指定元素e（找到第i-1个结点，将新结点插入其后）

bool ListInsert(LinkList &L, int i, ElemType e){
    if (i<1)
        return false;
    LNode *p;       //指针p指向当前扫描到的结点
    int j=0;        //当前p指向的是第几个结点
    p = L;          //L指向头结点，头结点是第0个结点
    while (p!=NULL && j<i-1){   //循环找到第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;
}

平均时间复杂度为 $O(n)$

2.4.3.1.2 不带头结点

bool ListInsert(LinkList &L, int i, ElemType e){
    if (i<1)
        return false;
    // 如果不带头结点，则插入、删除第一个元素时，需要更改头指针L
    if (i==1){
        LNode *s = (LNode *) malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L = s;      //头指针指向新结点
        return true;
    }
    LNode *p;       //指针p指向当前扫描到的结点
    int j=1;        //当前p指向的是第几个结点
    p = L;          //L指向第一个结点
    while (p!=NULL && j<i-1){   //循环找到第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;
}

2.4.3.2 指定结点的后插操作

InsertNextNode(&L,e)：在p结点后插入元素e

bool InsertNext(LNode *p, ElemType e){
    if (p==NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    /*
    某些情况下有可能分配内存失败，如内存不足
    if (s==NULL)    //分配内存失败
        return false;
    */
    s->data = e;    //用结点s保存数据元素e
    s->next = p->next;
    p->next = s;        //将结点s连到p之后
    return true;
}

时间复杂度为 $O(1)$

返回前插元素的代码，原代码就可以改成

bool ListInsert(LinkList &L, int i, ElemType e){
    if (i<1)
        return false;
    // 如果不带头结点，则插入、删除第一个元素时，需要更改头指针L
    if (i==1){
        LNode *s = (LNode *) malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L = s;      //头指针指向新结点
        return true;
    }
    LNode *p;       //指针p指向当前扫描到的结点
    int j=1;        //当前p指向的是第几个结点
    p = L;          //L指向第一个结点
    while (p!=NULL && j<i-1){   //循环找到第i-1个结点
        p = p->next;
        j++;
    }
    return InsertNextNode(p, e);
}

2.4.3.3 指定结点的前插操作

InsertPriorNode(&L,*P,e)：在p结点前插入元素e

方法1：传入头指针

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

时间复杂度为 $O(n)$

方法2：

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连到p之后
    s->data = p->data   //将p中元素复制到s中
    p->data = e;        //p中元素覆盖为e
    return true;
}

时间复杂度为 $O(1)$

2.4.3.4 按位序删除(带头结点)

LisDelete(&L,i,&e):删除操作，删除L中第i个位置的元素，并用e返回删除元素的值

bool LisDelete(LinkList &L, int i, ElemType &e){
    if (i<1)
        return false;
    LNode *p;       //指针p指向当前扫描到的结点
    int j=0;        //当前p指向的是第几个结点
    p = L;          //L指向头结点，头结点是第0个结点
    while (p!=NULL && j<i-1){   //循环找到第i-1个结点
        p = p->next;
        j++;
    }
     if (p==NULL) //i值不合法
        return false;
     if (p->next == NULL) //第i-1个结点后已无其他结点
        return false;
    LNode *q = p->next; //命q指向被删除结点
    e = q->data;        //用e返回元素的值
    p->next = q->next;  //将*q结点从链中断开
    free(q);            //释放节点的存储空间
    return true;
}

平均时间复杂度 $O(1)$

2.4.3.5 指定结点的删除

bool DeleteNode(LNode *p){
    if (p==NULL) //i值不合法
        return false;
    LNode *q = p->next; //命q指向被删除结点
    p->data = p->next->data；    //和后继结点交换数据域
    p->next = q->next;  //将*q结点从链中断开
    free(q);        //释放节点的存储空间
    return true;
}

平均时间复杂度为 $O(1)$

但是此方法存在局限性：

如果p是最后一个结点则找不到后继结点，会出bug，此时只能从表头依次寻找p的前驱，时间复杂度为 $O(n)$

因此说明了单链表的局限性：

无法逆向检索，有时候不太方便

2.4.3.6 单链表的查找操作（带头结点）

2.4.3.6.1 按位查找

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

LNode * GetElem(LinkList L, int i){ 
    if (i<1)
        return NULL;
    LNode *p;       //指针p指向当前扫描到的结点
    int j=0;        //当前p指向的是第几个结点
    p = L;          //L指向头结点，头结点是第0个结点
    while (p!=NULL && j<i-1){   //循环找到第i-1个结点
        p = p->next;
        j++;
    }
    return p;
}

平均时间复杂度： $O(n)$

2.4.3.6.2 按值查找

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

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

平均时间复杂度： $O(n)$

2.4.3.7 求表的长度

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

时间复杂度： $O(n)$

2.4.3.8 单链表的建立

初始化一个单链表
每次取一个数据元素，插入到表尾/表头

2.4.3.8.1 尾插法

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指向新的表尾结点
        scanf("%d",&x);
    }
    r->next = NULL;     //表尾点指针置空
    return L；
}

时间复杂度为 $O(n)$

2.4.3.8.2 头插法

LinkList List_HeadInsert(LinkList &L){  //正向建立单链表
    LNode *s; int x;
    L=(LinkList)malloc(sizeof(LNode));  //创建头结点
    L->next = NULL;                     //初始为空链表
    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;
}

时间复杂度为 $O(n)$

2.4.4 双链表

为了克服单链表只有一个指向其后继的指针，引入了双链表，双链表结点中又两个指针prior和next，分别指向其前驱结点和后驱结点。其结点类型描述如下

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;
}

2.4.4.1 双链表的插入

//在p结点后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
    if (p==NULL||s==NULL)   //非法参数
        return false;
    s->next = p->next;      //将结点*s插入到点*p之后
    if (p->next != NULL)    //如果p结点后又后继结点
        p->next->prior = s;
    s->prior = p;
    p->next =s;
}

2.4.4.2 双链表的删除

//删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
    if (p==NULL)    return false;
    DNode *q = p->next;     //找到p的后继结点q
    if (q==NULL)    return false;   //p没有后继
    p->next = q->next;
    if (q->next!=NULL)  //q结点不是说最后一个结点
        q->next->prior = p;
    free(q);        //释放结点空间
    return true;
}

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

2.4.5 循环链表

2.4.5.1 循环单链表

循环单链表.png

//初始化一个循环单链表
bool InitList(LinkList &L){
    L = (LNode *) malloc(sizeof(LNode));        //分配一个头结点
    if (L==NULL)        //内存不足，分配失败
        return false;
    L->next = L;        //头结点next指向头结点
    // 普通的单链表结尾指向NULL
    return true;
}

循环单链表可以从表中的任意一个结点开始遍历整个列表

2.4.5.2 循环双链表

循环双链表表头结点的prior指向表尾结点；表尾结点的next指向头结点

bool InitDLinkList(DLinklist &L){
    L = (DNode *) malloc(sizeof(DNode));        //分配一个头结点
    if (L == NULL)      //内存不足，分配失败
        return false;
    L->prior = L;       //头结点的prior指向头结点
    L->next = L;        //头结点的next指向结点
    return true;
}

2.4.6 静态链表

静态链表需要预先分配一整片的连续内存空间，其借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，这个指针是结点的相对地址(数组下标)，又称游标。静态链表的结构类型描述如下：

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

void testSLinkList(){
    struct Node a[MaxSize];     //数组a作为静态链表
}

游标为-1表示已经到达表尾

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

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

2.5 顺序表和链表的比较

逻辑结构：都属于线性表，都是线性结构
存储结构：
- 顺序表是顺序存储，支持随机存取、存储密度高；缺点是大片连续空间分配不方便，改变容量不方便
- 链表是链式存储，离散的小空间分配方便，改变容量方便；缺点是不可随机存取，存储密度低
基本操作：
- 创建数据表
  - 顺序表需要预分配大片连续空间，若分配空间过小，则之后不方便扩展容量；若分配空间过大，浪费内存资源
  - 链表只需分配一个头结点(也可不要头结点，只声明一个指针)，之后方便扩展
- 销毁操作
  - 顺序表①修改Length=0②若用静态分配，系统自动回收空间；若用动态分配，则需要手动free
  - 链表：依次删除各个结点
- 增加和删除
  - 顺序表插入/删除元素要将后续元素都后移/前移，时间复杂度为O(n)，时间开销来自移动元素
  - 链表插入/删除元素只需要修改指针即可，时间复杂度为O(n)，时间开销来自查找目标元素
- 查找操作
  - 顺序表：按位查找：O(1);按值查找：O(n)若表内元素有序，则 $O(log_2{n})$
  - 链表：O(n)

数据结构(二)线性表

2.1 线性表的定义

2.2 线性表的基本操作

2.3 线性表的数据表示

2.3.1 顺序表的定义

2.3.2 顺序表的实现

2.3.2.1 静态分配

2.3.2.2 动态分配

2.3.2.3 顺序表的特点:

2.3.3 顺序表上的基本操作的实现

2.3.3.1 插入操作

2.3.3.2 删除操作

2.3.3.3 按位查找

2.3.3.4 按值查找

2.4 线性表的链式表示

2.4.1 单链表的定义

2.4.2 单链表的实现

2.4.2.1 不带头节点的单链表

2.4.2.2 带头结点的单链表

2.4.3 单链表上基本操作的实现

2.4.3.1 按位序插入

2.4.3.1.1 带头结点

2.4.3.1.2 不带头结点

2.4.3.2 指定结点的后插操作

2.4.3.3 指定结点的前插操作

2.4.3.4 按位序删除(带头结点)

2.4.3.5 指定结点的删除

2.4.3.6 单链表的查找操作（带头结点）

2.4.3.6.1 按位查找

2.4.3.6.2 按值查找

2.4.3.7 求表的长度

2.4.3.8 单链表的建立

2.4.3.8.1 尾插法

2.4.3.8.2 头插法

2.4.4 双链表

2.4.4.1 双链表的插入

2.4.4.2 双链表的删除

2.4.5 循环链表

2.4.5.1 循环单链表

2.4.5.2 循环双链表

2.4.6 静态链表

2.5 顺序表和链表的比较

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读