- 作者原創(chuàng)蠢熄，轉(zhuǎn)載請(qǐng)注明出處。
個(gè)人博客：renzhe.name
用 C 語(yǔ)言實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表悔常，即單鏈表。本文實(shí)現(xiàn)了動(dòng)態(tài)單鏈表给赞，關(guān)于靜態(tài)單鏈表這里不再細(xì)說(shuō)了。
關(guān)于抽象數(shù)據(jù)類型的定義這里就不再粘貼處了矫户，可以參照上一篇的定義片迅。
下面直接看具體 C 語(yǔ)言實(shí)現(xiàn)代碼，包括簡(jiǎn)單的測(cè)試程序皆辽。
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define INFEASIBLE 0
typedef int Status;
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode *next;
}LNode, *LinkList;
/**
* 操作結(jié)果：構(gòu)造一個(gè)空的線性表L
* @param L
*/
void InitList(LinkList *L) {
*L = (LinkList)malloc(sizeof(struct LNode));
if (!*L) {
exit(OVERFLOW);
}
(*L)->next = NULL;
}
/**
* 初始條件：線性表 L存在
* 操作結(jié)果：銷毀線性表 L
* @param L
*/
void DestroyList(LinkList *L) {
LinkList q;
while (*L) {
q = (*L)->next;
free(*L);
*L = q;
}
}
/**
* 初始條件：線性表 L 存在
* 操作結(jié)果：將 L 置為空表
* @param L
*/
void ClearList(LinkList L) {
LinkList p, q;
p = L->next;
while (p) {
q = p->next;
free(p);
p = q;
}
L->next = NULL;
}
/**
* 初始條件：線性表 L 存在
* 操作結(jié)果：若 L 為空表柑蛇，返回 TRUE，否則返回 FALSE
* @param L
* @return
*/
Status ListEmpty(LinkList L) {
return L->next == NULL;
}
/**
* 初始條件：線性表 L 存在
* 操作結(jié)果：返回 L 中的數(shù)據(jù)元素個(gè)數(shù)
* @param L
* @return
*/
int ListLength(LinkList L) {
int i = 0;
LinkList p = L->next;
while (p) {
i++;
p = p->next;
}
return i;
}
/**
* 初始條件：線性表 L 存在驱闷，且 1 <= i <= ListLength(L)
* 操作結(jié)果：用 e 返回 L 中第 i 個(gè)元素的值
* @param L
* @param i
* @param e
* @return
*/
Status GetElem(LinkList L, int i, ElemType *e) {
LinkList p = L->next;
int j = 1;
while (p && j < i) {
p = p->next;
++j;
}
if (!p || j > i) {
return ERROR;
}
*e = p->data;
return OK;
}
/**
* 初始條件：線性表 L 存在
* 操作結(jié)果：返回 L 中第一個(gè)值與元素 e 相同的元素在 L 中的位置耻台。若元素不存在，則返回 0
* @param L
* @param e
* @param compare
* @return
*/
int LocateElem(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 0;
}
Status compare(ElemType e1, ElemType e2) {
if (e1 == e2) {
return 1;
} else {
return 0;
}
}
/**
* 初始條件：線性表 L 存在
* 操作結(jié)果：若 cur_e 是 L 中的元素空另，且不是第一個(gè)盆耽，則用 pre_e 返回其前驅(qū)，否則失敗，pre_e 無(wú)定義
* @param L
* @param cur_e
* @param pre_e
* @return
*/
Status PriorElem(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 INFEASIBLE;
}
/**
* 初始條件：線性表 L 存在
* 操作結(jié)果：若 cur_e 是 L 中的元素摄杂，且不是最后一個(gè)坝咐，則用 next_e 返回其后驅(qū)，否則失敗析恢，next_e 無(wú)定義
* @param L
* @param cur_e
* @param pre_e
* @return
*/
Status NextElem(LinkList L, ElemType cur_e, ElemType *next_e) {
LinkList q, p = L->next;
while (p->next) {
if (p->data == cur_e) {
*next_e = p->next->data;
return OK;
}
p = p->next;
}
return INFEASIBLE;
}
/**
* 初始條件：線性表 L 存在墨坚，且 1 <= i <= ListLength(L) + 1
* 操作結(jié)果：在 L 中第 i 個(gè)元素前插入新的元素 e，L 的長(zhǎng)度加 1
* @param L
* @param i
* @param e
* @return
*/
Status ListInsert(LinkList L, int i, ElemType e) {
int j = 0;
LinkList p = L, s;
while (p && j < i - 1) {
p = p->next;
++j;
}
if (!p || j > i - 1) {
return ERROR;
}
s = (LinkList)malloc(sizeof(struct LNode));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
/**
* 初始條件：線性表 L 存在且非空映挂，且 1 <= i <= ListLength(L)
* 操作結(jié)果：刪除 L 中的第 i 個(gè)元素并用 e 返回其值泽篮，L 的長(zhǎng)度減 1
* @param S
* @param i
* @param e
* @return
*/
Status ListDelete(LinkList L, int i, ElemType *e) {
int j = 0;
LinkList q, p = L;
while (p->next && j < i - 1) {
p = p->next;
++j;
}
if (!p || j > i - 1) {
return ERROR;
}
*e = p->next->data;
q = p->next;
p->next = q->next;
free(q);
return OK;
}
/**
* 初始條件：線性表 L 存在
* 操作結(jié)果：對(duì)線性表進(jìn)行遍歷，在遍歷過(guò)程中對(duì)每個(gè)結(jié)點(diǎn)訪問一次柑船，遍歷過(guò)程中調(diào)用 vi() 操作元素
* @param L
* @param vi
*/
void TraverseList(LinkList L, void(*vi)(ElemType)) {
LinkList p = L->next;
while (p) {
vi(p->data);
p = p->next;
}
printf("\n");
}
void vi(ElemType e) {
printf("%d ", e);
}
/**
* 操縱結(jié)果：前插法創(chuàng)建含 n 個(gè)元素的單鏈表
* @param L
* @param n
*/
void CreateList_H(LinkList *L, int n) {
InitList(L);
LinkList p;
for (int i = 0; i < n; ++i) {
p = (LinkList)malloc(sizeof(struct LNode));
scanf("%d",&p->data);
p->next = (*L)->next;
(*L)->next = p;
}
}
/**
* 操縱結(jié)果：后插法創(chuàng)建含 n 個(gè)元素的單鏈表
* @param L
* @param n
*/
void CreateList_R(LinkList *L, int n) {
InitList(L);
LinkList p, r = *L;
for (int i = 0; i < n; ++i) {
p = (LinkList)malloc(sizeof(struct LNode));
scanf("%d", &p->data);
p->next = NULL;
r->next = p;
r = p;
}
}
/*--------------------主函數(shù)------------------------*/
/**
* 測(cè)試程序
* @return
*/
int main() { // 測(cè)試程序只測(cè)試函數(shù)是否有邏輯錯(cuò)誤
LinkList list;
int temp;
ElemType *e;
// CreateList_H(&list, 3);
CreateList_R(&list, 3);
printf("%d\n", ListEmpty(list));
printf("%d\n", ListLength(list));
TraverseList(list, vi);
temp = ListInsert(list, 1, 99);
TraverseList(list, vi);
temp = ListInsert(list, 5, 100);
TraverseList(list, vi);
temp = GetElem(list, 3, e);
printf("%d\n", *e);
temp = PriorElem(list, 4, e);
printf("%d\n", *e);
temp = NextElem(list, 6, e);
printf("%d\n", *e);
printf("%d\n", LocateElem(list, 6, compare));
temp = ListDelete(list, 4, e);
TraverseList(list, vi);
ClearList(list);
printf("%d\n", ListLength(list));
DestroyList(&list);
}
上面測(cè)試代碼在 Clion 下的執(zhí)行結(jié)果如下圖所示咪辱。
想要查看源碼可以訪問下面 github 鏈接，如果覺得不錯(cuò)椎组，請(qǐng)給個(gè) Star油狂。
本文屬數(shù)據(jù)結(jié)構(gòu)系列持續(xù)更新中。
