文档介绍：该【数据结构知识点整理(加算法) 】是由【莫比乌斯】上传分享，文档一共【29】页，该文档可以免费在线阅读，需要了解更多关于【数据结构知识点整理(加算法) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构考核知识点
数据计算机加工处理的对象
数据元素组成数据的基本单位
数据项 数据元素可由若干个数据项(dataitem)组成,数据项是数据的不可分割的最小单位
逻辑结构数据元素间的逻辑关系
存储结构 数据在计算机内的表示形式
数据结构 数据结构主要是为研究和解决如何使用计算机组织和处理这些非数值问题而产生的理论、技术和方法。,对数据元素间逻辑关系的描述称为数据的逻辑结构;数据必须在计算机内存储,数据的存储结构是数据结构的实现形式,是其在计算机内的表示;此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。
数据类型是程序设计语言中的概念,它是数据抽象的一种方式。一个数据类型定义了一个值的集合以及作用于该值集的运算集合。程序设计语言中,一个数据类型不仅规定了该类型的变量(或常量)的取值范围,还定义了该类型允许的运算。
数据抽象使程序设计者可以将数据元素间的逻辑关系和数据在计算机内的具体表示分别考虑。
过程抽象使程序设计者将一个运算的定义与实现运算的具体方法分开考虑。抽象的好处主要在于降低了问题求解的难度。
抽象数据类型(abstractdatatypeADT)是一个数据类型,其主要特征是该类型的对象及其运算的规范,与该类型对象的表示和运算的实现分离,实行封装和信息隐蔽,即所谓使用和实现分离
数据结构的规范数据结构被看成是一个类属抽象数据类型(ADT),用格式化的自然语言来描述。数据结构可以形式地用一个C++的抽象模板类描述
数据结构的实现
template<classT>
classSeqStack:publicStack<T>
{
public:
……
private:
inttop;//top记录最后入栈的元素在s的下标
intmaxTop;//最大栈顶指针
T*s;//s指向动态生成的一维数组,存放元素
};
template<classT>
SeqStack<T>::SeqStack(intmSize)
{
maxTop=mSize-1;//设置栈的容量值
s=newT[mSize];//生成存储栈的数组
top=-1;//top==-1表示空栈
}
算法描述笼统的说,算法是求解一类问题的任意一种特殊的方法。较严格的说法是一个算法是对特定问题的求解步骤的一种描述,它是指令的有限序列;此外,算法具有下列五个特征:
输入:算法有零个或多个输入
输出:算法至少产生一个输出
确定性:算法的每一条指令都有确切的定义,没有二义性。
能行性:算法的每一条指令都足够基本,它们可以通过已经实现的基本运算执行有限次来实现。
有穷性:算法必须总能在执行有限步之后终止。
算法分析
算法的性能标准
正确性:算法的执行结果应当满足预先规定的功能和性能要求。
简明性:一个算法应当思路清晰、层次分明、简单明了、易读易懂。
健壮性:当输入不合法数据时,应能做适当处理,不至于引起严重后果。
效率:有效使用存储空间,并有高的时间效率。
算法的时间复杂度是程序运行从开始到结束所需的时间
算法的空间复杂度一个算法的空间复杂度是指算法运行所需的存储量
线性表 线性表是n(³0)个元素a0,a1,…,an-1的线性序列,记为:(a0,a1,…,an-1)。其中n是线性表中元素的个数,称为线性表的长度;n=0时称为空表。ai是表中下标为i的元素(i=0,1,…,n-1),称ai是ai+1的直接前驱元素,ai+1是ai的直接后继元素。线性表是动态数据结构,它的表长可以改变。
顺序表 顺序表示的线性表称为顺序表
顺序表长度顺序表中数据的个数
顺序表在程序中的表示
template<classT>
classSeqList:publicLinearList<T>
{
public://公有函数
SeqList(intmSize);
~SeqList(){delete[]elements;}
boolFind(inti,T&x)const;
intSearch(Tx)const;
boolInsert(inti,Tx);
boolDelete(inti);
……
……
private://私有数据
intmaxLength; //顺序表的最大长度
T*elements; //动态一维数组的指针
};
顺序表插入算法
Insert(i,x):在表中下标为i的元素ai后插入x。
若i=-1,则将新元素x插在最前面。若插入成功,返回true;
顺序表删除算法
Delete(i):删除元素ai。
单向链表
a0
a1
非空单链表
template<classT>
classSingleList:publicLinearList<T>
{
public:
SingleList(){first=NULL;n=0;}
~SingleList();
boolFind(inti,T&x)const;
intSearch(Tx)const;
boolInsert(inti,Tx);
boolDelete(inti);
……
…….
private:
Node<T>*first;
};
双向链表
表头指针头指针也就是表头指针,是以确定线性表中第一个元素对应的存储位置,一般用于处理数组,链表,队列等数据结构。
表尾指针尾指针,指向最后一个元素。
表头结点
循环单向链表
循环双向链表
单向链表定位算法
必须从头指针开始沿链逐个计数查找,称为顺序查找
template<classT>
boolSingleList<T>::Find(inti,T&x)const
{//在(a0,a1,...,an−1)中找下标为i的元素ai
if(i<0||i>n−1){ //对i进行越界检查
cout<<"OutOfBounds";returnfalse;
}
Node<T>*p=first;
for(intj=0;j<i;j++)p=p->link;
x=p->element;returntrue;
}
单向链表插入算法
生成数据域为x的新结点,q指向新结点;
从first开始找第i+1个结点,p指向该结点;
将q插入p之后。
表长加1。
单向链表删除算法
1、从first开始找第i+1个结点,p指向该结点,q指向p之前驱结点;
2、从单链表中删除p;
3、释放p之空间;
4、表长减1
双向链表插入操作步骤
(1)DNode<T>*q=newDNode<T>;
q->element=x;
(2)q->lLink=p->lLink;q->rLink=p;
p->lLink->rLink=q;p->lLink=q;
双向链表删除操作步骤
(1)p->lLink->rLink=p->rLink;
p->rLink->lLink=p->lLink;
(2)deletep;
栈 是限定插入和删除运算只能在同一端进行的线性数据结构
队列限定只能在其中一端插入元素,而在另一端删除元素的线性数据结构。(动态数据结构)
栈顶栈底允许插入和删除元素的一端称为栈顶,另一端称为栈底。
队首队尾允许插入元素的一端称队尾,允许删除元素的另一端称队头。
顺序栈 栈的顺序存储结构称为顺序栈。顺序栈可以用一个一维数组和一个记录栈顶位置的整形变量来实现,数组用于顺序存储栈中所有的数据元素,栈顶指针用于存储栈顶元素的位置。
链接栈使用了链表来实现栈,链表中的元素存储在不连续的地址,由于是动态申请内存,所以我们可以以非常小的内存空间开始,另外当某个项不使用时也可将内存返还给系统
栈顶指针栈顶指针是在栈操作过程中,有一个专门的栈指针(习惯上称它为TOP),指出栈顶元素所在的位置
顺序栈在程序中的表示
/*定义顺序栈的存储结构*/
typedefstruct{
     ElemTypestack[MAXNUM];
     inttop;
}SqStack;
/*初始化顺序栈函数*/
voidInitStack(SqStack*p)
{q=(SqStack*)malloc(sizeof(SqStack)/*申请空间*/)
/*入栈函数*/
voidPush(SqStack*p,ElemTypex)
{if(p->top<maxnum-1)
     {p->top=p->top+1;     /*栈顶+1*/
      p->stack[p->top]=x;}  /*数据入栈*/
}
/*出栈函数*/
ElemTypePop(SqStack*p)
{x=p->stack[p->top];/*将栈顶元素赋给x*/
p->top=p->top-1;}/*栈顶-1*/
/*获取栈顶元素函数*/
ElemTypeGetTop(SqStack*p)
{x=p->stack[p->top];}
/*遍历顺序栈函数*/
voidOutStack(SqStack*p)
{for(i=p->top;i>=0;i--)
printf("第%d个数据元素是:%6d\n",i,p->stack[i]);}
/*置空顺序栈函数*/
voidsetEmpty(SqStack*p)
{p->top=-1;}
链接栈在程序中的表示
//  
#ifndef LINKSTACK_H  
#define LINKSTACK_H  
  
template <class T>  
struct Node  
{  
    T data;  
    Node<T> *next;  //此处<T>也可以省略  
};  
  
template <class T>  
class LinkStack  
{  
public:  
    LinkStack( );              //构造函数,置空链栈  
    ~LinkStack( );             //析构函数,释放链栈中各结点的存储空间  
    void Push(T x);           //将元素x入栈  
    T Pop( );                  //将栈顶元素出栈  
    T GetTop( );               //取栈顶元素(并不删除)  
    bool Empty( );             //判断链栈是否为空栈  
private:  
    Node<T> *top;             //栈顶指针即链栈的头指针  
};  
  
#endif  
//  
#include ""  
  
/* 
 * 前置条件:栈不存在 
 * 输    入:无 
 * 功    能:栈的初始化 
 * 输    出:无 
 * 后置条件:构造一个空栈 
 */  
  
template <class T>  
LinkStack<T>::LinkStack( )  
{  
    top=NULL;   
}  
/* 
 * 前置条件:栈已存在 
 * 输    入:无 
 * 功    能:销毁栈 
 * 输    出:无 
 * 后置条件:释放栈所占用的存储空间 
 */  
template <class T>  
LinkStack<T>::~LinkStack( )  
{  
    while (top)  
    {  
        Node<T> *p;  
        p=top->next;  
        delete top;  
        top=p;  
    }  
}  
  
/* 
 * 前置条件:栈已存在 
 * 输    入:节点s 
 * 功    能:在栈顶插入该节点 
 * 输    出:无 
 * 后置条件:如果插入成功,栈顶增加了一个元素