《(补充)数据结构与算法.doc》由会员分享，可在线阅读，更多相关《(补充)数据结构与算法.doc（20页珍藏版）》请在金锄头文库上搜索。
1、数据结构：数据结构是由一个逻辑结构 S 和 S 上的一个基本运算集构成的整体( S ，)。数据结构的基本任务：数据结构的设计和实现。数据的形式有很多种： 数据的逻辑结构分为 4 种基本类型： 集合：集合中任何两个数据元素之间都没有逻辑关系，组织形式松散。 线性结构：线性结构中的结点按逻辑关系依次排列形成一个“锁链”。 树形结构：树形结构具有分支、层次特性，其形态有点象自然界中的树。 图状结构：图状结构中的结点按逻辑关系互相缠绕，任何两个结点都可以邻接。运算：是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。根据操作的效果，可将运算分成以下两种基本类型： 加工型运算 其操作改变了原逻辑结构的“
2、值”，如结点个数、某些结点的内容等；如：初始化、插入、删除、更新等操作。 引用型运算 其操作不改变原逻辑结构的“值”，只从中提取某些信息作为运算的结果。如：查找、读取等操作。算法：算法就是解决问题的方法和步骤，可以用语言来描述。根据描述算法语言的不同，将算法分为三类：运行终止的程序可执行部分、伪语言算法和非形式算法。非形式算法：用自然语言(如汉语)，同时可能还使用了程序设计语言或伪程序设计语言描述的算法称为非形式算法。算法与程序的关系：算法和程序都是用来表达解决问题的逻辑步骤，但算法独立于具体的计算机，与具体的程序设计语言无关，而程序正好相反；程序是算法，但算法不一定是程序。算法分析通常从以下
3、几个方面评价算法(包括程序)的质量： 正确性 算法应能正确地实现预定的功能(即处理要求)。 易读性 算法应易于阅读和理解，以便于调试、修改和扩充。 健壮性 当环境发生变化(如遇到非法输入)时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果。 高效性 即达到所需要的时空性能。一个算法的时空性能是指该算法的时间性能(或时间效率)和空间性能(或空间效率)。 最坏情况时间复杂性和平均时间复杂性统称为时间复杂性(或时间复杂度)，用 T ( n ) O ( f ( n )表示。其中 f ( n )是算法中频度最大的那条语句频度的数量级。例：求下列算法的时间复杂度。(1)for (i=0; in;
4、 i+) x+;【解答】：时间复杂度为O(n)。(2)for (i=0; in; i+) for (j=0; j=i; j+) x+;【解答】：时间复杂度为O(n2)。(3)i=1; while (in) i*=2;【解答】：时间复杂度为O(log2n)。/*设k次，则2k=n，所以k=log2n*/例：下列程序段的时间复杂性的量级为 。for ( i=1 ；i=n；i+) for ( j=i ；j=0，称为线性表的长度，简称表长。当n=0时线性表为空表，记作：L=（）。元素ai-1称为ai的直接前趋，ai+1称为ai的直接后继。顺序表：顺序表是线性表的顺序存储结构，是指在一个足够大的连续的存
5、储空间里，将线性表中的元素按照逻辑上的次序依次进行存储。这样得到的线性表称为顺序表。顺序表的结构如下图所示：（P17） 其中数组datamaxlen用来存储线性表中的各个元素，此外，设置一个变量listlen表示顺序表中的元素个数（表长）。顺序表的类型定义如下：（P17）#define maxsize 100 /假设元素个数不超过100typedef struct datatype datamaxsize; /顺序表中元素的类型用datatype泛指 int last; /表长sqlist;由上述定义不难发现，顺序表具有这样的特点：逻辑上相邻的元素，其存储地址也相邻。顺序表中基本运算的实现1初
6、始化顺序表建立一个空的顺序表L，只需将表长置为0即可。void initiate(sqlist *L) L-last=0; 2求表长即返回顺序表L的last值。int length(sqlist L) return (L.last); 3按给定序号取元素序号为i的元素ai在数组中的下标为i-1，若该元素存在，则返回相应的数组元素值。void get (sqlist L，int i, datatype *x) if（iL.listlen）error(该元素不存在); else *x= L.datai-1;4查找（定位） locate(L,x)：依次将顺序表L中的每个元素与给定的值x进行比较。若找
7、到则返回其序号（下标+1），否则返回0。int locate (sqlist L, datatype x) int i; for ( i=0; iL.listlen; i+) if (L.datai=x) return (i+1); return(0);5插入 insert(L,i,x)：算法思想如下：（1）首先要判断能否进行插入，即表是否为满以及插入位置i是否合理。（2）如果可以进行插入，需要执行下列步骤： 为了给待插入元素x腾出一个空位，需要将aian往后移一位。 将x插入到第i个位置上。 插入后，顺序表L的长度last要加1。void insert (sqlist *L, datatyp
8、e x, int i ) int j; if (iL-last+1) error (插入位置错误); else if (L- last =maxsize) error (溢出); else for (j=L- last -1; j=i-1; j-) /往后移动元素 L-dataj+1=L-dataj; L-datai-1=x; /插入x L- last +; /修改表长 算法分析：（P20）当插入位置i=1，2n+1时，移动元素的次数分别为n，n-1,1，0。因此平均移动次数为：(0+1+n) / ( n+1) = n / 2，所以插入算法的时间复杂度为O(n)。6删除 delete (L,i
9、)：void delete (sqlist *L, int i) int j； if (L- last L- last | i=0) error(无法删除);else for (j=i；j last -1；j+) L-dataj-1=L-dataj； L- last -； 算法的时间复杂度为O(n)。单链表在顺序表中插入和删除元素时，需要做大量移动元素的操作，比较浪费时间。要想在插入和删除时不需移动元素，可以采用链式存储结构，此时线性表中每个元素称为一个结点，如下图所示： 每个结点包括两个部分：数据域data，用于存储元素的值。指针域next，用于存储后继结点的地址。采用链式存储结构的线性表称
10、为链表。本节介绍的链表，每个结点只有一个指针域，称为单链表。单链表的简单操作（1）静态链表：用数组来存储元素的值和地址。（2）动态链表：根据实际需要，临时动态地分配存储空间来存储线性表中的元素。单链表的类型定义如下：typedef struct datatype data; /存放元素值 struct node *next; /指示后继结点的指针node;一个完整的单链表head如下图所示：其中，head称为头指针，第一个元素a1所在的结点称为首结点（第一个元素结点）。有时，为了使某些运算更方便实现，在首结点之前增加了一个结点，称为头结点，并称此时的链表为带头结点的单链表。单链表中基本运算的实
11、现1建空表一个空的单链表只有一个头结点，且后继指针为空，如下图所示： void initiate (node *L) L= (node *) malloc (sizeof (node); /产生一个头结点 L-next=NULL; /设置后继指针为空2求单链表的长度即求出单链表中元素的个数，用p指针依次指向每个元素结点并进行计数，算法如下：int length (node *L) int n=0; node *p=L-next; while (p!=NULL) n+; p=p-next; return n ;3按给定序号取元素node *get (node *L, int i ) node *
12、p=L-next; int j=0; while ( j!=i & p!=NULL ) p=p-next; j+; return p;4查找（定位）将单链表中各结点的data值逐个地与x进行比较，若找到则返回该结点的指针，否则继续往后搜索，若直到表尾都没有找到，则返回空指针。算法如下：node *locate (node *L, datatype x ) node *p=L-next; while (p!=NULL & p-data!=x ) p=p-next; return p;5插入如下图所示，插入操作主要由两条语句来实现：s-next=p-next； p-next=s； 完整的算法如下：void insert (node *L, int i, datatype x ) node *p=L; int k=0; while (k!=i-1 & p!=NULL) p=p-next; k+; if (p=NULL) error (插入序号错); else s= (node * ) malloc (sizeof (node); s-data=x; s-next=p-next; p-next=s;
