数据结构和算法简介ppt课件

.,线性表单链表,数据结构(C#语言版),.,目标,在本课程中，你将达到如下目标：认识线性表，了解线性表的逻辑结构和特点了解线性表的基本操作线性表的链式表示和实现,.,问题描述有一个学生成绩表，以升序的方式存储着N位学生的成绩，现需要编写一个学生成绩管理系统，实现如下的功能：对学生成绩表，实现插入、删除操作，并保证成绩按升序排列；可以按给定的姓名或学号查询指定学生的的信息；可以升序或降序显示所有学生的成绩。,问题引入学生成绩表的编程问题,.,认识线性表,线性表（linearlist）是由n（n0）个相同类型的数据元素（结点）a0,a1，,an-1组成的有限序列，一个有n个数据元素的线性表常常表示为（a0,a1，,an-1）。,1、线性表定义：,2、线性表特点：,有且仅有一个开始结点，没有直接前趋，而仅有一个直接后继a1有且仅有一个结束结点，没有直接后继，而仅有一个直接前趋。除了开始与结束结点外，其它结点都有且仅有一个直接前趋和直接后继。,.,线性表的基本操作,1、初始化操作：初始条件：线性表不存在操作结果：创建一个空的线性表2、插入操作：InsertNode(Ta,inti)初始条件：线性表存在，插入位置正确（1in+1,n为插入前的表长）操作结果：在线性表的第i个位置上插入一个值为a的新元素。3、删除操作：DeleteNode(inti)初始条件：线性表存在且不为空，删除位置正确（1in）。操作结果：在线性表中删除序号为i的数据元素。,.,4、取表元素：SearchNode(inti)初始条件：线性表存在，所取数据元素位置正确（1in）。操作结果：返回线性表中第i个数据元素。5、定位元素：SearchNode(Tvalue)初始条件：线性表存在操作结果：在线性表中查找值为value的数据元素。6、求表长度：GetLength()初始条件：线性表存在操作结果：返回线性表中所有数据元素的个数。7、清空操作：Clear()初始条件：线性表存在且有数据元素操作结果：从线性表中清除所有数据元素，线性表为空。8、判断线性表是否为空：IsEmpty()初始条件：线性表存在操作结果：如果线性表不包含任何数据元素则返回true，否则返回false。,线性表的基本操作,.,将上述操作定义在接口IlinearList中，代码如下：InterfaceIlinearListVoidInsertNode(Ta,inti);/插入操作VoidDeleteNode(inti);/删除操作TSearchNode(inti);/查找元素TSearchNode(Tvalue);/定位表元素IntGetLength();/求表长度VoidClear();/清空操作BoolIsEmpty();/判断表是否为空,线性表的基本操作,.,顺序存储结构用一组地址连续的存储单元依次存储线性表的数据元素。用物理位置来表示逻辑结构。用这种方法存储的线性表简称顺序表。,线性表的顺序表示和实现,顺序表的存储结构可以用C#语言中的一维数组来表示。,.,对顺序表的操作,1、初始化顺序表：步骤：初始化maxsize为实际值为数组申请可以存储maxsize个数据元素的存储空间，数据元素的类型由实际应用而定初始化length为02、插入操作：InsertNode(Ta,inti)步骤：若没有定指定插入位置，则将数据元素插入到顺序表的最末一个位置，指定插入位置i，若1ilength+1,则转入步骤2,否则无法插入。将第Length个至第i个存储位置上的元素依次后移，将新的元素置于i位置上。使顺序表长度length加13、删除操作：DeleteNode(inti)步骤：如果列表为空，或者不符合1ilength,则提示没有要删除的元素，否则转入步骤2。将第i+1到Length个元素依次前移。使顺序表长度length减1,.,利用顺序表，编程实现学生成绩的增加、删除、查询（按学号、姓名查询）、升序显示、降序显示。,独立实践,.,小结,线性表（linearlist）是由n（n0）个相同类型的数据元素（结点）组成的有限序列，有且仅有一个开始结点，开始结点没有直接前趋，仅有一个直接后继，有且仅有一个结束结点，结束结点没有直接后继，而仅有一个直接前趋。除了开始与结束结点