数据结构c语言版复习提纲及重点ppt课件.ppt

《数据结构c语言版复习提纲及重点ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构DataStructures2关于考试考题形式：选择题（20%）简答题（60%）算法题（20%）课程成绩：期末考试成绩占70%，平时成绩占30%平时成绩由作业、考勤、程序验收和实验报告组成。3第一章绪论本章内容：1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法的概念及5个重要特性1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求4第一章绪论本章学习要点：熟悉各名词、术语的含义，理解逻辑结构和存储结构（物理结构）概念。理解算法五个重要特性的确切含义。掌握计算语句频度和估算算法时间复杂度

2、的基本方法。5例题数据结构中的逻辑结构是指()，物理结构是指（　）。算法的基本特征包括有穷性、()、()、有输入和输出。算法的有穷性是指（　）。算法的确定性是指（　）。算法的可行性是指（　）。算法分析的两个主要内容是分析算法的（　）和空间复杂度。6例题语句频度是指（　）。设n为正整数，对下面的程序段，写出语句①、②、③的频度及该程序段的时间复杂度。for(i=1;i<=n;i++){s=0;①nfor(j=1;j<=n;j++)s=s+i×j;②n2if(s%2)③nprint(s);}7第二章线性表本章内容：2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的

3、链式表示与实现2.3.1线性链表2.3.2循环链表2.3.3双向链表2.4一元多项式的表示及相加8第二章线性表本章学习要点：线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储和链式存储，分别称为顺序表和链表（单向链表、双向链表和循环链表）。掌握线性表的基本操作（查找、插入、删除）在顺序表和链表上的具体实现方法。能够从时间和空间复杂度综合比较顺序表和链表的不同特点及其适用场合。第二章线性表本章内容：2.1线性表的基本概念2.2线性表的顺序存储结构2.3线性表的链式存储结构2.4双向链表2.5链表的应用一个线性表是有n个数据元

4、素的有限序列：(a1，a2，…，ai，…，an)线性表的顺序存储指用一组地址连续的存储单元依次存储线性表的数据元素。这称为顺序表。特点：存储单元地址连续（需要一段连续空间）逻辑上相邻的数据元素其物理位置也相邻存储密度大（100%）随机存取，元素的存储位置存在如下关系：Loc(ai)=Loc(a1)+(i-1)*d(1≤i≤n)a1a2...aian...d10线性表的顺序表示----顺序表L.elem[0]L.elem[1]qpL.elem[i]L.elem[i-1]L.elem[L.length-1]a1a2aiai+1an……p+1L.elem线性表L：(a1,a2,…

5、,ai-1,ai,ai+1,…,an)typedefstruct{ElemType*elem;//存储空间首地址intlength;//表长(元素个数)intlistsize;//存储容量}SqList；//顺序表类型第二章线性表本章内容：2.1线性表的基本概念2.2线性表的顺序存储结构2.3线性表的链式存储结构2.4双向链表2.5链表的应用线性表的链式存储指用任意的存储单元存放线性表中的元素，每个元素与其直接前驱和（或）直接后继之间的关系用指针来表示。这称为链表。单链表示意图a1a2ai-1…aiai+1an^…head头指针头结点首元结点第二章线性表单链表示意图a1a2

6、ai-1…aiai+1an^…head头指针头结点首元结点头指针是指向链表第一个结点的指针。头结点是链表中的第一个结点但是头结点中不存放数据元素。线性表L：(a1,a2,…,ai-1,ai,ai+1,…,an)单链表、循环链表和双向链表（a）单链表示意图a1a2ai-1…aiai+1an^…head头指针头结点首元结点taila2a1anan-1…(b)循环单链表heada1∧a2an-1anai…∧（c）双向链表示意图…单链表、循环链表的类型定义（a）单链表示意图a1a2ai-1…aiai+1an^…head头指针头结点首元结点taila2a1anan-1…（b）循环单链

7、表typedefstructLNode{ElemTypedata;/*存储数据元素*/structLNode*next;/*指向后继结点*/}SLink,*LinkList;LinkListhead,tail;15例题顺序表中，逻辑上相邻的数据元素在物理位置上(也相邻)。线性表L=(a1,a2,...,an)采用顺序存储，假定在不同的n+1个位置上的插入概率相同，则插入一个新元素平均需要移动的元素个数是(n/2)。在一个长度为n的顺序表中,在第i个元素(1in)之前插入一个新元素时,需向后移动(n-i+1)个元