单链表操作总结

By | 03月07日
Advertisement

最近工作涉及到很多链表操作,就把它笼统的复习了一遍。
常规的链表操作:

点击(此处)折叠或打开

  1. typedef struct _LIST_NODE_T
  2. {
  3. void *data;
  4. struct _LIST_NODE_T *next;
  5. }LIST_NODE_T;

1.链表逆序

点击(此处)折叠或打开

  1. //已知链表的头节点,将链表逆序----单向链表逆序
  2. LIST_NODE_T resever_list(LIST_NODE_T *head)
  3. {
  4. if(head == NULL || head->next == NULL)
  5. return head;
  6. LIST_NODE_T *p1 = head;
  7. LIST_NODE_T *p2 = p1->next;
  8. LIST_NODE_T *p3 = p2->next;
  9. p1->next = NULL;
  10. while(p3 != NULL)
  11. {
  12. p2->next = p1;
  13. p1 = p2;
  14. p2 = p3;
  15. p3 = p3->next;
  16. }
  17. p2->next = p1;
  18. head = p2;
  19. return head;
  20. }

2.找出链表的中间元素。----一个值得学习的方法。效率o(∩_∩)o

  1. //找出链表的中间元素
  2. LIST_NODE_T* find_midlist(LIST_NODE_T* head)
  3. {
  4. if(head == NULL || head->next == NULL)
  5. return head;
  6. LIST_NODE_T *p1, *p2;
  7. p1 = p2 = head;
  8. while(1)
  9. {
  10. if(p2->next != NULL && p2->next->next != NULL)
  11. {
  12. p1 = p1->next;
  13. p2 = p2->next->next;
  14. }
  15. else
  16. break;
  17. }
  18. return p1;
  19. }

3.将两个有序的链表合并成一个---常规方法

  1. //已知两个链表的head1 和head 各自有序。要求将其合并成一个链表依然有序
  2. LIST_NODE_T* merge(LIST_NODE_T *head1, LIST_NODE_T *head2, int (*pCmpFunc)(void*, void*))
  3. {
  4. if(head1 == NULL)
  5. return head2;
  6. else if(head2 == NULL)
  7. return head1;
  8. if(pCmpFunc == NULL)
  9. return NULL;
  10. LIST_NODE_T *head;
  11. LIST_NODE_T *cur;
  12. LIST_NODE_T *p1;
  13. LIST_NODE_T *p2;
  14. if(pCmpFunc(head1->data, head2->data) < 0)
  15. {
  16. head = head1;
  17. p1 = head1->next;
  18. p2 = head2;
  19. }
  20. else
  21. {
  22. head = head2;
  23. p2 = head2->next;
  24. p1 = head1;
  25. }
  26. cur = head;
  27. while(p1 != NULL && p2 != NULL)
  28. {
  29. if(pCmpFunc(p1->data, p2->data) < 0)
  30. {
  31. cur->next = p1;
  32. cur = p1;
  33. p1 = p1->next;
  34. }
  35. else
  36. {
  37. cur->next = p2;
  38. cur = p2;
  39. p2 = p2->next;
  40. }
  41. }
  42. if(p1 == NULL)
  43. cur->next = p2;
  44. else if(p2 == NULL)
  45. cur->next = p1;
  46. return head;
  47. }

4,将两个有序的链表合并成一个----递归方法

  1. LIST_NODE_T* mergeRecursive(LIST_NODE_T *head1, LIST_NODE_T *head2, int (*pCmpFunc)(void*, void*))
  2. {
  3. if(head1 == NULL)
  4. return head2;
  5. if(head2 == NULL)
  6. return head1;
  7. LIST_NODE_T *head = NULL;
  8. if(pCmpFunc(head1->data, head2->data) < 0)
  9. {
  10. head = head1;
  11. head1->next = mergeRecursive(head1->next, head2, pCmpFunc);
  12. }
  13. else
  14. {
  15. head = head2;
  16. head2->next = mergeRecursive(head1, head2->next, pCmpFunc);
  17. }
  18. return head;
  19. }

5.删除链表中的某个节点

  1. //只给定单链表某个节点p.删除该节点
  2. void deleNode(LIST_NODE_T *pNode, void (*pFreeFunc)(void *))
  3. {
  4. if(pNode == NULL)
  5. return;
  6. if(pNode->next == NULL)
  7. {
  8. if(pFreeFunc != NULL)
  9. pFreeFunc(pNode->data);
  10. delete pNode;
  11. pNode = NULL;
  12. return;
  13. }
  14. LIST_NODE_T pNodeNext = pNode->next;
  15. pNode->data = pNodeNext->data;
  16. pNode->next = pNodeNext->next;
  17. if(pFreeFunc != NULL)
  18. pFreeFunc(pNodeNext->data);
  19. delete pNodeNext;
  20. pNodeNext = NULL;
  21. return;
  22. }

6.在某个节点前插入元素

  1. //只给定单链表中某个节点p。 在p前面插入节点
  2. void insertNode(LIST_NODE_T *pNode, void *data)
  3. {
  4. if(pNode == NULL)
  5. return;
  6. LIST_NODE_T *pNewNode;
  7. pNewNode = new LIST_NODE_T();
  8. if(pNewNode == NULL)
  9. {
  10. std::cout<<"create new node error"<<std::endl;
  11. return;
  12. }
  13. LIST_NODE_T *pNodeNext = pNode->next;
  14. pNode->next = pNewNode;
  15. pNewNode->next = pNodeNext;
  16. pNewNode->data = pNode->data;
  17. pNode->data = data;
  18. }

7.给定单链表头节点,删除链表中倒数第k 个节点

  1. //给定单链表头节点,删除链表中倒数第k 个节点
  2. void deleNode1(LIST_NODE_T * phead, int nReserverK, void(* pFreeFunc)(void *))
  3. {
  4. if(phead == NULL)
  5. return;
  6. LIST_NODE_T *p1, *p2;
  7. p1 = p2 = phead;
  8. for(int i=1; i<=nReserverK; i++)
  9. {
  10. p2 = p2->next;
  11. if(p2 == NULL && i!=nReserverK)
  12. {
  13. return;
  14. }
  15. }
  16. while(p2 != NULL)
  17. {
  18. p1 = p1->next;
  19. p2 = p2->next;
  20. }
  21. deleNode(p1, pFreeFunc);
  22. }

Similar Posts:

  • 1139数据结构上机测试2-2:单链表操作B

     数据结构上机测试2-2:单链表操作B Time Limit: 1000ms   Memory limit: 65536K  有疑问?点这里^_^ 题目描述 按照数据输入的相反顺序(逆位序)建立一个单链表,并将单链表中重复的元素删除(值相同的元素只保留最后输入的一个). 输入 第一行输入元素个数n: 第二行输入n个整数. 输出 第一行输出初始链表元素个数: 第二行输出按照逆位序所建立的初始链表: 第三行输出删除重复元素后的单链表元素个数: 第四行输出删除重复元素后的单链表. 示例输入 10

  • 1138数据结构上机测试2-1:单链表操作A

     数据结构上机测试2-1:单链表操作A Time Limit: 1000ms   Memory limit: 4096K  有疑问?点这里^_^ 题目描述 输入n个整数,先按照数据输入的顺序建立一个带头结点的单链表,再输入一个数据m,将单链表中的值为m的结点全部删除.分别输出建立的初始单链表和完成删除后的单链表. 输入 第一行输入数据个数n: 第二行依次输入n个整数: 第三行输入欲删除数据m. 输出 第一行输出原始单链表的长度: 第二行依次输出原始单链表的数据: 第三行输出完成删除后的单链表

  • 单链表操作的实现

    这次给大家带来一个单链表的C++模板实现.主要有插入(前插,后插,给定值插),删除(主要是给定值删除),倒置,等基本的操作,后续的操作会陆续做出来. 因为模板类比较特殊,分开的文件有的编译器在编译是不会出错,有的编译器会出错,因为我用的编译器,会出错,所以我把定义和实现都在一个文件中实现. 下面是主要的代码: #include<iostream> using namespace std; template <class T> class List { public: /内部节点类,

  • C语言之单链表操作之查找

    二.单链表的基本运算 建立了一个单链表之后,如果要进行一些如插入.删除等操作该怎么办?所以还须掌握一些单链表的基本算法,来实现这些操作.单链表的基本运算包括:查找.插入和删除.下面我们就一一介绍这三种基本运算的算法,并结合我们建立单链表的例子写出相应的程序. 1.查找 对单链表进行查找的思路为:对单链表的结点依次扫描,检测其数据域是否是我们所要查好的值,若是返回该结点的指针,否则返回NULL. 因为在单链表的链域中包含了后继结点的存储地址,所以当我们实现的时候,只要知道该单链表的头指针,即可依次

  • 数据结构实验三 单链表操作

    一. 实验目的1. 掌握握单链表的基本操作:插入.删除.查找等运算.二. 实验要求1. 认真阅读和掌握本实验的程序.2. 上机运行本程序.3. 保存和打印出程序的运行结果,并结合程序进行分析.4. 按照你对单链表的操作需要,重新改写主程序并运行,打印出文件清单和运行结果三. 实验内容单链表基本操作的实现这个程序中演示了单链表的创建.插入.删除和查找.请同学们先自己设计,然后与之对照,有错误的地方请修改:程序如下: #include<malloc.h> typedef struct node{

  • 不带头结点的单链表操作

    typedef int DataType; typedef struct ListNode { DataType data; struct ListNode *pNext; }SL 所有操作: #define _CRT_SECURE_NO_WARININGS 1 #include <stdio.h> #include <assert.h> #include <malloc.h> #include "SList.h" PSListNode BuyNod

  • 数据结构上机测试2-2:单链表操作B

    按照数据输入的相反顺序(逆位序)建立一个单链表,并将单链表中重复的元素删除(值相同的元素只保留最后输入的一个). 输入 第一行输入元素个数n: 第二行输入n个整数. 输出 第一行输出初始链表元素个数: 第二行输出按照逆位序所建立的初始链表: 第三行输出删除重复元素后的单链表元素个数: 第四行输出删除重复元素后的单链表. 示例输入 10 21 30 14 55 32 63 11 30 55 30 示例输出 10 30 55 30 11 63 32 55 14 30 21 7 30 55 11 63

  • [数据结构]基本概念、单链表操作

    1.数据在内存中的存储方式 数据在计算机程序中都是存储在内存空间中的. 连续内存空间,比如申请一个数组,申请内存的大小事先知道.[数组] 非连续内存空间,特点是申请次数无限制,每次固定大小.[链表] 2.时间复杂度和空间复杂度 时间复杂度:同一问题可用不同的算法解决,一个算法的质量优劣将影响算法乃至程序的效率.算法的时间复杂度是一个函数,定量描述算法的运行时间,通常用O表示. 空间复杂度:一个算法在运行过程中占用存储空间大小的度量,包括算法本身所占的存储空间.数据输出数据所占用的存储空间的大学.

  • 单链表操作(增删改查)(version 0.1)

    这天要面试,提前把链表操作重新写了一遍.备份一下,以备不时之需. 希望有人能看到这篇代码,并指正. // File Name : list.h #include "stdafx.h" #include "stdio.h" #include <stdlib.h> #include "string.h" //creat list //creat node //insert //del //find //sort typedef int d

  • 循环单链表操作(转)

    循环单链表的初始化,建立,插入,查找,删除. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 //////////////////////////////////////////////// //循环单链表的初始化,建立,插入,查找,删除.// //Autho

Tags: