数据结构：单链表

main.c

//
// Created by 方朋 on 16/12/20.
//


#include <stdio.h>
#include <stdlib.h>
#include "global.h"


Status visit(ElemType e)
{
    printf("%d ", e);
    return OK;
}

typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node *LinkList;  // TODO:


/* 初始化顺序线性表 */
Status InitList(LinkList *L)
{
    *L = (LinkList)malloc(sizeof(Node));
    if (!(*L))
        return ERROR;

    (*L)->next = NULL;
    return OK;
}

/* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status ListEmpty(LinkList L)
{
    LinkList p = L->next;
    if (p) return FALSE;
    return OK;
}

/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList *L)
{
    LinkList p, q;
    p = (*L)->next;
    while (p)
    {
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;
    return OK;
}

/* 初始条件：顺序线性表L已存在。
 * 操作结果：返回L中数据元素个数 */
int ListLength(LinkList L)
{
    int len = 0;
    LinkList p = L->next;

    while (p)
    {
        len++;
        p = p->next;
    }
    return len;
}

/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值 */
Status GetElem(LinkList L, int i, ElemType *e)
{
    LinkList p = L->next;
    int j = 1;
    while (p && j < i)
    {
        p = p->next;
        j++;
    }
    if (!p || j > i) return ERROR;
    *e = p->data;
    return OK;
}

/* 初始条件：顺序线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int LocateElem(LinkList L, ElemType e)
{
    int i = 1;
    LinkList p = L->next;
    while (p){
        if (p->data == e) {
            return i;
        }
        p = p->next;
        i++;
    }

    return 0;
}


/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(LinkList *L,int i,ElemType e)
{
    LinkList p = *L;

    int j = 1;

    while (p && j < i)
    {
        p = p->next;
        j++;
    }
    if (!p || j > i) return ERROR;

    LinkList q = (LinkList)malloc(sizeof(Node));
    q->data = e;
    q->next = p->next;
    p->next = q;
    return OK;


}

/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(LinkList *L, int i, ElemType *e)
{
    LinkList p = (*L)->next;
    LinkList pre;
    int j = 1;
    while (p && j < i)
    {
        pre = p;
        p = p->next;
        j++;
    }

    if(!p || j > i) return ERROR;
    *e = p->data;
    pre->next = p->next;
    free(p);
    return OK;
}

/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(LinkList L)
{
    LinkList p = L->next;
    while (p)
    {
        visit(p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

/*  随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */
void CreateListHead(LinkList *L, int n)
{
    *L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */
    (*L)->next = NULL;                  // 先建立一个带头结点的单链表

    LinkList p;
    int j;

    for (j = 1; j < n + 1; ++j) {
        p = (Node *)malloc(sizeof(Node));       // 生成新结点
        p->data = j;
        p->next = (*L)->next;
        (*L)->next = p;
    }
}

/*  随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
void CreateListTail(LinkList *L, int n)
{
    LinkList p, r;
    *L = (LinkList)malloc(sizeof(Node));    // L 为整个表
    r = *L;         // 头结点, 也是尾结点
    int j;
    for (j = 1; j < n + 1 ; ++j) {
        p = (Node *)malloc(sizeof(Node));       // 生成新结点
        p->data = j;
        r->next = p;        /* 将表尾终端结点的指针指向新结点 */
        r = p;              /* 将当前的新结点定义为表尾终端结点 */
    }
    r->next = NULL;         /* 表示当前链表结束 */
}

int main(int argc, char **argv)
{
    LinkList L;
    ElemType e;
    Status i;
    int j,k;

    InitList(&L);
    printf("初始化L后：ListLength(L)=%d\n",ListLength(L));

    for(j=1;j<=5;j++)
        ListInsert(&L,1,j);
    printf("在L的表头依次插入1～5后：L.data=");
    ListTraverse(L);

    printf("ListLength(L)=%d \n",ListLength(L));
    i=ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)\n",i);

    ClearList(&L);
    printf("清空L后：ListLength(L)=%d\n",ListLength(L));
    i=ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)\n",i);

    for(j=1; j <= 10; j++)
        ListInsert(&L,j,j);
    printf("在L的表尾依次插入1～10后：L.data=");
    ListTraverse(L);

    printf("ListLength(L)=%d \n",ListLength(L));

    ListInsert(&L,1,0);
    printf("在L的表头插入0后：L.data=");
    ListTraverse(L);
    printf("ListLength(L)=%d \n",ListLength(L));

    GetElem(L,5,&e);
    printf("第5个元素的值为：%d\n",e);

    printf("*******\n");

    for(j=3; j<=4; j++)
    {
        k=LocateElem(L,j);
        if(k)
            printf("第%d个元素的值为%d\n",k,j);
        else
            printf("没有值为%d的元素\n",j);
    }

    printf("*******\n");

    k = ListLength(L); /* k为表长 */

    i = ListDelete(&L, 3, &e);
    if (i == ERROR)
        printf("删除第%d个数据失败\n",3);
    printf("删除第%d个的元素值为：%d\n",3,e);

    i = ListDelete(&L, 12, &e);
    if (i == ERROR) {
        printf("删除第%d个数据失败\n",12);
    } else {
        printf("删除第%d个的元素值为：%d\n",12,e);
    }


    printf("依次输出L的元素：");
    ListTraverse(L);

    j=5;
    ListDelete(&L,j,&e); /* 删除第5个数据 */
    printf("删除第%d个的元素值为：%d\n",j,e);

    printf("依次输出L的元素：");
    ListTraverse(L);

    i=ClearList(&L);
    printf("\n清空L后：ListLength(L)=%d\n",ListLength(L));

    CreateListHead(&L, 20);
    printf("整体创建L的元素(头插法)：");
    ListTraverse(L);

    i=ClearList(&L);
    printf("\n删除L后：ListLength(L)=%d\n",ListLength(L));
    CreateListTail(&L,20);
    printf("整体创建L的元素(尾插法)：");
    ListTraverse(L);

    return 0;
}