/*
    Name: 线性表抽象数据类型（使用单链表实现）
    Copyright:
    Author: 巧若拙
    Date:11-09-14 23:34
    Description:
*/

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>

#define MAXSIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int ElemType;
typedef int Status; //函数类型，其值是函数结果状态代码，如OK等

typedef struct Node{
    ElemType data;//数据域
    struct Node *next;//指针域
} Node;

typedef struct Node *LinkList;

Status InitList(LinkList *L);//建立一个带头结点的空线性表L
Status ListEmpty(LinkList L);//判断线性表是否为空，若线性表为空，返回TRUE，否则返回FALSE
Status ClearList(LinkList *L);//将线性表清空（只留下头结点）
int ListLength(LinkList L);//返回线性表L的元素个数
Status DisplayList(LinkList L);//输出线性表L的所有元素
Status GetElem(LinkList L, int i, ElemType *e);//将线性表L中第i个位置元素值赋给e
Status LocateElem(LinkList L, ElemType e);//在线性表L中查找是否存在与给定值e相等的元素
Status ListInsert(LinkList *L, int i, ElemType e);//在线性表L中的第i个位置之前插入新元素e
Status ListDelete(LinkList *L, int i, ElemType *e);//删除线性表L中的第i个位置，并将该元素值赋给e

int main(void)
{
    LinkList a = NULL;
    ElemType *p, e = 0;
    int i;
   
    InitList(&a);//建立一个空的线性表
   
    for (i=0; i<MAXSIZE; i++)
    {
        ListInsert(&a, i+1, i+100);
    }
   
    DisplayList(a);
   
    printf("len = %d\n", ListLength(a));
    for (i=1; i<ListLength(a); i+=2)
    {
        ListDelete(&a, i, &e);//删除线性表L中的第i个位置，并将该元素值赋给e
    }
    printf("len = %d\n", ListLength(a));
    printf("e = %d\n", e);
   
    DisplayList(a);
   
    i = 5;
    e = 1050;
    if (LocateElem(a, e))//在线性表L中查找是否存在与给定值e相等的元素
    {
        printf("存在%d\n", e);
    }
    else
    {
        printf("不存在%d\n", e);
        ListInsert(&a, i, e);
    }
   
    DisplayList(a);
   
    ListDelete(&a, ListLength(a), &e);//删除线性表L中的最后一个元素
    DisplayList(a);
   
    ListDelete(&a, 1, &e);//删除线性表L中的第一个元素
    DisplayList(a);
   
    return 0;
}

/*
函数功能：建立一个带头结点的空线性表L
初始条件：无
操作结果：初始化线性表L。操作成功返回OK，否则返回ERROR  
*/
Status InitList(LinkList *L)//建立一个带头结点的空线性表L  
{
    *L = (LinkList)malloc(sizeof(Node));

    if (!(*L))
    {
        printf("Out of space!");
        return ERROR;
    }
   
    (*L)->next = NULL;
   
    return OK;
}


/*
函数功能：判断线性表是否为空
初始条件：单链表线性表L已经存在
操作结果：若线性表为空，返回TRUE，否则返回FALSE
*/
Status ListEmpty(LinkList L)
{
    return (L->next == NULL) ? TRUE : FALSE;
}

/*
函数功能：将线性表清空
初始条件：单链表线性表L已经存在
操作结果：将线性表清空（只留下头结点）。操作成功返回OK，否则返回ERROR  
*/
Status ClearList(LinkList *L)
{
    LinkList p, q;
   
    if (*L == NULL)
    {
        return ERROR;
    }
   
    p = (*L)->next; //p指向第一个结点（非头结点）
    while (p)
    {
        q = p->next;
        free(p);
        p = q;
    }
   
    (*L)->next = NULL;
   
    return OK;
}

/*
函数功能：返回线性表L的元素个数
初始条件：单链表线性表L已经存在
操作结果：返回线性表L的元素个数
*/
int ListLength(LinkList L)
{
    LinkList p = L->next;
    int i = 0;
   
    while (p)
    {
        i++;
        p = p->next;   
    }
   
    return i;
}

/*
函数功能：输出线性表L的所有元素
初始条件：单链表线性表L已经存在
操作结果：输出线性表L的所有元素。操作成功返回OK，否则返回ERROR
*/
Status DisplayList(LinkList L)
{
    int i = 1;
    LinkList p = L->next;
   
    if (!p)
    {
        printf("none!\n");   
        return ERROR;
    }
   
    while (p)
    {
        printf("data[%d] = %d, ", i++, p->data);
        p = p->next;   
    }
    printf("\n");
        
    return OK;
}

/*
函数功能：将线性表L中第i个位置元素值赋给e
初始条件：单链表线性表L已经存在，1 <= i <= ListLength(L)；
操作结果：将线性表L中第i个位置元素值赋给e。操作成功返回OK，否则返回ERROR
*/
Status GetElem(LinkList L, int i, ElemType *e)
{
    int j = 1;
    LinkList p = L->next; //p指向第一个结点（非头结点）
   
    while (p && j < i) //寻找第i个结点
    {
        j++;
        p = p->next;   
    }
   
    if (!p || j > i) //第i个元素不存在
    {
        return ERROR;
    }
   
    *e = p->data;
   
    return OK;
}

/*
函数功能：在线性表L中查找是否存在与给定值e相等的元素
初始条件：单链表线性表L已经存在
操作结果：在线性表L中查找是否存在与给定值e相等的元素。找到返回TRUE，否则返回FALSE
*/
Status LocateElem(LinkList L, ElemType e)
{
    LinkList p = L->next; //p指向第一个结点（非头结点）
   
    while (p)
    {
        if (p->data == e)
        {
            return TRUE;
        }
        p = p->next;   
    }
   
    return FALSE;
}

/*
函数功能：在线性表L中的第i个位置之前插入新元素e
初始条件：单链表线性表L已经存在，1 <= i <= ListLength(L)；
操作结果：在线性表L中的第i个位置之前插入新元素e。操作成功返回OK，否则返回ERROR  
*/
Status ListInsert(LinkList *L, int i, ElemType e)
{
    LinkList s, p = *L; //p指向头结点
    int j = 1;
   
    while (p && j < i)//寻找第i-1个结点
    {
        j++;
        p = p->next;   
    }
   
    if (!p || j > i) //第i-1个结点不存在
    {
        return ERROR;
    }
   
    s = (LinkList)malloc(sizeof(Node));
    if (!s)
    {
        printf("Out of space!");
        return ERROR;
    }
   
    s->data = e;
    s->next = p->next;
    p->next = s;
   
    return OK;
}

/*
函数功能：删除线性表L中的第i个位置，并将该元素值赋给e
初始条件：单链表线性表L已经存在，1 <= i <= ListLength(L)；
操作结果：删除线性表L中的第i个位置，并将该元素值赋给e。
操作成功返回OK，否则返回ERROR  
*/
Status ListDelete(LinkList *L, int i, ElemType *e)
{
    LinkList q, p = *L; //p指向头结点
    int j = 1;
   
    while (p->next && j < i)//寻找第i个结点
    {
        j++;
        p = p->next;   
    }
   
    if (!(p->next) || j > i) //第i个结点不存在
    {
        return ERROR;
    }
   
    q = p->next; //q指向第i个结点
    p->next = q->next;
    *e = q->data;
    free(q);
   
    return OK;
}

补充一个对单链表线性表进行插入排序的算法，其中用到一个小技巧，不用定位插入位置的前驱结点，很巧妙哦！
/*
函数功能：给单链表线性表排序
初始条件：单链表线性表L已经存在，1 <= i <= ListLength(L)；
操作结果：使用插入排序的方法，为单链表线性表排序。
操作成功返回OK，否则返回ERROR
*/
Status ListSort(LinkList *L)
{
ElemType temp;
LinkList q, p, pos = (*L)->next; //p指向第1个结点

if (!pos)
{
printf("空表!");
return ERROR;
}
while (pos->next != NULL)//寻找最后一个结点
{
pos = pos->next;
}

while ((*L)->next != pos)
{
q = (*L)->next;
(*L)->next = q->next;
p = pos;
while (p->next != NULL && p->data < q->data) //寻找插入点
{
p = p->next;
}

q->next = p->next; //在p后插入q
p->next = q;

if (p->data > q->data) //若p的值大于q，交换二者的值，以保证线性表有序
{
temp = p->data;
p->data = q->data;
q->data = temp;
}

}

return OK;
}