第1章数据结构基础.

第一章数据结构基础要想成为一名真正的程序员，数据结构是必备的基础知识。只有学过数据结构，才能真正有效规范地组织程序中的数据。而在实际编程中，有些问题必须通过特定的数据结构才能更方便地解决。因此数据结构是每一个搞计算机的人都应当十分掌握的知识。要想全面而系统地学习数据结构的知识，这里的介绍显然是不充分的，建议应当找来专门介绍数据结构的书籍学习。如果你只想掌握一般层次的知识，或是已经学过数据结构，只是为了深入地学习本书后续的内容而进行回顾和复习，那么本章的介绍是足够的。1.1什么是数据结构数据结构就是指计算机内部数据的组织形式和存储方法。我们再熟悉不过的数组就是一种简单而典型的线性数据结构类型。本章中将更加具体地介绍一些常用的数据结构，主要包括：线性结构、树、图。线性结构是最常用，也是最简单的一种数据结构。还有一种常用的数据结构叫做图状结构，简称图结构。图结构中数据元素之间存在着“多对多”的关系，因此图结构较树结构，线性结构要复杂得多。在处理一些复杂的问题中，图结构往往能派上用场。1.2顺序表在计算机内部存储一张线性表（线性结构的数表），最为方便简单的就是用一组连续地址的内存单元来存储整张线性表。这种存储结构称为顺序存储结构，这种存储结构下的线性表就叫做顺序表。如图1-1所示，就是顺序表的示意。1.2.1顺序表的定义定义一张顺序表也就是在内存中开辟一段连续的存储空间，并给它一个名字来标识。只有定义了一个顺序表，才能利用该顺序表存放数据元素，也才能对该顺序表进行各种操作。有两种定义顺序表的方法，一是静态地定义一张顺序表；二是动态生成一张顺序表。1.2.2向顺序表中插入元素下面介绍如何在长度为n的顺序表中的第i个位置插入新元素item。所谓在长度为n的顺序表中的第i个位置插入新元素是指在顺序表第i-1个数据元素和第i个数据元素之间插入一个新元素item。函数InserElem的作用是在顺序表Sqlist中第i个位置上插入元素item，并将顺序表长度加１。其实现过程如下。（1）判断插入元素的位置是否合法。一个长度为n的顺序表的可能插入元素的位置是1~n+1，因此如果i1或者in+1或者表满n==MaxSize（因为表的内存大小固定不变）的插入都是非法的。（2）将顺序表的i-1以后的元素顺序后移一个元素的位置，即：将顺序表从第i个元素到第n个元素顺序后移一个元素的位置。（3）在表的第i个位置（下标为i-1）上插入元素item，并将表长加1。1.2.3从顺序表中删除元素下面介绍如何删除长度为n的顺序表中的第i个位置的元素。所谓删除长度为n的顺序表中的第i个位置的元素，就是指将顺序表第i个位置上的元素去掉。函数DelElem的作用是从顺序表Sqlist中删除第i个位置的元素，并将表的长度值减1。其实现过程如下。（1）判断要删除的元素是否合法。对于一个长度为n的顺序表，删除元素的合法位置是1~n，因此如果i1或者in都是不合法的。（2）将顺序表的第i位置以后的元素依次前移，这样就将第i个元素覆盖掉了，也就起到删除第i个位置元素的作用。（3）最后将表长减1。1.2.4实例与分析前面介绍了静态顺序表和动态顺序表的定义，创建，插入元素，删除元素等方法。下面通过具体的实例巩固学到的知识。【实例1-1】创建一个静态的顺序表存放整数，大小为10，完成以下的操作：（1）输入6个整数，打印出顺序表中的内容，并显示表中剩余的空间个数。（2）在顺序表中的第3个位置插入元素0，打印出顺序表中的内容，并显示表中剩余的空间个数。（3）再试图插入表中第11个位置整数0，程序提示超出范围（4）删除表中第6个元素，打印出顺序表中的内容，并显示表中剩余的空间个数。1.3链表与顺序表相同，链表也是一种线性表，它的数据的逻辑组织形式是一维的。而与顺序表不同的是，链表的物理存储结构是用一组地址任意的存储单元存储数据的。也就是说，它不像顺序表那样占据一段连续的内存空间，而是将存储单元分散在内存的任意地址上。在链表结构中，存储的每个数据元素记录都存放到幢淼囊桓鼋岬悖node）中，而每个结点之间由指针将其连接在一起，这样就形成了一条如同“链”的结构。1.3.1创建一个链表建立一条长度为n的链表的全过程，共分为以下几个步骤。（1）用malloc函数在内存的动态存储区中开辟一块大小为sizeof(LNode)的空间，并将其地址赋值给LinkList类型变量p,然后将数据e存入该结点的数据域data，指针域存放NULL。其中数据e由函数Get获得。（2）如果指针变量list为空，说明本次生成的结点为第一个结点，所以将p赋值给list，list是LinkList类型变量，只用来指向第一个链表结点，因此它是该链表的头指针，最后要返回。（3）如果指针变量list不为空，则说明本次生成的结点不是第一个结点，因此将p赋值给r-next。（4）再将p赋值给r，目的是使r再次指向最后的结点，以便生成链表的下一个结点，即：保证r永远指向原先链表的最后一个结点。（5）最后将生成的链表的头指针list返回主调函数，通过list就可以访问到该链表的每一个结点，并对该链表进行操作。1.3.2向链表中插入结点下面介绍如何在指针q指向的结点后面插入结点。该过程的步骤如下：（1）先创建一个新结点，并用指针p指向该结点。（2）将q指向的结点的next域的值（即q的后继结点的指针）赋值给p指向结点的next域。（3）将p的值赋值给q的next域。1.3.3从链表中删除结点下面介绍如何从非空链表中删除q所指的结点。在讨论这个问题时，必须考虑以下三种情形：（1）q所指向的是链表的第一个结点；（2）q所指向的结点的前驱结点的指针已知；（3）q所指向的结点的前驱结点的指针未知。1.3.4销毁一个链表在链表使用完毕后建议销毁它，因为链表本身会占用内存空间。如果一个系统中使用很多的链表，而使用完毕后又不及时地销毁它，那么这些垃圾空间积累过多，最终可能导致内存的泄漏甚至程序的崩溃。因此应当养成及时销毁不用的链表的习惯。函数destroyLinkList的作用是销毁一个链表list，它包括以下步骤。（1）首先将*list的内容赋值给p，这样p也指向链表的第一个结点，成为了链表的表头。（2）然后判断只要p不为空（NULL），就将p指向的下一个结点的指针（地址）赋值给q，并应用函数free释放掉p所指向的结点，p再指向下一个结点，如此循环，直到链表为空为止。（3）最后将*list的内容置为NULL，这样主函数中的链表list就为空了，防止了list变为野指针。而且链表在内存中也被完全地释放掉了。1.3.5实例与分析【实例1-3】编写一个程序，要求：从终端输入一组整数（大于10个数），以0作为结束标志，将这一组整数存放在一个链表中（结束标志0不包括在内），打印出该链表中的值；然后删除该链表中的第5个元素，打印出删除后的结果；最后在内存中释放掉该链表。1.4栈栈是一种重要的线性结构。可以这样讲，栈是前面讲过的线性表的一种具体形式。也就是说，栈必须通过顺序表或者链表来实现。顺序表或者链表既可以像前面介绍的那样独立存在，组织和操作数据，同时它们也是一些特殊的数据结构（栈，队列等）的实现的基础，它们的概念更宽泛一些。1.4.1栈的定义栈（stack）是一个后进先出(LIFO:lastinfirstout)的线性表，它要求只在表尾进行删除和插入等操作。也就是说，所谓栈其实就是一个线性表（顺序表，链表），但是它在操作上有一些特殊的要求和限制。首先，栈的元素必须先进后出，这与一般的顺序表不同。其次，栈的操作只能限定在这个顺序表的表尾进行。1.4.2创建一个栈创建一个栈有两个任务：一是在内存中开辟一段连续的空间，用作栈的物理存储空间；二是将栈顶、栈底地址赋值给sqStack类型变量（对象）的top和base域，并设置stacksize值，以便通过这个变量（对象）对栈进行各种操作。1.4.3入栈操作入栈操作又叫压栈操作，就是向栈中存放数据。入栈操作要在栈顶进行，每向栈中压入一个数据，top指针就增1，直到栈满为止。1.4.4出栈操作出栈操作就是在栈顶取出数据，栈顶指针随之下移的操作。每当从栈内弹出一个数据，栈的当前容量就减少1。可以重复出栈操作，直到该栈变为空栈为止。1.4.5栈的其他操作除了以上介绍的创建栈，入栈，出栈等操作外，对栈还有一些其他的操作。例如：清空一个栈，销毁一个栈，计算栈的当前容量等。其实程序员完全可以根据实际编程的需要来设计这些操作。1．清空一个栈2．销毁一个栈3．计算栈的当前容量1.4.6实例与分析【实例1-4】利用栈的数据结构，将二进制数转换为十进制数。分析：二进制数是计算机中数据的存储形式。它是由一串0/1编码组成。每个二进制数都可以转换成为相应的十进制数，转换的方法如下：一个二进制数要转换为相应的十进制数，就是从最低位起用每一位去乘以对应位的基，也就是说用第i位去乘以2i-1，然后再将每一位的乘积累加，就得到原二进制数对应的十进制表达。由于栈具有后进先出的特性，因此可以用栈很方便地实现二进制转换为十进制。具体做法是，将一串二进制的0/1码从高位到低位顺序入栈，然后再逐一从栈顶取出元素，取出的第i个元素乘以2i-1，再逐一累加在一起，最终得到该二进制数的十进制表达。1.5队列1.5.1队列的定义队列（queue）也是一种重要的线性结构。与栈相同，实现一个队列同样需要顺序表或者链表作为基础，也就是说可以用链表或者顺序表来构造一个队列。但是与栈不同的是，队列是一种先进先出(FIFO:firstinfirstout)的线性表。它要求所有的数据从队列的一端进入，从队列的另一端离开。在队列中，允许插入数据的一端叫做队尾(rear)，允许数据离开的一端叫做队头(front)。1.5.2创建一个队列创建一个队列要完成两个任务：一是在内存中创建一个头结点，但是该头结点不是用来存放数据的，而是为了操作方便人为添加的。当然也可以不定义这个头结点。二是将队列的头指针和尾指针都指向这个生成的头结点，此时队列中没有任何队列元素，该队列为空队列。不难看出应用这种绞酱唇ǖfront和尾指针rear都同时指向头结点。1.5.3入队列操作入队列操作就是将一个QNode类型的元素从队列的尾部进入队列。每当将一个队列元素插入队列，队列的尾指针都要进行修改（因为元素从队列的尾部进入队列），队头的指针不发生改变。1.5.4出队列操作出队列操作是将队列中的元素从队列的头部移出。每当从队列中移出数据时，队头指针不发生改变，但是头结点的next指针发生改变。队尾指针只有在原队列中只有一个元素，即队头等于队尾的情况下才会改变，否则也不改变。1.5.5销毁一个队列由于链队列是建立在内存的动态区的，因此当一个队列不再有用时应当把它及时销毁掉，以免过多地占用内存空间。销毁一个队列的方法与销毁一个链表的方法类似，代码如下：DestroyQueue(LinkQueue*q){while(q-front){q-rear=q-front-next;free(q-front);q-front=q-rear;}}通过上面的代码可以完整的销毁一个队列，最终q-rear和q-front都为空。1.5.6循环队列的概念还有一种用顺序表实现的队列叫做循环队列。所谓循环队列顾名思义就是该队列与传统的链队列不同，队列的空间是可以循环使用的。循环队列一般有固定的容量，与传统的队列相同，队列元素必须从队尾进入队列，必须从队头出队列。1.5.7循环队列的实现在实际的内存当中，不可能有像图1-20那样的环形存储区，只有线性的存储单元，因此循环队列实际上是用顺序表模拟出来的逻辑上循环，物理存储空间线性的队列数据结构。下面通过如图1-21所示的循环队列的几种状态来理解循环队列的实现方法和基本操作。1．定义一个循环队列2．初始化一个循环队列3．入队列操作4．出队列操作1.5.8实例与分析【实例1-5】实现一个链队列，任意输入一串字符，以@为结束标志，然后将队列中的元素逐一取出，打印在屏幕上