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

【1】创建一个节点，该节点包含两部分数据域和指针域。数据域是存储该节点的有效数据。指针域是存储下一个结点的地址。也可为NULL，若为NULL表示该节点为尾结点。//链表节点 typedef struct Node{ int dat;//结点值 struct Node *pNext;//下一个结点}Node, *pNode;//Node   等效于 struct Node//*pNode 等效于 struct Node *

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

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

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

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

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

所有相关的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); }

本人原创经验，仅供参考，若有不足之处请留言指正，若觉得写得好或凑合的话，请点击本页面左下角投票，谢谢了\(^o^)/

若有任何意见与帮助，请关注后私信留言，非喜勿喷

需要相关帮助请投票后关注私信