数据结构之顺序表精选.pptx

1、第二章 线性结构1SCIE,University of Electronic Science and Technology of China线性表堆栈队列串二维数组2.1线性表2SCIE,University of Electronic Science and Technology of China线性表的定义线性表是n个相同类型数据元素的有限线性序列，通常记为（a1,a2,a3,an）。线性表特点：各元素数据类型必须相同数据ai可以是数字、字符和记录等例1(1,1,2,3,5,8,13);例2(Sun，Mon，The，wed，Thu，Fri，Sat）例3 学生成绩表学号姓名成绩001丁一87

2、002马二802.1线性表逻辑结构：元素及元素之间的关系为线性；1有且仅有一个开始节点（该节点只有一个直接后继节点，没有直接前趋节点）2有且仅有一个结束节点（该节点只有一个直接前趋节点，没有直接后继节点）3其余节点有且仅有一个直接前趋和一个直接后继3SCIE,University of Electronic Science and Technology of China2.1线性表线性表不同的实现方式：数组存储链接存储1.顺序表顺序表定义顺序表基本操作：遍历、插入、删除顺序表算法分析2.单链表3.双向链表4.循环链表4SCIE,University of Electronic Science

3、and Technology of China2.1.1顺序表一、定义采用顺序存储结构的线性表通常称为顺序表用一组地址连续的存储单元依次存储线性表的数据元素。内存5SCIE,University of Electronic Science and Technology of China元素序号12ina1a2aian实现逻辑上相邻物理地址相邻随机存取存储地址 Loc(a1)Loc(a1)+kLoc(a1)+(i-1)*kLoc(a1)+(n-1)*k特点：2.1.1顺序表6SCIE,University of Electronic Science and Technology of China

4、可以借助于高级程序设计语言中的数组来表示：数组的下标与元素在线性表中的序号相对应。顺序表说明：typedef struct list_typeelemtype data MAXNUM;int length;list_type;list_type list;问题:如何获得第i的数据元素？list.datai 0i length2.1.1顺序表7SCIE,University of Electronic Science and Technology of China二、顺序表的基本操作遍历（查询）插入删除2.1.1顺序表8SCIE,University of Electronic Science

5、and Technology of China遍历运算问题描述在第1个元素到第length个元素依次取值a1a2ai an2.1.1顺序表9SCIE,University of Electronic Science and Technology of Chinatable.data i typedef struct list_typeelemtype data MAXNUM;int length;list_type;list_type table;。for(i=0;i table.length;i+)2.1.1顺序表插入运算问题描述在第i个元素前插入一个新元素new_node。aiana1a2

6、a1a2ai-1ai-1ai+1naewnodieai+1 an逐个向后挪动10SCIE,University of Electronic Science and Technology of China2.1.1顺序表从ai开始逐个向后，每个元素向后移动a1a2ai-1aiaai+i1.a.i.an ia1a2ai-1i+1a aanfor(j=i;j=i;j-)table.data j+1 =table.data j;newnodie11SCIE,University of Electronic Science and Technology of China2.1.1顺序表12SCIE,Un

7、iversity of Electronic Science and Technology of China算法void insert(table,new_node,location)输入：table:指向线性表的指针 new_node：需要插入的元素 location：插入的位置，在其之前插入输出table：线性表指针；;2.1.1顺序表13SCIE,University of Electronic Science and Technology of China算法void insert(table,new_node,location)搬动节点，腾空位置在腾空的位置处，放入新的元素数组长度因

8、为增加了一个新元素而加一;2.1.1顺序表14SCIE,University of Electronic Science and Technology of Chinavoid insert(table,new_node,location)location location 1;if(table-length=MAXNUM)error(1);elseif(locationtable-length)error(2);elsefor(j=table-length-1;j=location;j-)table-data j+1 =table-data j;table-data location =ne

9、w_node;table-length=table-length+1;2.1.1顺序表15SCIE,University of Electronic Science and Technology of Chinavoid error(int number)switch(number)case 1:printf(“the table is full”);break;case 2:printf(“cant insert at location”);break;default:printf(“unknown error”);2.1.1顺序表删除运算问题描述：删除第i个元素算法实现分析ana1a2ai

10、1aia1a2ai1aiai+1anai+116SCIE,University of Electronic Science and Technology of China删除算法是否与插入算法一样有个方向和过程的问题？172.1.1顺序表关键技术分析从an开始逐个向前，每个元素向前移动a1ana2ai-1 an an anfor(j=table.length;ji;j-)table.data j-1 =table.data j;从 ai1开始逐个向后，每个元素向前移动a1a2 ai-1 ai ai+1 anfor(j=i;jlength=table-length-1;void delete(t

11、able,location)location location 1;if(table-length 1)error(3);elseif(location table-length)error(4);elsefor(j=location;j length-1;j+)table-data j =table-data j+1;2.1.1顺序表21SCIE,University of Electronic Science and Technology of Chinavoid error(int number)switch(number)case 1:printf(“the table is full

12、”);break;case 2:printf(“cant insert at location”);break;case 3:printf(“the table is empty”);break;default:printf(“unknown error”);2.1.1顺序表22SCIE,University of Electronic Science and Technology of China编写算法的一般步骤：1、分析问题描述输入，输出及模块功能等2、分析算法实现的总体框架，关键问题的突破方法3、核心算法的实现4、算法补充完善，如：增加算法有效性的保护措施越界判断等2.1.1顺序表23

13、SCIE,University of Electronic Science and Technology of China算法效率数组顺序存储结构的特点元素随机获取特性。存取时间短，存取时间与位置无关算法效率（时间复杂度）：O(1)元素更动的搬移性平均N/2次的搬移O(n)2.1.1顺序表a1a2ai-1aiai+1an平均搬移节点个数为N N N N N 111N1(N-1)1(N-2)1(N-3)+NN2 1 1N(N+1)=(N(N-1)(N-2)1)=.N/224SCIE,University of Electronic Science and Technology of China例：设线性表的元素个数为N，请计算插入一个节点需要移动的节点的平均个数？观察：在表首插入一个节点，需要搬移的节点个数为 N在a1后插入一个节点，需要搬移的节点个数为N-1在ai处插入一个节点，则需要搬移的节点个数为N-i在各处插入节点的概率为1/N2.1.1顺序表25SCIE,University of Electronic Science and Technology of China作业：教材P74第9题