资源预览内容
第1页 / 共106页
第2页 / 共106页
第3页 / 共106页
第4页 / 共106页
第5页 / 共106页
第6页 / 共106页
第7页 / 共106页
第8页 / 共106页
第9页 / 共106页
第10页 / 共106页
亲,该文档总共106页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
1. 理解和掌握有关数据结构的相关概念; 2. 熟练掌握线形表存储结构和相关操作方法; 3. 掌握栈、队列、树数据结构的运算方法。,第一节 基本概念 第二节 线形表 第三节 栈、队列和数组 第四节 树结构,本 章 内 容,机械CAD/CAM课程教案,教学目的,第二章 机械CAD/CAM常用的数据结构,第 1 节 基本概念,1. 数据(data),是对客观事物的符号表示,是指所有能输入到计算 机内并被计算机处理的符号的总称。,2. 数据元素(data element),是数据的基本单位,是数据这个集合中相对独立的个体。,3. 数据的逻辑结构(The logical structure of the data),是指数据之间的逻辑关系。,表 学生成绩表,第 1 节 基本概念,4.数据的物理结构(The physical structure of the data ),是数据元素和它们之间的关系在计算机中的存储表示。 计算机处理信息的最小单位叫做位(bit),一个位表示一个二进制的数。 若干位的组合形成一个位串(string) 。用一个位串表示一个数据元素,称这样的位串为一个结点(node) 。,6. 数据运算(data operation),是指对数据进行的各种操作。,5. 数据类型(data type),是程序设计语言提供的变量类别。,7.数据结构(data structure),第 1 节 基本概念,是按某种逻辑结构组织起来,按一定的存储表示方式把组织好的数据存储到计算机中,并对之定义一系列操作运算的数据的集合。,第 2 节 线形表,线性表n(n0)个数据元素按前驱后继关系排成的有限序列。 同一表中的数据元素的类型必须相同; 除了第一个和最后一个数据元素外,每个数据元素有且只有一个直接前趋,有且只有一个直接后继;如工资表、学生名册。 线性表中数据元素的个数定义为线性表的长度。,线性表的顺序存储结构 顺序存储就是用一组连续的存储单元,按照数据元素的逻辑顺序依次存放。 假定每个数据元素占用L个存储单元,每个数据元素第1个单元的存储位置为该数据元素的存储位置,若第1个数据元素的存储化置为b,则第i个数据元素的存储位置为 Loc(ai)b十(i1)L,第 2 节 线形表,第 2 节 线形表,线性表的顺序存储结构 特点:1)有序性;2)均匀性。 操作:1)建表; 2)访问; 3)修改; 4)删除; 5)插入。,顺序表类型定义 #define ListSize 100 /表空间的大小可根据实际需要而定,这里假设为100 typedef int DataType; /DataType的类型可根据实际情况而定,这里假设为int typedef struct DataType dataListSize;/向量data用于存放表结点 int length;/当前的表长度 SeqList;,顺序表上实现的基本运算 (1)表的初始化 void InitList(SeqList *L) 顺序表的初始化即将表的长度置为0 L-length=0; (2)求表长 int ListLength(SeqList *L) 求表长只需返回L-length return L-length; (3)取表中第i个结点 DataType GetNode(L,i) 取表中第i个结点只需返回和L-datai-1即可 if (i L-length-1) Error(“position error“); return L-datai-1; ,线性表插入运算:,第 2 节 线形表,线性表的链式存储结构 特点:1)存储单元可以不连续、动态分配存储空间; 2)存储结点有两种域:数据域、指针域。 单向链表 双向链表 循环链表,单链表类型描述 typedef char DataType; /假设结点的数据域类型为字符 typedef struct node /结点类型定义 DataType data; /结点的数据域 struct node *next;/结点的指针域 ListNode; typedef ListNode *LinkList; ListNode *p; LinkList head;, 生成结点变量的标准函数 p=( ListNode *)malloc(sizeof(ListNode); /函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中 释放结点变量空间的标准函数 free(p);/释放p所指的结点变量空间 结点分量的访问 利用结点变量的名字*p访问结点分量 方法一:(*p).data和(*p).next 方法二:p-data和p-next 指针变量p和结点变量*p的关系 指针变量p的值结点地址 结点变量*p的值结点内容 (*p).data的值p指针所指结点的data域的值 (*p).next的值*p后继结点的地址 *(*p).next)*p后继结点,第 2 节 线形表,单向链表的操作 操作:1)建表; 2)访问; 3)修改; 4)删除; 5)插入。,第 2 节 线形表,建表,链表插入操作运算步骤:申请新结点存储空间;将待插入元素M存放在新增结点数据域;新增结点指针链接。,第 2 节 线形表,访问,第 2 节 线形表,查找 修改 删除 插入,第 2 节 线形表,双向链表,第 2 节 线形表,双向链表的操作 1)建表,第 2 节 线形表,建表,第 2 节 线形表,查找 修改 删除 插入,第 2 节 线形表,链式存储相对于顺序存储的特点: (1)删除或插入运算速度快,因为删除或插入运算过程中数据并不移动; (2)无需事先分配存储空间,以免有些空间不能充分利用; (3)表的容量易于扩充; (4)按逻辑顺序进行查找的速度慢; (5)比相等长度的顺序存储多占用作为指针域的存储空间。,线性表顺序存储与链式存储结构比较,顺序存储: 优点:结构均匀,便于数据元素访问和修改操作; 不足:删除插入大量数据元素需移动,运算效率低。 应用:多用于查找频繁、很少增删的场合。 链式存储: 优点:删除插入效率高,不需数据元素移动,不需 事先分配存储空间,存储空间利用充分。 不足:搜索效率低,需从头结点顺次搜寻。 应用多用于事先难以确定容量,频繁增、删场合。,第 3 节 栈、队列和数组,栈 栈的结构 (1)栈的逻辑结构 线形表:后进先出 (2)栈的存储结构 一般采用顺序存储结构,栈的定义 栈(Stack)是限制在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶(Top),另一端为栈底(Bottom).当表中没有元素时称为空栈。 假设栈S=(a1,a2,a3,an),则a1称为栈底元素,an为栈顶元素。栈中元素按a1,a2,a3,an的次序进栈,退栈的第一个元素应为栈顶元素。换句话说,栈的修改是按后进先出的原则进行的。因此,栈称为后进先出表(LIFO)。,栈:限定只能在表的一端进行插入和删除的特殊的线性表. 设栈s=(a1,a2,. . . ,ai,. . . ,an), 其中a1是栈底元素, an是栈顶元素。 栈顶(top):允许插入和删除的一端; 栈顶的当前位置由栈顶指针的位置指示器指示。 栈底(bottom):不允许插入和删除的一端。 进栈或入栈:栈的插入操作。 出栈或退栈:栈的删除操作。,栈的定义,空栈:没有元素的栈 栈的特性: 先进后出(LIFO),即只能在末端(栈顶)进行插、删的操作,栈的定义,栈中的几种基本操作: 1.设置空栈 初始化:initStack(S); 清空:emptyStack (S); 2.插入一个新的栈顶元素(进栈):push(S,x); 3.删除栈顶元素(出栈): pop(S); 4.读取栈顶元素:getTop(S); 5.判空栈:stackEmpty(S); 6.判满栈:stackFull(S); 7.显示栈中元素:stackTraverse(S);,第 3 节 栈、队列和数组,第 3 节 栈、队列和数组,第 3 节 栈、队列和数组,栈的存储结构,顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,一般用一维数组表示 必须附设一个位置指针top(栈顶指针)来动态地指示栈顶元素在顺序栈中的位置 链栈 采用链表作为存储结构实现的 必须设置一个栈顶指针永远指向栈顶,栈的表示和实现,一、顺序栈 栈的顺序存储结构简称为顺序栈,它 是运算受限的线性表。因此,可用数组来 实现顺序栈。因为栈底位置是固定不变的, 所以可以将栈底位置设置在数组的两端的 任何一个端点;栈顶位置是随着进栈和退 栈操作而变化的。,栈的表示和实现,需用一个整型变量top来指示当前栈顶的位 置,通常称top为栈顶指针。因此,顺序栈的 类型定义只需将顺序表的类型定义中的长度 属性改为top即可。,一、顺序栈,顺序栈的结构 #define Stack_Size 50 typedef struct StackElemType elemStack_Size; /*用一维数组存放自栈底到栈顶的数据元素*/ int top; /*附设一个位置指针top*/ SeqStack;,一、顺序栈,设S是SeqStack类型的指针变量。若栈底位置在向量的低端,即selem0是栈底元素. 那么: 进栈:stop加1;退栈:stop 减1; 空栈:stoptop =stacksize-1。 上溢:当栈满时再做进栈运算必定产生的空间溢出;下溢:当栈空时再做退栈运算产生的溢出。 上溢是一种出错状态,应该设法避免之;下溢则可能是正常现象,因为栈在程序中使用时,其初态或终态都是空栈,所以下溢常常用来作为程序控制转移的条件。,一、顺序栈,设数组S是一个顺序栈 栈S的最大容量stacksize=4 ,初始状态top=1,栈空,10进栈,30出栈,栈满,top=stacksize-1,进栈算法 #define Statck_Size 100 int Push(SeqStack *S, int x), if(S-top=Stack_Size1) return 0; S-top+; S-elemS-top=x; return(1); ,a2,a3,a4,9,8,7,6,5,4,3,2,1,a1,0,top,一、顺序栈,进栈算法 #define Statck_Size 100 int Push(SeqStack *S, int x), if(S-top=Stack_Size1) return(0); S-top+; S-elemS-top=x; return(1); ,a2,a3,a4,9,8,7,6,5,4,3,2,1,a1,0,top,一、顺序栈,进栈算法 #define Statck_Size 100 int Push(SeqStack *S, int x), if(S-top=Stack_Size1) return(0); S-top+; S-elemS-top=x; return(1); ,a2,a3,a4,9,8,7,6,5,4,3,2,1,a1,0,top,x,一、顺序栈,出栈算法: int pop(SeqStack *S, StackElementType *x), if(S-top= =1) printf(“stack empty”); return(0);
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号