線性表：包含零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列疫铜。
線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，指的是用一段連續(xù)的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素碍沐。
線性表特性：
- 是一個(gè)序列辙浑，元素直接是有順序的激涤。
- 表中元素個(gè)數(shù)叫表長，元素個(gè)數(shù)可以有多個(gè)例衍，也可以為0昔期。
- 某個(gè)元素的上一個(gè)元素叫直接前驅(qū)元素，下一個(gè)元素叫直接后繼元素佛玄。
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)
使用帶數(shù)據(jù)域和指針域的節(jié)點(diǎn)存儲(chǔ)單個(gè)元素的值硼一，并通過指針將所有元素連接起來。
優(yōu)點(diǎn)：
- 可以快速插入和刪除節(jié)點(diǎn)梦抢。
- 無需預(yù)先分配大量存儲(chǔ)空間般贼。
缺點(diǎn)：
- 查找、修改元素需要遍歷整個(gè)鏈表奥吩。
- 需要為表中的邏輯關(guān)系增加額外的存儲(chǔ)空間哼蛆。
時(shí)間復(fù)雜度
- 讀取時(shí)的時(shí)間復(fù)雜度為O(n)。
- 插入霞赫、刪除時(shí)的時(shí)間復(fù)雜度為O(1)腮介。
線性鏈表示意圖
線性鏈表插入元素示意圖
線性鏈表刪除元素示意圖
實(shí)現(xiàn)代碼如下：
// 線性表（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）
#include <stdio.h>
#include <malloc.h>
#include <time.h>
#define OK 1 // 執(zhí)行成功
#define ERROR 0 // 執(zhí)行失敗
#define TRUE 1 // 返回值為真
#define FALSE 0 // 返回值為假
typedef int Status; // 函數(shù)返回結(jié)果類型
typedef int ElemType; // 元素類型
// 鏈表節(jié)點(diǎn)
typedef struct Node {
ElemType data; // 存放鏈表元素
struct Node *next; // 指向下一個(gè)節(jié)點(diǎn)的指針
} Node;
typedef struct Node *LinkList; // 線性表鏈表結(jié)構(gòu)
/**
* 初始化線性表
* @param L 線性表
* @return 執(zhí)行狀態(tài)
*/
Status InitList(LinkList *L) {
*L = (LinkList) malloc(sizeof(Node)); // 為鏈表分配存儲(chǔ)空間
// 存儲(chǔ)空間分配失敗
if (!(*L)) {
return ERROR;
}
(*L)->next = NULL; // 讓頭節(jié)點(diǎn)指向?yàn)榭? return OK;
}
/**
* 判斷線性表是否為空
* @param L 線性表
* @return 執(zhí)行狀態(tài)
*/
Status ListEmpty(LinkList L) {
// 鏈表中含有元素，不為空
if (L->next) {
return FALSE;
} else {
return TRUE;
}
}
/**
* 清空線性表
* @param L 線性表
* @return 執(zhí)行狀態(tài)
*/
Status ClearList(LinkList *L) {
LinkList p, q; // p端衰、q用于遍歷并刪除L中的所有節(jié)點(diǎn)
p = (*L)->next; // p指向L的第一個(gè)節(jié)點(diǎn)
// 鏈表L中如果還有元素
while (p) {
q = p->next; // q指向p的下一個(gè)節(jié)點(diǎn)
free(p); // 釋放p節(jié)點(diǎn)
p = q; // 讓p指向q節(jié)點(diǎn)（即相對(duì)原來位置向后移動(dòng)一個(gè)位置）
}
(*L)->next = NULL; // 頭節(jié)點(diǎn)指針域置空
return OK;
}
/**
* 獲取線性表長度
* @param L 線性表
* @return 線性表長度
*/
int ListLength(LinkList L) {
int i = 0; // 用于統(tǒng)計(jì)元素個(gè)數(shù)
LinkList p = L->next; // p指向L的第一個(gè)節(jié)點(diǎn)
// 鏈表L中如果還有元素
while (p) {
i++; // 統(tǒng)計(jì)數(shù)加1
p = p->next; // 節(jié)點(diǎn)向后移動(dòng)
}
return i; // 返回鏈表中元素個(gè)數(shù)
}
/**
* 獲取線性表中指定位置的元素值
* @param L 線性表
* @param i 獲取元素位置下標(biāo)
* @param e 獲取元素值
* @return 執(zhí)行狀態(tài)
*/
Status GetElem(LinkList L, int i, ElemType *e) {
int j; // 計(jì)數(shù)器
LinkList p; // 用于遍歷鏈表元素
j = 1; // 初始下標(biāo)為1
p = L->next; // p指向L的第一個(gè)元素
// 當(dāng)鏈表L中如果還有元素叠洗，并且未到達(dá)i位置
while (p && j < i) {
p = p->next; // p指向下一個(gè)節(jié)點(diǎn)
j++; // 計(jì)數(shù)器加1
}
// p無下一個(gè)節(jié)點(diǎn)或計(jì)數(shù)器j超過i位置（即第i個(gè)元素不存在）
if (!p || j > i) {
return ERROR;
}
// 將i節(jié)點(diǎn)的數(shù)據(jù)賦值給e元素
*e = p->data;
return OK;
}
/**
* 定位元素e在線性表中的位置
* 找到的該元素返回元素下標(biāo)，未找到該元素返回0
* @param L 線性表
* @param e 元素
* @return 元素在線性表中的下標(biāo)
*/
int LocateElem(LinkList L, ElemType e) {
int i = 0; // 記錄元素的下標(biāo)
LinkList p = L->next; // p指向L的第一個(gè)元素
// 鏈表L中如果還有元素
while (p->next) {
i++; // 下標(biāo)加1
// p節(jié)點(diǎn)元素的值等于e
if (p->data == e) {
return i; // 返回e元素對(duì)應(yīng)的下標(biāo)
}
p = p->next; // p指向下一個(gè)元素
}
return 0;
}
/**
* 在線性表中指定位置插入新元素
* @param L 線性表
* @param i 插入位置
* @param e 插入的值
* @return 執(zhí)行狀態(tài)
*/
Status ListInsert(LinkList *L, int i, ElemType e) {
int j; // 下標(biāo)計(jì)數(shù)器
LinkList p, s; // p用來遍歷L的節(jié)點(diǎn)旅东，s用來生成新節(jié)點(diǎn)
j = 1; // 計(jì)數(shù)器起始值為1
p = *L; // p指向鏈表頭節(jié)點(diǎn)
// 鏈表L中如果還有元素灭抑，并且下標(biāo)未移動(dòng)到i位置
while (p && j < i) {
p = p->next; // p向后移動(dòng)
j++; // 下標(biāo)計(jì)數(shù)器加1
}
// p節(jié)點(diǎn)未空，或下標(biāo)計(jì)數(shù)器超出范圍（即第i個(gè)元素不存在抵代，插入失斕诮凇）
if (!p || j > i) {
return ERROR;
}
s = (LinkList) malloc(sizeof(Node)); // 生成新節(jié)點(diǎn)
s->data = e; // 給新節(jié)點(diǎn)賦值為e的值
s->next = p->next; // 新節(jié)點(diǎn)s的指針指向插入位置的下一個(gè)節(jié)點(diǎn)
p->next = s; // 插入位置的下一個(gè)節(jié)點(diǎn)指向新節(jié)點(diǎn)s
return OK;
}
/**
* 刪除線性表中指定位置的元素
* 刪除位置的值，將存到元素e中
* @param L 線性表
* @param i 刪除位置的下標(biāo)
* @param e 刪除位置的值
* @return 執(zhí)行狀態(tài)
*/
Status ListDelete(LinkList *L, int i, ElemType *e) {
int j; // 下標(biāo)計(jì)數(shù)器
LinkList p, q; // p用來遍歷L的節(jié)點(diǎn)荤牍，s用來指向?qū)h除的節(jié)點(diǎn)
j = 1; // 計(jì)數(shù)器起始值為1
p = *L; // p指向鏈表頭節(jié)點(diǎn)
// 鏈表L中如果還有元素案腺，并且下標(biāo)未移動(dòng)到i位置
while (p->next && j < i) {
p = p->next; // p向后移動(dòng)
j++; // 下標(biāo)計(jì)數(shù)器加1
}
// p節(jié)點(diǎn)未空，或下標(biāo)計(jì)數(shù)器超出范圍（即第i個(gè)元素不存在康吵，刪除失斁群）
if (!(p->next) || j > i) {
return ERROR;
}
q = p->next; // q指向被刪除節(jié)點(diǎn)
p->next = q->next; // p指向被刪除節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)
*e = q->data; // 將被刪除節(jié)點(diǎn)的值賦值給e元素
free(q); // 釋放被刪除節(jié)點(diǎn)的空間
return OK;
}
/**
* 打印單個(gè)元素
* @param e 元素值
* @return 執(zhí)行狀態(tài)
*/
Status visit(ElemType e) {
printf("%d ", e);
return OK;
}
/**
* 遍歷輸出線性表中所有元素
* @param L 線性表
* @return 執(zhí)行狀態(tài)
*/
Status ListTravel(LinkList L) {
LinkList p = L->next; // p指向L的第一個(gè)節(jié)點(diǎn)
printf("[ ");
// 鏈表L中如果還有元素
while (p) {
visit(p->data); // 打印單個(gè)元素
p = p->next; // p向后移動(dòng)
}
printf("]\n");
return OK;
}
/**
* 隨機(jī)產(chǎn)生n個(gè)元素，創(chuàng)建帶表頭結(jié)點(diǎn)的單鏈線性表（頭插法）
* @param L 線性表
* @param n 插入元素個(gè)數(shù)
*/
void CreateListHead(LinkList *L, int n) {
LinkList p; // 用來創(chuàng)建新節(jié)點(diǎn)
int i; // 用于遍歷下標(biāo)
srand(time(0)); // 設(shè)置隨機(jī)數(shù)種子
*L = (LinkList) malloc(sizeof(Node)); // 創(chuàng)建帶表頭節(jié)點(diǎn)的單鏈表
(*L)->next = NULL; // 將鏈表指針置空
// 給線性表L插入n個(gè)100以內(nèi)的隨機(jī)數(shù)
for (i = 0; i < n; i++) {
p = (LinkList) malloc(sizeof(Node)); // 生成新節(jié)點(diǎn)
p->data = rand() % 100 + 1; // 生成100以內(nèi)的隨機(jī)數(shù)涎才，賦值給新節(jié)點(diǎn)
p->next = (*L)->next; // 新元素指向頭節(jié)點(diǎn)的下一個(gè)元素
(*L)->next = p; // 頭節(jié)點(diǎn)指向新元素
}
}
/**
* 隨機(jī)產(chǎn)生n個(gè)元素，創(chuàng)建帶表頭結(jié)點(diǎn)的單鏈線性表（尾插法）
* @param L 線性表
* @param n 插入元素個(gè)數(shù)
*/
void CreateListTail(LinkList *L, int n) {
LinkList p, r; // p用來創(chuàng)建新節(jié)點(diǎn)，r用來指向L的表尾
int i; // 用于遍歷下標(biāo)
srand(time(0)); // 設(shè)置隨機(jī)數(shù)種子
*L = (LinkList) malloc(sizeof(Node)); // 創(chuàng)建帶表頭節(jié)點(diǎn)的單鏈表
r = *L; // r指向L的表尾
// 給線性表L插入n個(gè)100以內(nèi)的隨機(jī)數(shù)
for (i = 0; i < n; i++) {
p = (LinkList) malloc(sizeof(Node)); // 生成新節(jié)點(diǎn)
p->data = rand() % 100 + 1; // 生成100以內(nèi)的隨機(jī)數(shù)耍铜，賦值給新節(jié)點(diǎn)
r->next = p; // 表尾指向新節(jié)點(diǎn)
r = p; // 新節(jié)點(diǎn)成為表尾
}
r->next = NULL; // 設(shè)置表尾指向置空
}
int main() {
LinkList L; // 線性表
Status status; // 執(zhí)行狀態(tài)
ElemType e; // 線性表元素
int result; // 運(yùn)行結(jié)果
int j, k; // 用于遍歷元素的下標(biāo)
status = InitList(&L); // 初始化線性表
printf("初始化線性表L后邑闺，L的長度為：%d\n", ListLength(L));
result = ListEmpty(L); // 獲取線性表是否為空
printf("L是否為空：%s\n", result == TRUE ? "是" : "否");
/*** 給L的表頭插入5個(gè)元素 ***/
for (j = 1; j <= 5; j++) {
status = ListInsert(&L, 1, j); // 向線性表表頭插入值
}
printf("在L表頭依次插入1~5后，L中的值為：");
ListTravel(L); // 遍歷線性表
printf("插入5個(gè)元素后棕兼，L的長度為：%d\n", ListLength(L));
result = ListEmpty(L); // 獲取線性表是否為空
printf("L是否為空：%s\n", result == TRUE ? "是" : "否");
/*** 清空L中的元素 ***/
status = ClearList(&L); // 清空線性表
printf("清空線性表L后陡舅，L的長度為：%d\n", ListLength(L));
result = ListEmpty(L); // 獲取線性表是否為空
printf("L是否為空：%s\n", result == TRUE ? "是" : "否");
/*** 給L的表尾插入10個(gè)元素 ***/
for (j = 1; j <= 10; j++) {
ListInsert(&L, j, j); // 向線性表表尾插入值
}
printf("在L表尾依次插入1~10后，L中的值為：");
ListTravel(L); // 遍歷線性表
printf("插入10個(gè)元素后伴挚，L的長度為：%d\n", ListLength(L));
/*** 給L的表頭插入一個(gè)元素 ***/
ListInsert(&L, 1, 33); // 向線性表表頭插入元素33
printf("在L表頭插入元素33后靶衍，L中的值為：");
ListTravel(L); // 遍歷線性表
printf("插入元素33后，L的長度為：%d\n", ListLength(L));
/*** 獲取第5個(gè)元素的值 ***/
GetElem(L, 5, &e); // 獲取L中下標(biāo)為5的元素到e中
printf("L中第5個(gè)元素的值為：%d\n", e);
/*** 獲取下標(biāo)為3茎芋、4元素的值 ***/
for (j = 3; j <= 4; j++) {
k = LocateElem(L, j); // 獲取L中下標(biāo)為j的元素的值
if (k) {
printf("第%d個(gè)元素的值為：%d\n", k, j);
} else {
printf("沒有值為%d的元素\n", j);
}
}
/*** 刪除表中多個(gè)元素 ***/
k = ListLength(L); // k為表長
for (j = k + 1; j >= k; j--) {
status = ListDelete(&L, j, &e); // 刪除L中第j個(gè)元素颅眶，并把刪除元素的值賦值給e
if (status == ERROR) {
printf("刪除第%d個(gè)元素失敗\n", j);
} else {
printf("刪除第%d個(gè)元素的值為：%d\n", j, e);
}
}
printf("刪除表中元素后，L中的值為：");
ListTravel(L); // 遍歷線性表
/*** 刪除L中第5個(gè)元素 ***/
j = 5;
ListDelete(&L, j, &e); // 刪除L中第j個(gè)元素田弥，并把刪除元素的值賦值給e
printf("刪除第%d個(gè)元素的值為：%d\n", j, e);
printf("刪除第%d個(gè)元素后涛酗，L中的值為：",j);
ListTravel(L); // 遍歷線性表
/*** 清空L中元素,并使用頭插法插入20個(gè)元素 ***/
status = ClearList(&L); // 清空表中元素
printf("清空L中元素后，L的長度為：%d\n", ListLength(L));
CreateListHead(&L, 20); // 使用頭插法插入20個(gè)隨機(jī)元素
printf("使用頭插法插入20個(gè)隨機(jī)元素后偷厦，L中的值為：");
ListTravel(L); // 遍歷線性表
/*** 清空L中元素,并使用尾插法插入20個(gè)元素 ***/
status = ClearList(&L); // 清空表中元素
printf("清空L中元素后商叹，L的長度為：%d\n", ListLength(L));
CreateListTail(&L, 20); // 使用尾插法插入20個(gè)隨機(jī)元素
printf("使用尾插法插入20個(gè)隨機(jī)元素后，L中的值為：");
ListTravel(L); // 遍歷線性表
return 0;
}
線性鏈表運(yùn)行結(jié)果
