搜索
数据结构主要知识点第一部分：1、数据是客观事物的符号表示，在计算机科学中是指所有能输入到算机中并被计算机所处理的符号的总称。2、数据对象是性质相同的数据元素的集合。3、数据结构是相互间存在一种或多种特定关系的数据元素的集合。4、数据结构的四种基本形式是：集合、线性结构、树形结构和图状结构或网状结构。5、数据类型是一个值的集合和定义在这个值集上的一组操作的总称。6、顺序存储结构的特点是：1）占用一块地址连续的内存单元；2）用存储位置的物理相邻表示数据间的逻辑相邻；3）可以实现随机存取。7、链式存储结构的特点是：1）动态分配存储空间；2）用指针表示数据间的逻辑关系；3）不能实现随机存取。8、算法是对特定问题求解步骤的一种描述、是指令的有限序列。9、算法满足以下5个性质：1）输入：一个算法可以有0个或多个输入；2）输出：一个算法要有一个或多个输出；3）有穷性：一个算法必须在执行有穷步骤后结束，每一步骤也必须在有限时间内完成；4）确定性：算法中的每一步骤都有明确的含义，没有二义性；5）可行性：算法中描述的每一个操作，都可以通过已经实现的基本运算，执行有限次后完成。10、算法的四项基本要求是：1）正确性、可读性、健壮性和效率与低存储需量。2）评价算法时间效率的指标是时间复杂度。3）时间复杂度是用算法中基本操作的重复执行次数与问题规模之间的函数关系，来描述算法的时间效率。但由于难以求得基本操作的重复执行次数与问题规模之间的精确的解析的函数关系，所以算法时间复杂度通常用问题规模（n）的某类函数的阶来表示。评价算法空间效率的指标是空间复杂度。11、五种常见的算法时间复杂度是：常量阶、线性阶、对数阶、多项式阶和指数阶。12、描述以下三个概念的区别：头指针、头结点、第一个元素结点。第一个元素结点是指链表中存储线性表中第一个数据元素的结点。为操作方便，通常在链表的第一个结点之前附设一个结点，称为头结点，该结点的数据域不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对第一个元素结点进行同一处理。头指针是指向链表中第一个结点（或为头结点或为第一个元素结点）的指针。若链表中附设头结点，则不管线性表是否为空，头指针均不为空，若链表中不设头结点，则空链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。13、在顺序表中插入或删除一个元素，需要平均移动表长一半的元素，具体移动元素的个数与表长和该元素在表中的位置有关。在单链表中，除第一个数据元素结点外，任一结点的存储位置由其直接前驱结点的指针域的值指示。在单链表中设置头结点的作用是插入和删除第一个数据元素结点时不必进行特殊处理。第二部分：1、已知L是无表头结点的单链表，且P结点即不是第一个结点也不是最后一个结点，试写出实现下列操作的语句序列：1)在Ｐ结点后插入Ｓ结点S-next=P-next;P-next=S;2)在Ｐ结前后插入Ｓ结点Q=p;P=L;while(P-next!=Q)P=P-next;S-next=P-next;P-next=S;3)在表首插入S结点S-next=L;L-S;4)在表尾插入S结点P=L;while(P-next!=NULL)P=P-next;S-next=P-next;P-next=S;2、已知L是带表头结点的单链表，且P结点即不是第一个结点也不是最后一个结点，试写出实现下列操作的语句序列：1）删除P结点直接后继结点Q=p-next;P-next=P-next-next;free(Q);2）删除P结点直接前驱结点Q=p;P=L;while(P-next-next!=Q)P=P-next;Q=p-next;P-next=P-next-next;free(Q);3）删除P结点Q=P;P=L;while(P-next!=Q)P=P-next;P-next=P-next-next;free(Q);4）删除第一个数据元素结点P=L;Q=P-next;P-next=P-next-next;free(Q);5）删除最后一个数据元素结点while(P-next-next!=NULL)P=P-next;Q=p-next;P-next=P-next-next;free(Q);第三部份：1、顺序栈的存储结构定义#defineSTACK_INIT_SIZE100typedefstruct{//这里SElemType的类型根据具体情况，由程序员自行定义SElemType*base;//栈基址SElemType*top;//栈顶指针intstacksize;//当前已经分配的存储单元，以元素为单位}SqStack;//顺序栈数据类型2、有关顺序栈的基本操作1）构造一个空栈intInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)return0;//内存分配失败，返回0S.top=S.base;S.stacksize=STACK_INIT_SIZE;//return1;}//InitStack2）元素进栈（不考虑栈满）intPush(SqStack&S,SElemTypee){*S.top=e;S.top++;return1;}//Push3）元素出栈intPop(SqStack&S,SElemType&e){if(S.top==S.base)return0;//若栈为空，出栈失败，返回0S.top--;e=*S.top;//用引用参数e保存栈顶元素的值return1;//出栈成功，返回1}//Pop2、（1）链栈结点类型的定义typedefstructLnode{/*链栈结点类型*/ElemTypedata;//数据域，ElemType的类型根据具体情况，由程序员自行定义structLNode*next;//指针域}LNode,*Link;（2）链栈的存储结构定义typedefstruct{Linkhead;//栈顶指针intlen;//链栈的当前长度}LinkStack;/*链栈类型*/（3）有关链栈的基本操作1）创建带头结点的空链栈intInitLinkStack(LinkStack&S){/*创建带头结点的空链栈*/S.head=(LNode*)malloc(sizeof(LNode));/*创建头结点*/if(!S.head)return0;//内存分配失败S.head-next=NULL;S.len=0;return1;//空链栈创建成功}2）创建新结点intNewNode(Link&p,ElemTypee){p=(LNode*)malloc(sizeof(LNode));/*创建新结点，引用变量p保存新结点的地址*/p-data=e;/*结构变量整体赋值*/p-next=NULL;return1;}3）元素进栈intPush(LinkStack&S,ElemTypee){intr;Linkp;r=NewNode(p,e);/*p指向新结点*/if(!r)return0;p-next=S.head-next;/*新结点插在头结点之后*/S.head-next=p;S.len++;return1;}4）元素出栈intPop(LinkStack&S,ElemType&e){Linkp;if(S.len==0)return0;//若栈为空，则出栈失败p=S.head-next;/*保存栈顶结点的指针*/e=p-data;/*用引用参数e，保存栈顶结点数据域的值*/S.head-next=p-next;/*修改栈顶指针，S.head-next就是栈顶指针*/S.len--;free(p);//释放栈顶元素所占用的内存return1;//出栈成功}3、循环队列的存储结构定义#defineMAXQSIZE100typedefstruct{QElemType*base;//QElemType的类型根据具体情况，由程序员自行定义intrear;//队尾指针intfront;//对头指针}SqQueue;//循环队列数据类型有关循环队列的基本操作1）创建一个空的循环队列intinitqueue(SqQueue&Q){Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base)return0;//内存分配失败Q.front=Q.rear=0;return1;//队列创建成功}//initqueue2）新元素入队列IntEnQueue(SeQueue&Q,QelemTypee){if((Q.rear+1)%MAXQSIZE==Q.front)return0;//队列满Q.base[Q.rear]=e;//新元素插在队尾Q.rear=(Q.rear+1)%MAXQSIZE;//队尾指针加1Return1;//入队列成功}3）删除队头元素intDelqueue(SqQueue&Q,QElemType&x){if(Q.front==Q.rear)return0;//队列为空x=Q.base[Q.front];//用引用参数x保存队头元素的值Q.front=(Q.front+1)%MAXQSIZE;//队头指针加1return1;//删除成功}//Delqueue（1）链队列结点类型typedefstructLnode{/*链队列结点类型*/ElemTypedata;//ElemType的类型根据具体情况，由程序员自行定义structLNode*next;}LNode,*Link;（2）链队列类型typedefstruct{Linkfront,rear;//头、尾指针intlen;//队列的当前长度}LinkQueue;/*链队列类型*/4、有关链队列的基本操作1）创建带头结点的空链队列intInitLinkQueue(LinkQueue&Q){/*创建带头结点的空链队列*/Q.front=(LNode*)malloc(sizeof(LNode));/*创建头结点*/if(!Q.front)return0;//头结点创建失败Q.rear=Q.front;//头、尾指针都指向头结点Q.front-next=NULL;Q.len=0;return1;}2）新元素插入到队尾intEnterQueue(LinkQueue&Q,ElemTypee){intr;Linkp;r=NewNode(p,e);/*p指向新结点*/if(!r)return0;//创建新结点失败Q.rear-next=p;/*新结点插在队尾结点之后*/Q.rear=p;/*尾指针等于p*/Q.len++;return1;//新元素插入成功}3）删除队头元素intDelQueue(LinkQueue&Q,ElemType&e){Linkp;if(Q.len==0)return0;//队列为空p=Q.front-next;/*保存队头结点的指针*/e=p-data;/*用引用参数e保存队头结点数据域的值*/Q.front-next=p-next;/*修改队头指针，Q.front-next就是队头指针*/Q.len--;if(Q.rear==p)Q.rear=Q.front;/*若队列中只有一个结点，队头也是队尾*/free(p);/*删除队尾，需要对队尾指针重新赋值*/return1;}第四部分：二叉树是每个结点上最多有左右两个分支的有序二叉树。在二叉树的第k层上至多有2k-1个结点。深度为k的二叉树至多有2k-1个结点。具有n个结点的完全二叉树的深度为（log2n）向下取整后再加1。若一棵深度为k的二叉树，共有2k-1个结点，则此二叉树就是满二叉树，满二叉树的叶子结点都在最底层。设T1、T2都是深度为d的二叉树，其中T1还是满二叉树。对T