数据结构之顺序表.ppt
SCIE,University of Electronic Science and Technology of China1第二章第二章 线性结构线性结构n线性表n堆栈n队列n串n二维数组SCIE,University of Electronic Science and Technology of China22.12.1线性表线性表n线性表的定义 线性表是n个相同类型数据元素的有限线性序列，通常记为（a1,a2,a3,an）。线性表特点：各元素数据类型必须相同数据ai可以是数字、字符和记录等 例1(1,1,2,3,5,8,13);例2(Sun，Mon，The，wed，Thu，Fri，Sat）例3 学生成绩表学号姓名成绩001丁一87002马二80SCIE,University of Electronic Science and Technology of China32.12.1线性表线性表逻辑结构：元素及元素之间的关系为线性；（1）有且仅有一个开始节点（该节点只有一个直接后继节点，没有直接前趋节点）（2）有且仅有一个结束节点（该节点只有一个直接前趋节点，没有直接后继节点）（3）其余节点有且仅有一个直接前趋和一个直接后继SCIE,University of Electronic Science and Technology of China42.12.1线性表线性表线性表不同的实现方式：2.1.1顺序表 数组存储 顺序表定义 顺序表基本操作：遍历、插入、删除 顺序表算法分析2.1.2单链表2.1.3双向链表 链接存储2.1.4循环链表SCIE,University of Electronic Science and Technology of China52.1.12.1.1顺序表顺序表 一、定义 采用顺序存储结构的线性表通常称为顺序表 用一组地址连续的存储单元依次存储线性表的数据元素。内存存储地址元素序号12ina1a2aian特点特点：实现逻辑上相邻物理地址相邻 随机存取Loc(a1)Loc(a1)+kLoc(a1)+(i-1)*kLoc(a1)+(n-1)*kSCIE,University of Electronic Science and Technology of China62.1.12.1.1顺序表顺序表 可以借助于高级程序设计语言中的数组来表示：数组的下标与元素在线性表中的序号相对应。顺序表说明：typedef struct list_typeelemtype data MAXNUM;int length;list_type;list_type list;问题:如何获得第i的数据元素？list.datai 0i lengthSCIE,University of Electronic Science and Technology of China72.1.12.1.1顺序表顺序表n二、顺序表的基本操作p遍历（查询）p插入p删除pSCIE,University of Electronic Science and Technology of China82.1.12.1.1顺序表顺序表n遍历运算p问题描述在第1个元素到第length个元素依次取值a1 a2 ai anSCIE,University of Electronic Science and Technology of ChinaSCIE,University of Electronic Science and Technology of China9 92.1.12.1.1顺序表顺序表for(i=0;i table.length;i+)for(i=0;i table.length;i+)typedef struct list_typeelemtype data MAXNUM;int length;list_type;list_type table;table.data i。SCIE,University of Electronic Science and Technology of China102.1.12.1.1顺序表顺序表n插入运算p问题描述在第i个元素前插入一个新元素new_node。a1a2ai-1aiana1a2ai-1newnodeai+1aianai+1逐个向后挪动SCIE,University of Electronic Science and Technology of China112.1.12.1.1顺序表顺序表n从ai开始逐个向后，每个元素向后移动n从an开始逐个向前，每个元素向后移一格a1a2ai-1aiai+1.anaiaiaiaia1a2ai-1aiai+1ananai+1aifor(j=i;j=i;j-)table.data j+1 =table.data j;newnodeSCIE,University of Electronic Science and Technology of China122.1.12.1.1顺序表顺序表n算法p输入：table:指向线性表的指针new_node：需要插入的元素location：插入的位置，在其之前插入p输出table：线性表指针void insert(table,new_node,location)；;SCIE,University of Electronic Science and Technology of China132.1.12.1.1顺序表顺序表n算法搬动节点，腾空位置在腾空的位置处，放入新的元素数组长度因为增加了一个新元素而加一void insert(table,new_node,location);SCIE,University of Electronic Science and Technology of China142.1.12.1.1顺序表顺序表void insert(table,new_node,location)for(j=table-length-1;j=location;j-)table-data j+1 =table-data j;table-data location =new_node;table-length=table-length+1;if(table-length=MAXNUM)error(1);elseif(locationtable-length)error(2);else location location 1;SCIE,University of Electronic Science and Technology of China152.1.12.1.1顺序表顺序表void 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”);SCIE,University of Electronic Science and Technology of China162.1.12.1.1顺序表顺序表anain删除运算p问题描述：删除第i个元素p算法实现分析a1a2aianai1a1a2ai1ai+1ananai+1删除算法是否与插入算法一样有个方向和过程的问题？SCIE,University of Electronic Science and Technology of China172.1.12.1.1顺序表顺序表for(j=i;j i;j-)table.data j-1 =table.data j;n关键技术分析p从an开始逐个向前，每个元素向前移动p从ai1开始逐个向后，每个元素向前移动a1a2ai+1aianai-1anananfor(j=table.length-1;j i;j-)table.data j-1 =table.data j;a1a2ai-1aiai+1 anfor(j=i;j table.length-1;j+)table.data j =table.data j+1;SCIE,University of Electronic Science and Technology of China182.1.12.1.1顺序表顺序表n算法p输入table：线性表指针location：需要删除的节点位置p输出table：线性表指针void delete(table,location)SCIE,University of Electronic Science and Technology of China192.1.12.1.1顺序表顺序表n算法1、从ai节点开始，向后逐个向前搬动节点，挤掉第i个元素2、数组长度因为减少了一个新元素而减一void delete(table,location)SCIE,University of Electronic Science and Technology of China202.1.12.1.1顺序表顺序表void delete(table,location)for(j =location;j length-1;j+)table-length=table-length-1;if(table-length 1)error(3);elseif(location table-length)error(4);else location location 1;table-data j =table-data j+1;SCIE,University of Electronic Science and Technology of China212.1.12.1.1顺序表顺序表void error(int number)switch(number)case 1:printf(“the table is full”);break;case 2:printf(“cant insert at location”);break;case 3:printf(“the table is empty”);break;default:printf(“unknown error”);SCIE,University of Electronic Science and Technology of China222.1.12.1.1顺序表顺序表编写算法的一般步骤：1、分析问题描述输入，输出及模块功能等2、分析算法实现的总体框架，关键问题的突破方法3、核心算法的实现4、算法补充完善，如：增加算法有效性的保护措施越界判断等SCIE,University of Electronic Science and Technology of China232.1.12.1.1顺序表顺序表数组顺序存储结构的特点元素随机获取特性。存取时间短，存取时间与位置无关算法效率（时间复杂度）：元素更动的搬移性平均N/2次的搬移 算法效率O(1)O(n)SCIE,University of Electronic Science and Technology of China242.1.12.1.1顺序表顺序表例：设线性表的元素个数为N，请计算插入一个节点需要移动的节点的平均个数？观察：在表首插入一个节点，需要搬移的节点个数为在ai处插入一个节点，则需要搬移的节点个数为a1a2ai-1aianai+1在a1后插入一个节点，需要搬移的节点个数为在各处插入节点的概率为平均搬移节点个数为N1NN1(N-1)N1(N-2)N1(N-3)N11+N1(N(N-1)(N-2)=1)=N12N(N+1).N/2NN-1N-i1/NSCIE,University of Electronic Science and Technology of China252.1.12.1.1顺序表顺序表作业：教材P74第9题
