目錄

初識線性表

線性表的基本操作

順序表的定義

順序表的基本操作

單鏈表的定義

單鏈表的基本操作?

雙鏈表的介紹

循環(huán)鏈表的介紹

靜態(tài)鏈表的介紹

初識線性表

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

是線性表中的第 “i” 個元素線性表中的位序；是表頭元素；是表尾元素。

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

線性表的基本操作

實際開發(fā)中，可根據(jù)實際需求定義其他的基本操作，對數(shù)據(jù)的操作(記憶思路)為：創(chuàng)銷、增刪改查，函數(shù)名和參數(shù)的形式都可以改變。那么我們為什么要實現(xiàn)對數(shù)據(jù)結(jié)構(gòu)的基本操作呢？

1）團(tuán)隊合作編程，你定義的數(shù)據(jù)結(jié)構(gòu)要讓別人能夠很方便的使用(封裝)

2）將常用的操作/運算封裝成函數(shù)，避免重復(fù)工作，降低出錯風(fēng)險。

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ù)。

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

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

當(dāng)我們對參數(shù)的修改結(jié)果需要帶過來時，需要傳入引用 “&” 。給出如下代碼進(jìn)行解釋：

#include <stdio.h>
void test(int x) {
	x = 1024;
	printf("test函數(shù)內(nèi)部 x=%d\n", x);
}

int main() {
	int x = 1;
	printf("調(diào)用test前 x=%d\n", x);
	test(x);
	printf("調(diào)用test后 x=%d\n", x);
}

控制臺打印的結(jié)果如下， 其實test函數(shù)里的x是main函數(shù)里面x的復(fù)制品，兩者是兩種不同內(nèi)存地址的數(shù)據(jù)，test僅僅是改變了其內(nèi)容x的數(shù)據(jù)，并沒有改變main函數(shù)中x的數(shù)據(jù)，說白了就是main函數(shù)的x調(diào)用test函數(shù)并沒有對參數(shù)的修改結(jié)果帶回來，所有結(jié)果依然是1。

如果我們在test函數(shù)中采用引用類型，test函數(shù)對x的修改就會帶回到main函數(shù)當(dāng)中，如下：

回顧重點，其主要內(nèi)容整理成如下內(nèi)容：

順序表的定義

順序表是用順序存儲的方式實現(xiàn)線性表順序存儲。把邏輯上相鄰的元素存儲在物理位置上也相鄰的存儲單元中，元素之間的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。

順序表的靜態(tài)分配實現(xiàn)(順序表的表長剛開始確定就無法更改)

#define MaxSize 10			// 定義最大長度
typedef struct {			
	ElemType data[MaxSize]; // 用靜態(tài)的“數(shù)組”存儲數(shù)據(jù)元素
	int length;				// 順序表的當(dāng)前長度
}SqList;					// 順序表的類型定義

順序表的動態(tài)分配實現(xiàn)

#define InitSize 10			// 順序表的初識長度
typedef struct {			
	ElemType *data;		    // 指示動態(tài)分配數(shù)組的指針
	int MaxSize;			// 順序表的最大容量
	int length;				// 順序表的當(dāng)前長度
}SeqList;					// 順序表的類型定義（動態(tài)分配方式）

順序表的特點

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

2）存儲密度不高，每個節(jié)點只存儲數(shù)據(jù)元素

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

4）插入、刪除操作不方便，需要移動大量元素

回顧重點，其主要內(nèi)容整理成如下內(nèi)容：

順序表的基本操作

插入操作：ListInsert(&L,i,e)：在表L中的第i個位置上插入指定元素e。其基礎(chǔ)代碼如下：

#include <stdio.h>

#define MaxSize 10			// 定義最大長度
typedef struct {			
	int data[MaxSize]; // 用靜態(tài)的“數(shù)組”存儲數(shù)據(jù)元素
	int length;				// 順序表的當(dāng)前長度
}SqList;					// 順序表的類型定義

bool ListInsert(SqList& L, int i, int e) {
	if (i<1 || i>L.length + 1) { // 判斷i的范圍是否有效
		return false;
	}
	if (L.length >= MaxSize) { // 當(dāng)前的存儲空間已滿，不能插入
		return false;
	}
	for (int j = L.length; j >= i; j--){ // 將第i個元素及之后的元素后移
		L.data[j] = L.data[j - 1];
	}
	L.data[i - 1] = e; // 在位置i處存放e
	L.length++; // 長度+1
	return true;
}

int main() {
	SqList L; // 聲明一個順序表
	InitList(L); // 初始化順序表
	// ...此處省略代碼，插入幾個元素
	ListInsert(L, 3, 3);
	return 0;
}

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

最好情況：新元素插入到表尾，不需要移動元素

????????????????? i = n + 1，循環(huán)0次，最好的時間復(fù)雜度 = O(1)

最壞情況：新元素插入到表頭，需要將原有的n個元素全都向后移動

????????????????? i = 1，循環(huán)n次，最壞時間復(fù)雜度 = O(n)

平均情況：假設(shè)新元素插入到任何一個位置的概率相同，即i=1,2,3,..,length+1的概率都是p=。i=1，循環(huán)n次；i=2，循環(huán)n-1次；i=3，循環(huán)n-2次 ... i=n+1時，循環(huán)0次。

???????????????? 平均循環(huán)次數(shù) = np + (n-1)p+...+1·p = = ，平均時間復(fù)雜度 = O(n)

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

bool ListDelete(SqList &L, int i, int &e){
	if (i<1 || i>L.length) { // 判斷i的范圍是否有效
		return false;
	}
	e = L.data[i - 1]; // 將被刪除的元素賦值給e
	for (int j = i; j < L.length; j++){ // 將第i個元素及之后的元素前移
		L.data[j-1] = L.data[j];
	}
	L.length--; // 線性表長度減1
	return true;
}

int main() {
	SqList L; // 聲明一個順序表
	InitList(L); // 初始化順序表
	// ...此處省略代碼，插入幾個元素
	int e = -1; // 用變量e把刪除的元素“帶回來”
	if (ListDelete(L, 3, e)) {
		printf("已刪除第3個元素，刪除元素值為=%d\n", e);
	}
	else {
		printf("位序i不合法，刪除失敗\n");
	}
	return 0;
}

刪除操作的時間復(fù)雜度分析

最好情況：刪除表尾元素，不需要移動其他元素。

????????????????? i=n，循環(huán)0次；最好時間復(fù)雜度 = O(1)

最壞情況：刪除表頭元素，需要將后續(xù)的n-1個元素全都向前移動

??????????????? ? i=1，循環(huán)n-1次；最壞時間復(fù)雜度 = O(n)

平均情況：假設(shè)刪除任何一個元素的概率相同，即i=1,2,3,..,length的概率都是p=，i=1，循環(huán)n-1次；i=2時，循環(huán)n-2次；i=3時，循環(huán)n-3次...i=n時，循環(huán)0次

????????????????? 平均循環(huán)次數(shù)=(n-1)p+(n-2)p+...+1·p=，平均時間復(fù)雜度=O(n)

回顧重點，其主要內(nèi)容整理成如下內(nèi)容：

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

ElemType GetElem(SeqList L, int i) {
	return L.data[i - 1];
}

由于順序表的各個數(shù)據(jù)元素在內(nèi)存中連續(xù)存放，因此可以根據(jù)起始地址和數(shù)據(jù)元素大小立即找到第i個元素——“隨機(jī)存儲”特性，因此其時間復(fù)雜度：O(1)。

按值查找：在表L中查找具有給定關(guān)鍵字值的元素。

int LocateElem(SeqList L, ElemType e) {
	for (int i = 0; i < L.length; i++) {
		if (L.data[i] == e) {
			return i + 1;// 數(shù)組下標(biāo)為i的元素值等于e，返回其位序i+1
		}
	}
	return 0; // 退出循環(huán)，說明查找失敗
}

按值查找操作的時間復(fù)雜度分析

最好情況：目標(biāo)元素在表頭

????????????????? 循環(huán)1次：最好時間復(fù)雜度=O(1)

最壞情況：目標(biāo)元素在表尾

????????????????? 循環(huán)n次：最壞時間復(fù)雜度=O(n)

平均情況：假設(shè)目標(biāo)元素出現(xiàn)在任何一個位置的概率相同，都是，目標(biāo)元素在第1位，循環(huán)1次；在第2位，循環(huán)2次，...；在第n位，循環(huán)n次。

????????????????? 平均循環(huán)次數(shù)=1·+2·+3·+....+n· = = ，平均時間復(fù)雜度=O(n)

回顧重點，其主要內(nèi)容整理成如下內(nèi)容：

單鏈表的定義

單鏈表每個節(jié)點除了存放數(shù)據(jù)元素之外，還要存儲指向下一個節(jié)點的指針。其不要求大片連續(xù)空間，改變?nèi)萘糠奖?，但是不可隨機(jī)存取，要耗費一定空間存放指針。

要聲明一個單鏈表時，只需聲明一個頭指針L，指向單鏈表的第一個結(jié)點。

typedef struct LNode { // 定義單鏈表結(jié)點類型
	ElemType data; // 每個節(jié)點存放一個數(shù)據(jù)元素
	struct LNode* next; // 指針指向下一個節(jié)點
}LNode, *LinkList;

不帶頭節(jié)點的單鏈表

// 初始化一個空的單鏈表
bool InitList(LinkList& L) {
	L = NULL; // 空表，暫時沒有任何節(jié)點
	return true;
}

帶頭節(jié)點的單鏈表

// 初始化一個單鏈表（帶頭節(jié)點）
bool InitList(LinkList& L) {
	L = （Lode * ）malloc(sizeof(LNode)); // 分配一個頭節(jié)點
	if (L == NULL) // 內(nèi)存不足，分配失敗
		return false;
	L->next = NULL; // 頭節(jié)點之后暫時還沒有節(jié)點
	return true;
}

回顧重點，其主要內(nèi)容整理成如下內(nèi)容：?

單鏈表的基本操作?

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

按位序插入（帶頭節(jié)點）

按位序插入（不帶頭節(jié)點）

后插操作

前插操作

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

按位序刪除（帶頭節(jié)點）

按位查找：獲取表L中第i個位置的元素的值。

按值查找：在表L中查找具有給定關(guān)鍵字值的元素。

回顧重點，其主要內(nèi)容整理成如下內(nèi)容：?

尾插法建立單鏈表

頭插法建立單鏈表

頭插法、尾插法：核心就是初始化操作、指定結(jié)點的后插操作。頭插法的重要應(yīng)用：鏈表的逆置。

雙鏈表的介紹

雙向鏈表（Doubly Linked List），也稱雙鏈表，是一種常見的線性數(shù)據(jù)結(jié)構(gòu)，與單向鏈表類似，但每個節(jié)點有兩個指針，一個指向前一個節(jié)點，一個指向后一個節(jié)點，因此可以雙向遍歷。

每個節(jié)點包含三個部分：數(shù)據(jù)域、指向前一個節(jié)點的指針域 prev 和指向后一個節(jié)點的指針域 next。第一個節(jié)點的 prev 指針一般為空，最后一個節(jié)點的 next 指針一般為空。

相比單向鏈表，雙向鏈表在插入、刪除等操作時更為靈活，同時可以雙向遍歷，方便查找前一個及后一個節(jié)點，因此在某些場景下使用雙向鏈表更為方便快捷。但是，雙向鏈表相對于單向鏈表需要額外的空間來存儲指向前一個節(jié)點的指針，因此會占用更多的內(nèi)存空間。

雙鏈表的初始化（帶頭結(jié)點）

雙鏈表的插入

雙鏈表的刪除

雙鏈表的遍歷（雙鏈表不可隨機(jī)存取，按位查找、按值查找操作都只能用遍歷方式實現(xiàn)）。

回顧重點，其主要內(nèi)容整理成如下內(nèi)容：

循環(huán)鏈表的介紹

循環(huán)鏈表（Circular Linked List）是一種特殊的鏈表結(jié)構(gòu)，它的最后一個節(jié)點指向頭節(jié)點，從而形成一個環(huán)形結(jié)構(gòu)。循環(huán)鏈表可以是單向的或雙向的。

循環(huán)單鏈表：循環(huán)單鏈表是一種只有一個指針域的單向鏈表，其最后一個節(jié)點的指針指向頭節(jié)點，實現(xiàn)了鏈表的循環(huán)。下面是一個用C語言實現(xiàn)循環(huán)單鏈表的基本代碼：

// 單向循環(huán)鏈表結(jié)點定義
typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// 創(chuàng)建循環(huán)單鏈表
ListNode* createCircularLinkedList(int data[], int n) {
    ListNode *head = (ListNode*)malloc(sizeof(ListNode));
    head->val = 0;  // 頭結(jié)點不存儲數(shù)據(jù)
    head->next = NULL;
    ListNode *tail = head;
    for (int i = 0; i < n; ++i) {
        ListNode *node = (ListNode*)malloc(sizeof(ListNode));
        node->val = data[i];
        node->next = NULL;
        tail->next = node;
        tail = node;
    }
    tail->next = head;  // 最后一個節(jié)點指向頭節(jié)點，形成循環(huán)
    return head;
}

// 遍歷循環(huán)單鏈表
void traverseCircularLinkedList(ListNode *head) {
    ListNode *p = head->next;
    while (p != head) {
        printf("%d ", p->val);
        p = p->next;
    }
}

// 刪除循環(huán)單鏈表
void deleteCircularLinkedList(ListNode *head) {
    ListNode *p = head->next;
    while (p != head) {
        ListNode *temp = p;
        p = p->next;
        free(temp);
    }
    free(head);
}

循環(huán)雙鏈表：循環(huán)雙鏈表是一種具有兩個指針域的鏈表，除了每個節(jié)點都有一個指向下一個節(jié)點的指針 next 外，還有一個指向前一個節(jié)點的指針 prev。它的最后一個節(jié)點的 next 指針指向頭節(jié)點，頭節(jié)點的 prev 指針指向最后一個節(jié)點，這樣就形成了一個環(huán)形結(jié)構(gòu)。下面是一個用C++實現(xiàn)循環(huán)雙鏈表的基本代碼：

// 雙向循環(huán)鏈表結(jié)點定義
struct ListNode {
    int val;
    ListNode *prev, *next;
    ListNode(int x) : val(x), prev(NULL), next(NULL) {}
};

// 創(chuàng)建循環(huán)雙向鏈表
ListNode* createCircularDoublyLinkedList(vector<int>& nums) {
    int n = nums.size();
    ListNode *head = new ListNode(0);  // 頭結(jié)點不存儲數(shù)據(jù)
    ListNode *tail = head;
    for (int i = 0; i < n; ++i) {
        ListNode *node = new ListNode(nums[i]);
        node->prev = tail;
        node->next = head;
        tail->next = node;
        head->prev = node;
        tail = node;
    }
    return head;
}

// 遍歷循環(huán)雙向鏈表
void traverseCircularDoublyLinkedList(ListNode *head) {
    ListNode *p = head->next;
    while (p != head) {
        cout << p->val << " ";
        p = p->next;
    }
}

// 刪除循環(huán)雙向鏈表
void deleteCircularDoublyLinkedList(ListNode *head) {
    ListNode *p = head->next;
    while (p != head) {
        ListNode *temp = p;
        p = p->next;
        delete temp;
    }
    delete head;
}

靜態(tài)鏈表的介紹

靜態(tài)鏈表（Static Linked List）是一種利用數(shù)組來模擬鏈表的數(shù)據(jù)結(jié)構(gòu)，其本質(zhì)上并不是真正的鏈表，而是通過數(shù)組和指針來實現(xiàn)鏈表的功能。在靜態(tài)鏈表中，用數(shù)組來存儲節(jié)點的數(shù)據(jù)元素，同時用另外一個數(shù)組來存儲鏈表節(jié)點的指針。下面是一個用C++實現(xiàn)靜態(tài)鏈表的基本代碼：

const int N = 100000;

struct ListNode {
    int val, next;
} nodes[N];

// 根據(jù)數(shù)組創(chuàng)建靜態(tài)鏈表
int createStaticLinkedList(int data[], int n) {
    for (int i = 0; i < n; ++i) {
        nodes[i].val = data[i];
        nodes[i].next = i + 1;
    }
    nodes[n - 1].next = -1;
    return 0;  // 返回頭指針位置
}

// 向靜態(tài)鏈表插入元素
// pos為需要插入的位置，val為要插入的元素值
void insertStaticLinkedList(int pos, int val) {
    int p = 0;  // p初始化為頭指針
    while (pos--) p = nodes[p].next;  // 在pos-1的位置停留
    int q = 0;  // q初始化為空閑節(jié)點的位置
    while (nodes[q].next != -1) q = nodes[q].next;  // 找到最后一個空閑節(jié)點
    nodes[q].val = val;
    nodes[q].next = nodes[p].next;
    nodes[p].next = q;  // 將q插入在p之后
}

// 從靜態(tài)鏈表刪除元素
// pos為需要刪除的位置
void deleteStaticLinkedList(int pos) {
    int p = 0;  // p初始化為頭指針
    while (pos--) p = nodes[p].next;  // 在pos-1的位置停留
    int q = nodes[p].next;
    nodes[p].next = nodes[q].next;  // 將q從鏈表中刪除
    nodes[q].next = -1;  // 將q加入到空閑節(jié)點鏈表中
}

靜態(tài)鏈表優(yōu)缺點：

增刪操作不需要大量移動元素。不能隨機(jī)存取，只能從頭結(jié)點開始依次往后查找，容量固定不變。

在實際應(yīng)用中，使用靜態(tài)鏈表需要注意以下問題：

靜態(tài)鏈表中的空閑節(jié)點需要預(yù)先分配好，不能像動態(tài)鏈表那樣動態(tài)申請內(nèi)存，否則會破壞靜態(tài)鏈表的結(jié)構(gòu)。

靜態(tài)鏈表的節(jié)點數(shù)量是有限的，因為數(shù)組的大小是固定的，因此應(yīng)該根據(jù)實際情況來設(shè)置數(shù)組的大小。

順序表和鏈表的優(yōu)缺點：

順序表

優(yōu)點：存儲密度高，因為在內(nèi)存中是一段連續(xù)的空間存儲數(shù)據(jù)，訪問元素的時間復(fù)雜度為O(1)，因此查找、修改等操作效率較高。支持下標(biāo)訪問元素，編程簡單直觀。

缺點：插入、刪除元素時需要移動其他元素，時間復(fù)雜度為O(n)，因此插入、刪除操作效率相對較低。內(nèi)存空間的分配和釋放需要考慮到數(shù)組大小，因此當(dāng)需要頻繁的插入、刪除操作時可能會浪費內(nèi)存空間。

鏈表

優(yōu)點：插入、刪除元素時只需要修改指針指向，不需要移動其他元素，時間復(fù)雜度為O(1)，因此插入、刪除操作效率較高。內(nèi)存空間的分配和釋放更加靈活，可以根據(jù)實際需要動態(tài)分配。

缺點：存儲密度較低，因為每個節(jié)點需要額外存儲指針信息，占用內(nèi)存空間較大。訪問元素需要遍歷整個鏈表，時間復(fù)雜度為O(n)，因此查找、修改等操作效率相對較低。不支持下標(biāo)訪問元素，需要通過指針進(jìn)行訪問。

實現(xiàn)線性表時，使用順序表還是鏈表好？

當(dāng)我們需要高效地進(jìn)行查找、修改操作時，可以使用順序表；當(dāng)我們需要高效地進(jìn)行插入、刪除操作時，可以使用鏈表。如果需要頻繁地進(jìn)行插入、刪除操作，并且元素數(shù)量不確定或者需要動態(tài)改變，則應(yīng)該優(yōu)先考慮使用鏈表。但是，順序表的實現(xiàn)和使用比鏈表更為簡單，因此當(dāng)元素數(shù)量相對固定或者需要使用下標(biāo)操作時，可以優(yōu)先考慮使用順序表。文章來源地址http://www.zghlxwxcb.cn/news/detail-494294.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)--》從線性表說起，掌握常用基礎(chǔ)算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！