一、线性表

线性表是最基本、最简单，也是最常用的一种数据结构。 一个线性表(linear list)是n个具有相同特性的数据元素的有限序列。 数据元素之间的关系是一对一。

线性、非线性是在逻辑层次上讨论，不考虑存储层次

1.1 顺序表

顺序存储，逻辑相邻，物理存储地址也相邻

1.1.1 数据结构声明

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
/* ElementType类型根据实际情况而定，这里假设为int */
typedef int ElementType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;
//顺序表结构设计
typedef struct {
    ElementType *data;
    int length;
}Sequencelist;

1.1.2.顺序表初始化

Status InitList(Sequencelist *list){
    //为顺序表分配一个大小为MAXSIZE 的数组空间
    list->data =  malloc(sizeof(ElementType) * MAXSIZE);
    //存储分配失败退出
    if(!list->data) exit(ERROR);
    //空表长度为0
    list->length = 0;
    return OK;
}

1.1.3.顺序表的插入

Status ListInsert(Sequencelist *list,int i,ElementType e){
    //i值不合法判断
    if((i<1) || (i>list->length+1)) return ERROR;
    //存储空间已满
    if(list->length == MAXSIZE) return ERROR;
    //插入数据不在表尾,则先移动出空余位置
    if(i <= list->length){
        for(int j = list->length-1; j>=i-1;j--){
            //插入位置以及之后的位置后移动1位
            list->data[j+1] = list->data[j];
        }
    }
    //将新元素e 放入第i个位置上
    list->data[i-1] = e;
    //长度+1;
    ++list->length;
    return OK;
}

1.1.4.顺序标的取值

Status GetElem(Sqlist L,int i, ElemType *e){
    //判断i值是否合理, 若不合理,返回ERROR
    if(i<1 || i > L.length) return  ERROR;
    //data[i-1]单元存储第i个数据元素.
    *e = L.data[i-1];
    return OK;
}

1.1.5顺序表的删除

/*
 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 操作结果: 删除L的第i个数据元素,L的长度减1
 */
Status ListDelete(Sqlist *L,int i){
    //线性表为空
    if(L->length == 0) return ERROR;
    //i值不合法判断
    if((i<1) || (i>L->length)) return ERROR;
    for(int j = i; j < L->length;j++){
        //被删除元素之后的元素向前移动
        L->data[j-1] = L->data[j];
    }
    //表长度-1;
    L->length --;
    return OK;
}

1.1.6 清空顺序表

/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(Sqlist *L)
{
    L->length=0;
    return OK;
}

1.1.7.判断顺序表是否为空

/* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status ListEmpty(Sqlist L)
{
    if(L.length==0)
        return TRUE;
    else
        return FALSE;
}

1.1.8 获取顺序表的长度

//1.7 获取顺序表长度ListEmpty元素个数 */
int ListLength(Sqlist L)
{
    return L.length;
}

1.1.9 顺序表的查找

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

1.2 单链表

链式存取，用一组地址任意的存储单元存放线性表中的数据元素 此处我们引入了头结点，哨兵

数据结构声明

结点

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
/* ElementType类型根据实际情况而定，这里假设为int */
typedef int ElementType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;
//单链表结构设计
typedef struct {
    ElementType data;//数据
    struct Node *next;//指针域
}Node;
typedef struct Node * LinkList;

1.2.1.初始化

Status InitList(LinkList *list){
    //初始化哨兵，听起来高大上
    *list = (LinkList)malloc(sizeof(Node));
    //存储空间分配失败
    if(*list == NULL) return ERROR;
    //将头结点的指针域置NULL
    (*list)->next = NULL;
    return OK;
}

1.2.2 遍历Traverse

Status ListTraverse(LinkList list)
{
    LinkList p = list->next;
    while(p)
    {
        printf("%d\n",p->data);
        p = p->next;
    }
    return OK;
}

1.2.3 单链表插入

/*
 初始条件:顺序线性表L已存在,1≤i≤ListLength(L);
 操作结果：在L中第i个位置之后插入新的数据元素e，L的长度加1;
 */
Status ListInsert(LinkList *L,int i,ElemType e){
    int j;
    LinkList p,s;
    p = *L;
    j = 1;
    //寻找第i-1个结点
    while (p && j<i) {
        p = p->next;
        ++j;
    }
    //第i个元素不存在
    if(!p || j>i) return ERROR;
    //生成新结点s
    s = (LinkList)malloc(sizeof(Node));
    //将e赋值给s的数值域
    s->data = e;
    //将p的后继结点赋值给s的后继
    s->next = p->next;
    //将s赋值给p的后继
    p->next = s;
    return OK;
}

1.2.4 单链表读取值

/*
 初始条件: 顺序线性表L已存在,1≤i≤ListLength(L);
 操作结果：用e返回L中第i个数据元素的值
 */
Status GetElem(LinkList L,int i,ElemType *e){
    //j: 计数.
    int j;
    //声明结点p;
    LinkList p;
    //将结点p 指向链表L的第一个结点;
    p = L->next;
    //j计算=1;
    j = 1;
    //p不为空,且计算j不等于i,则循环继续
    while (p && j<i) {
        //p指向下一个结点
        p = p->next;
        ++j;
    }
    //如果p为空或者j>i,则返回error
    if(!p || j > i) return ERROR;
    //e = p所指的结点的data
    *e = p->data;
    return OK;
}

1.2.5 单链表删除元素

/*
 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
 */
Status ListDelete(LinkList *L,int i,ElemType *e){
    int j;
    LinkList p,q;
    p = (*L)->next;
    j = 1;
    //查找第i-1个结点,p指向该结点
    while (p->next && j<(i-1)) {
        p = p->next;
        ++j;
    }
    //当i>n 或者 i<1 时,删除位置不合理
    if (!(p->next) || (j>i-1)) return  ERROR;
    //q指向要删除的结点
    q = p->next;
    //将q的后继赋值给p的后继
    p->next = q->next;
    //将q结点中的数据给e
    *e = q->data;
    //让系统回收此结点,释放内存;
    free(q);
    return OK;
}

1.2.6 清空链表

/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList *L)
{
    LinkList p,q;
    p=(*L)->next;           /*  p指向第一个结点 */
    while(p)                /*  没到表尾 */
    {
        q=p->next;
        free(p);
        p=q;
    }
    (*L)->next=NULL;        /* 头结点指针域为空 */
    return OK;
}

1.2.7 单链表前插入法

/* 随机产生n个元素值,建立带表头结点的单链线性表L(前插法)*/
void CreateListHead(LinkList *L, int n){
    LinkList p;
    //建立1个带头结点的单链表
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    //循环前插入随机数据
    for(int i = 0; i < n;i++)
    {
        //生成新结点
        p = (LinkList)malloc(sizeof(Node));
        //i赋值给新结点的data
        p->data = i;
        //p->next = 头结点的L->next
        p->next = (*L)->next;
        //将结点P插入到头结点之后;
        (*L)->next = p;
    }
}

1.2.8 单链表后插入法

/* 随机产生n个元素值,建立带表头结点的单链线性表L(后插法)*/
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 = p;
    }
    //将尾指针的next = null
    r->next = NULL;
}