数据结构线性表分析.ppt

* 4 双向链表删除一结点 a2 a2 a2 P ① ② ① p -＞ prior -＞ next=p -＞ next； ② p -＞ next -＞ prior=p -＞ prior； * 数据结构课程设计 名称：学生数据管理 内容：实现学生数据管理的如下功能 插入 删除 查找 显示 录入 存储 装入 修改 * 数据结构：线性表 数据对象：班或系的学生记录 学生记录： 学号 姓名 年龄 性别 家庭住址 入学时间 家庭电话号码 * 线性表 显示 存储 装入 修改 插入 删除 查找 录入 文件 键盘 数据控制与 数据流分析 * * 线性表是N个数据元素的有限序列构成 的一种线性结构。 线性表的形式定义： Linear--List=（D，R） D={a1，a2，……an} R={〈ａi-1，ai〉│i=2..n} n 称为线性表长度，n=0称空表； ai为数据元素。 * 线性表还可以逻辑地表示为： （a1，a2，……an） 线性表的特点： 唯一首元素； 唯一尾元素； 除首元素外，任何元素有一个前驱； 除尾元素外，任何元素有一个后继； 每个元素有一位序。 第二节 线性表的抽象类型定义 * 数据对象：D 数据关系：R 基本操作： Initlist（L) Destroylist （L) Clearlist （L) Listempty （ L) Listlength （L) Getelem(L,i,e) Locatelem(L,e) Priorelem(L,e,pe) Nextelem(L,e,ne) Listinset(L,i,e) Listdelete(L,i,e) Listtraverse(L) ADT　List { } ADT List 第三节 线性表的顺序表示和实现 * 一 顺序表示 用一组连续的存储单元依次存储线性表的数据元素。 设 b 为首地址 L为数据元素长度 a1 a2 an 空闲 b b+L b+（n-1）L b+（maxlen-1）L * 二 线性表的顺序结构实现 线性表由三个部分组成： 1）一组连续存储空间 2）当前长度 3）空间大小 用c 语言可描述为： elem[ ] length listsize * #define List-Init-Size 100 #define Listincrement 10 typedef struct { Elemtype *elem； int length； int listsize； } Sqlist； * 初始化一个线性表 Status Initlist_Sq(Sqlist L) { L.elem=分配List-Init-Size个空间; L.length=0; L.listsize= List-Init-Size; return OK; } * 线性表插入前后状况 77 42 30 24 28 21 13 12 插入25 77 42 30 28 24 25 21 13 12 下移一格 三 插入操作的算法实现 * Status Listinsert_Sq(Sqlist L,int i, Elemtype e) { if (i1‖i L.length+1) return ERROR; if (L.length=L.listsize) {newbase=追加分配新空间 L.elem=newbase; L.listsize+=Listincrement; } q=(L.elem[i-1]); for (p=(L.elem[L.length-1]);p=q;--p) *(p+1)=*p; *q=e; ++L.length; return OK; } * 线性表删除前后状况 77 42 30 24 28 21 13 12 删除24 77 42 28 30 21 13 12 上移一格 四 删除操作的算法实现 * Status Listdelete_Sq(Sqlist L,int i, Elemtype e) { if (i1‖i L.length) return ERROR; p=(L.elem[i-1]); e=*p; q=L.elem+L.length-1; for (++p;p=q;++p) *(p-1)=*p; --L.length; return OK; } * 五 算法分析 设在线性表第 i 个元素前插入一新元素的概率为 Pi，删除第 i 个元素的概率为