首页 > 代码库 > 链表的基本操作

链表的基本操作

2024-08-09 22:01:40   223人阅读

 

链表的基本操作

分类： 数据结构与算法2014-04-09 15:59 8903人阅读 评论(0) 收藏 举报
链表逆序排序销毁增加节点

内容包括链表的创建，增加、删除节点，链表的逆序、排序和销毁等。

 

[cpp] view plaincopy技术分享技术分享
 
  1. #include<stdio.h>  
  2. #include<stdlib.h>  
  3.   
  4. typedef struct node  
  5. {  
  6.     int data;  
  7.     node* pNext;  
  8. }Node;  
  9.   
  10. //链表的操作，以有头节点为例，无头节点类似  
  11. Node* head = NULL;  
  12.   
  13. //创建链表，头结点data=http://www.mamicode.com/0，pNext=NULL;
  14. bool createNodeList()  
  15. {  
  16.     head = (Node*) malloc(sizeof(Node));  
  17.     if(NULL == head)  
  18.     {  
  19.         return false;  
  20.     }  
  21.     else  
  22.     {  
  23.         head->data = 0;  
  24.         head->pNext = NULL;  
  25.         return true;  
  26.     }  
  27. }  
  28.   
  29. //增加节点  
  30. bool addNode(Node* node)  
  31. {  
  32.     if(NULL == head)  
  33.     {  
  34.         return false;  
  35.     }  
  36.     Node* p = head->pNext;  
  37.     Node* q = head;  
  38.     while(NULL != p)  
  39.     {  
  40.         q = p;  
  41.         p = p->pNext;  
  42.     }  
  43.     q->pNext = node;  
  44.     node->pNext = NULL;  
  45.     return true;      
  46. }  
  47.   
  48. //删除节点  
  49. bool deleteNode(int index)  
  50. {  
  51.     if(NULL == head)  
  52.     {  
  53.         return false;  
  54.     }  
  55.     Node* p = head->pNext;  
  56.       
  57.     int length = 0;  
  58.     while(NULL != p)  
  59.     {  
  60.         length ++;  
  61.         p = p->pNext;  
  62.     }  
  63.   
  64.     if(length < index)  
  65.     {  
  66.         return false;  
  67.     }  
  68.     else  
  69.     {  
  70.         Node* q = head;  
  71.         p = head;  
  72.         for(int i=0;i<index;i++)  
  73.         {  
  74.             q = p;  
  75.             p = p->pNext;  
  76.         }  
  77.         Node* t = p->pNext;  
  78.         q->pNext = t;  
  79.         free(p);  
  80.         return true;  
  81.     }  
  82. }  
  83.   
  84. //逆序  
  85. void reverseNodeList()  
  86. {  
  87.     if(NULL == head)  
  88.     {  
  89.         return;  
  90.     }  
  91.     //如果链表长度为1  
  92.     if(head->pNext == NULL)  
  93.     {  
  94.         return;  
  95.     }  
  96.     Node* p = head->pNext;  
  97.     Node* q = p->pNext;  
  98.     Node* t = NULL;  
  99.     while(NULL != q)  
  100.     {  
  101.         t = q->pNext;  
  102.         q->pNext = p;  
  103.         p = q;  
  104.         q = t;  
  105.     }  
  106.     head->pNext->pNext = NULL;  
  107.     head->pNext = p;  
  108. }  
  109.   
  110. //排序(降序)  
  111. void sort()  
  112. {  
  113.     //冒泡排序  
  114.     Node* pHead = head;  
  115.     if(head == NULL)  
  116.     {  
  117.         return;  
  118.     }  
  119.     if(pHead->pNext == NULL)  
  120.     {  
  121.         return;  
  122.     }  
  123.     Node* pi = pHead->pNext;  
  124.     Node* pj = pi->pNext;  
  125.     for(;pi != NULL;pi=pi->pNext)  
  126.     {  
  127.         for(pj = pi->pNext;pj != NULL;pj=pj->pNext)  
  128.         {  
  129.             if(pj->data>pi->data)  
  130.             {  
  131.                 int tmp = pj->data;  
  132.                 pj->data = pi->data;  
  133.                 pi->data = tmp;  
  134.             }  
  135.         }  
  136.     }  
  137. }  
  138. //销毁  
  139. void destroyNodeList()  
  140. {  
  141.     if(NULL == head)  
  142.     {  
  143.         return;  
  144.     }  
  145.     if(NULL == head->pNext)  
  146.     {  
  147.         free(head);  
  148.         head = NULL;  
  149.         return;  
  150.     }  
  151.     Node* p = head->pNext;  
  152.     while(NULL != p)  
  153.     {  
  154.         Node* tmp = p;  
  155.         p = p->pNext;  
  156.         free(tmp);  
  157.     }  
  158.     free(head);  
  159.     head = NULL;  
  160. }  
  161.   
  162. void main()  
  163. {  
  164.     createNodeList();  
  165.   
  166.     Node* node1 = (Node*)malloc(sizeof(Node));  
  167.     node1->data = 1;  
  168.     node1->pNext = NULL;  
  169.   
  170.     Node* node2 = (Node*)malloc(sizeof(Node));  
  171.     node2->data = 2;  
  172.     node2->pNext = NULL;  
  173.   
  174.     addNode(node1);  
  175.     addNode(node2);  
  176.   
  177.     reverseNodeList();  
  178.   
  179.     Node* node3 = (Node*)malloc(sizeof(Node));  
  180.     node3->data = 3;  
  181.     node3->pNext = NULL;  
  182.   
  183.     addNode(node3);  
  184.   
  185.     sort();  
  186.   
  187.     deleteNode(2);  
  188.       
  189.     destroyNodeList();  
  190. }  

链表的基本操作


联系
我们