数据结构——链表 Ⅰ_链表结构体定义

一、基本认识

---

1.定义：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

 

 2. 优点：

①插入和删除不必改变其他元素，只需改变指针，复杂度O（1）；

②不用像数组一样需要预先知道数据大小，链表结构可以充分利用计算机内存空间；

3.缺点：

①查找结点或访问结点效率低，需要O（n）的时间；

②增加了结点的指针域，空间开销大；

4.链表的要素

头指针：用来说明链表开始了，头指针指向这个链表，若要访问链表，则要访问头指针；

结点（node）：链表中每一个结构体变量；

尾指针：用来说明链表的结束（它是一个空指针NULL）；

5.链表的分类: 单向链表，双向链表，循环链表；

下文主要介绍单向链表的原理及基本操作的代码实现。

二、单向链表

 类似于火车，可以从车厢一走到车厢二，但是不能往回，因为单向链表只有指向下一个结点地址的指针。

1. 创建一个单链表结点结构体

typedef struct node
{
	int data;
	struct node* next;  // ① 
}Nodes;

//① typedef新定义了一个类型struct node（就像int、double一样），这个指针只能指向struct node这个类型的元素；

2.创建单链表

Nodes* CreatLink(Nodes a[], int n)  //① 
{
	Node *head;
	head=&a[0];                     //② 
	for(int i=0;i<n;i++)
	{
		a[i].next=&a[i+1];
	} 
	a[n-1].next=NULL;               //③ 
	return head;                    //④ 
}

//①这个函数的返回值为Nodes类型的指针，要返回链表实际上就是要返回头指针。这个函数作用是创建一个长度为n数据类型为Nodes的链表；

//②把数组a的第一个元素的地址赋给头指针，让头指针指向第一个结点，然后用循环连接各个结点；

//③末指针设为NULL；

//④返回头指针，实际上代表链表本身；

3.查找/访问链表种的元素

void FindByData(Nodes *head, int ToFindTheData)
{
	Nodes *p=head;   
	while(p!=NULL)
	{
		if(p->data = ToFindTheData)     //①
		{
			break;                     //②
		}
		p=p->next ;                    //③
	}
	if(p==NULL)   cout<<"can't find";
	else cout<<p->data ;
}

 //① 这是比较int型数据的情况，如果要比较字符串类型（比如人名），可以这样写：strcmp（p->data, ToFindTheData）==0；

//②如果找到了就退出循环；

//③只要没找到，就要进行下一次查找，所以p要移动位置；

4.删除链表中的元素

Nodes* DeleteByData(Node *head,int ToDeleteTheData)    //①
{
	Nodes *p,*front;
	while(p!=NULL)
	{
		if(p->data == ToDeleteTheData )
		{
			break;
		}
		front=p;                                      //②
		p=p->next ;
	}
	if(p!=NULL)
	{
		front->next = p->next ;                      
	}
	return head;
}

//①传的第一个参数是告诉计算机我们要在哪个链表里删元素；

//②p移动之前要把p的位置保存下来，这样做的意义是，如果下一个位置是我们要删除的元素A，此时我们需要把A的前面的元素和A的后面的元素连接起来，但是此时p已经变成了p->next，所以需引入front；

5.链表的插入

实际解决问题时，我们会知道应该在哪插入，这里以data的大小为例

Nodes* Insert(Nodes *head,Nodes *aNewNode)
{
	Nodes *p,*front;
	p=head;
	while(p!=NULL && p->data < aNewNode->data)   //① 
	{
		front=p;
		p=p->next;
	}
	if(p==head)                                  //② 
	{
		aNewNode->next=head;
		head=aNewNode;
	}
	else if(p==NULL)                             
	{
		front->next = aNewNode;
		aNewNode->next = NULL;
	}
	else                                         
	{
		front->next = aNewNode;
		aNewNode->next = p;
	}
	return head;
}

//①判断应该在哪里插入

//②退出循环之后检查p的状态