算法与数据结构复习重点ppt课件.ppt

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

1、一、绪论（一）数据结构的研究对象：数据结构的研究对象包括：数据的各种逻辑结构和存储结构以及对数据的各种操作。（二）算法的五个特征：有穷性、确定性、可行性、输入、输出。（三）算法的时间复杂度：T(n)=O(f(n))T（n）叫算法的渐进时间复杂度，简称时间复杂度，O为数量级。10/6/20211习题：1、写出下列算法的时间复杂度。（1）for(i=0;i

2、括（数据的各种逻辑结构和存储结构以及对数据的各种操作）。3、从逻辑上可以把数据结构分为（线性结构）和（非线性结构）两种类型。10/6/20212二、线性表（一）顺序表：10/6/20213顺序表的存储结构：#defineMaxsizemaxlentypedefintelemtype;typedefstruct{elemtypev[Maxsize];intlen;}sqlist;10/6/20214习题：给出顺序表的结构定义，在顺序表List中元素数组下标位置i插入一个元素x。#defineMAX

3、SIZE100structlist//顺序表结构{intv[MAXSIZE];//元素数组intlen;//顺序表当前包含的元素个数};typedefstructlistList;intinsert(List*L,inti,intx){//略}10/6/20215（二）单链表每个结点包括两个域:数据域、指针域。单链表存储结构：typedefstructnode{elemtypedata;structnode*next;}Lnode，*linklist;10/6/20216习题：给出单链表的结构定

4、义，编写函数实现链表的插入和删除操作。structlinknode//单链表结点结构{intdata;//结点数据structlinknode*next;//后继结点指针};typedefstructlinknodeLnode;（1）在结点p之后插入值为x的新节点svoidinsert(Lnode*p,intx;){}（2）将结点p的后继结点删除，并释放结点空间voiddelete(Lnode*p){}10/6/20217（三）单循环链表：使单链表的最后一个节点的指针域的值不为NULL,而是指向

5、头结点。这样，整个链表就形成了一个环，这种链表称为单循环链表。10/6/20218习题：1．线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D     ）。A）必须是连续的       B）部分地址必须是连续的C）一定是不连续的     D）连续或不连续都可以2．链表不具备的特点是（B）。A）插入和删除不需要移动元素B）可随机访问任一节点C）不必预分配空间D）所需空间与其长度成正比10/6/202193.不带头结点的单链表head为空的判定条件是（A）。A）head==NULLB）he

6、ad—>next==NULLC）head—>next==headD）head!=NULL4．带头结点的单链表head为空的判定条件是（B）。A）head==NULLB）head—>next==NULLC）head—>next==headD）head!=NULL5．带头结点的循环单链表head为空的判定条件是（C）。A）head==NULLB）head—>next==NULLC）head—>next==headD）head!=NULL10/6/2021106．在单链表中，指针p指向元素为x的结点，

7、实现“删除x的后继”的语句是(   B   )。A）p=p->next;          B）p->next=p->next->next;C）p->next=p;          D）p=p->next->next;7．在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为___n-i+1______。10/6/202111三、栈和队列（一）栈栈(Stack)是限制仅在表的一端进行插入和删除操作的线性表。栈又称为后进先出的线性表，简称LIFO线性表。顺序栈的顺序存储

8、结构：#definemaxsize100//栈的最大容量typedefstruct{elemtpelem[maxsize];inttop;}sqstacktp;10/6/202112（二）队列队列（queue)是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。队尾(rear)——允许插入的一端；队头(front)——允许删除的一端。队列特点：先进先出(FIFO)或后进后出(LILO)。10/6/202113顺序队列的存储结构：#definemaxsize100typedefstruct