1. 线性表的定义和特点

线性表：由(n>=0)个数据特性相同的元素构成的有限序列。

• 对于非空的线性表和线性结构，其特点如下：

  1. 存在唯一的一个被称作"第一个"的数据元素
  2. 存在唯一的一个被称作"最后一个"的数据元素
  3. 除了第一个之外，结构中的每个数据元素均有一个前驱
  4. 除了最后一个之外，结构中的每个数据元素都有一个后继

线性表中的元素的个数n定义为线性表的长度，如果n = 0则称为空表。

1.1 线性表的类型定义

ADT List{
        Data: 线性表的数据对象集合为{a1,a2,......an}，每个元素的类型均为DataType。
                    除了第一个元素a1外，每一个元素有且只有一个直接前驱元素。
            除了最后一个元素an外，每个元素有且只有一个直接后继元素。
              数据元素之间的关系是一对一的关系。
    
Operation
    InitList(&L) 
    操作结果:初始化操作，建立一个空的线性表L.

    DestroyList(&L) 
    初始条件: 线性表L已存在
    操作结果: 销毁线性表L.

    ClearList(&L)
    初始条件: 线性表L已存在
    操作结果: 将L重置为空表.

    ListEmpty(L)
    初始条件: 线性表L已存在
    操作结果: 若L为空表，则返回true，否则返回false.

    ListLength(L)
    初始条件: 线性表L已存在
    操作结果: 返回L中数据元素的个数

    GetElem(L，i，&e)
    初始条件: 线性表L已存在，且1<=i<ListLength(L)
    操作结果: 用e返回L中第i个数据元素的值;

    LocateElem(L，e)
    初始条件: 线性表L已存在
    操作结果: 返回L中第1个值与e相同的元素在L中的位置. 若数据不存在则返回0;

    PriorElem(L，cur_e，&pre_e);
    初始条件: 线性表L已存在
    操作结果: 若cur_e是L的数据元素，且不是第一个，则用pre_e返回其前驱，否则操作失败.

    NextElem(L，cur_e，&next_e);
    初始条件: 线性表L已存在
    操作结果: 若cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败.

    ListInsert(L，i，e);
    初始条件: 线性表L已存在，且1<=i<=listLength(L)
    操作结果: 在L中第i个位置之前插入新的数据元素e，L长度加1.

    ListDelete(L，i);
    初始条件: 线性表L已存在，且1<=i<=listLength(L)
    操作结果: 删除L的第i个元素，L的长度减1.

    TraverseList(L);
    初始条件: 线性表L已存在
    操作结果: 对线性表L进行遍历，在遍历的过程中对L的每个结点访问1次. 
    
} ADT List;

2. 顺序表

2.1 结构设计

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

/* ElemType类型根据实际情况而定，这里假设为int */
typedef int ElemType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;

/*线性结构使用顺序表的方式存储*/

//顺序表结构设计
typedef struct {
    ElemType *datas;
    int length;
} SqList;

2.2 方法实现

//1.1 顺序表初始化
Status InitList(SqList *L)
{
    // 为顺序表分配一个大小为MAXSIZE的数组空间
    L->datas = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);
    // 存储分配失败退出
    if (!L->datas) exit(ERROR);
    //空表长度为0
    L->length = 0;
    return OK;
}

//1.2 顺序表的取值
Status GetElem(SqList L, int idx, ElemType *elem)
{
    //判断i值是否合理，若不合理，返回ERROR
    if (idx < 0
        || idx > L.length) {
        return ERROR;
    }
    *elem = L.datas[idx];
    return OK;
}

//1.3 顺序输出List
Status TraverseList(SqList L)
{
    for (int i = 0; i < L.length; i++)
        printf("%d ", L.datas[i]);
    printf("\n");
    return OK;
}

//1.4 顺序表的插入
Status InsertList(SqList *L, int idx, ElemType elem)
{
    //idx值不合法判断
    if (idx < 0
        || idx > L->length
        || L->length == MAXSIZE) { //存储空间已满
        return ERROR;
    }
    // 插入数据不在表尾,则先移动出空余位置
    if (idx < L->length) {
        // 插入位置以及之后的位置后移动1位
        for (int i = L->length; i > idx; i--)
            L->datas[i] = L->datas[i-1];
    }
    // 将新元素elem放入第idx个位置上
    L->datas[idx] = elem;
    // 长度+1
    ++L->length;
    return OK;
}

//1.5 顺序表的删除
Status ListDelete(SqList *L, int idx) {
    if (L->length == 0 //空表
        || idx < 0 //idx值不合法判断
        || idx > L->length) {
        return ERROR;
    }
    if (idx < L->length) {
        // 被删除元素之后的元素向前移动
        for (int i = idx + 1; i < L->length; i++)
            L->datas[i-1] = L->datas[i];
    }
    // 长度-1
    --L->length;
    return OK;
}

//1.6 清空顺序表
Status ClearList(SqList *L)
{
    L->length=0;
    return OK;
}

//1.7 判断顺序表清空
Status ListEmpty(SqList L)
{
    return L.length == 0;
}

//1.8 获取顺序表长度
int ListLength(SqList L)
{
    return L.length;
}

//1.9 顺序表查找元素并返回位置
int LocateElem(SqList L, ElemType elem)
{
    int i;
    // 循环比较
    for (i = 0; i < L.length; i++)
        if (L.datas[i] == elem)
            return i;
    // 表里面没找到
    return NOT_FOUND;
}

int main(int argc, const char * argv[]) {
    
    SqList L;
    //初始化
    if (InitList(&L)) {
        printf("Init OK.\n");
    }
    //插入数据
    for (int i = 0; i < MAXSIZE; i++) {
        if (InsertList(&L, i, i) == ERROR) {
            printf("insert ERROR.\n");
        }
    }
    //遍历
    TraverseList(L);
    
    //获取第5个元素
    ElemType elem;
    GetElem(L, 5, &elem);
    printf("5th: %d\n", elem);
    
    //删除第5个元素
    ListDelete(&L, 5);
    TraverseList(L);
    
    int loc = LocateElem(L, 6);
    if (loc != NOT_FOUND) {
        printf("6 is %dth element\n", loc);
    }
    
    return 0;
}

主函数：

int main(int argc, const char * argv[]) {
    
    SqList L;
    //初始化
    if (InitList(&L)) {
        printf("Init OK.\n");
    }
    //插入数据
    for (int i = 0; i < MAXSIZE; i++) {
        if (InsertList(&L, i, i) == ERROR) {
            printf("insert ERROR.\n");
        }
    }
    //遍历
    TraverseList(L);
    
    //获取第5个元素
    ElemType elem;
    GetElem(L, 5, &elem);
    printf("5th: %d\n", elem);
    
    //删除第5个元素
    ListDelete(&L, 5);
    TraverseList(L);
    
    int loc = LocateElem(L, 6);
    if (loc != NOT_FOUND) {
        printf("6 is %dth element\n", loc);
    }
    
    return 0;
}

// 输出
Init OK.
0 1 2 3 4 5 6 7 8 9 
5th: 5
0 1 2 3 4 6 7 8 9 
6 is 5th element
Program ended with exit code: 0

3. 链表

3.1 结构设计

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

/* ElemType类型根据实际情况而定，这里假设为int */
typedef int ElemType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;

/*线性结构使用顺序表的方式存储*/

//链表结构设计
typedef struct Node {
    ElemType data;
    struct Node *next;
} Node;

3.2 方法实现

//1.1 初始化单链表线性表
Status InitList(LinkList *L)
{
    //产生头结点,并使用L指向此头结点
    *L = (LinkList)malloc(sizeof(Node));
    //存储空间分配失败
    if (*L == NULL) return ERROR;
    //将头结点的指针域置空
    (*L)->next = NULL;
    return OK;
}

//1.2 单链表的取值
Status GetElem(LinkList L, int idx, ElemType *elem)
{
    // 用来计数
    int i = 0;
    // 声明一个节点，指向头结点的下一个
    LinkList p = L->next;
    // p不为空，且i小于idx,则循环继续
    while (p && i < idx) {
        p = p->next;
        i++;
    }
    //如果p为空或者i>idx,则返回error
    if(!p || i > idx) return ERROR;
    //elem = p所指的结点的data
    *elem = p->data;
    return OK;
}

//1.3 顺序输出单链表
Status ListTraverse(LinkList L)
{
    // 声明一个节点，指向头结点的下一个
    LinkList p = L->next;
    while (p) {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

//1.4 单表的插入
Status ListInsert(LinkList *L, int idx, ElemType elem)
{
    int i = 0;
    LinkList p, s;
    // 寻找第idx-1个结点，所以这里指向表头
    p = *L;
    while (p && i < idx) {
        p = p->next;
        i++;
    }
    // 第idx个元素不存在
    if(!p || i > idx) return ERROR;
    
    // 创建新节点
    s = (LinkList)malloc(sizeof(Node));
    s->data = elem;
    //将p的后继结点赋值给s的后继
    s->next = p->next;
    //将s赋值给p的后继
    p->next = s;
    return OK;
}

//1.5 单链表删除元素
Status ListDelete(LinkList *L, int idx, ElemType *elem)
{
    int i = 0;
    LinkList p, q;
    // 寻找第idx-1个结点，所以这里指向表头
    p = *L;
    while (p && i < idx) {
        p = p->next;
        i++;
    }
    // 第idx个元素不存在
    if(!p || i > idx) return ERROR;
    // q指向要删除的结点
    q = p->next;
    // 将q的后继赋值给p的后继
    p->next = q->next;
    // 将q结点中的数据给elem
    *elem = q->data;
    // 释放被删除节点
    free(q);
    return OK;
}

//1.6 清空单链表
Status ClearList(LinkList *L)
{
    LinkList p, q;
    // 从表头下一个开始删
    p = (*L)->next;
    // 清空表头，防止野指针
    (*L)->next = NULL;
    while(p) {
        // q指向要删除的结点的下一个节点
        q = p->next;
        // 释放被删除节点
        free(p);
        // p变为下一个节点
        p = q;
    }
    return OK;
}

//1.7 判断顺序表清空
Status ListEmpty(LinkList L)
{
    return L->next == NULL;
}

//1.8 获取顺序表长度
int ListLength(LinkList L)
{
    int i = 0;
    LinkList p = L;
    while (p) {
        p = p->next;
        i++;
    }
    return i;
}

//1.9 顺序表查找元素并返回位置
int LocateElem(LinkList L, ElemType elem)
{
    if (L->next == NULL) return NOT_FOUND;
    int i = 0;
    LinkList p = L->next;
    while (p) {
        if (p->data == elem) {
            return i;
        }
        p = p->next;
        i++;
    }
    return NOT_FOUND;
}

主函数：

int main(int argc, const char * argv[]) {
    
    LinkList L;
    ElemType elem;
        
    //初始化
    if (InitList(&L)) {
        printf("Init OK.\n");
    }
    //插入数据
    for (int i = 0; i < MAXSIZE; i++) {
        if (ListInsert(&L, i, i) == ERROR) {
            printf("insert ERROR.\n");
        }
    }
    //遍历
    ListTraverse(L);
    
    //获取第6个元素
    GetElem(L, 5, &elem);
    printf("6th: %d\n", elem);
    
    //删除第6个元素
    ListDelete(&L, 5, &elem);
    //遍历
    ListTraverse(L);
    
    int loc = LocateElem(L, 6);
    if (loc != NOT_FOUND) {
        printf("6 is at %d\n", loc);
    }
    
    return 0;
}

// 输出
Init OK.
0 1 2 3 4 5 6 7 8 9 
6th: 5
0 1 2 3 4 6 7 8 9 
6 is at 5
Program ended with exit code: 0

3.3 初始化头插法

新节点插入到头结点之后：

void CreateListHead(LinkList *L, int n){
    // 生成头结点
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    // 循环前插入随机数据
    LinkList p;
    for (int i = 0; i < n; i++) {
        p = (LinkList)malloc(sizeof(Node));
        p->data = i;
        // 新节点指向头结点的下一个节点
        p->next = (*L)->next;
        // 头结点指向新节点
        (*L)->next = p;
    }
}

3.4 初始化尾插法

新节点插入到最后：

void CreateListTail(LinkList *L, int n)
{
    LinkList p, r;
    // 建立1个带头结点的单链表
    *L = (LinkList)malloc(sizeof(Node));
    //r指向尾部的结点
    r = *L;
    // 循环尾插入随机数据
    for (int i = 0; i < n; i++) {
        p = (Node *)malloc(sizeof(Node));
        p->data = i;
        // 尾节点的下一个节点指向新节点
        r->next = p;
        // r指向当前的尾节点
        r = p;
    }
    // 插入完毕，尾节点的下一个节点应该为NULL
    r->next = NULL;
}