Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

单向链表

物有本末,事有终始 2019-08-23 11:39:00 阅读数:24 评论数:0 点赞数:0 收藏数:0

链表的操作不外乎 增 删 改 查 还能有个额外的打印

1. 头插 , 2.尾插 , 3.中端插入  4.头删  5.尾删 6.中段删除  7.查 8. 改  9.反转打印   10.反转链表   11.判断链表是否有环    12.合并两个有序链表   13.链表排序(选择)

链表节点结构

  typedef struct _T_LINKNODE{ int data; _T_LINKNODE* pNext; }T_LINKNODE, *PT_LNode; 

创建节点并初始化

 PT_LNode creadNode()        //创建节点
 {
     PT_LNode pNew = (PT_LNode)malloc(sizeof(T_LINKNODE));
     init(pNew);
     return pNew;
 }
 
 void init(PT_LNode pHead)    //初始化
 {
     pHead->data = ;
     pHead->pNext = NULL;
 }

 

增 : 头插 尾插  和查找插入 头节点可以用于计数节点个数

1.头插: 新节点的next  指向头节点的next   头节点的next指向新节点  

 int insertHead(PT_LNode pHead, int data) //头插 头节点计数
 {
   if (isEmpty(pHead))
 4   {
     insertBack(pHead, data);
     return ++(pHead->data);
   }
   else
   {
10     PT_LNode pNew = creadNode();
11     pNew->data = data;
12     pNew->pNext = pHead->pNext;
     pHead->pNext = pNew;
     return ++(pHead->data);
   }
 }

 

2.尾插: 创建一个同链表的结构一样的类型指针(不需要malloc)  利用循环找到next指向NULL的指针 , 把指向NULL的指针指向新节点 完成插入.

 int insertBack(PT_LNode pHead, int data) //尾插 头节点计数
 {
   PT_LNode p = pHead;
   while (p->pNext)
   {
 6     p = p->pNext;
   }
 8   PT_LNode pNew = creadNode();
   pNew->data = data;
   p->pNext = pNew;
   return ++(pHead->data);
 }

 

3.查找插入: 先判断要查找的数据是否存在 ,可以利用查找函数返回的指针用作插入 (特殊情况 , 如果满足头插和尾插的条件可以分别调用写好函数插入) 

 

 int insertNode(PT_LNode pHead, int Fdata, int newData)        
 {
     
     PT_LNode tempNode = findData(pHead, Fdata);      //findData在下面
 
     PT_LNode pNew = creadNode();
     pNew->data = newData;
     if ((!tempNode->pNext) && (tempNode->data  == Fdata))
     {
         insertBack(pHead, newData);
     }
     else
     {
         pNew->pNext = tempNode->pNext;
         tempNode->pNext = pNew;
         return ++(pHead->data);
     }
 }

 

删除节点 , 和插入一 一对应 删除的数据返回出来以备不时之需

4.头删除: 使用临时指针 指向要删除的节点 头指针再指向删除节点的next重新链接链表 

 int deleteHead(PT_LNode pHead)
 {
   int temp;
   PT_LNode p = pHead->pNext;
 5   pHead->pNext = p->pNext;
   temp = p->data;
   free(p);
   p = NULL;
   --pHead->data;
   return temp;    
 }

 

5.尾删除: 利用循环找到末尾的上一个节点 直接free掉末尾 , 末尾的上一个节点指向NULL

 int deleteBack(PT_LNode pHead)
 {
   int temp;
   PT_LNode p = pHead; 
   while (p->pNext->pNext)
 6   { 
     p = p->pNext;
   }
   temp = p->pNext->data;
10   free(p->pNext);
   p->pNext = NULL;
   --pHead->data;
   return temp;
 }

 

6.查找删除节点: 找到要删除的当前节点的上一个节点 , 用一个临时节点指向当前节点 , 把当前节点的上一个节点 指向 当前节点的下一个节点 , 再free掉临时节点置空

 int temp;
 PT_LNode p = pHead->pNext;
 while (p->pNext)
 {
 if (p->pNext->data == deleteData)
 {
   break;
 }
   p = p->pNext;
 }
 if ((!p->pNext) && (p->data == deleteData))
 {
   deleteBack(pHead);
 }
 else if ( p == pHead->pNext && p->data == deleteData)
 {
   deleteHead(pHead);
 }
 else
 {
   PT_LNode pTemp = p->pNext;
   p->pNext = pTemp->pNext;
   temp = pTemp->data;
   free(pTemp);
   pTemp->pNext = NULL;
   --pHead->data;
   return temp;
 }

 

7.改之前先查: 遍历所有节点 找到符合条件的节点(要找的数据节点)并返回指向要找节点的指针

 

 PT_LNode findData(PT_LNode pHead, int Fdata)    //返回要查找数据的指针
 {
     PT_LNode p = pHead;
     bool flag = true;
     while (p->pNext)
     {
         if (p->data == Fdata)
         {
             break;
         }
         else
         {
             p = p->pNext;
         }
     }
     (!p->pNext) && (p->data != Fdata) ? flag = false : flag;
     if (flag)
     {
         printf("要查找的数据存在\n");
         return p;
     }
     else
     {
         printf("要查找的数据不存在\n");
         return NULL;
     }
 }

8.改: 利用查找函数返回的指针赋值

 void changeData(PT_LNode pHead, int Fdata, int newData)
 {
     PT_LNode pTemp = findData(pHead, Fdata);
     if (!pTemp)
     {
         printf("数据不存在\n");
         return ;
     }
     else
     {
         pTemp->data = newData;
     }
 }

9.反转打印(递归法)

 void reversalPrint(PT_LNode pHead)
 {
     if (!pHead)
     {
         return;
     }
     reversalPrint(pHead->pNext);
     printf("%d<-", pHead->data);
 }

10.反转链表(递归法) : 递归逐层进入到最里层(递归边界 next == NULL) 再从最里层的next开始逐层向外指后 , 

当前节点制空 并 返回指向当前层的指针(当前节点是pHead)         

 PT_LNode reversalList(PT_LNode pHead)
 {
     if (!pHead->pNext || !pHead)
     {
         return pHead;    
 
     }    
     PT_LNode pTemp = reversalList(pHead->pNext);  //传入当前节点pHead进入递归 并 另存当前节点
     pHead->pNext->pNext = pHead;           //当前节点指向上一个节点
     pHead->pNext = NULL;                //把上一个节点制空
     return pTemp;                    //返回当前节点 , 用作上一层递归
 }

11.判断单链表是否有环  用两个指针都指向头节点 , 从第一个开始p1每次都比p2快一个节点 , 如果有环则会相遇 

 bool judgeCircle(PT_LNode pHead)
 {
     PT_LNode p1, p2;
     p1 = pHead;    p2 = pHead;
     while (p1->pNext && p2->pNext)
     {
         
         p2 = p2->pNext;
         p1 = p1->pNext->pNext;
         if (p1 == p2)
         {
             return true;
         }
     }
     return false;
 }

 12.合并两个有序递增的链表: 1对1   2对2  的比较大小 , 小的先插入新链表以此类推 ,因为链表是有序递增的 比较剩下的一定比插入好的大

            所以依次插入新链表

 PT_LNode mergeList(PT_LNode pHead3, PT_LNode pHead1, PT_LNode pHead2)
 {
     PT_LNode p1 = pHead1;
     PT_LNode p2 = pHead2;
     while (p1 || p2)    //必须两个链表都遍历完
     {
         if (p1 && p2)    
         {
             if (p1->data < p2->data)  //1对1 2对2 彼此对应比较 较小的放前面
             {
                 insertBack(pHead3, p1->data);
                 p1 = p1->pNext;
             }
             else
             {
                 insertBack(pHead3, p2->data);
                 p2 = p2->pNext;
             }
         }
         else        //链表节点数量不相同 , 则把后面的都插入 , 因为是链表已经是有序的 , 前面比较都是比后面的小 , 所以剩余的节点全部依次插入新链表
         {
             while (p1)
             {
                 insertBack(pHead3, p1->data);
                 p1 = p1->pNext;
             }
             while (p2)
             {
                 insertBack(pHead3, p2->data);
                 p2 = p2->pNext;
             }
             break;      //链表遍历完成 退出遍历
         }
     }
     return pHead3;    //返回新链表
 }

 13.链表的排序(选择)  : p1第一次循环把第一个数据和后面的全部一 一比较(满足条件交换)    p1第二次循环把第二个和后面都比较,以此类推 时间复杂度O(n^2)

 void ListSort(PT_LNode pHead)
 {
     PT_LNode p1, p2;
     int temp;
     for (p1 = pHead->pNext; p1->pNext; p1 = p1->pNext)
     {
         for (p2 = p1->pNext; p2; p2 = p2->pNext)
         {
             if (p1->data > p2->data)
             {
                 temp = p1->data;
                 p1->data = p2->data;
                 p2->data = temp;
             }
         }
     }
 }

 

版权声明
本文为[物有本末,事有终始]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/yxnrh/p/11374541.html