那种投票网站里面怎么做,国外seo查询,加强社区网站建设,政务网站建设的功能模块欢迎光顾我的homepage
前言 链表和顺序表都是线性表的一种#xff0c;但是顺序表在物理结构和逻辑结构上都是连续的#xff0c;但链表在逻辑结构上是连续的#xff0c;而在物理结构上不一定连续#xff1b;来看以下图片来认识链表与顺序表的差别
这里以动态顺序表… 欢迎光顾我的homepage
前言 链表和顺序表都是线性表的一种但是顺序表在物理结构和逻辑结构上都是连续的但链表在逻辑结构上是连续的而在物理结构上不一定连续来看以下图片来认识链表与顺序表的差别
这里以动态顺序表为例和链表中的单链表对比一下
动态顺序表
单链表 这里就可以很清晰的看到顺序表的底层其实就是一个数组数据的是连续存储的顺序表物理结构连续而链表它每一个数据都不是连续的链表物理结构上不一定连续。
链表节点 通过观察上图我们会发现链表每一个节点都存放在数据和下一个节点的地址。 那么来想一下为了链表每一个节点都统一起来都存储有效数据和下一个节点的地址我们就需要创建应该结构体来存储有效数据和下一个节点的指针注这里只是单链表
typedef int SLType;
typedef struct SLTNode
{SLType data;struct SLTNode* next;
}SLT;
创建好链表节点接下来就来实习单链表存储数据的这些功能。
单链表实现
先来看一下单链表都实现都哪些功能
//输出链表
void SLTPrint(SLT* phead);
//创建节点
SLT* SLTCreat(SLType x);
//单链表头插
void SLTPushFront(SLT** pphead, SLType x);
//单链表尾插
void SLTPushBack(SLT** pphead, SLType x);
//单链表头删
void SLTPopFront(SLT** pphead);
//单链表尾删
void SLTPopBack(SLT** pphead);
//查找数据
SLT* SLTFind(SLT* phead, SLType x);
//指定位置之前插入
void SLTInsert(SLT** pphead, SLT* pos, SLType x);
//指定位置之后插入
void SLTInsertAfter(SLT* pos, SLType x);
//删除指定节点
void SLTErase(SLT** pphead, SLT* pos);
//删除指定位置后一个节点
void SLTEraseAfter(SLT* pos);
创建节点 这里创建节点还是使用动态内存来创建创建完成后将数据存储进去并把新节点的下一个节点置为NULL
代码如下
//创建节点
SLT* SLTCreat(SLType x)
{SLT* newnode (SLT*)malloc(sizeof(SLT));assert(newnode);newnode-data x;newnode-next NULL;return newnode;
} 测试一下代码是否正确 可以看到代码没有问题。
输出链表 由于这里实现单链表存储的是整型数据就以整型的方式输出若存储其他类型的数据就以存储类型的方式输出。
输出链表首先就要遍历链表因为链表最后一个节点里存储的下一个节点的地址为空即最后一个节点 -next 为空所以遍历链表结束的条件就是ptail NULL没输出一个就让ptail指向下一个节点直到为空遍历结束。 来写代码实现
//输出链表
void SLTPrint(SLT* phead)
{SLT* ptail phead;while (ptail! NULL)//也可以直接写成 ptail{printf(%d - , ptail-data);ptail ptail-next;}printf(NULL\n);
}
这里先创建两个节点并存储数据输出看一下结果
int main()
{SLT* plist SLTCreat(1);plist-next SLTCreat(2);SLTPrint(plist);return 0;
} 这里也成功输出插入的两个数据。最后一个节点的next指向空
单链表头插 在链表头部插入数据不用像顺序表那样去移动所以的有效数据链表只需要改变一个指针的指向即可 假设现在链表中已经存在两个数据再进行头插这时就只需要改变plist的指向即可当然新节点的next指针也要指向下一个节点(plist指向的节点)。
代码如下
//单链表头插
void SLTPushFront(SLT** pphead, SLType x)
{assert(pphead);SLT* newnode SLTCreat(x);newnode-next *pphead;*pphead newnode;
}
还有一种情况如果现在链表中没有数据再进行头插这里代码也能实现链表没有数据时的头插
单链表尾插 链表的尾插因为指针传的是指向头节点的指针的地址所以我们需要先遍历链表找到链表的尾部再修改尾节点的next指针指向。
假设现在链表中已经存在两个数据再进行尾插此时我们只需要找到链表的尾部修改尾节点next指针指向即可代码如下
//单链表尾插
void SLTPushBack(SLT** pphead, SLType x)
{assert(pphead);SLT* newnode SLTCreat(x);SLT* ptail *pphead;//遍历链表while (ptail-next){ptail ptail-next;}ptail-next newnode;
} 考虑了这种情况再来看以下链表为空的情况如果链表为空这里ptail-next就对空指针进行解引用操作了所以我们需要判断链表是否为空如果为空插入的新节点就是头节点直接让plist即*pphead)指向新节点即可如果不为空就正常进行尾插。
最终代码如下
//单链表尾插
void SLTPushBack(SLT** pphead, SLType x)
{ assert(pphead);SLT* newnode SLTCreat(x);if (*pphead NULL) //判断链表是否为空{*pphead newnode;}else {SLT* ptail *pphead;//遍历链表while (ptail-next){ptail ptail-next;}ptail-next newnode;}
} 这里代码可以正常进行尾插。
单链表头删 链表头删首先我们要判断链表是否为空如果为空空链表没有数据该如何删除呢
链表头删我们需要修改plist*pphead指向链表的下一个节点即头节点的next指针。 此外因为我们的节点都是动态申请的内存所以在删除时需要把它释放掉。
思路很简单写一下代码
//单链表头删
void SLTPopFront(SLT** pphead)
{assert(pphead *pphead);SLT* del (*pphead);*pphead (*pphead)-next;free(del);del NULL;
} 再来看一个如果链表为空又是啥结果呢
现在链表已经为空在执行一次头删代码
这里assert断言报错。
单链表尾删 首先尾删与头删一样链表不能为空。 尾删与尾插也有共同之处就是遍历链表找到链表的尾节点。找到尾节点删除尾节点然后修改尾节点上一个节点的next指针为NULL所以在遍历链表时就要多记录一个节点。
//单链表尾删
void SLTPopBack(SLT** pphead)
{assert(pphead *pphead);SLT* ptail *pphead;SLT* pcur *pphead;//遍历链表while (ptail-next){pcur ptail;ptail ptail-next;}pcur-next NULL;free(ptail);ptail NULL;
} 在测试的时候我们会发现一个问题如果链表只有一个节点删除之后我们的plist指针并没有置为空而我们的空间已经释放掉了这是很危险的所以这里我们先判断一下链表是否只有一个节点如果是我们释放完空间以后将(*pphead)置为空以免出现野指针的情况。
完善后代码
//单链表尾删
void SLTPopBack(SLT** pphead)
{assert(pphead *pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else {SLT* ptail *pphead;SLT* pcur *pphead;//遍历链表while (ptail-next){pcur ptail;ptail ptail-next;}free(ptail);ptail NULL;pcur-next NULL;}
} 测试没有问题代码能够完成尾删这个功能。
查找数据 查找数据遍历链表查找数据如果找到就返回数据所在节点的地址如果没有找到就返回NULL;
//查找数据
SLT* SLTFind(SLT* phead, SLType x)
{SLT* ptail phead;while (ptail){if (ptail-data x){return ptail;}ptail ptail-next;}return NULL;
}
这里测试以下
数据存在时
数据不存在时
指定节点之前插入 在链表指定节点之前插入数据我们还需要知道指定节点的前一个节点所以仍然需要遍历链表寻找指定节点pos前一个节点。
//指定位置之前插入
void SLTInsert(SLT** pphead, SLT* pos, SLType x)
{assert(pphead *pphead);SLT* ptail *pphead;if (ptail pos)//头插{SLTPushFront(pphead, x);}else{SLT* newnode SLTCreat(x);while (ptail-next ! pos)//找到pos位置{ptail ptail-next;}newnode-next pos;ptail-next newnode;}
} 当然这里如果故意传NULL给pos这就没啥意义了这里也可以写以下assert断言pos。
指定节点之后插入 在指定节点之后插入数据就不需要再进行遍历链表这里直接插入即可。
//指定位置之后插入
void SLTInsertAfter(SLT* pos, SLType x)
{assert(pos);SLT* newnode SLTCreat(x);newnode-next pos-next;pos-next newnode;
} 删除指定节点 删除链表中的指定节点我们需要这个节点的上一个节点所以又需要遍历链表找到pos上一个节点修改pos-next指针指向。
代码如下
//删除指定节点
void SLTErase(SLT** pphead, SLT* pos)
{//找到pos上一个节点SLT* ptail *pphead;while (ptail-next ! pos){ptail ptail-next;}SLT* p pos-next;free(pos);pos NULL;ptail-next p;
} 删除指定节点后一个节点 删除链表指定节点后一个节点因为pos就是删除节点的上一个节点所以不需要遍历链表直接删除即可。
//删除指定位置后一个节点
void SLTEraseAfter(SLT* pos)
{assert(pos-next);SLT* del pos-next;pos-next pos-next-next;free(del);del NULL;
} 这里如果传过来的就是链表的尾节点那删除后一个节点所以断言pos-next
代码总览
#includeSList.h
//创建节点
SLT* SLTCreat(SLType x)
{SLT* newnode (SLT*)malloc(sizeof(SLT));assert(newnode);newnode-data x;newnode-next NULL;return newnode;
}
//输出链表
void SLTPrint(SLT* phead)
{SLT* ptail phead;while (ptail ! NULL)//也可以直接写成 ptail{printf(%d - , ptail-data);ptail ptail-next;}printf(NULL\n);
}
//单链表头插
void SLTPushFront(SLT** pphead, SLType x)
{assert(pphead);SLT* newnode SLTCreat(x);newnode-next *pphead;*pphead newnode;
}
//单链表尾插
void SLTPushBack(SLT** pphead, SLType x)
{ assert(pphead);SLT* newnode SLTCreat(x);if (*pphead NULL) //判断链表是否为空{*pphead newnode;}else {SLT* ptail *pphead;//遍历链表while (ptail-next){ptail ptail-next;}ptail-next newnode;}
}
//单链表头删
void SLTPopFront(SLT** pphead)
{assert(pphead *pphead);SLT* del (*pphead);*pphead (*pphead)-next;free(del);del NULL;
}
//单链表尾删
void SLTPopBack(SLT** pphead)
{assert(pphead *pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else {SLT* ptail *pphead;SLT* pcur *pphead;//遍历链表while (ptail-next){pcur ptail;ptail ptail-next;}free(ptail);ptail NULL;pcur-next NULL;}
}
//查找数据
SLT* SLTFind(SLT* phead, SLType x)
{SLT* ptail phead;while (ptail){if (ptail-data x){return ptail;}ptail ptail-next;}return NULL;
}
//指定位置之前插入
void SLTInsert(SLT** pphead, SLT* pos, SLType x)
{assert(pphead *pphead);SLT* ptail *pphead;if (ptail pos)//头插{SLTPushFront(pphead, x);}else{SLT* newnode SLTCreat(x);while (ptail-next ! pos)//找到pos位置{ptail ptail-next;}newnode-next pos;ptail-next newnode;}
}
//指定位置之后插入
void SLTInsertAfter(SLT* pos, SLType x)
{assert(pos);SLT* newnode SLTCreat(x);newnode-next pos-next;pos-next newnode;
}
//删除指定节点
void SLTErase(SLT** pphead, SLT* pos)
{//找到pos上一个节点SLT* ptail *pphead;while (ptail-next ! pos){ptail ptail-next;}SLT* p pos-next;free(pos);pos NULL;ptail-next p;
}
//删除指定位置后一个节点
void SLTEraseAfter(SLT* pos)
{assert(pos-next);SLT* del pos-next;pos-next pos-next-next;free(del);del NULL;
}
感谢各位大佬支持并指出问题
如果本篇内容对你有帮助可以一键三连支持以下感谢支持
