线性表的顺序与链式实现

作者: 爱笑的云里看梦 | 来源:发表于2018-04-04 23:33 被阅读10次

C++线性表的链式存储结构
数据结构课程第四周线性表、链式表的比较和应用
线性链表
队列之-链式实现
线性表的链式存储结构Java实现
数据结构之有序线性表的链式存储结构
线性表的顺序存储与链式存储
数据结构-线性表（顺序表和链表）
线性表的顺序与链式实现
线性表的链式存储结构(LinkList)

简介

数据结构中的逻辑结构分为线性结构和非线性结构。简单地说，线性结构是N个数据元素的有序集合。

线性表是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：k1，k2，…，kn，其中k1是开始结点，kn是终端结点。

一、线性表的顺序表示和实现

线性表的顺序表示指的是用物理上的一段连续的地址来存储数据元素，如下图所示。如果第一个元素的在内存上的地址为a1，每个元素占用的空间是l，那么第n个元素的地址就是a1+(n-1) x l。

顺序表示.png

只要确定了第一个元素的地址，那么我们可以对线性表中的任一元素随机存取，由于编程语言中的数组也有随机存取的特点，下面就用数组来描述线性表的顺序存储结构。

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INIT_SIZE 10        //初始化表长
#define INCREMENT_SIZE 5    //分配增量

typedef int Status;
typedef int Elemtype;


//存储结构
typedef struct {
    Elemtype *elem;
    int length;
    int size;
}SqList;

//初始化一个空的线性表
Status InitList(SqList &L) {
    //分配内存空间
    L.elem = (Elemtype *)malloc(INIT_SIZE * sizeof(Elemtype));
    if(!L.elem) {
        //分配空间失败
        return ERROR;
    }
    L.length = 0;
    L.size = INIT_SIZE;
    return OK;
}

//销毁线性表
Status destroyList(SqList &L) {
    free(L.elem);
    L.length = 0;
    L.size = 0;
    return OK;
}

//清空线性表
Status clearList(SqList &L) {
    L.length = 0;
    return OK;
}

//判断线性表是否为空
Status isEmpty(const SqList L) {
    if(0 == L.length) {
        return TRUE;
    } else {
        return FALSE;
    }
}

//返回线性表的长度
int getLength(const SqList L) {
    return L.length;
}

//根据位置获取元素
Status getElemByLocation(const SqList L, int i, Elemtype &e) {
    if(i < 1 || i > L.length) {
        return ERROR;
    }
    e = L.elem[i - 1];
    return OK;
}

//比较两个元素是否相等
Status compare(Elemtype e1, Elemtype e2) {
    if(e1 == e2) {
        return 0;
    }else if(e1 > e2) {
        return 1;
    } else {
        return -1;
    }
}

//查找元素
Status findElem(const SqList L, Elemtype e,Status (*compare)(Elemtype,Elemtype)) {
    int i;
    for(i = 0; i < L.length; ++i) {
        if(!compare(L.elem[i], e)) {
            return i+1;
        }
    }
    if(i >= L.length) {
        return ERROR;
    }
    return ERROR;
}

//查找前驱元素
Status preElem(const SqList L,Elemtype cur_e, Elemtype &e) {
    int i;
    for(i = 0; i < L.length; ++i) {
        if(cur_e == L.elem[i]) {
            if(i != 0) {
                e = L.elem[i-1];
                return OK;
            } else {
                return ERROR;
            }
        }
    }
    if(i >= L.length) {
        return ERROR;
    }
    return ERROR;
}

//查找后继元素
Status nextElem(const SqList L,Elemtype cur_e, Elemtype &e) {
    int i;
    for(i = 0; i < L.length; ++i) {
        if(cur_e == L.elem[i]) {
            if(i + 1 < L.length) {
                e = L.elem[i+1];
                return OK;
            } else {
                return ERROR;
            }
        }
    }
    if(i >= L.length) {
        return ERROR;
    }
    return ERROR;
}

//插入一个元素
Status insertElem(SqList &L, int i, Elemtype e) {
    if(i < 1 || i > L.length + 1) {
        return ERROR;
    }

    if(L.length >= L.size) {
        Elemtype* newElem = (Elemtype *) realloc(L.elem,(L.size + INCREMENT_SIZE)*sizeof(Elemtype));
        if(!newElem) {
            return ERROR;
        }
        L.elem = newElem;
        L.size = L.size + INCREMENT_SIZE;
    }
    Elemtype *p = &L.elem[i - 1];
    Elemtype *q;
    if(L.length == 0) {
        q = &L.elem[L.length];
    } else {
        q = &L.elem[L.length - 1];
    }
    while (q >= p) {
        *(q+1) = *q;
        q--;
    }
    *p = e;
    L.length++;
    return OK;
}

//删除元素并且返回值
Status deleteElem(SqList &L, int i, Elemtype &e) {
    if(i < 1 || i > L.length) {
        return ERROR;
    }
    Elemtype *p = &L.elem[i - 1];
    e = *p;
    while (p < &L.elem[L.length - 1]) {
        *p = *(p+1);
        p++;
    }
    L.length --;
    return OK;
}

//访问元素
void visit(Elemtype e) {
    cout << e << " ";
}

//遍历线性表
Status traverseList(const SqList L, void (*visit)(Elemtype)) {
    int i;
    for(i = 0; i < L.length; ++i) {
        visit(L.elem[i]);
    }
    return OK;
}

二、线性表的链式存储和实现

线性表的顺序存储结构是逻辑位置和物理位置都相邻，而链式存储结构是逻辑位置相邻，但物理位置不一定相邻，相比顺序存储结构，它不能随机存取，但在插入和删除操作时不需要移动元素，大大提高了增加和删除元素的效率。

通常链式存储结构会有一个个结点组成，结点中包含两个域一个是数据域，一个是指针域，数据域中存储数据，指针域中存储下一个后继元素的地址，如下图所示，这一个个结点组成链表，也称线性链表或单链表。
实现代码如下：

/*
 * 线性表的链式存储
 * */
#include <iostream>
#include <cstdlib>
using namespace std;

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int ElemType;
typedef int Status;


//存储结构
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*linkList;

//初始化线性表
void initList(linkList &L) {
    L = (linkList)malloc(sizeof(LNode));
    if(!L) {
        exit(OVERFLOW);
    }
    L->next = NULL;
}

//销毁线性表
void destroyList(linkList &L) {
    linkList temp;
    while (L) {
        temp = L->next;
        free(L);
        L = temp;
    }
}

//清空线性表
void clearList(linkList L) {
    linkList p = L->next;
    L->next = NULL;
    destroyList(p);
}

//判断是否为空
Status isEmpty(linkList L) {
    if(L->next) {
        return FALSE;
    } else {
        return TRUE;
    }
}

//获取长度
int getLength(linkList L) {
    int i = 0;
    linkList p = L->next;
    while (p) {
        i++;
        p = p->next;
    }
    return i;
}

//根据位置获取元素
Status getElem(linkList L, int i, ElemType &e) {
    int j = 1;
    linkList p = L->next;
    while (p && j < i) {
        j++;
        p = p->next;
    }
    if(!p || j > i) {
        return ERROR;
    }
    e = p->data;
    return OK;
}

//比较两个元素是否相等
Status compare(ElemType e1, ElemType e2) {
    if(e1 == e2) {
        return 0;
    } else if(e1 > e2) {
        return 1;
    } else {
        return -1;
    }
}

//查找指定元素的位置
int findElem(linkList L, ElemType e,Status (*compare)(ElemType,ElemType)) {
    int i = 0;
    linkList p = L->next;
    while (p) {
        i++;
        if(!compare(p->data, e)) {
            return i;
        }
        p = p->next;
    }
    return -1;
}

//获得前驱元素
Status preElem(linkList L, ElemType cur_e, ElemType &pre_e) {
    linkList q, p = L->next;
    while (p->next) {
        q = p->next;
        if(q->data == cur_e) {
            pre_e = p->data;
            return OK;
        }
        p = q;
    }
    return ERROR;
}

//获得后继元素
Status nextElem(linkList L,ElemType cur_e, ElemType &next_e) {
    linkList p = L->next;
    while (p->next) {
        if(p->data == cur_e) {
            next_e = p->next->data;
            return OK;
        }
        p = p->next;
    }
    return ERROR;
}

//插入元素
Status insertElem(linkList &L, int i, ElemType e) {
    int j = 0;
    linkList s,p = L;
    while (p && j < i - 1) {
        j++;
        p = p->next;
    }
    if(!p || j > i - 1) {
        return ERROR;
    }
    s = (linkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

//删除元素
Status deleteElem(linkList L, int i, ElemType &e) {
    int j = 0;
    linkList q,p = L;
    while (p->next && j < i - 1) {
        j++;
        p = p->next;
    }
    if(!p->next || j > i - 1) {
        return ERROR;
    }
    q = p->next;
    p->next = q->next;
    e = q->data;
    free(q);
    return OK;
}
/*
 * 访问元素
 */
void visit(ElemType e)
{
    cout << e << " ";
}

/*
 * 遍历线性表
 */
void TraverseList(linkList L, void (*visit)(ElemType))
{
    linkList p = L->next;
    while (p)
    {
        visit(p->data);
        p = p->next;
    }
}

通过代码实现了线性结构中线性表的顺序及链式的表示方式。

顺序存储结构中的元素在逻辑位置和物理位置上都相邻，链式存储结构中的元素在逻辑位置上相邻，但在物理位置上不一定相邻。

顺序存储结构读取元素的效率比较高，链式存储结构添加和删除元素的效率比较高。链式存储结构除了单链表之外，还有循环链表和双向链表。