結構定義
typedef int ElemType;
struct List {
ElemType *data; // 動態數組
int size; // 當前長度
int maxSize; // 容量
};
16 操作清單
| 分類 | 操作 | 關鍵點 |
|---|
| 初始化/銷毀 | initList(L, ms) | malloc 分配、檢查 ms 有效性 |
| clearList(L) | free 內存、歸零字段 |
| 查詢 | sizeList(L) | 返回 size |
| emptyList(L) | size==0 判斷 |
| getElem(L, pos) | 1-based 索引轉 0-based、越界終止 |
| 遍歷/查找 | traverseList(L) | 順序打印 |
| findList(L, x) | 順序掃描、命中返下標否則 -1 |
| 修改 | updatePosList(L, pos, x) | 越界返 0，成功返 1 |
| 插入 | insertFirstList(L, x) | 後移元素、擴容檢查 |
| insertLastList(L, x) | 尾部追加、擴容檢查 |
| insertPosList(L, pos, x) | pos 合法性、後移、擴容 |
| insertOrderList(L, x) | 有序插入、順序查找位置 |
| 刪除 | deleteFirstList(L) | 前移元素、返被刪值、空表終止 |
| deleteLastList(L) | size--、返原尾值 |
| deletePosList(L, pos) | 前移、返被刪值 |
| deleteValueList(L, x) | 查找首個 x、前移、成否返 1/0 |
動態擴容機制
void againMalloc(List *L) {
ElemType *p = realloc(L->data, 2 * L->maxSize * sizeof(ElemType));
if (!p) exit(1);
L->data = p;
L->maxSize *= 2;
}
測試主程序
int main() {
List L; initList(&L, 5);
int a[] = {2,4,6,8,10,12,14,16,18,20};
for (int i=0;i<10;i++) insertLastList(&L, a[i]);
insertPosList(&L, 11, 48); insertPosList(&L, 1, 64);
// ... 驗證查找、修改、刪除、遍歷
clearList(&L);
return 0;
}
