《数据结构》课程PPT教学课件（2012）第2章 线性表 2.3 线性表的链式表示和实现 2.3.1 链表的表示

要求 有三个人要被关进监狱三年，监狱长给他们三个一人一个要求。 美国人爱抽雪茄，要了三箱雪茄。 法国人最浪漫，要一个美丽的女子相伴。 而犹太人说，他要一部与外界沟通的电话。 三年过后，第一个冲出来的是美国人，嘴里鼻孔里塞满了雪茄，大喊道： “给我火，给我火！”原来他忘了要火了。 接着出来的是法国人。只见他手里抱着一个小孩子，美丽女子手里牵着一 个小孩子，肚子里还怀着第三个。 最后出来的是犹太人，他紧紧握住监狱长的手说：“这三年来我每天与外 界联系，我的生意不但没有停顿，反而增长了200%，为了表示感谢，我送你一 辆劳施莱斯！” 这个故事告诉我们，什么样的选择决定什么样的生活。今天的生活 是由三年前我们的选择决定的，而今天我们的块择将决定我们三年后 的生活。我们要选择接触最新的信息，了解最新的趋势，从而更好的 创造自己的将来

要求 有三个人要被关进监狱三年，监狱长给他们三个一人一个要求。 美国人爱抽雪茄，要了三箱雪茄。 法国人最浪漫，要一个美丽的女子相伴。 而犹太人说，他要一部与外界沟通的电话。 三年过后，第一个冲出来的是美国人，嘴里鼻孔里塞满了雪茄，大喊道： “给我火，给我火！”原来他忘了要火了。 接着出来的是法国人。只见他手里抱着一个小孩子，美丽女子手里牵着一 个小孩子，肚子里还怀着第三个。 最后出来的是犹太人，他紧紧握住监狱长的手说：“这三年来我每天与外 界联系，我的生意不但没有停顿，反而增长了200％，为了表示感谢，我送你一 辆劳施莱斯！” 这个故事告诉我们，什么样的选择决定什么样的生活。今天的生活 是由三年前我们的选择决定的，而今天我们的抉择将决定我们三年后 的生活。我们要选择接触最新的信息，了解最新的趋势，从而更好的 创造自己的将来

目录 第1章 绪论 第2章 线性表 栈和队列 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第9章 查找 第10章 排序 2

2 第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第9章 查找 第10章 排序 目 录

课堂讨论： 顺序表各种操作算法的“通式” 该如何书写？ 采用抽象数据类型来表示 顺序表的存储结构是一维数组，如果插入的元素 个数超过数组定义的长度怎么办？ 采用动态分配的一维数组 3

3 课堂讨论： 顺序表各种操作算法的“通式” 该如何书写？ ———采用抽象数据类型来表示 顺序表的存储结构是一维数组，如果插入的元素 个数超过数组定义的长度怎么办？ ———采用动态分配的一维数组

动态数组简介 先为顺序表空间设定一个初始分配量，一旦因 插入元素而空间不足时，可为顺序表增加一个固定长 度的空间增量。存储结构描述如下（见教材P22)： #define LIST INIT SIZE 100/存储空间的初始分配量 #define LISTINCREMENT 10/存储空间的分配增量 Typedef struct{ ElemType *elem; /表基址（用指针*elem表示） int length; /表长度（表中有多少个元素） int listsize; /当前分配的表尺寸（字节单位） SqList; 注：三个分量可简写为：L.elem L.length L.listsize

4 动态数组简介 先为顺序表空间设定一个初始分配量，一旦因 插入元素而空间不足时，可为顺序表增加一个固定长 度的空间增量。 #define LIST_INIT_SIZE 100 //存储空间的初始分配量 #define LISTINCREMENT 10//存储空间的分配增量 Typedef struct{ ElemType *elem; //表基址(用指针*elem表示） int length; //表长度（表中有多少个元素） int listsize; //当前分配的表尺寸（字节单位） }SqList; 注：三个分量可简写为：L.elem L.length L.listsize 存储结构描述如下（见教材P22）：

动态创建一个空顺序表的算法： Status InitList Sq(SqList &D) /创健一个空线性表 L.elem=(ElemType*)malloc(LIST_INIT_SIZE sizeof(ElemType)); IfL.elem)exit(OVERFLOW);/分配失败，结束程序 [.length=0; /暂无元素放入，空表 L.listsize=LIST INIT SIZE; /表尺寸=初始分配量 Return OK; //InitList Sq malloc(m)函数的意思是：新开一 片大小为m字节的连续空间，并把 sizeof(x)算符的意思是： 该区首址作为函数值。 计算变量x的长度（字节数）

5 sizeof(x)算符的意思是： 计算变量x的长度(字节数) malloc (m)函数的意思是：新开一 片大小为m字节的连续空间，并把 该区首址作为函数值。 Status InitList_Sq( SqList &L ) //创建一个空线性表 { L.elem=(ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType)); If(!L.elem) exit(OVERFLOW); //分配失败，结束程序 L.length=0; //暂无元素放入，空表 L.listsize=LIST_INIT_SIZE; //表尺寸=初始分配量 Return OK; } //InitList_Sq 动态创建一个空顺序表的算法：

动态顺序表的插入算法 Status ListInsert Sq(SqList &L,int i,ElemType e) {/在顺序线性表中第个位置之前插入新的元素© if(iL.length-+1)return ERROR;/检验i值的合法性 if(L.length≥L.listsize)八/若表长超过表尺寸则要增加尺寸 newbase =ElemType*)realloc L.elem,(L.listsize LISTINCREMENT)*sizeof ElemType )) if(newbase-NULL)exit(OVERFLOW);/分配失败则退出并报错 L.elem newbase /重置新基址 L.listsize=L.listsiz远+LISTINCREMENT;}/增加表尺寸 realloc(*p,newsize)函数的意思是：新开- 片大小为newsize的连续空间，并把以*p为 首址的原空间数据都拷贝进去

6 realloc (*p, newsize)函数的意思是：新开一 片大小为newsize的连续空间，并把以*p为 首址的原空间数据都拷贝进去。 动态顺序表的插入算法 Status ListInsert_Sq(SqList &L, int i, ElemType e) { //在顺序线性表中第i个位置之前插入新的元素e if( i L.length+1) return ERROR; // 检验i 值的合法性 if ( L.length ≥ L.listsize ) //若表长超过表尺寸则要增加尺寸 { newbase = ( ElemType* ) realloc ( L.elem , (L.listsize + LISTINCREMENT )* sizeof ( ElemType ) ); if (newbase=NULL )exit( OVERFLOW ) ; //分配失败则退出并报错 L.elem = newbase ; //重置新基址 L.listsize = L.listsize + LISTINCREMENT ; } //增加表尺寸

g=&L.elem[i-1] 儿为插入位置。这是没有头结点的情况 for (p=L.elem[L.tength-1];p>=q -p)*(p+1)=*p 插入位置及之后的元素统统后移，为元素位置 g=e 7插入e ++L.length /增加1个数据元素，则表长+灯 return OK }//ListInsert Sq 动态数组的核心是real loc(void *ptr.,news i ze)函数！

7 q = &L.elem[i-1] ; // q为插入位置。这是没有头结点的情况 for ( p = L.elem[L.length-1] ; p>=q ; -p ) *(p+1) = *p ; //插入位置及之后的元素统统后移, p为元素位置 *q= e ; //插入e ++L.length ; //增加1个数据元素，则表长+1 return OK ; } //ListInsert_Sq 动态数组的核心是realloc(void *ptr, newsize)函数！

动态顺序表的删除算法 Status ListDelete Sq(SqList &L,int i,ElemType &e) {在顺序表L中删除第个元素，用e返回其值 ifiL.length)return ERROR;∥i值不合法，返▣ p=&L.elem[i-1]; ∥p是被删除无素的位置 e=*p; /被删除元素的值赋给e qL.elem+L.length-l;从q是表尾的位置 for(+p;p<=q;p+)*(p-1)=*p;/待删元素后面的统统前移 -L.length; 1表长-1 return OK; //ListDelete Sq 8

8 动态顺序表的删除算法 Status ListDelete_Sq(SqList &L, int i, ElemType &e) { //在顺序表L中删除第 i 个元素，用 e 返回其值 if (i L.length) return ERROR; // i 值不合法，返回 p=&L.elem[i-1]; // p 是被删除元素的位置 e=*p; //被删除元素的值赋给 e q=L.elem+L.length-1; // q 是表尾的位置 for(++p; p<=q; p++) *(p-1) = *p; //待删元素后面的统统前移 -L.length; //表长 - 1 return OK; } //ListDelete_Sq

2.2节小结 线性表顺序存储结构特点：逻辑关系上相邻的两个元素 在物理存储位置上也相邻； 优点：可以随机存取表中任一无素，方便快捷： 缺点：在插入或删除某一元素时，需要移动大量元素。 解决问题的思路：改用另一种线性存储方式： 链式存储结构

9 链式存储结构 2.2节小结 线性表顺序存储结构特点：逻辑关系上相邻的两个元素 在物理存储位置上也相邻； 优点：可以随机存取表中任一元素，方便快捷； 缺点：在插入或删除某一元素时，需要移动大量元素。 解决问题的思路：改用另一种线性存储方式：

第2章线性表 2.1线性表的逻辑结构 2.2线性表的顺序表示和实现 2.3线性表的链式表示和实现 2.4应用举例 10

10 第2章 线性表 2.1 线性表的逻辑结构 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 应用举例