数据结构与算法02——线性表

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

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。

对于⾮非空的线性表和线性结构,其特点如下:

1、存在唯⼀的被称作“第一个”的数据元素，存在唯⼀的“最后⼀个”的数据元素。

2、除了了第一个之外，结构中的每个数据元素均有⼀个前驱

3、除了了最后⼀个之外，结构中的每个数据元素都有⼀个后继

顺序表的存储结构

线性表的顺序表示指的是一组地址连续的存储单元依次存储线性表的数据元素，也称为线性表的顺序存储结构或顺序映像。通常称这种存储结构的线性表为顺序表(Sequential List). 其特点是,逻辑上相邻的数据元素物理次序也是相邻的。

单链表的节点：是由数据域和指针域组成

image.png

单链表的首指针指向首元结点（第一个节点），最后一个节点的指针域为空，其余节点的指针域指向下一个节点。

image.png

单链表的头结点
1.便于首元结点的处理
2.便于空表和非空表的统一处理

image.png

二、关于顺序存储的实现
顺序表的结构设计

/* ElemType类型根据实际情况而定，这里假设为int */
typedef int ElemType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;
//顺序表结构设计
typedef struct {
    ElemType *data;
    int length;
}Sqlist;

length是作为一个线性表判断的依据

1.初始化

Status InitList (Sqlist *L){
    //为顺序表分配一个大小为MAXSIZE 的数组空间
    L->data = malloc(sizeof(ElemType)* MAXSIZE);
    if(!L->data) exit(ERROR);
     //空表长度为0
     L->length = 0;
     return OK;
}

2.数据插入

/*
初始条件：顺序线性表L已存在,1≤i≤ListLength(L);
操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
*/
Status ListInsert(Sqlist *L,int i,ElemType e){
    
    //i值不合法判断
    if((i<1) || (i>L->length+1)) return ERROR;//因为  习惯。是从第一位开始存储的
    //存储空间已满
    if(L->length == MAXSIZE) return ERROR;
 
    //插入数据不在表尾,则先移动出空余位置
    if(i <= L->length){
        for(int j = L->length-1; j>=i-1;j--){
       
            //插入位置以及之后的位置后移动1位
            L->data[j+1] = L->data[j];
        }
    }
    
    //将新元素e 放入第i个位置上
    L->data[i-1] = e;
    //长度+1;
    ++L->length;
    
    return OK;
    
}

3.顺序表的删除

/*
 初始条件：顺序线性表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+1)) return ERROR;
    
    for(int j = i; j < L->length;j++){
        //被删除元素之后的元素向前移动
        L->data[j-1] = L->data[j];
    }
    //表长度-1;
    L->length --;
    return OK;
}

4.删除顺序表

/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
    L->length=0;

5.顺序表查找元素并返回位置

/* 初始条件：顺序线性表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;
}

三、线性表-关于链式存储的设计
单链表的插入（前插法和后插法）
在单链表的的两个数据元素a,b之间插入一个元素c ，p是单链表存储结构中指向结点a的指针

1.找到插入结点之前的结点的指针p
2.创建一个新的结点s
3.给s的数据域赋值
4.把s的指针域next指向要插入的结点之后的结点，就是b
5.把a的指针指向s

image.png

单链表的删除（a,b,c）删除b
1.找到删除结点之前的结点的指针p
2.创建一个指针s指向要删除的结点b
3.把a的指针域的next指向b的next
4.把s结点释放free

image.png

（如果不释放会一直占用这块内存）

//3.1 单链表前插入法
/* 随机产生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;
        
    }
}

//3.2 单链表后插入法
/* 随机产生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;
  
}

不管是前插法还是后插法：都是先处理要插入的结点（要插入的的结点需要一个指针域next去指向它，防止丢失），再更新新结点的指针域next的指向，最后更新首元结点的指向或者表尾终端结点的指向