链表

2022-04-08 本文已影响0人 jancywen

定义：数据元素随机存储，并通过指针表示数据之间逻辑关系的存储结构就是链式存储结构

节点

链表中每个数据的存储称为节点由两部分组成：

数据元素本身，其所在的区域称为数据域；
指向直接后继元素的指针，所在的区域称为指针域；

链表实际存储的是一个一个的节点，真正的数据元素包含在这些节点中

链表的构成

一个完整的链表需要由以下几部分构成：

头指针：一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据；
节点：链表中的节点又细分为头节点、首元节点和其他节点：

头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题；

首元节点：由于头节点（也就是空节点）的缘故，链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义；

其他节点：链表中其他的节点；

链表中有头节点时，头指针指向头节点；反之，若链表中没有头节点，则头指针指向首元节点

链表的创建

声明一个头指针（如果有必要，可以声明一个头节点）；
创建多个存储数据的节点，在创建的过程中，要随时与其前驱节点建立逻辑关系；

//声明节点结构
typedef struct Link {
    int  elem;//存储整形元素
    struct Link *next;//指向直接后继元素的指针
}link;
//创建链表的函数
link * initLink() {
    link * p = (link*)malloc(sizeof(link));//创建一个头结点
    link * temp = p;//声明一个指针指向头结点，用于遍历链表
    int i = 0;
    //生成链表
    for (i = 1; i < 5; i++) {
        //创建节点并初始化
        link *a = (link*)malloc(sizeof(link));
        a->elem = i;
        a->next = NULL;
        //建立新节点与直接前驱节点的逻辑关系
        temp->next = a;
        temp = temp->next;
    }
    return p;
}

链表插入元素

向链表中增添元素，根据添加位置不同，可分为以下 3 种情况：

插入到链表的头部（头节点之后），作为首元节点；
插入到链表中间的某个位置；
插入到链表的最末端，作为链表中最后一个数据元素；

新元素插入步骤：

将新结点的 next 指针指向插入位置后的结点；
将插入位置前结点的 next 指针指向插入结点；

//p为原链表，elem表示新数据元素，add表示新元素要插入的位置
link * insertElem(link * p, int elem, int add) {
    link * temp = p;//创建临时结点temp
    link * c = NULL;
    int i = 0;
    //首先找到要插入位置的上一个结点
    for (i = 1; i < add; i++) {
        if (temp == NULL) {
            printf("插入位置无效\n");
            return p;
        }
        temp = temp->next;
    }
    //创建插入结点c
    c = (link*)malloc(sizeof(link));
    c->elem = elem;
    //向链表中插入结点
    c->next = temp->next;
    temp->next = c;
    return  p;
}

链表删除元素

操作步骤：

将结点从链表中摘下来; temp->next=temp->next->next;
手动释放掉结点，回收被结点占用的存储空间; free(del);

链表元素查找

从表头依次遍历表中节点，用被查找元素与各节点数据域中存储的数据元素进行比对，直至比对成功或遍历至链表最末端的 NULL

链表元素更新

遍历找到存储此元素的节点，对节点中的数据域做更改操作即可

栈

栈是一种只能从表的一端存取数据且遵循 "先进后出" 原则的线性存储结构。

栈的开口端被称为栈顶；相应地，封口端被称为栈底

向栈中添加元素，此过程被称为"进栈"（入栈或压栈）；
从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）；

链栈

采用链式存储结构实现栈结构；

通常将链表的头部作为栈顶，尾部作为栈底，

将链表头部作为栈顶的一端，可以避免在实现数据 "入栈" 和 "出栈" 操作时做大量遍历链表的耗时操作。

链表的头部作为栈顶，意味着：

在实现数据"入栈"操作时，需要将数据从链表的头部插入；
在实现数据"出栈"操作时，需要删除链表头部的首元节点；

队列

数据从表的一端进，从另一端出，且遵循 "先进先出" 原则的线性存储结构就是队列。

链式队列

链式队列，简称"链队列"，即使用链表实现的队列存储结构。

初始状态

初始状态的队列中没有存储任何数据元素，top(队头) 和 rear(队尾) 指针都同时指向头节点。

//链表中的节点结构
typedef struct QNode{
    int data;
    struct QNode * next;
}QNode;
//创建链式队列的函数
QNode * initQueue(){
    //创建一个头节点
    QNode * queue=(QNode*)malloc(sizeof(QNode));
    //对头节点进行初始化
    queue->next=NULL;
    return queue;
}

...
QNode * queue,*top,*rear;
queue=top=rear=initQueue();//创建头结点

链式队列数据入队

链队队列中，当有新的数据元素入队，只需进行以下 3 步操作：

将该数据元素用节点包裹，例如新节点名称为 elem；
与 rear 指针指向的节点建立逻辑关系，即执行 rear->next=elem；
最后移动 rear 指针指向该新节点，即 rear=elem；

QNode* enQueue(QNode * rear,int data){
    //1、用节点包裹入队元素
    QNode * enElem=(QNode*)malloc(sizeof(QNode));
    enElem->data=data;
    enElem->next=NULL;
    //2、新节点与rear节点建立逻辑关系
    rear->next=enElem;
    //3、rear指向新节点
    rear=enElem;
    //返回新的rear，为后续新元素入队做准备
    return rear;
}

链式队列数据出队

链式队列中队头元素出队，需要做以下 3 步操作：

通过 top 指针直接找到队头节点，创建一个新指针 p 指向此即将出队的节点；
将 p 节点（即要出队的队头节点）从链表中摘除；
释放节点 p，回收其所占的内存空间；

void DeQueue(QNode * top,QNode * rear){
    QNode * p=NULL;
    if (top->next==NULL) {
        printf("队列为空");
        return ;
    }
    p=top->next;
    printf("%d",p->data);
    top->next=p->next;
    if (rear==p) {
        rear=top;
    }
    free(p);
}

注意：将队头元素做出队操作时，需提前判断队列中是否还有元素，如果没有，要提示用户无法做出队操作，保证程序的健壮性。

链表

节点