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

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

《数据结构之顺序表精选.pptx》由会员分享，可在线阅读，更多相关《数据结构之顺序表精选.pptx（25页珍藏版）》请在冰点文库上搜索。

第二章线性结构1SCIE,UniversityofElectronicScienceandTechnologyofChina线性表堆栈队列串二维数组2.1线性表2SCIE,UniversityofElectronicScienceandTechnologyofChina线性表的定义线性表是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马二802.1线性表逻辑结构：

元素及元素之间的关系为线性；1有且仅有一个开始节点（该节点只有一个直接后继节点，没有直接前趋节点）2有且仅有一个结束节点（该节点只有一个直接前趋节点，没有直接后继节点）3其余节点有且仅有一个直接前趋和一个直接后继3SCIE,UniversityofElectronicScienceandTechnologyofChina2.1线性表线性表不同的实现方式：

数组存储链接存储1.顺序表顺序表定义顺序表基本操作：

遍历、插入、删除顺序表算法分析2.单链表3.双向链表4.循环链表4SCIE,UniversityofElectronicScienceandTechnologyofChina2.1.1顺序表一、定义采用顺序存储结构的线性表通常称为顺序表用一组地址连续的存储单元依次存储线性表的数据元素。

内存5SCIE,UniversityofElectronicScienceandTechnologyofChina元素序号12ina1a2aian实现逻辑上相邻物理地址相邻随机存取存储地址Loc（a1）Loc（a1）+kLoc（a1）+（i-1）*kLoc（a1）+（n-1）*k特点：

2.1.1顺序表6SCIE,UniversityofElectronicScienceandTechnologyofChina可以借助于高级程序设计语言中的数组来表示：

数组的下标与元素在线性表中的序号相对应。

顺序表说明：

typedefstructlist_typeelemtypedataMAXNUM;intlength;list_type;list_typelist;问题:

如何获得第i的数据元素？

list.datai0ilength2.1.1顺序表7SCIE,UniversityofElectronicScienceandTechnologyofChina二、顺序表的基本操作遍历（查询）插入删除2.1.1顺序表8SCIE,UniversityofElectronicScienceandTechnologyofChina遍历运算问题描述在第1个元素到第length个元素依次取值a1a2aian2.1.1顺序表9SCIE,UniversityofElectronicScienceandTechnologyofChinatable.dataitypedefstructlist_typeelemtypedataMAXNUM;intlength;list_type;list_typetable;。

for（i=0;itable.length;i+）2.1.1顺序表插入运算问题描述在第i个元素前插入一个新元素new_node。

aiana1a2a1a2ai-1ai-1ai+1naewnodieai+1an逐个向后挪动10SCIE,UniversityofElectronicScienceandTechnologyofChina2.1.1顺序表从ai开始逐个向后，每个元素向后移动a1a2ai-1aiaai+i1.a.i.ania1a2ai-1i+1aaanfor（j=i;j=i;j-）table.dataj+1=table.dataj;newnodie11SCIE,UniversityofElectronicScienceandTechnologyofChina2.1.1顺序表12SCIE,UniversityofElectronicScienceandTechnologyofChina算法voidinsert（table,new_node,location）输入：

table:

指向线性表的指针new_node：

需要插入的元素location：

插入的位置，在其之前插入输出table：

线性表指针；;2.1.1顺序表13SCIE,UniversityofElectronicScienceandTechnologyofChina算法voidinsert（table,new_node,location）搬动节点，腾空位置在腾空的位置处，放入新的元素数组长度因为增加了一个新元素而加一;2.1.1顺序表14SCIE,UniversityofElectronicScienceandTechnologyofChinavoidinsert（table,new_node,location）locationlocation1;if（table-length=MAXNUM）error

（1）;elseif（locationtable-length）error

（2）;elsefor（j=table-length-1;j=location;j-）table-dataj+1=table-dataj;table-datalocation=new_node;table-length=table-length+1;2.1.1顺序表15SCIE,UniversityofElectronicScienceandTechnologyofChinavoiderror（intnumber）switch（number）case1:

printf（“thetableisfull”）;break;case2:

printf（“cantinsertatlocation”）;break;default:

printf（“unknownerror”）;2.1.1顺序表删除运算问题描述：

删除第i个元素算法实现分析ana1a2ai1aia1a2ai1aiai+1anai+116SCIE,UniversityofElectronicScienceandTechnologyofChina删除算法是否与插入算法一样有个方向和过程的问题？

172.1.1顺序表关键技术分析从an开始逐个向前，每个元素向前移动a1ana2ai-1anananfor（j=table.length;ji;j-）table.dataj-1=table.dataj;从ai1开始逐个向后，每个元素向前移动a1a2ai-1aiai+1anfor（j=i;jlength=table-length-1;voiddelete（table,location）locationlocation1;if（table-length1）error（3）;elseif（locationtable-length）error（4）;elsefor（j=location;jlength-1;j+）table-dataj=table-dataj+1;2.1.1顺序表21SCIE,UniversityofElectronicScienceandTechnologyofChinavoiderror（intnumber）switch（number）case1:

printf（“thetableisfull”）;break;case2:

printf（“cantinsertatlocation”）;break;case3:

printf（“thetableisempty”）;break;default:

printf（“unknownerror”）;2.1.1顺序表22SCIE,UniversityofElectronicScienceandTechnologyofChina编写算法的一般步骤：

1、分析问题描述输入，输出及模块功能等2、分析算法实现的总体框架，关键问题的突破方法3、核心算法的实现4、算法补充完善，如：

增加算法有效性的保护措施越界判断等2.1.1顺序表23SCIE,UniversityofElectronicScienceandTechnologyofChina算法效率数组顺序存储结构的特点元素随机获取特性。

存取时间短，存取时间与位置无关算法效率（时间复杂度）：

O

（1）元素更动的搬移性平均N/2次的搬移O（n）2.1.1顺序表a1a2ai-1aiai+1an平均搬移节点个数为NNNNN111N1（N-1）1（N-2）1（N-3）+NN211N（N+1）=（N（N-1）（N-2）1）=.N/224SCIE,UniversityofElectronicScienceandTechnologyofChina例：

设线性表的元素个数为N，请计算插入一个节点需要移动的节点的平均个数？

观察：

在表首插入一个节点，需要搬移的节点个数为N在a1后插入一个节点，需要搬移的节点个数为N-1在ai处插入一个节点，则需要搬移的节点个数为N-i在各处插入节点的概率为1/N2.1.1顺序表25SCIE,UniversityofElectronicScienceandTechnologyofChina作业：

教材P74第9题