数据结构与算法-线性表

2020-05-17 本文已影响0人 MrDemon_

一、定义

满足数据元素不同,但是在同一个线性表中的元素必定具有相同的特点,即属于同一数据对象, 相邻数据元素之间存在这个序偶关系. 诸如此类由(n>=0)个数据特性相同的元素构成的有限序列称为线性表.

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

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

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

存储类别	顺序存储结构	单链表存储结构
存储分配方式	用一段连续的存储单元依次存储线性表的数据元素	采用链式存储结构，用一组任意的存储单元存放线性表的元素
时间性能	查找O(1)、插入和删除O(n)	查找O(n)、插入和删除O(1)
空间性能	需要预分配存储空间，分大了浪费，小了容易发生上溢	不需要分配存储空间，只要有就可以分配，元素个数不受限制

若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。
当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，用顺序存储结构效率会高很多

二、顺序存储实现

使用数组实现，一组地址连续的存储单元，数组大小有两种方式指定，一是静态分配，二是动态扩展。

注：线性表从1开始，而数组从0开始。

优点：随机访问特性，查找O(1)时间，存储密度高；逻辑上相邻的元素，物理上也相邻；
缺点：插入删除需移动大量元素。

顺序表

插入时：对于线性表来说最小能插入的位置是1，最大能插入的位置是8（=7+1），所以 1<= index <=(7+1)；
删除时：只能在蓝色方块之间寻找节点删除，即1 <= index <= 7

2.1 顺序表初始化

先定义一些状态

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

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

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

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

在初始化

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

2.2 顺序表的插入

/*
 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)+1;
 操作结果：在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;

}

2.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)) return ERROR;

    for(int j = i; j < L->length;j++){
        //被删除元素之后的元素向前移动
        L->data[j-1] = L->data[j];
    }
    //表长度-1;
    L->length --;

    return OK;

}

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

2.5 清空顺序表

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

2.6 判断顺序表为空

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

2.7 获取顺序表长度（元素个数）

int ListLength(Sqlist L)
{
    return L.length;
}

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

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

2.10 test

Sqlist L;
    Sqlist Lb;
    ElemType e;
    Status iStatus;

    //1.1 顺序表初始化
    iStatus = InitList(&L);
    printf("初始化L后: L.Length = %d\n", L.length);

    //1.2 顺序表数据插入
    for(int j=1; j <= 5;j++){
        iStatus = ListInsert(&L, 1, j);
    }
    printf("插入数据L长度: %d\n",L.length);

    //1.3 顺序表取值
    GetElem(L, 5, &e);
    printf("顺序表L第5个元素的值为:%d\n",e);

    //1.4 顺序表删除第2个元素
    ListDelete(&L, 2);
    printf("顺序表删除第%d元素,长度为%d\n",2,L.length);

    //1.5 清空顺序表
    iStatus = ClearList(&L);
    printf("清空后,L.length = %d\n",L.length);

    //1.6 判断List是否为空
    iStatus=ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)\n",iStatus);

    //1.8 TraverseList
    for(int j=1; j <= 5;j++){
        iStatus = ListInsert(&L, 1, j);
    }
    TraverseList(L);

三、单链表存储实现

链表的定义是递归的，它或者为空null，或者指向另一个节点node的引用，这个节点含有下一个节点或链表的引用。

与顺序存储相比，允许存储空间不连续，插入删除时不需要移动大量的元素，只需修改指针即可，但查找某个元素，只能从头遍历整个链表。

首元结点：指链表中存储线性表中第一个数据元素的结点，是链表的开始结点。

头指针：指向链表中第一个结点（或为头结点或为首元结点）的指针

头结点：头结点是在链表的首元结点之前附设的一个结点，数值域可不设任何信息（也可根据需求保存信息，如链表的长度等），头结点的指针域指向链表的第一个元素。

单链表分为带头结点和不带头结点两种，不管有没有头结点，头指针都指向链表的第一个节点（有头结点指向头结点）。

带头节点的好处有：

1.链表第一位置节点上的操作和其它位置上的操作一致（便于首元结点处理理）
2.无论链表是否为空，头指针都指向头结点，空表和非空表处理一样（便于空表和非空表的统一处理）

链表元素结构

链表元素结构g

没有头节点，首指针指向首元结点

有头节点，首指针指向头节点

含有头节点的空链表

含有头节点的非空链表

含有头节点的非空链表g

注：链表麻烦的地方是插入和删除时指针的修改，保证不断链，一般先链后断。

下面代码演示一下（以下代码都是带头结点的）

3.1 初始化单链表线性表

先定义一些状态

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

#define MAXSIZE 20 /* 存储空间初始分配量 */

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

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

typedef struct Node * LinkList;

初始化单链表线性表

Status InitList(LinkList *L){

    //产生头结点,并使用L指向此头结点
    *L = (LinkList)malloc(sizeof(Node));
    //存储空间分配失败
    if(*L == NULL) return ERROR;
    //将头结点的指针域置空
    (*L)->next = NULL;

    return OK;
}

3.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是插入位置前一个node, s是要插入的node
    p = *L;
    j = 1;

    //寻找第i-1个结点  0>1>2>3>4>5 i = 3
    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;

    s->next = p->next;
    //将s赋值给p的后继
    p->next = s;

    return OK;
}

单链表插入

3.3 单链表删除元素

/*
 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
 */

Status ListDelete(LinkList *L,int i,ElemType *e){

    int j;
    LinkList p,q;//p是插入位置前一个node, q是要删除的node
    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;
}

单链表删除元素

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

3.4 单链表元素输出

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

3.5 单链表清空

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

3.6 单链表前插入法（头插法）

将新节点插入到当前链表的表头，（头结点之后），插入的顺序与链表中的顺序相反，关键点就是记住旧的表头，生成一个新的放到旧表头前面

/* 随机产生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.7 单链表后插入法（尾插发）

增加一个尾指针，新节点插到链表的尾部，插入的顺序和链表的顺序一致

/* 随机产生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;
}

尾插发

数据结构与算法-线性表

一、定义

二、顺序存储实现

2.1 顺序表初始化

2.2 顺序表的插入

2.3 顺序表的删除

2.4 顺序表的取值

2.5 清空顺序表

2.6 判断顺序表为空

2.7 获取顺序表长度（元素个数）

2.8 顺序输出List

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

2.10 test

三、单链表存储实现

3.1 初始化单链表线性表

3.2 单链表插入

3.3 单链表删除元素

3.4 单链表取值

3.4 单链表元素输出

3.5 单链表清空

3.6 单链表前插入法（头插法）

3.7 单链表后插入法（尾插发）

猜你喜欢

热点阅读

数据结构与算法-线性表

一、定义

二、顺序存储实现

2.1 顺序表初始化

2.2 顺序表的插入

2.3 顺序表的删除

2.4 顺序表的取值

2.5 清空顺序表

2.6 判断顺序表为空

2.7 获取顺序表长度（元素个数）

2.8 顺序输出List

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

2.10 test

三、单链表存储实现

3.1 初始化单链表线性表

3.2 单链表插入

3.3 单链表删除元素

3.4 单链表取值

3.4 单链表元素输出

3.5 单链表清空

3.6 单链表前插入法 （头插法）

3.7 单链表后插入法 （尾插发）

猜你喜欢

热点阅读

3.6 单链表前插入法（头插法）

3.7 单链表后插入法（尾插发）