网站首页新世纪建设集团有限公司,注册监理工程师注册查询系统,西安网站建设优化与推广,安庆什么网站好小事做链表的定义与创建
线性表#xff1a; 1. 物理结构上不一定是线性的 2. 逻辑结构上一定是线性的
链表是一种物理存储结构上非连续#xff0c;非顺序的存储结构
链表也是线性表的一种#xff0c;但是在物理结构上不是连续的
链表是由一个一个的节点组成#xff0c;需要数…链表的定义与创建
线性表 1. 物理结构上不一定是线性的 2. 逻辑结构上一定是线性的
链表是一种物理存储结构上非连续非顺序的存储结构
链表也是线性表的一种但是在物理结构上不是连续的
链表是由一个一个的节点组成需要数据的时候只需要申请空间即可
节点包含两个组成部分 1. 存储的数据 2. 指向下一个节点的指针
//节点的结构演示
struct SListNode //single list node
{int data;struct SListNode* next; //指向下一个节点的指针
}
下面我们将详细的进行链表节点的定义
//定义节点的结构
//数据 指向下一个节点的指针
typedef int SLTDataType; //由于数据不止 int 一种类型所以统一用 SLTDataType 表示
typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;
这里我们将struct SListNode 统一改写成 SLTNode
接下来我们来学习创建几个节点
//创建四个节点
SLTNode* node1 (SLTNode*)malloc(sizeof(SLTNode));
node1-data 1;
SLTNode* node2 (SLTNode*)malloc(sizeof(SLTNode));
node2-data 2;
SLTNode* node3 (SLTNode*)malloc(sizeof(SLTNode));
node3-data 3;
SLTNode* node4 (SLTNode*)malloc(sizeof(SLTNode));
node4-data 4;
//将四个节点连接起来
node1-next node2;
node2-next node3;
node3-next node4;
node4-next NULL;
由于创建的新节点的内存情况未知所以使用 malloc 来动态分配内存。realloc 主要用于调整已分配内存块的大小 链表的打印
void SLTPrint(SLTNode* phead)
{SLTNode* pcur phead;while (pcur){printf(%d-, pcur-data);pcur pcur-next; }printf(NULL\n);
}
但是我们一般不会像那样创建节点而是给一个空链表去插入数据所以下面是链表的尾插 链表的尾插
想找到进行尾插要先找到尾节点再将尾节点和新节点连接起来
注意 我们在尾插头插等等时都需要用到malloc创建新的空间重复的书写会使代码显得冗长所以我们封装一个函数专门用于开辟空间
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));//判断空间是否开辟成功if (newnode NULL){perror(malloc failed !);exit(1); //用非零的数表示非正常退出}newnode-data x;newnode-next NULL;return newnode;
}
有了创建控件函数后我们开始写尾插代码
void SLTPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* newnode SLTBuyNode(x);//先找尾SLTNode* ptail phead; while (ptail-next ! NULL){ptail ptail-next;}//此时ptail指向的就是尾节点ptail-next newnode;
}
请注意这里的原链表并不知道是否是空链表若为空则对空指针解引用是非法的。所以需要对两种情况进行讨论
void SLTPushBack(SLTNode* phead, SLTDataType x)
{//空链表情况SLTNode* newnode SLTBuyNode(x);if (phead NULL){phead newnode;}else{//非空链表情况//先找尾SLTNode* ptail phead; while (ptail-next ! NULL){ptail ptail-next;}//此时ptail指向的就是尾节点ptail-next newnode;}
}
这里用个很重大的问题我们传入实参 plist 而我们需要形参改变实参plist虽然也是指针但他存储着一个结构体的地址我们现在就是要修改这个地址的相关内容所以我们需要使用二级指针来传址调用
下面是一些对应关系 第一个节点 *plist **pphead 指向第一个节点的指针 plist *pphead 指向第一个节点的指针的地址 plist pphead
//链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//空链表情况SLTNode* newnode SLTBuyNode(x);if (*pphead NULL){*pphead newnode;}else{//非空链表情况//先找尾SLTNode* ptail *pphead; while (ptail-next ! NULL){ptail ptail-next;}//此时ptail指向的就是尾节点ptail-next newnode;}
}
由于节点的地址的地址不能为空所以再加入断言尾插代码就写好了。
void SLTPopBack(SLTNode** pphead)
{assert(pphead *pphead); //链表不能为空SLTNode* prev *pphead;SLTNode* ptail *pphead;while (ptail-next){prev ptail;ptail ptail-next;}free(ptail);ptail NULL;prev-next NULL;
}
链表的头插相对简单
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode SLTBuyNode(x);newnode-next *pphead;*pphead newnode;
} 链表的尾删
思路为先找到尾节点将尾节点释放掉由于释放了尾节点后尾节点的上一个节点依然指向尾节点所以还需将上一个节点置零
void SLTPopBack(SLTNode** pphead)
{assert(pphead *pphead); //链表不能为空SLTNode* prev *pphead;SLTNode* ptail *pphead;while (ptail-next){prev ptail;ptail ptail-next;}free(ptail);ptail NULL;prev-next NULL;
}
当链表只有一个节点的时候此时尾节点的上一个节点并不实际存在所以需要单独讨论
void SLTPopBack(SLTNode** pphead)
{assert(pphead *pphead); //链表不能为空//链表只有一个节点时if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{//有多个节点时SLTNode* prev *pphead;SLTNode* ptail *pphead;while (ptail-next){prev ptail;ptail ptail-next;}free(ptail);ptail NULL;prev-next NULL;}
}
