数据结构与算法Python语言描述学习教案.pptx

会计学内容提要(nèirónɡtíyào) 学生信息表
通讯录
短信、聊天记录
邮件列表
购物清单(qīngdān)
账单 线性表 ADTList{
数据(shùjù)对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

数据(shùjù)关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

基本操作：
InitList(&L)//初始化
操作结果：构造一个空的线性表L。

CreatList(&L,n)//创建
操作结果：构造一个含n个元素的线性表L。

DestroyList(&L)//结构销毁
初始条件：线性表L已存在。
操作结果：销毁线性表L。//引用型操作

ListLength(L)//求线性表的长度
初始条件：线性表L已存在(cúnzài)。
操作结果：返回L中元素个数。

ListEmpty(L)//判断线性表是否为空
初始条件：线性表L已存在(cúnzài)。
操作结果：若L不空，返回true，否则为false。

PriorElem(L,cur_e,&pre_e) //求数据元素的前驱
初始条件：线性表L已存在(cúnzài)。
操作结果：若cur_e是L的元素，但不是第一个，则用pre_e返回
它的前驱，否则操作失败，pre_e无定义。

NextElem(L,cur_e,&next_e) //求数据元素的后继
初始条件：线性表L已存在(cúnzài)。
操作结果：若cur_e是L的元素，但不是最后一个，则用next_e
返回它的后继，否则操作失败，next_e无定义。
GetElem(L,i,&e)//取线性表中第i个数据(shùjù)元素
初始条件：线性表L已存在，且1≤i≤LengthList(L)。
操作结果：用e返回L中第i个元素的值。

LocateElem(L,e,compare())//定位函数
初始条件：线性表L已存在，e为给定值，
compare()是元素判定函数。
操作结果：返回第1个与e满足compare关系的元素的位序。
若这样的元素不存在，则返回值为0。

ListTraverse(L,visit())//遍历线性表
初始条件：线性表L已存在，visit()为某个访问函数。
操作结果：依次对L的每个元素调用函数visit()。
一旦visit()失败，则操作失败。//加工型操作：&L!!!

ClearList(&L)//线性表置空
初始条件：线性表L已存在。
操作结果(jiēguǒ)：将L重置为空表

ListInsert(&L,i,e)//插入数据元素
初始条件：线性表L已存在，且1≤i≤LengthList(L)+1。
操作结果(jiēguǒ)：在L的第i个元素之前插入新的元素e，L的长度增1。

ListDelete(&L,i,&e)//删除数据元素
初始条件：线性表L已存在且非空，1≤i≤LengthList(L)。
操作结果(jiēguǒ)：删除L的第i个元素，并用e返回其值，L的长度减1。

}ADTList题目：假设利用两个线性表LA和LB分别(fēnbié)表示两个集合A和B，现要求一个新的集合A=A∪B。

方法：只要从LB中依次取出每个数据元素，并依值在LA中进行查访，若不存在，则插入。voidunionSet(List&La,ListLb){

La_len=ListLength(La);
Lb_len=ListLength(Lb);

for(i=1;i<=Lb_len;i++){
GetElem(Lb,i,e);
if(!LocateElem(La,e,EQUAL))
InsertList(La,++La_len,e);
}
}题目：已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并(guībìng)为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。

方法：设置两个指针分别指向LA和LB的当前元素，将数值较小的元素插入LC中。voidMergeList(ListLa,ListLb,List&Lc){
ClearList(Lc);//这里假定Lc已经做过InitList操作(cāozuò)， //ClearList之后表的空间还在！

i=j=1;k=0;
La_len=ListLength(La);Lb_len=ListLength(Lb);

while((i<=La_len)&&(j<=Lb_len)){
GetElem(La,i,ai);GetElem(Lb,j,bj);
if(ai<=bj){ListInsert(