单链表

#include<stdio.h>
#include<malloc.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define NULL 0
typedef int Status;
typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
} LNode,*LinkList;
Status InitList_h(LinkList &h)
{
    //初始化线性表
    h=(LinkList )malloc(sizeof(LNode));
    //h指向头节点，头节点数据域为空
    h->next=NULL;
    return OK;
}// InitList_h
Status DispList_h(LinkList &h)
{
    //输出线性表
    LinkList p=h->next;
    while(p!=NULL)
    {
        printf("%c",p->data);
        p=p->next;
    }
    return OK;
} // DispList_h
Status CreateList_h(LinkList &h,ElemType a[],int n)
{
    //尾插法建表
    LinkList s,r;
    int i;
    h=(LinkList )malloc(sizeof(LNode));
    r=h;
    for(i=0; i<n; i++)
    {
        s=(LinkList )malloc(sizeof(LNode));
        s->data=a[i];
        r->next=s;
        r=s;
    }
    r->next=NULL;
    return OK;
}// CreateList_h
Status ListLength_h(LinkList h)
{
    //求线性表的长度
    LinkList p=h;
    int n=0;
    while(p->next!=NULL)
    {
        n++;
        p=p->next;
    }
    return(n);
}// ListLength_h
Status ListEmpty_h(LinkList h)
{
    //判断单链表是否为空
    return(h->next==NULL);
}// ListEmpty_h
Status DestroyList_h(LinkList &h)
{
    //销毁线性表
    LinkList p=h,q=p->next;
    while(q!=NULL)
    {
        free(p);
        p=q;
        q=p->next;
    }
    free(p)
    return OK;
}// DestroyList_h
Status GetElem_h(LinkList h, int i, ElemType &e)
{
    // h为带头节点的单链表的头指针。
    // 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
    int j=0;
    LinkList p=h;
    while(j<i&&p!=NULL)
    {
        j++;
        p=p->next;
    }
    if(p==NULL)
    {
        return ERROR;
    }
    else
    {
        e=p->data;
        return OK;
    }
}// GetElem_h
Status ListInsert_h(LinkList &h, int i, ElemType e)
{
    //插入数据元素
    int j=0;
    LinkList p=h,s;
    /*   找到插入节点的上一个元素，如果是头节点则退出，
    当i=1时表示头节点，i=2时，表示第一个元素  */
    while(j<i-1&&p!=NULL)
    {
        j++;
        p=p->next;
    }
    if(p==NULL)
    {
        return ERROR;
    }
    else
    {
        s=(LinkList )malloc(sizeof(LNode));
        s->data=e;
        s->next=p->next;
        p->next=s;
        return OK;
    }
}// ListInsret_h
Status ListDelete_h(LinkList &h, int i, ElemType &e)
{
    //删除数据元素
    int j=0;
    LinkList p=h,q;
    while(j<i-1&&p!=NULL)    //查找删除元素的前一个节点
    {
        j++;
        p=p->next;
    }
    if(p==NULL)
    {
        return ERROR;
    }
    else
    {
        q=p->next;   //q为要删除的元素节点
        if(q==NULL)
        {
            return ERROR;
        }
        e=q->data;   //e为删除节点的数据区域
        p->next=q->next;
        free(q);
        return OK;
    }
}// ListDelete_h
int LocateElem_h(LinkList h, ElemType e)
{
    //按元素值查找元素
    LinkList p=h->next;
    int i=1;
    while(p!=NULL&&p->data!=e)
    {
        p=p->next;
        i++;
    }  //如果要插入的节点为头节点，则退出
    if(p==NULL)
    {
        return ERROR;
    }
    else
    {
        return(i);
    }
}// LocateElem_h
int main()
{
    ElemType e,a[5]= {'a','b','c','d','e'};
    LinkList h;
    printf("(1)初始化单链表h\n");
    InitList_h(h);                              //初始化单链表h
    printf("(2)依次采用尾插法插入a,b,c,d,e元素\n");
    CreateList_h(h,&a[0],5);     //依次采用尾插入法插入a，b，c，d，e元素
    printf("(3)输出单链表h：");
    DispList_h(h);                             //输出单链表h
    printf("\n");
    printf("(4)单链表h的长度为：");
    printf("%d",ListLength_h(h));                //输出单链表h的长度
    printf("\n");
    if(ListEmpty_h(h))
    {
        printf("(5)该单链表为空\n");
    }
    else
    {
        printf("(5)该单链表不为空\n");           //判断单链表h是否为空
    }
    GetElem_h(h,3,e);
    printf("(6)单链表h的第三个元素为：");
    printf("%c",e);
    printf("\n");                 //输出单链表h的第3个元素
    printf("(7)单链表h中a的位置为：");
    printf("%d",LocateElem_h(h,'a'));          //输出元素'a'的位置
    printf("\n");
    ListInsert_h(h,4,'f');                      //在第4个元素位置插入'f'元素
    printf("(8)在第4个元素位置上插入 f 元素\n");
    printf("(9)输出单链表h：");
    DispList_h(h);      //输出单链表h
    printf("\n");
    ListDelete_h(h,3,e);                      //删除h的第3个元素
    printf("(10)删除h的第3个元素\n");
    printf("(11)输出单链表h:");                //输出单链表h
    DispList_h(h);
    printf("\n");
    printf("(12)释放单链表h\n");
    DestroyList_h(h);                        //释放单链表h
    return 0;
    }