单链表
一、链表是什么？
??概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
二、链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1.单向和双向
2.带头或不带头
3. 循环或者非循环
三、单链表的实现
动态申请一个节点
ListNode* ListCreate(LTDataType x)
{
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
if (NULL == head)
{
assert(0);
return NULL;
}
head->data = x;
head->next = NULL;
return head;
}
单链表的尾插
void ListPushBack(ListNode** pHead, LTDataType x)
{
assert(pHead);
if (*pHead == NULL)
{
*pHead = ListCreate(x);
return;
}
else
{
ListNode* cur = *pHead;
while (cur->next)
{
cur = cur->next;
}
cur->next = ListCreate(x);
}
}
单链表的尾删
void ListPopBack(ListNode** pHead)
{
assert(pHead);
if (NULL == *pHead)
{
return;
}
else if (NULL == (*pHead)->next)
{
free(*pHead);
*pHead== NULL;
}
else
{
ListNode* cur = *pHead;
ListNode* pre = NULL;
while (cur->next)
{
pre = cur;
cur = cur->next;
}
pre->next = NULL;
free(cur);
}
}
单链表的头插
void ListPushFront(ListNode** pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = ListCreate(x);
newnode->next = *pHead;
*pHead = newnode;
}
单链表的头删
void ListPopFront(ListNode** pHead)
{
assert(pHead);
if (NULL == *pHead)
{
return;
}
else
{
ListNode *delNode = *pHead;
*pHead = (delNode)->next;
free(delNode);
}
}
单链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
assert(pHead);
if (NULL == pHead)
{
return;
}
ListNode* cur = pHead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
printf("没有这个元素\n");
return NULL;
}
在pos之后插入节点x
因为无法对pos之前的节点进行操作，所以在pos之后插入新节点。
void ListInsert(ListNode* pos, LTDataType x)
{
if (NULL == pos)
{
return;
}
ListNode* newNode = ListCreate(x);
newNode->next = pos->next;
pos->next = newNode;
}
删除pos之后位置的元素
void ListErase(ListNode* pos)
{
if (NULL == pos || NULL == pos->next)
{
return;
}
ListNode* delNode = pos->next;
pos->next = delNode->next;
free(delNode);
}
逆序打印链表
此为递归做法。
void ListReversePrint(ListNode* pHead)
{
if (NULL != pHead)
{
ListReversePrint(pHead->next);
printf("%d ", pHead->data);
}
}
测试函数
void TestList()
{
ListNode* pHead = NULL;
ListPushBack(&pHead, 1);
ListPushBack(&pHead, 2);
ListPushBack(&pHead, 3);
ListPushBack(&pHead, 4);
ListPushBack(&pHead, 5);
ListPrint(pHead);
ListPushFront(&pHead, 0);
ListPrint(pHead);
ListPopFront(&pHead);
ListPrint(pHead);
ListInsert(ListFind(pHead, 3),9);
ListPrint(pHead);
ListErase(ListFind(pHead, 3));
ListPrint(pHead);
ListReversePrint(pHead);
ListDestory(&pHead);
}
总结
??无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
完整代码
ListNode.h
#pragma once
#include<malloc.h>
#include<assert.h>
#include<stdio.h>
#include<Windows.h>
// 单链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
}ListNode;
//动态申请一个节点
ListNode* ListCreate(LTDataType);
//删除
void ListDestory(ListNode** pHead);
//单链表打印
void ListPrint(ListNode* pHead);
//单链表尾插
void ListPushBack(ListNode** pHead, LTDataType x);
//单链表尾删
void ListPopBack(ListNode** pHead);
//单链表头插
void ListPushFront(ListNode** pHead, LTDataType x);
//单链表头删
void ListPopFront(ListNode** pHead);
//单链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
//在pos插入元素
void ListInsert(ListNode* pos, LTDataType x);
//删除pos位置元素
void ListErase(ListNode* pos);
//逆置链表
void ListReversePrint(ListNode* plist);
void TestList();
ListNode.c
#include"ListNode.h"
//申请一个节点
ListNode* ListCreate(LTDataType x)
{
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
if (NULL == head)
{
assert(0);
return NULL;
}
head->data = x;
head->next = NULL;
return head;
}
//销毁单链表
void ListDestory(ListNode** pHead)
{
assert(pHead);
ListNode* cur = *pHead;
while (cur)
{
*pHead = cur->next;
free(cur);
cur = *pHead;
}
*pHead = NULL;
}
//打印单链表
void ListPrint(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead;
while (cur)
{
printf("%d-->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
//单链表的尾插
void ListPushBack(ListNode** pHead, LTDataType x)
{
assert(pHead);
if (*pHead == NULL)
{
*pHead = ListCreate(x);
return;
}
else
{
ListNode* cur = *pHead;
while (cur->next)
{
cur = cur->next;
}
cur->next = ListCreate(x);
}
}
//单链表的尾删
void ListPopBack(ListNode** pHead)
{
assert(pHead);
if (NULL == *pHead)
{
return;
}
else if (NULL == (*pHead)->next)
{
free(*pHead);
*pHead== NULL;
}
else
{
ListNode* cur = *pHead;
ListNode* pre = NULL;
while (cur->next)
{
pre = cur;
cur = cur->next;
}
pre->next = NULL;
free(cur);
}
}
//单链表的头插
void ListPushFront(ListNode** pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = ListCreate(x);
newnode->next = *pHead;
*pHead = newnode;
}
//单链表的头删
void ListPopFront(ListNode** pHead)
{
assert(pHead);
if (NULL == *pHead)
{
return;
}
else
{
ListNode *delNode = *pHead;
*pHead = (delNode)->next;
free(delNode);
}
}
//单链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
assert(pHead);
if (NULL == pHead)
{
return;
}
ListNode* cur = pHead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
printf("没有这个元素\n");
return NULL;
}
//在pos之后插入元素x
void ListInsert(ListNode* pos, LTDataType x)
{
if (NULL == pos)
{
return;
}
ListNode* newNode = ListCreate(x);
newNode->next = pos->next;
pos->next = newNode;
}
//删除pos之后位置的元素
void ListErase(ListNode* pos)
{
if (NULL == pos || NULL == pos->next)
{
return;
}
ListNode* delNode = pos->next;
pos->next = delNode->next;
free(delNode);
}
//逆置链表
void ListReversePrint(ListNode* pHead)
{
if (NULL != pHead)
{
ListReversePrint(pHead->next);
printf("%d ", pHead->data);
}
}
void TestList()
{
ListNode* pHead = NULL;
ListPushBack(&pHead, 1);
ListPushBack(&pHead, 2);
ListPushBack(&pHead, 3);
ListPushBack(&pHead, 4);
ListPushBack(&pHead, 5);
ListPrint(pHead);
ListPushFront(&pHead, 0);
ListPrint(pHead);
ListPopFront(&pHead);
ListPrint(pHead);
ListInsert(ListFind(pHead, 3),9);
ListPrint(pHead);
ListErase(ListFind(pHead, 3));
ListPrint(pHead);
ListReversePrint(pHead);
ListDestory(&pHead);
}
main.c
#include"ListNode.h"
int main()
{
TestList();
system("pause");
return 0;
}