C语言数据结构与算法之单链表

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。本文将为大家介绍C语言中单链表的基本概念与读取数据元素，需要的可以参考一下

基本概念

链表的每一个结点中只包含一个指针域

优点 : 储存空间利用高效

举例来说：

 typedef struct student{ int id;		//学生编号 char* name; //学生名称 //指向下一结点的指针 struct Student* pNext; }Student;

与之相反的是多链表

 typedef struct student{ int id;		//学生编号 char* name; //学生名称 //指向下一结点的指针 struct Student* pNext; struct Student* qNext; }Student;

读取数据元素

获取第i个结点的数据元素

声明一个结点指针p指向链表的第一个结点a1，初始化j从1开始
当j
当链表末尾 p 为空时，则说明第 i 个元素不存在；否则查找成功，返回结点 p 的数据

1.定义数据元素

 //定义数据元素 typedef struct student{ int id; char* name; }ElementType;

2.定义顺序表结构

 typedef struct { ElementType dates[MAX_SIZE];   //当前顺序表中的数据集合 int length;					   //当前顺序表中的元素个数 }SeqList;

3.定义链表的结点（包括数据域和指针域）

 typedef struct Node { ElementType date;  //数据域 struct Node* node; //指针域，指向下一个结点 }Node;

4.设置头结点

我们在定义链表时，习惯性的会定义头结点，以便统一链表结点的插入和删除操作

 typedef struct Linklist { Node* next;  //头指针 int length; }Linklist;

如果链表有头结点，next就指向头结点，没有就指向第一个结点

链表的长度初始值为0

插入数据元素

在第i个结点后插入数据元素

创建一个空节点，分配内存空间，设置数据元素
获取第i个结点，设置新结点的后继结点为该结点的后继结点
设置第i个结点的后继结点为该结点

1.创建空节点并为数据域赋值

 //创建空节点并为数据赋值 Node* node = (Node*)malloc(sizeof(Node)); node -> date = element; node -> next = NULL;

2.通过循环找到要插入的结点

 for (int i = 1; currNode && i next; }

3.将结点插入并对接前面的结点

 if (currNode) { node->next = currNode->next; currNode->next = node; linkList->length++; }

初始化链表

 void InitLinkList(LinkList* linkList, ElementType* dateArrar, int length) { for (int i = 0; i

打印链表

 void PrintLinkList(LinkList* linklist) { Node* node = linklist->next; if (!node) { printf("链表为空！\n"); linklist->length = 0; return 0; } for (int i = 0; i length; i++) { printf("%d\t%s\t\n", node->date.id, node->date.name); node = node->next; } }

顺序表查空

 int IsLinkListEmpty(LinkList* linkList) { return linkList->length == 0 ? TRUE : FALSE; }

顺序表的删除

删除第i个结点及其数据元素

获取第i个结点，若该结点不是第一个结点，则获取第i - 1个结点
将第i -1个结点的后缀结点设为第i个结点的后缀结点
删除第i个结点，释放内存空间，记录并返回删除数据元素的值

情况1：当删除的是第一个元素

 if (pos == 1) { node = linkList->next; if (node) { element = node->date; linkList->next = node->next; free(node);  //释放被删除的结点 linkList->length--; } return element; }

情况2：除第一个结点外

找到要删除的结点和他的前缀结点
要删除结点的next 赋值给前缀结点
释放要删除的结点

 Node* preNode; //前缀结点 node = linkList->next; for (int i = 1; node && i next; } if (node) { element = node->date; preNode->next = node->next; free(node); linkList->length--; } return element;

完整代码

 ElementType DeleteLinkListElement(LinkList* linkList, int pos) { ElementType element;   //被删除的元素 element.id = -999;     //赋一个不可能的值，来判断删除是否成功 Node* node = NULL; if (pos == 1) { node = linkList->next; if (node) { element = node->date; linkList->next = node->next; free(node);  //释放被删除的结点 linkList->length--; } } Node* preNode; //前缀结点 node = linkList->next; for (int i = 1; node && i next; } if (node) { element = node->date; preNode->next = node->next; free(node); linkList->length--; } return element; }

删除单链表整表

声明结点p 和 q
将第一个结点赋值给p
循环将下一个结点赋值给q，释放p，将q赋值给p

 void CleatLinkList(LinkList* linkList) { Node* node = linkList->next; Node* nextNode; while (node) { nextNode = node->next;  //先记录当前结点的下一个结点，以便释放当前结点的内存 free(node); node = nextNode; } linkList->next = NULL; linkList->length = 0; }