第一章_数据结构基础.ppt

第一章 数据结构基础 要想成为一名真正的程序员，数据结构是必备的基础知识。只有学过数据结构，才能真正有效规范地组织程序中的数据。而在实际编程中，有些问题必须通过特定的数据结构才能更方便地解决。因此数据结构是每一个搞计算机的人都应当十分掌握的知识。 要想全面而系统地学习数据结构的知识，这里的介绍显然是不充分的，建议应当找来专门介绍数据结构的书籍学习。如果你只想掌握一般层次的知识，或是已经学过数据结构，只是为了深入地学习本书后续的内容而进行回顾和复习，那么本章的介绍是足够的。 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类型变量，只用来指向第一个链表结点，因