指针及其应用5——指针链表

简介: 指针及其应用5——指针链表

链表结构

【存储方式的分类】 :顺序存储结构和链式存储结构;

 

【顺序存储结构】 :在(子)程序的说明部分就必须加以说明,以便分配固定大小的存储单 元,直到(子)程序结束,才释放空间。因此,这种存储方式又称为静态存储。所定义的变量相应的称为静态变量。

它的优缺点如下:    

1、优点:可以通过一个简单的公式随机存取表中的任一元素,逻辑关系上相邻的两个元素在物理位置上也是相邻的,且很容易找到前趋与后继元素;    

2、缺点:在线性表的长度不确定时,必须分配最大存储空间,使存储空间得不到充分利用,浪费了宝贵的存储资源;线性表的容量一经定义就难以扩充;在插入和删除线性表的元素时,需要移动大量的元素,浪费了时间;

 

【链式存储结构】 :在程序的执行过程中,通过两个命令向计算机随时申请存储空间或随时释放存储空间,以达到动态管理、使用计算机的存储空间,保证存储资源的充分利用。这样的存储方式称为动态存储。所定义的变量称为动态变量。

它的优点如下:

可以用一组任意的存储单元(这些存储单元可以是连续的,也可以不连续的)存储线性表的数据元素,这样就可以充分利用存储器的零碎空间;

 

【概念】 :为了表示任意存储单元之间的逻辑关系,对于每个数据元素来说,除了要存储它本身的信息(数据域、data)外,还要存储它的直接后继元素的存储位置(指针域、link 或 next)。我们把这两部分信息合在一起称为一个“结点 node”。  

1、N 个结点链接在一起就构成了一个链表。N=0 时,称为空链表。

2、为了按照逻辑顺序对链表中的元素进行各种操作,我们需要定义一个变量用来存储 整个链表的第一个结点的物理位置,这个变量称为“头指针、H 或 head”。也可以把头指针定义成一个结点,称为“头结点”,头结点的数据域可以不存储任何信息,也可以存储线性表的长度等附加信息,头结点的指针域(头指针)存储指向第一个结点的指针,若线性表为 空表,则头结点的指针域为空(NIL)。由于最后一个元素没有后继,所以线性表中最后一个 结点的指针域为空(NIL)。

3、 由于此链表中的每个结点都只包含一个指针域,故称为“线性链表或单链表”。

(一)单链表的定义

1.类型和变量的说明

1. struct Node {
2. int data;
3.     Node *next;
4.  };
5.  Node *p;

2.申请存储单元      

p=new Node;  //动态申请、空间大小由指针变量的基类型决定

3.指针变量的赋值

指针变量名=NULL;  //初始化,暂时不指向任何存储单元

如何表示和操作指针变量?不同于简单变量(如 A=0;),c++规定用“指针变量名->” 的形式引用指针变量(如 P->data=0;)。

 

(二)单链表的结构、建立、输出    由于单链表的每个结点都有一个数据域和一个指针域,所以,每个结点都可以定义成 一个记录。比如,有如下一个单链表,如何定义这种数据结构呢?

下面给出建立并输出单链表的程序,大家可以把它改成过程用在以后的程序当中。

1. #include<iostream>
2. using namespace std;
3. struct Node {
4.  int data;
5.  Node *next; 
6. } ;
7. Node *head,*p,*r;//r指向链表的当前最后一个结点,可以称为尾指针 
8. int x;
9. int main()  
10. {
11.   cin>>x;
12.   head=new Node;//申请头结点 
13.   r=head;
14.   while(x!=-1){//读入的数非-1 
15.     p=new Node;//否者申请一个新结点 
16.     p->data=x;
17.     p->next=NULL;
18.     r->next=p;//把新节点连接到前面的链表中,实际上r是p的直接前趋 
19.     r=p;//尾指针后移一个 
20.     cin>>x;
21.   }
22.   p=head->next;//头指针没有数据,从第一个结点开始就可以了 
23.   while(p->next!=NULL)
24.   {
25.     cout<<p->data<<" ";
26.     p=p->next; 
27.   }
28.   cout<<p->data<<endl;//最后一个结点数据单独输出 
29.   return 0;
30.  }

(三)单链表的操作

1. 查找“数据域满足一定条件的结点”

1. p=head->next; 
2. while((p->data!=x)&&(p->next!=NULL))  p=p->next; //找到第一个就结束 
3. if(p->data==x) 
4.     找到了处理; 
5. else
6.     输出不存在;

如果想找到所有满足条件的结点,则修改如下:

1. p=head->next;
2. while(p->next!=NULL) {       //一个一个判断
3. if(p->data==x)  //找到一个处理一个 ;  
4.     p=p->next;
5.  }

2. 取出单链表的第 i 个结点的数据域

1. void get(Node *head,int i) {
2.     Node *p;
3. int j;
4.     p=head->next;
5.     j=1;
6. while((p!=NULL)&&(j<i)){
7.         p=p->next;
8.         j=j+1;
9.     }
10. if((p!=NULL)&&(j==i))  cout<<p->data;     
11. else  cout<<"i not exsit!";
12. }

3. 插入一个结点在单链表中去

1. void insert(Node *head,int i,int x) //插入 X 到第 i 个元素之前 
2. {  
3.     Node *p,*s;
4. int j;  
5.     p=head;  
6.     j=0;  
7. while((p!=NULL)&&(j<i-1))  //寻找第 i-1 个结点,插在它的后面  
8.     {   
9.         p=p->next;   
10.         j=j+1;     
11.     }  
12. if(p==NULL)    cout<<"no this position!";     
13. else  {   //插入   
14.         s=new Node;   
15.         s->data=x;   
16.         s->next=p->next;   
17.         p->next=s;
18.       } 
19. }

4. 删除单链表中的第 i 个结点(如下图的“b”结点)  

1. void delete(Node *head,int i)  //删除第 i 个元素
2. {    
3.     Node *p,*s;
4. int j;  
5.     p=head;  
6.     j=0;  
7. while((p->next!=NULL)&&(j<i-1)) {   
8.         p=p->next;   
9.         j=j+1;  
10.     }              //p 指向第 i-1 个结点  
11. if (p->next==NULL)    cout<<"no this position!";  
12. else  {       //删除 p 的后继结点,假设为 s   
13.         s=p->next;   
14.         p->next=p->next->next; //或 p->next=s->next   
15. free(s);  
16.     } 
17. }

5. 求单链表的实际长度

1. int len(Node *head) {    
2. int n=0;  
3.     p=head;
4. while(p!=NULL)  {   
5.         n=n+1;   
6.         p=p->next;
7.     }  
8. return n;
9. }

(四)双向链表

每个结点有两个指针域和若干数据域,其中一个指针域指向它的前趋结点,一个指向它 的后继结点。它的优点是访问、插入、删除更方便,速度也快了。但“是以空间换时间”。

【数据结构的定义】

1. struct node{
2.  int data;
3.  node *pre,*next;//pre 指向前趋,next指向后继 
4. }; 
5. node *head,*p,*q,*r;

下面给出双向链表的插入和删除过程。

1. void insert(node *head,int i,int x){//在双向链表的第i个结点之前插入x 
2.  node *s,*p;
3.  int j;
4.  s=new node;
5.  s->data=x;
6.  p=head;
7.  j=0;
8.  while((p->next!=NULL)&&(j<i)){
9.    p=p->next;
10.     j=j+1;
11.   }//p指向第i个结点
12.   if(p==NULL)
13.     cout<<"no this position!";
14.   else {//将s结点插入到结点p之前 
15.     s->pre=p->pre;//将s的前趋指向p的前趋 
16.     p->pre=s;//将s作为p新的前趋 
17.     s->next=p;//将s的后继指向p 
18.     p->pre->next=s;//将P的本来前趋结点的后继指向s 
19.   }  
20. } 
21. void delete(node *head,int i){//删除双向链表的第i个结点 
22.   int j;
23.   node *p;
24.   p=head;
25.   j=0;
26.   while((p->next!=NULL)&&(j<i)){ 
27.     p=p->next;
28.     j=j+1;
29.   }//p指向第i个结点 
30.   if(p==NULL)
31.     cout<<"no this position!";
32.   else{
33.     p->pre->next=p->next;//p的前趋结点的后继赋值为p的后继 
34.     p->next->pre=p->pre;//p的后继结点的前趋赋值为p的前趋 
35.   }
36. }

(五)循环链表

单向循环链表:最后一个结点的指针指向头结点。如下图:

双向循环链表:最后一个结点的指针指向头结点,且头结点的前趋指向最后一个 结点。如下图:

(六)循环链表的应用举例

约瑟夫环问题

【问题描述】   有 M 个人,其编号分别为 1-M。这 M 个人按顺序排成一个圈(如图)。现在给定一个 数 N,从第一个人开始依次报数,数到 N 的人出列,然后又从下一个人开始又从 1 开始依次报数,数到 N 的人又出列...如此循环,直到最后一个人出列为止。

【输入格式】  

输入只有一行,包括 2 个整数 M,N。之间用一个空格分开(0 < n <= m <= 100)。

【输出格式】  

输出只有一行,包括 M 个整数

【样列输入】8 5

【样列输出】5 2 8 7 1 4 6 3

【参考程序】

1. #include<iostream> 
2. using namespace std;
3. struct node{
4.  long d;
5.  node *next;
6. };
7. long n,m;
8. node *head,*p,*r;
9. int main()
10. {
11.   long i,j,k,l;
12.   cin>>n>>m;
13.   head=new node;
14.   head->d=1;
15.   head->next=NULL;
16.   r=head;
17.   for(i=2;i<=n;i++){
18.     p=new node;
19.     p->d=i;
20.     p->next=NULL;
21.     r->next=p;
22.     r=p;
23.   }
24.   r->next=head;
25.   r=head;
26.   for(i=1;i<=n;i++){
27.     for(j=1;j<=m-2;j++) r=r->next;
28.     cout<<r->next->d<<" ";
29.     r->next=r->next->next;
30.     r=r->next;
31.   }
32.   return 0; 
33. }

 

相关文章
|
1月前
链表指针的传参,传值和传地址
本文讨论了链表操作中指针传参的问题,特别是指针的传值与传地址的区别,并提供了修正代码,以确保链表插入操作能正确地修改指针指向的地址。
12 1
链表指针的传参,传值和传地址
|
2月前
|
存储 Java 索引
【数据结构】链表从实现到应用,保姆级攻略
本文详细介绍了链表这一重要数据结构。链表与数组不同,其元素在内存中非连续分布,通过指针连接。Java中链表常用于需动态添加或删除元素的场景。文章首先解释了单向链表的基本概念,包括节点定义及各种操作如插入、删除等的实现方法。随后介绍了双向链表,说明了其拥有前后两个指针的特点,并展示了相关操作的代码实现。最后,对比了ArrayList与LinkedList的不同之处,包括它们底层实现、时间复杂度以及适用场景等方面。
66 10
【数据结构】链表从实现到应用,保姆级攻略
|
2月前
|
传感器 物联网 大数据
C 指针在物联网的应用
在物联网(IoT)中,C 语言及其指针功能广泛应用于嵌入式系统。C 指针在内存管理、设备驱动、数据结构处理、传感器通信等方面发挥关键作用,如动态分配内存、直接访问硬件寄存器、传递复杂数据结构等,有效提升了资源受限环境下的性能和灵活性。通过函数指针和省电模式管理,还能实现事件驱动编程和节能目标,使 C 语言成为 IoT 开发的重要工具。
66 12
|
28天前
|
存储
探索数据结构:单链表的实践和应用
探索数据结构:单链表的实践和应用
|
30天前
|
存储
一篇文章了解区分指针数组,数组指针,函数指针,链表。
一篇文章了解区分指针数组,数组指针,函数指针,链表。
17 0
|
30天前
|
C语言
无头链表二级指针方式实现(C语言描述)
本文介绍了如何在C语言中使用二级指针实现无头链表,并提供了创建节点、插入、删除、查找、销毁链表等操作的函数实现,以及一个示例程序来演示这些操作。
20 0
|
2月前
|
存储 安全 C语言
C语言 二级指针应用场景
本文介绍了二级指针在 C 语言中的应用,
|
2月前
|
前端开发 JavaScript C++
详解链表在前端的应用,顺便再弄懂原型和原型链!
该文章深入解析了链表在前端开发中的应用,并详细阐述了JavaScript中的原型和原型链的概念及其工作原理。
|
3月前
|
算法 Java
双指针在数组遍历中的应用
文章深入探讨了双指针技术在数组遍历中的应用,通过实战例子详细解释了快慢指针和首尾指针的不同用法,并提供了解决LeetCode相关问题的Java代码实现。
|
3月前
|
存储 搜索推荐 C语言
C语言中的指针函数:深入探索与应用
C语言中的指针函数:深入探索与应用