2023年7月20日发(作者：)

据结构与算法设计关系

摘要：分别介绍数据结构和算法设计研究的内容，以及两者之间的联系和区别，最后举例说说明两者之间的联系。

关键词：数据结构 算法设计 存储 复杂度

正文：

一，数据结构研究的内容

在大二的时候，我们学习了《数据结构教程》课程，从中我们知道了，数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

现在我们知道了数据结构是指数据以及相互之间的关系，可以看做是相互之间存在着某种特定的关系的数据元素的集合，因此，可以把数据结构看成是带结构的数据元素的集合，数据结构包括以下几个方面，同时也是数据结构要研究的内容。

1， 数据元素之间的逻辑关系，即数据的逻辑结构，数据的逻辑结构师从逻辑关系（主要是相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的，因此数据的逻辑结构可以看做是从具体问题抽象出来的数学模型；

2， 数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，也称为数据的物理结构，数据的存储结构师逻辑结构用计算机语言的实现或在计算机中的表示（亦成文映象），也就是逻辑结构在计算机中的存储方式，也是依赖于计算机语言的；

3， 施加在该数据上的操作，即数据的运算，数据运算时定义在数据的逻辑结构上的，每种逻辑结构都有一种相应的运算。

以上是数据结构的包括的内容，也是数据结构研究的内容，其中每个方面又包括许多小的方面，逻辑结构包括集合，线性结构，树形结构，图形结构等，存储结构包括顺序存储结构，链式存储结构，索性存储结构，哈希（或散列）存储结构。

当然，在我们大学期间，不能感受到数据结构研究内容的深刻，但是数据结构研究的内容非常广，而却有着非常重要的意义。

二，算法设计研究的内容

通过大二一年的学习，以及动手实践，我们应该对算法非常熟悉了。算法是什么？算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。当面临某个问题时，需要找到用计算机解决这个问题的方法和步骤，算法是解决这个问题的方法和步骤的描述。

算法是计算机学科中最具有方法论性质的核心概念，被誉为计算机学科的灵魂。算法由操作，控制结构，数据结构3要素组成。算法的基本特征包括又穷性，确定性，可行性。以上是算法的一些基本特征，那么算法设计研究的内容是什么了，算法设计研究的内容包括以下几个方面。

1. 算法实现平台有很多种类，它们的函数库，类库也有较大差异，但必须具备的最基本操作功能是相同的，操作包括：算术运算，关系比较，逻辑运算，数据传送。

2. 一个算法功能的实现不仅取决于所选用的操作，还取决于各操作之间的执行顺序，即控制结构，算法的控制结构给出了算法的框架，决定了各操作的执行顺序。

1 3. 算法操作的对象是数据，数据间的逻辑关系，数据的存储方式以及处理方式就是数据的数据结构。

以上就是算法设计研究的内容，我是从算法的3要素来看算法设计研究的内容的。算法设计研究的内容也非常广，我们不能单凭我们大学学的知识去看算法设计的研究，我们学的只是九牛一毛，所以需要我们去多阅读一些关于算法研究方面的书籍。

三，两者之间的联系与区别

在介绍数据结构研究的内容的时候，就提到了两者之间的关系，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。由此可见数据结构和算法设计密不可分，好的数据结构也需要好的算法设计才能实现。

在介绍算法设计研究内容的时候，我们可以知道算法操作的对象是数据，数据间的逻辑结构，数据的存储方式，简而言之，算法操作的对象是数据结构。由此可见，数据结构也是算法设计研究的一方面，说明两者有着密不可分的关系。

但是两者也有着不同的地方，数据结构重在研究数据以及数据之间的关系，不会着重于其实现的过程，但是算法设计不仅要考虑到数据之间的关系，也要分析实现的过程，并要分析最优的算法实现，以及算法效率，空间利用率。

四，举例说明

下面举一些有关两者之间联系的例子，并简要说明。

例子：给定一个文本文件，要求统计给定单词在文本中出现的总次数，并检索输出某个单词出现在文本中的行号、在该行中出现的次数以及位置。

程序如下：

#include

#include

#include

#include

#include

#define MAXSTRLEN 64

void GetNext(char T[MAXSTRLEN],int (&next)[64])

{int i,j;i=1;next[1]=j=0;

while(i<(int)T[0])

if(j==0||T[i]==T[j])

{++i;++j;next[i]=j;}

else j=next[j];

for(j=1;j<(int)T[0];j++)

{printf("next[%d]=%-3d",j,next[j]);

if((j)%5==0) printf("n");}

cout<

}

void GetNext(char T[MAXSTRLEN],int (&next)[64],int m)

2 {int i,j;i=0;next[0]=-1;

for(j=1;j

{i=next[j-1];

while(T[j]!=T[i+1]&&i>=0) i=next[i];

if(T[j]==T[i+1]) next[j]=i+1;

else next[j]=-1;}

for(j=0;j<=m;j++)

{printf("next[%d]=%-3d",j,next[j]);

if((j+1)%5==0) printf("n");}

cout<

}

void GetNextV al(charT[MAXSTRLEN],int (&next)[64])

{int i,j;i=1;next[1]=j=0;

while(i<(int)T[0])

if(j==0||T[i]==T[j])

{++i;++j;

if(T[i]!=T[j]) next[i]=j;

else next[i]=next[j];}

else j=next[j];

for(i=1;i<(int)T[0];i++)

{printf("next[%d]=%-3d",i,next[i]);

if(i%5==0) cout<

cout<

}

int IndexKMP(char S[MAXSTRLEN],char T[MAXSTRLEN],int (&next)[64])

{int i,j,n,m;i=j=1;

n=(int)S[0];m=(int)T[0];

while((i

if(j==0||S[i]==T[j]) {++i;++j;}

else j=next[j];

if(j>=m) return i+1-m;

else return 0;

}

int IndexKMP(char S[MAXSTRLEN],char T[MAXSTRLEN],int (&next)[64],int pos)

{int i,j;i=pos;j=1;

while((i<(int)S[0]||j<(int)T[0])&&T[j]!='0'&&S[i]!='0')

if(j==0||S[i]==T[j]) {++i;++j;}

3 else j=next[j];

if(j>=(int)T[0]) return i+1-(int)T[0];

else return 0;

}

int IndexKMP(char S[MAXSTRLEN],char T[MAXSTRLEN],int (&next)[64],int n,int m)

{int i,j;i=j=0;

while(i

if(S[i]==T[j]) {++i;++j;}

else if(j==0) i++;

else j=next[j-1]+1;

if(j

else return i-m+1;

}

int IndexBF(char S[MAXSTRLEN],char T[MAXSTRLEN],int pos)

{int i,j;i=pos;j=1;

while(i<=S[0]&&j<=T[0])

if(S[i]==T[j]) {++i;++j;}

else {i=i-j+2;j=1;}

if(j>T[0]) return i-T[0];

else return 0;

}

void main()

{printf("运行结果:n");

int Index,N,M,next[64]={0};

char s[MAXSTRLEN],t[MAXSTRLEN];

printf("GetNext-IndexKMP 的结果:n");

printf("输入主串 s:");gets(s);

printf("输入模式串 t:");gets(t);

N=strlen(s);M=strlen(t);

printf("主串 s 长=%dn",N);

printf(" 模式串 t 长=%dn",M);

GetNext(t,next,M);

Index=IndexKMP(s,t,next,N,M);

if(Index!=-1)

printf("模式串在主串的位置从第%d 个字符开始n",Index);

else printf("主串 s 中不含模式串 tn");

printf("GetNext-IndexKMP 的结果:n");

4 s[0]=N;t[0]=M;

GetNext(t,next);

Index=IndexKMP(s,t,next,1);

if(Index)

printf("模式串在主串的位置从第%d 个字符开始n",Index);

else printf("主串 s 中不含模式串 tn");

printf("GetNextV al-IndexKMP的结果:n");

GetNextV al(t,next);

Index=IndexKMP(s,t,next,1);

if(Index)

printf("模式串在主串的位置从第%d 个字符开始n",Index);

else printf("主串 s 中不含模式串 tn");

printf("GetNext-IndexKMP 的结果:n");

GetNext(t,next);

Index=IndexKMP(s,t,next);

if(Index)

printf("模式串 t 在主串 s 中的位置从第%d 个字符开始n",Index);

else printf("主串 s 中不含模式串 tn");

printf("IndexBF 的结果:n");

Index=IndexBF(s,t,1);

if(Index)

printf("模式串 t 在主串 s 中的位置从第%d 个字符开始n",Index);

else printf("主串 s 中不含模式串 tn");

();}

这个程序的思路大致可以分为以下几个方面：

(1) 定义一个串变量；

(2) 定义文本文件；

(3) 输入文件名，打开该文件；

(4) 循环读入文本行，写入文本文件，其过程如下：

while(不是文件输入结束){

读入一文本行至串变量；

串变量写入文件；

输入是否结束输入标志；

｝

(5) 关闭文件。

本程序用到了顺序存储结构，也利用到了串的一些操作，串是非数值处理中的主要对象，如在信息检索、文本编辑、符号处理等许多领域，得到越来越广泛的应用。在串的基本操作中，在主串中查找模式串的模式匹配算法是文本处理中最常用、 最重要的

5 操作之一， 称为模式匹配或串匹配， 就是求子串在主串中首次出现的位置。朴素模式匹配算法的基本思路是将给定字串与主串从第一个字符开始比较，找到首次与子串完全匹配的子串为止，并记住该位置。但为了实现统计子串出现的个数，不仅需要从主串的第一个字符位置开始比较，而且需要从主串的任一位置检索匹配字符串。为了实现这个过程，因此需要找到一种比较好的算法设计思路。

C语言中以"0"表示串值的终结。此时的串长为隐含值，显然不便于进行某些串操作。在这种存储结构表示时实现串求子串操作如下：求子串 SubStrmg(&Sub,S,pos,len)过程即为复制字符序列的过程， 将串S 中从第 pos 个字符开始长度为 len 的字符序列复制到串 Sub 中。显然，本操作不会有需截断的情况，但有可能产生用户给出的参数不符合操作的初始条件，当参数非法时，返回 ERROR这种思路顺利的解决了这个问题。

通过这个例子我们也看到了数据结构与算法设计之间的关系，两者互相影响，在做程序设计的时候，都要考虑到两方面的的设计。

参考文献：

【1】 李春葆 尹为民. 《数据结构教程》. 清华大学出版社. 2009. 572千字

【2】 吕国英. 《算法设计与分析》 清华大学出版社. 2009. 469千字

6