数据结构C语言版课件.ppt

数据结构 C语言版 第0章　指导思想和目标 第1章　绪 论 小结 本章的重点是了解数据结构的逻辑结构、存储结构、数据的运算三方面的概念及相互关系，难点是算法复杂度的分析方法。 需要达到识记层次的基本概念和术语有：数据、数据元素、数据项、数据结构。特别是数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。数据结构的两大类逻辑结构和四种常用的存储表示方法。 需要达到领会层次的内容有算法、算法的时间复杂度和空间复杂度、最坏的和平均时间复杂度等概念，算法描述和算法分析的方法、对一般的算法要能分析出时间复杂度。 对基本概念的理解 数据 数据元素 数据结构 　　例如一个表（数据库） 逻辑结构： 　　线性结构和非线性结构 存储方法： 　　顺序存储方法，链接存储方法，索引存储方法，散列存储方法 难点问题： 　　算法的描述和分析，主要是算法复杂度的分析 习 题 一 1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 1.3 常用的存储表示方法有哪几种? 1.4 设有两个算法在同一机器上运行，其执行时间分别为100n^2和2^n,要使前者快于后者，n至少要多大? 1.5 按增长率由小至大的顺序排列下列各函数： 2^100, (2/3)^n，(3/2)^n， n^n , , n! ，2^n ，lgn ,n^lgn, n^(3/2) 数据结构 C语言版 内 容 2.1 线性表的定义 2.2 基于抽象数据类型线性表的操作 2.3 线性表的存储结构 2.4 基于顺序存储结构的线性表操作算法 2.5 基于链式存储的线性表操作算法 2.6 循环链表的操作算法 2.7 双向链表的操作算法 2.8 顺序存储线性表与链式存储线性表的比较 2.9 一元多项式的表示及相加 第2章　线性表 循环链表的操作与单链表的差别 循环链表的操作与单链表基本一致，差别仅在于算法中的循环条件不是P或 P－netx 是否为空，而是它们是否等于头指针。 1.在双向链表中插入节点 Status ListInsert_Dul(DuLinkList L,int i,ElemType e){??????//在带头结点的双链循环线性表L中第i个位置之前插入元素e,i的合法值为1≤i≤表长+1。??????if (!(p=GetElemp_DuL(L,i))) //在L中确定第i个元素的位置指针p????????return ERROR; //p=NULL,即第i个元素不存在??????if(!(s=(DuLinkList) malloc (sizeof (DuLNode)))) return ERROR;??????s-data=e;??????s-prior=p-prior; p-prior-next=s;??????s-next=p; p-prior=s;??????return OK;????}//ListInsert_DuL 2.在双向链表中删除节点 Status ListDelete_Dul(DuLinkList L,int i,ElemType e){??????//删除带头结点的双链循环线性表L中第i个元素，i的合法值为1≤i≤表长。??????if (!(p=GetElemp_DuL(L,i))) //在L中确定第i个元素的位置指针p????????return ERROR;??????e=p-data;??????p-prior-next=p-next;??????p-next-prior=p-prior;??????free(p); return OK;????}//ListDelete_DuL 两个多项式的相加操作算法 　　　根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应指数相加，若其和不为零，则构成和多项式中的一项；对于两个一元多项式中所有指数不相同的项，则分别复抄到和多项式中去。????在此，和多项式链表中的结点无需另生成，而应该从两个多项式的链表中摘取。其运算规则如下：假设指针qa和qb分别指向多项式A和多项式B当前进行比较的某个结点，则比较两个结点中的指数项，有下列三种情况： ????1）指针qa所指结点的指数值＜指针qb所指结点的指数值，则应摘取指针qa所指结点插入到和多项式链表中去；????2）指针qa所指结点的指数值＞指针qb所指结点的指数值，则应摘取指针qb所指结点插入到和多项式链表中去；????3）指针qa所指结点的指数值＝指针qb所指结点的指数值，则将两个结点中的系数