- 作者原創(chuàng)，轉(zhuǎn)載請注明出處。
個(gè)人博客：renzhe.name
用 C 語言實(shí)現(xiàn)順序存儲結(jié)構(gòu)的線性表，即順序表。
下面是線性表的抽象數(shù)據(jù)類型定義：
ADT List {
數(shù)據(jù)對象：D = { ai | ai∈ElemSet, i=1,2,...,n, n≧0 }
數(shù)據(jù)關(guān)系：R = {<ai-1, ai> | ai-1, ai∈D, i=2,3,...,n }
基本操作：
InitList(&L);
操作結(jié)果：構(gòu)造一個(gè)空的線性表L
DestroyList(&L);
初始條件：線性表 L存在
操作結(jié)果：銷毀線性表 L
ClearList(&L);
初始條件：線性表 L 存在
操作結(jié)果：將 L 置為空表
ListEmpty(L);
初始條件：線性表 L 存在
操作結(jié)果：若 L 為空表，返回 TRUE，否則返回 FALSE
ListLength(L);
初始條件：線性表 L 存在
操作結(jié)果：返回 L 中的數(shù)據(jù)元素個(gè)數(shù)
GetElem(L, i, &e);
初始條件：線性表 L 存在，且 1 <= i <= ListLength(L)
操作結(jié)果：用 e 返回 L 中第 i 個(gè)元素的值
LocateElem(L, e);
初始條件：線性表 L 存在
操作結(jié)果：返回 L 中第一個(gè)值與元素 e 相同的元素在 L 中的位置。若元素不存在，則返回 0
PriorElem(L, cur_e, &pre_e);
初始條件：線性表 L 存在
操作結(jié)果：若 cur_e 是 L 中的元素，且不是第一個(gè)，則用 pre_e 返回其前驅(qū)，否則失敗，pre_e 無定義
NextElem(L, cur_e, &next_e);
初始條件：線性表 L 存在
操作結(jié)果：若 cur_e 是 L 中的元素，且不是最后一個(gè)，則用 next_e 返回其后驅(qū)，否則失敗，next_e 無定義
ListInsert(&L, i, e);
初始條件：線性表 L 存在，且 1 <= i <= ListLength(L) + 1
操作結(jié)果：在 L 中第 i 個(gè)元素前插入新的元素 e，L 的長度加 1
ListDelete(&L, i, &e);
初始條件：線性表 L 存在且非空，且 1 <= i <= ListLength(L)
操作結(jié)果：刪除 L 中的第 i 個(gè)元素并用 e 返回其值，L 的長度減 1
TraverseList(L);
初始條件：線性表 L 存在
操作結(jié)果：對線性表進(jìn)行遍歷，在遍歷過程中對每個(gè)結(jié)點(diǎn)訪問一次，遍歷過程中調(diào)用 vi() 操作元素
}
具體代碼如下：
#include <stdio.h>
#include <malloc.h>
#define LIST_INIT_SIZE 10
#define LIST_INCREMENT 2
#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 {
ElemType *elem;
int length;
int listSize;
}SqList;
/**
* 操作結(jié)果：構(gòu)造一個(gè)空的順序表 L
* @param L
*/
void InitList(SqList *L) {
L->elem = malloc(LIST_INIT_SIZE * sizeof(SqList));
if (!L->elem) {
exit(OVERFLOW);
}
L->length = 0;
L->listSize = LIST_INIT_SIZE;
}
/**
* 初始條件：線性表 L存在
* 操作結(jié)果：銷毀線性表 L
* @param L
*/
void DestroyList(SqList *L) {
free(L->elem);
L->elem = NULL;
L->length = 0;
L->listSize = 0;
}
/**
* 初始條件：線性表 L 存在
* 操作結(jié)果：將 L 置為空表
* @param L
*/
void ClearList(SqList *L) {
L->length = 0;
}
/**
* 初始條件：線性表 L 存在
* 操作結(jié)果：若 L 為空表，返回 TRUE，否則返回 FALSE
* @param L
* @return
*/
Status ListEmpty(SqList L) {
if (L.length == 0) {
return TRUE;
} else {
return FALSE;
}
}
/**
* 初始條件：線性表 L 存在
* 操作結(jié)果：返回 L 中的數(shù)據(jù)元素個(gè)數(shù)
* @param L
* @return
*/
int ListLength(SqList L) {
return L.length;
}
/**
* 初始條件：線性表 L 存在，且 1 <= i <= ListLength(L)
* 操作結(jié)果：用 e 返回 L 中第 i 個(gè)元素的值
* @param L
* @param i
* @param e
* @return
*/
Status GetElem(SqList L, int i, ElemType *e) {
if (i < 1|| i > L.length) {
return ERROR;
}
*e = *(L.elem + i - 1);
return OK;
}
/**
* 初始條件：線性表 L 存在
* 操作結(jié)果：返回 L 中第一個(gè)值與元素 e 相同的元素在 L 中的位置。若元素不存在，則返回 0
* @param L
* @param e
* @param compare
* @return
*/
int LocateElem(SqList L, ElemType e, Status(*compare)(ElemType, ElemType)) {
ElemType *p;
int i = 1;
p = L.elem;
while (i <= L.length && !compare(*p++, e)) {
++i;
}
if (i < L.length) {
return i;
} else {
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 無定義
* @param L
* @param cur_e
* @param pre_e
* @return
*/
Status PriorElem(SqList L, ElemType cur_e, ElemType *pre_e) {
int i = 2;
ElemType *p = L.elem + 1;
while (i < L.length && *p != cur_e) {
p++;
i++;
}
if (i > L.length) {
return INFEASIBLE;
} else {
*pre_e = *(--p);
return OK;
}
}
/**
* 初始條件：線性表 L 存在
* 操作結(jié)果：若 cur_e 是 L 中的元素，且不是最后一個(gè)，則用 next_e 返回其后驅(qū)，否則失敗，next_e 無定義
* @param L
* @param cur_e
* @param next_e
* @return
*/
Status NextElem(SqList L, ElemType cur_e, ElemType *next_e) {
int i = 1;
ElemType *p = L.elem;
while (i < L.length - 1 && *p != cur_e) {
p++;
i++;
}
if (i == L.length) {
return INFEASIBLE;
} else {
*next_e = *++p;
return OK;
}
}
/**
* 初始條件：線性表 L 存在，且 1 <= i <= ListLength(L) + 1
* 操作結(jié)果：在 L 中第 i 個(gè)元素前插入新的元素 e，L 的長度加 1
* @param L
* @param i
* @param e
* @return
*/
Status ListInsert(SqList *L, int i, ElemType e) {
ElemType *newBase, *p, *q;
if (i < 1 || i > L->length + 1) {
return ERROR;
}
if (L->length == L->listSize) {
newBase = realloc(L->elem, (LIST_INIT_SIZE + LIST_INCREMENT) * sizeof(SqList));
if (!newBase) {
exit(OVERFLOW);
}
L->elem = newBase;
L->listSize += LIST_INCREMENT;
}
q = L->elem + i - 1;
for (p = L->elem + L->length - 1; p >= q; --p) {
*(p + 1) = *p;
}
*q = e;
++L->length;
return OK;
}
/**
* 初始條件：線性表 L 存在且非空，且 1 <= i <= ListLength(L)
* 操作結(jié)果：刪除 L 中的第 i 個(gè)元素并用 e 返回其值，L 的長度減 1
* @param L
* @param i
* @param e
* @return
*/
Status ListDelete(SqList *L, int i, ElemType *e) {
ElemType *p, *q;
if (i < 1 || i > L->length) {
return ERROR;
}
p = L->elem + i - 1;
*e = *p;
q = L->elem + L->length - 1;
for (++p; p <= q; ++p) {
*(p - 1) = *p;
}
--L->length;
return OK;
}
/**
* 初始條件：線性表 L 存在
* 操作結(jié)果：對線性表進(jìn)行遍歷，在遍歷過程中對每個(gè)結(jié)點(diǎn)訪問一次，遍歷過程中調(diào)用 vi() 操作元素
* @param L
* @param vi
*/
void TraverseList(SqList L, void(*vi)(ElemType *)) {
ElemType *p = L.elem;
for (int i = 0; i < L.length; ++i) {
vi(p);
++p;
}
printf("\n");
}
void vi(ElemType *e) {
printf("%d ", *e);
}
/*--------------------主函數(shù)------------------------*/
/**
* 測試程序
* @return
*/
int main() { //這里的測試程序只是測了一下函數(shù)是否有邏輯錯(cuò)誤
SqList S;
int temp;
ElemType *e;
InitList(&S);
printf("%d\n", ListEmpty(S));
printf("%d\n", ListLength(S));
temp = ListInsert(&S, 1, 4);
temp = ListInsert(&S, 2, 8);
temp = ListInsert(&S, 3, 9);
temp = ListInsert(&S, 3, 3);
TraverseList(S, vi);
temp = GetElem(S, 3, e);
printf("%d\n", *e);
temp = PriorElem(S, 3, e);
printf("%d\n", *e);
temp = NextElem(S, 3, e);
printf("%d\n", *e);
printf("%d\n", LocateElem(S, 8, compare));
temp = ListDelete(&S, 4, e);
TraverseList(S, vi);
ClearList(&S);
printf("%d\n", ListLength(S));
DestroyList(&S);
}
想要查看源碼可以訪問下面 github 鏈接，如果覺得不錯(cuò)，請給個(gè) Star。
本文屬數(shù)據(jù)結(jié)構(gòu)系列持續(xù)更新中。
