簡介

數(shù)據(jù)結(jié)構(gòu)中的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)屉佳。簡單地說把敢，線性結(jié)構(gòu)是N個數(shù)據(jù)元素的有序集合钞楼。

線性表是一個含有n≥0個結(jié)點的有限序列，對于其中的結(jié)點蒸眠，有且僅有一個開始結(jié)點沒有前驅(qū)但有一個后繼結(jié)點漾橙，有且僅有一個終端結(jié)點沒有后繼但有一個前驅(qū)結(jié)點，其它的結(jié)點都有且僅有一個前驅(qū)和一個后繼結(jié)點楞卡。一般地霜运，一個線性表可以表示成一個線性序列：k1，k2蒋腮，…淘捡，kn，其中k1是開始結(jié)點池摧，kn是終端結(jié)點焦除。

一、線性表的順序表示和實現(xiàn)

線性表的順序表示指的是用物理上的一段連續(xù)的地址來存儲數(shù)據(jù)元素险绘，如下圖所示踢京。如果第一個元素的在內(nèi)存上的地址為a1，每個元素占用的空間是l宦棺，那么第n個元素的地址就是a1+(n-1) x l瓣距。

順序表示.png

只要確定了第一個元素的地址，那么我們可以對線性表中的任一元素隨機存取代咸，由于編程語言中的數(shù)組也有隨機存取的特點蹈丸，下面就用數(shù)組來描述線性表的順序存儲結(jié)構(gòu)。

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


//存儲結(jié)構(gòu)
typedef struct {
    Elemtype *elem;
    int length;
    int size;
}SqList;

//初始化一個空的線性表
Status InitList(SqList &L) {
    //分配內(nèi)存空間
    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;
}

//根據(jù)位置獲取元素
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;
}

//查找前驅(qū)元素
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;
}

二呐芥、線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)

線性表的順序存儲結(jié)構(gòu)是邏輯位置和物理位置都相鄰逻杖，而鏈?zhǔn)酱鎯Y(jié)構(gòu)是邏輯位置相鄰，但物理位置不一定相鄰思瘟，相比順序存儲結(jié)構(gòu)荸百，它不能隨機存取，但在插入和刪除操作時不需要移動元素滨攻，大大提高了增加和刪除元素的效率够话。

通常鏈?zhǔn)酱鎯Y(jié)構(gòu)會有一個個結(jié)點組成，結(jié)點中包含兩個域一個是數(shù)據(jù)域光绕，一個是指針域女嘲，數(shù)據(jù)域中存儲數(shù)據(jù)，指針域中存儲下一個后繼元素的地址诞帐，如下圖所示欣尼，這一個個結(jié)點組成鏈表，也稱線性鏈表或單鏈表停蕉。
實現(xiàn)代碼如下：

/*
 * 線性表的鏈?zhǔn)酱鎯? * */
#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;


//存儲結(jié)構(gòu)
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;
}

//根據(jù)位置獲取元素
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;
}

//獲得前驅(qū)元素
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;
    }
}

通過代碼實現(xiàn)了線性結(jié)構(gòu)中線性表的順序及鏈?zhǔn)降谋硎痉绞健?/p>

順序存儲結(jié)構(gòu)中的元素在邏輯位置和物理位置上都相鄰愕鼓，鏈?zhǔn)酱鎯Y(jié)構(gòu)中的元素在邏輯位置上相鄰钙态，但在物理位置上不一定相鄰。

順序存儲結(jié)構(gòu)讀取元素的效率比較高拒啰，鏈?zhǔn)酱鎯Y(jié)構(gòu)添加和刪除元素的效率比較高驯绎。鏈?zhǔn)酱鎯Y(jié)構(gòu)除了單鏈表之外，還有循環(huán)鏈表和雙向鏈表谋旦。