八亿建站,千博企业网站管理系统2013,做门户网站用什么服务器,辽宁手机版建站系统开发目录 前言
一.什么是链表
1.概念
编辑
2.分类
二.单链表的实现(不带头单向不循环链表)
2.1初始化
2.2打印
2.3创建新节点
2.4头插、尾插
2.5头删、尾删
2.6查找
2.7在指定位置之前插入
2.8在指定位置之后插入
2.9删除pos位置
2.10删除pos之后的
2.11销毁链表…目录 前言
一.什么是链表
1.概念
编辑
2.分类
二.单链表的实现(不带头单向不循环链表)
2.1初始化
2.2打印
2.3创建新节点
2.4头插、尾插
2.5头删、尾删
2.6查找
2.7在指定位置之前插入
2.8在指定位置之后插入
2.9删除pos位置
2.10删除pos之后的
2.11销毁链表 前言
通过前面所学的顺序表我们发现存在着几个问题,顺序表的中间/头部的插入需要挪动数据、扩容存在着性能的消耗、或多或少有空间的浪费由此我们引入链表这一概念.
一.什么是链表
1.概念 链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 2.分类
结构多样根据是否带头单向/双向循环/不循环分为8种
其中使用较多的是单链表不带头单向不循环链表和双向链表(带头双向循环链表),这节讲解单链表的实现
二.单链表的实现(不带头单向不循环链表)
2.1初始化
结构的声明和定义
typedef int SLTDataType;
//该链表由节点组成
typedef struct SListNode
{SLTDataType data;struct SListNode* next;//这里不能写成SLTNode,这时还未重命名
}SLTNode;//typedef struct SListNode SLTNode;
2.2打印
这里有pcur去接收phead,然后依次遍历当pcur指向NULL时跳出循环最后再打印NULL
void SLTPrint(SLTNode* phead)
{SLTNode* pcur phead;while (pcur){printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
}
2.3创建新节点
与顺序表的扩容不同这里需要新节点即开辟不会造成浪费
如果开辟失败则会报错
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));//新节点if (newnode NULL){perror(malloc fail!);exit(1);}newnode-data x;newnode-next NULL;return newnode;
}
2.4头插、尾插
头插相较于尾插较容易这里面传递的是二级指针
//链表的头插、尾插
void SLTPushBack(SLTNode** phead, SLTDataType x);
void SLTPushFront(SLTNode** phead, SLTDataType x);//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode SLTBuyNode(x);//链表为空新节点为pheadif (*pphead NULL){*pphead newnode;return;}//链表不为空找尾节点SLTNode* ptail *pphead;while (ptail-next){ptail ptail-next;}//为空跳出循环此时ptail就是尾节点ptail-next newnode;
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode SLTBuyNode(x);//newnode *ppheadnewnode-next *pphead;*pphead newnode;
}
2.5头删、尾删
//链表的头删、尾删
void SLTPopBack(SLTNode** phead);
void SLTPopFront(SLTNode** phead);//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//链表不为空//链表只有一个节点,有多个节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;return;}SLTNode* ptail *pphead;SLTNode* prev NULL;while (ptail-next)//prev ptail ptail-next{prev ptail;ptail ptail-next;}prev-next NULL;//销毁尾节点free(ptail);ptail NULL;
}//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//让第二个节点成为新的头//把旧的头节点释放掉SLTNode* next (*pphead)-next;free(*pphead);*pphead next;
}
2.6查找
通过遍历链表查找是否与x相等,若有则返回pcur;若未找到,则返回NULL
//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(pphead);//遍历链表SLTNode* pcur *pphead;while (pcur){if (pcur-data x){return pcur;}pcur pcur-next;}//没有找到return NULL;
}
2.7在指定位置之前插入
与头插类似
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//要加上链表不为空,若是空链表那么前面将断言assert(*pphead);SLTNode* newnode SLTBuyNode(x);//pos刚好是头节点if (pos *pphead){//头插SLTPushFront(pphead,x);return;}//pos不是头节点的情况SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}//prev-newnode-posprev-next newnode;newnode-next pos;
}
2.8在指定位置之后插入
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode SLTBuyNode(x);//pos newnode pos-nextnewnode-next pos-next;pos-next newnode;
}
2.9删除pos位置
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//pos刚好是头节点没有前驱节点执行头删if (*pphead pos){//头删SLTPopFront(pphead);return;}SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}//prev pos pos-nextprev-next pos-next;free(pos);pos NULL;
}
2.10删除pos之后的
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);//删除链表之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//pos-next不能为空assert(pos-next);//pos pos-next pos-next-nextSLTNode* del pos-next;free(del);del NULL;
}
2.11销毁链表
//销毁链表
void SListDesTroy(SLTNode** pphead); //销毁链表
void SListDesTroy(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur *pphead;while (pcur){SLTNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
} 如果上述内容对您有帮助希望给个三连谢谢
