重庆网站排名推广,最好用的软件,重庆网站开发设计公司,9377传奇一、链表
1.1、什么是链表
1、链表是物理存储单元上非连续的、非顺序的存储结构#xff0c;数据元素的逻辑顺序是通过链表的指针地址实现#xff0c;有一系列结点#xff08;地址#xff09;组成#xff0c;结点可动态的生成。
2、结点包括两个部分#xff1a;#x…一、链表
1.1、什么是链表
1、链表是物理存储单元上非连续的、非顺序的存储结构数据元素的逻辑顺序是通过链表的指针地址实现有一系列结点地址组成结点可动态的生成。
2、结点包括两个部分1存储数据元素的数据域内存空间2存储指向下一个结点地址的指针域。
3、相对于线性表顺序结构操作复杂。
1.2、链表的分类
链表的结构非常多样以下的情况组合起来就有8种链表结构
1单项和双向 2带头和不带头 3循环和不循环 1.3、链表和顺序表的比较
1数组使用一块连续的内存空间地址去存放数据但
例如 int a[5]{1,2,3,4,5}。突然我想继续加两个数据进去但是已经定义好的数组不能往后加只能通过定义新的数组
int b[7]{1,2,3,4,5,6,7}; 这样就相当不方便比较浪费内存资源,对数据的增删不好操作。
2链表使用多个不连续的内存空间去存储数据 可以 节省内存资源只有需要存储数据时才去划分新的空间对数据的增删比较方便
注意
1.链式结构在逻辑上是连续的但在物理上不一定连续
2.现实中的结点一般都是从堆上申请出来的
3.从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续
二、无头单向非循环链表
2.1、无头单向非循环链表的结构 链表有一个数据域存放数据一个指针域存放下一个结点的地址。
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;
2.2、无头单向非循环链表的实现
//打印
void SLTPrint(SLTNode* phead);//创建一个新节点
SLTNode* BuySListNode(SLTDataType x);//尾增
void SLTPushBack(SLTNode** pphead, SLTDataType x);//头增
void SLTPushFront(SLTNode** pphead, SLTDataType x);//尾删
void SLTPopBack(SLTNode** pphead);//头删
void SLTPopFront(SLTNode** pphead);// 作业
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);// 删除pos的后一个位置
void SLTPopAfter(SLTNode* pos);// 单链表的销毁
void SListDestroy(SLTNode** pphead);
2.2.1、创建一个新节点
SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc);exit(-1);}newnode-data x;newnode-next NULL;return newnode;
}
创建一个新节点用malloc开辟一个链表节点空间强制转换成链表结构体将data置为X将next置为空并返回新节点。
2.2.2、单链表的尾插
//单链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode BuySListNode(x);//没有一个节点if (*pphead NULL){*pphead newnode;}else{SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}
单链表的尾插首先需要判断是否是空链表如果为空就把该节点置为头节点若不为空先便利找到尾结点然后将新节点插入尾节点后面。
2.2.3、单链表的头插法
//单链表的头插法 效率高简单
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;
}
头插法相对简单只需要将新节点插到头结点的前面并且将头结点指针赋给新节点。 2.2.4、单链表的尾删
//单链表的尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//空assert(*pphead);// 1个节点if ((*pphead)-next NULL){free((*pphead));*pphead NULL;}else //两个或者多个节点{ //方法一 /*SLTNode* tail *pphead;while (tail-next-next){tail tail-next;}free(tail-next);tail-next NULL;*///方法二SLTNode* tail *pphead;SLTNode* tailprev NULL;while (tail-next){tailprev tail;tail tail-next;}free(tail);tail NULL;tailprev-next NULL;}
}
和尾插法一样首先先判断链表是否只有一个节点或者没有节点为空将会最后一个链表置空如果超过一个节点先找到倒数第二个节点然后置空最后一个节点将倒数第二个节点的next置空
2.2.5、单链表的头删法
//链表的头删法 效率高简单
void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* newnode (*pphead)-next;free(*pphead);*pphead newnode;
}
free第一个节点将头指针后移一位。
2.2.6、单链表的查找
//查找元素 修改
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur phead;while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;
}
借助cur指针便利链表curcur-next;若cur-datax,返回cur,没找到返回NULL。
2.2.7、在pos之前插入
//在pos之前插入
// 传头指针是因为有可能时头插
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pos);if (pos *pphead){SLTNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLTNode* newnode BuySListNode(x);prev-next newnode;newnode-next pos;}
}
在pos位置插入相对
2.2.8、在pos之后插入
//在pos之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode BuySListNode(x);newnode-next pos-next;pos-nextnewnode;}
2.2.9、删除pos位置
//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);if (pos *pphead){SLTPopFront(pphead);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);//pos NULL; //可有可无因为pos只是形参对他的操作不影响外部的节点}
}
2.2.10、删除pos后一位置
//删除pos后一位置
void SLTPopAfter(SLTNode* pos)
{assert(pos);assert(pos-next NULL);SLTNode* posnext pos-next;pos-next posnext-next;free(posnext);posnext NULL;
}
//删除一个pos,没有头节点
// 把pos下一个节点的值赋给pos,将下一个节点删除
//但是无法删除尾结点
2.2.11、单链表的销毁
//单链表的销毁
void SListDestroy(SLTNode** pphead)
{assert(*pphead);SLTNode* pre *pphead;SLTNode* p pre-next;while (p!NULL){free(pre);pre p;p p-next;}free(pre-next);pre-next NULL;
}
三、带头双向循环链表
双向链表的原理与单链表类似双向链表需要两个指针来链接一个指向前面的一个指向后面的。同时需要一个head头链表方便操作。 3.1带头双向链表实现
3.1.1、创建结构体
typedef int DataType;
typedef struct ListNode
{struct ListNode *next;struct ListNode *pre;DataType data;
}LTNode;
此结构中比单链表结构增加一个结构体指针pre用于存放上一个节点的地址。 next是存放一个节点的地址。 data是存放数据。
3.1.2、申请结点
LTNode* BuyListNode(DataType x)//申请结点
{LTNode* node (LTNode*)malloc(sizeof(LTNode));if (node NULL){perror( malloc fail);exit(-1);}node-next NULL;node-pre NULL;node-data x;return node;
}动态申请结点函数返回的是一个指针类型用malloc开辟一个LTNode大小的空间并用node指向这个空间再判断是否为空如为空就perror显示错误信息。反之则把要存的数据x存到newnode指向的空间里面把指针置为空。
3.1.3、初始化创建头结点
LTNode* LTInit()//初始化创建头结点
{LTNode* phead BuyListNode(0);phead-next phead;phead-pre phead;return phead;
}单链表开始是没有节点的可以定义一个指向空指针的结点指针但是此链表不同需要在初始化函数中创建个头结点它不用存储有效数据。因为链表是循环的在最开始需要让头结点的next和pre指向头结点自己。 因为其他函数也不需要用二级指针因为头结点指针是不会变的变的是next和pre改变的是结构体只需要用结构体针即可也就是一级指针为了保持一致此函数也不用二级指针把返回类型设置为结构体指针类型。
3.1.4、打印链表
void LTPrint(LTNode* phead)//打印链表
{assert(phead);LTNode* cur phead-next;while (cur!phead){printf(%d , cur-data);cur cur-next;}printf(\n);
}
打印链表先断言phead它不能为空再把头结点下个地址存到cur中用while循环去遍历终止条件是等于头指针停止因为他是循环的并更新cur。
3.1.5、在pos位置之前插入
void LTInsert(LTNode* pos, DataType x)//在pos位置之前插入数据
{assert(pos);LTNode* node BuyListNode(x);LTNode* bef pos-pre;bef-next node;node-pre bef;node-next pos;pos-pre node;
}断言pos不能为空插入数据先申请一结点放到定义的node指针变量中为了不用考虑插入顺序先把pos前面的存到bef中然后就可以随意链接 bef指向新节点新节点前驱指针指向bef新节点指向pospos前驱指针指向新节点。
3.1.6、删除任意位置数据
void LTErase(LTNode* pos)//删除pos位置数据
{assert(pos);pos-pre-next pos-next;pos-next-pre pos-pre;free(pos);
}删除把pos位置之前的结点直接指向pos的下一个结点把pos下一个结点的前驱指针指向pos之前的结点。
3.1.7、尾插
void LTPushBack(LTNode* phead, DataType x)//尾插
{/*assert(phead);//复杂方法/*LTNode* newnode BuyListNode(x);LTNode* tail phead-prev;tail-next newnode;newnode-prev tail;newnode-next phead;phead-prev newnode;*/assert(phead);//简便方法LTInsert(phead, x);
}简便方法尾插是在尾部插入用简便方法调用LTInsert函数传入头指针和x。
复杂方法是申请结点newnode把头指针前的上一个结点存到尾指针变量中再双向链接newnode最后还得把头和尾刚申请的结点循环起来。
3.1.8、尾删
void LTPopBack(LTNode* phead)//尾删
{//assert(phead);//复杂方法//assert(phead-next ! phead); // 空//LTNode* tail phead-prev;//LTNode* tailPrev tail-prev;//tailPrev-next phead;//phead-prev tailPrev;//free(tail);assert(phead);//简便方法assert(phead-next ! phead); // 空LTErase(phead-pre);
}
简便方法因为是尾删删的是尾部直接调用LTErase函数传入头指针的上一个结点也就是尾部因为是双向循环不用遍历直接直到尾部。
复杂方法先把头结点上一个结点地址存起来再把尾部的上一个结点地址存起来再把第二次存的直接链接头部头部链接第二次存的结点再把第一次的结点释放掉。
3.1.9、头插
void LTPushFront(LTNode* phead, DataType x)//头插
{//assert(phead);//复杂方法//LTNode* newnode BuyListNode(x);//LTNode* back phead-next;//phead-next newnode;//newnode-prev phead;//newnode-next back;//back-prev newnode;assert(phead);//简便方法LTInsert(phead-next, x);
}
简便方法因为是头插直接调用LTInsert函数传 头结点下一个结点指针和x。
复杂方法申请结点存到newnode再把头结点下一个结点地址存到指针back里头部和新节点和back三节点双向链接。
3.1.10、头删
void LTPopFront(LTNode* phead)//头删
{//assert(phead);//assert(phead-next ! phead); // 空/*LTNode* back phead-next;LTNode* second back-next;free(back);phead-next second;second-prev phead;*/assert(phead);assert(phead-next ! phead); // 空LTErase(phead-next);}
简便方法因为头删直接调LTErase函数传入头结点下一个指针。
复杂方法先把头结点下一个结点地址存到back指针里再把back一个结点地址存到second指针里先释放中间的back最后头结点和second双向链接。
3.1.11、查找元素
LTNode* LTFind(LTNode* phead, DataType x)//查找
{assert(phead);LTNode* cur phead-next;while (cur!phead){if (cur-data x){return cur;}cur cur-next;}return NULL;}查找把头结点下一个结点存到cur然后用while循环遍历终止条件是cur等于头结点指针如果cur等于x直接返回cur指针再更新cur最后遍历完返回NULL表示没有该数据。
3.1.12、释放链表
void LTDestroy(LTNode* phead)//释放链表
{assert(phead);LTNode* cur phead-next;while (cur ! phead){LTNode* next cur-next;free(cur);cur next;}free(phead);
}释放链表从头开始释放把头结点下一个结点存到cur中再用用while循环终止条件是cur不等于头指针在里面把cur下一个指针存到next中释放掉cur再把next更新为cur。 最后头结点也是申请的也得释放。
3.1.13、判断是否为空
bool LTEmpty(LTNode* phead)//判断是否为空
{assert(phead);return phead-next phead;
}
3.1.14、求链表长度
size_t LTSize(LTNode* phead)//求链表长度
{assert(phead);size_t size 0;LTNode* cur phead-next;while (cur ! phead){size;cur cur-next;}return size;
}求链表长度先把头结点下一个结点存到cur中再用while循环遍历终止条件是cur等于头结点用size记录长度并更新cur最后返回size32位机器下是无符号整型size_t。
到这里链表的基本问题就解释完了相信多多少少会解决大家心头的疑问在数据结构的学习中应当善于思考多画图死磕代码注意细节将伪代码转换为代码这样才能很好的掌握数据结构的有关知识共勉加油
