博客

#include <iostream>
#include <cstdlib>
using namespace std;

/**
*单链表的初始化、增删改查
*注意点1:指针结点必须要先赋空间才能使用
*注意点2:该程序省去了一些判断条件，默认初始化和增删改查各项操作都是可执行的
*/

typedef struct lNode
{
    int data;           //数据域
    struct lNode *next; //指针域
}LNode, *LinkList;

/******************初始化单链表*************************/
void InitList(LinkList &l)
{
    //初始化生成一个{1,2,3,4,5,6}这样的单链表
    LinkList p , q;
    成功创建一个头结点(空结点)
    l = (LinkList)malloc(sizeof(LinkList));
    l->next=NULL;
    p=l;
    /**
    开始生成单链表(头插法,每次插入在头结点后进行)
    for(int i=6 ; i>=1 ; i--)
    {
        q=(LinkList)malloc(sizeof(LinkList));
        q->data=i;
        q->next=p->next;
        p->next = q ;
    }
    **/
    //开始生成单链表(尾插法，每次插入在最后一个结点后面进行)
    for(int i=1 ; i<=6 ; i++)
    {
        q=(LinkList)malloc(sizeof(LinkList)); //引入头文件<cstdlib>
        q->data=i;
        p->next =q;
        p=q;
        p->next=NULL;
    }
}
/******************显示单链表*************************/
void Showlist(LinkList &l)
{
    LinkList p;
    for(p=l->next;p!=NULL;p=p->next)
        cout<<p->data<<"  ";
    cout<<endl;
}
/**************查找单链表的第n个结点的元素*************/
void Findlist1(LinkList &l , int pos , int &e)
{
    LinkList p;
    p=l;//此时p是头结点，并非第一个结点
    for(int i=1;i<=pos;i++)
        p=p->next;
    e=p->data;
}
/**************查找单链表是否存在某个元素*************/
void Findlist2(LinkList &l , int num , int &pos)
{
    LinkList p;
    int i= 0;
    for(p=l->next;p!=NULL;p=p->next)
    {
        i++;
        if(p->data == num)
        {
            pos=i;
            break;
        }
    }
}

/**************在单链表中某个位置插入某个元素*************/
void Insertlist( LinkList &l, int pos , int num)
{
    LinkList p;
    p=l;
    LNode *q=new LNode;//等同(LinkList)malloc(sizeof(LinkList));
    q->data=num;
    for(int i=1;i<pos;i++)
        p=p->next;
    q->next=p->next;
    p->next=q;
}
/**************在单链表中删除某个位置的结点*************/
void Delelist(LinkList &l, int pos , int &e)
{
    LinkList p , q;
    p=l;
    for(int i=1;i<pos;i++)
        p=p->next;
    q=p->next;
    e=q->data;
    p->next=q->next;
    free(q);
}
/*******************************************************/
int main()
{
    LinkList l ;
    int e , pos;
    cout<<"-------------------------"<<endl;
    cout<<"初始化单链表的信息如下："<<endl;
    InitList(l); //初始化单链表
    Showlist(l);
    cout<<"-------------------------"<<endl;
    Findlist1(l , 3 , e);
    cout<<"查找单链表第3个元素的值："<<endl<<e<<endl;
    cout<<"-------------------------"<<endl;
    Findlist2(l , 5 , pos);
    cout<<"查找元素5在单链表的位置："<<endl<<pos<<endl;
    cout<<"-------------------------"<<endl;
    cout<<"在单链表第5个位置插入9："<<endl;
    Insertlist(l, 5 , 9);
    Showlist(l);
    cout<<"-------------------------"<<endl;
    cout<<"删除单链表第6个元素的值："<<endl;
    Delelist(l, 6 , e);
    Showlist(l);
    cout<<"-------------------------"<<endl;
    return 0;
}