第11章线性表.ppt

1、计算机教学实验中心 西安交通大学,C语言程序设计 第11章 线性表,教学目标,介绍线性表的两种存储结构定义：一种是顺序表；另一种是链表。,学习要求,掌握线性表顺序存储结构的定义，顺序表的插入和删除； 掌握线性表非顺序存储结构的定义，单链表的插入和删除。 区分带头结点链表和不带头结点链表异同 领会循环链表、双向链表结构,11.1 线性表概述,计算机的处理效率与数据的组织形式和存储结构密切相关。这类似于人们所用的“英语词典” ，它是由按英文字母的顺序组织排列的“词条”组成,这样人们查阅词典时可以按照自己熟悉的排列顺序去查找。查找的速度较快。另外在当今网络世界中数据通讯更加依赖于数据的组织形式和存储

2、结构。总之计算机处理数据要追求“时间”和“空间”上的双重效率。而“时空效率”与数据的组织存储结构密切相关。 这里我们研究在日常生活中一类常见的表格数据（即用表格形式存放的数据）的处理方法。观察下列表格数据：列车时刻表、学生成绩单和英文周名缩写名称表等，如表11-1、表11-2、表11-3所示：,表11-1 列车时刻表,表11-2学生成绩单,表11-3英文周名缩写名称表,线性表概述（续）,这些表格形式的数据具有如下共同特点： 1）表中每一行信息虽然组成的内容不同，但都具有某个明确独立的含义，将表中每一行信息称之为一个数据元素； 2）每个数据元素在表中的位置固定，除了第一个元素和最后一个元素外，其

3、余元素都有唯一一个前驱元素和唯一一个后继元素； 3）表中数据元素的个数不一定相等，有长有短； 4）大多数表格中数据元素会增加或减少，是动态变化的。如表11-1和表11-2。但也有线性表是固定不变，如表11-3。 将这些表格形式的数据加以抽象，统称为线性表。,线性表的定义,线性表的抽象定义： 线性表是由n（n0）个类型相同的数据元素a 1，a 2，a 3，a n 组成的有限序列，记为：（ a 1，a 2，a 3，a n ）。线性表中当前存储的数据元素数目叫做表的长度，n为表长，当线性表中不包含任何数据元素即n=0时 ，称为空表。 注意两点： 1）数据元素a i（1in）表示某个具体意义的信息，它

4、可以是一个数，或者是一个字符串，或者是由数和字符串组成的更复杂的信息。但同一个线性表中的所有数据元素必须具有相同的属性（或者说具有相同的数据类型）； 2）若线性表是非空表，则有：（）第一个元素a 1无前趋元素；（）最后一个元素a n无后继元素；（）其它元素a i（1in）均只有一个直接前趋a i-1 和一个直接后继a i+1。,线性表定义（续）,例如： 某校19982003年在校学生人数（2500，3450，5000，5100，5400，5500）是一个线性表； 每个月份英文缩写名称组成一个线性表（JAN，FEB，MAR，APR，MAY，JUN，JUL，AUG，SEP，OCT，NOV，DEC）

5、； 屏幕上若干像素（50，50，RED），（100，150，RED），（200，200，BLUE），（200，250，GREEN）亦是一线性表； 像学生情况登记表、电话号码簿、股票市场里的信息列表、航班时刻表、各种各样的统计报表等等都是线性表。因此研究线性表的存储结构便于拓宽计算机在各行各业中的应用。,线性表的另一种形式化定义,在计算机系的数据结构专业课程中，对于线性表给出了如下形式化的定义： linear_list = ( D , R ) 其中，D是数据元素的集合， D = a 1，a 2，a 3，a n R是数据元素之间关系的集合， R= , 。 其中给出了数据元素的一种先后次序关系，即表

6、中的数据元素都有固定的位置。,线性表的操作,经过分析研究，人们总结出线性表应该具有如下常用的基本操作： 1）求表长：设L代表某个线性表，统计L里总共有多少个元素。记作Length（L）。例如股民要了解有多少股票；学校要了解学生人数；政府要掌握本地区人口数量等。 2）取元素：获取L中某个数据元素的信息，记作Get（L，i），i为表中元素的位置或序号，仅当1iLength（L）时，取得线性表L中的第i个元素a i（或a i的存储位置），否则无意义。 3）置换元素: 置换或修改L中某个数据元素的信息。记作Replace（L，i，x）。 4）插入元素:在L中某个位置上增加一个数据元素。记作Insert

7、（L，i，x），在L的第i个位置上插入元素x。例如某班转来一名新学生；股票市场发行新股票等。 5）删除元素:删除线性表中某个位置上的一个数据元素。记作Delete（L，i），删除线性表L的第i个位置上的元素ai。,线性表的操作（续）,6）查找元素：查找某个数据元素是否在线性表中存在。记作Locate（L，x），x为要查找的数据元素。若在L中有多个x，则只返回第一个x的位置，若在L中不存在x，则返回0。例如查找电话号码；查找某趟列车；查询某个学生的成绩等。 7）求前驱元素，记作Prior（L，i），取元素ai的直接前驱，当2iLength（L）时，返回a i的直接前趋a i-1。注意表头元素a

8、1无前驱。 8）求后继元素，记作Succ（L，i），取元素ai的直接后继，当1iLength（L）-1时，返回a i的直接后继a i+1。注意表尾元素a n无后继。 9）排序：对线性表中的数据元素按某个数据项的值递增（或递减）的顺序排列。记作Sort(L)。 对线性表还有一些更为复杂的操作，如：将两个线性表合并成一个线性表；将一个线性表分解为两个线性表等。这些运算都可以通过上述九种基本运算的组合派生来实现。,线性表的两种存储结构,在计算机内，线性表有两种存储结构：顺序存储结构和链式存储结构。下面讲述怎样利用C语言中的结构体类型来定义顺序存储结构和链式存储结构。分别称为顺序表和链表。,11.2

9、顺序表 - 顺序存储结构,线性表的顺序存储结构就是将线性表中的每个数据元素按其逻辑次序依次存放在一组地址连续的存储器空间里。由于逻辑上相邻的数据元素存放在内存的相邻单元中，所以线性表的逻辑关系蕴含在存储单元的物理位置中。也就是说，在顺序存储结构中，线性表的逻辑关系的存储是隐含的，并没有额外开辟存储空间去存放关系集合。只存放了数据元素集合。 假设线性表中每个数据元素占用 C 个存储单元（字节数） ， 用Loc（a i）表示元素a i的存储位置（ a i 的地址），则顺序存储结构的存储示意图如图11.1所示。,图11.1 线性表的顺序存储结构示意图,从图11.1可以看出，若已知线性表的第一个元素的

10、存储位置是Loc（a1），则第i个元素的存储位置为： Loc（a i）=Loc（a 1）+C * (i-1) 1in,C语言使用一维数组描述顺序表,为了简单起见，假设线性表中的数据元素类型为浮点型，线性表顺序存储结构用C可描述为如下顺序表： #define MAXSIZE 1000 / MAXSIZE为表中数据元素个数 的最大可能性 float seqlistMAXSIZE; / 浮点类型一维数组 int last = -1; / last为线性表中表尾元素的下标 由此可见，线性表的顺序存储结构实际上就是C语言中的一维数组存储结构。MAXSIZE为线性表中数据元素个数的最大可能值，last为线

11、性表中表尾元素的下标。last赋值-1表明此时此刻线性表为空表。值得说明的是数据元素类型选取浮点型是为了后面讨论方便而已。,使用一维数组描述顺序表（续）,事实上线性表中数据元素的类型可以是整型数，也可以是复杂的构造类型。例如表11-2学生成绩单可以定义为如下顺序表： #define MAXSIZE 1000 struct student long num; char name9; char sex; float score; student_scoreMAXSIZE; int last = -1;,线性表的基本操作函数或函数原型,1。int isempty() return last = -1

12、?1:0; / 判空表 2。int isfull() return last = MAXSIZE-1; / 判表满 3。int length() return last+1; / 求表长 4。int get_data(int i,float *x) / 取元素 i-; if (i =0 ,线性表的基本操作函数或函数原型（续）,5。 取前驱元素函数 int get_prior(int i,float *x) /取前驱元素 i-; if(i0 ,线性表的基本操作函数或函数原型（续）,6。取后继元素函数 int get_succ(int i,float *x) i-; if(i=0 ,线性表的基本操

13、作函数或函数原型（续）,7。置换元素函数 int replace(int i,float x) /置换元素 i-; if (i=0 ,线性表的基本操作函数或函数原型（续）,8。 int insert_data(int i,float x); /插入元素 9。 int delete_data(int i); /删除元素 10。void print_list(); /显示表中所有元素 11。int find_data(float x); /查找元素 12。void sort(); /排序元素 下面讨论在顺序存储结构下，插入和删除函数的算法实现。查找和排序函数的实现算法放在第13章、第14章讨论。,

14、顺序存储结构下，插入函数算法实现,已知线性表的当前状态是 （a 1，a 2，a i-1，a i，a n）， 要在第i个位置插入一个元素x，线性表成为 （a 1，a 2，a i-1，x，a i，a n）。 插入算法的主要步骤如下： 第1步: 判定表不满，方可插入； 第2步: 判定插入位置i的合法性； 第3步: 将第n至第i个元素后移一个存储位置； 第4步: 将x插入到a i-1之后； 第5步: 线性表的长度加1。,顺序存储结构下，插入函数算法实现（续）,int insert_data(int i,float x) if (isfull() / 判定表满否 printf(表已满，不能插入！n);

15、return 0; if ( i=1 ,顺序存储结构下，删除函数算法实现,已知线性表当前状态是 （a 1，a 2，a i-1，a i，a i+1，a n）， 若删除第i个元素a i，则线性表成为 （a 1，a 2，a i-1，a i+1，a n）。 需要提醒的是首先应该检查i的合法性,即位置i上是否存在元素 删除算法的主要步骤如下： 第1步： 判定表不空方可删除； 第2步： 判定删除位置i值的合法性； 第3步： 将位置i+1，i+2，n上的元素依次向前移动一个存储位置； 第4步： 将线性表的长度减1。,顺序存储结构下，删除函数算法实现 （续）,int delete_data(int i) if

16、(isempty() / 判定表空否 printf(表已空，不能删除！n); return 0; if (i=1) ,顺序存储结构适合于表中元素个数变动较少的线性表,从上述算法中，不难看出在某一个位置上插入或删除一个数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于插入或删除元素的位置。平均地看每插入（或删除）一个元素需要移动表中一半元素，而插入和删除又是使用频率较高的操作。一般情况下，线性表的顺序存储结构适合于表中元素个数变动较少的线性表。下面给出测试验证的主函数：,打印输出线性表中所有元素,void print_list() / 打印输出线性表中所有元素 float x; fl

17、oat *px= ,测试验证的主函数,void main() / 测试数据元素从表尾插入顺序表 for(int i=0;i6;i+) insert_data(i+1,(i+1)*100.0); print_list(); / 打印顺序表中的所有元素 /测试插入位置错误调用插入函数 insert_data(-1,1000); insert_data(9,1000); print_list(); / 打印结果 /测试从表头插入元素 insert_data(1,1000.0); print_list(); / 打印结果 / 测试从表的中间位置插入元素 insert_data(3,250.0); pr

18、int_list(); / 打印结果 ,线性表的顺序存储结构有五个特点,综合分析线性表的顺序存储结构有五个特点： 1）可以随机存取线性表中每一个元素，存取元素的速度与它在表中的位置无关； 2）不需要额外开辟空间存储关系集合，其逻辑关系隐含在物理存储结构中； 3）插入和删除元素速度较慢； 4）扩充性差，注意顺序表类定义中MAXSIZE值的确定是件困难的事，MAXSIZE值太大造成存储空间冗余，太小不利于扩充； 5）需要一整块连续空间，但表中元素进进出出，不可能一下子放满，有存储空间空闲不能作为它用。因此能否设计一种非顺序存储结构来克服顺序结构的后三条缺点。,用链式结构存储一个线性表，其特点是用一

19、组任意的存储区域存储该线性表，此存储区域可以是连续的，也可以是分散的。这样，逻辑上相邻的元素在物理位置上就不一定是相邻的，为了能正确反映元素的逻辑次序，就必须在存储每个元素a i的同时，存储其直接后继（或直接前驱）的存储位置。这样在链式结构中每个元素都由两部分组成：存储数据元素的数据域（data）；存储直接后继元素存储位置的指针域（next）。其存储结构示意如下： 在下面讨论中将这样存储的每个数据元素称为结点。,11.3 单链表,结点定义,下面给出每个数据元素存储结构的定义，又称结点定义： struct node float data; /数据域 struct node *next; /指针域

20、 typedef struct node NODE; NODE *head; 由于线性表每个元素都有唯一的后继（除了最尾元素），所以开辟指针域记录后继元素的地址。最尾元素的指针域为空，即为NULL。数据元素本身存储类型同顺序表一样定义成浮点类型。这样一来线性表的非顺序存储结构如图11.2所示：,线性表的非顺序存储结构示意图,图11.2 线性表的非顺序存储结构示意图 非顺序存储结构中每个结点的存储既不是连续的，也不是顺序的。而是散落在存储器的各个区域。通过指针将线性表中每个结点有机地连接起来。指针就好像自行车链条一样。因此图11.2所示的线性表存储结构被称为单向链表，简称单链表。,单链表的基本操

21、作函数原形,与顺序表一样，有了存储结构定义，就要考虑线性表的基本操作如何实现。单链表的基本操作可以写成如下函数原形： int length(); /求表长 int get_data(int i,float *x); /取元素 int get_succ(int i,float *x); /取前驱元素 int get_proc(int i,float *x); /取后继元素 int replace_data(int i,float x) /置换元素 int insert_data(float data,int i); /插入元素 int delete_data(int i); /删除元素 void

22、 print_list(); /打印所有元素 NODE *find_data(int i); /查找元素 void sort(); /排序,单链表结构的特点,单链表结构的特点是： 1）线性表中实际有多少元素就存储多少个结点； 2）元素存放可以不连续，其物理存放次序与逻辑次序不一定一致。换句话说，a i-1可能存放在存储器的下半区，而a i可能存放在存储器的上半区； 3）线性表中元素的逻辑次序通过每个结点指针域有机地连接来体现； 4）插入和删除不需要大量移动表中元素。,其单链表的逻辑示意图,例11-1：一个由食品名组成的线性表（biscuit，butter，cheese，eggs，grapes，

23、jam），采用单链表为存储结构时，其单链表的逻辑示意图为： 在此单链表中，head是指向单链表中第一个结点的指针，我们称之为头指针；最后一个元素jam所在结点不存在后继，因而其指针域为“空”（用NULL或表示）。该单链表在存储器中的物理映像如图11.4所示。,单链表在存储器中的物理映像,设有线性表（a 1，a 2，a i-1，a i，a n），采用单链表存储结构，头指针为head，要求在数据元素a i的结点之前插入一个数据元素为data的新结点 插入前单链表的逻辑状态，如图11.5所示,在链表中插入一个新结点示意图,设新插入的结点指针是newnode，插入后单链表的逻辑状态如图11.6所示,新

24、结点插入步骤,若已知previous指向为a i的前趋a i-1结点，newnode指向新结点。只要执行以下两步操作即可完成插入新结点： 令新结点指针域指向a i结点 newnode-next=previous-next； 令a i-1结点的指针域指向新结点 previous-next=newnode;,单链表结点插入算法描述,插入操作执行之前，首先要得到单链表中插入位置的前一个结点的指针（存储位置）。插入算法的主要步骤如下： 第1步： 判定插入位置是否正确，若正确继续下一步，否则结束算法； 第2步： 申请一个新结点，判定内存有无空间； 第3步： 元素放入数据域，NULL放入指针域； 第4步：

25、 判定是否为插入在表头，若是表头，则修改head和新结点指针； 第5步： 寻找插入位置，指向a i-1结点； 第6步： 修改a i-1结点的指针域和新结点的指针域。,单链表中结点插入函数,int insert_data(float data,int i) /data为要插入的元素值，i为插入位置 NODE *current,*previous,*newnode; int j=1; if(ilength()+1)|(idata=data; newnode-next=NULL;,单链表中结点插入函数（续）,if(i=1) /插入表头，另做处理 newnode-next=head; head=new

26、node; return 1; current=previous=head; while(current!=NULL ,在链表中删除一个新结点示意图,删除操作和插入操作一样，首先要搜索单链表以找到指定删除结点的前趋结点(假设为previous)，然后只要将待删除结点的指针域内容赋予previous所指向的结点的指针域就可以了。 已知单链表的头指针为head，删除前单链表的逻辑状态如图11.7所示。,在链表中删除一个新结点示意图（续）,删除结点之后，单链表的逻辑状态如图11.8所示。,结点删除的操作步骤,若已知previous指向为a i的前趋a i-1结点，只要执行以下两步操作即可完成删除结点

27、： 令a i-1结点指针域指向a i+1结点 previous-next=current-next； 释放a i结点所占存储空间 free(current)；,单链表结点删除算法描述,删除算法的主要步骤和C函数如下： 第1步： 判定是否为空表，若为空表，删除错误，结束算法，否则继续下一步； 第2步： 判定删除位置是否正确，若正确继续下一步，否则结束算法； 第3步： 寻找删除位置，指向a i-1结点； 第4步： 若删除表头元素，修改head指针； 第5步： 若删除非表头元素，修改a i-1结点指针域； 第6步： 释放被删结点的存储空间。,单链表中结点删除函数,int delete_data(in

28、t i) NODE *current,*previous; int j=1; if(head=NULL) /判定是否为空表 printf(表已空，不能删除。n); return 0; ; if(ilength() /判定删除位置是否正确 printf(删除位置不正确，不能删除！n); return 0; current=previous=head;,单链表中结点删除函数（续）,while(current ,length()函数完成求链表的长度,int length() / 求表长函数 int counter=0; / 设置计数器 NODE *current=head; while(curren

29、t!=NULL) / 循环计数每一个结点 current=current-next; counter+; return counter; / 返回表长值 ,print_list()函数用于打印整个链表中的所有数据元素,void print_list() /顺次打印输出链表中所有元素 NODE *current; current=head; while(current) /链表不空就循环 printf(“%f ”,current-data); /显示当前结点值 current=current-next; /指向下一个结点值 printf(“n”); ,测试插入函数和删除函数的main()函数,void main() int i; /从链表头连续插入5个元素