顺序表和链表

目录

  • 线性表
    • 顺序表
      • 概念与结构
      • 分类
        • 静态顺序表
        • 动态顺序表
      • 动态顺序表的实现
        • SeqList.h
        • SeqLIst.c 和 test.c
        • 初始化SLInit
        • 增容SLCheckCapacity
        • 尾插SLPushBack
        • 打印SLPrint
        • 头插SLPushFront
        • 尾删SLPopBack
        • 头删SLPopFront
        • 查找SLFind
        • 任意插SLInsert
        • 任意删SLErase
        • 销毁顺序表SLDestroy
      • 顺序表问题与思考
    • 单链表
      • 概念与结构
        • 节点/结点
        • 链表的性质
      • 单链表的实现
        • SLIst.h
        • SList.c和test.c
        • 打印print
        • 申请新的节点
        • 尾插push_back
        • 头插push_front
        • 尾删pop_back
        • 头删pop_front
        • 查找find
        • 指定节点之前插入数据insert
        • 指定节点之后插入数据insert_after
        • 删除指定节点erase
        • 删除指定节点之后的节点erase_after
        • 销毁单链表destroy
    • 链表的分类
    • 双向链表
      • 概念与结构
      • 实现双向链表
        • List.h
        • List.c和test.c
        • 申请新节点
        • 初始化1
        • 初始化2(推荐)
        • 打印
        • 尾插
        • 头插
        • 尾删
        • 头删
        • 查找
        • 任意位置之前插
        • 删除任意节点
        • 销毁1
        • 销毁2（推荐）

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。
线性表是一种在实际中广泛使用的数据结构。
常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就是逻辑上的连续的一条直线。
但在物理结构上并不一定是连续的。线性表在物理上存储时，通常以数组和链式结构的形式存储。

在这里插入图片描述

顺序表

顺序表就是一种在逻辑上连续，物理上也连续的线性表。

在这里插入图片描述

概念与结构

概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，
一般情况下采用数组存储。
在这里插入图片描述

顺序表和数组的区别？
顺序表的底层结构是数组，对数组的封装，实现了常用的增删查改等接口。

在这里插入图片描述

分类

顺序表分为：静态顺序表和动态顺序表。

静态顺序表
//静态循序表的结构
#define N 8
typedef int SLDataType;
typedef struct SeqList
{SLDataType data[N]; //定长数组int size; //有效数据个数
}SL;

在这里插入图片描述

静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费。

动态顺序表
//动态循序表的结构
typedef int SLDataType;
typedef struct SeqList
{SLDataType* data;int size; //有效数据个数int capacity; //空间容量
}SL;

在这里插入图片描述

动态顺序表按需申请，可增容。 - 一般2倍增容。

动态顺序表的实现

我们分一个.h头文件和2个.c源文件，去实现顺序表。

SeqList就是sequence list 就是顺序表的意思。

在这里插入图片描述

SeqList.h
//动态顺序表的实现#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDataType;
typedef struct SeqList
{SLDataType* data;int size; //有效数据个数int capacity; //空间容量
}SL;//初始化
void SLInit(SL* ps);//尾插
void SLPushBack(SL* ps, SLDataType x);//打印
void SLPrint(SL* ps);//头插
void SLPushFront(SL* ps, SLDataType x);//尾删
void SLPopBack(SL* ps);//头删
void SLPopFront(SL* ps);//查找指定数据 - 找到返回下标，找不到返回-1
int SLFind(SL* ps, SLDataType x);//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x);//删除指定位置的数据
void SLErase(SL* ps, int pos);//销毁顺序表
void SLDestroy(SL* ps);
SeqLIst.c 和 test.c

函数功能的实现和测试

初始化SLInit
//初始化
void SLInit(SL* ps)
{assert(ps);//防止ps为NULLps->data = NULL;//初始化ps->size = ps->capacity = 0;//初始化
}

test.c

	SL sl;//创建一个空的顺序表SLInit(&sl);//初始化//只有传地址才能改变sl的值

在这里插入图片描述

增容SLCheckCapacity

在所有的插入动作之前都要判断是否需要增容。

//检查是否需增容
//static是让改函数只能在SeqList.c中使用
static void SLCheckCapacity(SL* ps)
{assert(ps);//防止ps为NULLif (ps->capacity == ps->size)//只有有效数据等于容量时才需要增容{int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//三目操作符定义新容量SLDataType* tmp = realloc(ps->data, NewCapacity * sizeof(SLDataType));//向堆区申请空间，申请的空间是原来的二倍。if (tmp == NULL)//检查是否申请空间失败{perror("SLCheckCapacity()::realloc()");exit(1);}ps->data = tmp;//把申请的空间给dataps->capacity = NewCapacity;//把新容量给顺序表的容量}
}
尾插SLPushBack
//尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//防止ps为NULL//检查是否需要增容SLCheckCapacity(ps);//尾插ps->data[ps->size++] = x;//在尾部插入元素，更新有效数据个数
}
打印SLPrint
//打印
void SLPrint(SL* ps)
{assert(ps);//防止ps为NULLfor (int i = 0; i < ps->size; i++)//遍历顺序表{printf("%d ", ps->data[i]);//打印顺序表中的数据}printf("\n");
}

test.c

	//测试尾插SLPushBack(&sl, 1);SLPrint(&sl);SLPushBack(&sl, 2);SLPrint(&sl);SLPushBack(&sl, 3);SLPrint(&sl);SLPushBack(&sl, 4);SLPrint(&sl);

在这里插入图片描述

头插SLPushFront
//头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//防止ps为NULL//检查是否需要增容SLCheckCapacity(ps);//头插for (int i = ps->size; i > 0; i--)//从后向前遍历顺序表，防止数据覆盖{ps->data[i] = ps->data[i - 1];}ps->data[0] = x;//头插ps->size++;//更新有效数据个数
}

test.c

	//测试头插SLPushFront(&sl, 1);SLPrint(&sl);SLPushFront(&sl, 2);SLPrint(&sl);SLPushFront(&sl, 3);SLPrint(&sl);SLPushFront(&sl, 4);SLPrint(&sl);

在这里插入图片描述

尾删SLPopBack
//尾删
void SLPopBack(SL* ps)
{assert(ps && ps->size);//防止ps为NULL且顺序表中没有数据ps->size--;//更新有效数据个数，达到遍历时访问不到尾部数据的目的
}

test.c

	//尾插SLPushBack(&sl, 1);SLPrint(&sl);SLPushBack(&sl, 2);SLPrint(&sl);SLPushBack(&sl, 3);SLPrint(&sl);SLPushBack(&sl, 4);SLPrint(&sl);//测试尾删SLPopBack(&sl);SLPrint(&sl);SLPopBack(&sl);SLPrint(&sl);SLPopBack(&sl);SLPrint(&sl);SLPopBack(&sl);SLPrint(&sl);SLPopBack(&sl);SLPrint(&sl);

在这里插入图片描述
第五次尾删时assert代码生效。

头删SLPopFront
//头删
void SLPopFront(SL* ps)
{assert(ps && ps->size);//防止ps为NULL且顺序表中没有数据for (int i = 0; i < ps->size - 1; i++)//从前向后遍历顺序表，防止数据被覆盖{ps->data[i] = ps->data[i + 1];}ps->size--;//更新有效数据个数
}

test.c

	//尾插SLPushBack(&sl, 1);SLPrint(&sl);SLPushBack(&sl, 2);SLPrint(&sl);SLPushBack(&sl, 3);SLPrint(&sl);SLPushBack(&sl, 4);SLPrint(&sl);//测试头删SLPopFront(&sl);SLPrint(&sl);SLPopFront(&sl);SLPrint(&sl);SLPopFront(&sl);SLPrint(&sl);SLPopFront(&sl);SLPrint(&sl);SLPopFront(&sl);SLPrint(&sl);

在这里插入图片描述
第五次头删时assert代码生效。

查找SLFind
//查找指定数据 - 找到返回下标，找不到返回-1
int SLFind(SL* ps, SLDataType x)
{assert(ps);//防止ps为NULLfor (int i = 0; i < ps->size; i++)//遍历顺序表与x相等的数据{if (x == ps->data[i])return i;//找到了，返回下标}return -1;//找不到返回-1
}

test.c

	//尾插SLPushBack(&sl, 1);SLPrint(&sl);SLPushBack(&sl, 2);SLPrint(&sl);SLPushBack(&sl, 3);SLPrint(&sl);SLPushBack(&sl, 4);SLPrint(&sl);//测试查找指定数据 - 找到返回下标，找不到返回-1int find = SLFind(&sl, 3);if (find != -1)printf("找到了，下标是:%d\n", find);elseprintf("找不到\n");

在这里插入图片描述

任意插SLInsert
//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);//防止ps为NULLassert(pos >= 0 && pos <= ps->size);//pos的合法范围//检查是否需要增容SLCheckCapacity(ps);for (int i = ps->size; i > pos; i--)//从后向前遍历[pos, size]的数据,防止数据被覆盖{ps->data[i] = ps->data[i - 1];}ps->data[pos] = x;//指定位置插ps->size++;//更新有效数据个数
}

test.c

	//尾插SLPushBack(&sl, 1);SLPrint(&sl);SLPushBack(&sl, 2);SLPrint(&sl);SLPushBack(&sl, 3);SLPrint(&sl);SLPushBack(&sl, 4);SLPrint(&sl);//测试在指定位置之前插入数据SLInsert(&sl, 1, 5);SLPrint(&sl);//1 5 2 3 4
}

在这里插入图片描述

任意删SLErase
//删除指定位置的数据
void SLErase(SL* ps, int pos)
{assert(ps && ps->size);//防止ps为NULL且顺序表中没有数据assert(pos >= 0 && pos < ps->size);//pos的合法范围for (int i = pos; i < ps->size - 1; i++)//从前向后遍历顺序表，防止数据被覆盖{ps->data[i] = ps->data[i + 1];}ps->size--;//更新有效数据个数
}

test.c

	//尾插SLPushBack(&sl, 1);SLPrint(&sl);SLPushBack(&sl, 2);SLPrint(&sl);SLPushBack(&sl, 3);SLPrint(&sl);SLPushBack(&sl, 4);SLPrint(&sl);//测试删除指定位置的数据SLErase(&sl, 2);SLPrint(&sl);//1 2 4

在这里插入图片描述

销毁顺序表SLDestroy
//销毁顺序表
void SLDestroy(SL* ps)
{assert(ps);//防止ps为NULLif (ps->data)//data不为NULL才释放空间free(ps->data);//将顺序表还原ps->data = NULL;ps->capacity = ps->size = 0;
}

test.c

	//尾插SLPushBack(&sl, 1);SLPrint(&sl);SLPushBack(&sl, 2);SLPrint(&sl);SLPushBack(&sl, 3);SLPrint(&sl);SLPushBack(&sl, 4);SLPrint(&sl);//测试销毁顺序表SLDestroy(&sl);

在这里插入图片描述

顺序表问题与思考

  1. 中间/头部的插⼊删除，时间复杂度为O(N)
  2. 增容需要申请新空间，拷⻉数据，释放旧空间。会有不⼩的消耗。
  3. 增容⼀般是呈2倍的增⻓，势必会有⼀定的空间浪费。

那么如何解决以上问题呢？

单链表

单链表是一种逻辑上连续，物理上不连续的线性表。

在这里插入图片描述

概念与结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，
数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

在这里插入图片描述
淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。
将火车里的某节车厢去掉/加上，不会影响其他车厢，每节车厢都是独立存在的。

在链表里，每节“车厢”是什么样的呢？

在这里插入图片描述

节点/结点

与顺序表不同的是，链表里的每节“车厢”都是独立申请下来的空间，我们称之为“节点/结点”。

节点主要由两个部分组成：当前节点要保存的数据和保存下一个节点的地址（指针变量）。

图中指针变量plist保存的是第一个节点的地址，我们称plist此时“指向”第一个节点，
如果我们希望plist“指向”第二个节点时，只需要修改plist保存的内容为0x0012FFA0。

链表中每个节点都是独立申请的（即需要插入数据时才会去申请一块节点的空间），
我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。

链表的性质
  1. 链式结构在逻辑上是连续的，在物理上不一定连续
  2. 节点一般是从堆上申请的
  3. 从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能联系，可能不连续

结合前面学到的结构体知识，我们可以给出每个节点对应的结构体代码：
假设当前保存的节点的数据类型为整型：

struct SListNode
{int data; //节点数据struct SListNode* next; //保存下一个节点的地址
};

当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要
保存整型数据，也要保存下一个节点的地址（当下一个节点为空时保存的地址为空）。

每一个节点都能找到下一个节点，所有的节点连起来，就成了一条线，
在这条线上我们能找到每一个节点。

单链表的实现

我们分一个.h头文件和2个.c源文件，去实现单链表。

SList就是singly-linked list，就是单链表的意思。

在这里插入图片描述

SLIst.h
//单链表的动态实现#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//节点的创建
typedef int SListDataType;
typedef struct SListNode
{SListDataType data; //节点的数据struct SListNode* next; //指向下一个节点的指针
}Node;//打印
void print(Node** pph);//尾插
void push_back(Node** pph, SListDataType x);//头插
void push_front(Node** pph, SListDataType x);//尾删
void pop_back(Node** pph);//头删
void pop_front(Node** pph);//查找指定节点的数据 - 找到返回节点，找不到返回NULL
Node* find(Node** pph, SListDataType x);//在指定节点之前插入数据
void insert(Node** pph, Node* pos, SListDataType x);//在指定节点之后插入数据
void insert_after(Node* pos, SListDataType x);//删除pos节点
void erase(Node** pph, Node* pos);//删除pos之后的节点
void erase_after(Node* pos);//销毁单链表
void destroy(Node** pph);
SList.c和test.c

函数功能的实现和测试

打印print
//打印
void print(Node** pph)
{assert(pph);//防止pph为空Node* cur = *pph;//记录第一个节点的地址while (cur)//遍历单链表{printf("%d->", cur->data);//打印每个节点的数据cur = cur->next;//找下一个节点}printf("NULL\n");//最后一个节点的next为NULL
}
申请新的节点
//申请新的节点
Node* buyNode(SListDataType x)
{Node* newnode = (Node*)malloc(sizeof(Node));//向堆区申请一个节点的空间if (newnode == NULL)//判断是否申请成功{perror("buyNode");exit(1);}//给新的节点赋值newnode->data = x;newnode->next = NULL;return newnode;//将新的节点返回
}
尾插push_back
//尾插
void push_back(Node** pph, SListDataType x)
{assert(pph);//防止pph为NULLNode* newnode = buyNode(x);//申请新的节点if (*pph == NULL)//空链表{*pph = newnode;//空链表直接插入新节点}else//非空链表{Node* tail = *pph;//tail是用来找单链表的尾节点while (tail->next)//用tail->next是否为NULL，判断是否找到了尾节点{tail = tail->next;//找下一个节点}tail->next = newnode;//跳出循环，此时tail指向尾节点，尾插}
}

test.c

	Node* phead = NULL;//测试尾插push_back(&phead, 1);print(&phead);push_back(&phead, 2);print(&phead);push_back(&phead, 3);print(&phead);push_back(&phead, 4);print(&phead);

在这里插入图片描述

头插push_front
//头插
void push_front(Node** pph, SListDataType x)
{assert(pph);//防止pph为NULLNode* newnode = buyNode(x);//申请新节点newnode->next = *pph;//新节点的下一个节点指向第一个节点*pph = newnode;//*pph指向新节点，完成头插
}

test.c

	//测试头插push_front(&phead, 5);print(&phead);push_front(&phead, 6);print(&phead);push_front(&phead, 7);print(&phead);//7 6 5

在这里插入图片描述

尾删pop_back
//尾删
void pop_back(Node** pph)
{assert(pph && *pph);//防止pph为NULL且单链表是一个空链表//链表中只有一个节点if ((*pph)->next == NULL){//释放第一个节点free(*pph);*pph = NULL;}//链表中有多个节点else{Node* ptail = *pph;//ptail负责找尾节点Node* pprev = *pph;//pprev负责找尾节点的前一个结点while (ptail->next)//判断ptail是否指向尾节点{pprev = ptail;//保存当前的ptailptail = ptail->next;//ptail继续找尾}//释放尾节点free(ptail);ptail = NULL;//尾节点的前一个节点的next指针需置空pprev->next = NULL;}
}

test.c

	//尾插push_back(&phead, 1);print(&phead);push_back(&phead, 2);print(&phead);push_back(&phead, 3);print(&phead);push_back(&phead, 4);//测试尾删pop_back(&phead);print(&phead);pop_back(&phead);print(&phead);pop_back(&phead);print(&phead);pop_back(&phead);print(&phead);pop_back(&phead);print(&phead);

在这里插入图片描述

第五次删除时链表已经为空，断言报错。

头删pop_front
//头删
void pop_front(Node** pph)
{assert(pph && *pph);//防止pph为NULL且单链表是一个空链表Node* next = (*pph)->next;//创建临时变量next保存第二个节点的地址free(*pph);//释放第一个节点*pph = next;//让*pph指向第二个节点，完成头删
}

test.c

	//尾插push_back(&phead, 1);print(&phead);push_back(&phead, 2);print(&phead);push_back(&phead, 3);print(&phead);push_back(&phead, 4);//测试头删pop_front(&phead);print(&phead);pop_front(&phead);print(&phead);pop_front(&phead);print(&phead);pop_front(&phead);print(&phead);pop_front(&phead);print(&phead);

在这里插入图片描述

第五次删除时链表已经为空，断言报错。

查找find
//查找指定节点的数据 - 找到返回节点，找不到返回NULL
Node* find(Node** pph, SListDataType x)
{assert(pph);//防止pph为NULLNode* pcur = *pph;//记录第一个节点的地址while (pcur)//遍历单链表{if (x == pcur->data)//找数据return pcur;//找到了，返回该数据对应的节点pcur = pcur->next;//找下一个节点}return NULL;//找不到，返回NULL
}

test.c

	//尾插push_back(&phead, 1);print(&phead);push_back(&phead, 2);print(&phead);push_back(&phead, 3);print(&phead);push_back(&phead, 4);//测试查找指定元素Node* f = find(&phead, 4);if (f == NULL)printf("找不到\n");elseprintf("找到了\n");

在这里插入图片描述

指定节点之前插入数据insert
//在指定节点之前插入数据
void insert(Node** pph, Node* pos, SListDataType x)
{//防止pph为NULL且单链表为空且pos为NULLassert(pph && *pph && pos);if (*pph == pos)//如果pos指向第一个节点，直接头插push_front(pph, x);else//pos不是第一个节点{Node* newnode = buyNode(x);//申请新节点Node* pprev = *pph;//记录第一个节点while (pprev->next != pos)//pprev指向的节点的下一个节点不是pos指向的节点，就跳出循环{pprev = pprev->next;/找下一个节点}newnode->next = pos;//让新的节点的next指针指向pos指向的节点pprev->next = newnode;//pprev指向的节点的next指针存放新节点的地址}}
test.c```c//尾插push_back(&phead, 1);print(&phead);push_back(&phead, 2);print(&phead);push_back(&phead, 3);print(&phead);push_back(&phead, 4);//测试在指定节点之前插入数据Node* f = find(&phead, 4);insert(&phead, f, 8);print(&phead);//1 2 3 8 4

在这里插入图片描述

指定节点之后插入数据insert_after
//在指定节点之后插入数据
void insert_after(Node* pos, SListDataType x)
{assert(pos);//防止pos为NULLNode* newnode = buyNode(x);//申请新节点//将newnode节点插在pos和pos->next节点之间newnode->next = pos->next;pos->next = newnode;
}

test.c

	//尾插push_back(&phead, 1);print(&phead);push_back(&phead, 2);print(&phead);push_back(&phead, 3);print(&phead);push_back(&phead, 4);//测试在指定节点之后插入数据Node* f = find(&phead, 4);insert_after(f, 9);print(&phead);//1 2 3 4 9

在这里插入图片描述

删除指定节点erase
//删除pos节点
void erase(Node** pph, Node* pos)
{//防止pph为NULL且单链表为空且pos为NULLassert(pph && *pph && pos);if (pos == *pph)//pos是第一个节点就头删pop_front(pph);else//pos不是第一个节点{Node* pprev = *pph;//记录第一个节点while (pprev->next != pos)//pprev指向的节点的下一个节点是pos指向的节点就跳出循环{pprev = pprev->next;//找下一个节点}pprev->next = pos->next;//pprev指向的节点的next指针存放pos的下一个节点的地址//释放要被删除的节点free(pos);pos = NULL;}
}

test.c

	//尾插push_back(&phead, 1);print(&phead);push_back(&phead, 2);print(&phead);push_back(&phead, 3);print(&phead);push_back(&phead, 4);//测试删除pos节点Node* f = find(&phead, 3);erase(&phead, f);print(&phead);//1 2 4

在这里插入图片描述

删除指定节点之后的节点erase_after
//删除pos之后的节点
void erase_after(Node* pos)
{assert(pos && pos->next);//防止pos为NULL且pos->next为NULLNode* del = pos->next;//保存要删除的节点pos->next = del->next;//让pos的next指针存放要删的节点的下一个节点free(del);//释放要删除的节点del = NULL;
}

test.c

	//尾插push_back(&phead, 1);print(&phead);push_back(&phead, 2);print(&phead);push_back(&phead, 3);print(&phead);push_back(&phead, 4);//测试删除pos之后的节点Node* f = find(&phead, 2);erase_after(f);print(&phead);//1 2 4

在这里插入图片描述

销毁单链表destroy
//销毁链表
void destroy(Node** pph)
{assert(pph && *pph);//防止pph为NULL且链表为空Node* pcur = *pph;//记录第一个节点while (pcur)//遍历单链表{Node* next = pcur->next;//保存当前节点的下一个节点free(pcur);//释放当前节点pcur = next;//让当前节点指向保存的节点}*pph = NULL;//*pph指向的第一个节点已经释放，最后给*pph置空
}

test.c

	//尾插push_back(&phead, 1);print(&phead);push_back(&phead, 2);print(&phead);push_back(&phead, 3);print(&phead);push_back(&phead, 4);//测试销毁链表destroy(&phead);print(&phead);

在这里插入图片描述

链表的分类

链表的结构非常多样，以下情况组合起来就有8种（2×2×2）链表结构：

在这里插入图片描述

链表说明：

在这里插入图片描述
虽然有这么多的链表的结构，但是我们实际中最常用的还是两种结构：单链表和双向链表

双向链表

概念与结构

在这里插入图片描述
带头链表中的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，值起“放哨”作用。

实现双向链表

在这里插入图片描述

List.h
#pragma once//双向链表的实现#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//双向链表节点的结构
typedef int LTDataType;
typedef struct ListNode
{int data;struct ListNode* prev;struct ListNode* next;
}LTNode;初始化
//void LTInit(LTNode** pphead);LTNode* LTInit();//尾插
void LTPushBack(LTNode* ph, LTDataType x);//打印
void LTPrint(LTNode* ph);//头插
void LTPushFront(LTNode* ph, LTDataType x);//尾删
void LTPopBack(LTNode* ph);//头删
void LTPopFront(LTNode* ph);//查找
LTNode* LTFind(LTNode* ph, LTDataType x);//在任意位置之前插入节点
void LTInsert(LTNode* pos, LTDataType x);//删除任意节点
void LTErase(LTNode* pos);销毁
//void LTDestroy(LTNode** pph);void LTDestroy(LTNode* ph);
List.c和test.c
申请新节点
//申请新节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//申请节点大小的空间if (newnode == NULL)//判断是否申请失败{perror("malloc fail!");exit(1);}newnode->data = x;//节点元素赋值newnode->next = newnode->prev = newnode;//循环链表，自己指向自己，成环return newnode;
}
初始化1
//初始化
void LTInit(LTNode** pph)
{assert(pph);//防止pph为NULL*pph = LTBuyNode(-1);//创建头节点,元素无效，赋值为-1
}

test.c

	LTNode* phead = NULL;LTInit(&phead);
初始化2(推荐)
LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);//申请头节点return phead;//返回头节点
}

test.c

	LTNode* phead = LTInit();//接收返回的头节点
打印
//打印
void LTPrint(LTNode* ph)
{assert(ph);//防止ph为NULLLTNode* pcur = ph->next;//pcur指向头节点的下一个节点while (pcur != ph)//遍历一趟{printf("%d->", pcur->data);//打印pcur = pcur->next;//找下一个节点}printf("\n");
}
尾插
//尾插
void LTPushBack(LTNode* ph, LTDataType x)
{assert(ph);//防止ph为NULLLTNode* newnode = LTBuyNode(x);//申请新节点//新节点的prev指针指向尾节点newnode->prev = ph->prev;//新节点的next指针指向头节点newnode->next = ph;//尾节点的next指针指向新节点ph->prev->next = newnode;//头节点的prev指针指向新节点ph->prev = newnode;
}

test.c

	LTNode* phead = LTInit();//测试尾插LTPushBack(phead, 1);LTPrint(phead);LTPushBack(phead, 2);LTPrint(phead);

在这里插入图片描述

头插
//头插
void LTPushFront(LTNode* ph, LTDataType x)
{assert(ph);//防止ph为NULLLTNode* newnode = LTBuyNode(x);//申请新节点//新节点的prev指针指向头节点newnode->prev = ph;//新节点的next指针指向第一个节点newnode->next = ph->next;//第一个节点的prev指针指向新节点ph->next->prev = newnode;//头节点的next指针指向新节点ph->next = newnode;
}

test.c

	//测试头插LTPushFront(phead, 3);LTPrint(phead);LTPushFront(phead, 4);LTPrint(phead);

在这里插入图片描述

尾删
//尾删
void LTPopBack(LTNode* ph)
{//防止ph为NULL且保证链表中有有效节点assert(ph && ph->next != ph);//保存要删除的尾节点LTNode* del = ph->prev;//头节点的prev指针指向倒数第二个节点ph->prev = del->prev;//倒数第二个节点的next指针指向头节点del->prev->next = ph;//释放尾节点free(del);del = NULL;
}

test.c

	//尾插LTPushBack(phead, 1);LTPrint(phead);LTPushBack(phead, 2);LTPrint(phead);//测试尾删LTPopBack(phead);LTPrint(phead);LTPopBack(phead);LTPrint(phead);LTPopBack(phead);LTPrint(phead);

在这里插入图片描述
第三次删除时链表中没有有效节点，所以断言报错。

头删
//头删
void LTPopFront(LTNode* ph)
{//防止ph为NULL且保证链表中有有效节点assert(ph && ph->next != ph);//保存要删除的第一个节点LTNode* del = ph->next;//头节点的next指针指向第二个节点ph->next = del->next;//第二个节点的prev指针指向头节点del->next->prev = ph;//释放要删除的第一个节点free(del);del = NULL;
}

test.c

	//尾插LTPushBack(phead, 1);LTPrint(phead);LTPushBack(phead, 2);LTPrint(phead);//测试头删LTPopFront(phead);LTPrint(phead);LTPopFront(phead);LTPrint(phead);LTPopFront(phead);LTPrint(phead);

在这里插入图片描述第三次删除时链表中没有有效节点，所以断言报错。

查找
//查找
LTNode* LTFind(LTNode* ph, LTDataType x)
{assert(ph);//防止ph为NULL//让pcur指向第一个节点LTNode* pcur = ph->next;while (pcur != ph)//遍历一遍链表{if (pcur->data == x)//找到返回该节点return pcur;pcur = pcur->next;//找下一个节点}return NULL;//找不到，返回NULL
}

test.c

	//尾插LTPushBack(phead, 1);LTPrint(phead);LTPushBack(phead, 2);LTPrint(phead);//测试查找LTNode* find = LTFind(phead, 2);if (find)printf("找到了\n");elseprintf("没找到\n");

在这里插入图片描述

任意位置之前插
//在任意位置之前插入节点
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);//防止pos为NULLLTNode* newnode = LTBuyNode(x);//申请新节点//新节点的prev指针指向pos的前一个节点newnode->prev = pos->prev;//新节点的next指针指向pos节点newnode->next = pos;//pos前一个节点的next指针指向新节点pos->prev->next = newnode;//pos的prev指针指向新节点pos->prev = newnode;
}

test.c

	//尾插LTPushBack(phead, 1);LTPrint(phead);LTPushBack(phead, 2);LTPrint(phead);//测试任意之前插LTNode* find = LTFind(phead, 2);LTInsert(find, 5);LTPrint(phead);

在这里插入图片描述

删除任意节点
//删除任意节点
void LTErase(LTNode* pos)
{assert(pos);//防止pos为NULL//pos的前一个结点的next指针指向pos的下一个节点pos->prev->next = pos->next;//pos的下一个节点的prev指针指向pos的前一个结点pos->next->prev = pos->prev;//释放pos节点free(pos);pos = NULL;
}

test.c

	//尾插LTPushBack(phead, 1);LTPrint(phead);LTPushBack(phead, 2);LTPrint(phead);//测试删任意节点LTNode* find = LTFind(phead, 2);LTErase(find);find = NULL;//删完之后find为野指针，需置空LTPrint(phead);

在这里插入图片描述

销毁1
//销毁
void LTDestroy(LTNode** pph)
{assert(pph);//防止pph为NULL//pcur指向第一个节点LTNode* pcur = (*pph)->next;while (pcur != *pph)//遍历一遍链表{LTNode* next = pcur->next;//next指向pcur的下一个节点free(pcur);//释放pcur节点pcur = next;//把pcur的下一个节点给pcur}free(*pph);//释放头节点*pph = NULL;
}

test.c

	//尾插LTPushBack(phead, 1);LTPrint(phead);LTPushBack(phead, 2);LTPrint(phead);//测试销毁LTDestroy(&phead);

在这里插入图片描述
出销毁，phead也为空，不会出现野指针情况。

销毁2（推荐）
void LTDestroy(LTNode* ph)
{assert(ph);LTNode* pcur = ph->next;while (pcur != ph){LTNode* next = pcur->next;free(pcur);pcur = next;}free(ph);ph = NULL;
}

test.c

	LTDestroy(phead);phead = NULL;

在这里插入图片描述
phead需手动置空

推荐销毁2的原因是：销毁1传的是二级指针，而其他的双向链表函数都是传的一级指针，
违反了接口一致性，对于销毁2，虽然需要手动置空，但既然我们已经销毁链表了，大概
率是不会再用phead了，所以推荐销毁2。
请添加图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/40148.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

性能测试、负载测试、压力测试的全面解析

性能测试、负载测试、压力测试的全面解析

在软件测试领域&#xff0c;性能测试、负载测试和压力测试是评估系统稳定性和可靠性的关键手段。​它们各自关注不同的测试目标和应用场景&#xff0c;理解这些差异对于制定有效的测试策略至关重要。 本文对性能测试、负载测试和压力测试进行深入分析&#xff0c;探讨其定义、…
阅读更多...
FPGA_YOLO(二)

FPGA_YOLO(二)

上述对cnn卷积神经网络进行介绍，接下来对YOLO进行总结，并研究下怎么在FPGA怎么实现的方案。 对于一个7*7*30的输出 拥有49个cell 每一个cell都有两个bbox两个框，并且两个框所包含的信息拥有30个 4个坐标信息和一个置信度5个，剩下就是20个类别。 FPGA关于YOLO的部署 1…
阅读更多...
Windows系统安装Node.js和npm教程【成功】

Windows系统安装Node.js和npm教程【成功】

0.引言——Node.js和npm介绍 项目描述Node.js基于Chrome V8引擎的JavaScript运行环境&#xff0c;使JavaScript可用于服务器端开发。采用单线程、非阻塞I/O及事件驱动架构&#xff0c;适用于构建Web服务器、实时应用和命令行工具等npmNode.js的包管理器与大型软件注册表。拥有…
阅读更多...
使用外部事件检测接入 CDH 大数据管理平台告警

使用外部事件检测接入 CDH 大数据管理平台告警

CDH 大数据管理平台 CDH&#xff08;Cloudera Distribution Hadoop&#xff09;是一个企业级的大数据平台&#xff0c;由 Cloudera 公司提供&#xff0c;它包含了 Apache Hadoop 生态系统中的多种开源组件&#xff0c;并对其进行了优化和集成&#xff0c;以支持大规模数据存储…
阅读更多...
Node.js的安装和环境配置

Node.js的安装和环境配置

漂亮女同事想了解Node.js的安装和环境配置。首先&#xff0c;我说需要回忆一下自己安装Node.js的经历&#xff0c;确保步骤是正确的。可能用户是刚接触开发的新手&#xff0c;所以需要详细但清晰的指导。 首先&#xff0c;应该介绍Node.js是什么&#xff0c;不过用户可能已经知…
阅读更多...
在普通用户下修改root用户密码

在普通用户下修改root用户密码

1 从普通用户切换到root用户 sudo -s 再输入密码。 2 输入passwd ,会提醒你输入当前用户密码&#xff0c;验证后会提醒你输入root用户密码。 3 切换到root用户&#xff0c;使用修改过的密码登陆。 4 成功进入root用户。
阅读更多...
【#2】介绍第三方库

【#2】介绍第三方库

一、JsonCpp 库 &#x1f525; JSONCPP 是一个开源的 C 库&#xff0c;用于解析和生成 JSON&#xff08;JavaScript Object Notation&#xff09;数据。它提供了简单易用的接口&#xff0c;支持 JSON 的序列化和反序列化操作&#xff0c;适用于处理配置文件、网络通信数据等场…
阅读更多...
Qt开发：QInputDialog的使用

Qt开发：QInputDialog的使用

文章目录 一、QInputDialog的介绍二、 QInputDialog的基本用法三、使用 QInputDialog的实例四、QInputDialog的信号与槽 一、QInputDialog的介绍 QInputDialog 是 Qt 提供的一个对话框类&#xff0c;用于获取用户输入的文本、整数或浮点数。它提供了简单易用的静态方法和可定制…
阅读更多...
SCI一区 | Matlab实现DBO-TCN-LSTM-Attention多变量时间序列预测

SCI一区 | Matlab实现DBO-TCN-LSTM-Attention多变量时间序列预测

SCI一区 | Matlab实现DBO-TCN-LSTM-Attention多变量时间序列预测 目录 SCI一区 | Matlab实现DBO-TCN-LSTM-Attention多变量时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.【SCI一区级】Matlab实现DBO-TCN-LSTM-Attention多变量时间序列预测&#xff08;程…
阅读更多...
Vulnhub-Thales通关攻略

Vulnhub-Thales通关攻略

第0步&#xff1a;网卡配置 靶机端&#xff1a;将下载好的靶机环境&#xff0c;导入 VritualBox&#xff0c;设置为 Host-Only 模式 Kali端&#xff1a;将 VMware 中桥接模式网卡设置为 VritualBox 的 Host-only 第一步&#xff1a;确定靶机IP #靶机IP 192.168.56.101#KaliIP 1…
阅读更多...
JVM 02

JVM 02

今天是2025/03/23 19:07 day 10 总路线请移步主页Java大纲相关文章 今天进行JVM 3,4 个模块的归纳 首先是JVM的相关内容概括的思维导图 3. 类加载机制 加载过程 加载&#xff08;Loading&#xff09; 通过类全限定名获取类的二进制字节流&#xff08;如从JAR包、网络、动态…
阅读更多...
Python学习笔记（7）关于列表创建，增加，删除

Python学习笔记（7）关于列表创建，增加，删除

列表 **Python中一切都是对象 存放多个值的连续内存空间 大小可变 增加元素 a a[50]#➕运算符操作&#xff0c;产生了新对象 list.append(x) #将元素x增加至list尾部 list.extend(alist) #将列表alist增加至list尾部 list.insert(index.x) #将元素x插入list指定index位置 …
阅读更多...
【图片识别Excel表格】批量将图片上的区域文字识别后保存为表格，基于WPF和阿里云的项目实战总结

【图片识别Excel表格】批量将图片上的区域文字识别后保存为表格，基于WPF和阿里云的项目实战总结

一、项目背景 在信息处理和文档管理中，经常会遇到需要从大量图片中提取文字并进行整理的场景。例如，财务部门需要从大量报销票据中提取金额、日期等信息；法务部门需要从合同文档中提取关键条款；教育行业需要从试卷中提取学生的答题内容等。传统的手工处理方式不仅耗时长、…
阅读更多...
【C语言】文件操作（详解）

【C语言】文件操作（详解）

个人主页 今天我们来讲一下有关文件的相关操作&#xff0c;希望看完这篇文章对你有所帮助&#xff0c;大力感谢你对博主的支持&#xff01; 文章目录 ⭐一、为什么使用文件&#x1f389;二、什么是文件2.1 程序文件2.2 数据文件2.3 文件名 &#x1f3a1;三、二进制文件和文本…
阅读更多...
数据库中不存在该字段

数据库中不存在该字段

mybatisplus 定义的类中某些字段是数据库里面没有的&#xff0c;我们可用tablefield(existfalse)来注解&#xff0c;演示如下&#xff1a;
阅读更多...
计算机组成原理———I\O系统精讲＜1＞

计算机组成原理———I\O系统精讲＜1＞

本篇文章主要介绍输入输出系统的发展概况 一.输入输出系统的发展概况 1.早期阶段 该阶段的特点是I/O设备与主存交换信息都必须通过CPU 当时的I/O设备有如下几个特点&#xff1a; &#xff08;1&#xff09;每个I\O设备都必须配有一套独立的逻辑电路与CPU相连&#xff0c;用来…
阅读更多...
Linux操作系统7- 线程同步与互斥7（RingQueue环形队列生产者消费者模型改进）

Linux操作系统7- 线程同步与互斥7（RingQueue环形队列生产者消费者模型改进）

上篇文章&#xff1a;Linux操作系统7- 线程同步与互斥6&#xff08;POSIX信号量与环形队列生产者消费者模型&#xff09;-CSDN博客 本篇代码仓库&#xff1a;myLerningCode/l36 橘子真甜/Linux操作系统与网络编程学习 - 码云 - 开源中国 (gitee.com) 目录 一. 单生产单消费单保…
阅读更多...
全面讲解python的uiautomation包

全面讲解python的uiautomation包

在常规的模拟鼠标和键盘操作&#xff0c;我们一般使用pyautogui&#xff0c;uiautomation模块不仅能直接支持这些操作&#xff0c;还能通过控件定位方式直接定位到目标控件的位置&#xff0c;而不需要自己去获取对应坐标位置。uiautomation模块不仅支持任意坐标位置截图&#x…
阅读更多...
图解CNN、RNN、LSTM

图解CNN、RNN、LSTM

一、CNN 二、RNN 三、LSTM 以上笔记参考自b站up主 自然卷小蛮&#xff08;自然卷小蛮的个人空间-自然卷小蛮个人主页-哔哩哔哩视频&#xff09;&#xff0c;感兴趣的可以去深入了解。
阅读更多...
3.25学习总结 抽象类和抽象方法+接口+内部类+API

3.25学习总结 抽象类和抽象方法+接口+内部类+API

抽象类和抽象方法&#xff1a; 有抽象方法&#xff0c;那么类肯定是抽象类。父类不一定是抽象的&#xff0c;但如果父类中有抽象方法那一定是抽象类。 如果子类中都存在吃这个行为&#xff0c;但吃的具体东西不同&#xff0c;那么吃这个行为定义在父类里面就是抽象方法&#x…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023