Buer blog | 详情

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 链表由一系列节点(链表中的每一个元素称为节点)组成，节点可以再运行时动态生成，克服了数组需要预先知道数据量大小的缺点。每个节点包括两个部分：一个是存储数据元素的数据域，另一个时存储相邻节点地址的指针域。

特性

根据指针域的不同，链表可分为单向链表和双向链表，单向链表中各节点只记录后继元素的地址，双向链表的节点会记录前驱、后继两个节点的地址。相较于线性表的顺序结构，链表操作复杂。由于不必按顺序存储，链表在插入的时候可以达到O ( 1 )的复杂度，比线性表快得多，但是查找一个节点或者访问特定编号的节点则需要O ( n )的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O ( 1 )。

物理结构物理结构

链表使用链式存储方式存储数据，便于插入和删除，遍历方面可以通过ST表等进行优化。竞赛中链表的插入和删除操作顺序时常考点。

例题：例1 向一个栈顶指针为hs 的链式栈中插入一个指针s指向的节点时，应执行( )。 A.hs->next = s ; B.s->next = hs ; hs = s ; C.s->next = hs->next ; hs->next = s ; D.s->next = hs ; hs = hs->next ; 【正确答案】b 解析：为栈顶元素next指针赋值就是入栈操作，入栈后应记得更新栈顶指针。

例2 双向链表中有两个指针域llink和rlink，分别指向前驱与后继。设p指向链表中的一个节点，q指向一待插入节点，现要求在p前插入q，则正确的插入为( )。

A.p->llink=q;q->rlink=p;p->link->rlink=q;q->llink =p->llink;

B.g->llink=p->llink;p->llink->rlink=q;q->rlink=p;p->llink =q->rlink;

C.q->rlink=p;p->rlink=q;p->llink->rlink=q;q->rlink=p;

D.p->llink->rlink=q;q->rlink=p;q->llink=p->llink;p->llink =q;

**【正确答案】D

解析:插入新节点时，需要注意改变指针指向时不要弄丢节点(p->llink)。**

例3 链表不具有的特点是( )。

A.可随机访问任一元素。

B.不必事先估计存储空间。

C.插入和删除不需要移动元素。

D.所需空间与线性表长度成正比。

【正确答案】A 解析:根据链表的概念可知。

例4 从一个具有 n 个结点的单链表中查找其值等于 x 结点时，在查找成功的情况下，需平均比较（）个结点。 A.n B.n/2 C.(n-1)/2 D.(n+1)/2 **【正确答案】D

解析：n=1和n=n，1+n的和除以2

链表的代码

#include<bits/stdc++.h> 
using namespace std;
//创建和遍历链表3
//指针、结构体（创建） 
struct Node{
	int data;//值域 
	Node *next;//指针域，指向下一个 
};
//继续创建三个指针 指向链表的头head，指向链表尾 tail 
//在链表中游走的指针 p 
Node *head,*tail,*p; 
int x;
void inst(int key,int pos); 
void del(int data); 
int main(){
	//创建链表，不停增加结点，直到输入的值为-1时，输出链表
	cin>>x; 
	//声明一个结点，因为是第一个声明的结点，所以必须是头结点head 
	head = new Node;// 产生一个Node结点
	tail = head;//因为初始结点，头和尾结点都是一个 
	while(x!=-1)
	{
		p=new Node;//创建结点，将p指向这个新建的结点
		p->data = x; 
		tail->next = p; 
		tail = p;
		tail->next = NULL;//最后一个结点的尾部没有了
		cin>>x; 
	}
	del(8);//调用删除方法 
	inst(21,4);//调用插入方法 
	//遍历链表输出
	if(head->next!=NULL){ 
		p = head->next; 
		while(p->next!=NULL) 
		{
			cout<<p->data<<" ";
			p=p->next;//将p移到下一个结点
		}
		cout<<p->data;//因为前面输出的时候跳过了一个结点 
	}else{
		cout<<"空链表";
	}
	return 0;
} 

//链表的删除  
void del(int key){
	Node *pre;//寻找符合条件结点的前驱
	p=head;pre=p;
	//判断p是否已经移到尾结点	
	while(p->next!=NULL) {
		if(p->data==key){
			//符合条件的结点p的前驱结点pre
			//pre的后继指向p的后继		 
			pre->next=p->next;
			delete p;//释放p所指向的结点
			p=pre->next;	
		}else{//当前的结点值不为key，指针p继续往前走 
			pre=p; 
			p=p->next;
		}
	}
	//while 循环完成之后，p指向的是最后一个结点，需要单独拿出来处理	
	if(p->data==key){
		delete p;//删除最后一个结点后，pre就是最后一个结点了 
		pre->next=NULL;//所以pre的后继应该为NULL 
	}
	 
} 
//在指定位置，插入结点
// pos 指定位置 
void inst(int data,int pos){
	//*pre 前驱结点的指针 
	Node *pre,*np;
	p=head;pre=p;
	//用来记录当前结点是第几个结点 
	int k=0; 
	while(p->next!=NULL){
		p=p->next;
		k++;
		//当前结点到达指定插入结点的位置时		
		if(k==pos){
			np=new Node;
			np->data=data;
			np->next=p;
			pre->next=np;
			break;
		}else{
			pre=p;
		}
	}
	//如果链表中已有的结点不足时 
	if(k<pos){
		np=new Node;
		np->next=NULL;
		np->data=data;
		p->next=np;
	}
}

#include<stdio.h> 
#include<stdlib.h>
 
//单链表  
typedef struct student{ 
	//data是数据域 
	int data; 
	//next是指针域，用于存放单链表指向的下一个链表的地址 
	struct student* next; 
}student;
 
//双向链表  
typedef struct two_student{ 
	//数据域 
	int data; 
	//前驱指针 
	struct two_student* last; 
	//后驱指针 
	struct two_student* next; 
}two_student;

//循环链表： 
void forList( student* p,student* head ) { 
	//如果给的地址是最后一个节点，那么让它指向头节点 
	if( p == NULL ) 
	{ 
		p->next = head; 
	} 
} 

//链表的初始化 
student* start() 
{ 
	//申请一片地址用来存放新开辟的结构体 
	student* tmp = (student*)malloc(sizeof(student)); 
	//刚开辟时，结构体的长度只有1，所以后面不连接结构体，结构体指向空地址 
	tmp->next = NULL; 
	//返回结构体地址 
	return tmp; 
}

//链表动态分配节点，写入数据，传入的data即是你要给结构体内储存的数据。
student* newlist(int data)
{ 
	//动态申请内存，由于tmp是局部变量，所以和start里的tmp不冲突使用
	student* tmp = (student*)malloc(sizeof(student)); 
	//把想要传递的数据通过tmp来赋值 
	tmp->data = data; 
	//确保当前创建的节点是全新节点没有任何链接，方便后续操作 
	tmp->next = NULL; 
	//判断是否创建成功： 
	//malloc如果因为内存不够等原因无法开辟空间，会返回NULL 
	if ( tmp == NULL ) 	{ 
		//给出错误信息 
		printf("开辟空间失败"); 
		//返回空地址 
		return NULL; 
	} 
	else{ 
		//创建成功则返回创建的结构体 
		return tmp; 
	} 
}
 
//链表的遍历输出
void prlist(student* L)
{
	//第一次写这里报错了，大家一定要记住写地址的时候每个变量都需要星号
	student* p, * q;
	//这里的意思是，从L地址开始遍历
	p = L;
	//检测到下一个地址为空即意味着走到了最后一个节点，此时结束
	while ( p->next != NULL )
	{
		q = p->next;
		printf("%d",p->data);
		p = p->next;
	}
}

//头插法创建链表
student* head_newlist(int data[],int n)
{
	//创建头节点
	student* head = (student*)malloc(sizeof(student));
	//给头节点的指针域置空
	head->next = NULL;
	//创建后续节点
	for( int i = 0 ; i < n ; i++ )
	{
		//创建一个节点
		student* node = (student*)malloc(sizeof(student));
		//给节点的数据域赋值
		node->data = data[i];
		//头指针后移
		node->next = head->next; 
		//指针后增 
		head->next = node; 
	} 
	return head; 
}

//尾插法创建链表
student* bottom_newlist(int data[],int n)
{
	//创建头节点
	student* head = (student*)malloc(sizeof(student));
	//创建尾节点
	student* bottom = (student*)malloc(sizeof(student));
	//给头节点的指针域置空
	head->next = NULL;
	//尾指针初始化
	bottom = head;
	//创建后续节点
	for( int i = 0 ; i < n ; i++ )
	{
		//创建一个节点
		student* node = (student*)malloc(sizeof(student));
		//给节点的数据域赋值
		node->data = data[i];		
		//尾指针后移		
		bottom->next = head->next;		
		//尾指针后移		
		bottom->next = node;		
		bottom = node;	
	}	
	//保证最后一个指针指向空	
	bottom->next = NULL;	
	return head;
}

//链表的查找
void findList(student* head,int find)
{
	student* p = head->next;
	while( p != NULL )
	{
		if( p->data == find )
		{
			printf("找到了！");
		}
		p = p->next;
	}
	printf("没找到！");
}
//链表的删除（删除链表中所有的del，如果只想删除第一个del，只需要在185行加入一个return 0; 即可）
int delectList(student* head,int del)
{
	//创建两个指针，分别表示要删除的节点和要删除的节点的前一个节点
	student* p,*q;
	//判断如果是空链表则终止操作
	if( head == NULL || head->next == NULL )
	{
		printf("你的表是空的！");
		return 0;
	}
	//对地址赋值
	p = head;
	q = head->next;
	//遍历链表
	while( p != NULL )
	{
		//如果发现data是要删除的项，则进行删除操作
		if( q->data == del )
		{
		//假定要删除的节点是a，前一项是a-1，后一项是a+1，这里的操作是把a-1和a+1相连
		p->next = q->next;
		//释放a的空间
		free(q);
		printf("删除了一个对应节点");
		}
		else	
		{
			//让指针后移
			p = p->next;
			q = q->next;
		}
	}
	return 0;
}
//链表的插入
int inList(student* head,int data,int count)
{
	//把头节点赋给p方便操作
	student* p = head;
	//获取一个计数器
	int i = 0;
	//寻找到需要插入的点的前一个节点
	while( p->next != NULL && i < count - 1 )
	{
		//指针后移
		p = p->next;
		//循环变量自增
		i++;
	}
	//如果没找到，则返回1表示没有找到可以插入的点（通常是插入节点比链表长度长）
	if( p == NULL )
	{
		return 1;
	}
	else
	{
		//创建一个需要插入的链表
		student* node = (student*)malloc(sizeof(student));
		//给节点的数据域赋值
		node->data = data;
		//新节点的指针域指向链接前的节点指向的后一个节点
		node->next = p->next;
		//新节点链接的前一个节点的指针指向这个新的节点
		p->next = node;
		return 0;
	}
}
//获取链表长度
int getListlenth(student* head)
{
	//获得计数器
	int len = 0;
	//创建指针用于遍历整个链表
	student* p = head->next;
	//迭代遍历获取链表长度
	while( p != NULL )
	{
		len++;
		p = p->next;
	}
	//返回长度
	return len;
}
//链表的完全释放
void clearList(student* head)
{
	student* p;	
	while( head->next != NULL )	
	{	
		p = head;
		head = head->next;	
		free(p);	
	}
} 

int main(){ 
	printf("各种链表的详细用法"); 
	return 0; 
}

特性

物理结构 物理结构

链表的代码

物理结构物理结构