数据结构与算法3-线性表

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

• 存在唯⼀的一个被称作”第一个”的数据元素;
• 存在唯一的一个被称作”最后一个"的数据元素
• 除了了第⼀个之外,结构中的每个数据元素均有一个前驱
• 除了了最后⼀个之外,结构中的每个数据元素都有一个后继.

线性表的类型定义

线性表是一个相当灵活的数据结构,其长度可根据需要增长或缩短,即对线性表的数据元素不仅可以进行访问,而且可以对其进行插入和删除等操作.

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.

线性表的顺序表示与实现

1. 线性表的顺序存储表示

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

#define MAXSIZE 100
#define ElemType int

typedef struct {
    ElemType *data;
    int length;
}Sqlist;

顺序表的基本操作的实现

1. 初始化

顺序表的初始化就是构成一个空的顺序表;
算法步骤:
1.为顺序表L动态分配一个预定义大小的数组空间,使elem 指向这段空间的基地址;
2.将表的当前长度设置为0;

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

2. 顺序表插入

算法步骤:
1.判断插入位置i是否合法(i值的合法范围1<=i<n+1),若不合法则返回ERROR;
2.判断顺序表的存储空间是否已满,若满则返回ERROR;
3.将第n个至第i个位置的元素依次向后移动一个位置,空出第i个位置(i = n+1)时无需要移动;
4.将要插入的新元素e放入第i个位置;
5.表长累积1.

//1.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.顺序表取值

算法步骤
1.判断指定的位置序号i是否合理(1<=i<L.length),若不合理,则返回ERROR;
2.若i值合理,则将第i个数据元素L.data[i-1]赋值给参数e, 通过e返回第i个数据元素的传值.

//1.2 顺序表的取值
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;
}

4.顺序表删除

算法步骤
1.判断删除位置i的合法(合法值 1 <= i <=n),若不合法则返回ERROR;
2.判断线性表是否为空
3.将第 i+1 个至第 n 个的元素依次向前移动一个位置( i=n 时无需移动)
4.表长减1;

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

5.清空顺序表

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

6.判断顺序表清空

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

7.获取顺序表长度

//1.7 获取顺序表长度
/* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(Sqlist L)
{
    return L.length;
}

8.顺序输出List

//1.8 顺序输出List
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status TraverseList(Sqlist L)
{
    int i;
    for(i=0;i<L.length;i++)
        printf("%d\n",L.data[i]);
    printf("\n");
    return OK;
}

9.查找元素并返回位置

//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;
}

线性表的链式表示与实现

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

image.png

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

//定义结点
typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

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

image.png

单链表的头结点

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

image.png

1.初始化

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

2.单链表插入

image.png

//2.2 单链表插入
/*
 初始条件:顺序线性表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;
}

3.单链表取值

//2.3 单链表取值
/*
 初始条件: 顺序线性表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;
}

4.单链表删除元素

image.png

//2.4 单链表删除元素
/*
 初始条件：顺序线性表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;
}

5.顺序输出

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

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;
}

7.创建线性表-前插法

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;
        
    }
}

8.创建线性表-后插法

image.png

//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;
    
}

线性表-链式结构和顺序结构对比

存储分配⽅方式

• 顺序存储结构⽤一段连续的存储单元依次存储线性表的数据元素;
• 单链表采⽤用链式存储结构,用一组任意的存储单元存放线性表的元素;

时间性能

• 查找

  • 顺序存储 O(1)
  • 单链表O(n)

• 插⼊入和删除

  • 存储结构需要平均移动一个表⻓一半的元素,时间O(n)
  • 单链表查找某位置后的指针后,插⼊和删除为 O(1)

空间性能

• 顺序存储结构需要预先分配存储空间,分太⼤大,浪费空间;分⼩小了了,发⽣生上溢出;
• 单链表不不需要分配存储空间,只要有就可以分配, 元素个数也不不受限制;