C语言数据结构之单项非循环链表操作增删改查
1、【1】链表的特点：
N个节点离散分配。
每一个节点之间通过指针相连。
每一个节点有一个前驱节点和一个后继节点。
首节点没有前驱节点，尾节点没有后继节点。
【2】
链表前须知：
首节点 ：存放第一个有效数据的节点。
尾节点 ：存放最后一个有效数据的节点。
头指针 ：指向头节点的指针。
尾指针 ：指向尾节点的指针。
头节点 ：在首节点前的另外个结点为头结点。头结点数据域可不存放有效数据，亦可存放链表长度，指针域存放首节点地址，其类型与首节点的数据类型相同，它没有前驱结点，头节点的存在是为了方便链表的操作。
2、【1】创建一个节点，该节点包含两部分数据域和指针域。
数据域是存储该节点的有效数据。
指针域是存储下一个结点的地址。也可为NULL，若为NULL表示该节点为尾结点。
//链表节点
typedef struct Node
{
int dat;//结点值
struct Node *pNext;//下一个结点
}Node, *pNode;
//Node 等效于 struct Node
//*pNode 等效于 struct Node *
3、【1】创建链表。
先为头结点申请内存，并初始化头指针和尾指针指向头结点，且头结点指针域为NULL。
为新结点申请内存，为新结点赋值，新插入的节点为最后个结点，其指针域为NULL。
将最后个结点指针域更新为新插入的结点。
更新最后个结点为新插入的结点。
//创建链表
pNode CreatList(void)
{
pNode newNode = NULL;//新结点指针
pNode endNode = NULL;//尾指针
pNode pHead = NULL;//头指针
int len = 0;//链表长度
int val = 0;//结点值
pHead = (pNode)malloc(sizeof(Node));//为头结点申请内存
if (pHead == NULL)//内存申请失败
{
printf("内存申请失败，程序终止......\r\n");
while (1);
}
//初始化头结点
pHead->pNext = NULL;
endNode = pHead;
printf("请输入链表结点数量: ");
scanf_s("%d", &len);
for (int i = 0; i < len; i++)
{
newNode = (pNode)malloc(sizeof(Node));//为结点申请内存
if (newNode == NULL)//内存申请失败
{
printf("内存申请失败，程序终止......\r\n");
while (1);
}
printf("请输入第%d个结点值: ", i+1);
scanf_s("%d", &val);
newNode->dat = val;//结点值
newNode->pNext = NULL;//新插入的结点为最后个结点
endNode->pNext = newNode;//指向新插入的结点
endNode = newNode;//更新最后个结点
}
return pHead;//头指针
}
【2】判断链表是否为空链表，若头结点指针域为NULL，即该链表为空。
//链表是否为空
bool IsEmpyList(pNode pHead)
{
if (pHead->pNext == NULL)//头结点指针域
return true;
else
return false;
}
【3】显示链表中所有结点值。当其指针域非NULL显示数据域的值，然后继续寻找下一个结点。
//显示链表结点值
void ShowList(pNode pHead)
{
if (IsEmpyList(pHead))
{
printf("链表为空......\r\n");
return;
}
printf("链表元素: ");
pHead = pHead->pNext;//首节点
while (pHead != NULL)//指针域非空
{
printf("%d ", pHead->dat);//结点数据
pHead = pHead->pNext;//下一个结点
}
printf("\r\n");
}
【4】验证链表的创建个显示是否正确。
void main(void)
{
pNode pHead = NULL;//头结点指针
pHead = CreatList();//创建链表
ShowList(pHead);//显示链表元素
while(1);
}
4、【1】获取链表的结点数量。该函数和显示链表结点值功能相识，一个是显示输出一个数量加1。
//链表结点数量
int CountList(pNode pHead)
{
int count = 0;
if (IsEmpyList(pHead))
{
printf("链表为空......\r\n");
return count;
}
pHead = pHead->pNext;//首节点
while (pHead != NULL)//指针域非空
{
count++;//节点数加1
pHead = pHead->pNext;//下一个结点
}
return count;
}
【2】验证获取链表结点数量是否正确。
void main(void)
{
pNode pHead = NULL;//头结点指针
pHead = CreatList();//创建链表
ShowList(pHead);//显示链表元素
printf("链表节点数为: %d\r\n", CountList(pHead));
while(1);
}
5、【1】链表升排序，排序思维和数组排序是一样的。第一个数据和第二个数据比，第一个数据和第三个数据比，依次循环
//链表升排序
void SortRiseList(pNode pHead)
{
pNode p = NULL, q = NULL;
int i = 0, j = 0;
int dat = 0;
int len = 0;
if (IsEmpyList(pHead))
{
printf("链表为空......\r\n");
return;
}
len = CountList(pHead);//链表元素数量
for (i = 0, p = pHead->pNext; i < len - 1; i++, p = p->pNext)
{
for (j = i + 1, q = p->pNext; j < len; j++, q = q->pNext)
{
if (p->dat > q->dat)//交换数据
{
dat = p->dat;
p->dat = q->dat;
q->dat = dat;
}
}
}
}
【2】链表降排序。
//链表降排序
void SortFallList(pNode pHead)
{
pNode p = NULL, q = NULL;
int i = 0, j = 0;
int dat = 0;
int len = 0;
if (IsEmpyList(pHead))
{
printf("链表为空......\r\n");
return;
}
len = CountList(pHead);//链表元素数量
for (i = 0, p = pHead->pNext; i < len - 1; i++, p = p->pNext)
{
for (j = i + 1, q = p->pNext; j < len; j++, q = q->pNext)
{
if (p->dat < q->dat)//交换数据
{
dat = p->dat;
p->dat = q->dat;
q->dat = dat;
}
}
}
}
【3】验证链表升降排序的正确性。
void main(void)
{
pNode pHead = NULL;//头结点指针
pHead = CreatList();//创建链表
ShowList(pHead);//显示链表结点值
printf("链表节点数为: %d\r\n\r\n", CountList(pHead));
printf("升排序");
SortRiseList(pHead);//链表升排序
ShowList(pHead);//显示链表结点值
printf("降排序");
SortFallList(pHead);//链表降排序
ShowList(pHead);//显示链表结点值
while(1);
}
6、【1】向链表中插入新结点。先判断插入位置是否合法，若插入位置合法，则寻找要插入位置的前一个位置，并返回其指针。
//向链表插入结点
void InsertList(pNode pHead, int pos, int value)
{
int i = 0;
pNode newNode = NULL;
if ((pHead == NULL) || (pos < 1) || (pos > CountList(pHead) + 1))
{
printf("插入位置无效......\r\n");
return;
}
while ((pHead != NULL) && (i < pos - 1))
{
pHead = pHead->pNext;
i++;
}
printf("插入位置:%d 插入的值:%d\r\n", pos, value);
newNode = (pNode)malloc(sizeof(Node));//为新结点申请内存
if (newNode == NULL)
{
printf("内存申请失败，程序终止......\r\n");
return;
}
newNode->dat = value;//新结点值
newNode->pNext = pHead->pNext;//新结点指向当前结点的下个结点
pHead->pNext = newNode;//当前结点的下个结点为新插入结点
}
【2】验证向链表指定位置插入某值。
void main(void)
{
pNode pHead = NULL;//头结点指针
pHead = CreatList();//创建链表
ShowList(pHead);//显示链表结点值
printf("链表节点数为: %d\r\n\r\n", CountList(pHead));
printf("升排序");
SortRiseList(pHead);//链表升排序
ShowList(pHead);//显示链表结点值
printf("降排序");
SortFallList(pHead);//链表降排序
ShowList(pHead);//显示链表结点值
printf("\r\n");
InsertList(pHead, 2, 99);
ShowList(pHead);//显示链表结点值
while(1);
}
7、【1】删除链表某位置的结点，其原理和向链表中插入新结点相识，先判断插入位置是否合法，若插入位置合法，则寻找要插入位置的前一个位置，并返回其指针，但记得返回前必须前释放内存，否则会导致内存泄漏。
//删除链表结点
void InsertList(pNode pHead, int pos, int *delVal)
{
int i = 0;
pNode delNode = NULL;
if ((pHead == NULL) || (pos < 1) || (pos > CountList(pHead)))
{
printf("删除位置无效......\r\n");
return;
}
while ((pHead != NULL) && (i < pos - 1))
{
pHead = pHead->pNext;
i++;
}
printf("删除位置:%d 删除的值:%d\r\n", pos, pHead->pNext->dat);
*delVal = pHead->pNext->dat;
delNode = pHead->pNext;
pHead->pNext = pHead->pNext->pNext;
free(delNode);
}
pHead = CreatList();//创建链表
ShowList(pHead);//显示链表结点值
printf("链表节点数为: %d\r\n\r\n", CountList(pHead));
printf("升排序");
SortRiseList(pHead);//链表升排序
ShowList(pHead);//显示链表结点值
printf("降排序");
SortFallList(pHead);//链表降排序
ShowList(pHead);//显示链表结点值
printf("\r\n");
InsertList(pHead, 2, 99);
ShowList(pHead);//显示链表结点值
printf("\r\n");
InsertList(pHead, 3, &delVal);//删除链表结点
ShowList(pHead);//显示链表结点值
while(1);
}
8、所有相关的API和主函数
//链表节点
typedef struct Node
{
int dat;//结点值
struct Node *pNext;//下一个结点
}Node, *pNode;
//Node 等效于 struct Node
//*pNode 等效于 struct Node *
pNode CreatList(void)//创建链表
bool IsEmpyList(pNode pHead)//链表是否为空
void ShowList(pNode pHead)//显示链表结点值
int CountList(pNode pHead)//链表结点数量
void SortRiseList(pNode pHead)//链表升排序
void SortFallList(pNode pHead)//链表降排序
void InsertList(pNode pHead, int pos, int value)//向链表插入结点
void InsertList(pNode pHead, int pos, int *delVal)//删除链表结点
void main(void)
{
pNode pHead = NULL;//头结点指针
int delVal = 0;
pHead = CreatList();//创建链表
ShowList(pHead);//显示链表结点值
printf("链表节点数为: %d\r\n\r\n", CountList(pHead));
printf("升排序");
SortRiseList(pHead);//链表升排序
ShowList(pHead);//显示链表结点值
printf("降排序");
SortFallList(pHead);//链表降排序
ShowList(pHead);//显示链表结点值
printf("\r\n");
InsertList(pHead, 2, 99);
ShowList(pHead);//显示链表结点值
printf("\r\n");
InsertList(pHead, 3, &delVal);//删除链表结点
ShowList(pHead);//显示链表结点值
while(1);
}
