《数据结构基础知识》由会员分享，可在线阅读，更多相关《数据结构基础知识（19页珍藏版）》请在金锄头文库上搜索。
1、复习提纲第一章数据结构概述基本概念与术语 ( P3)1.数据结构 是一门研究非数值计算程序设计问题中计算机的操作对象以及他 们之间的关系和操作的学科 ?2. 数据 是用来描述现实世界的数字 ，字符 ，图像 ,声音 ,以及能够输入到计算机中并能被计算机识别的符号的集合2 ?数据元素是数据的基本单位3 ?数据对象 相同性质的数据元素的集合4?数据结构三方面内容 ：数据的逻辑结构 ?数据的存储结构 ?数据的操作 ?( 1 ) 数据的逻辑结构指数据元素之间固有的逻辑关系( 2 ) 数据的存储结构指数据元素及其关系在计算机内的表示(3 ) 数据的操作指在数据逻辑结构上定义的操作算法?，如插入 ，删除等?
2、5?时间复杂度分析1、名词解释：数据结构、二元组2、根据数据元素之间关系的不同，数据的逻辑结构可以分为集合、线性结构、树形结构和图状结构四种类型。3、 常见的数据存储结构一般有四种类型，它们分别是顺序存储结构、链式存储结构 、索引存储结构 _ 和散列存储结构 _ 。4、 以下程序段的时间复杂度为 0(呼 ) _ 。int i,j,x;for(i=0;i n:i+)n+1for(j=0;j=0) 个具有相同性质的数据元素a1,a2,a3 有穷序列,an 组成的顺序表结构#define MAXSIZE 100 typedef int DataType;Typedef structDataType
3、itemsMAXSIZE;In t le ngth;Sqlist,*Li nkList;2. 单链表(1) 链表结点结构/链表的节点结构Typedef struct Nodeint data; struct Node *n ext; Ln ode,*P node,*Li nkList;(2) 结点遍历void TraverseList(L in kList t) Lin kList p;while(t) p=t;t=t- n ext free(p);(3) 链表操作算法：初始化、插入、输出、删除void In itList(Li nkList *h)*h=(Li nkList)malloc(s
4、izeof(LNode);if(!h)print(“初始化错误” );return;(*h)- next=NULL;void In sertList(L in kList h,i nt pos,datatype x)Lin kList p=h,q;int i=0;while(p&in ext;i+;if(!p|ipos-1)print(“插入位置出错 ！ ”) ；In itList(&q);q- next=NULL;欢迎下载2q-data=x;void DeleteList(L in kList h,i nt pos)Lin kList p=h,q;int i=0;while(p&in ext
5、;i+;if(!p|ipos-1)coutn ext;p-n ext=q-n ext;free(q);1、 线性表中，第一个元素没有直接前驱，最后一个元素没有直接后驱。2、 在一个单链表中，若p 所指结点是 q 所指结点的前驱结点，则删除结点q 的操作语句为p_next=q_next;free(q);。3、 在长度为 N 的顺序表中，插入一个新元素平均需要移动表中n/2 个元素，删除一个元素平均需要移动 (n-1)/2 个元素。4、若线性表的主要操作是在最后一个元素之后插入一个元素或删除最后一个元素，则采用带头结点的双循环链表 存储结构最节省运算时间。5、 已知顺序表中每个元素占用3 个存储单
6、元，第13 个元素的存储地址未336 ，则顺序表的首地址为 _300 _。6、 设有一带头结点单链表L, 请编写该单链表的初始化，插入、输出和删除函数。( 函数名自定义 )void In itList(Li nkList *L)(*L)=(Li nkList)malloc(sizeof(LNode);if(!L)cout next=NULL;void In sertList(L in kList L,i nt pos,DataType x)Lin kList p=L,q;int i=0;while(p&in ext; i+; if(!p|ipos-1)coutn ext=p-n ext;p_n
7、 ext=q;q-data=x;void TraverseList(L in kList L)Lin kList t;while(L)t=L;L=L-n ext; free(t);void TraverseList(L in kList L)Lin kList t=L;while(L)t=t-n ext; coutdata” ”；coute ndl;void DeleteList(L in kList L,i nt pos)Lin kList p=L,q;int i=0;while(p&in ext;i+ ；if(!p|ipos-1)coutn ext;p_n ext=q _n ext;fre
8、e(q):第三章栈和队列1.栈（ 1 栈的结构与定义（ 2 顺序栈操作算法：入栈、出栈、判断栈空等） （3 链栈的结构与定义）队列2.（1队列的定义）欢迎下载41、一个栈的入栈序列为“ABCDE ，则以下不可能的出栈序列是（）A. BCDAEB. EDACBC. BCADED. AEDCB2、 栈的顺序表示仲，用TOP 表示栈顶元素，那么栈空的条件是（）A. TOP=STACKSIZE B. TOP=1C. TOP=0D. TOP=-13、 允许在一端插入，在另一端删除的线性表称为队列。插入的一端为_队尾 _删除的一端为_ 队头。4、 栈的特点是 _ 先进后出 _，队列的特点是_ 先进先出 _
9、 。5、对于栈和队列，无论他们采用顺序存储结构还是链式存储结构，进行插入和删除操作的时间复杂度都是 _ O（1）_ 。6、 已知链栈 Q, 编写函数判断栈空，如果栈空则进行入栈操作，否则出栈并输出。（要求判断栈空、出栈、入栈用函数实现）void EmptyStack （ L in kStack Q ）Lin kStack t;char x=a; / 假设链栈存储字符型数据if（Q- next ） t=Pop （ Q,x ）;coutdata; else Push （ Q,x） ;基本概念数据结构的研究对象是什么？数据，数据元素 ( 数据结构中讨论的”基本单位 ”、数据整体中相对独立的单位、数据
10、元素的特点：相对性 ) ，数据结构，数据类型和抽象数据类型，数据对象数据结构是什么？定义：数据元素以及它们之间存在一种或多种特定的关系。特点：数据元素集合相同，而其上的关系不同，则构成的数据结构不同。逻辑结构是什么？主要有哪几类？逻辑结构：对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合 和定义在此集合上的若干关系表示。存储结构是什么？存储结构：是数据逻辑结构在计算机中的表示和实现，故又称数据”物理结构 ”。什么是算法？定义：是对问题求解过程的一种描述， 是为解决一个或一类问题给出的一个确定的、有限长的操作序列。五大特性：有穷性、确定性、可行性、输入、输出线性表线性表的定义 ？线性表是由 n(n 0) 个属性相同数据元素印向 2-a n 组成的一个有限序列，线性表或是空表，或可以表示为A=(a i,a2, ， ai, ， an)其中 ai(i=1 ,2, ， n) 是线性表中的一个元素。如何在顺序存储结构表示的线性表中实现插入元素操作?欢迎下载5int insertElement(List_Array *list_ptr, char *element)/ 把新字符串插入到线性表的最后位置if(list_ptr-cou nt = LISTMAX) return (-1); /到达最大大小else
