数据结构——链表（基本操作及2022王道综合应用题）

基本操作单链表相关

//线性表的链式表示
#include
//定义单链表 
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*linkList;

//链表可以选择是否带头结点 
 
//利用头插法建立单链表,逆向建立单链表 
linkList List_HeadInsert(linkList &L)
{
	LNode *s;//头指针
	int x;
	L=(linkList)malloc(sizeof(LNode));
	L->next =NULL;
	scanf("%d",&x);
	while(x!=9999){//输入9999表示结束 
		s=(LNode*)malloc(sizeof(LNode));
		s->data=x;
		s->next=L->next;
		L->next=s;
		scanf("%d",&x);
	}
	return L;
}
//利用尾插法建立单链表，正向建立单链表
linkList List_TailInsert(linkList &L)
{
	int x;
	LNode *s,*r=L;//r为表尾指针
	scanf("%d",&x);
	while(x!=9999){//输入9999表示结束
		s=(LNode*)malloc(sizeof(LNode));
		s->data=x;
		r->next=s;
		r=s;
		scanf("%d",&x) ;
	} 
	r->next=NULL;
	return L;	
 } 
 //按序号查找结点值
 LNode *GetElem(linkList L,int i){
 	int j=1;
	 LNode *p=L->next;
	 if(i==0)
		return L;//如果i等于0，返回头结点 
	if(i<1)
		return NULL;//如果i无效，返回NULL 
	while(p&&jnext;
		j++;
	}
	return p;//返回第i个结点的指针，若i大于表长，则返回NULL 
 } 
 //按值查找表结点
 LNode *LocateElem(linkList L,int e)
 {
 	LNode *p=L->next;
 	while(p!=NULL&&p->data!=e);
 		p=p->next;
 	return p;
  } 
  //插入结点操作
   //实现插入结点的代码如下
   p=GetElem(L,i-1);
   s->next=p->next;
   p->next=s;
   //对某一个结点进行前插操作
   //在单链表的插入算法中，通常采用后插操作
   //将*s插入到*p之前的主要代码片段
   s->next=p->next;
   p->next=s;
   temp=p->data;
   p->data=s->data;
   s->data= temp;
   //删除结点操作
   //实现删除结点的代码片段如下
   p=GetElem(L,i-1);
   q=p->next;
   p->next=q->next;
   free(q);
   //删除结点*p 
   //删除*p可用删除*p的后继结点操作来实现
   //将后继结点的值赋予其自身，然后删除后继结点，时间复杂度为O（1） 
   //实现上述操作的代码片段如下:
   q=p->next;
   p->data=p->next->data;
   p->next=q->next;
   free(q);

双链表相关

//双链表相关操作
//当访问某个结点的前驱节点时，单链表只能从头开始遍历，访问后继结点的时间复杂度为O(1),访问前驱结点的时间复杂度为O（n）
//双链表结点类型
typedef struct DNode{
	int data;
	struct DNode *prior,*next;
}DNode,*DlinkList;
//双链表的按值查找表和按位查找操作与单链表相同
//但在插入和删除操作上，与单链表区别较大
//双链表可以很方便地找到前驱结点，插入、删除操作的时间复杂度为O（1）

//双链表的插入操作
//在p所指的结点之后插入结点*s 
	s->next=p->next;
	p->next->prior=s;
	s->prior=p;
	p->next=s;
	
//双链表的删除操作
//删除结点*p的后继节点*q 
	p->next=q->next;
	q->next->prior=p;
	free(q);

循环链表

//循环链表
 
 //循环单链表
 //循环单链表与循环链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点
 //循环单链表的判空条件不是头结点是否为空，而是它是否等于头指针
 //单链表只能从开始遍历整个链表，而循环单链表可以从表中任意一个结点开始遍历整个链表
 //有时对单链表的操作是在表头和表尾进行的----> 不设头指针而仅设尾指针
  
  
  //循环双链表
  //与循环单链表不同，在循环双链表中，头结点的prior指针还要指向表尾结点

静态链表

//静态链表
//借助数组描述线性表的链式存储结构
//指针是结点的相对地址（数组下标），游标
//静态链表需要预先分配一块连续的内存空间

//静态链表结构类型
#define MaxSize 50
typedef struct{
	int data;
	int next;
}SlinkList;
//静态链表以next==1作为其结束的标志

综合应用题第一题

//利用递归算法,删除不带头结点的单链表中所有值为x的结点
#include
using namespace std;

//定义单链表 
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*linkList;

//初始化单链表
//建立单链表之前要先初始化单链表 
void InitList(linkList &L)
{
	L = NULL;
}

//尾插法建立单链表
linkList List_TailInsert(linkList &L)
{
	InitList(L);//初始化
	LNode *s,*r;
	int e;
	printf("输入元素（输入-1为停止）");
	scanf("%d",&e);
	if(e != -1)//首先对第一个结点赋值
	{
		L = (linkList)malloc(sizeof(LNode));
		L->data = e;
		r = L;
		scanf("%d",&e);
		while(e != -1)
		{
			s = (LNode*)malloc(sizeof(LNode));
			s->data = e;
			r->next = s;
			r = s;
			scanf("%d",&e);
		}
	}
	r->next = NULL;
	return L;
}

void Print_List(linkList &L){
    cout<<"单链表为："<next){
        cout<data<<"->";
    }
    cout<<"Nulln";
}

  
  //递归算法，执行删除操作
  
 

  void Del_X_3(linkList &L,int x)
  {
  	LNode *p;
  	
  	if(L==NULL)//递归出口 
		return ;
	if(L->data==x)
	{
		p=L;//删除*L，并让L指向下一结点
		L=L->next;
		free(p);

		Del_X_3(L,x); //递归调用 
	}
	else//若L所指的结点不为x 
		Del_X_3(L->next,x);//递归调用 		
  }

  int main()
  {
  	linkList L;
  	InitList(L);
  	List_TailInsert(L);
  	Print_List(L); 
  	int x;
  	cout<<"请输入要删除的元素x："<>x;
	Del_X_3(L,x);
	Print_List(L);
	 
	 return 0;
  }

第二题

//在带头结点的单链表中，删除所有值为x的结点，并释放其空间
//假设值为x的结点不唯一
#include
using namespace std;

//定义单链表
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*linkList;

//初始化单链表
void InitList(linkList &L)
{
	L=NULL;
 } 
 
 //尾插法建立带头结点的单链表
 void List_TailInsert(linkList &L)
 {
 	int x;
 	cout<<"请依次输入单链表中的元素（-1结束输入）："<next = NULL;   
    LNode *s,*r;  
    r = L;    
 
    while (1) {//插入结点s 
    	cin>>x;
    	if(x==-1)
    		break ;
        s = (LNode*)malloc(sizeof(LNode));  
        s->data=x;   
        
        r->next = s;
        r = s;
    }
        r->next = NULL;
 	
  } 
  
 
  
  //标答 ——解法二
  void Del_x(linkList &L, int x)
  {
		LNode *p=L->next,*r=L,*q;//r指向尾结点，初值为头结点
		while(p!=NULL)
		{
			if(p->data!=x)
			{
				r->next=p;
				r=p;
				p=p->next;
			}
			else 
			{
				q=p;
				p=p->next;
				free(q);
			}
		 } 
  		r->next=NULL;
  } 
  
  
   
 //打印带头结点的单链表的所有数据
void Print_List(linkList L)
{
	printf("单链表中的数据为：n");
	while(L->next != NULL)
	{
		L = L->next;
		printf("%d ",L->data);
	}
	printf("n");
}

int main()
{
	int x;
	linkList L;
	InitList(L);
	List_TailInsert(L);
	Print_List(L);
	cout<<"请输入想要删除的元素x:"<>x;
	Del_x(L,x);
	Print_List(L);
	
	return 0;
}

第三题

//设L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值
#include
using namespace std;

//定义单链表
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*linkList;

//初始化单链表
void InitList(linkList &L)
{
	L=NULL;
 } 
 
 //尾插法建立带头结点的单链表
 void List_TailInsert(linkList &L)
 {
 	int x;
 	cout<<"请依次输入单链表中的元素（-1结束输入）："<next = NULL;   
    LNode *s,*r;  
    r = L;    
 
    while (1) {//插入结点s 
    	cin>>x;
    	if(x==-1)
    		break ;
        s = (LNode*)malloc(sizeof(LNode));  
        s->data=x;   
        
        r->next = s;
        r = s;
    }
        r->next = NULL;
 	
  } 


 //打印带头结点的单链表的所有数据
void Print_List(linkList L)
{
	printf("单链表中的数据为（反向输出）：n");
	while(L->next != NULL)
	{
		L = L->next;
		printf("%d ",L->data);
	}
	printf("n");
}

//递归实现逆置输出链表中的元素
//每次都先输出后面结点的值，再输出本身 
void  Reverse(linkList L)
{
	if(L->next!=NULL)
		Reverse(L->next);
	if(L!=NULL)
		cout<data<<" ";
}
//如果没有这个函数会把头结点乱码输出 
void Ignore_Head(linkList L)
{
	if(L!=NULL)
		Reverse(L->next);
}

int main()
{
	int x;
	linkList L;
	InitList(L);
	List_TailInsert(L);
	cout<<"从尾到头逆序输出链表中的元素："< 
第四题 
//ÊÔ±àÐ´ÔÚ´øÍ·½áµãµÄµ¥Á´±íÖÐÉ¾³ýÒ»¸ö×îÐ¡Öµ½áµãµÄ¸ßÐ§Ëã·¨
//¼ÙÉè×îÐ¡Öµ½áµãÊÇÎ¨Ò»µÄ
#include 
using namespace std;

//¶¨Òåµ¥Á´±í
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*linkList;

//³õÊ¼»¯µ¥Á´±í
void InitList(linkList &L)
{
	L=NULL;
}

//Î²²å·¨½¨Á¢´øÍ·½áµãµÄµ¥Á´±í
void  List_TailInsert(linkList &L)
{
	int x;
	cout<<"ÇëÒÀ´ÎÊäÈëÁ´±íÖÐµÄÔªËØ£¨-1´ú±í½áÊø£©£º"<next=NULL;
	LNode *s,*r; 
	r=L;
	
	while(x!=-1)
	{
		cin>>x;
		if(x==-1)
			break;
		s=(LNode*)malloc(sizeof(LNode)); 
		s->data=x;
		r->next=s;
		r=s;		
	}
		r->next=NULL;
}

//´òÓ¡Êä³öÁ´±í 
void PrintList(linkList L)
{
	cout<<"µ¥Á´±íÖÐµÄÊý¾ÝÎª£º"<next!=NULL)
	{
		L=L->next;
		cout<data<<" ";
	 } 
	 cout<next;//pÎª¹¤×÷Ö¸Õë£¬preÖ¸ÏòÆäÇ°Çý
	LNode *minpre=pre,*minp=p;//±£´æ×îÐ¡Öµ½áµã¼°Ç°Çý
	while(p!=NULL)
	{
		if(p->datadata){
			minp=p;
			minpre=pre;
		}
		pre=p;
		p=p->next;
	 } 
	 minpre->next=minp->next;
	 free(minp);
	 return L;
 } 
 
 
 int main()
 {
 	linkList L;
 	InitList(L);
 	List_TailInsert(L);
 	PrintList(L);
 	Del_min_List(L);
 	PrintList(L);
 	
 	return 0;
 }

数据结构——链表（基本操作及2022王道综合应用题）

C/C++/C#相关栏目本月热门文章