单链表的建立（源码）

#include 
#include 
#include 
#include 

using namespace std;

typedef struct LNode{              //定义单链表结点类型
    int data;                       //数据域：每个结点存放一个数据元素
    struct LNode *next;             //指针域：指针指向下一个结点
}LNode, *LinkList;


//按位查找，返回第i个元素（带头结点）
LNode *GetElem(LinkList L, int i)     //LinkList L可以换成LNode *L
{
    if(i < 0)
        return NULL;
    LNode *p;              //指针p用来指向当前扫描到的结点
    int j = 0;
    p = L;
    while(p != NULL && j < i)
    {
        p = p->next;
        j++;
    }
    return p; //返回一个指针
}

//按值查找，找到数据域为e的结点
LNode *LocateElem(LinkList L, int e, int &place)  //用place返回位序！
{
    int i = 1;
    LNode *p = L->next;  //从第一个结点开始查找数据域为e的结点
    while(p != NULL && p->data != e)
    {
        p = p->next;
        i++;
    }
    place = i;
    return p; //返回一个指针
}


//求表的长度，头结点无数据，去除头结点
int ListLength(LinkList L)
{
    int len = 0;
    LNode *p = L;
    while(p->next != NULL)
    {
        p = p->next;
        len++;
    }
    return len - 1;  //去除头结点
}


//初始化一个单链表（带头结点）
bool InitList(LinkList &L)
{
    L = (LNode *)malloc(sizeof(LNode));  //创建并分配一个头结点
    if(L == NULL)
        return false;                //内存不足，分配失败
    L->next = NULL;                      //头结点后暂时还没有结点
    return true;
}



//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, int e)
{
    //以下代码等价于直接调用 LNode *p = GetElem(L, i - 1) //找到第i-1个结点，并用p指向它
    if(i < 1)
        return false;
    LNode *p;                //指针p指向当前扫描到的结点
    int j = 0;
    p = L;
    while(p != NULL && j < i - 1)      //找到插入位置的前驱结点
    {
        p = p->next;
        j++;
    }
    //以下代码等价于直接调用 return InsertNextNode(p, e);
    if(p == NULL)              //i值不合法
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}




//在第i个位置插入元素e（不带头结点）
bool ListInsert2(LinkList &L, int i, int e)
{
    if(i < 1)
        return false;
    if(i == 1)
    {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L = s;                 //头指针指向新结点
    }
    LNode *p;                //指针p指向当前扫描到的结点
    int j = 0;
    p = L;
    while(p != NULL && j < i - 1)      //找到插入位置的前驱结点
    {
        p = p->next;
        j++;
    }
    if(p == NULL)              //i值不合法
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}



//后插 *** 作：在p结点之后插入元素e
bool InsertNextNode(LNode *p, int e)
{
    if(p == NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s == NULL)           //内存分配失败
        return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;

}



//前插 *** 作：在p结点之前插入元素e
bool InsertPriorNode(LNode *p, int e)
{
    if(p == NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s == NULL)
        return false;     //内存分配失败
    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return true;
}



//（带头结点）删除表L中第i个位置的元素，并用e返回删除元素的值。


bool ListDelete(LinkList &L, int i, int &e)
{
    LNode *p = GetElem(L, i - 1); //找到第i-1个结点，并用p指向它
    if(p == NULL)
        return false;     //i值不合法
    if(p->next == NULL)
        return false;     //第i-1个结点之后已无其他结点
    LNode *q = p->next;    //定义一个指针q，指向要删除的结点
    e = q->data;
    p->next = q->next;     //将*q从链中断开
    free(q);
    return true;
}



//尾插法建立单链表
LinkList List_TailInsert(LinkList &L)
{
    int x;
    L = (LinkList)malloc(sizeof(LNode)); //建立头结点
    L->next = NULL;
    LNode *s,*r = L;
    printf("请输入插入的值:\n");                     //建立表尾指针
    scanf("%d", &x);
    while(x != 9999)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;          //表尾指针后继置空
    return L;               //返回头结点L
}



//头插法建立单链表
LinkList List_HeadInsert(LinkList &L)
{
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    printf("请输入插入的值:\n");
    scanf("%d", &x);
    while(x != 9999)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

//**************************************功能函数*********************************************


//遍历输出函数
void PrintList(LinkList L)
{
    LinkList p = L->next; //跳过头结点
    if(ListLength(L))
    {
        printf("当前单链表所有元素：\n");
        while(p)
        {
            printf("%d ", p->data);
            p = p->next;
        }
        printf("\n");
    }
    else
        printf("当前单链表为空\n");
}


//插入功能函数
void Insert(LinkList &L)
{
    int place, e;
    bool flag;
    printf("请输入要插入的位置（从1开始）及元素（空格隔开）：\n");
    scanf("%d %d", &place, &e);
    flag = ListInsert(L, place, e);
    if(flag)
    {
        printf("插入成功！\n");
        PrintList(L);
    }
}


//删除功能函数
void Delete(LinkList &L)
{
    int place, e;
    bool flag;
    printf("请输入要删除的位置（从1开始）：\n");
    scanf("%d", &place);
    flag = ListDelete(L, place, e);
    if(flag)
    {
        printf("元素%d删除成功！\n", e);
        PrintList(L);
    }
}


//查找功能函数，调用LocateElem查找
void Search(LinkList L)
{
    int e, place;
    LNode *q;
    printf("请输入想查找的值：");
    scanf("%d", &e);
    q = LocateElem(L, e, place);
    if(q)
        printf("找到该元素！在链表的第%d个位置！\n",place);//用place返回位序！
    else
        printf("未找到该元素！\n");
}


void menu()
{
    printf("         \n");
    printf("1、尾插\n");
    printf("2、头插\n");
    printf("3、插入\n");
    printf("4、删除\n");
    printf("5、按值查找\n");
    printf("6、输出\n");
    printf("7、退出\n");
}



int main()
{
    LinkList L;              //声明一个指向单链表的指针
    int choice;
    while(1)
    {
        menu();
        printf("请输入菜单序号：\n");
        scanf("%d", &choice);
        if(choice == 0)
            break;
        switch(choice)
        {
            case 1:List_TailInsert(L);break;
            case 2:List_HeadInsert(L);break;
            case 3:Insert(L);break;
            case 4:Delete(L);break;
            case 5:Search(L);break;
            case 6:PrintList(L);break;
            default:printf("输入错误！\n");
        }
    }
    return 0;

}