数据结构之链表

简介:

(本文参考《剑指offer》总结笔记,供学习使用)

    链表是一种动态数据结构,是因为在创建链表的时候,无须知道链表的长度。当插入一个结点时,我们只需要为新结点分配内存,然后调整指针的指向来确保新节点被链接到链表当中。由于没有闲置的内存,链表的空间效率比数组高。


    单向链表的结点定义为:

1
2
3
4
5
struct  ListNode
{
     int         m_nValue;
     ListNode*    m_pNext;
};

例:向链表中插入数据

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
52
53
54
55
56
57
58
59
60
61
62
63
#include<stdio.h>
struct  ListNode
{
     int  m_nValue;
     ListNode* m_pNext;
};
void  createListNode(ListNode** pHead, int  n);
void  addToTail(ListNode** pHead,  int  value);
void  printList(ListNode** pHead);
void  main(){
     //建立头结点
     ListNode* pHead= new  ListNode();
 
     //创建链表,需要指定创建几个结点
     createListNode(&pHead,5); //这里需要注意的是,传递的头结点是一个指针的地址。在createListNode函数中传递了pHead,当我们向一个空链表中插入一个结点的时候,新插入的结点就是链表的头指针。由于此时会改动头指针,因此必须把pHead参数设为指向指针的指针,否则出了传递参数的函数pHead仍然是一个空指针
     
     //往链表的结尾添加一个结点
     printf ( "向链表中插入结点:10\n" );
     addToTail(&pHead,10);
 
     printf ( "输出链表为:\n" );
     printList(&pHead);
}
void  addToTail(ListNode** pHead,  int  value)
{    
     ListNode* pNew= new  ListNode();
     pNew->m_nValue=value;
     pNew->m_pNext=NULL;
     
     if (*pHead==NULL)
         *pHead=pNew;
     else
     {
         ListNode* pNode=*pHead;
         while (pNode->m_pNext!=NULL)
             pNode=pNode->m_pNext;
         pNode->m_pNext=pNew;
     }    
}
void  createListNode(ListNode** pHead, int  n){
     //这里需要注意的是,传递的头结点是一个指针的地址。在createListNode函数中传递了pHead,当我们向一个空链表中插入一个结点的时候,新插入的结点就是链表的头指针。由于此时会改动头指针,因此必须把pHead参数设为指向指针的指针,否则出了传递参数的函数pHead仍然是一个空指针
     int  x=0;
     ListNode* pNode=*pHead;
     printf ( "please input first ListNode number:" );
     scanf ( "%d" ,&pNode->m_nValue);
     pNode->m_pNext=NULL;
     for ( int  i=1;i<n;i++){
         printf ( "please input %d number:" ,i+1);
         ListNode* pNew= new  ListNode();
         scanf ( "%d" ,&x);
         pNew->m_nValue=x;
         pNew->m_pNext=pNode->m_pNext;
         pNode->m_pNext=pNew;
     }
}
void  printList(ListNode** pHead){
     ListNode* pNode=*pHead;
     while (pNode->m_pNext!=NULL){
         printf ( "%d->" ,pNode->m_nValue);
         pNode=pNode->m_pNext;
     }
     printf ( "%d\n" ,pNode->m_nValue);
}


例:往链表的结尾添加一个结点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void  AddToTail(ListNode** pHead,  int  value)
     //pHead是一个指向指针的指针。因为当我们往一个空链表中插入一个结点时,新插入的结点是链表
     //的头指针。由于此时会改动头指针,因此必须把pHead参数设为指向指针的指针,否则出了这个函数
     //pHead仍然是一个空指针。
     
     ListNode* pNew= new  ListNode();
     pNew->m_nValue=value;
     pNew->m_pNext=NULL;
     
     if (*pHead==NULL)
         *pHead=pNew;
     else
     {
         ListNode* pNode=*pHead;
         while (pNode->m_pNext!=NULL)
             pNode=pNode->m_pNext;
         pNode->m_pNext=pNew;
     }    

    注:由于链表中的内存不是一次性分配的,因此我们无法保证链表和数组一样是连续的。



例:从尾到头打印链表

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
//使用栈结构打印链表
void  PrintListReversingly_Iteratively(ListNode* pHead)
{
     std::stack<ListNode*> nodes;
 
     ListNode* pNode = pHead;
     while (pNode != NULL)
     {
         nodes.push(pNode);
         pNode = pNode->m_pNext;
     }
 
     while (!nodes.empty())
     {
         pNode = nodes.top();
         printf ( "%d\t" , pNode->m_nValue);
         nodes.pop();
     }
}
 
 
//使用递归打印链表
void  PrintListReversingly_Recursively(ListNode* pHead)
{
     if (pHead != NULL)
     {
         if  (pHead->m_pNext != NULL)
         {
             PrintListReversingly_Recursively(pHead->m_pNext);
         }
  
         printf ( "%d\t" , pHead->m_nValue);
     }
}

注:基于递归代码简洁,但是当链表非常长的时候,就会导致函数调用层级很深,从而有可能导致函数调用栈溢出。显示用栈基于循环实现的代码鲁棒性更好。


本文转自 叫我北北 51CTO博客,原文链接:http://blog.51cto.com/qinbin/1919695


相关文章
|
1月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
53 4
|
22天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
43 5
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
83 4
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
47 0
|
2月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
29 7
|
2月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
27 3
|
2月前
|
算法 Java
数据结构与算法学习五:双链表的增、删、改、查
双链表的增、删、改、查操作及其Java实现,并通过实例演示了双向链表的优势和应用。
21 0
数据结构与算法学习五:双链表的增、删、改、查
【数据结构】——双向链表详细理解和实现
【数据结构】——双向链表详细理解和实现