算法与数据结构的关系(6页).doc
-算法与数据结构的关系-第 6 页算法与数据结构的关系摘要：何为数据；算法分析研究的内容；数据结构研究的内容；算法与数据结构的联系与区别；数据结构的选择对算法效率的影响。关键词：算法、数据结构、程序正文：一、 数据结构研究的内容：为了了解什么是数据结构先必须明白数据的概念。数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。例如，日常生活中使用的各种文字、数字、和特定的符号都是数据。从计算机的角度来看，数据是所有能被输入到计算机中，且能被计算机处理的符号的集合。他是计算机处理信息的某种特定的符号表示形式。计算机解决问题的实质是对数据进行加工处理。另外，数据元素是数据（集合）中的一个“个体”，是数据的基本单位。数据结构是指数据以及相互之间的关系，可以看做是相互之间存在的某种特定关系的数据元素的集合，因此，可以吧数据结构看成是带结构的数据元素的集合。数据结构研究的内容可以包含以下几个方面：（1） 数据元素之间的逻辑关系，即数据的逻辑结构；（2） 数据元素及其关系在计算机存储其中的存储方式，即数据的存储结构，也称为数据的物理结构；（3） 施加在该数据结构上的操作，即数据运算。常见的数据逻辑结构包括：集合、线性结构、树形结构、图形结构等。常见的数据存储结构包括：顺序存储结构、链式存储结构、索引存储结构、哈希存储结构（也叫散列存储结构）。二、 算法分析研究的内容：算法是指在解决问题时按照某种机械步骤一定可以得到问题的结果（有解时给出解，无解时给出无解的结论）的处理过程。简言之，算法就是计算机解决问题的步骤。当面临某个问题时，需要找到用计算机解决这个问题的方法和步骤，算法就是解决这个问题的方法和步骤的描述。所谓机械步骤是指，算法中有待执行的运算和操作，必须是相当基本的。换言之，他们都是能够精确地被计算机运行的算法，计算机甚至不需要掌握算法的含义，即可根据该算法的每一步骤要求，进行操作并最终得出正确的结果。算法由操作、控制结构、数据结构3要素构成。算法分析的主要任务是对设计出的每一个具体的算法，利用数学工具，讨论其复杂度。对算法的分析一方面能深刻地理解问题的本质以及可能的求解技术，另一方面可以探讨某种具体算法实用于哪类问题，或某类问题宜采用哪种算法。算法分析就是研究算法从而达到优化计算机解决问题的效率的目的。对算法的分析和评价，一般应考虑正确性、可维护性、可读性、运算量、占用存储空间等诸多因素。其中评价算法的3条主要标准是：（1） 算法实现所耗费的时间；（2） 算法实现所好费的存储空间，其中主要考虑辅助存储空间；（3） 算法应易于理解，易于编码，易于调试等。其中时间复杂度是评价算法优劣的一条最重要的标准。三、 数据结构与算法的联系：算法与数据结构关系密切。两者既有联系又有区别，下面就这两个方面进行分别讨论。（1）数据结构与算法的联系：程序=算法+数据结构。数据结构是算法实现的基础，算法总是要依赖于某种数据结构来实现的。往往是在发展一种算法的时候，构建了适合于这种算法的数据结构。算法的操作对象是数据结构。算法的设计和选择要同时结合数据结构，简单地说数据结构的设计就是选择存储方式，如确定问题中的信息是用数组存储还是用普通的变量存储或其他更加复杂的数据结构。算法设计的实质就是对实际问题要处理的数据选择一种恰当的存储结构，并在选定的存储结构上设计一个好的算法。不同的数据结构的设计将导致差异很大的算法。数据结构是算法设计的基础。用一个形象的比喻来解释：开采煤矿过程中，煤矿以各种形式深埋于地下。矿体的结构就像相当于计算机领域的数据结构，而煤就相当于一个个数据元素。开采煤矿然后运输、加工这些“操作”技术就相当于算法。显然，如何开采，如何运输必须考虑到煤矿的存储（物理）结构，只拥有开采技术而没有煤矿是没有任何意义的。算法设计必须考虑到数据结构，算法设计是不可能独立于数据结构的。另外，数据结构的设计和选择需要为算法服务。如果某种数据结构不利于算法实现它将没有太大的实际意义。知道某种数据结构的典型操作才能设计出好的算法。总之，算法的设计同时伴有数据结构的设计，两者都是为最终解决问题服务的。（2）数据结构与算法的区别：数据结构关注的是数据的逻辑结构、存储结构以及基本操作，而算法更多的是关注如何在数据结构的基础上解决实际问题。算法是编程思想，数据结构则是这些思想的逻辑基础。四、 数据结构与算法的关系举例：例如：有若干学生数据，每个学生数据包括学号（学生编号唯一）、姓名、班号和若干门课程成绩（每个学生所选的科目数可能不同，假设最多6们），要求设计一个程序输出每个学生的学号、姓名、平均分以及每门课的平均分。现在有三种数据存储方案。方案一 将学生的全部数据项放在一个表中，一个学生的全部数据对应一条记录。由于课程最多可选6们，对应的成绩也应有6个。对应的数据结构如下：Struct studint no;char name10;int classno;int deg1;int deg2;int deg3;int deg4;int deg5;int deg6;方案二 将学生的全部数据项放在一个表中，但一个学生的一门课程成绩对应一条记录。这样成绩项只需要一个，为了区分不同课程成绩，需要增加一个课程编号项目。对应数据结构如下：struct studInt no;Char name10;Int classno;Int causeno;Int deg;方案三 将学生的学号、姓名、班号放在一个表中，讲成绩数据放在另一个表中，两者通过学号关联。前者一个学生对应一条记录，后者一门课程成绩对应一条记录。对应的数据结构如下：struct studnint no;char name10;int bno;struct studdint no;int cno;int deg;选择不同的数据结构就必须选择不同的算法，比较三种实现方法方案存储空间执行时间算法简洁性综合评价方案一中好差差方案二差差好中方案三好中好好参考文献：数据结构教程清华大学出版社算法设计与分析清华大学出版社算法与数据结构清华大学出版社数据结构与算法国防工业出版社设计一待排序的线性表以顺序存储结构存储，试写出冒泡排序算法。参考程序如下：#include “stdio.h”#define N 10main( ) int aN+1;int i,j,t;for(i=1;i<=N;i+) scanf(“%d”,&ai);printf(“n”);for(j=1;j<N;j+) for(i=1;i<N-j;i+) if(ai>ai+1) t=ai; ai=ai+1; ai+1=t;printf(“the sorted numbers:n”);for(i=1;i<=N;i+) printf(“%4d”,ai);#include<stdio.h>#include<stdlib.h>#define max_list_size 1000typedef struct lnode *list_pointer;typedef struct lnode int data; list_pointer link;list_node;void insert(list_pointer *ptr) list_pointer temp; temp = (list_pointer)malloc (sizeof (list_node); temp->data = rand()%max_list_size; temp->link = *ptr; *ptr = temp;void display(list_pointer ptr) while(ptr) printf("%5d", ptr->data); ptr = ptr->link; void BUBBLESORT(list_pointer *ptr) list_pointer p, q, r, s, t; t = NULL; s = *ptr; while(s->link) /这行以下三行为初始化部分 p = NULL; q = s; r = s->link; while(r) /循环来交换位置，直到得到最大或最小数 if(q->data > r->data) if(!p) q->link = r->link; r->link = q; s = r; else q->link = r->link; r->link = q; p->link = r; p = q; q = r; r = r->link; p->link = q->link;/将得到最大或最小值插入t所指向链表 q->link = t; t = q; s ->link = t;/ s->link 循环结束后， s 中尚且剩一个最小的元素 t = s; *ptr = t;int main() int i; list_pointer ptr = NULL; printf("结点数：%5dn", max_list_size); for( i = 0; i != max_list_size; i+) insert(&ptr); display(ptr); printf("nn"); BUBBLESORT(&ptr); display(ptr); system("PAUSE");
