线性表的链式表示-蒲公英云

线性表的链式表示

上篇文章是线性表的顺序表示，本篇便是线性表的链式表示。

主函数的步骤包括，输入线性表数据，对链表的删除，插入。利用指针进行对链表的访问。

同时为了增加程序可读性，将结构体定义为LNode，*linklist。

#include<iostream>
//线性表的链式表示
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*linklist;//指向结构体的指针变量 
int initlist(linklist &l)//初始化链表 
{
    l=new LNode;//新的头节点 
    l->next=NULL;
    return 1;//成功初始化 
}
int getelem(linklist l,int i,int &e)//链表的取值 
{
    LNode *p;
    p=l->next;
    int j=1;
    while(p&&i<j)
    {
        p=p->next;
        j++;
    }
    if(!p||i>=j)  return 0;
    e=p->data;
    return 1;
}
int loateelem(linklist l,int e)//查找 
{
    linklist p;
    int i;
    p=l;
    while(p)
    {
        p=p->next;
        if (p->data==e)
          return 1;
    }
    if(!p)
     return 0;
}
int listinsert(linklist &l,int i,int e)//线性表的插入 
{
    linklist p,s;
    s=new LNode;
    int j=0;
    p=l;
    while(p&&j<(i-1))
    {
        p=p->next;
        j++;
    }
    if(!p||j>(i-1))  return 0;
    s->data=e;
    s->next=p->next;
    p->next=s;
    return 1;
}
int listdelet(linklist &l,int i)//链表的删除 
{
    linklist p,q;
    int j=0;
    p=l;
    while(p->next && j<(i-1))
    {
        p=p->next;
        j++;
    }
    if(!(p->next)||j>(i-1))  return 0;
    q=p->next;
    p->next=p->next->next;
    delete q;
    return 1;
}
void creatlist(linklist &l,int n)//创建链表 
{
    l=new LNode;
    linklist p;
    l->next=NULL;
    for(int i=0;i<n;i++)
    {
        p=new LNode;
        cin>>p->data;
        p->next=l->next;
        l->next=p;
    }
}
int main()
{
    linklist l,p;
    int n,i,j,k;
    cin>>n;
    initlist(l);//初始化链表 
    creatlist(l,n);//创建链表 
    p=l->next;//p指向首元节点 
    for(i=0;i<n;i++)
    {
        cout<<p->data<<" ";//输出节点的数据域 
        p=p->next;//p继续指向下一个节点 
    }
    cout<<endl<<"删除的数据：";//删除链表数据 
    cin>>k;
    if(listdelet(l,k)) 
    {
        cout<<"删除成功"<<endl;
        p=l->next;
        for(i=0;i<n-1;i++)
        {
            cout<<p->data<<" ";//输出节点的数据域 
            p=p->next;//p继续指向下一个节点 
        }
    }
    else cout<<"删除失败"<<endl;
    cout<<endl<<"输入插入的位置与数值：";//插入数据 
    cin>>j>>k;
    if(listinsert(l,j,k));
        {    
            cout<<"插入成功"<<endl;
            p=l->next;//p指向首元节点 
            for(i=0;i<n;i++)
            {
                cout<<p->data<<" ";//输出节点的数据域 
                p=p->next;//p继续指向下一个节点 
            }
        }
    if(!listinsert(l,j,k))    cout<<"插入失败"<<endl;
    return 0;    
}