0-软件技术基础-数据结构(L1-3)-sxdai

1数据结构成都理工高校工程技术学院计科系代世雄2010年３月８日数据结构与算法的基本概念的基本概念什么是数据？

数据就是是信息的载体,它可以用计算机表示并加工。可以看出，数据这个概念本身是随着计算机的发展而不断扩展的概念。在计算机发展的初期，由于计算机主要用于数值计算，数据指的就是数值。计算机硬件和软件技术的不断发展，扩大了计算机的应用领域，诸如字符、文字、表格、图形、图像、声音等也属于数据的范畴2数据结构与算法的基本概念的基本概念什么是数据元素？数据元素是数据集合中的一个个体，它是数据的基本单位。例如：全部学生的学籍登记卡组成学生的学籍数据，每个学生的学籍登记卡就是学籍数据的一个数据元素。数据元素可以是一个数或字符串，也可以由若干数据项组成(数据的最小单位)。在这种状况下，通常把数据元素称为记录。34表2-1学生学籍登记表学号姓名性别民族籍贯专业1王安男汉北京计算机通信2李华男回河北软件3张莉女汉山西计算机应用4张平女汉广东软件数据结构与算法的基本概念的基本概念什么是数据结构？（１）数据结构就是探讨数据及数据元素之间关系的一门学科。（２）数据结构的基本单位是数据元素，它可以是基本类型，也可以是结构类型。数据结构的三个方面：数据的逻辑结构。数据的存储结构。数据的操作集合。561.数据的逻辑结构2.数据的存储结构3.数据的运算：检索、排序、插入、删除、修改等。A.线性结构B.非线性结构A.依次存储B.链式存储线性表栈队树形结构图形结构数据结构的三个方面反映数据元素之间的逻辑关系数据元素在计算机内部的组织方式C.散列结构（散列表）D.索引结构（索引表）数据的逻辑结构数据的逻辑结构就是它是描述数据间的依次（逻辑）关系，只是抽象地反映数据元素的结构，而不管它们在计算机中如何存放。一般用下列二元组来描述：DS=（D，R）其中：D：是数据元素的有限集合；R：是数据元素之间关系的集合。数据的逻辑结构与数据在计算机中的存放的物理位置无关7数据的存储结构数据的存储结构又称物理结构，是指数据结构在计算机中的表示(又称映象)，即数据在计算机中的存放。常用的存储结构包括依次结构和链式结构。逻辑结构和存储结构的关系１、数据的逻辑结构是从逻辑关系（某种依次）上视察数据，它是独立于计算机的；可以在理论上、形式上进行探讨、推理、运算等各种操作。２、数据的存储结构是逻辑结构在计算机中的实现，是依靠于计算机的；离开了机器，则无法进行任何操作。３、任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依靠于接受的存储结构。8数据的操作集合数据的操作集合：是指对存放在物理结构上的数据，按定义的逻辑结构进行的各种操作。常见操作有：输入、检索、插入、删除、修改、排序等。9数据结构与算法算法：为解决一个问题而实行的方法和步骤，就称为算法。算法的基本特性：１、有穷性：一个算法必需总是在执行有穷步之后结束，且每一步都在有穷时间内完成。２、确定性：每一步的依次与内容必需是唯一确定的。３、可行性：可以通过基本运算执行有限次来实现。４、数据输入：可以有０个或多个输入５、数据输出：必需至少有１个输出10算法和程序的区分算法是解决问题的一种方法或过程，考虑的是如何将输入转换为输出。一个问题可以有多种算法。程序是某种程序设计语言对算法的具体实现。算法和程序的主要区分在于：有穷性，正确性，和描述方法。１、程序可以是无穷的，如OS，算法是有穷的。２、程序可以是错误的，算法必需是正确的。３、程序是用程序设计语言描述，可在计算机上执行；算法还可以用框图、自然语言等形式来描述。11算法优劣的评价标准评价算法优劣的标准：时间困难度和空间困难度频度：是指该语句重复执行的次数。算法的时间困难度：指在计算机上运行该算法所花费的时间。用“O（数量级）”来表示，称为“阶”。常见的时间困难度有：O(1)O(logn)O(n)O(n2)空间困难度：指算法在计算机上运行所占用的存储空间。度量同时间困难度。时间与空间是一对冲突，要节约空间往往要消耗较多的时间，反之亦然。目前，内存空间足够，应重点考虑时间。12数据结构与算法－课堂练习131.数据在计算机内存中的表示是指数据的存储结构。 (Ｙ/N)3.以下（14）不是数据结构探讨的主要问题。(A)数据元素之间的逻辑关系 (B)数据元素之间的存储结构(C)软件开发方法 (D)实现操作的算法4.数据的基本单位是数据元素。5.数据类型是具有共同属性的一类变量的抽象。6.在数据结构中，一个存储结点存放一个（）。(A)数据项(B)数据元素(C)数据结构(D)数据类型7.数据类型是某种程序设计语言中已实现的数据结构。8.数据在计算机内在中的表示是指数据的存储结构。9.以下特征中哪个不是算法的特征 ()。(A)可行性 (B)确定性(C)有穷性(D)唯一性10.算法指的是（15）。（A）计算机程序（B）解决问题的有限运算序列（C）排序算法（D）解决问题的计算方法11.数据元素是数据的基本单位，数据项是数据的最小单位。线性结构线性结构：是最常用的数据结构。线性结构的基本特点：数据元素是有序且有限的。线性结构的逻辑特征：在线性结构中１、有且仅有一个无干脆前趋而仅有一个干脆后继的起始元素２、有且仅有一个无干脆后继而仅有一个干脆前趋的终点元素３、其余元素均为内部元素常用的线性结构包括：线性表、堆栈、队列、数组、串。14线性表线性表是由ｎ个(n>=0)相同类型元素构成的集合。15线性表的逻辑结构线性表是由n个数据元素组成的有限序列。记作：L=(a1，a2，…an)数据元素之间的关系ai-1领先于ai，ai领先于ai+1ai-1是ai的干脆前驱元素，ai＋1是ai的干脆后继元素除a1外，每个元素有且只有一个干脆前驱元素。除an外，每个元素有且只有一个干脆后继元素。线性表中数据元素的个数n(n>＝0)称为表的长度。n=0时称为空表16线性表的基本运算17Setnull（L）置空表Length（L）求表长度；求表中元素个数Get（L，i）取表中第i个元素（1≤i≤n）Prior（L，i）取i的前趋元素Next（L，i）取i的后继元素Locate（L，x）返回指定元素在表中的位置Insert（L，i，x）插入元素Delete（L，x）删除元素Empty（L）判别表是否为空线性表的依次存储结构线性表的依次存储结构将表中元素一个接一个的存入一组连续的存储单元中，这种存储结构是依次结构。接受依次存储结构的线性表简称为“依次表”。依次表的存储特点是：只要确定了起始位置，表中任一元素的地址都通过下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L1≤i≤n其中，L是元素占用存储单元的长度。18线性表元素存储示意图19线性表依次存储结构的特点线性表依次存储结构的特点：(1)占用连续的内存；(2)数据元素的逻辑结构和物理结构保持一样；(3)只要确定存储依次表的起始位置，表中随意元素可随机存取；故该结构亦称随机存储结构。线性表依次存储结构的缺点：(1)在插入或删除操作时，需移动大量的元素；(2)在给长度变更较大的线性表支配空间时，必需按最大空间支配；使存储空间不能得到充分利用；(3)表的容量难以扩容。20依次存储结构的插入运算21依次存储结构的插入运算22当在依次存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于插入或删除元素的位置。假设在第i个元素之前插入一个新元素的概率为1/(n+1)，即在表的任何位置(包括an之后)插入新元素的概率是相等的，则插入操作中元素的平均移动次数(事实上就是时间困难度)为： T=依次存储结构的特点小结依次存储结构的特点数据连续存放、随机存取逻辑上相邻，物理上也相邻存储结构简洁、易实现插入、删除操作不便存储密度大，空间利用率高结论：依次存储结构适合于表中元素变动较少的状况。23线性链表(LinkedList)线性表的依次存储结构简洁实现，可以随机存取表中的随意元素。依次表缺点是：–难于插入、删除操作；–须要预先支配空间，不管这些空间能否最大限度地利用。链表存储结构在这两个方面恰好是优点：–简洁插入、删除操作–不须要预分空间。24线性链表(LinkedList)链表：是指用一组随意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的随意位置上的。结点：数据元素ai的存储映象，它包括两个域：数据域：存储每个结点值；指针域：存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构：25线性链表(LinkedList)结点（NODE）表中元素的存储单元。链表存储结构形式为：数据域指针域链表结构的C语言描述为：structnode{intdata;structnode*next;};typedefstructnodeNODE；26线性链表(LinkedList)基本概念链表（Link）:由结点组成的表。头指针（head）:指向链表中第1个结点的指针。头结点:为便利操作，在头指针和首元结点之间设置的结点。首元结点:第一个结点（a1）。27线性链表(LinkedList)可以认为利用小的零散空间“串”起来，表示线性表，即把线性表的元素分散插入到系统所限制的零散空间中，然后用“指针”串起来，组成一个有序的线性表，用指针表示数据元素的逻辑关系。元素的存储，可以是连续的，也可以不是连续的。结点至少包括数据元素和指针两个区域。28a[0]a[2]a[3]a[1]300020001000单链表结构图示单链表的头指针为H：29160H160110a5200…

…150a2190160a1150…

…190a3210200a6260210a4110…

….240a8NULL

…

...

260a7240线性链表可以看出，用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的，逻辑上相邻的两个数据元素其存储的物理位置不要求相邻，因此，这种存储结构为非依次映像或链式映像。在运用中，我们只关切数据元素的逻辑次序而不必关切它的真正存储地址。通常，我们在单链表第一个元素所在的结点之前附设一个结点——头结点（增加的目的是统一空表与非空表的处理）。头结点的指针域存储第一个元素所在结点的存储位置；头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息。若线性表为空表，则头结点的指针域为“空”。30带头结点的单链表通常状况下，为了运算的统一，常在第一个结点前附设一个结点，称为“头结点”，头指针具有标识作用，因而，常用作链表的名字31LNode*p;p=（LNode*）malloc(sizeof(LNode))；则完成了申请一块LNode类型的存储单元的操作，并将其地址赋值给指针变量p。∧H空表a1a2an∧H

非空表…Pp->datap->next带头结点单链表的插入操作32线性链表操作：插入元素3333p指向当前结点，pre表示前一个结点(的指针)。在*p前(*pre后)插入元素s的语句序列：

s->next=pre->next; pre->next=s;aknextai-1nextainextpre带头结点单链表的删除操作34图2-8带头结点的单链表图2-9在单链表中删除一个结点线性链表操作：删除元素35ai-1nextainextai+1next*p表示当前结点,*pre表示*p的前驱结点删除*p结点的语句序列为：

pre->next=p->next;free(p); 循环链表假如链表最终一个结点的指针域指向头结点，整个链表形成一个环，这样的链表称为循环链表。这样，从表中任一结点动身均可找到表中其它结点，其逻辑状态图如图2-1036图2-10循环单链表循环链表循环链表一般设表头结点，这样链表将永不为空，这将使空表和非空表的逻辑状态及运算统一起来。循环链表的操作和线性链表基本一样，差别仅在于算法中的循环条件不是p或p->next是否为空，而是它们是否等于头指针。与单链表比较，循环链表有以下特点：(1)在循环单链表中，从表中任何一个结点动身都能访问到其它全部的结点；而单链表一般把头指针作为入口点，从某一结点动身，只能访问到其全部后继结点。(2)循环单链表的空表判定条件是：head->next=head。37双向链表前面探讨的链式存储结构中只有一个指示干脆后继的指针域，所以从某结点动身只能顺指针往后查找其它结点。若要查找结点的干脆前趋，则应从头指针动身(或在循环单链表中从p结点动身)始终往后找，直到结点q满足q->next=p，那么q是p的前趋结点。为克服链表这种单向性的缺点，为有更大的灵敏性来操作线性链表，可接受双向链表存储结构。38双向链表在每个结点上增加另一个指向线性表中每个元素的前趋结点的指针域prior，就得到双向链表。其结点的结构如下图所示。其中，prior是指向前趋结点的指针域；data是数据域；next是指向后继结点的指针域。39双向链表结点结构双向链表将双向链表的头结点和尾结点链接起来组成双向循环链表。双向链表的几种不同状态如图2-12，图2-13，图2-14和图2-15所示。40图2-12带头结点的空双向链表图2-13带头结点的非空双向链表双向循环链表41图2-14空的双向循环链表

图2-15非空双向循环链表双向链表在非空双向循环链表中，设p是指向链表中任一结点的指针，则有：p->next->prior=p->prior->next=p这个等式反映了这种链表的本质，在此链表上进行插入或删除操作是特殊便利的。双向链表虽然多花了存储空间，但却换得了操作上的更大灵敏性。双向链表的运算如LENGTH(Head)，GET(Head,i)，LOCATE(Head,x)等操作，仅涉及一个方向的指针，操作类似单链表。但插入INSERT、删除DELETE时要同时修改两个方向的指针。42双向链表的插入操作43图2-16在双向链表中插入结点插入时相关操作序列为：①s->prior=p->prior;②(p->prior)->next=s;③s->next=p;④p->prior=s。双向链表的删除操作44图2-17在双向链表中删除结点删除时相关操作序列为：①(p->prior)->next=p->next;②(p->next)->prior=p->prior;

线性表－课堂练习451.数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储结构无关，是独立于计算机的。(Ｙ/N)2.在线性表中，数据的存储方式有依次和链接两种。3.线性链表的地址()。(A)必需连续 (B)部分地址必需连续(C)确定不连续 (D)连续与否均可以4.线性表接受链式存储时，结点的存储地址必需是连续的5.依次表和线性链表的物理存贮形式都是依次存贮6.数组也是一种数据结构，一维数组就是一种依次表结构。7.线性表不具有的特点是（11）。(A)随机访问 (B)无须事先估计所需存储空间大小(C)插入时不必移动元素(D)所需空间与纯属表长度成正比8.数据在计算机内存中的表示是指数据的存储结构。9.链表可以随机访问随意一个结点，而依次表则不能。线性表－课堂练习46下述哪一条是依次存储结构的优点？（）A．插入运算便利B．可便利地用于各种逻辑结构的存储表示C．存储密度大D．删除运算便利下面关于线性表的叙述中，错误的是哪一个？（）A．线性表接受依次存储，必需占用一片连续的存储单元B．线性表接受依次存储，便于进行插入和删除操作C．线性表接受链接存储，不必占用一片连续的存储单元D．线性表接受链接存储，便于插入和删除操作。若某线性表最常用的操作是存取任一指定序号的元素和在最终进行插入和删除运算，则利用（）存储方式最节约时间。A．依次表B．双链表C．带头结点的双循环链表D．单循环链表线性表－课堂练习47链表不具有的特点是（）A．插入、删除不须要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比栈和队列栈(stack)和队列(queue)是常常遇到的两种数据结构，它们都是特殊状况下的线性表。前面介绍的线性表的向量及链表存储，进行插入、删除时是比较麻烦的。向量导致数据元素的大量移动，而链表中则要顺链找寻指定位置。假如能够把插入、删除操作都限制在线性表的端部进行，则运算效率可以大大提高。本节要探讨的就是这种限制存取位置的线性表——栈和队列。48栈栈（也称堆栈）1．栈的定义栈（stack）是限定只能在表的同一端进行插入和删除操作的线性表。其中允许进行插入和删除操作的一端称为栈顶(top)，而表中固定的一端称为栈底(bottom)。栈中元素个数为零时称为空栈。由于栈中元素的插入和删除只能在栈顶进行，所以总是后进栈的元素先出来，即栈具有后进先出(LastInFirstOut，缩写为LIFO)的特性，故栈又称为“后进先出表”(LIFO表)。49栈在日常生活中，有不少类似栈的例子。例如食堂中盘子的叠放，假如限定一次叠放一只，那么每次都是叠放到原来一叠盘子的顶上，这相当于入栈操作；而当取用一只盘子时，也是从这一叠盘子的顶上取用，这相当于出栈操作。50栈栈的五种基本运算：(1)Inistack(S)。初始化栈S为空栈。(2)Empty(S)。判定S是否为空栈。若S是空栈则返回值为真(Ture)，否则返回值为假(False)。(3)Push(S，x)。进栈操作。在栈S的栈顶插入数据元素x。(4)Pop(S)。出栈操作。若栈S不是空栈，则删除栈顶元素。(5)Gettop(S)。取栈顶元素。它只读取栈顶元素，不变更栈中的内容。51栈52例2-9

有三个元素的进栈序列是1，2，3，举出此三个元素可能的出栈序列，并写出相应的进栈和出栈操作序列如图2-18所示(假设以I和O表示进栈和出栈操作)。图2-18三个元素可能的出栈序列栈的表示和实现因为栈是线性表的一种特例，所以线性表的存储结构对它都适用。一般称接受依次存储结构的栈为依次栈；接受链式存储结构的栈为链栈。1)栈的依次存储结构——依次栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设指针top指示栈顶元素的当前位置。空栈的栈顶指针值为-1。设用数组Stack[MAXSIZE]表示栈，则对非空栈，Stack[0]为最早进入栈的元素，Stack[top]为最迟进入栈的元素，即栈顶元素。当top=MAXSIZE-1时意为栈满，此时若有元素入栈则将产生“数组越界”的错误，称为栈的“上溢”(overflow)；反之，top=-1意为栈空，若此时再作退栈操作，则发生“下溢”(underflow)。图2-19展示了依次栈中数据元素和栈顶指针之间的对应关系，设MAXSIZE=m。53栈的表示和实现54图2-19栈顶指针和栈中元素之间的关系

55栈的链式存储结构—链栈栈的运用特殊广泛，常常会出现在一个程序中须要同时运用多个栈的情形，为了不因栈上溢而产生错误中断，必需给每个栈预分一个较大的空间，但这并不简洁做到，因为各个栈实际所用空间很难估计。考虑到在实际进程中，当一个栈发生上溢时，其它栈可能还留有很多空间，所以可设法动态地加以调整，以达到多个栈共享内存时，只要有一个栈未满，其它任何栈的入栈操作均不会发生上溢。2)栈的链式存储结构——链栈接受依次存储结构，对于一个栈、两个栈可以清晰自然地表达，但当遇到多个栈共享空间的问题或栈的最大容量事先不能估计时，接受链式存储结构是有效的方法。56链栈存储结构的C语言描述structsnode{intdata;structsnode*link;};typedefstructsnodeSNODE;SNODE*top；链栈为空的条件：top=NULL链栈为满的条件：t=NULLt为申请的结点，为NULL表示失败。57栈的链式存储结构58图2-21链栈示意图栈的链式存储结构称为链栈，它是运算是受限的单链表。栈的链式存储结构对于链栈，不会产生单个栈满而其余栈空的情形，只有当整个可用空间都被占满，malloc函数无法实现时才会发生上溢。因此多个链栈共享空间也就是