文档介绍：重点：顺序表和链表上各种基本算法的实现及相关的时间性能分析
难点：线性表应用的算法设计
线性表
线性表
线性表的类型定义
线性表的顺序表示和实现
线性表的链式表示和实现
线 10 /* 存储空间的分配增量 */ typedef struct{ ElemType *elem; /* 存储空间的基址 */ int length; /* 当前长度 */ int listsize; /* 当前分配的存储容量 */ }SqList; 该方案解决方案一中的“上溢”问题和“空间利用率不高”问题 ，但是有时间和空间代价的 。 1) 必须记载当前线性表的实际分配的空间大小； 2) 当线性表不再使用时，应释放其所占的空间； 3) 要求实现级的语言能提供空间的动态分配与释放管理。
*-
第3讲 线性表—顺序表、链表
章节范围：~
重点：顺序表和链表上各种基本算法的实现及相关的时间性能分析
难点：线性表应用的算法设计
第二章 线性表
第二章 线性表
线性表的类型定义
线性表的顺序表示和实现
线性表的链式表示和实现
线性链表
静态链表
循环链表
双向链表
一元多项式的表示及相加(基于线性表的应用)
*-
上次课的要点
如何辨别C程序中的标识符?
线性表的逻辑特征
ADT List及基于ADT List的算法设计
线性表的顺序存储——顺序表
逻辑上相邻，物理上必然相邻
随机存取
类型定义——方案1和方案2
*-
–类型定义与基本操作实现
C中的动态分配与释放函数
void *malloc(unsigned int size) 生成一大小为size的结点空间，将该空间的起始地址赋给p；
free(void *p) 回收p所指向的结点空间;
void *realloc(void *p, unsigned int size) 将p所指向的已分配内存区的大小改为size，size可以比原分配的空间大或小。
old
p
new
size
起址 返回
*-
–类型定义与基本操作实现
基本操作的实现 P10
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
/* 函数结果状态类型，其值为上述的状态代码 */
typedef int Status;
*-
–类型定义与基本操作实现
基本操作的实现
初始化 Status InitList_Sq(SqList &L) Status InitList_Sq( SqList &L) { // 构造一个空的线性表L = (ElemType *) malloc(LIST_INIT_SIZE*sizeof(ElemType)); if ( == NULL ) exit(OVERFLOW); // 存储分配失败 = 0; // 空表长度为0 = LIST_INIT_SIZE;// 初始存储容量 return OK; } // InitList_Sq
*-
–类型定义与基本操作实现
基本操作的实现
求表长
取第i个元素 [i-1] (0<i<+1)
按值查找 int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType)) { for(i=0; i< && !(*compare)([i],e); i++); if (i<) return i+1; else return 0; }
*-
–插入操作的实现
基本操作的实现
插入操作 Status ListInsert_Sq(SqList &L, int i, ElemType e)
15 23 46 16 57 10 64
1 2 3 4