数据结构-单链表
对于顺序表来说，我要一次性的申请一块内存空间，但有时候用户并不确定要多大的内存空间!有时候可能会向里边添加元素，但是受限于申请的内存大小，导致加入元素的时候并不方便，而且顺序表的插入和删除相对复杂，需要设计元素的移动。基于顺序表的缺陷，引入链表，在创建链表的时候，我只需要申请一个头结点，存储链表的头，当需要添加元素的时候，我就申请一块内存，将链表头的下一个节点的指针，指向该地址空间九就可以完成链表结点的插入，可以方便的实现增删等功能。创建链表的头
typedef struct LinkedList
{
DataType_t data; //结点的数据域
struct LinkedList *next; //结点的指针域
}LList_t;创建一个空链表
LList_t * LList_Create(void)
{
//1.创建一个头结点并对头结点申请内存
LList_t *Head = (LList_t *)calloc(1,sizeof(LList_t));
if (NULL == Head)
{
perror("Calloc memory for Head is Failed");
exit(-1);
}
//2.对头结点进行初始化，头结点是不存储有效内容的！！！
Head->next = NULL;
//3.把头结点的地址返回即可
return Head;
}创建新结点
//func：创建新结点，并初始化
//argc：要添加的新结点的元素的值
//ret：新结点结构体的地址
LList_t * LList_NewNode(DataType_t data)
{
//1.创建一个新结点并对新结点申请内存
LList_t *New = (LList_t *)calloc(1,sizeof(LList_t));
if (NULL == New)
{
perror("Calloc memory for NewNode is Failed");
return NULL;
}
//2.对新结点的数据域和指针域进行初始化
New->data = data;
New->next = NULL;
return New;
}头部插入元素
bool LList_HeadInsert(LList_t *Head,DataType_t data)
{
//1.创建新的结点，并对新结点进行初始化
LList_t *New = LList_NewNode(data);
if (NULL == New)
{
printf("can not insert new node\n");
return false;
}
//2.判断链表是否为空，如果为空，则直接插入即可
if (NULL == Head->next)
{
Head->next = New;
return true;
}
//3.如果链表为非空，则把新结点插入到链表的头部
New->next= Head->next;
Head->next = New;
return true;
}尾部插入元素
bool LList_TailInsert(LList_t *Head,DataType_t data)
{
LList_t *Phead=Head;
//1.创建新的结点，并对新结点进行初始化
LList_t *New = LList_NewNode(data);
if (NULL == New)
{
printf("can not insert new node\n");
return false;
}
while(Phead->next != NULL){
Phead = Phead->next;
}
Phead->next = New;
return true;
}指定元素后边插入
bool LList_DestInsert(LList_t *Head,DataType_t dest,DataType_t data)
{
//定义两个指针用于遍历
LList_t *Pphead;
Pphead = Head->next;
LList_t *New = LList_NewNode(data);
if (NULL == New)
{
printf("can not insert new node\n");
return false;
}
if(Head->next == NULL){
printf("this is a void list\n");
return false;
}
while(Pphead->data != dest){
if(Pphead->next == NULL ){
printf("NO value\n");
return false;
}
else{
Pphead = Pphead->next ;
}
}
New->next =Pphead->next;
Pphead->next= New;
return true;
}首删
bool LList_HeadDel(CircLList_t *Head)
{
//对单向循环链表的头尾结点的地址进行备份
CircLList_t *Phead = Head->next;
CircLList_t *Pphead = Head->next;
//判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return false;
}
if(Head->next->next == Head->next){
Head->next->next =NULL;
free(Head->next);
Head->next = Head;
return true;
}
//遍历链表找到尾结点
while(Phead->next != Head->next){
Phead = Phead->next;
}
//进行删除操作，重新连接
Phead->next = Pphead->next;
Head->next = Pphead->next;
Pphead->next = NULL;
free(Pphead);
return true;
}指定元素删除
bool LList_DestDel(LList_t *Head,DataType_t dest)
{
LList_t *Phead = Head;
LList_t *Pphead = Head->next;
//1.判断链表是否为空，如果为空，则直接退出
if (NULL == Head->next)
{
return false;
}
//循环查找目标节点
while(Pphead->data != dest){
if(Pphead->next == NULL){
printf("not exit this node\n");
return false;
}
Phead = Pphead;
Pphead = Pphead->next;
}
Phead->next = Pphead->next;
Pphead->next = NULL;
free(Pphead);
return true;
}尾部删除
bool LList_TailDel(LList_t *Head)
{
LList_t *Phead = Head;
LList_t *Pphead = Head->next;
//判断链表是否为空
if(Head->next == NULL){
printf("this is a void list，do not del \n");
return false;
}
//循环找到链表的最后一个节点和倒数第二个节点
while(Pphead->next != NULL){
Phead = Pphead;
Pphead = Pphead->next;
}
//删除尾节点
Phead->next = NULL;
free(Pphead);
return true;
}删除链表中最小的结点
bool LList_MinDel(LList_t *Head)
{
LList_t *Phead = Head->next;
DataType_t min = Phead->data;
LList_t *Pphead = Head->next;
//判断链表是否为空
if(Head->next == NULL){
printf("this is a void list，do not del \n");
return false;
}
//循环找到最小的节点（循环的时候比较不了最后一个元素)
while(Pphead->next != NULL){
if(Pphead->data < min){
min = Pphead->data;
Phead = Pphead;
}
Pphead = Pphead->next;
}
//比较最后一个元素是否是最小的
if(Pphead->data < min){
min = Pphead->data;
Phead = Pphead;
}
if(Phead->next == NULL){
LList_TailDel(Head);
}
else{
LList_DestDel(Head,min);
}
return true;
}删除链表中倒数k个元素
DataType_t LList_FindnLast(LList_t *Head,unsigned int n)
{
LList_t *Pphead = Head;
LList_t *Phead = Head;
//判断链表是否为空
if(Head->next == NULL){
printf("this is a void list，do not del \n");
return false;
}
for(int i=1;i<n;i++){
Pphead = Pphead->next;
}
while(Pphead->next != NULL){
Pphead = Pphead->next;
Phead = Phead->next;
}
return Phead->data;
}遍历链表并打印
void LList_Print(LList_t *Head)
{
//对链表的头文件的地址进行备份
LList_t *Phead = Head;
//首结点
while(Phead->next)
{
//把头的直接后继作为新的头结点
Phead = Phead->next;
//输出头结点的直接后继的数据域
printf("data = %d\n",Phead->data);
}
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]