数据结构的小论文

数据结构的小论文作者学号

名称解释〔1〕数据是信息的载体，是对客观事物的符号表示。通俗的说，但凡能被计算机识别、存取和加工处理的符号、字符、图形、图象、声音、视频信号等一切信息都可以称为数据。〔2〕数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。简言之，数据结构是指数据之间的关系，即数据的组织形式。〔3〕数据元素之间的逻辑关系，称为数据的逻辑结构。〔4〕数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。〔5〕线性结构是指数据元素之间存在“一对一”关系的逻辑结构。〔6〕非线性结构是指数据元素之间存在“一对一”或“一对多”关系的逻辑结构。〔除了线性结构以外的树形结构和图形结构等统称为非线性结构〕。二、名词解释〔1〕线性表——线性表是具有相同数据类型的n〔n>=0〕个数据元素的有限序列。其逻辑特征反映了结点间一对一的关系，是一种线性结构。〔2〕顺序表——用一组地址连续的存储单元依次顺序存储线性表的数据元素〔相邻结点存放在相邻的物理位置〕，称为顺序表。它是一种随机存取结构，可以通过公式来计算结点的存取地址。〔3〕单链表——单链表的每个结点都有两个域，一个数据域和一个指针域，称之为单链表。〔4〕双链表——以链表形式存储的线性表，其结点包含一个数据域和两个指针域，称之为双链表。〔5〕循环链表——假设线性链表的最后一个结点的指针指向头结点，使得链表头尾结点相连，就构成了循环链表。〔6〕存储密度——存储密度定义为结点数据本身所占的存储量与结点结构实际分配的存储量的比值。顺序表的存储密度等于1；链表结构存储密度小于1。三.名词解释〔1〕栈只允许在一端进行插入或删除操作的线性表称为栈。其最大的特点是“后进先出”。〔2〕顺序栈采用顺序存储结构的栈称为顺序栈。〔3〕链栈采用链式存储结构的栈称为链栈。四.名词解释〔1〕队列只允许在一端进行插入，另一端进行删除操作的线性表称为队列。其最大的特点是“先进先出”。〔2〕顺序队列采用顺序存储结构的队列称为顺序队列。〔3〕链队列采用链式存储结构的称队列为链队列。〔4〕循环队列为了解决顺序队列中“假溢出”现象，将队列的存储空间想象为一个首尾相链的环〔即把队头元素与对尾元素链结起来〕，存储在其中的队列称为循环队列。五、名词解释〔1〕字符串由零个或多个字符组成的有限序列称为字符串〔简称串〕。〔2〕空白串由一个或多个空格组成的串称为空白串〔也称为空格串〕。〔3〕空串长度为零的字符串称为空串。〔请注意空串和空白串的区别〕〔4〕顺序串串的顺序存储结构简称为顺序串。〔5〕链式串串的链式存储结构简称为链式串。〔6〕模式匹配子串的定位运算又称为模式匹配。六、名词解释〔1〕结点——树的结点包含一个数据及假设干指向其子树的分支。〔2〕结点的度——结点所拥有的子树数称为该结点的度。〔3〕树的度——树中各结点度的最大值称为该树的度。〔4〕二叉树——一棵非空的二叉树，每个结点至多只有两棵子树，分别称为左子树和右子树，左、右子树的次序不能任意交换，且左右子树又分别是一棵二叉树。〔5〕哈夫曼树——带权路径长度最小的二叉树，即最优二叉树，也称为哈夫曼树。七．名称解释〔1〕有向图——在一个图中，如果每条边都有方向，那么称该图有向图。〔2〕无向图——在一个图中，如果每条边都没有方向，那么称该图为无向图。〔3〕完全有向图——在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，那么称该图为有向完全图。〔在一个含有n个顶点的有向完全图中，有n(n-1)条弧。〕〔4〕最小生成树——假设无向连通图是一个网，那么它的所有生成树中必有一棵边的权值之和为最小的生成树，简称为最小生成树。建立一个好的C语言数据课程设计的要求是：可读性较强：〔1〕、结构严谨，都采用模块化设计采用了多文件结构，不同的文件实现了不同的功能，最好能够将每个模块的函数都在相应的头文件中声明并带有功能注解。〔2〕、较详细的注释使得程序更容易阅读。在每个函数、每种数据类型的定义、每条关键语句都不得有相应的注释。〔3〕、书写标准：在输入编辑源程序时我们力争使程序语句更标准〔用上面提到的格式标准〕。〔4〕标识符〔如函数名、变量名、数据类型名〕命名有讲究：采用操作_对象的命名规那么，如creat_train);表示创立火车链表之意，尽量使标识符“词能达意”，增强可读性。容易维护：很强的健壮性：支持数据更新：功能比拟完善：比拟友好的界面：数据结构的概念数据结构是计算机科学与技术专业的专业根底课，是十分重要的核心课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，要想更好地运用计算机来解决实际问题，仅掌握几种计算机程序设计语言是难以应付众多复杂的课题的。要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握好数据结构的有关知识。打好“数据结构”这门课程的扎实根底，对于学习计算机专业的其他课程，如操作系统、编译原理、数据库管理系统、软件工程、人工智能等都是十分有益的。有关概念和术语在系统地学习数据结构知识之前，先对一些根本概念和术语赋予确切的含义。数据〔Data〕是信息的载体，它能够被计算机识别、存储和加工处理。它是计算机程序加工的原料，应用程序处理各种各样的数据。计算机科学中，所谓数据就是计算机加工处理的对象，它可以是数值数据，也可以是非数值数据。数值数据是一些整数、实数或复数，主要用于工程计算、科学计算和商务处理等；非数值数据包括字符、文字、图形、图像、语音等。数据元素〔DataElement〕是数据的根本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。例如，学生信息检索系统中学生信息表中的一个记录、八皇后问题中状态树的一个状态、教学方案编排问题中的一个顶点等，都被称为一个数据元素。有时，一个数据元素可由假设干个数据项〔DataItem〕组成，例如，学籍管理系统中学生信息表的每一个数据元素就是一个学生记录。它包括学生的学号、姓名、性别、籍贯、出生年月、成绩等数据项。这些数据项可以分为两种：一种叫做初等项，如学生的性别、籍贯等，这些数据项是在数据处理时不能再分割的最小单位；另一种叫做组合项，如学生的成绩，它可以再划分为数学、物理、化学等更小的项。通常，在解决实际应用问题时是把每个学生记录当作一个根本单位进行访问和处理的。数据对象〔DataObject〕或数据元素类〔DataElementClass〕是具有相同性质的数据元素的集合。在某个具体问题中，数据元素都具有相同的性质〔元素值不一定相等〕，属于同一数据对象〔数据元素类〕，数据元素是数据元素类的一个实例。例如，在交通咨询系统的交通网中，所有的顶点是一个数据元素类，顶点A和顶点B各自代表一个城市，是该数据元素类中的两个实例，其数据元素的值分别为A和B。数据结构〔DataStructure〕是指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结构。根据数据元素间关系的不同特性，通常有以下四类根本的结构：⑴集合结构。在集合结构中，数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构。⑵线性结构。该结构的数据元素之间存在着一对一的关系。⑶树型结构。该结构的数据元素之间存在着一对多的关系。⑷图形结构。该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构。数据结构课程的内容数据结构与数学、计算机硬件和软件有十分密切的关系。数据结构是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术专业的核心课程，是高级程序设计语言、编译原理、操作系统、数据库、人工智能等课程的根底。同时，数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。数据结构课程集中讨论软件开发过程中的设计阶段、同时设计编码和分析阶段的假设干根本问题。此外，为了构造出好的数据结构及其实现，还需考虑数据结构及其实现的评价与选择。因此，数据结构的内容包括三个层次的五个“要素”，如图1.5所示。数据结构的核心技术是分解与抽象。通过分解可以划分出数据的三个层次；再通过抽象，舍弃数据元素的具体内容，就得到逻辑结构。类似地，通过分解将处理要求划分成各种功能，再通过抽象舍弃实现细节，就得到运算的定义。上述两个方面的结合使我们将问题变换为数据结构。这是一个从具体〔即具体问题〕到抽象〔即数据结构〕的过程。然后，通过增加对实现细节的考虑进一步得到存储结构和实现运算，从而完成设计任务。这是一个从抽象〔即数据结构〕到具体〔即具体实现〕的过程。熟练地掌握这两个过程是数据结构课程在专业技能培养方面的根本目标。数据结构作为一门独立的课程在国外是从1968年才开始的，但在此之前其有关内容已散见于编译原理及操作系统之中。20世纪60年代中期，美国的一些大学开始设立有关课程，但当时的课程名称并不叫数据结构。1968年美国唐.欧.克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《根本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。从20世纪60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越重视数据结构。从70年代中期到80年代，各种版本的数据结构著作相继出现。目前，数据结构的开展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和开展，如多维图形数据结构等；另一方面，从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新的趋势，越来越被人们所重视。算法特性算法〔Algorithm〕是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。一个算法应该具有以下特性：⑴有穷性。一个算法必须在有穷步之后结束，即必须在有限时间内完成。⑵确定性。算法的每一步必须有确切的定义，无二义性。算法的执行对应着的相同的输入仅有唯一的一条路经。⑶可行性。算法中的每一步都可以通过已经实现的根本运算的有限次执行得以实现。⑷输入。一个算法具有零个或多个输入，这些输入取自特定的数据对象集合。⑸输出。一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系。经典例题——迷宫数字迷宫求解求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。如图1示:图1在此介绍如何使用栈的方式来完成。为防止检查迷宫边界的麻烦,事先将迷宫的四周用上了墙壁。在程序中我们可以用二维数组来表示迷宫,其中1代表墙壁,0代表通路如图2示:此时,从入口出发,顺某一方向向前探索,假设能走通。那么继续往前走,否那么沿原路退回,换一个方向再继续探索,直到所有可能的通路都探索到为止。在探索下一通路时,为保证每一方向都能遍历到,我们按图示东、南、西、北的顺序进行,在程序中用0、1、2、3来表示四个方向,仍然用数组来存放方向,坐标变化在图中巳标出。在以试错法一遍又一遍查找可行路径时,必须利用栈的特性,将刚走过的位置,也就是由现有位置(i,j)移至新位置(g,h)时,就先将(i,j)存入栈里,以备无路前进时后退之用,另外,有一重要数据也必须一起存入栈里,就是当由(g,h)位置退回至(i,j)位置时,要重新查找新路时的新方向d,因此存入栈的数据有i,j,d,为了防止在由(i,j)走到(g,h)时,又由(g,h)走回(i,j),但凡走过的点,其迷宫值将由0变成2,在后退时又得将2复原成0。具体算法如下:#defineSIZE7#defineCOL5#defineROW5#include<stdio.h>intmaze[SIZE][SIZE];/*存放迷宫*/typedefstruct{intvert;inthoriz;}offsets;offsetsmove[4]={{0,1},{1,0},{0,-1},{-1,0}};/*存放四个方向的坐标修改值*/typedefstructstack{intx;inty;intz;structstack*next;}STACK;voidpush(STACK**stk1,inti,intj,intd){STACK*top;top=(STACK*)malloc(sizeof(STACK));top->x=i;top->y=j;top->z=d;top->next=*stk1;3stk1=top;}/*入栈函数*/voidpop(STACK**stk1,int*p1,int*p2,int*p3){STACK*top;if(*stk1==NULL)printf("stackunderflow!");else{*p1=(*stk1)->x;*p2=(*stk1)->y;*p3=(*stk1)->z;top=*stk1;*stk1=(*3stk1)->next;free(top);}}/*出栈函数*/voidprint_ants()/*打印迷宫*/{inti,j;for(i=1;i<SIZE-1;i++,printf("\n"))for(j=1;j<SIZE-1;j++)printf("%3d",maze[i][j]);printf("