单链表操做

2021年09月15日 阅读数:2
这篇文章主要向大家介绍单链表操做,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
 
   
   
  1. #include <iostream> 
  2. #include <cstdlib> 
  3. using namespace std; 
  4.  
  5. int LENGTH = 0;            //全局变量用于保存链表的长度         
  6. typedef int ElemType; 
  7. typedef struct LNode 
  8. {   
  9.   ElemType data; 
  10.   LNode        *next; 
  11. }LinkList; 
  12.  
  13. int CreateListF(LinkList *&l, ElemType e[], int length)        //此函数根据传过来的数组,建立一个链表,    参数中有一个为 *&l , 其中&l为一个别名,能够看作是l,而且前面有个指针,则表示是指针变量 
  14.   LinkList *head = NULL,*temp = NULL;             //采用头插法,即新的元素都添加到头位置 
  15.   int loop1 = 0; 
  16.   l = (LinkList *)malloc(sizeof(LinkList)); 
  17.   if(l == NULL) return -1; 
  18.  
  19.   while(loop1 < length) 
  20.   { 
  21.     temp = (LinkList *)malloc(sizeof(LinkList)); 
  22.     if(temp == NULL) return -1; 
  23.     temp->data = e[loop1++]; 
  24.     temp->next = head; 
  25.     head = temp;     
  26.   }   
  27.   l->next = head; 
  28.   LENGTH = length; 
  29.   return 1;                                                                 //若是中间发生了什么问题返回-1,若是运行正常则返回1 
  30.  
  31. int CreateListR(LinkList *&l, ElemType e[], int length) //此函数与上面的惟一的差异是采用的尾插法,把节点插在尾部 
  32.   LinkList *tail = NULL, *temp = NULL; 
  33.   int loop1 = 0; 
  34.   l = (LinkList *)malloc(sizeof(LinkList)); 
  35.   if(l == NULL)    return -1; 
  36.   tail = l; 
  37.   while(loop1 < length) 
  38.   { 
  39.     temp = (LinkList *)malloc(sizeof(LinkList)); 
  40.     if(temp == NULL)    return -1; 
  41.     temp->data = e[loop1++]; 
  42.     temp->next = NULL; 
  43.     tail->next = temp; 
  44.     tail = temp; 
  45.   } 
  46.   tail->next = NULL; 
  47.   LENGTH = length; 
  48.   return 1; 
  49.  
  50. int InsertNode(LinkList *&l, ElemType e, int pos = 0)                 //此函数执行插入操做,若没有指定pos的话,就把元素插到尾部,不然插到指定的位置 
  51.   LinkList *temp = NULL, *value = NULL; 
  52.   int pos1 = 0; 
  53.   if(pos < 0 || pos > LENGTH + 1) return -1; 
  54.   if(pos == 0)              
  55.   { 
  56.     value = l; 
  57.     while(value->next) value = value->next; 
  58.     temp = (LinkList *)malloc(sizeof(LinkList)); 
  59.     if(temp == NULL)    return -1; 
  60.     temp->data = e; 
  61.     temp->next = NULL; 
  62.     value->next = temp; 
  63.     LENGTH++; 
  64.   }else 
  65.   { 
  66.     value = l; 
  67.     while(++pos1 < pos) 
  68.     { 
  69.       value = value->next; 
  70.     } 
  71.     temp = (LinkList *)malloc(sizeof(LinkList)); 
  72.     if(temp == NULL) return -1; 
  73.     temp->data = e; 
  74.     temp->next = value->next; 
  75.     value->next = temp; 
  76.     LENGTH++; 
  77.   } 
  78.   return 1; 
  79.  
  80. int DeleteNode(LinkList *&l, int pos)            //删除指定位置的节点,若是节点的位置不正确则返回-1 
  81.   LinkList *temp = l, *pre = l;     
  82.   int loop1 =0; 
  83.   if(pos < 1 || pos > LENGTH) return -1;   
  84.   while(++loop1 <= pos) 
  85.   { 
  86.     pre = temp; 
  87.     temp = temp->next; 
  88.   } 
  89.   pre->next = temp->next; 
  90.   LENGTH--; 
  91.   free(temp); 
  92.   return 1; 
  93.  
  94. void Merge(LinkList *l1, LinkList *l2, LinkList *&l)                                         //实现两个有序链表的合并,此算法无新意 
  95.   LinkList *temp1 = l1->next, *temp2 = l2->next, *temp = NULL, *tail = NULL; 
  96.   l = (LinkList *)malloc(sizeof(LinkList)); 
  97.   tail = l; 
  98.   while(temp1 != NULL && temp2 != NULL) 
  99.   { 
  100.     if(temp1->data > temp2->data) 
  101.     { 
  102.       temp = (LinkList *)malloc(sizeof(LinkList)); 
  103.       temp->data = temp2->data; 
  104.       temp2 = temp2->next; 
  105.       tail->next = temp; 
  106.       tail = temp; 
  107.     }else if(temp1->data < temp2->data) 
  108.     { 
  109.       temp = (LinkList *)malloc(sizeof(LinkList)); 
  110.       temp->data = temp1->data; 
  111.       temp1 = temp1->next; 
  112.       tail->next = temp; 
  113.       tail = temp; 
  114.     }else  
  115.     { 
  116.       temp = (LinkList *)malloc(sizeof(LinkList)); 
  117.       temp->data = temp2->data; 
  118.       tail->next = temp; 
  119.       tail = temp; 
  120.       temp2 = temp2->next; 
  121.       temp1 = temp1->next; 
  122.     } 
  123.   } 
  124.   if(temp1 == NULL) 
  125.   { 
  126.     while(temp2 != NULL) 
  127.     { 
  128.       temp = (LinkList *)malloc(sizeof(LinkList)); 
  129.       temp->data = temp2->data; 
  130.       temp2 = temp2->next; 
  131.       tail->next = temp; 
  132.       tail = temp; 
  133.     } 
  134.   }else if(temp2 == NULL) 
  135.   { 
  136.     while(temp1 != NULL) 
  137.     { 
  138.       temp = (LinkList *)malloc(sizeof(LinkList)); 
  139.       temp->data = temp1->data; 
  140.       temp1 = temp1->next; 
  141.       tail->next = temp; 
  142.       tail = temp; 
  143.     } 
  144.   } 
  145.   tail->next = NULL; 
  146.  
  147. void DelSame(LinkList *&l)        //此算法是删除重复的值,其中的值按照递增排列,方法是比较先后两个值域是否相等,若是相等则删除后面的节点,不然先后指针都向后退 
  148.   LinkList *pre = l->next; 
  149.   LinkList *temp = pre->next; 
  150.  
  151.   while(pre != NULL && temp != NULL)    //此处应该有temp != NULL 的判断, 由于当temp == NULL 的时候,没有值,会发生非法访问内存操做 
  152.   { 
  153.     if(pre->data == temp->data) 
  154.     { 
  155.       pre->next = temp->next; 
  156.       free(temp); 
  157.       temp = pre->next; 
  158.     }else 
  159.     { 
  160.       pre = pre->next; 
  161.       temp = temp->next; 
  162.     } 
  163.   } 
  164.    
  165.  
  166. void DelSame2(LinkList *&l)                     //此算法是为了删除重复的值,可是此算法与上一个法的区别是,它可以删除不相邻的重复的值 
  167. {                  //实现的思路是先读出一个节点,而后依次查找后面的节点,如相等则删除。     此算法无新意,且时间复杂度为O(n的平方)     不太好 
  168.   LinkList *head = l->next, *pre = NULL, *temp = NULL; 
  169.   while(head != NULL) 
  170.   { 
  171.     pre = head; 
  172.     temp = head->next; 
  173.     while(temp) 
  174.     { 
  175.       if(temp->data == head->data) 
  176.       {  pre->next = temp->next; 
  177.         free(temp); 
  178.         temp = pre->next; 
  179.       }else 
  180.       { 
  181.         pre = pre->next; 
  182.         temp = temp->next; 
  183.       } 
  184.     } 
  185.     head = head->next; 
  186.   } 
  187.  
  188. int maopao(LinkList *&l)                            //本算法的目的是使用冒泡排序法,把链表按照元素的递增顺序排列 
  189.   LinkList *cur = l->next , *min = cur, *temp = cur->next ;                //cur用来变量链表,min指向最小的数据元素的位置    此算法的时间复杂度依旧是n的平方, 不甚好 
  190.   if(cur == NULL || temp == NULL) return -1; 
  191.   while(cur != NULL && temp != NULL) 
  192.   { 
  193.     while(temp != NULL) 
  194.     { 
  195.       if(temp->data < min->data) 
  196.       { 
  197.         min = temp; 
  198.       } 
  199.       temp = temp->next; 
  200.     } 
  201.     if(min != cur)                     //原本min和cur是指向同一个位置的,若是min的指向改变,那么说明找到了一个更小的元素,则进行交换数据操做 
  202.     { 
  203.       cur->data ^= min->data; 
  204.       min->data ^= cur->data; 
  205.       cur->data ^= min->data; 
  206.     } 
  207.     cur = cur->next; 
  208.     min = cur; 
  209.     temp = cur->next; 
  210.   } 
  211.   return 1; 
  212.  
  213. int Reverse(LinkList *&l) 
  214.   LinkList *cur = l->next ,*temp = cur->next ;         //cur与temp的关系是temp指向cur的next指针, 由于后面会改变cur的next指针,因此此处用temp来保存其值 
  215.   l->next = NULL; 
  216.   while(cur != NULL)                                //由于后面的操做,都是关于cur指针的, 因此此处没有判别temp是否到达终点, 当temp到达终点的时候,cur并无到达终点 
  217.   { 
  218.     cur->next = l->next;                    //此处改变了cur的next指针的值,可是temp已经保存其改变以前的指针了 
  219.     l->next = cur; 
  220.     cur = temp;                                        //此处把temp直接赋值为cur 
  221.     if(cur == NULL)    break;                                                                                            //此处很重要由于如当cur为NULL 的时候, temp 已经为NULL了, 若是在temp已经为NULL的状况下执行 temp = temp ->next. 就会引发非法内存发文操做 
  222.     temp = temp->next;                            //把temp向后挪一位 
  223.   } 
  224.   return 1; 
  225. /* 
  226.   此算法的目的是为把链表的元素先后颠倒,可是不许申请 额外的 
  227.   思想是把链表中的元素 一个一个取出来 进行倒插操做,,,,,,,,此算法思想甚好 
  228. */ 
  229.  
  230.  
  231. int Reverse2(LinkList *&l)             //此算法的目的同上 
  232.   LinkList *pre = l->next ,*mid = pre->next, *rear = mid->next; 
  233.   pre->next = NULL; 
  234.   l->next = NULL; 
  235.   while(mid != NULL) 
  236.   { 
  237.     mid->next = pre; 
  238.     pre = mid; 
  239.     mid = rear; 
  240.     rear = rear->next; 
  241.     if(rear == NULL) 
  242.     { 
  243.       mid->next = pre; 
  244.       break
  245.     } 
  246.   } 
  247.   l->next = mid; 
  248.   return 1; 
  249. /* 
  250.   此算法的思想是 用三个指针分别指向 连续的三个链表元素, 而后依次把中间的next指针指向其前面的指针, 而后把这三个指针依次向后移动一位 
  251.   直到最后的一个指针指向NULL 的时候,此时就不须要在循环了, 直接执行大括号里面的语句 而后退出函数便可             
  252. */ 
  253.  
  254.  
  255.  
  256.  
  257.  
  258.  
  259.  
  260. void DispList(LinkList *l) 
  261.   LinkList *temp; 
  262.   temp = l; 
  263.   temp = temp->next; 
  264.   while(temp) 
  265.   { 
  266.     cout<<temp->data<<"    "
  267.     temp = temp->next; 
  268.   } 
  269.   cout<<endl; 
  270.  
  271. int main() 
  272.   int iarr[10] = {1,2,4,3,4,2,5,2,3,5}; 
  273.   int iarr2[7] = {2,4,6,7,9,11,12}; 
  274.   LinkList *l = NULL; 
  275.   LinkList *ll = NULL; 
  276.   LinkList *lll = NULL; 
  277.   CreateListR( l, iarr, 10); 
  278.   CreateListR( ll, iarr2, 7); 
  279. //  DispList(ll); 
  280. /*  InsertNode(l, 9, 6); 
  281.   DispList(l); 
  282.   DeleteNode(l,4); 
  283.   DispList(l); 
  284.  
  285.     Merge(l,ll,lll); 
  286.     DispList(l); 
  287.     DispList(ll); 
  288.     DispList(lll); 
  289.   */ 
  290.   DispList(l); 
  291.     Reverse2(l); 
  292.   DispList(l); 
  293.   return 1;