当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 如何使用一个尾指针来达到单链表的连续插入？

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

2018年10月24日  | 移动技术网IT编程  | 我要评论

东方神女李勤全图,现任公安部副部长,黑芝麻产地

目录

单链表的操作

文档声明

本链表仅有的特殊之处就是设置了一个尾指针，以便达到前插法、后插法插入数据之前不会重置表的目的，简单说就是一个表，按照书上的写法，前插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;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网