数据结构之顺序表

《数据结构之顺序表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、SCIE,UniversityofElectronicScienceandTechnologyofChina1第二章线性结构线性表堆栈队列串二维数组SCIE,UniversityofElectronicScienceandTechnologyofChina22.1线性表线性表的定义线性表是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马二80………S

2、CIE,UniversityofElectronicScienceandTechnologyofChina32.1线性表逻辑结构：元素及元素之间的关系为线性；（1）有且仅有一个开始节点（该节点只有一个直接后继节点，没有直接前趋节点）（2）有且仅有一个结束节点（该节点只有一个直接前趋节点，没有直接后继节点）（3）其余节点有且仅有一个直接前趋和一个直接后继SCIE,UniversityofElectronicScienceandTechnologyofChina42.1线性表线性表不同的实现方式：2.1.1顺序表数组存储顺序表定义顺序表基本操作：遍历、插入、删除顺序表算法分析2.1.2单链表2

3、.1.3双向链表链接存储2.1.4循环链表SCIE,UniversityofElectronicScienceandTechnologyofChina52.1.1顺序表一、定义采用顺序存储结构的线性表通常称为顺序表用一组地址连续的存储单元依次存储线性表的数据元素。内存存储地址元素序号12ina1a2…ai…an特点：实现逻辑上相邻—物理地址相邻随机存取Loc(a1)Loc(a1)+k…Loc(a1)+(i-1)*k…Loc(a1)+(n-1)*kSCIE,UniversityofElectronicScienceandTechnologyofChina62.1.1顺序表可以借助于高级程序设

4、计语言中的数组来表示：数组的下标与元素在线性表中的序号相对应。顺序表说明：typedefstructlist_type{elemtypedata[MAXNUM];intlength;}list_type;list_typelist;问题:如何获得第i的数据元素？list.data[i]0≤i≤lengthSCIE,UniversityofElectronicScienceandTechnologyofChina72.1.1顺序表二、顺序表的基本操作遍历（查询）插入删除……SCIE,UniversityofElectronicScienceandTechnologyofChina82.1.1

5、顺序表遍历运算问题描述在第1个元素到第length个元素依次取值a1a2…ai…anSCIE,UniversityofElectronicScienceandTechnologyofChina92.1.1顺序表for(i=0;i

6、问题描述在第i个元素前插入一个新元素new_node。a1a2ai-1aian……a1a2ai-1newnodeai+1ai……anai+1逐个向后挪动SCIE,UniversityofElectronicScienceandTechnologyofChina112.1.1顺序表从ai开始逐个向后，每个元素向后移动从an开始逐个向前，每个元素向后移一格a1a2ai-1aiai+1......anaiaiaiaia1a2ai-1aiai+1…anan…ai+1aifor(j=i;j<=table.length;j++){table.data[j+1]=table.data[j];}for(j

7、=table.length;j>=i;j--){table.data[j+1]=table.data[j];}newnodeSCIE,UniversityofElectronicScienceandTechnologyofChina122.1.1顺序表算法输入：table:指向线性表的指针new_node：需要插入的元素location：插入的位置，在其之前插入输出table：线性表指针voidinsert(table,