学习链表有段时间了,今天给大家整理了有关链表的基本操作,例如链表的创建、增、删、查等基本操作
结构体定义
typedef int DataType;
typedef struct ListNode
{
DataType data;
struct ListNode *next;
} ListNode;
头文件的定义
其中包含了面试题的头文件
void ListInit(ListNode **Node);
void ListDestroy(ListNode **Node);
void ListPushFront(ListNode **Node,DataType data);
void ListPushBack(ListNode **Node,DataType data);
void ListPopFront(ListNode **Node);
void LIstPopBack(ListNode **Node);
ListNode* ListFind(ListNode *Node , DataType data);
void ListInsert(ListNode **Node,ListNode *pos,DataType data);
void ListDelete(ListNode **Node,ListNode *pos);
// 删除一个无头单链表的非尾结点(不能遍历链表)
void ListDelNotFirst(ListNode **Node ,ListNode *pos);
//递归写法
void ListReversePrint(ListNode *Node);
void ListReveresePrint2(ListNode *Node);
void ListPrint(ListNode *Node);
void ListIntersection(ListNode *list1,ListNode *list2);
void TestListInterstion();
ListNode* ListJosephCircle(ListNode *list,DataType k);
void TestListJosephCircle();
ListNode *ListMerge(ListNode *list1,ListNode *list2);
void TestMerge();
void ListFindMidNode(ListNode *list);
void TestFindMid();
void ListFindTailK(ListNode *list,DataType k);
void TestFindTailK();
void ListDelTailK(ListNode *list, DataType k);
void TestDelTailK();
链表的具体基本操作 文件名(List.c)
链表的初始化及销毁
#include "List.h"
void ListInit(ListNode **Node)
{
assert(Node != NULL);
*Node = NULL;
}
void ListDestroy(ListNode **Node)
{
*Node = NULL;
}
链表结点的创建
static ListNode * CreateNode(DataType data)
{
ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
assert(newNode);
newNode->data = data;
newNode->next = NULL;
return newNode;
}
头插法
//头插
void ListPushFront(ListNode **Node,DataType data)
{
//assert(Node != NULL);
ListNode *newNode = CreateNode(data); // *newNode 用来存储新结点的地址
newNode->next = *Node; // 把头结点的地址赋给新结点
*Node = newNode; // 把新结点的地址赋给头结点 ( *Node用来存储下一个结点的地址)
}
尾插法
//尾插
void ListPushBack(ListNode **Node,DataType data)
{
ListNode *newNode = CreateNode(data);
ListNode *cur = *Node; //把头结点地址赋给cur
if (*Node == NULL) //判断头结点是否为空,如果为空,将新的结点赋给头结点(如果是空链表)
{
*Node = newNode;
return;
}
while (cur->next !=NULL) //如果头结点不为空,则将判断头结点指向下一个结点以及后面的结点是否为空
{ // 如果有空结点,则将赋给当前cur,
cur = cur->next;
}
cur->next = newNode; //将新的结点地址赋给当前的下一结点
}
头结点的删除
void ListPopFront(ListNode **Node)
{
//assert(Node != NULL);
//assert(*Node != NULL);
ListNode *del = *Node; // 将头结点的地址del,然后指向下一个结点并赋给Node,然后释放del(头结点存储在del中)
*Node = del->next;
free(del);
}
尾结点的删除
void ListPopBack(ListNode **Node)
{
/*ListNode *del = *Node ;
while (del->next != NULL)
{
del = del->next;
}
*Node = del->next;
free(del);*/
ListNode *del;
ListNode *cur = *Node;
while (cur->next->next != NULL) // cur->next->next :头指针指向头结点,然后指向下一个结点
{ // 判断并找到最后一个结点的地址,赋给del
cur = cur->next;
}
del = cur->next;
cur->next = NULL;
free(del);
}
查找
//查找
ListNode* ListFind(ListNode *Node , DataType data)
{
ListNode *cur;
for (cur = Node;cur != NULL;cur=cur->next)
{
if (data == cur->data)
{
return cur;
}
}
return NULL;
}
结点前插入
//在某结点前插入结点
void ListInsert(ListNode **Node,ListNode *pos,DataType data)
{
ListNode *cur = *Node;
ListNode *newNode;
if (*Node == pos)
{
ListPopFront(Node);
return;
}
while (cur->next != pos)
{
cur = cur->next;
}
newNode = CreateNode(data);
newNode->next = cur->next;
cur->next =newNode;
}
删除指定结点
//删除指定结点
void ListDelete(ListNode **Node,ListNode *pos)
{
ListNode *cur = *Node;
if (*Node == pos)
{
ListPopFront(Node);
}
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = pos->next;
free(pos);
}
单链表的打印
//单链表的打印
void ListPrint(ListNode *Node)
{
ListNode *cur = Node;
if (Node == NULL)
{
return;
}
while (cur != NULL)
{
printf("%d--> ",cur->data);
cur = cur->next;
}
}