《数据结构复习提纲(整理)》由会员分享，可在线阅读，更多相关《数据结构复习提纲(整理)（10页珍藏版）》请在金锄头文库上搜索。
1、复习提纲复习提纲第一章第一章 数据结构概述数据结构概述基本概念与术语（基本概念与术语（P3） 1 数据结构数据结构 是一门研究非数值计算程序设计问题中计算机的操作对象以及他是一门研究非数值计算程序设计问题中计算机的操作对象以及他 们之间的关系和操作的学科们之间的关系和操作的学科. 2 数据数据 是用来描述现实世界的数字是用来描述现实世界的数字,字符字符,图像图像,声音声音,以及能够输入到计算机中以及能够输入到计算机中 并能被计算机识别的符号的集合并能被计算机识别的符号的集合 2数据元素数据元素 是数据的基本单位是数据的基本单位 3数据对象数据对象 相同性质的数据元素的集合相同性质的数据元素的集
2、合 4数据结构数据结构 包括三方面内容包括三方面内容:数据的逻辑结构数据的逻辑结构.数据的存储结构数据的存储结构.数据的操作数据的操作. （1）数据的逻辑结构）数据的逻辑结构 指数据元素之间固有的逻辑关系指数据元素之间固有的逻辑关系. （2）数据的存储结构）数据的存储结构 指数据元素及其关系在计算机内的表示指数据元素及其关系在计算机内的表示( 3 ) 数据的操作数据的操作 指在数据逻辑结构上定义的操作算法指在数据逻辑结构上定义的操作算法,如插入如插入,删除等删除等. 5.时间复杂度分析时间复杂度分析 - -1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为
3、集合、线性结构、树形结构集合、线性结构、树形结构和图状结构图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是_顺序存储结构顺序存储结构 _、_链式存储结构链式存储结构_、_索引存储结构索引存储结构_和_散列存储结构散列存储结构 _。 4、以下程序段的时间复杂度为_O(N2)_。int i,j,x; for(i=0;i=0)个具有相同性质的数据元素个具有相同性质的数据元素 a1,a2,a3,an 组成的组成的 有穷序列有穷序列/顺序表结构顺序表结构 #define MAXSIZE 100 typedef int DataType;Typedef structDataType i
4、temsMAXSIZE; Int length; Sqlist,*LinkList;/初始化链表初始化链表 void InitList(LinkList *L) (*L)=(LinkList)malloc(sizeof(LNode); if(!L) coutnext=NULL; /插入数据插入数据 void InsertList(LinkList L,int pos,DataType x) LinkList p=L,q; int i=0; while(pi+; if(!p|ipos-1)coutnext=p-next; p-next=q; q-data=x; /销毁链表销毁链表 void De
5、storyList(LinkList L) LinkList t; while(L)t=L;L=L-next;free(t); /遍历链表遍历链表 void TraverseList(LinkList L) LinkList t=L; while(L)t=t-next;coutdatanext;i+; if(!p|ipos-1) coutnext; p-next=q-next; free(q): 第三章第三章 栈和队列栈和队列1. 栈栈 （1） 栈的结构与定义栈的结构与定义 （2） 顺序栈操作算法：入栈、出栈、判断栈空等顺序栈操作算法：入栈、出栈、判断栈空等（3） 链栈的结构与定义链栈的结构与
6、定义 2. 队列队列 （1） 队列的定义队列的定义- -1、一个栈的入栈序列为“ABCDE”，则以下不可能的出栈序列是（） A. BCDAEB. EDACBC. BCADED. AEDCB 2、栈的顺序表示仲，用 TOP 表示栈顶元素，那么栈空的条件是（） A. TOP=STACKSIZEB. TOP=1C. TOP=0D. TOP=-1 3、允许在一端插入，在另一端删除的线性表称为_队列_。插入的一端为 _队尾_，删除的一端为_队头_。 4、栈的特点是_先进后出_，队列的特点是_先进先出_。 5、对于栈和队列，无论他们采用顺序存储结构还是链式存储结构，进行插入和 删除操作的时间复杂度都是_O
7、(1)_。 6、已知链栈 Q，编写函数判断栈空，如果栈空则进行入栈操作，否则出栈并输 出。 （要求判断栈空、出栈、入栈用函数实现）/判断栈空判断栈空(完成题目要求完成题目要求) void EmptyStack(LinkStack Q) LinkStack t; char x=a; /假设链栈存储字符型数据假设链栈存储字符型数据 if(Q-next)t=Pop(Q,x);coutdata; else Push(Q,x); /初始化栈初始化栈 void InitStack(LinkStack *Q) *Q=(LinkStack)malloc(sizeof(SNode); if(!Q)coutnex
8、t=NULL; /入栈入栈 void Push(LinkStack Q,datatype x) LinkStack t; InitStack( t-data=x; t-next=Q-next;Q-next=t; /出栈出栈 void Pop(LinkStack Q,datatype if(!t)coutnext=t-next; x=t-data;free(t); 基本概念基本概念 数据结构的研究对象是什么？数据结构的研究对象是什么？ 数据数据，数据元素数据元素（数据结构中讨论的数据结构中讨论的“基本单位基本单位“、数据整体中相对独立、数据整体中相对独立 的单位、的单位、 数据元素的特点：相对性
9、）数据元素的特点：相对性） ，数据结构，数据结构，数据类型和抽象数据类型数据类型和抽象数据类型，数据数据 对象对象 数据结构是什么？数据结构是什么？ 定义定义：数据元素以及它们之间存在一种或多种特定的关系。数据元素以及它们之间存在一种或多种特定的关系。 特点特点 ：数据元素集合相同，而其上的关系不同，则构成的数据结构不同。数据元素集合相同，而其上的关系不同，则构成的数据结构不同。 逻辑结构是什么？主要有哪几类？逻辑结构是什么？主要有哪几类？逻辑结构逻辑结构：对数据元素之间存在的逻辑关系的描述，它可以用一个数据对数据元素之间存在的逻辑关系的描述，它可以用一个数据 元素的集合和定义在此集合上的若干
10、关系表示。元素的集合和定义在此集合上的若干关系表示。 存储结构是什么？存储结构是什么？ 存储结构：是数据逻辑结构在计算机中的表示和实现，故又称数据存储结构：是数据逻辑结构在计算机中的表示和实现，故又称数据“物理物理 结构结构“。 什么是算法？什么是算法？ 定义：是对问题求解过程的一种描述，是为解决一个或一类问题给出的定义：是对问题求解过程的一种描述，是为解决一个或一类问题给出的 一个确定的、有限长的操作序列。一个确定的、有限长的操作序列。 五大特性：五大特性：有穷性、确定性、可行性、输入、输出有穷性、确定性、可行性、输入、输出线性表线性表 线性表的定义线性表的定义? 线性表是由线性表是由 n(
11、n0)个属性相同数据元素个属性相同数据元素 a1,a2an组成的一个有限序列，组成的一个有限序列， 线性表或是空表，或可以表示为线性表或是空表，或可以表示为 A=(a1，a2，ai，an) 其中其中 ai(i=1，2，n)是线性表中的一个元素。是线性表中的一个元素。 如何在顺序存储结构表示的线性表中实现插入元素操作？如何在顺序存储结构表示的线性表中实现插入元素操作？ int insertElement(List_Array *list_ptr, char *element) /把新字符串插入到线性表的最后位置把新字符串插入到线性表的最后位置 if(list_ptr-count = LISTMA
12、X)return (-1); / 到达最大大小到达最大大小else strcpy(list_ptr-listlist_ptr-count,element);list_ptr-count+; /下一个元素下一个元素return (1); / 成功返回成功返回 如何在顺序存储结构表示的线性表中实现元素删除操作？如何在顺序存储结构表示的线性表中实现元素删除操作？ int deleteElement(List_Array *list_ptr, int pos) int k; /检查下标检查下标 pos 位置上是否存在数据位置上是否存在数据 if (pos list_ptr-count-1) retur
13、n (-1); /出错出错 else /将将 pos 位置后所有元素向前移动位置后所有元素向前移动 for (k = pos; k count - 1;k+) strcpy(list_ptr-listk,list_ptr-listk+1); list_ptr-count-; return (1); / 删除成功删除成功 如何在顺序存储结构表示的线性表中找到元素后继？如何在顺序存储结构表示的线性表中找到元素后继？ 物理地址上紧接着该元素后一个级即该元素的后继物理地址上紧接着该元素后一个级即该元素的后继 用数组的下标加用数组的下标加 1 即可找到即可找到. 如何在顺序存储结构表示的线性表中找到元素
14、前驱？如何在顺序存储结构表示的线性表中找到元素前驱？ 物理地址上紧接着该元素前一个即该元素的前驱物理地址上紧接着该元素前一个即该元素的前驱 用数组下标减用数组下标减 1 即可找到即可找到 链表链表 什么是链接存储结构？什么是链接存储结构？ 通过指针管理的一组存储单元，通过指针管理的一组存储单元， （这组存储单元的内存地址可以是连续的，（这组存储单元的内存地址可以是连续的， 也可以是不连续的）也可以是不连续的） 。 链接存储结构中的每个存储单元称为链接存储结构中的每个存储单元称为“结点结点”，结点包含一个数据域和一，结点包含一个数据域和一 个指针域；个指针域； 链接存储结构中的结点通过指针域指示
15、后继结点的内存地址；链接存储结构中的结点通过指针域指示后继结点的内存地址； 访问链接存储结构通常由第一个结点开始，逐一访所有结点。访问链接存储结构通常由第一个结点开始，逐一访所有结点。 如何将新结点添加到单链表中？如何将新结点添加到单链表中？ 表头位置表头位置00 Node *t=new Node; t-Data=d; t-next=head; head=t; 表尾位置表尾位置00 Node *t =new Node; t-data=d; last-next=t; last=t; 两个结点中间两个结点中间 查找单链表中指定结点？查找单链表中指定结点？ 设置一个跟踪链表结点的指针设置一个跟踪链表
