线性表

“线性表(Linear List)”：由同类型数据元素构成有序序列的线性结构

表中元素个数称为线性表的长度线性表没有元素时，称为空表表起始位置称表头，表结束位置称表尾

线性表的链式存储

1. 结构定义：

typedef struct LNode* List; //List是struct LNode*的别名 struct LNode { ElementType Data; List Next; //下一个节点的位置 }; struct LNode L; List Ptrl;

2. 求表长

int Length(List PtrL) { List p = PtrL; int j = 0; while (p) { p = p->Next; j++; } return j; } > 平均时间复杂度 O(n)

3. 查找

+ 按序号查找 ``` List FindKth(int K, List PtrL) { List p = PtrL; int i = 1; while (p != NULL && i < K) { p = p->Next; i++; } if (i == K) return p; else return NULL;

} ```

+ 按值查找 ``` List Find(ElementType X, List PtrL) { List p = PtrL; while (p != NULL && p->Data != X) p = p->Next; return p;

} ```

> 平均时间复杂度 O(n)

4. 插入

（1）先构造一个新结点，用s指向； （2）再找到链表的第 i-1个结点，用p指向； （3）然后修改指针，插入结点 ( p之后插入新结点是s)

List Insert(ElementType X, int i, List PtrL) { List p,s; if (i == 1) { s = (List)malloc(sizeof(struct LNode)); s->Data = X; s->Next = PtrL; return s; } p = FindKth(i - 1,PtrL); if (p == NULL) { printf("参数i错"); return NULL; } else { s= (List)malloc(sizeof(struct LNode)); s->Data = X; s->Next = p->Next; p->Next = s; return PtrL; } } > 平均时间复杂度 O(n)

5. 删除

（1）先找到链表的第 i-1个结点，用p指向； （2）再用指针s指向要被删除的结点（p的下一个结点）; （3）然后修改指针，删除s所指结点; （4）最后释放s所指结点的空间。

List Delete(int i, List PtrL) { List p, s; if (i == 1) { s = PtrL; if (PtrL != NULL) PtrL = PtrL->Next; else return NULL; free(s); return PtrL; } p = FindKth(i-1, PtrL); if (p == NULL) { printf("第%d个节点不存在", i - 1); return NULL; } else if (p->Next == NULL) { printf("第%d个节点不存在", i); return NULL; } else { s = p->Next; p->Next = s->Next; free(s); return PtrL; } } > 平均时间复杂度 O(n)