数据结构-链表
头文件:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
主函数:
//主函数
int main(int argc, const char *argv[])
{LkList_t *LkList = LkListCreate(); //初始化 printf("%#x\n",LkList); //打印地址LkListHeadInsert(LkList,10); //头节点后添加节点LkListHeadInsert(LkList,20); //头节点后添加节点LkListDestInsert(LkList,20,15); //指定节点后添加节点LkListTailInsert(LkList,9); //尾节点后添加节点LkListTailInsert(LkList,8); //尾节点后添加节点LkListTailInsert(LkList,7); //尾节点后添加节点LkListPrint(LkList); //20,15,10,9,8,7 LkListHeadDel(LkList); //头节点后删除节点LkListTailDel(LkList); //删除尾节点LkListDestDel(LkList,10); //删除指定节点printf("\n"); LkListPrint(LkList); //15,9,8}
定义结构体
typedef int DataType_t; //用户自定义指针类型//定义结构体
typedef struct LinkedList
{DataType_t Data; //数据域 struct LinkedList *Next; //指针域 }LkList_t; //别名
初始化
//创建头节点
LkList_t *LkListCreate(void)
{LkList_t *Head = (LkList_t *)calloc(1,sizeof(LkList_t));//判断申请堆内存是否成功 if (NULL == Head){perror("Calloc memory for Head failed");exit(-1);}Head->Next=NULL;return Head;
}
创建独立节点
//创建独立节点
LkList_t *LkListNewNode(DataType_t Data)
{LkList_t *New = (LkList_t *)calloc(1,sizeof(LkList_t));//判断申请堆内存是否成功if (NULL == New){perror("Calloc memory for New is failed");return NULL;}New->Data = Data;New->Next = NULL;return New;}
插入节点
1.头节点后插入节点
2.尾节点后插入节点
3.指定位置插入节点
//头节点后插入节点
bool LkListHeadInsert(LkList_t *Head , DataType_t Data)
{LkList_t *New = LkListNewNode(Data); //调用函数创建新节点//判断是否创建成功if (NULL == New){return false;}//如果为空链表,将头节点的Next指向新创建的节点 if (NULL == Head->Next){Head->Next = New;return true;}else{New->Next = Head->Next;Head->Next = New;}
}//尾节点后插入节点
bool LkListTailInsert(LkList_t *Head , DataType_t Data)
{LkList_t *New = LkListNewNode(Data); //调用函数创建新节点//判断是否创建成功if (NULL == New){return false;}//如果为空链表,将头节点的Next指向新创建的节点if (NULL == Head->Next){Head->Next = New;return true;}//非空链表else{LkList_t *p = Head; //将头节点地址赋值给p指针while (p->Next != NULL){p = p->Next;}p->Next = New; }
}//指定位置插入节点
bool LkListDestInsert(LkList_t *Head , DataType_t Dest , DataType_t Data)
{LkList_t *New = LkListNewNode(Data); //调用函数创建新节点//判断是否创建成功if (NULL == New){return false;}//如果为空链表,将头节点的Next指向新创建的节点 if (NULL == Head->Next){Head->Next = New;return true;}//非空链表else{LkList_t *p = Head; //将头节点地址赋值给p指针while (p->Data != Dest){p = p->Next;}New->Next = p->Next;p->Next = New; }
}
删除节点
1.删除首节点
2.删除尾节点
3.删除指定节点
//删除首节点
bool LkListHeadDel(LkList_t *Head)
{//判断是否为空链表if (NULL == Head->Next){return false;}else{ LkList_t *p; p = Head->Next;Head->Next = p->Next; //头节点的Next指向第二个节点p->Next = NULL; //首节点的Next赋值为NULLfree(p); //释放首节点return true;}
}//删除尾节点
bool LkListTailDel(LkList_t *Head)
{//判断是否为空链表if (NULL == Head->Next){return false;}else{ LkList_t *p1 = Head; //记录尾节点的前一个地址 LkList_t *p2 = Head->Next; //记录尾节点的地址while (p2->Next != NULL){p1 = p2;p2 = p2->Next;}p1->Next = NULL; //当前倒数第二个节点指向NULL,成为尾节点free(p2); //释放尾节点return true;}
}//指定位置删除节点
bool LkListDestDel(LkList_t *Head , DataType_t Dest)
{//判断是否为空链表if (NULL == Head->Next){return false;}else{LkList_t *p1 = Head; //记录前一个节点的地址LkList_t *p2 = Head->Next; //记录删除节点的地址//判断是否p->Data == Destwhile (p2->Data != Dest){p1 = p2; p2 = p2->Next;}p1->Next = p2->Next; //将删除节点的Next,赋值给前一个节点p2->Next = NULL; //将删除节点的Next指向空free(p2); //释放该节点return true;}
}
遍历链表
//遍历链表
void LkListPrint(LkList_t *Head)
{LkList_t *p = Head; //打印整个链表while (p->Next != NULL){p = p->Next;printf("Data=%d\n",p->Data);}}