单链表(linked List):由各个内存结构通过一个next指针链接在一起组成,每一个内存结构都存在后继内存结构(链尾除外),内存结构由数据域和next指针域组成。
Data 数据 + Next 指针,组成一个单链表的内存结构;第一个内存结构称为 链头,最后一个内存结构称为 链尾;链尾的 Next 指针设置为 NULL (指向空);单链表的方向单一(只能从链头一直遍历到链尾)
单链表的结构体定义
typedef int DataType; typedef struct ListNode { DataType data; struct ListNode* next; }ListNode;
创建节点
//动态申请一个节点,赋值X ListNode* BuyListNode(DataType x) { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); assert(node);//使用断言检测空间申请失败与否,一搬不会失败,当代计算机的内存足够大几百行的代码一般不会申请失败 node->data = x; node->next = NULL; return node;//返回此节点的地址 }
打印链表
//定义一个ListNode型的指针来遍历打印Data值 void ListPrint(ListNode* head) { ListNode* cur = head; while (cur) {//当cur走到链表尾时判出 printf("%d--->", cur->data); cur = cur->next; } printf("NULLn"); }为什么要使用二级指针?
单链表尾插
ATTENTION:此处函数的参数传了一个二级指针
如图,如果我们不修改head指针的指向时,使用一级指针,可如果我们想修改head的指向时就要使用二级指针,与普通变量类似,若要修改普通变量的值,则需要传入变量的地址,若只是使用变量则传值即可。同理,若要修改head的指向,则需要传入二级指针,若使用一级指针,则只能修改所对应的内存块中的值,却无法修改指针本身的值即指针指向的是哪个内存块。
函数中传递指针,在函数中改变指针的值,就是在改变实参中的数据信息。但是这里改变指针的值实际是指改变指针指向地址的值,因为传递指针就是把指针指向变量的地址传递过来,而不是像值传递一样只是传进来一个实参的拷贝。所以当我们改变指针的值时,实参也改变了。
void ListPushBack(ListNode** head, DataType x) { assert(head);//检测head是否存在 if (*head == NULL) {//如果链表为空直接申请一个节点地址赋给*head *head = BuyListNode(x); } else { ListNode* cur = *head; while (cur->next) {//遍历找到尾节点 cur = cur->next; } cur->next= BuyListNode(x); } }
单链表尾删
void ListPopBack(ListNode** head) { assert(head); if (*head == NULL) {//链表为空 return; } else { if ((*head)->next==NULL ) {//只有一个节点时 *head= NULL;//让头节点指向NULL free(*head); } else { ListNode* cur = *head;//cur来遍历,prev储存cur前一个节点的地址 ListNode* prev = NULL; while (cur->next) {//cur走到最后一个节点时判出 prev = cur; cur = cur->next; } prev->next = NULL; free(cur); } } }
** 单链表头插**
void ListPushFront(ListNode** head, DataType x) { assert(head); if (NULL == *head) {//如果链表为空,直接申请一个新节点给head *head = BuyListNode(x); } else { ListNode* cur = BuyListNode(x);//申请新节点 cur->next = *head;//让新节点成为头 *head = cur; } }
单链表头删
void ListPopFront(ListNode** head) { assert(head); if (*head == NULL) {//如果链表为空则删除不了 return; } else { ListNode* cur = *head;//让head指向它的下一个节点 *head = (*head)->next; free(cur); } }
单链表查找
ListNode* ListFind(ListNode* head, DataType x) { assert(head); if (head == NULL) { return NULL; } else { ListNode* cur = head; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } }
单链表在pos之后插入值
void ListInsertAfter(ListNode** pos, DataType x) { assert(pos); if (pos == NULL) { return; } ListNode* node = BuyListNode(x); node->next = (*pos)->next;//申请一个节点指向pos->next,再让pos指向它 (*pos)->next = node; }
单链表删除pos之后的值
void ListEraseAfter(ListNode** pos) { assert(pos); if (*pos == NULL) { return; } else { if ((*pos)->next == NULL) {//如果是尾节点则删不了 return; } ListNode* node = (*pos)->next; (*pos)->next = node->next;//让pos指向pos的下下个节点 free(node); } }
单链表销毁
如果不销毁的话会造成内存泄露
void ListDestory(ListNode** head) { assert(head); ListNode* cur = *head;//遍历删除并释放空间 while (cur) { *head = cur->next; free(cur); cur = *head; } *head = NULL; }完整代码
//"singleList.c" #include#include #include "List.h" #include //动态申请一个节点,赋值X ListNode* BuyListNode(DataType x) { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); assert(node); node->data = x; node->next = NULL; return node; } // 单链表销毁 void ListDestory(ListNode** head) { assert(head); ListNode* cur = *head;//遍历删除并释放空间 while (cur) { *head = cur->next; free(cur); cur = *head; } *head = NULL; } // 单链表打印 void ListPrint(ListNode* head) { ListNode* cur = head; while (cur) { printf("%d--->", cur->data); cur = cur->next; } printf("NULLn"); } // 单链表尾插 void ListPushBack(ListNode** head, DataType x) { assert(head); if (*head == NULL) { *head = BuyListNode(x); } else { ListNode* cur = *head; while (cur->next) { cur = cur->next; } cur->next= BuyListNode(x); } } // 单链表尾删 void ListPopBack(ListNode** head) { assert(head); if (*head == NULL) { return; } else { if ((*head)->next==NULL ) { (*head)->next = NULL; free(*head); } else { ListNode* cur = *head; ListNode* prev = NULL; while (cur->next) { prev = cur; cur = cur->next; } prev->next = NULL; free(cur); } } } // 单链表头插 void ListPushFront(ListNode** head, DataType x) { assert(head); if (NULL == *head) { *head = BuyListNode(x); } else { ListNode* cur = BuyListNode(x); cur->next = *head; *head = cur; } } // 单链表头删 void ListPopFront(ListNode** head) { assert(head); if (*head == NULL) { return; } else { ListNode* cur = *head; *head = (*head)->next; free(cur); } } // 单链表查找 ListNode* ListFind(ListNode* head, DataType x) { assert(head); if (head == NULL) { return NULL; } else { ListNode* cur = head; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } } // 单链表在pos之后插入值 void ListInsertAfter(ListNode** pos, DataType x) { assert(pos); if (pos == NULL) { return; } ListNode* node = BuyListNode(x); node->next = (*pos)->next; (*pos)->next = node; } // 单链表删除pos之后的值 void ListEraseAfter(ListNode** pos) { assert(pos); if (*pos == NULL) { return; } else { if ((*pos)->next == NULL) { return; } ListNode* node = (*pos)->next; (*pos)->next = node->next; free(node); } } void test() { ListNode* head = NULL; ListPushBack(&head, 1);//尾插 ListPushBack(&head, 2); ListPushBack(&head, 3); ListPushBack(&head, 4); ListPushBack(&head, 5); ListPushBack(&head, 6); ListPrint(head); ListPopBack(&head);//尾删 ListPrint(head); ListPushFront(&head, 0);//头插 ListPrint(head); ListPopFront(&head);//头删 ListPrint(head); ListPrint(ListFind(head, 5));//查找结点 ListNode* pos = ListFind(head, 5); ListInsertAfter(&pos, 6);//pos位置之后插入 ListPrint(head); ListEraseAfter(&pos);//删除pos之后的值 ListPrint(head); ListDestory(&head);//销毁链表 ListPrint(head); }
//"main.c" #include "List.h" int main() { test(); return 0; }
//"List.h" typedef int DataType; typedef struct ListNode { DataType data; struct ListNode* next; }ListNode; // 创建结点. ListNode* BuyListNode(); // 单链表销毁 void ListDestory(ListNode** pHead); // 单链表打印 void ListPrint(ListNode* pHead); // 单链表尾插 void ListPushBack(ListNode** pHead, DataType x); // 单链表尾删 void ListPopBack(ListNode** pHead); // 单链表头插 void ListPushFront(ListNode** pHead, DataType x); // 单链表头删 void ListPopFront(ListNode** pHead); // 单链表查找 ListNode* ListFind(ListNode* pHead, DataType x); // 单链表在pos之后插入值 void ListInsertAfter(ListNode** pos, DataType x); // 单链表删除pos之后的值 void ListEraseAfter(ListNode** pos); void test();
测试结果
void test() { ListNode* head = NULL; ListPushBack(&head, 1);//尾插 ListPushBack(&head, 2); ListPushBack(&head, 3); ListPushBack(&head, 4); ListPushBack(&head, 5); ListPushBack(&head, 6); ListPrint(head); ListPopBack(&head);//尾删 ListPrint(head); ListPushFront(&head, 0);//头插 ListPrint(head); ListPopFront(&head);//头删 ListPrint(head); ListPrint(ListFind(head, 5));//查找结点 ListNode* pos = ListFind(head, 5); ListInsertAfter(&pos, 6);//pos位置之后插入 ListPrint(head); ListEraseAfter(&pos);//删除pos之后的值 ListPrint(head); ListDestory(&head);//销毁链表 ListPrint(head); }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)