如何使用一个尾指针来达到单链表的连续插入？

目录

• 单链表的操作
  • 文档声明
  • 创建单链表
    • 1.头文件及宏定义
    • 2.定义链表结构体及类型重定义
    • 3.声明函数以及定义全局变量
    • 4.主函数
    • 5.initList
    • 6.CreateList_L
    • 7.CreateList_R
    • 8.GetElem
    • 9.ListDelete
    • 10.ListPrint
    • 11.insert
    • 12.findMax
    • 13.print
  • 全部代码展示

单链表的操作

文档声明

本链表仅有的特殊之处就是设置了一个尾指针，以便达到前插法、后插法插入数据之前不会重置表的目的，简单说就是一个表，按照书上的写法，前插1,2,3，后插1,2,3之后链表是1 2 3。我的写法链表会是3->2->1->1->2->3。

创建单链表

1.头文件及宏定义

#include<iostream>
#include<stdio.h>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2

2.定义链表结构体及类型重定义

typedef int Status;
typedef struct LNode{
	int x;
	struct LNode *next;
}LNode,*LinkList;
//上边那步可以分解为
/*
struct LNode{
    int x;
    struct LNode *next;
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;
*/

3.声明函数以及定义全局变量

LinkList t;//尾指针
Status initList(LinkList &L);//初始化链表
void CreateList_L(LinkList &L,int n);//左（前）插法插入n个数据
void CreateList_R(LinkList &L,int n);//右（后）插法插入n个数据
Status GetElem(LinkList L,int i);//返回第i个结点的值
Status ListDelete(LinkList &L,int i);//删除第i个结点
void ListPrint(LinkList L);//遍历链表
void insert(LinkList &L,int i);//在第i个结点后插入一个结点
Status findMax(LinkList L);//找出这个链表中的最大值
Status print();//菜单界面

4.主函数

int main(){
	
	int x=0,n=0;
	LinkList L;
	while(1){
		print();
		cin>>x;
		switch(x){
			
			case 1:initList(L);break;
			case 2:cin>>n;
			CreateList_L(L,n);break;
			case 3:cin>>n;
			CreateList_R(L,n);break;
			case 4:cin>>n;
			cout<<GetElem(L,n)<<endl;break;
			case 5:ListPrint(L);break;
			case 6:cin>>n;
			insert(L,n);break;
			case 7:cout<<findMax(L)<<endl;break;
			case 8:cin>>n;
			ListDelete(L,n);break;
			case 9:return 0;
		}
	}
	return 0;
} 

5.initList

Status initList(LinkList &L){
	L=new LNode;
	L->next=NULL;
	t=L;
	return OK;
}

6.CreateList_L

void CreateList_L(LinkList &L,int n){
	for(int i=0;i<n;++i){
		LinkList p=new LNode;
		if(t==L){
			t=p;
		}
		cin>>p->x;
		p->next=L->next;
		L->next=p;
	}
}

7.CreateList_R

void CreateList_R(LinkList &L,int n){
	LinkList r=t;
	for(int i=0;i<n;++i){
		LinkList p=new LNode;
		cin>>p->x;
		p->next=NULL;
		r->next=p;
		r=p;
	}
	t=r;
}

8.GetElem

Status GetElem(LinkList L,int i){
	LinkList p=L->next;
	int j=1;
	while(p&&j<i){
		p=p->next;
		++j;
	}
	if(!p||j>i){ 
		cout<<"您要查找的元素不合法
错误:"; 
		return -1;
	} 
	return p->x;
}

9.ListDelete

Status ListDelete(LinkList &L,int i){
	LinkList p=L;
	int j=0;
	while((p->next)&&(j<i-1)){
		p=p->next;
		++j;
	}
	if(!(p->next)||(j>i-1)){
		cout<<"您要删除的元素不合法
错误:-1
"; 
		return -1;
	}
	LinkList q=p->next;
	p->next=q->next;
	delete q;
	return OK;
}

10.ListPrint

void ListPrint(LinkList L){
	LinkList p=L->next;
	if(p!=NULL){
		printf("%d",p->x);
		p=p->next;
	}
	while(p!=NULL){
		printf("->%d",p->x);
		p=p->next;
	}
	printf("
");
}

11.insert

void insert(LinkList &L,int i){
	LinkList p=L;
	while(i--&&p){
		p=p->next;
	}
	if(p==NULL||i<-1){
		cout<<"您要插入的位置不合法
错误:-1
";
		return;
	}
	LinkList q=new LNode;
	cin>>q->x;
	q->next=p->next;
	p->next=q;
}

12.findMax

Status findMax(LinkList L){
	if(L->next==NULL)return 0;
	LinkList p=new LNode;
	p=L->next;
	int max1=p->x;
	while(p->next){
		p=p->next;
		max1=max(p->x,max1);
	}
	return max1;
}

13.print

Status print(){
	cout<<"==========================================
";
	cout<<"1.创建一个空表
";
	cout<<"2.前插法插入n个数据
";
	cout<<"3.后插法插入n个数据
";
	cout<<"4.获取第n个结点的值
";
	cout<<"5.遍历链表
";
	cout<<"6.在第n个结点后插入一个结点
";
	cout<<"7.找出这个链表的最大值
";
	cout<<"8.删除第n个结点
";
	cout<<"9.退出系统
";
	cout<<"==========================================
"; 
	return OK;
}

全部代码展示

#include<iostream>
#include<stdio.h>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef struct LNode{
	int x;
	struct LNode *next;
}LNode,*LinkList;
LinkList t;
Status initList(LinkList &L){
	L=new LNode;
	L->next=NULL;
	t=L;
	return OK;
}
void CreateList_L(LinkList &L,int n){
	for(int i=0;i<n;++i){
		LinkList p=new LNode;
		if(t==L){
			t=p;
		}
		cin>>p->x;
		p->next=L->next;
		L->next=p;
	}
}
void CreateList_R(LinkList &L,int n){
	LinkList r=t;
	for(int i=0;i<n;++i){
		LinkList p=new LNode;
		cin>>p->x;
		p->next=NULL;
		r->next=p;
		r=p;
	}
	t=r;
}
Status GetElem(LinkList L,int i){
	LinkList p=L->next;
	int j=1;
	while(p&&j<i){
		p=p->next;
		++j;
	}
	if(!p||j>i){ 
		cout<<"您要查找的元素不合法
错误:"; 
		return -1;
	} 
	return p->x;
}
Status ListDelete(LinkList &L,int i){
	LinkList p=L;
	int j=0;
	while((p->next)&&(j<i-1)){
		p=p->next;
		++j;
	}
	if(!(p->next)||(j>i-1)){
		cout<<"您要删除的元素不合法
错误:-1
"; 
		return -1;
	}
	LinkList q=p->next;
	p->next=q->next;
	delete q;
	return OK;
}
void ListPrint(LinkList L){
	LinkList p=L->next;
	if(p!=NULL){
		printf("%d",p->x);
		p=p->next;
	}
	while(p!=NULL){
		printf("->%d",p->x);
		p=p->next;
	}
	printf("
");
}
void insert(LinkList &L,int i){
	LinkList p=L;
	while(i--&&p){
		p=p->next;
	}
	if(p==NULL||i<-1){
		cout<<"您要插入的位置不合法
错误:-1
";
		return;
	}
	LinkList q=new LNode;
	cin>>q->x;
	q->next=p->next;
	p->next=q;
}
Status findMax(LinkList L){
	if(L->next==NULL)return 0;
	LinkList p=new LNode;
	p=L->next;
	int max1=p->x;
	while(p->next){
		p=p->next;
		max1=max(p->x,max1);
	}
	return max1;
}
Status print(){
	cout<<"==========================================
";
	cout<<"1.创建一个空表
";
	cout<<"2.前插法插入n个数据
";
	cout<<"3.后插法插入n个数据
";
	cout<<"4.获取第n个结点的值
";
	cout<<"5.遍历链表
";
	cout<<"6.在第n个结点后插入一个结点
";
	cout<<"7.找出这个链表的最大值
";
	cout<<"8.删除第n个结点
";
	cout<<"9.退出系统
";
	cout<<"==========================================
"; 
	return OK;
}
int main(){
	
	int x=0,n=0;
	LinkList L;
	while(1){
		print();
		cin>>x;
		switch(x){
			
			case 1:initList(L);break;
			case 2:cin>>n;
			CreateList_L(L,n);break;
			case 3:cin>>n;
			CreateList_R(L,n);break;
			case 4:cin>>n;
			cout<<GetElem(L,n)<<endl;break;
			case 5:ListPrint(L);break;
			case 6:cin>>n;
			insert(L,n);break;
			case 7:cout<<findMax(L)<<endl;break;
			case 8:cin>>n;
			ListDelete(L,n);break;
			case 9:return 0;
		}
	}
	return 0;
}