链表排序、链表删除、访问倒数第k个节点

心已赠人 2022-08-02 02:27 254阅读 0赞

1.设一个带头结点的单向链表的头指针为head，设计算法，将链表的记录，按照data域的值递增排序。

2.已知线性表中的元素以单链表作存储结构。试写一算法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删除结点空间。

3.输出该链表中倒数第k个结点， tail为倒数第0个节点

  1. //
  3. #include "stdafx.h"
  4. #include<iostream>
  5. using namespace std;
  6. template<class T>
  7. struct Node{
  8.     T value;
  9.     Node*next;
  10. };
  12. template<class T>
  13. class list
  14. {
  15. private:
  16.     Node<T>*head;
  17.     Node<T>*tail;
  18.     int len;//链表长度
  19. public:
  20.     list();
  21.     Node<T>*append(T ele);
  22.     Node<T>*findKthfromhead(int k);
  23.     Node<T>*findKthfromtail(int k);
  24.     Node<T>*sort_list(int endpos);//链表排序
  25.     Node<T>*delete_list(T x, T y);//删除表中所有大于x且小于y的元素（若表中存在这样的元素）
  26.     Node<T>*reverse_list();//反转
  28. Node<T>*list<T>::delete_exist();//删除重复元素
  30. int length();
  31. };
  33. template<class T>
  34. Node<T>*list<T>::reverse_list()
  35. {
  36. <span style="white-space:pre">    </span>int k1 = length()-1;
  37. <span style="white-space:pre">    </span>int k2 = 0;
  38. <span style="white-space:pre">    </span>while (k1 - k2 > 0)
  39. <span style="white-space:pre">    </span>{
  40. <span style="white-space:pre">        </span>int mm;
  41. <span style="white-space:pre">        </span>mm = findKthfromhead(k1)->value;
  42. <span style="white-space:pre">        </span>findKthfromhead(k1)->value = findKthfromhead(k2)->value;
  43. <span style="white-space:pre">        </span>findKthfromhead(k2)->value = mm;
  44. <span style="white-space:pre">        </span>--k1;
  45. <span style="white-space:pre">        </span>++k2;
  46. <span style="white-space:pre">    </span>}
  49. <span style="white-space:pre">    </span>return head;
  50. }
  51. template<class T>
  52. Node<T>*list<T>::delete_list(T x, T y)
  53. {
  54.     _ASSERT(y > x);
  55.     _ASSERT(len > 0);
  57.     sort_list(len - 1);
  58.     if (head->value >= y || tail->value <= x)
  59.         return head;
  60.     if (head->value > x)
  61.     {
  62.         Node<T>*m = new Node < T >;
  63.         while (head->value < y)
  64.         {
  65.             Node<T>*node = new Node < T > ;
  66.             node = head;
  67.             if (head->next == NULL)
  68.             {
  69.                 head = NULL;
  70.                 len = 0;
  71.                 return head;
  72.             }
  73.             head->value = head->next->value;
  74.             head = head->next;
  75.             --len;
  76.             delete node;
  77.         }
  78.         return head;
  79.     }
  81.     Node<T>*node = new Node < T >;
  82.     Node<T>*m = new Node < T >;
  83.     node = head;
  84.     while (node->value <= x)
  85.     {
  86.         m = node;
  87.         m->value = node->value;
  88.         node = node->next;
  89.     }
  92.     while (node->value < y)
  93.     {
  94.         Node<T>*n = new Node < T > ;
  95.         n = node;
  96.         if (node->next == NULL)
  97.         {
  98.             m->next = NULL;
  99.             tail = m;
  100.             --len;
  101.             return head;
  102.         }
  103.         node->value = node->next->value;
  104.         node = node->next;
  105.         --len;
  106.         delete n;
  107.     }
  108.     m->next = node;
  110.     return head;
  111. }
  112. template<class T>
  113. Node<T>*list<T>::sort_list(int endpos)//递归实现排序
  114. {
  115.     int k = 0;
  116.     int pp;
  117.     if (endpos == 0)
  118.         return head;
  119.     Node<T>*node = new Node < T >;
  120.     node = head;
  121.     while (k < endpos)
  122.     {
  123.         if (node->value > node->next->value)
  124.         {
  125.             pp = node->value;
  126.             node->value = node->next->value;
  127.             node->next->value = pp;
  128.         }
  129.         ++k;
  130.         node = node->next;
  131.     }
  132.     --endpos;
  133.     sort_list(endpos);
  134.     //delete node;
  135. }
  137. template<class T>
  138. Node<T>*list<T>::findKthfromhead(int k)
  139. {
  140.     //if (len == 0)
  141.     //    return NULL;
  142.     _ASSERT(k < len);
  143.     Node<T>*KthNode = new Node < T > ;
  144.     KthNode = head;
  145.     while (k)
  146.     {
  147.         KthNode = KthNode->next;
  148.         --k;
  149.     }
  151.     return KthNode;
  152. }
  154. template<class T>
  155. Node<T>*list<T>::findKthfromtail(int k)
  156. {
  157.     _ASSERT(k < len);
  159.     return findKthfromhead(len-1-k);
  160. }
  162. template<class T>
  163. int list<T>::length()
  164. {
  165.     return len;
  166. }
  168. template<class T>
  169. Node<T>*list<T>::append(T ele)
  170. {
  171.     if (head == NULL)
  172.     {
  173.         head = new Node < T > ;
  174.         tail = new Node < T >;
  175.         head->value = ele;
  176.         head->next = NULL;
  177.         tail->value = ele;
  178.         tail->next = NULL;
  179.         len = 1;
  180.         return head;
  181.     }
  182.     if (head->next == NULL)
  183.     {
  184.         head->next = tail;
  185.         tail->value = ele;
  186.         tail->next = NULL;
  187.         len = 2;
  188.         return head;
  189.     }
  190.     else
  191.     {
  192.         Node<T>*node = new Node < T > ;
  193.         node->next = NULL;
  194.         node->value = ele;
  195.         tail->next = node;
  196.         tail = node;
  197.         ++len;
  198.         return head;
  199.     }
  200. }
  202. template<class T>
  203. list<T>::list()
  204. {
  205.     head = NULL;
  206.     tail = NULL;
  207.     len = 0;
  208. }
  209. template<class T>
  210. Node<T>*list<T>::delete_exist()
  211. {
  212. <span style="white-space:pre">    </span>sort_list(len - 1);
  213. <span style="white-space:pre">    </span>
  214. <span style="white-space:pre">    </span>Node<T>* node,*n,*m;
  217. <span style="white-space:pre">    </span>n=node = head;
  218. <span style="white-space:pre">    </span>
  219. <span style="white-space:pre">    </span>while (node->next != NULL)
  220. <span style="white-space:pre">    </span>{
  221. <span style="white-space:pre">        </span>
  222. <span style="white-space:pre">        </span>if (node->value == node->next->value)
  223. <span style="white-space:pre">        </span>{
  224. <span style="white-space:pre">            </span>while (node->next != NULL&&node->value == node->next->value)
  225. <span style="white-space:pre">            </span>{
  226. <span style="white-space:pre">                </span>m = node;
  227. <span style="white-space:pre">                </span>node = node->next;
  230. <span style="white-space:pre">                </span>delete m;
  231. <span style="white-space:pre">                </span>--len;
  232. <span style="white-space:pre">            </span>}
  233. <span style="white-space:pre">            </span>n->next = node;
  234. <span style="white-space:pre">            </span>node = node->next;
  235. <span style="white-space:pre">            </span>
  236. <span style="white-space:pre">        </span>}
  237. <span style="white-space:pre">        </span>else
  238. <span style="white-space:pre">        </span>{
  239. <span style="white-space:pre">            </span>n = node;
  240. <span style="white-space:pre">            </span>node = node->next;
  243. <span style="white-space:pre">        </span>}
  244. <span style="white-space:pre">    </span>}
  245. <span style="white-space:pre">    </span>/*
  246. <span style="white-space:pre">    </span>while (node->next != NULL)
  247. <span style="white-space:pre">    </span>{
  250. <span style="white-space:pre">        </span>m = n->next;
  251. <span style="white-space:pre">        </span>m->value = n->next->value;
  252. <span style="white-space:pre">        </span>while (n->value == n->next->value)
  253. <span style="white-space:pre">        </span>{
  256. <span style="white-space:pre">            </span>m = n;
  257. <span style="white-space:pre">            </span>m->value = n->value;
  258. <span style="white-space:pre">            </span>n->value = n->next->value;
  259. <span style="white-space:pre">            </span>n = n->next;
  260. <span style="white-space:pre">            </span>if (n->next == NULL)
  261. <span style="white-space:pre">            </span>{
  262. <span style="white-space:pre">                </span>//delete m;  
  263. <span style="white-space:pre">                </span>--len;
  264. <span style="white-space:pre">                </span>return head;
  265. <span style="white-space:pre">            </span>}
  266. <span style="white-space:pre">            </span>//delete m;  
  267. <span style="white-space:pre">            </span>--len;
  268. <span style="white-space:pre">        </span>}
  269. <span style="white-space:pre">        </span>node->next = m;
  270. <span style="white-space:pre">        </span>node->next->value = m->value;
  273. <span style="white-space:pre">        </span>n = n->next;
  274. <span style="white-space:pre">        </span>n->value = n->next->value;
  275. <span style="white-space:pre">    </span>}
  276. <span style="white-space:pre">    </span>*/
  279. <span style="white-space:pre">    </span>return head;
  282. }
  283. int _tmain(int argc, _TCHAR* argv[])
  284. {
  285.     list<int>aa;
  286.     aa.append(6);
  287.     cout <<"长度为"<< aa.length() << endl;
  288.     aa.append(5);
  289.     cout << "长度为" << aa.length() << endl;
  290.     aa.append(4);
  291.     cout << "长度为" << aa.length() << endl;
  292.     aa.append(3);
  293.     cout << "长度为" << aa.length() << endl;
  294.     aa.append(2);
  295.     cout << "长度为" << aa.length() << endl;
  296.     cout <<"第三个数为"<< aa.findKthfromhead(3)->value << endl;
  297.     cout << "倒数第三个数为" << aa.findKthfromtail(3)->value << endl;
  298.     aa.sort_list(aa.length() - 1);
  299.     //aa.delete_list(1, 7);
  300.     aa.delete_list(1, 4);
  301.     cout << "长度为" << aa.length() << endl;
  302.     for (int i = 0; i < aa.length(); i++)
  303.         cout << aa.findKthfromhead(i)->value << endl;
  305.     system("pause");
  306.     return 0;
  307. }

发表评论

表情：
评论列表 （有 0 条评论，254人围观）

还没有评论，来说两句吧...

相关阅读

    相关 链表中倒数第K个节点

    输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2

    偏执的太偏执、偏执的太偏执、/ 0 赞/ 94 阅读

    相关 链表中倒数第k个节点

    链表中倒数第k个节点 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节

    末蓝、末蓝、/ 0 赞/ 285 阅读