单链表.cpp

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;     //用作函数值类型，表示函数结果状态
typedef int ElemType;
typedef int KeyType;    //关键字类型为整数类型

/*单链表默认是带头结点*/
typedef struct LNode {
    ElemType data;      //数据域
    struct LNode *next; //指针域
}LNode, *LinkList;

/*函数接口*/
/*1.构建一个空的单链表L*/
Status InitList_L(LinkList &L);
/*2.销毁单链表L*/
Status DestroyList_L(LinkList &L);
/*3.将单链表L重置为空表*/
Status ClearList_L(LinkList &L);
/*4.单链表L为空表时返回TRUE，否则FALSE*/
Status ListEmpty_L(LinkList L);
/*5.求单链表L的表长*/
int ListLength_L(LinkList L);
/*6.查找。返回单链表L中第一个数据域值为e的结点地址，若不存在则返回NULL*/
LNode* Search_L(LinkList &L, ElemType e);
/*7.返回p结点的直接后继结点的指针，若p结点是尾元结点则返回NULL*/
LNode* NextElem_L(LNode *p);
/*8.构建元素e的结点，返回指向该结点的指针*/
LNode* MakeNode_L(ElemType e);
/*9.在p结点之后插入q结点*/
Status InsertAfter_L(LNode *p, LNode *q);
/*10.删除p结点的直接后继结点，用e返回结点值，若p空或指向尾元指针则操作失败*/
Status DeleteAfter_L(LNode *p, ElemType &e);
/*11.遍历单链表L*/
void ListTraverse_L(LinkList L, Status(*visit)(ElemType e));
/*12.建立一个长度为n的单链表，数组A[]提供n个元素值*/
Status CreatList_L(LinkList &L, int n, ElemType *A);


/*1.构建一个空的单链表L*/
Status InitList_L(LinkList &L) {
    if (NULL == (L = (LNode*)malloc(sizeof(LNode))))    //  生成新结点
        return OVERFLOW;
    L->next = NULL;
    return OK;
}

/*2.销毁单链表L*/
Status DestroyList_L(LinkList &L) {
    LNode *p;
    while (L) {
        p = L->next;
        free(L);
        L = p;
    }
    return OK;
}

/*3.将单链表L重置为空表*/
Status ClearList_L(LinkList &L) {
    LNode *p, *q;
    p = L->next;
    while (p) {
        q = p->next;
        free(p);
        p = q;
    }
    L->next = NULL;
    return OK;
}

/*4.单链表L为空表时返回TRUE，否则FALSE*/
Status ListEmpty_L(LinkList L){
    if (NULL == L->next)
        return TRUE;
    else
        return FALSE;
}

/*5.求单链表L的表长*/
int ListLength_L(LinkList L) {
    LNode *p;
    int count = 0;
    p = L->next;
    while (p) {
        count++;
        p = p->next;
    }
    return count;
}

/*6.查找。返回单链表L中第一个数据域值为e的结点地址，若不存在则返回NULL*/
LNode* Search_L(LinkList L, ElemType e) {
    LNode *p;
    if (NULL == L->next)    //L是空表
        return NULL;
    p = L->next;
    while (p != NULL && p->data != e) {     //查找值为e的结点
        p = p->next;
    }
    return p;   //若p=NULL则返回NULL，否则p->data==e,查找成功
}

/*7.返回p结点的直接后继结点的指针，若p结点是尾元结点则返回NULL*/
LNode* NextElem_L(LNode *p) {
    if (NULL == p->next)
        return NULL;
    return p->next;
}

/*8.构建元素e的结点，返回指向该结点的指针*/
LNode* MakeNode_L(ElemType e) {
    LNode *p;
    p = (LNode *)malloc(sizeof(LNode)); //分配结点空间
    if (NULL != p) {
        p->data = e;
        p->next = NULL;
    }
    return p;
}

/*9.在p结点之后插入q结点*/
Status InsertAfter_L(LNode *p, LNode *q) {
    if (NULL == p || NULL == q)
        return ERROR;       //参数不合理
    q->next = p->next;      //修改q的指针域
    p->next = q;            //修改p的指针域
    return OK;
}

/*10.删除p结点的直接后继结点，用e返回结点值，若p空或指向尾元指针则操作失败*/
Status DeleteAfter_L(LNode *p, ElemType &e) {
    LNode *q;
    if (NULL == p || NULL == p->next)
        return ERROR;       //删除位置不合理
    q = p->next;
    p->next = q->next;      //修改被删结点q的指针域
    e = q->data;
    free(q);                //释放结点q
    return OK;
}

/*11.遍历单链表L*/
void ListTraverse_L(LinkList L, Status(*visit)(ElemType e)) {
    LNode *p;
    ElemType e;
    p = L;
    while (NULL != p) {
        e = p->data;
        visit(e);
        p = p->next;
    }
}

/*12.建立一个长度为n的单链表，数组A[]提供n个元素值*/
Status CreatList_L(LinkList &L, int n, ElemType *A) {
    LNode *p, *q;
    int i;
    if (OVERFLOW == InitList_L(L))
        return OVERFLOW;
    p = L;
    for(i=0; i<n; i++){         //依次在表尾插入n个结点
        q = MakeNode_L(A[i]);
        InsertAfter_L(p, q);    //令p指向新插入结点
        p = q;
    }
    return OK;
}