• 单链表


    链表与顺序表的比较:

            (1)顺序表便于访问查询,具有随机存取特性,链表便于插入删除。

            (2)顺序表的存储密度为1,链表的存储密度小于1。

                         存储密度=节点中数据元素所占的存储量 / 节点所占存储量

    初始定义结构体

    1. typedef struct LNode
    2. {
    3. int data;
    4. struct LNode* next;
    5. }LinkNode;

    一.建立单链表

    1.头插法建立单链表 O(n)

    1. void CreateListF(LinkNode*& L, int a[], int n)
    2. {
    3. LinkNode* s;
    4. L = (LinkNode*)malloc(sizeof(LinkNode));
    5. L->next = NULL; //创建头节点,将其next域置为NULL
    6. for (int i = 0; i < n; i++) //循环创建数据节点s,并将其插入到L中
    7. {
    8. s = (LinkNode*)malloc(sizeof(LinkNode)); //创建数据节点s
    9. s->data = a[i];
    10. //将s节点插入原首节点前,头节点后
    11. s->next = L->next;
    12. L->next = s;
    13. }
    14. }

    2.尾插法建立单链表 O(n)

    关键:建立一个节点r,r开始时指向头节点,插入数据后一直指向尾节点。

    1. void CreateListR(LinkNode*& L, int a[], int n)
    2. {
    3. LinkNode* s, * r;
    4. L = (LinkNode*)malloc(sizeof(LinkNode)); //创建头节点
    5. r = L; //r始终指向尾节点,开始时指向头节点
    6. for (int i = 0; i < n; i++) //循环建立数据节点s,并将其插入到L中
    7. {
    8. s = (LinkNode*)malloc(sizeof(LinkNode));//创建数据节点s
    9. s->data = a[i]; //为s赋予数据
    10. r->next = s; //在L尾端插入s
    11. r = s; //更新L尾端指针
    12. }
    13. r->next = NULL; //将尾节点的next域置为NULL
    14. }

    二.单链表的基本运算 

    1.初始化单链表 O(1)

    1. void InitList(LinkNode*& L)
    2. {
    3. L = (LinkNode *)malloc(sizeof(LinkNode));
    4. L->next = NULL; //创建头节点,将其next域置为NULL
    5. }

    2.销毁线性表  O(n)

    1. void DestroyList(LinkNode*& L)
    2. {
    3. LinkNode* pre = L, * p = L->next; //pre指向节点p的前驱节点
    4. while (p != NULL) //遍历单链表
    5. {
    6. free(pre); //释放pre节点
    7. pre = p; //pre、p同步后移一个节点
    8. p = pre->next;
    9. }
    10. free(pre); //循环结束时p为NULL,pre指向尾节点,释放它
    11. }

    3.判断线性表是否为空表 O(1)

    1. bool ListEmpty(LinkNode* L)
    2. {
    3. return(L->next == NULL);
    4. }

    4.求线性表长度  O(n)

    1. int ListLength(LinkNode* L)
    2. {
    3. int n = 0;
    4. LinkNode* p = L; //p指向头节点,n置为0(即头结点的序号为0)
    5. while (p->next != NULL)
    6. {
    7. n++;
    8. p = p->next;
    9. }
    10. return n; //循环结束时,p指向尾节点,其序号n为节点的个数
    11. }

    5.输出线性表  O(n)

    1. void DisplayList(LinkNode* L)
    2. {
    3. LinkNode* p = L->next; //p指向首节点
    4. while (p != NULL)
    5. {
    6. printf("%d", p->data); //p不为NULL,就输出p节点的data域
    7. p = p->next;
    8. }
    9. printf("\n");
    10. }

    注意:

    LinkNode* p=L             为p指向头节点

    LinkNode* p=L->next     为p指向首节点 

    6.按序号求链表中的元素 O(n)

    1. bool GetElem(LinkNode* L, int i, int& e)
    2. {
    3. int j = 0;
    4. LinkNode* p = L; //p指向头节点,j置为0(即头结点的序号为零)
    5. if (i <= 0)return false; //i错误返回假
    6. while (j < i && p!= NULL)
    7. {
    8. j++;
    9. p = p->next;
    10. } //找到第i个节点,循环结束后p可能指向第i个节点,也可能指向NULL
    11. if (p == NULL)
    12. {
    13. return false;
    14. }
    15. else
    16. {
    17. e = p->data;
    18. return true;
    19. }
    20. }

    7.按元素查找位置  O(n)

    1. int LocateElem(LinkNode* L, int e)
    2. {
    3. int i = 1;
    4. LinkNode* p = L->next; //p指向首节点,i置为1(即首节点的序号为1)
    5. while (p != NULL && p->data != e) //查找data值为e的节点,当p的data为e或为查找到时时循环结束
    6. {
    7. p = p->next;
    8. i++;
    9. }
    10. if (p == NULL)
    11. {
    12. return (0);
    13. }
    14. else
    15. {
    16. return i;
    17. }
    18. }

     8.插入数据元素 O(n)

    1. bool ListInsert(LinkNode*& L, int i, int e)
    2. {
    3. int j = 0;
    4. LinkNode* p = L, * s; //p指向头节点,j置为0(即头节点的序号为0),s为创建要被插入元素做准备
    5. //p的作用是标记第i-1个节点的地址,j是标记元素下标,p根据j找到第i-1个节点地址。
    6. if (i < 0)return false; //i错误返回false
    7. while (j < i - 1 && p != NULL)
    8. {
    9. j++;
    10. p = p->next;
    11. } //查找到第i-1个节点,查找第i-1个结点的好处是便于插入操作
    12. //如若查找的是第i个节点,则需在其前面插入,单链表无法指向其前方的元素
    13. if (p == NULL) //未找到第i-1个节点p,返回false
    14. {
    15. return false;
    16. }
    17. else
    18. {
    19. s = (LinkNode*)malloc(sizeof(LinkNode));
    20. s->data = e; //创建新节点s,将其data域置为e
    21. s->next = p->next;
    22. p->next = s; //将s节点插入到p之后
    23. return true;
    24. }
    25. }

    9.删除数据元素 O(n)

    1. bool ListDelete(LinkNode*& L, int i)
    2. {
    3. int j = 0;
    4. LinkNode* p = L, * q; //p指向头节点,j置为0(头结点的序号为0)
    5. if (i <= 0)return false; //i错误返回false
    6. while (j < i - 1 && p != NULL)
    7. {
    8. j++;
    9. p = p->next;
    10. } //查到到第i-1个节点,用p指向该节点,查找到第i-1个节点的好处是便于下面的删除操作
    11. q = p->next; //用q指向p的下一个节点
    12. if (p == NULL || q == NULL) //如果p=NULL,则证明未找到i-1个节点如果q==NULL,则证明要删除的节点为NULL(不存在)
    13. {
    14. return false;
    15. }
    16. else
    17. {
    18. p->next = q->next;
    19. free(q); //删除第i个节点
    20. return true;
    21. }
    22. }

    三.单链表的应用示例 

    1.有一个带头结点的单链表L=(a1,b1,a2,b2,······,an,bn),设计一个算法将其拆分成两个带头结点的单链表L1与L2,其中L1=(a1,a2,a3,·······an),L2=(bn,bn-1,······b1),要求L1使用L的头节点。

    思路:整体建表法。利用原单链表L中的所有节点通过改变其指针域重组成两个单链表L1和L2。由于L1中节点的相对顺序与L中的相同,所以采用尾插法建立单链表L1;由于L2中的节点相对顺序与L中的相反,所以采用头插法建立单链表L2。

    时间复杂度:O(n)

    1. //L1使用尾插法,L2使用头插法
    2. void split(LinkNode*& L, LinkNode*& L1, LinkNode*& L2)
    3. {
    4. LinkNode* p = L->next, * q, * r1; //p指向第一个数据节点
    5. L1 = L; //L1利用原来的L的头节点
    6. r1 = L1; //r1始终指向L1尾节点
    7. L2 = (LinkNode*)malloc(sizeof(LinkNode)); //创建L2的头节点
    8. L2->next = NULL; //置L2的指针域为NULL
    9. while (p != NULL)
    10. {
    11. r1->next = p;
    12. r1 = p; //采用尾插法将p插入L1
    13. p = p->next; //p移动到下一个节点
    14. q = p->next; //q用来记录p的下一个节点
    15. p->next = L2->next;
    16. L2->next = p; //将p连接到L2中
    17. p = q; //p移动到其原来下一个节点位置
    18. }
    19. r1->next = NULL; //L1尾节点的next域置为空
    20. }

     2.设计一个算法,删除单链表L中元素值最大的节点

    思路:双指针法。在单链表中删除一个节点首先要找到它的前驱节点,用指针p遍历整个单链表,pre指向p的前驱节点,在遍历时用maxp指向data域值最大的节点,maxpre指向max节点的前驱节点,当单链表遍历完成后,通过maxpre节点删除其后继节点。

    时间复杂度:O(n)

    1. void delmaxnode(LinkNode*& L)
    2. {
    3. LinkNode* p = L->next, * pre = L, * maxp = p, * maxpre = pre;
    4. //建立四个节点,p用来遍历,pre用来记录p的前一个节点位置,maxp记录元素值最大的节点位置,maxpre用来记录maxp前一节点位置
    5. while (p != NULL)//遍历整个单链表
    6. {
    7. if (maxp->data < p->data)
    8. {
    9. maxp = p; //标记元素最大值的位置
    10. maxpre = pre;
    11. }
    12. pre = p; //推进遍历过程
    13. p = p->next;
    14. }
    15. //删除该元素
    16. maxpre->next = maxp->next;
    17. free(maxp);
    18. }

    3.有一个带头结点的单链表L(至少有一个数据节点),设计一个算法实现所有数据节点按data域递增排序。

    思路:直接插入法。由于单链表L中有一个以上的数据节点,首先构造一个只含头节点和首节点的有序单链表(只含一个数据节点的单链表一定是有序的)。然后遍历单链表L余下的节点(由p指向),在有序单链表中通过比较找插入节点p的前驱节点(由pre指向它),在pre结点之后插入p节点,直到p==NULL为止。

    时间复杂度:O(n*n)

    1. void sort(LinkNode*& L)
    2. {
    3. LinkNode* p, * pre, * q;
    4. p = L->next->next;
    5. L->next->next = NULL;
    6. while (p != NULL)
    7. {
    8. q = p->next; //用q记录p下一个结点的位置
    9. pre = L; //pre找寻L中比p的data域值小的节点的前驱地址
    10. while (pre->next != NULL && pre->next->data < p->data)//寻找过程
    11. {
    12. pre = pre->next;
    13. }
    14. //找到后插入
    15. p->next = pre->next;
    16. pre->next = p;
    17. //p回到其下一个位置
    18. p = q;
    19. }
    20. }
  • 相关阅读:
    手机转接器实现原理,低成本方案讲解
    程序员的孤独你不懂
    python入门系列(1)—— 环境安装
    如何设计分布式系统-分布式事务-TCC?
    [附源码]计算机毕业设计JAVAjsp宠物店管理系统
    力扣labuladong——一刷day33
    丁鹿学堂:js进阶之异步解决方案:generator迭代器
    STM32G0 定时器PWM DMA输出驱动WS2812配置 LL库
    MIKE水动力笔记12_数字化海图1之提取确值水深点
    年产200万件的超级工厂投产!巨头「闭环」汽车电子全产业链
  • 原文地址:https://blog.csdn.net/qq_64585761/article/details/127098097