欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  IT编程

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

程序员文章站 2022-07-02 15:51:44
[TOC] 单链表的操作 文档声明 本链表仅有的特殊之处就是设置了一个尾指针，以便达到前插法、后插法插入数据之前不会重置表的目的，简单说就是一个表，按照书上的写法，前插1,2,3，后插1,2,3之后链表是1 2 3。我的写法链表会是3 2 1 1 2 3。 创建单链表 1.头文件及宏定义 2.定义链 ......

目录

单链表的操作

文档声明

本链表仅有的特殊之处就是设置了一个尾指针，以便达到前插法、后插法插入数据之前不会重置表的目的，简单说就是一个表，按照书上的写法，前插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<<"您要查找的元素不合法\n错误:"; 
        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<<"您要删除的元素不合法\n错误:-1\n"; 
        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("\n");
}

11.insert

void insert(linklist &l,int i){
    linklist p=l;
    while(i--&&p){
        p=p->next;
    }
    if(p==null||i<-1){
        cout<<"您要插入的位置不合法\n错误:-1\n";
        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<<"==========================================\n";
    cout<<"1.创建一个空表\n";
    cout<<"2.前插法插入n个数据\n";
    cout<<"3.后插法插入n个数据\n";
    cout<<"4.获取第n个结点的值\n";
    cout<<"5.遍历链表\n";
    cout<<"6.在第n个结点后插入一个结点\n";
    cout<<"7.找出这个链表的最大值\n";
    cout<<"8.删除第n个结点\n";
    cout<<"9.退出系统\n";
    cout<<"==========================================\n"; 
    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<<"您要查找的元素不合法\n错误:"; 
        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<<"您要删除的元素不合法\n错误:-1\n"; 
        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("\n");
}
void insert(linklist &l,int i){
    linklist p=l;
    while(i--&&p){
        p=p->next;
    }
    if(p==null||i<-1){
        cout<<"您要插入的位置不合法\n错误:-1\n";
        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<<"==========================================\n";
    cout<<"1.创建一个空表\n";
    cout<<"2.前插法插入n个数据\n";
    cout<<"3.后插法插入n个数据\n";
    cout<<"4.获取第n个结点的值\n";
    cout<<"5.遍历链表\n";
    cout<<"6.在第n个结点后插入一个结点\n";
    cout<<"7.找出这个链表的最大值\n";
    cout<<"8.删除第n个结点\n";
    cout<<"9.退出系统\n";
    cout<<"==========================================\n"; 
    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;
}

上一篇： UART学习之路（三）基于STM32F103的USART实验

下一篇： C++11中weak_ptr的使用

推荐阅读