线性表(余云)剖析.ppt

数 据 结 构 院(系): 信息工程学院 教 师: 余 云 第2章　线性表 教 学 目 标 教学内容 一、顺序表的类型定义 补充：C++中的参数传递 4）传地址方式－－数组名作参数 1. 初始化线性表L InitList(L) 2. 销毁线性表L DestoryList(L) 3. 清空线性表L ClearList(L) 4. 求线性表L的长度 ListLength(L) 5. 判断线性表L是否为空 IsEmpty(L) 6. 获取线性表L中的某个数据元素内容 GetElem(L,i,e) 7. 检索值为e的数据元素 LocateELem(L,e) 8. 在线性表L中插入一个数据元素 ListInsert(L,i,e) 9. 删除线性表L中第i个数据元素 ListDelete(L,i,e) 2.3.2 单链表基本操作的实现 【算法思想】 （1）生成新结点作头结点，用头指针L指向头结点。 （2）头结点的指针域置空。 【算法描述】 LinkList InitList_L(LinkList L){ L=new LNode; L-next=NULL;　　　　　 return L; } 1.初始化(构造一个空表 ) void DestroyList_L(LinkList L) { LinkList p; while(L) { p=L; L=L-next; delete p; } } 2.销毁 a 1 a n a 2 ... L p int ClearList(LinkList L){ // 将L重置为空表 LinkList p,q; p=L-next; //p指向第一个结点 while(p) //没到表尾 { q=p-next; delete p; p=q; } L-next=NULL; //头结点指针域为空 return 1; } 3.清空 a 1 a 2 ... a n L q p p p p p int ListLength_L(LinkList L){ //返回L中数据元素个数 LinkList p; p=L-next; //p指向第一个结点 int i=0; while(p){ //遍历单链表,统计结点数 i++; p=p-next; } return i; } 4.求表长 int ListEmpty(LinkList L){ //若L为空表，则返回1，否则返回0 if(L-next) //非空 return 0; else return 1; } 5. 判断表是否为空 按序号查找 按值查找 6. 查找 思考：链表里如何找到第i个元素？ 链表的查找：要从链表的头指针出发，顺着链域next逐个结点往下有哪些信誉好的足球投注网站，直至有哪些信誉好的足球投注网站到第i个结点为止。因此，链表不是随机存取结构 按序号查找 从第1个结点（L-next）顺链扫描，用指针p指向当前扫描到的结点，p初值p?=?L-next。 用j做计数器，累计当前扫描过的结点数，j初值为1。 当p指向扫描到的下一结点时，计数器j加1。 当j?=?i时，p所指的结点就是要找的第i个结点。 【算法思想】 按序号查找 6.获取线性表L中的某个数据元素的内容 LinkList GetElem_L(LinkList L,int i){ p=L-next; j=1; //初始化 while(pji) { //向后扫描，直到p指向第i个元素或p为空 p=p-next; ++j; } if(!p || ji) return NULL; //第i个元素不存在 return p; }//GetElem_L 按序号查找 【算法描述】 从第一个结点起，依次和e相比较。 如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”； 如果查遍整个链表都没有找到其值和e相等的元素，则返回“NULL”。 【算法思想】 按值查找 7.在线性表L中查找值为e的数据元素 LNode *L