链表结构

超、凢脫俗 2022-06-08 02:18 324阅读 0赞

《信息学奥赛一本通》：

【存储方式的分类】：顺序存储结构和链式存储结构；

【顺序存储结构】：在（子）程序的说明部分就必须加以说明，以便分配固定大小的存储单元，直到（子）程序结束，才释放空间。因此，这种存储方式又称为静态存储。所定义的变量相应的称为静态变量。它的优缺点如下：

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

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

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

它的优点如下：

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

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

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

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

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

（一）单链表的定义

1．类型和变量的说明

struct Node{
    	int data;//数据域 
    	Node *next;//指针域 
    };
    Node *p;

2．申请存储单元

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

3．指针变量的赋值

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

如何表示和操作指针变量？不同于简单变量（如 A=0；）， c++规定用“指针变量名->”的形式引用指针变量（如 P->data=0；）。

（二）单链表的结构、建立、输出

由于单链表的每个结点都有一个数据域和一个指针域，所以，每个结点都可以定义成一个记录。比如，有如下一个单链表，如何定义这种数据结构呢？

![20170911234224280][]

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

#include<iostream> 
    using namespace std;
    struct Node{
    	int data;//数据阈 
    	Node *next;//指针阈 
    };
    Node *head,*p,*r;//r指向链表的当前最后一个节点，可以称为尾指针
    int x;
    int main()
    {
    	cin>>x;
    	head=new Node;//申请头节点
    	r=head;
    	while(x!=-1)//读入的数非-1
    	{
    		p=new Node;//否则，申请一个新节点
    		p->data=x;
    		p->next=NULL;
    		r->next=p;//把新节点链接到前面的链表中，实际上r是p的直接前驱
    		r=p;//尾指针后移一个 
    		cin>>x; 
    	} 
    	p=head->next;//头指针没有数据，只需要从第一个节点开始就可以了
    	while(p->next!=NULL)
    	{
    		cout<<p->data<<" ";
    		p=p->next; 
    	} 
    	cout<<p->data<<endl;//最后一个节点的数据单独输出 
    	system("pause"); 
    }

![20170912001953089][]

（三）单链表的操作

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

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

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

p=head->next;
    while(p->next!=NULL)//一个一个处理
    {
    	if(p->data==x)//找到一个处理一个 
    	p=p->next;
    }

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

![20170912112424956][]

void get(Node *head,int i)
    {
    	Node *p;
    	int j;
    	p=head->next;
    	j=1;
    	while((p!=NULL)&&(j<i))
    	{
    		p=p->next;
    		j=j+1;
    	}
    	if((p!=NULL)&&(j==i))
    	{
    		cout<<p->data;
    	}
    	else 
    		cout<<i<<" not exsit!";
    }

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

![20170912110443164][]

![20170912111646347][]

[http://www.cnblogs.com/scandy-yuan/archive/2013/01/06/2847801.html][http_www.cnblogs.com_scandy-yuan_archive_2013_01_06_2847801.html]

void insert(Node *head,int i,int x)//插入x到第i个元素之前
    {
    	Node *p,*s;
    	int j;
    	p=head;
    	j=0;
    	while((p!=NULL)&&(j<i-1))//寻找第i-1个结点，插在它的后面
    	{
    		p=p->next;
    		j=j+1;
    	} 
    	if(p==NULL)
    		cout<<"no this position!";
    	else
    	{
    		s=new Node;
    		s->data=x;
    		s->next=p->next;
    		p->next=s;
    	}
    }

4． 删除单链表中的第 i 个结点（如下图的“b”结点）

![20170912112600130][]

![20170912113559164][]

void delete(Node *head,int i)//删除第i个元素
    {
    	Node *p,*s;
    	int j;
    	p=head;
    	j=0;
    	while((p->next!=NULL)&&(j<i-1))
    	{
    		p=p->next;
    		j=j+1;
    	}
    	if(p->next==NULL)
    		cout<<"no this position!";
    	else//删除p的后继结点，假设为s 
    	{
    		s=p->next;
    		p->next=p->next->next;//p->next=s->next;
    		free(s);
    	}
    }

5． 求单链表的实际长度

int len(Node *head)
    {
    	int n=0;
    	p=head;
    	while(p!=NULL)
    	{
    		n=n+1;
    		p=p->next;
    	}
    	return n;
    }

[20170911234224280]: /images/20220608/da3ce29e53824853b083916ac286dd90.png
[20170912001850047]: /images/20220608/cede3f5f45da49ed9ff1324a0f015032.png
[20170912001953089]: /images/20220608/6b88371981d24c47b7b236d9345eabf6.png
[20170912112424956]: /images/20220608/baf0e20a79fd4b28a423b581d7f1a3d0.png
[20170912110443164]: /images/20220608/a5d80e26c6fb4914b33cd80a59c2ce80.png
[20170912111646347]: /images/20220608/e2ea3b506868461783324bca27934dc7.png
[http_www.cnblogs.com_scandy-yuan_archive_2013_01_06_2847801.html]: http://www.cnblogs.com/scandy-yuan/archive/2013/01/06/2847801.html
[20170912112600130]: /images/20220608/5cd783636a4443709055ae6611f77d70.png
[20170912113559164]: /images/20220608/467e1f6a7ef34505a1f20466fc22133b.png