以此文记录学习单链表的相关知识，以备后续回顾复习。
完整代码：链表学习相关的笔记和代码（C 语言）
无聊的配图
一、单链表相关说明
-
链表的结点由存放数据元素的数据域和存放后继结点地址的指针域组成
-
链表中第一个节点的存储位置叫做头指针
-
线性列表的最后一个结点指针为“空”，NULL
-
头指针：是指链表指向第一个结点的指针，若链表则是指向头结点的指针；头指针具有标识作用，所以常用头指针冠以链表的名字；无论链表是否为空，头指针都不为空，头指针是链的必要元素；
-
头结点： 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度） 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了 头结点不是链表第一要素
-
假设指针标量 p 指向链表中的任意结点，则访问结点分量有一下方式:
- (* p).data 和 (* p).next
- p->data 和 p->next
-
链表操作中动态存储分配要使用的标准函数：
- malloc(size):在内存的动态存储区申请一个长度为 size 字节的连续空间
- calloc(n, size):在内存的动态存储区申请 n 个长度为 size 字节的连续空间，函数返回值为分配空间的首地址，若函数执行失败，则返回值为0
- free(p):释放右指针 p 所指向的存储单元，而存储单元的大小是最近一次调用 malloc 或 calloc 函数时所申请的存储空间
- 以上函数包含在 stdlib.h 文件中 调用动态存储分配函数返回的指针是指向 void 类型或 char 类型的指针，在具体使用时，要根据所指向的数据类型进行强制类型转换
-
单链表建立的头插法和尾插法：
- 头插法： 头插法是将连败哦右端看成是固定的，链表不断向左延伸而得到的；头插法最先得到的是尾结点。
- 尾插法： 尾插法是将链表的左端固定，链表不断的向右延伸而得到的；尾插法最先得到的是头结点
二、单链表相关操作实现
1. LinkList.h
#ifndef LinkList_h
#define LinkList_h
#define OK 1
#define ERROR 0
#include <stdio.h>
typedef int Status; //定义函数返回值类型
typedef int ElemType; //结点数据的数据类型声明
typedef struct Node *LinkList;
/**
"*L":这里我们传入的是一个指向头指针的指针，因为我们传入的头指针初始化指向的是 NULL，在函数中我们要修改头指针变量指向的地址(即头指针变量的值)使其指向头结点，所以要修改头指针变量的值我们必须把头指针变量的地址传进来，头指针变量的地址存在指向头指针的指针中，所以这里传入的是指向头指针的指针；如果不穿地址，传头指针变量，则相当于传入的是头指针变量的值，函数内部会复制一份副本，达不到真正修改原头指针指向的目的。（这里把头指针看做一个普通变量可以方便理解，只不过指针存的是地址）
*/
//链表初始化
Status initLinkList(LinkList *L);
/**
*L:链表头指针
n:链表长度
*/
//头插法整表创建
Status createLinkLisAtHead(LinkList *L, int n);
/**
*L:链表头指针
n:链表长度
*/
//尾插法整表创建
Status createLinkLisAtTail(LinkList *L, int n);
//整表删除
Status clearLinkList(LinkList *L);
//获取链表长度 返回值为链表长度
int getLinkListLength(LinkList *L);
//打印整个链表
Status printLinkList(LinkList *L);
/**
*L:链表头指针
index:指定下标
*data:指向获取到的值的地址
*/
//获取指定位置结点的值
Status getData(LinkList *L, int index, ElemType *data);
/**
*L:链表头指针
index:指定插入下标
data:要插入的值
*/
//在链表任意位置插入数据
Status instertData(LinkList *L, int index, ElemType data);
/**
*L:链表头指针
data:要新增的值
*/
//在链表末尾追加数据
Status appendData(LinkList *L, ElemType data);
/**
*L:链表头指针
index:指定删除的下标
data:删除的结点的值
*/
//删除某一结点
Status deleteNode(LinkList *L, int index, ElemType *data);
#endif /* LinkList_h */
2. LinkList.c
#include "LinkList.h"
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
//线性表的单链表存储结构
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
Status initLinkList(LinkList *L)
{
//L 是头指针,指向头结点
(*L) = (LinkList)malloc(sizeof(Node));
if ((*L) == NULL) {
printf("链表初始化失败!\n");
return ERROR;
}
printf("链表初始化成功!\n");
//初始化头结点指针指向 NULL，数据域不做处理
(*L)->next = NULL;
return OK;
}
Status createLinkLisAtHead(LinkList *L, int n)
{
if ((*L) == NULL) {
printf("链表未初始化!\n");
return ERROR;
}
LinkList p; //声明指向新节点的指针
srand((int)time(0));//随机数种种子
for (int i = 0; i < n; i++) {
p = (LinkList)malloc(sizeof(Node));
if (p == NULL) {
printf("第%d 个结点创建失败!\n",i);
return ERROR;
}
p->data = rand() % 100;
p->next = (*L)->next;
(*L)->next = p;
}
printf("头插法链表整表创建成功!\n");
return OK;
}
Status createLinkLisAtTail(LinkList *L, int n)
{
if ((*L) == NULL) {
printf("链表未初始化!\n");
return ERROR;
}
LinkList p; //声明指向新节点的指针
LinkList tail = *L;//保存尾结点的临时变量
srand((int)time(0));//随机数种种子
for (int i = 0; i < n; i++) {
p = (LinkList)malloc(sizeof(Node));
if (p == NULL) {
printf("第%d 个结点创建失败!\n",i);
return ERROR;
}
p->data = rand() % 100;
p->next = NULL;
tail->next = p;
tail = p;
}
printf("尾插法链表整表创建成功!\n");
return OK;
}
Status clearLinkList(LinkList *L)
{
if ((*L) == NULL) {
printf("链表未初始化!\n");
return ERROR;
}
LinkList p;//声明遍历链表指向当前结点的指针
LinkList q;//临时指向当前结点下一个结点的指针
p = (*L)->next;//指向第一个节点
while (p != NULL) {
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL;//头结点指针域置空
return OK;
}
int getLinkListLength(LinkList *L)
{
if ((*L) == NULL) {
printf("链表未初始化!\n");
return ERROR;
}
int length = 0;
LinkList p;//声明遍历链表指向当前结点的指针
p = (*L)->next;//指向第一个节点
while (p) {
length++;
p = p->next;
}
return length;
}
Status printLinkList(LinkList *L)
{
if ((*L) == NULL) {
printf("链表未初始化!\n");
return ERROR;
}
int i = 0;
LinkList p;//声明遍历链表指向当前结点的指针
p = (*L)->next;//指向第一个节点
if (p == NULL) {
printf("链表为空!\n");
return ERROR;
}
while (p) {
i++;
printf("链表第%d个元素值为:%d!\n", i, p->data);
p = p->next;
}
return OK;
}
Status getData(LinkList *L, int index, ElemType *data)
{
*data = -1;
if ((*L) == NULL) {
printf("链表未初始化!\n");
return ERROR;
}
int currentIndex = 1;
LinkList p;//声明遍历链表指向当前结点的指针
p = (*L)->next;//指向第一个节点
if (p == NULL) {
printf("链表为空!\n");
return ERROR;
}
if (index < 1) {
printf("查询下标不能小于1!\n");
return ERROR;
}
while (p && currentIndex < index) {
p = p->next;
currentIndex++;
}
if (p == NULL) {
printf("查询下标超出了链表的最大长度!\n");
return ERROR;
}
*data = p->data;
return OK;
}
Status instertData(LinkList *L, int index, ElemType data)
{
if ((*L) == NULL) {
printf("链表未初始化!\n");
return ERROR;
}
if (index < 1) {
printf("插入下标不能小于1!\n");
return ERROR;
}
int currentIndex = 1;
LinkList p;//声明遍历链表指向当前结点的指针
LinkList newNode;//声明一个新节点
p = *L;//头指针
while (p && currentIndex < index) { //寻找第 index - 1个结点
p = p->next;
currentIndex++;
}
if (p == NULL) {
printf("插入下标超出了链表的范围!\n");
return ERROR;
}
newNode = (LinkList)malloc(sizeof(Node));
newNode->data = data;
newNode->next = p->next;
p->next = newNode;
return OK;
}
Status appendData(LinkList *L, ElemType data)
{
if ((*L) == NULL) {
printf("链表未初始化!\n");
return ERROR;
}
LinkList p;//声明遍历链表指向当前结点的指针
LinkList newNode;//声明一个新节点
LinkList tail = NULL;//记录尾结点
p = *L;//头指针
while (p) {
tail = p;
p = p->next;
}
newNode = (LinkList)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
tail->next = newNode;
return OK;
}
Status deleteNode(LinkList *L, int index, ElemType *data)
{
if ((*L) == NULL) {
printf("链表未初始化!\n");
return ERROR;
}
LinkList p,pnext;
int j = 0;
p = (*L);
if (p->next == NULL) {
printf("链表为空，无法删除指定节点.\n");
*data = -1;
return ERROR;
}
while (p->next && j < index - 1) {
j++;
p = p->next;
}//条件最多定位到最后一个节点；
if ( p->next == NULL) {
printf("您要删除的节点，超过了链表的长度 %d，请重新操作！\n", j);
*data = -1;
return ERROR;
}
pnext = p->next;
p->next = pnext->next;
*data = pnext->data;
free(pnext);
printf("节点删除成功\n");
return OK;
}
网友评论