2013考研数据结构辅导

《2013考研数据结构辅导》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、个人收集整理仅供参考学习第一章绪论掌握基本概念1、元素：数据基本单位。2、逻辑结构定义：元素及关系，与计算机无关，只是实际问题的数学抽象表示。分类：集合、线性结构、树、图3、存储结构定义：逻辑结构在计算机中的表示（内存）分类：顺序存储（数组）、链式存储（链表）4、算法及效率常见的基础算法定义：（计算机）解决问题的有限步骤效率度量：时间复杂度、空间复杂度第二章线性表第一节线性表逻辑结构1、定义：由n（n>=0）个元素组成的有限序列。n为0，空表，n>0时，Lists=(a1,a2,…an),ai称为元素，称为序偶，或前驱和后继关

2、系个人收集整理仅供参考学习1、操作：插入、删除、排序、查找等第二节顺序表1、定义：用物理地址连续的一段内存存储线性表中逻辑相邻的元素，这种存储结构称为顺序表。2、C++的存储实现constintMaxSize=100;//表示表中存储元素的最大值Tdata[MaxSize];//数组data用来存储元素，以整型为例intlength;//length值记录表data中存储元素的实际个数3、操作（常见算法）1）插入：已知表中length个元素已经存在，实现在表的i位置插入x算法基本思想：A）表满不插入B）位置i是否合法C）an，ai依次后移D）x

3、插入E）n值加1算法实现：C++描述（函数）templatvoidList::Insert（inti，intx）{intj；个人收集整理仅供参考学习if（length>=MaxSize）throw“表满，不能插入”；if(i<1

4、

5、i>length+1)throw“插入位置不合法”；for(j=length-1;j>=i-1;j--)data[j+1]=data[j];//元素后移r[i]=x;//元素插入length++;//表长增1}算法效率：表长为n的顺序表，i位置插入数据，需要（n-i+1）个元素后移等概率插入条件

6、下，平均移动元素的次数=∑PiMi=1/(n+1)(n+(n-1)+…1+0)=n/2即：算法的平均时间复杂度为O(n);1）删除：已知表中n个元素已经存在，实现在表的i位置删除略3）逆置：将表中元素反向存储templatevoidList::Reverse（）{intlow,high;low=0;high=length-1;while(low

7、、定义：用物理（内存）地址任意的存储单元存储逻辑相邻的元素，元素间的逻辑关系通过各个结点的指针信息来体现。2、C++存储实现（以单向链表为例）结点结构如下(C++结构类型)：datanext其中data存储元素信息，next存储逻辑关系的后继结点地址个人收集整理仅供参考学习非空表firsta1a2an∧//空表first∧除特殊说明外，一般均以带头结点的链表为例实现相关操作，算法设计简单first为头指针，用来指示头结点地址。结点（结构类型）的C++描述：templatestructNode{Tdata；//data存储元素信息

8、Node*next；//next存储逻辑关系的后继结点地址};1、算法设计举例1）链表的遍历：按逻辑次序依次输出表中元素templatevoidLinkList::Visit(){Node*p;p=first->next;while(p!=NULL)个人收集整理仅供参考学习{cout<data<<“”;p=p->next;}}1）链表插入(在非递增有序表中插入元素x，使序列仍然有序)算法基本思想：a）查找插入位置*p（在其后插入）b）插入xtemplatevoidLinkList:

9、:Insert(Tx){Node*p,*s;p=first;while(p->next&&p->next->data>=x)p=p->next;//查找插入位置s=newNode;//为x元素申请结点空间s->data=x;s->next=p->next;//在结点*p后插入结点*sp->next=s;}引申：有序链表的构造(删除)个人收集整理仅供参考学习templatevoidLinkList::Create(){intn=10;for(inti=1;i<=n;i++){intx;cout<<“输入元素”；c

10、in>>x;Insert(x);}}1）逆置算法：将表中元素逆序存储templatevoidLinkList::Reverse(