2.1线性表的类型定义-结论 2.2线性表的顺序表示和实现 。结论 ▣定义：用一组地址连线的存储单元依火存储线 ·使用不同的算法策略，可以得到不同时间复 性表中的数据元素 杂度的算法 ■特点：逻枰上相邻，物理上也相邻。随机存取 ,输入线性表的特征会形响算法的策略 （是否有序？…) 逻料序号12345 6 陈述问 。输出线性表的特征会形响算法的策略 688970674078 题时用 (是否有序？…) C数组下标012345 13n 回 1W万 图 2.2-顺序表的存储 2.2-顺序表类型定义（方案一） 假设每个元素占用个存储单元，则元素的存 顺序表定义 储位置： ·方案一 #define LIST_SIZE 100 LOC(a)=LOC(a)+ typedef struct{ LOC(a)=LOC(aj)+(i-1)*I ElemType elem[LIST_SIZE]; 严存情空何1 int length; 胪当前长度 12 …i )SqList_static; an 评价： ↑ 1LSTS1ZE进小，则会号顺序表上道： a+(n-1)*I idle 2)LIST SIZE过大，则女导数空间的利用率不高 15/73 图 13 图 2.2-顺序表类型定义（方案二） 2.2C中的动态分配与释放函数 方案二 C中的动态分配与释放函数 void *malloc(unsigned int size) 大小为心的韩底空间，将请空间的起地 typedef struct( ElemType 'elem; ”存储空间的基址 地址赋给p: int length: 产当前长度 free(void *p) int listsize: :当前分配的存储客量1 回收p所指向的结点空间： )SqList; .void *realloc(void *p,unsigned int size) 将D所描向的已分配内存区的大小改为size,sizc 该方案解决方案一中的上滥"问圆和“空间利用率不高问 愿，但是有时间和空间代价的。 分配成助示组 可以比原分配的空间大或小。 )必须记藏当前做性表的实际分配的空间大小： 当 引当或不再使用时，应放其所占的空间： 3)要夹现的语言能展供空间的动本分配与放理， 177万 图13/73 2.1 线性表的类型定义-结论 „ 结论 „ 使用不同的算法策略，可以得到不同时间复 杂度的算法 „ 输入线性表的特征会影响算法的策略 （是否有序？…） „ 输出线性表的特征会影响算法的策略 （是否有序？…） 14/73 2.2 线性表的顺序表示和实现 „ 定义：用一组地址连续的存储单元依次存储线 性表中的数据元素 „ 特点：逻辑上相邻，物理上也相邻。随机存取 68 89 70 67 40 78 逻辑序号 1 2 3 4 5 6 C数组下标 0 1 2 3 4 5 陈述问 题时用 15/73 2.2 -顺序表的存储 假设每个元素占用l个存储单元，则元素的存 储位置： LOC(a i+1) = LOC( a i )+l LOC(a i ) = LOC(a1)+(i-1)*l a1 a2 … a i …… … an 1 2 … i ……… n a a+l … a+(i-1)*l … … … a+(n-1)*l idle 16/73 2.2 –顺序表类型定义(方案一) „ 顺序表定义 „ 方案一 #define LIST_SIZE 100 typedef struct{ ElemType elem[LIST_SIZE]; /* 存储空间*/ int length; /* 当前长度*/ }SqList_static; 评价： 1)LIST_SIZE过小，则会导致顺序表上溢； 2) LIST_SIZE过大，则会导致空间的利用率不高 17/73 2.2 –顺序表类型定义(方案二) „ 方案二 #define LIST_INIT_SIZE 100 /* 存储空间的初始分配量*/ #define LISTINCREMENT 10 /* 存储空间的分配增量 */ typedef struct{ ElemType *elem; /* 存储空间的基址 */ int length; /* 当前长度 */ int listsize; /* 当前分配的存储容量 */ }SqList; 该方案解决方案一中的“上溢”问题和“空间利用率不高”问 题 ，但是有时间和空间代价的 。 1) 必须记载当前线性表的实际分配的空间大小； 2) 当线性表不再使用时，应释放其所占的空间； 3) 要求实现级的语言能提供空间的动态分配与释放管理。 18/73 2.2 –C中的动态分配与释放函数 „ 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 起址 返回 回收 分配成功示例