C++实现单链表的基本操作

墨蓝 2022-03-08 10:13 278阅读 0赞

## C++实现单链表的基本操作 ##

包含了单链表的创建、插入、删除、排序、输出等功能。

//C++实现单链表的基本操作
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define ERROR 1;
    typedef int ElemType;
    typedef int Status;
    
    //定义单链表中每个节点的存储结构
    typedef struct LNode{
        
    	ElemType data;
    //	节点的数据域 
    	struct LNode *next;
    //	节点的指针域 
    }LNode , *LinkList; 
    
    //初始化
    void InitList(LinkList L){
        
    //    构造一个空的单链表L
        L = new LNode;
        L ->next = NULL;
        cout<<"初始化成功"<<endl;
    } 
    
    //为链表填入元素
    void Create(LinkList L, int n){
        
    	L = new LNode;
    	LNode *r;
    	L ->next = NULL;
    	r = L;
    	for(int i=0;i<n;++i){
        
    		LNode *p;
    		p=new LNode;
    		cin>>p ->data;
    		p ->next = NULL;
    		r ->next = p;
    		r = p;
    	}
    }
    
    //插入元素
    int Insert(LinkList L , int i , ElemType e){
        
    	cout<<"请输入要插入的元素和他的位置"<<endl;
    	cin>>e>>i;
    	LNode *p;
    	p = L;
    	int j = 0;
    	while(p!=NULL&&(j<i-1)){
        
    		p = p->next;
    //		移动指针 查找第i-1个节点 并将p指向该节点 
    	}
    	if(p==NULL||j>i-1)
    	{
        
    		return ERROR;
    	}
    	LNode *s;
    	s=new LNode;
    	s->data = e;
    	s->next=p->next;
    	p->next=s;
    //	这几步的操作分别将结点s的数据域置为e,s的指针域指向原来p的指针域指向的结点，
    //	再将p的指针域指向结点s，实现了结点s的插入。 
    } 
    
    //删除元素
    int Delete(LinkList L , int i) {
        
    	cout<<"请输入要删除的元素的位置"<<endl;
    	cin>>i;
    	LNode *p;
        p = L;
    	int j = 0;
    	while(p->next != NULL&&(j<i-1)){
        
    		p = p->next;
    		++j;
    	}
    	if(p->next == NULL||j>i-1){
        
    		return ERROR;
    		LNode *q;
    		q=p->next;
    		p->next=q->next;
    //		以上操作实现了将q结点删除 
    		delete q;
    //		将该删除节点的空间释放 
    	}	
    }
    
    //排序
    void Sort(LinkList L,int n){
        
    	sort(L,L+n);
    } 
    
    //打印链表中的元素
    Print(LinkList L)
    {
        
    LinkList P = L->next;
    while (P != NULL)
    {
        
    if(P->next==NULL){
        
    	cout<<P->data;
    }
    else{
        
    	cout<<P->data<<' ';
    }
    P = P->next;
    }
    }
    
    int main(){
        
    	int n,x;
    	cout<<"请输入n值"<<endl;
    	cin>>n;
    	LinkList L;
    //	在主函数中声明链表L 
    	InitList(L); 
    //	顺序表的初始化
    
    loop:
    	cout<<"请选择您想进行的操作"<<endl;
    	cout<<"0.给链表读入值"<<endl;
    	cout<<"1.给链表插入值"<<endl;
    	cout<<"2.给链表删除值"<<endl;
    	cout<<"3.给链表排序"<<endl;
    	cout<<"4.输出链表"<<endl;
    	
    	cin>>x; 
    	
    	switch(x){
        
    		case 0:{
        
    			cout<<"请输入数组的各个元素"<<endl;
    			Create(L , n);
    			cout<<"退出请按1，输入其他数字返回上级清单"<<endl;
    			int p;
    			cin>>p;
    			if(p == 1){
        
    			return 0;
    			}
    			else{
        
    			goto loop;	
    			} 	
    		break;
    		}
    		
    		case 1:{
        
    			int i;
    			ElemType e;
    			Insert(L , i , e);
    			cout<<"插入之后的数组"<<endl;
    			Print(L);
    			cout<<"退出请按1，输入其他数字返回上级清单"<<endl;
    			int p;
    			cin>>p;
    			if(p == 1){
        
    		    return 0;
    			}
    			else{
        
    			goto loop;	
    			} 	
    		break;
    		}
    		
    		case 2:{
        
    			int i;
    			Delete(L , i);
    			cout<<"删除之后的数组："<<endl;
    			Print(L);
    		cout<<"退出请按1，输入其他数字返回上级清单"<<endl;
    			int p;
    			cin>>p;
    			if(p == 1){
        
    			return 0; 
    			}
    			else{
        
    			goto loop;	
    			} 	
    		break;
    		}
    		
    		case 3:{
        
    		    Sort(L,n);
    			Print(L);
    			cout<<"退出请按1，输入其他数字返回上级清单"<<endl;
    			int p;
    			cin>>p;
    			if(p == 1){
        
    			return 0;
    			}
    			else{
        
    			goto loop;	
    			} 	
    			break;
    		}
    		
    		case 4:{
        
    			Print(L);
    		cout<<"退出请按1，输入其他数字返回上级清单"<<endl;
    			int p;
    			cin>>p;
    			if(p == 1){
        
    			return 0;
    			}
    			else{
        
    			goto loop;	
    			} 	
    		break;
    		}
    		
    		default : {
        
    		cout<<"请输入正确的数字！"<<endl;
    		goto loop;
    			break;
    		}
    	}
    	return 0;  
    }