1 单链表
1.1 概念与结构
概念: 链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构,数据元素的逻辑顺序是通过链表中的 指针链接次序实现的 。单链表就如同火车一样去掉或加上车厢不会影响到其他的车厢那么在链表中,每节车厢是什么样子的呢?如图下: 1.1.1 结点 与顺序表不同的是,链表⾥的每节"⻋厢"都是独⽴申请下来的空间,我们称之为“结点/结点” 结点的组成主要有两个部分:当前结点要保存的数据和保存下⼀个结点的地址(指针变量) 。 图中指针变量 plist保存的是第⼀个结点的地址,我们称plist此时“指向”第⼀个结点,如果我们希望 plist“指向”第⼆个结点时,只需要修改plist保存的内容为0x0012FFA0。 链表中每个结点都是独⽴申请的(即需要插⼊数据时才去申请⼀块结点的空间),我们需要通过指针 变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。 1.1.2 链表的性质 1、 链式机构在逻辑上是连续的,在物理结构上不⼀定连续 2、 结点⼀般是从堆上申请的 3、 从堆上申请来的空间,是按照⼀定策略分配出来的,每次申请的空间可能连续,可能不连续 结合前⾯学到的结构体知识,我们可以给出每个结点对应的结构体代码: // 定义一个结构体链表 ypedef struct SlsitNode {SLDatetype data; //结点数据
struct SlsitNode* next; //指针变量⽤保存下⼀个结点的地址
}Slist; / /申请新的结点
Slist* SLTbuycode(SLDatetype x)
{
Slist* node = (Slist*)malloc(sizeof(Slist));
if (node == NULL)
{
perror("malloc fail");
exit(1);
}
node->data = x;
node->next = NULL;
return node;
} 首先来实现单链表的尾插 void Insertback(Slist **phead,SLDatetype x)
{
assert(phead);
Slist* newcode = SLTbuycode(x);
if (*phead == NULL)
{
*phead = newcode;
}
else
{
Slist* Sltail = *phead;
while (Sltail->next)
{
Sltail = Sltail->next;
}
Sltail->next = newcode;
newcode->next = NULL;
}
} 进入函数首先先判断是否为空,然后去申请一个新的结点空间,如果头节点为空的话就让我们申请的结点变成头节点,如果不为空就去遍历结点找到最后一个结点让最后结点的next指向我们申请的新的结点,然后让我们申请新的结点的next赋值为空 实现单链表的头插 void Inserthead(Slist** phead, SLDatetype x)
{
assert(phead);
Slist* newcode = SLTbuycode(x);
newcode->next = *phead;
*phead = newcode;
} 首先判断传来的是否为空,然后申请一个新的结点赋值给newcode,让newcode->next指向*phead,然后在把phead变成头节点 //链表打印 void Sltprintf(Slist* phead) {
Slist* p = phead;
while (p != NULL)
{
printf("%d->", p->data);
p = p->next;
}
printf("NULL");
printf("\n");
} 因为不需要改变结点的值只需要遍历数组,所以只需要用形参就行,先创建一个新的结点指向头节点以防改变头节点的位置,然后判断是否为空不为空就一直遍历让p一直指向后面的结点然后输出 //尾删 void popback(Slist** phead)
{
assert(phead&&*phead);
Slist* sltail = *phead;
if ((*phead)->next == NULL)
{
free(*phead);
*phead = NULL;
}
Slist* pre = NULL;
while (sltail->next)
{
pre = sltail;
sltail = sltail->next;
}
pre->next = NULL;
free(sltail);
sltail = NULL;
} 要想删除结点就要结点不能为空,定义一个新的指针指向头节点如果要删除只有一个结点那就直接释放然后把头节点指向空,如果不是就在定义一个指针指向空然后去遍历一直找到最后结点的前一个结点让前一个结点的next直接指向空然后去释放最后一个结点。 //头删
void pophead(Slist** phead)
{
assert(phead && *phead);
Slist* p = (*phead)->next;
free(*phead);
*phead =p;
} 要把头节点的next赋给新定义的结点然后去释放头节点,最后在重新让phead指向新的结点。 //查找数据
Slist* sltfind(Slist* phead, SLDatetype x)
{
Slist* prer = phead;
while (prer!=NULL)
{
if (prer->data == x)
{
return prer;
}
prer = prer->next;
}
return NULL;
} 因为查找只需要遍历数组只需要穿形式参数不需要改变值,首先定义一个让他指向头结点然后去遍历数组如果找到了就返回这个结点如果没有找到就返回NULL; //指定位置前插入
void SLtInsert(Slist** phead, Slist* pos, SLDatetype x)
{
assert(phead && pos);
if (*phead== pos)
{
Inserthead(phead, x);
}
else {
Slist* newcode = SLTbuycode(x);
Slist* pre = *phead;
while (pre->next != pos)
{
pre = pre->next;
}
newcode->next = pos;
pre->next = newcode;
}
} 如果要在头结点前插入数据就相当于头插可以调用一下头插函数,然后不是就去申请一个空间然后一直遍历让他找到pos的前一个结点然后让新结点的next指向pos,然后在让pre的next指向newcode; //在指定位置后插入数据
void SLtInsertback(Slist* pos, SLDatetype x)
{
assert(pos);
Slist* newcode = SLTbuycode(x);
newcode->next=pos->next;
pos->next = newcode;
} 首先要让申请的新结点的next指向pos的next然后在把pos的next指向新结点这; //在指点位置前删除数据
void sltdelet(Slist** phead, Slist* posr)
{
assert(phead && posr);
if (posr == *phead)
{
pophead(phead);
}
Slist* pre = *phead;
while (pre->next != posr)
{
pre = pre->next;
}
pre->next = posr->next;
free(posr);
posr = NULL;
} 如果指定的位置时头结点就相当于头删除直接调用头删函数就行,如果不是头结点就定义一个结构体的指针指向头结点然后一直遍历到指定位置的前一个结点把指定位置的next赋值给pre的next最后释放posr。 //在指定结点之后删除
void sltdeletback(Slist* pos)
{
assert(pos&&pos->next);
Slist* del = pos->next;
pos->next = del->next;
free(del);
} 这里也比较简单只需要得知pos指向的下一个结点的下一个地址就简单了; //单链表的释放 void sltdestory(Slist** phead)
{
Slist* pre = *phead;
while (pre)
{
Slist* node = pre->next;
free(pre);
pre = node;
}
*phead = NULL;
} 轮流释放每一个结点然后让释放前把结点的next存到一个新的结构体指针里面然后去释放单链表 下面时三个部分的代码 Sqlist.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDatetype;
typedef struct SlsitNode {
SLDatetype data;
struct SlsitNode* next;
}Slist;
//尾插
void Insertback(Slist *phead, SLDatetype x);
//打印
void Sltprintf(Slist* phead);
//头插
void Inserthead(Slist** phead, SLDatetype x);
//尾删
void popback(Slist** phead);
//头删
void pophead(Slist** phead);
//查找
Slist* sltfind(Slist* phead, SLDatetype x);
//在指定之前插入数据
void SLtInsert(Slist** phead,Slist *pos ,SLDatetype x);
//在指定之后插入数据
void SLtInsertback( Slist* pos, SLDatetype x);
//在指定之前删除数据
void sltdelet(Slist** phead, Slist* pos);
//在指定之后删除数据
void sltdeletback(Slist* pos);
//单链表的销毁
void sltdestory(Slist **phead);
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Sqlist.h"
void test()
{
/*Slist* node1 = (SLDatetype*)malloc(sizeof(Slist));
Slist* node2 = (SLDatetype*)malloc(sizeof(Slist));
Slist* node3 = (SLDatetype*)malloc(sizeof(Slist));
Slist* node4 = (SLDatetype*)malloc(sizeof(Slist));
node1->data = 1;
node2->data = 2;
node3->data = 3;
node4->data = 4;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;*/
Slist* plist = NULL;
Insertback(&plist ,1);
Insertback(&plist, 2 );
Insertback(&plist, 3);
Sltprintf(plist);
/* Inserthead(&plist, 1);
Sltprintf(plist);
Inserthead(&plist, 2);
Sltprintf(plist);*/
/*Inserthead(&plist, 3);*/
/*popback(&plist);*/
/*Sltprintf(plist);*/
Slist* find = sltfind(plist,1);
/*if (find==NULL)
{
printf("没找到");
}
else
{
printf("找到了");
}*/
/*SLtInsert(&plist, find, 99);
Sltprintf(plist);*/
SLtInsertback(find,99);
Sltprintf(plist);
/* sltdelet(&plist,find);
Sltprintf(plist);*/
/* sltdeletback(find);*/
/*Sltprintf(plist);*/
/*sltdestory(&plist);*/
}
int main()
{
test();
}
sllist.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Sqlist.h"
//打印
void Sltprintf(Slist* phead) {
Slist* p = phead;
while (p != NULL)
{
printf("%d->", p->data);
p = p->next;
}
printf("NULL");
printf("\n");
}
//申请新的结点
Slist* SLTbuycode(SLDatetype x)
{
Slist* node = (Slist*)malloc(sizeof(Slist));
if (node == NULL)
{
perror("malloc fail");
exit(1);
}
node->data = x;
node->next = NULL;
return node;
}
//尾插
void Insertback(Slist **phead,SLDatetype x)
{
assert(phead);
Slist* newcode = SLTbuycode(x);
if (*phead == NULL)
{
*phead = newcode;
}
else
{
Slist* Sltail = *phead;
while (Sltail->next)
{
Sltail = Sltail->next;
}
Sltail->next = newcode;
newcode->next = NULL;
}
}
//头插
void Inserthead(Slist** phead, SLDatetype x)
{
assert(phead);
Slist* newcode = SLTbuycode(x);
newcode->next = *phead;
*phead = newcode;
}
//尾删
void popback(Slist** phead)
{
assert(phead&&*phead);
Slist* sltail = *phead;
if ((*phead)->next == NULL)
{
free(*phead);
*phead = NULL;
}
Slist* pre = NULL;
while (sltail->next)
{
pre = sltail;
sltail = sltail->next;
}
pre->next = NULL;
free(sltail);
sltail = NULL;
}
//头删
void pophead(Slist** phead)
{
assert(phead && *phead);
Slist* p = (*phead)->next;
free(*phead);
*phead =p;
}
//查找数据
Slist* sltfind(Slist* phead, SLDatetype x)
{
Slist* prer = phead;
while (prer!=NULL)
{
if (prer->data == x)
{
return prer;
}
prer = prer->next;
}
return NULL;
}
//指定位置前插入
void SLtInsert(Slist** phead, Slist* pos, SLDatetype x)
{
assert(phead && pos);
if (*phead== pos)
{
Inserthead(phead, x);
}
else {
Slist* newcode = SLTbuycode(x);
Slist* pre = *phead;
while (pre->next != pos)
{
pre = pre->next;
}
newcode->next = pos;
pre->next = newcode;
}
}
//在指定位置后插入数据
void SLtInsertback(Slist* pos, SLDatetype x)
{
assert(pos);
Slist* newcode = SLTbuycode(x);
newcode->next=pos->next;
pos->next = newcode;
}
//在指点位置前删除数据
void sltdelet(Slist** phead, Slist* posr)
{
assert(phead && posr);
if (posr == *phead)
{
pophead(phead);
}
Slist* pre = *phead;
while (pre->next != posr)
{
pre = pre->next;
}
pre->next = posr->next;
free(posr);
posr = NULL;
}
//在指定结点之后删除
void sltdeletback(Slist* pos)
{
assert(pos&&pos->next);
Slist* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
void sltdestory(Slist** phead)
{
Slist* pre = *phead;
while (pre)
{
Slist* node = pre->next;
free(pre);
pre = node;
}
*phead = NULL;
}