線性表的定義和基本操作

一、線性表的定義

線性表（Linear List）是具有相同數(shù)據(jù)類型的n(n>=0)個數(shù)據(jù)元素的有限序列，其中n為表長，當n=0時線性表是一個空表。若用L命名線性表，則其一般表示為

L = (a1,a2,...,ai,ai+1,...,an)

ai是線性表中的“第i個”元素線性表中的位序

a1是表頭元素；an是表尾元素。

除第一個元素外，每個元素有且僅有一個直接前驅(qū)；出最后一個元素外，每個元素有且僅有一個直接后繼；

二、線性表的基本操作

InitList(&L)：初始化表。構(gòu)造一個空的線性表L，分配內(nèi)存空間。

DestroyList(&L)：銷毀操作。銷毀線性表，并釋放線性表L所占有的內(nèi)存空間。

ListInsert(&L,i,e)：插入操作。在表L中的第i個位序（位置）上插入制定元素e。

ListDelete(&L,i,&e)：刪除操作。刪除表L中第i個位序（位置）的元素，并用e返回刪除元素的值。

LocateElem(L,e)：按值查找操作。在表L中查找具體給定關(guān)鍵字值的元素。

GetElem(L,i)：按位查找操作。獲取表L中第i個位置的元素的值。

其他常用操作：

Length(L)：求表長操作。返回線性表L的長度，即L中數(shù)據(jù)元素的個數(shù)。

PrinList(L)：輸出操作。按前后順序輸出線性表L的所有元素值。

Empty(L)：判空操作。若L為空表，則返回true，否則返回false。

Tips：

①對數(shù)據(jù)的操作（記憶思路）——創(chuàng)（Init）銷（Destroy）、增（Insert）刪（Delete）改（Alter）查（Query）

②C語言函數(shù)的定義

③實際開發(fā)中，可根據(jù)實際需求定義其他的基本操作

④函數(shù)名和參數(shù)的形式、命令都可改變

⑤什么時候需要傳入“&”——對參數(shù)的修改結(jié)果需要“帶回來”

三、初始化代碼實踐

1、順序表靜態(tài)分配

#include <stdio.h>
// 順序表存儲空間靜態(tài)分配
#define MaxSize 10      // 定義最大長度
typedef int ElemType;   // int類型重命名為ElemType，方便后續(xù)調(diào)整
typedef struct{         // 定義結(jié)構(gòu)體
    ElemType data[MaxSize];         // 用靜態(tài)的數(shù)組存放數(shù)據(jù)元素
    ElemType length;                // 數(shù)組長度
}SqList;
void InitList(SqList &L){           // 初始化順序表
    L.length=0;                     // 長度賦值,沒有設(shè)置數(shù)據(jù)元素的默認值
}
int main() {
    SqList L;           // 聲明一個順序表
    InitList(L);    // 初始化順序表
    for (int i = 0; i < MaxSize; i++) {
        // 嘗試違規(guī)打印整個data數(shù)組
        printf("data[%d]=%d\n", i, L.data[i]);
    }
    return 0;
}

#include <stdio.h>
// 順序表存儲空間靜態(tài)分配
#define MaxSize 10      // 定義最大長度
typedef int ElemType;   // int類型重命名為ElemType，方便后續(xù)調(diào)整
typedef struct{         // 定義結(jié)構(gòu)體
    ElemType data[MaxSize];         // 用靜態(tài)的數(shù)組存放數(shù)據(jù)元素
    ElemType length;                // 數(shù)組長度
}SqList;
void InitList(SqList &L){          // 初始化順序表
    for(int i=0;i<MaxSize;i++){    // 設(shè)置數(shù)據(jù)元素的默認值，否則內(nèi)存中會有遺留的“臟數(shù)據(jù)”
        L.data[i]=0;
    }
    L.length=0;                     // 長度賦值,沒有設(shè)置數(shù)據(jù)元素的默認值
}
int main() {
    SqList L;           // 聲明一個順序表
    InitList(L);    // 初始化順序表
    for (int i = 0; i < L.length; i++) {    //按照數(shù)據(jù)長度進行打印
        // 嘗試違規(guī)打印整個data數(shù)組
        printf("data[%d]=%d\n", i, L.data[i]);
    }
    return 0;
}

2、順序表動態(tài)分配

#include <stdio.h>
#include <stdlib.h>
// 順序表存儲空間動態(tài)分配
#define InitSize 10      // 順序表初始長度
typedef int ElemType;   // int類型重命名為ElemType，方便后續(xù)調(diào)整
typedef struct{         // 定義結(jié)構(gòu)體
    ElemType *data;     // 用靜態(tài)的數(shù)組存放數(shù)據(jù)元素
    ElemType MaxSize;   // 順序表最大容量
    ElemType length;    // 順序表數(shù)據(jù)長度
}SqList;
void InitList(SqList &L){           // 初始化順序表
    // 用malloc函數(shù)申請一片連續(xù)的存儲空間
    L.data = (ElemType *) malloc(InitSize * sizeof(ElemType));
    L.MaxSize = InitSize;
    L.length = 0;
}
void IncreaseSize(SqList &L, ElemType len){
    ElemType *p=L.data;
    L.data = (int *) malloc((L.MaxSize + len) * sizeof(ElemType));
    for (ElemType i = 0; i < L.length; i++) {
        L.data[i]=p[i];     // 將數(shù)據(jù)復(fù)制到新區(qū)域
    }
    L.MaxSize=L.MaxSize+len;    // 順序表最大長度增加len
    free(p);            // 釋放原來的內(nèi)存空間
}
int main() {
    SqList L;           // 聲明一個順序表
    InitList(L);    // 初始化順序表
    IncreaseSize(L, 5);
    return 0;
}

3、特點

隨機訪問：即可以在O(1)時間內(nèi)找到第i個元素。

存儲密度高：每個節(jié)點只存儲數(shù)據(jù)元素。

擴展容量不方便：即便采取動態(tài)分配的方式實現(xiàn)，拓展長度的時間復(fù)雜度也比較高。

插入、刪除操作不方便：需要移動大量的元素。

四、插入和刪除

1、順序表插入實踐

#include <stdio.h>

#define MaxSize 10      // 指定大小
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];
    ElemType length;
}SqList;

bool InsertList(SqList &L, ElemType position, ElemType element){
    if (position < 1 || position > L.length + 1) {      // 判斷插入是否合理
        return false;
    }
    if (L.length >= MaxSize) {          // 判斷插入是否合理
        return false;
    }
    for (ElemType i = L.length; i >= position; i--) {   // 循環(huán)從最后一位開始，到插入的位序，減減
        L.data[i] = L.data[i-1];        // 將前一位值向后移一位
    }
    L.data[position-1] = element;       // 插入的位置附上要插入的值，注意數(shù)組下標和位序是相差一位的
    L.length++;                         // 插入一個元素之后，數(shù)組的長度是要加1
    return true;
}

void PrintList(SqList L){
    for (ElemType i = 0; i < L.length; i++) {
        printf("data[%d]=%d\n",i,L.data[i]);
    }
}
int main() {
    SqList L;   // 初始化
    for (ElemType i = 0; i < 6; i++) {      // 數(shù)組賦值
        L.data[i]=i*2;
    }
    L.length=6;
    bool ret;
    ret = InsertList(L, 6, 20); // 調(diào)用插入
    if (ret) {          // 判斷是否正常插入
        printf("insert element success\n");
        PrintList(L);
    } else {
        printf("insert element failed\n");
    }
    return 0;
}

插入操作的時間復(fù)雜度

最好情況：新元素插入到表尾，按照以上例子為插入位序為6的位置，不需要移動元素，循環(huán)0次，最好時間復(fù)雜度=O(1)

最壞情況：新元素插入到表頭，需要將原有的n個元素全部都向后移動，循環(huán)n次，最壞時間復(fù)雜度=O(n)

平均情況：假設(shè)新元素插入到任何一個位置的概率相同，即i=1,2,3,…,length+1的概率都是
$$p=\frac{1}{n+1}$$
i=1,循環(huán)n次，i=2，循環(huán)n-1，…，i=n+1，循環(huán)0次
$$平均循環(huán)次數(shù)=np+(n?1)p?(n?2)p+...+1.p=\frac{n(n+1)}{2}?\frac{1}{n+1}=\frac{n}{2}$$
平均時間復(fù)雜度=O(n)

2、順序表刪除實踐

#include <stdio.h>

#define MaxSize 10      // 指定大小
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];
    ElemType length;
}SqList;

bool DeleteList(SqList &L, ElemType position, ElemType &element){
    if (position < 1 || position > L.length + 1) {      // 判斷刪除是否合理
        return false;
    }
    element = L.data[position-1];       // 刪除的數(shù)據(jù)，注意數(shù)組的下標和位序的關(guān)系
    for (ElemType i = position; i <L.length; i++) {   // 循環(huán)從要刪除的位序開始，結(jié)束條件為到數(shù)組長度減一位的位置
        L.data[i-1] = L.data[i];        // 將刪除位序的值向前移動
    }
    L.length--;                         // 刪除一個元素之后，數(shù)組的長度是要減1
    return true;
}

void PrintList(SqList L){
    for (ElemType i = 0; i < L.length; i++) {
        printf("data[%d]=%d\n",i,L.data[i]);
    }
}
int main() {
    SqList L;   // 初始化
    for (ElemType i = 0; i < 6; i++) {      // 數(shù)組賦值
        L.data[i]=i*2;
    }
    L.length=6;
    ElemType num;
    bool ret;
    ret = DeleteList(L, 2, num); // 調(diào)用插入
    if (ret) {          // 判斷是否正常插入
        printf("delete element success!delete element is %d\n",num);
        PrintList(L);
    } else {
        printf("insert element failed\n");
    }
    return 0;
}

最好情況：刪除表尾元素，不需要移動元素，循環(huán)0次，最好時間復(fù)雜度=O(1)

最壞情況：刪除表頭元素，需要將后續(xù)n-1個元素全部向前移動，循環(huán)n-1次，最壞時間復(fù)雜度=O(n)

平均情況：假設(shè)刪除任何一個元素的概率相同，即i=1,2,3,…,length+1的概率都是
$$p=\frac{1}{n}$$
i=1,循環(huán)n-1次，i=2，循環(huán)n-2，…，i=n，循環(huán)0次
$$平均循環(huán)次數(shù)=(n?1)p?(n?2)p+...+1.p=\frac{n(n?1)}{2}?\frac{1}{n}=\frac{n?1}{2}$$
平均時間復(fù)雜度=O(n)

3、順序表查詢實踐

#include <stdio.h>

// 靜態(tài)分配
#define MaxSize 10		// 定義最大長度

typedef int Element;

typedef struct{
    Element data[MaxSize];		// 用靜態(tài)的“數(shù)組”存放數(shù)據(jù)元素
    int length;
}SqList;
	
int GetList(SqList L,int position){		// 查詢該位序的值
    return L.data[position - 1];		// 位序和數(shù)組下標少一位
}

int LocateList(SqList L,int num){		// 查詢值在數(shù)據(jù)哪個位序
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == num) {
            return i+1;					// 返回位序和數(shù)組下標相差一位
        }
    }
}
int main() {
    SqList L;
    for (int i = 0; i < 5; i++) {
        L.data[i] = i*2;
    }
    L.length=5;
    int ret;
    ret = GetList(L, 3);
    printf("Get List num is %d\n", ret);

    ret = LocateList(L,4);
    printf("Locate List position is %d\n", ret);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
// 動態(tài)分配
#define InitSize 10

typedef int Element;

typedef struct{
    Element *data;
    int MaxSize;
    int length;
}SqList;

void InitList(SqList &L){               // 初始化
    L.data = (int *) malloc(InitSize*sizeof(int));
    L.MaxSize = InitSize;
    L.length = 0;
}

int GetList(SqList L,int position){		// 查詢該位序的值
    return L.data[position - 1];		// 位序和數(shù)組下標少一位
}

int LocateList(SqList L,int num){		// 查詢值在數(shù)據(jù)哪個位序
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == num) {
            return i+1;					// 返回位序和數(shù)組下標相差一位
        }
    }
}
int main() {
    SqList L;
    InitList(L);
    for (int i = 0; i < 5; i++) {
        L.data[i] = i*2;
    }
    L.length=5;
    int ret;
    ret = GetList(L, 3);
    printf("Get List num is %d\n", ret);

    ret = LocateList(L,4);
    printf("Locate List position is %d\n", ret);
    return 0;
}

時間復(fù)雜度：

按位查找：O(1)

按值查找：最好時間復(fù)雜度：O(1)，在第一個位置

? 最壞時間復(fù)雜度：O(n)，在最后一個位置

? 平均時間復(fù)雜度：O(n)，目標元素在每個位置的概率相同
$$O=(1+2+...+n)\frac{1}{n}=\frac{n(n+1)}{2}?\frac{1}{n}=\frac{n+1}{2}=O(n)$$文章來源地址http://www.zghlxwxcb.cn/news/detail-735069.html

到了這里，關(guān)于線性表的定義和基本操作的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！