第九周软件工程学习知识总结（《数据结构与算法》）
一.动态数组的有序线性表
1.头文件：
2.c档
3.主程序
4.运行结果
二.线性表的链结表表示法
1.线性表可以使用固定数组和变动数组来实现；另外，线性表也可使用链结表来表示。
链结表 (linked list) 就是用「链」连接在一起的多个节点。 节点 (node)：包含两个部分数据 (data) 与链 (link)，如下图所示
数据可以是一个整数 (integer)、有理数 (rational number)、实数 (real number)、字符串 (string)、或学生记录 (student record) 等。
链的作用就是将两个节点连接在一起。 链是有方向的，从一个节点出发到另一个节点，这个方向可理解为「指向」;也就是说从节点 A 指向节点 B。
如果一个节点的链没有指向另一个节点，则它的链是空的，用 NULL 表示，符号为 ?或 ?。
节点可以有一个、两个或多个链。
单链节点可用来设计单链线性表 (single-linked linear list)、栈 (stack)、和队列 (queue)。
双链节点可用来设计双链线性表 (double-linked linear list)、循环双链线性表 (circular double-linked linear list)、和二叉树 (binary tree)。
多键节点可用来设计多叉树 (multi-tree) 和图 (graph) 。
单链线性表是多个单链节点的数据结构，如下图所示：
所有的节点都要连结，不能有断链的节点。
只有一个节点没有链指向它，称为头节点 (head node)、始节点 (starting node)、或第一节点 (first node)。
只有一个节点它的链是空的，称为尾节点 (tail node)、终结点 (ending node)、或最后节点 (last node)。
如果线性表任意两个互相连结的节点，节点1 指向节点2，且节点1的数据小于或等于节点2 的数据，亦即 a0?a1?a2?…?an-2?an-1，则线性表是一个单链有序线性表 (single-linked ordered linear list)。
C 程序语言可使用递归结构 (recursive structure) 定义单链有序线性表的节点 :
typedef int ElemType;
// 定义线性表元素类型为整数
int. typedef struct node {
// 定义链结表节点
ElemType elem;
// 节点数据，整数
struct node* next;
// 节点的链，递归定义。 }
Node;
// 节点型态
typedef Node* Link;
// 节点的链，是节点的指针。
// 有序线性表是一个节点指针，指向链结表的头节点。
typedef Link List; List L;
// 声明一个单链有序线性表。
单链有序线性表基本操作介面：
// 初始化线性表，将 size 设为 0。
void initial(List *);
// 线性表的大小。
int getSize(List); // 取出线性表的第 i 个元素, 返回该元素的值；
// 若 i 大于线性表的元素个数，返回 -1。
ElemType getElem(List, int);
// 搜寻线性表的元素，返回该元素的位置。若成功，返回该元素的位置；
// 否则，返回 -1。
int search(List, ElemType);
// 将一个元素插入线性表适当的位置。若成功，返回该元素的位置；
// 否则，返回 -1
int insert(List *, ElemType);
// 从线性表删除一个元素。若成功，返回该元素原来的位置；否则，
// 返回 -1。
int delete(List *, ElemType);
// 将线性表清空。
void clear(List *);
// 检查线性表是否為空表。若是空，返回 1；否则，返回 0。
int is_empty(List);
// 打印线性表元素。我们增加这个函数，因为它的必要性。
void printlst(List);
1.头文件
2.c档
3.主程序
4.运行结果
三.循环链表
1.
