C语言数据结构之单项非循环链表操作增删改查

2025-04-22 12:37:29

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); }

声明：本网站引用、摘录或转载内容仅供网站访问者交流或参考，不代表本站立场，如存在版权或非法内容，请联系站长删除，联系邮箱：site.kefu@qq.com。