考研数据结构考前辅导串讲.ppt

《考研数据结构考前辅导串讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构本课程的主要内容教材：严蔚敏吴伟民：数据结构（C语言版）清华大学出版社内容：1~10章中的主要内容第一章绪论逻辑结构（元素间关系）集合线性表栈队列树形结构图状结构物理结构（存储形式）顺序链式数据结构的基本概念数据结构包括三个方面：逻辑结构：数据之间的关系，不管数据在计算机中的存储方式存储结构：数据在计算机中的存储方式运算：定义在数据上的运算的集合算法设计与分析时间复杂度：一个语句的频度，是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n)，它是该算法所求问题规模n的函数当问题的规模趋于无穷大时，T(n

2、)的数量级称为渐进时间复杂度，简称为时间复杂度，记为T(n)=O(f(n))，表示T(n)的数量级空间复杂度：定义为算法所耗费的存储空间，它是问题规模n的函数。渐进空间复杂度简称为空间复杂度，记做S(n)=O(f(n))第二章线性表线性表顺序存储链式存储单链表循环链表双向链表顺序表示（1）一组地址连续的存储单元依次存放线性表中的元素,称顺序表。特点：逻辑上相邻，物理上也相邻。随机存取688970674078逻辑序号123456C数组下标012345陈述问题时用顺序表示（2）可以通过直接计算，得到每个元素的存储地址Loc(ai+1

3、)=Loc(ai)+lLoc(ai)=Loc(a1)+l*(i-1)其中：Loc(a1)称为线性表的起始位置或基地址。每个数据元素占用l个存储单元a1a2…ai………an12…i………naa+l…a+(i-1)*l………a+(n-1)*lidle顺序表示（3）基本操作的实现插入操作前提：分配的空间未满；插入位置合适（在表中适当的地方）在第I个位置插入一个元素三个步骤：将第I个数据元素至第N个元素依次后移一个位置将该元素插入在第I个位置修改表的长度1523461657106448插入e01234567i152346165710

4、6412345678948顺序表示（4）删除操作前提：表不空，且要删除的元素存在删除地I个元素的步骤将I+1至N元素依次前移一个位置修改表的长度152346165710641234567816删除e01234567i1523465710641234567顺序存储的插入操作的效率设线性表中有n个元素,在下标为i的元素之前插入元素的概率为pi在下标为i的元素之前插入一个元素需移动元n-i+1个元素，则插入一个元素所需的平均移动次数为：设每个位置上插入的概率相同顺序存储的删除操作的效率则删除一个元素所需的平均移动次数为：设

5、每个位置上删除的概率相同插入和删除算法的时间复杂度为O(n)线性链表（1）它包含两个域，一个表示数据本身，一个表示数据元素间的关联。这样一个整体称为一个结点。结点中表示关联的部分称为指针域，内部存放指针或链。结点：数据元素的存储映象，由数据域和指针域构成这里数据元素之间的逻辑关系是由结点中的指针表示的。n个结点链结成一个链表，即为线性表的链式存储结构。由于只有一个指针域，所以由称为线性链表或单链表。数据域指针域线性链表（2）单链表：typedefstructLNode{ElemTypedata;structLnode*next;

6、}Lnode,*LinkListHeada1La2a3a4a5线性链表（3）“第一个结点”问题：第一个结点加入时链表为空，它没有直接前驱结点，它的地址就是整个链表的指针，需要放在链表的头指针变量中；而其它结点有直接前驱结点，其地址放入直接前驱结点的指针域。头结点：为了方便操作，有时在链表的头部加入一个“头结点”，头结点的类型与数据结点一致，这样即使是空表，头指针变量L也不为空了。头结点的加入使得“第一个结点”的问题不再存在，也使得“空表”和“非空表”的处理成为一致。头结点的加入完全是为了运算的方便，它的数据域无定义，指针域中存

7、放的是第一个数据结点的地址，空表时为空。线性链表（4）插入操作：(1)后插结点：设p指向单链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的后面操作如下：①s->next=p->next;②p->next=s;注意：两个指针的操作顺序不能交换。线性链表（5）删除操作：设p指向单链表中某结点，删除*p。要实现对结点*p的删除，首先要找到*p的前驱结点*q，然后完成指针的操作即可。指针的操作由下列语句实现：q->next=p->next;free(p);若要删除*p的后继结点(假设存在)，则可以直接完成：s=p->nex

8、t;p->next=s->next;free(s);循环链表（1）优点：从循环链表中任一结点出发，都能访问遍所有结点。在单循环链表上的操作基本上与非循环链表相同，只是将原来判断指针是否为NULL变为是否是头指针而已，没有其它较大的变化。对于单链表只能从头结点开始