当前位置：文档之家› 数据结构《第4章串存储与基本操作的实现》

数据结构《第4章串存储与基本操作的实现》

第四章串存储与基本操作的实现

本章学习要点

◆熟悉串的相关概念以及串与线性表的关系

◆重点掌握串的定长存储、堆分配存储的表示方法与基本操作的实现

◆了解串的各种存储结构，能根据需要合理选用串的存储结构解决实际问题

“串”(string)，是字符串的简称，它是一种特殊的线性表，其特殊性在于组成线性表的数据元素是单个字符。字符串在计算机处理实际问题中使用非常广泛，比如人名、地名、商品名、设备名等均为字符串。同样在文字编辑、自然语言理解和翻译、源程序的编辑和修改等方面，都离不开对字符串的处理。

4.1串的基本概念

4.1.1串的概念

1．串的定义

串（string）是由n个字符组成的有限序列，记为：S=”a0a1a2…a n-1” (n≥0)。

其中，S是串的名字，字符序列a0a1a2…a n-1是串的值，a i(0≤i≤n-1)可以是字母、数字或其他字符元素；由于在C语言系统中数组元素的下标是从0开始的，所以串中所含元素的序号等于该元素的下标值加1；串中所含字符的个数n称为该串的长度，长度为0的字符串称为空串（null string）。

从串的定义可以看出，串实际上是数据元素为字符的特殊的线性表。

例如：

（1）A=“X123” (长度为4的串)

（2）B=“12345654321” (长度为11的串)

（3）C=“Bei Jing” (长度为8的串)

（4）D=“” (长度为0的空串)

（5）E=“This is a string” (长度为16的串)

（6）F=“ is a ” (长度为6的串)

2．子串、主串和位置

串中任意连续的字符组成的子序列称为该串的子串；相应地，包含子串的串称为主串。串中的字符在串序列中的序号称为该字符在该串中的位置；子串的第一个字符在主串中的位置称为子串在主串中的位置。显然，串为其自身的子串，并规定空串为任何串的子串。显然，在不考虑空子串的情况下，一个长度为n的字符串具有n(n+1)/2个子串。

例如：

在上例的(6)中串F就是(5)中串E的子串，且子串F在主串E中的位置是5。由于空格符也是一个字符，所以在串G=“abc defghne”中包含有子串“c def”,而串“cdef”不是串G的子串。串G中第一个字符…e?的位置是6，第二个字符…e?的位置是11。

3．串的比较

如果两个串的长度相等且对应位置上的字符相同，则称这两个串相等。两个串A、B的比较过程是：从前往后逐个比较对应位置上的字符的ASCII码值，直到不相等或有一个字符串结束为止，此时的情况有以下几种：

（1）两个串同时结束，表示A等于B；

（2）A中字符的ASCII码值大于B中相应位置上字符的ASCII码值或B串结束，表示A大于B；（3）B中字符的ASCII码值大于A中相应位置上字符的ASCII码值或A串结束，表示A小于B。

例如：

“abc”=“abc”,“abc”<“abcd”,“abxy”>“abcdefg”,“132”>“123456”

“ABab”<“abAB”,“3+2”>“2+3”。

4．空格串

由一个或多个空格字符组成的串称为空格串，空格串的长度为串中所含空格字符的个数。在串操作中不要将空格串和空串混淆。

4.1.2串的基本操作

尽管串的定义和线性表极为相似，但是串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以单个元素作为操作对象，比如对线性表的查找、访问、插入、删除和排序等；而在串的基本操作中，通常以串整体或串的一部分（子串）作为操作对象，比如子串的查找、截取子串、删除一个子串、插入子串和子串替换等操作。

串的基本操作主要有：

（1）StrAssign(&T,chars)—由字符串常量chars生成字符串T的操作。

（2）StrCopy(&T,S)—由串S复制生成串T的操作。

（3）StrCompare(S,T)—若S=T返回0，S>T返回正数，S

（4）StrLength(S)—返回串S的长度。

（5）Concat(&T,S1,S2)—将串S1和S2连接起来生成串T的操作。

（6）SubString(&Sub,S,pos,len)—以串S中pos位置开始的len个字符生成子串Sub的操作。

（7）Index(S,T,pos)—返回子串T在S中pos个字符以后出现的位置。

（8）Replace(&S,T,V)—将串S中所有不重叠子串T替换为串V的操作。

（9）StrInsert(&S,pos,T)—在串S中第pos个字符前插入串T的操作。

（10）StrDelete(&S,pos,len)—删除串S中第pos个字符开始的len个字符的操作。

4.2串的存储表示与实现

既然串是线性表的特例，所以线性表的两种存储结构对于串也是适用的。在应用中具体选用何种存储结构与串的操作有关，比如对串进行插入和删除操作运算时选用链存储结构较好，对串进行查找和求子串运算时选用顺序存储结构较好。

本章主要介绍串的3种存储表示方法：

（1）串的定长顺序存储表示法

（2）串的堆分配存储表示法

（3）串的块链式存储表示法

4.2.1串的定长顺序存储表示

串的定长顺序存储表示是用一组地址连续的存储单元来存储串中的字符序列。在串的定长顺序存储表示中，按照预定义的大小，为每个定长的串变量分配一个固定长度的存储区，所以可以用定长字符数组来表示。

1．定长顺序存储结构

在C++运行环境中，定长顺序结构定义为：

#include"iostream.h"

#include"stdio.h"

#define MAXLEN 255 //定义串的最大长度为255

typedef char SString[MAXLEN+1]; //定义定长顺序存储类型SString

2．基本操作的C++程序实现

（1）求串长度操作int Length_SS(SString S)

操作返回串S中所含字符的个数，即串的长度；如果S为空串则返回0。

int Length_SS(SString S)

{

int i=0;

while(S[i])i++;

return i;

}

（2）串连接操作int Concat_SS(SString &T,SString S1,SString S2)

该操作将串S1、S2连接生成串T，如果在连接过程中产生了截断（即S1的长度加上S2的长度大于MAXLEN）则返回0，否则返回1。

int Concat_SS(SString &T,SString S1,SString S2)

{

int i,j,k;

i=j=k=0;

while(T[i++]=S1[j++]);

i--;

while(i

{ i++;k++; }

T[i]=0;

if((i==MAXLEN)&&S2[k]) /*判断是否产生截断*/

return(0);

else

return(1);

}

（3）求子串操作int SubString_SS(SString &Sub,SString S,int pos,int len)

该操作截取串S中从第pos个字符开始的连续的len个字符生成子串Sub，如果位置pos和长度len合理则返回1，否则返回0.

int SubString_SS(SString &Sub,SString S,int pos,int len)

{

int i=0;

if(pos<1||len<0||pos+len>Length_SS(S)+1) /*判断位置和长度是否合理*/ return 0;

while(i

{Sub[i]=S[i+pos-1]; i++; }

Sub[i]='\0';

return 1;

}

（4）初始化串操作int StrAssign_SS(SString &T,char *s)

该操作用字符数组s，初始化定长顺序串T。如果不产生截断（长度合理）返回1，否则返回0。

int StrAssign_SS(SString &T,char *s)

{

int i=0;

while(i

T[i]=0;

if((i==MAXLEN)&&s[i]) /*判断是否产生截断*/

return 0;

else return 1;

}

（5）串复制操作void StrCopy_SS(SString &T,SString S)

该操作将定长顺序串S，复制到定长顺序串T。

void StrCopy_SS(SString &T,SString S)

{

int i=0;

while(T[i]=s[i])i++;

}

（6）串比较操作int StrCompare_SS(SString S,SString T)

该操作比较顺序串S、T的大小，如果S>T则返回正数,如果S=T则返回0,否则返回负数。

int StrCompare_SS(SString S,SString T)

{

int i=0;

while(S[i]&&T[i]&&(S[i]==T[i]))i++;

return (int)(S[i]-T[i]);

}

（7）串的替换操作int Replace_SS(SString &S,int n,int m,SString T)

该操作将串S中从第n个字符开始的连续的m个字符替换成串T中的字符，如果n和m的选取合理则返回1，否则返回0。

int Replace_SS(SString &S,int n,int m,SString T)

{

SString S1;

int len=Length_SS(T);

int i=n-1,j=0,k=n+m-1; /*i为开始替换位置，j指向第一个替换字符，k为剩余字符的开始位置*/

if(n<1||m<0||n+m>Length_SS(S)+1||Length_SS(S)+len-m>MAXLEN) /*判断位置是否合理*/ return(0);

StrCopy_SS(S1,S); /*将剩余部分复制到S1中*/

while(S[i++]=T[j++]); /*替换S中指定部分的字符*/

i--;

while(S[i++]=S1[k++]); /*将剩余部分复制到S中*/

return(1);

}

（8）主函数演示程序main()

void main_SS()

{

SString s1,s2,s3,sub,T;

char str1[100],str2[100];

int l1,l2,l3,pos,len,n;

while(1)

{

cout<<"(1)串初始化操作：\n输入两个字符串:\n";

cin.getline(str1,sizeof(str1));

//表示从键盘输入一个可以含有空格字符的长度小于100的字符串到str1中，

//语句“cin>>str1”不能输入空格字符（空格符表示输入结束）且对串的长度不做检查。

cin.getline(str2,sizeof(str2));

StrAssign_SS(s1,str1);

StrAssign_SS(s2,str2);

l1=Length_SS(s1);

l2=Length_SS(s2);

cout<<"(2)求串长操作：\ns1的长度="<

n=StrCompare_SS(s1,s2);

cout<<"(3)串比较操作：\n比较结果为: ";

if(n>0)cout<<"s1>s2\n";

else if(n==0)cout<<"s1=s2\n";

else cout<<"s1

Concat_SS(s3,s1,s2);

cout<<"(4)串连接操作：\ns1+s2="<

l3=Length_SS(s3);

cout<<"s1+s2的长度="<

cout<<"(5)求子串操作：\n输入开始位置和串长(pos len):\n";

cin>>pos>>len;

if(SubString_SS(sub,s3,pos,len))

cout<<"sub="<

else cout<<"位置不正确\n";

cout<<"(6)串替换操作：\n输入替换的位置和字符数(pos len):";

cin>>pos>>len;

cout<<"输入替换串:\n"; cin.get();

cin.getline(str1,sizeof(str1));

StrAssign_SS(T,str1);

if(Replace_SS(s3,pos,len,T))

cout<<"替换结果为:\ns3="<

else cout<<"替换不成功!\n";

}

}（程序运行过程略）

3．定长顺序存储的特点

（1）对于求串长度和串的复制操作而言，其时间复杂度依赖于字符串的长度；

（2）在串删除和串插入操作时必须移动大量的字符；

（3）如果在串输入、串连接、串插入和串替换操作中串值的长度超过MAXLEN，则按约定采取“截尾”法处理，这将导致操作结果的不合理。

4.2.2串的堆分配存储表示

由于串操作基本上是以串整体的形式参与，在应用程序中串变量的长度相差较大，并且在操作中串值长度的变化也比较大。因此，事先为串变量设置固定大小空间的数组不尽合理。

用堆分配存储表示串的方法是：在程序执行过程中，根据串变量值的大小，在堆空间中动态分配一个连续的地址空间来存储串变量中的字符，这样既可以避免产生串操作中的“截断”现象又能合理使用内存空间资源。

1．串的堆分配存储结构

在C++运行环境中，堆分配存储结构定义为

struct HString

{

char *ch; //串变量中字符数组的首地址

int length; //串的长度

};

2．在堆分配存储结构中串基本操作的C++程序实现

（1）串的赋值操作void StrAssign_HS(HString &T,char str[])

该操作由字符串常量str生成一个HString型串T。

void StrAssign_HS(HString &T,char str[])

{

int len=0,i;

while(str[len])len++; //计算串的长度

T.length=len;

if(!len)T.ch=NULL; //对空串进行初始化

else

{

T.ch=new char[len+1]; //在堆内存中分配相应大小的存储空间

for(i=0;T.ch[i]=str[i];i++); //将数据从str复制到T.ch中

}

（2）求串长的操作int Length_HS(HString S)

该操作返回串S的长度，如果S为空串则返回0。

int Length_HS(HString S)

{

return(S.length);

}

（3）串的比较操作int StrComp_HS(HString S,HString T)

该操作比较串S、T的大小。

int StrComp_HS(HString S,HString T)

{ int i;

for(i=0;i

if(S.ch[i]!=T.ch[i])break;

return((int)(S.ch[i]-T.ch[i]));

}

（4）串的清空操作void ClearString_HS(HString &S)

该操作清空串S所占的堆空间。

void ClearString_HS(HString &S)

{

if(S.ch)

{ delete[]S.ch;

S.ch=NULL;

S.length=0;

}

（5）串的连接操作void Concat_HS(HString &T,HString S1,HString S2)

该操作计算串S1、S2的连接串T。

void Concat_HS(HString &T,HString S1,HString S2)

{

int i,j,k;

T.length=S1.length+S2.length;

i=j=k=0;

T.ch=new char[T.length+1]; //分配链接串的储存空间

while(T.ch[i++]=S1.ch[j++]); //将S1复制到T

i--;

while(T.ch[i++]=S2.ch[k++]); //将S2连接到T的末尾

}

（6）求子串的算法int SubString_HS(HString &Sub,HString S,int pos,int len)

该操作求串S中pos个字符开始的len个字符组成的子串Sub，如果位置合理返回1否则返回0。

int SubString_HS(HString &Sub,HString S,int pos,int len)

{

int i;

if(pos<1||len<1||pos+len>S.length+1) return(0); //如果位置不合理时返回0值

Sub.ch=new char[len+1]; //动态分配子串的存储空间

Sub.length=len;

for(i=0;i

Sub.ch[i]=0;

Return(1);

}

（7）串插入操作的算法int StrInsert_HS(HString &S,int pos,HString H)

该操作在串S的第pos个字符前面插入字符串H，如果位置合理返回1，否则返回0。

int StrInsert_HS(HString &S,int pos,HString H)

{

int i,j,k;

HString S1;

if(pos<1||pos>S.length+1) return 0; //位置不合理返回0值

S1.length=S.length+H.length;

S1.ch=new char[S1.length+1]; //重新分配空间

for(i=0;i

k=i; j=0;

while(S1.ch[i++]=H.ch[j++]); //将H插入

i--;

while(S1.ch[i++]=S.ch[k++]); //取S中剩余的内容

delete[]S.ch;

S=S1;

return 1;

}

（8）串替换操作的算法int Replace_HS(HString &S,int n,int m,HString T)

该操作将串S中第n个字符开始的m个字符替换为串T，如果位置n和字符数m合理返回1否则返回0。

int Replace_HS(HString &S,int n,int m,HString T)

{

int i,j=0,k=n+m-1;

HString S1;

if(n<1||m<0||n+m>S.length+1)return(0); //长度或位置不合理

S1.length=S.length+T.length-m;

S1.ch=new char[S1.length+1]; //重新分配储存空间

for(i=0;i

while(S1.ch[i++]=T.ch[j++]); //取T中的内容

i--;

while(S1.ch[i++]=S.ch[k++]); //取S中剩余的部分

delete[]S.ch;

S=S1;

return(1);

}

（9）主函数演示程序main()

void main_HS()

{

HString S1,S2,S,sub,V,T;

SString ss1,ss2;

int n,pos,len;

while(1)

{

cout<<"(1)串初始化操作：\n输入两个字符串:\n";

cin.getline(ss1,sizeof(ss1));

cin.getline(ss2,sizeof(ss2));

StrAssign_HS(S1,ss1);

StrAssign_HS(S2,ss2);

cout<<"(2)求串长操作：\nlen1="<

cout<<"len2="<

cout<<"(3)串比较操作：\n比较大小的结果为：";

n=StrComp_HS(S1,S2);

if(n>0) cout<<"S1>S2\n";

else if(n<0)cout<<"S1

else cout<<"S1==S2\n";

Concat_HS(S,S1,S2);

cout<<"(4)串连接操作：\n:s1+s2="<

cout<<"length="<

cout<<"(5)取子串操作：\n输入取子串的位置和长度(pos len):\n";

cin>>pos>>len;

if(SubString_HS(sub,S,pos,len))

cout<<"sub="<

else

cout<<"位置不对!\n";

cout<<"(6)串插入操作：\n请输入插入位置:"; cin>>pos;cin.get();

cout<<"输入要插入的子串V:\n"; cin.getline(ss1,sizeof(ss1));

StrAssign_HS(V,ss1);

if(StrInsert_HS(S,pos,V))

cout<<"插入结果为s="<

else

cout<<"位置不对!\n";

cout<<"(7)串替换操作；\n输入替换子串的位置和长度(pos len):\n";

cin>>pos>>len;cin.get();

cout<<"输入替换串T:\n"; cin.getline(ss1,sizeof(ss1));

StrAssign_HS(T,ss1);

if(Replace_HS(S,pos,len,T))

cout<<"结果为s="<

else

cout<<"位置不对!\n";

}

3．堆分配存储表示的特点

从以上串基本操作的算法可以看出，堆分配存储结构的串既有顺序存储结构的特点，处理方便，同时在操作中对串的长度又没有任何限制，更显灵活，因此该存储结构在有关字符串处理的应用程

序中常被采用。

4.2.3串的块链式存储表示

1．块链式存储的概念

和线性表的链式存储结构类似，可以采用链表方式存储串。由于串中的每个数据元素是一个字符，在用链表存储串值时，存在一个“结点大小”的问题，即每个结点最多可以存放多少个串中字符。对于串“abcdefghijk ”，如果采用每个结点存放一个字符的链表结构存储，其存储方式如图4.1(a)所示；如果采用每个结点存放三个字符的链表结构存储，其存储方式如图4.1(b)所示。由于串长不一定是结点大小的整数倍，所以在链表的最后一个结点不一定能被串中的字符占满，此时可补上若干个非串值字符…#?（或其它非串值字符）。

为了便于进行串的操作，当以链表存储串值时，除了头指针head 外还可以附设一个指向尾结点的指针tail ，并给出当前串的长度。称如此定义的串的存储结构为串的块链式存储结构。 2．块链式存储结构的表示

在C++运行环境中，可将块链式存储结构表示如下： #define CHUNKSIZE 80 //定义每个结点的大小 struct Chunk {

char ch[CHUNKSIZE]; //块内的字符数组

Chunk* next; //指向下一个结点的指针 }; //块结构的类型定义 struct LString{

Chunk *head,*tail; //串的头指针和尾指针 int curlen; //串的长度

}; //块链式结构的类型定义

在一般情况下，对串的操作只需要从前向后扫描即可，故对串值不必建立双向链表。设尾指针的目的是为了便于进行串的连接操作，在串连接时需要处理第一个串尾结点中的无效字符。 3．块链式存储的存储密度

在串的块链式存储结构中，结点大小的选择很重要，它直接影响到串处理操作的效率。如果块选取的充分大时（可在一个块中存储串的所有字符）即为定长存储；如果每个块只放一个字符时即为链表存储。为了便于研究串值的存储效率我们给出如下存储密度的计算公式：

实际分配的存储位

串值所占的存储位串值的存储密度

假定next 指针变量占用4个字节，每个字符占用1个字节，每个块中存放m 个字符，那么串值的存储密度可以表示为ρ=m/(m+4)。显然，存储密度小（比如每个块存放1个字符时ρ=20%），运算处理方便，但是存储占用量大；存储密度大（比如每个块存放80个字符时ρ=20/21=95%），虽然存储占用量小，但是串值的运算处理（比如串的插入、删除、连接和替换等操作）不太方便。

4．块链式存储表示的特点

在一般情况下，对以块链式存储表示的串进行操作时比较麻烦，比如在串中插入一个子串时可能需要分割结点，连接两个串时，如果第一个串的最后一个结点没有填满，还需要添加其它字符。总的来说，用链表作为串的存储方式是不太实用的。因此，串的块链式存储结构不如定长顺序存储和堆分配存储结构灵活，它占用存储空间大且操作复杂。

4.3串的模式匹配

设S和T是两个给定的串，在串S中寻找串值等于T的子串的过程称为模式匹配。其中，串S 称为主串，串T称为模式。如果在串S中找到等于串T的子串，则称匹配成功；否则匹配失败。模式匹配是各种串处理系统中最重要的操作之一。

模式匹配的操作记为Index(S,T,pos)，该函数的功能是，从串S的第pos个字符开始的字符序列中查找值等于T的子字符串。如果匹配成功，函数返回T在S中第pos个字符以后的串值中第一次出现的开始位置；否则函数返回0值。显然这里隐含要求模式串T不能为空串。

4.3.1串模式匹配的BF算法

模式匹配最简单、最直观的算法是BF（Brute-Force,布鲁特-福斯）算法。该算法在计算过程中，分别利用指针i和指针j指示主串S和模式T中当前正待比较的字符下标。算法的基本思想是：从主串S的第pos个字符起和模式T的第一个字符比较，若相等，则继续逐个比较后面的字符；否则从主串S的下一个字符起再重新和模式T的第一个字符开始逐个比较。以此类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功，函数返回T的第一个字符在S中的位置，否则匹配不成功，函数返回0值。

BF算法表示的串查找函数int IndexBF_SS(SString S,SString T,int pos)的C++语言表示为：

int IndexBF_SS(SString S,SString T,int pos)

{//求子串T在S中从pos个位置开始首次出现的位置

int i=pos-1,j=0;

if(i<0||pos+Length_SS(T)>Length_SS(S)+1)

return(0);

while(S[i+j]&&T[j])

{

if(S[i+j]==T[j])j++; //若字符相等，则继续比较后续字符

else

{i++; j=0;} //若不相等，则重新开始新一轮比较

}

if(!T[j]) return(i+1); //若匹配成功，则返回T首次出现的开始位置

else return(0); //若匹配不成功，则返回0

}

在一般情况下，BF算法的时间复杂度为O(m+n)，其中m,n分别为串S和T的长度。但是在有些情况下，该算法的效率很低。

例如：

S=“aaaaaa……aaaaab”共有52个…a?和1个…b?,T=“aaaaaaab”共有7个…a?和1个…b?。由于每趟比较都是在最后一个字符出现不相等，此时需要将初始位置指针i回溯到i+1的位置上，并从模式的第一个字符开始重新比较。从图4.2所示的匹配过程可以直观地算出，初始位置指针i一共要回溯52-7=45次，总的比较次数为：8×(45+1)=368次。所以，在最坏的情况下BF算法的时间复杂度为O(m×n)。

4.3.2模式匹配的KMP 算法

模式匹配的另一种算法是由D.E.Knuth,J.H.Morris 和V .R.Pratt 同时发现的，称之为克努特-莫里斯-普拉特操作，简称KMP 算法，他是一种改进的模式匹配算法。此算法可使时间复杂度在O(m+n)的数量级上完成串的模式匹配操作。 1．模式的next 数组

模式匹配的KMP 算法是，每当一趟匹配比较过程中出现字符不相同的情况时，不需要回溯指针i,而是利用已经得到的“部分匹配”的结果将模式T 向右“滑动”尽可能远的一段距离后，再继续进行比较。为此需要引入一个有关模式串T 的整型数组next ，其中第j 个元素next[j-1]表示当模式串T 中的第j 个字符与主串S 中相应字符匹配失败时，在模式T 中需要重新和主串S 中该字符进行比较的字符的下标值。

next 数组定义为：

??+=<<=-=其它情况且时当0}1]-T[j ,1],k -T[j k],-T[j 1]-T[k ,T[1],T[0],0|max{01][ j k k j j next

其中next[j]=k 表明，存在整数k 满足条件0

“T[0]T[1]…T[k-1]”=“T[j-k]T[j-k+1]…T[j-1]”，

而对任意的整数k 1(0

“T[0]T[1]…T[k 1-1]”≠“T[j-k 1]T[j-k 1+1]…T[j-1]”

例如：

（1）模式T=“aaaaaaab ”的next 数组为next={-1,0,1,2,3,4,5,6} （2）模式T=“abaabcac ”的next 数组为next={-1,0,0,1,1,2,0,1}

（3）模式T=“ababcabcacbab ”的next 数组为next={-1,0,0,1,2,0,1,2,0,1,0,0,1} 2．next 数组的算法实现

由定义可知，next[0]=-1,next[1]=0，假设现已求得next[0],next[1], …,next[j],那么可以采用以下递推的方法求出next[j+1]。

令k=next[j]，

(1)如果k=-1或T[j]=T[k],则转入步骤(3) (2)取k=next[k],再重复操作(1)、(2) (3)next[j+1]=k+1;

计算next 数组的算法void GetNext(char* T,int* next)用C++语言实现如下 void GetNext(char* T,int* next) { int i=0,k=-1,n=0; next[0]=-1;

while(T[n])n++; //计算模式串T的长度n

while(i

{

if(k==-1||T[i]==T[k]) next[++i]=++k;

else k=next[k];

}

void main()

{

char p[6][50]={"ababcabcacbab","abaabcac","aaabcaab","abcabca","babbabab","abcaabbabcabaac"};

int next[50],i,j;

for(i=0;i<6;i++)

{

GetNext(p[i],next); //计算模式串p[i]的next数组

for(j=0;p[i][j];j++)cout<

cout<

}

}运行结果为：

-1 0 0 1 2 0 1 2 0 1 0 0 1 -1 0 0 1 1 2 0 1 -1 0 1 2 0 0 1 2

-1 0 0 0 1 2 3

-1 0 0 1 1 2 3 2

-1 0 0 0 1 1 2 0 1 2 3 4 2 1 1

3．KMP模式匹配算法的实现

KMP模式匹配算法int Index_KMP(SString S,SString T,int pos)的C++语言实现

int Index_KMP(SString S,SString T,int pos)

{

int i=pos-1,j=0; //i指向S中第一个比较字符，j指向T中第一个字符int m=Length_SS(T), n=Length_SS(S);

int *next=new int[m]; //定义模式T的next数组

if(i<0||pos+m>n+1) return 0; //位置不合理返回0值

GetNext(T,next); //计算next

while(i

{ if(j==-1||S[i]==T[j])

{j++;i++;} //比较后继字符

else j=next[j]; //回溯模式指针j

}

if(j>=m) r eturn(i-m+1); //匹配成功

else return(0);

}

void main()

{ SString S,T;

int pos,n;

cout<<"输入主串S:\n"; cin>>S;

cout<<"输入子串T:\n"; cin>>T;

cout<<"输入位置pos:\n";cin>>pos;

if(n=Index_KMP(S,T,pos))

cout<<"首次匹配地址为:"<

else cout<<"匹配不成功!\n";

}

【例4.1】编写程序，分别计算模式匹配过程中，BF算法和KMP算法的元素比较次数。

（1）函数int IndexBF(SString S,SString T,int& num)的功能是通过BF算法返回串T在S中首次出现的位置，参数num表示匹配过程中元素的比较次数。

int IndexBF(SString S,SString T,int& num)

{ int i=0,j=0;

num=0;

if(i<0||Length_SS(T)>Length_SS(S))

return(0);

while(S[i+j]&&T[j])

{ num++;

if(S[i+j]==T[j])j++; //若字符相等，则继续比较后续字符

else

{i++; j=0;} //若不相等，则重新开始新一轮比较

}

if(!T[j]) return(i+1); //若匹配成功，则返回T首次出现的开始位置

else return(0); //若匹配不成功，则返回0

}

（2）函数int IndexKMP(SString S,SString T,int& num)的功能是通过KMP算法返回串T在S中首次出现的位置，参数num表示匹配过程中字符元素的比较次数。

int IndexKMP(SString S,SString T,int& num)

{

int i=0,j=0; //i指向S中第一个比较字符，j指向T中第一个字符

int m=Length_SS(T), n=Length_SS(S);

int *next=new int[m]; //定义模式T的next数组

if(i<0||m>n) return 0; //位置不合理返回0值

GetNext(T,next); //计算next

num=0;

while(i

{ if(j!=-1)num++;

if(j==-1||S[i]==T[j])

{j++;i++;} //比较后继字符

else j=next[j]; //回溯模式指针j

}

if(j>=m) r eturn(i-m+1); //匹配成功

else return(0);

}

void main()

{

SString S,T;

int n1,n2,num1,num2;

while(1)

{

cout<<"input string S:\n";

cin.getline(S,sizeof(S));

cout<<"input string T:\n";

cin.getline(T,sizeof(T));

n1=IndexBF(S,T,num1);

n2=IndexKMP(S,T,num2);

cout<<"Index_BF:\nn="<

cout<<"Index_KMP:\nn="<

}

程序运行结果为：

input string S:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaab↙

input string T:

aaaaaaab↙

Index_BF:

n=46,num=368

Index_KMP:

n=46,num=98

input string S:

abcdabcdabcdabcde↙

input string T:

abcde↙Index_BF:

n=13,num=29

Index_KMP:

n=13,num=20

input string S: ADBADABBAABADABBADADA↙input string T:

ADABBADADA↙

Index_BF:

n=12,num=32

Index_KMP:

n=12,num=25

用KMP模式匹配算法的比较过程如下：

对于主串为S=“aaaaaa……aaaaab”（其中共有52个…a?和1个…b?）,模式串为T=“aaaaaaab”（其中共有7个…a?和1个…b?）时的比较次数。

首先求得模式T的next数组为next[]={-1,0,1,2,3,4,5,6}，置初值i=0,j=0；

（1）连续比较8次时，i=7,j=7，此时分别指向S的第8个…a?和T中最后的…b?；即S[i]≠T[j]。（2）取j为next[j]=next[7]的值6，即j=6指向T中第7个…a?(表示向后滑动模式T为7-6=1个字符)。（3）比较S[i]和T[j]，均为…a?相同，i++,j++。

（4）此时i的值+1,j=7，分别指向S的下一个…a?和T中最后的…b?；即S[i]≠T[j]，转入（2）继续。（5）重复（2）、（3）、（4）的步骤52-7=45次后，i、j均指向最后的字符…b?,即S[i]=T[j]，

（6）i++,j++操作后j=m(T的长度8)，循环结束，返回i-m+1.

从以上分析的比较过程可知，总的比较次数为：7+2×(52-7)+1=98次（见图4.3）

再如：

主串为S=“abcdabcdabcdabcde”，模式串为T=“abcde”,其next数组为next={-1,0,0,0,0}。那么，可以算出用BF算法时的比较次数为29次。而用KMP算法的比较过程为：

（1）比较5次后滑动模式T:j=next[4]=0,即向右滑动4个字符，此时j=0,i=4；

（2）再次连续比较5次后将模式T向右滑动4个字符，此时j=0,i=9；

以此类推，共需要比较的次数为5×4=20次（见图4.4）。

4.4应用举例

【例4.2】应用BF模式匹配函数IndexBF_SS(S,T,pos)实现算法：

int Replace_S(SString &S,SString T,SString V)

该函数的功能是，将定长存储串S中的所有子串T用定长串V来替换。如果操作成功函数返回值1，否则返回值0。

算法思想

假设模式串T的长度为lt，替换串V的长度为lv，先从pos=1的位置开始查找T在S中出现的位置n，如果操作成功，则将S中第n个开始lt个字符替换为串值V，并且pos=n+lv，继续开始下一轮的查找和替换过程，直到查找失败为止。

算法实现

int Replace_S(SString &S,SString T,SString V)

{

int n,pos=1;

int lt=Length_SS(T),lv=Length_SS(V);

while(n=IndexBF_SS(S,T,pos))

{

if(!Replace_SS(S,n,lt,V))return 0;

pos=n+lv;

}

return 1;

}

【例4.3】应用BF模式匹配函数IndexBF_SS(S,T,pos)实现算法：

int Replace_H(HString &S,HString T,HString V)

该函数的功能是，将堆分配存储串S中的所有子串T用堆分配存储串V来替换。如果操作成功函数返回值1，否则返回值0。

int Replace_H(HString &S,HString T, HString V)

{

int n,pos=1,lt=T.length,lv=V.length;

while(n=IndexBF_SS(S.ch,T.ch,pos))

{ if(!Replace_HS(S,n,lt,V)) return 0;

pos=n+lv;

}

return 1;

}

演示程序代码

串替换函数Replace_S()、Replace_H()的函数调用演示程序

void main ()

{

SString S1,T1,V1;

HString S2,T2,V2;

cout<<"《串替换函数演示程序》:\n";

cout<<"input S:";cin.getline(S1,MAXLEN);

cout<<"input T:";cin.getline(T1,MAXLEN);

cout<<"input V:";cin.getline(V1,MAXLEN);

StrAssign_HS(S2,S1);

StrAssign_HS(T2,T1);

StrAssign_HS(V2,V1);

if(Replace_S(S1,T1,V1))

cout<<"定长替换结果为:\n"<

else

cout<<"定长替换失败!\n";

if(Replace_H(S2,T2,V2))

cout<<"堆分配替换结果为:\n"<

else

cout<<"堆分配替换失败!\n";

}(程序运行结果略)

【例4.4】编程计算定长存储串S中所含不同字符的总数以及该串中每个字符的个数。

算法思想

首先定义结构体类型：struct num{char ch;int n;};以及该类型的数组a[]，其中ch表示字符串S 中的不同字符，n表示字符出现的次数。再对串S中的每个字符ch，在数组a中逐个扫描，如果查找成功，相应的字符数加1，否则在a中添加一个新字符，其个数置为1。

算法实现

void f4_3()

{ SString S;

struct num{char ch;int n;};

num a[MAXLEN];

int i=0,j,k=0;

char ch;

cout<<"输入一个字符串:\n";

cin.getline(S,MAXLEN);

while(ch=S[i++])

{

for(j=0;j

if(ch==a[j].ch) {a[j].n++;break;}

if(j==k){a[k].ch=ch; a[k++].n=1;}

}

cout<<"不同字符共有"<

for(i=0;i

{

cout<

if((i+1)%7==0)cout<

}

cout<

}

4.5习题

一、简答题

1．串和空串有和不同？

2．两个字符串相等的充要条件是什么？

3．串的3种存储表示方法是什么？

4．分别写出下面各个模式串的next数组：

（1）aaabcaab (2)abcabca (3)babbabab (4)abcaabbabcabaac

二、填空题

1．串是一种特殊的线性表，其特殊性主要体现在（）。

2．设有两个串P和Q，那么求Q在P中首次出现的位置的运算被称为（）。

3．设串S=”I AM A TEACHER”，那么S的长度为（）。

4．设S1=“abcdefg”，S2=“pqrst”，函数Con(x,y)返回x和y的连接串，Subs(S,i,j)返回S中从i个字符开始的j个字符组成的子串，Len(S)返回S的长度，则Con(Subs(S1,2,Len(S2)),Subs(S1,Len(S2),2))的结果是（）。

5．在串模式匹配的BF算法中，如果主串S=“ababcabcacbab”，模式串T=“abcac”，匹配过程中的元素比较次数为（）次，如果用KMP算法，其比较次数为（）次。

三、解答题

1．设串以堆分配方式存储，设计一个判等操作的算法Equal(S,T)，如果S与T相等则函数返回1，否则返回0值。

2．设串以定长顺序存储，设计一个串复制操作的算法CopyStr(S,T)，将T的内容复制到S。3．编写一个算法SubsNum(S,T)，返回串T在S中重复出现的次数（子串不能重叠）。

4．编写一个算法MaxNext(T,&m,&n)，该操作计算T中出现的第一个最长重复子串的位置m及其长度n。

5．假定串以堆分配方式存储，编写一个实现串通配符匹配的函数Pattern_Index(S,T)，其中通配符只有???，它可以和任一个字符匹配成功。

6．设串以堆分配方式存储，设计一个串置换操作的算法Replace(S,T,X)。该操作将S中所有不重复的子串T替换为串S。

7．假定串以定长顺序存储，设计一个求最长公共子串的算法MaxSubs(S,T,&m,&n)。该操作返回S、T的最长公共子串在S中首次出现的开始位置m和长度n。

数据结构课程设计报告模板

《数据结构I》三级项目报告大连东软信息学院电子工程系 ××××年××月

三级项目报告注意事项 1. 按照项目要求书写项目报告，条理清晰，数据准确； 2. 项目报告严禁抄袭，如发现抄袭的情况，则抄袭者与被抄袭者均以0分计； 3. 课程结束后报告上交教师，并进行考核与存档。三级项目报告格式规范 1. 正文：宋体，小四号，首行缩进2字符，1.5倍行距，段前段后各0行； 2. 图表：居中，图名用五号字，中文用宋体，英文用“Times New Roman”，位于图表下方，须全文统一。

目录一项目设计方案 (3) 二项目设计分析 (4) 三项目设计成果 (4) 四项目创新创业 (5) 五项目展望 (6) 附录一：项目成员 (6) 附录二：相关代码、电路图等 (6)

一项目设计方案 1、项目名称: 垃圾回收 2、项目要求及系统基本功能： 1）利用数据结构的知识独立完成一个应用系统设计 2）程序正常运行，能够实现基本的数据增加、删除、修改、查询等功能3）体现程序实现算法复杂度优化 4）体现程序的健壮性二项目设计分析 1、系统预期实现基本功能：（结合本系统预期具体实现，描述出对应基本要求(增、删、改、查等)的具体功能） 1. 2. 3. 4. 5. 6. 7. 2、项目模块功能描述（基本分为组织实施组织、程序功能模块编写、系统说明撰写等。其中程序功能子模块实现）模块一：主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块二：主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块n：主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

员工信息管理系统(数据结构)

员工信息管理系统课程设计报告系别：计算机与信息工程系班级： B080501 姓名：李海鹏学号： B08050128 指导教师：张红霞课设时间：2010-6-21到2010-6-25

摘要员工信息管理系统属于信息管理系统。员工信息管理是每个公司不可缺少的。系统用C程序开发，主要在于建立好一个合适的数据结构，并要求程序简洁实用。本系统利用C语言简洁、灵活，数据结构丰富等特点，编写适合公司使用的系统。整个系统使用起来也比较方便，入手简单，操作方便。论文主要介绍了程序设计过程、设计方案以及测试过程，重点讲解了设计过程中的思想，技术解决方案等等。关键字：员工信息管理，C程序，数据结构

前言 (3) 第1章课设题目 (4) 第2章开发运行环境及相关知识 (4) 第3章程序总体设计 (5) 3.1 主要功能模块 (5) 3.2 数据结构 (6) 第4章程序详细设计及实现 (7) 4.1 输入函数 (7) 4.2 排序函数 (7) 4.3 显示函数 (7) 4.4 查找函数 (7) 4.5更改函数 (8) 4.6 删除函数 (8) 4.7 主函数 (8) 4.8 其他函数 (9) 第5章系统功能测试 (9) 5.1 系统主界面 (9) 5.2 输入数据 (9) 5.3 显示数据 (10) 5.4 信息排序 (10) 5.5 更改信息 (11) 5.6 删除信息 (11) 第6章课设总结 (12) 第7章程序清单 (13) 参考文献 (22)

前言本课程设计旨在理论学习和基础实验的基础上，开发规模较大的程序，掌握应用计算机编程解决实际问题的基本方法，熟悉C程序开发的全过程，掌握数据结构的使用方法，熟练应用各种数据结构。本次任务是根据给定的数据和程序，应用单向链表处理一系列公司员工的信息。通过整个程序开发的过程，提高综合应用C语言的能力、编程和调试能力，为进一步学习相关专业课程创建较扎实的理论基础和实践基础。报告将分6个章节来详细讲述本次课设题目的开发过程。第1章主要描述课设的题目及要求；第2章来介绍程序开发运行环境；第3章介绍程序主体设计，网络程序概要；第4章是对程序进行详细分析，对各个函数进行详细描述，并阐述程序实现技术等信息；第5章为测试过程，主要用测试过程中的图片来表述最终信息；第6章也是最后一章，为本次实践活动的心得体会。

数据结构课程设计报告

《数据结构与算法》课程设计报告学号：班级序号：姓名：指导教师：成绩：中国地质大学信息工程学院地理信息系统系 2011年12 月

1．需求规格说明【问题描述】利用哈夫曼编码进行对已有文件进行重新编码可以大大提高减小文件大小，减少存储空间。但是，这要求在首先对一个现有文件进行编码行成新的文件，也就是压缩。在文件使用时，再对压缩文件进行解压缩，也就是译码，复原原有文件。试为完成此功能，写一个压缩/解压缩软件。【基本要求】一个完整的系统应具有以下功能：（1）压缩准备。读取指定被压缩文件，对文件进行分析，建立哈夫曼树，并给出分析结果（包括数据集大小，每个数据的权值，压缩前后文件的大小），在屏幕上输出。（2）压缩。利用已建好的哈夫曼树，对文件进行编码，并将哈夫曼编码及文件编码后的数据一起写入文件中，形成压缩文件(*.Haf)。（3）解压缩。打开已有压缩文件(*.Haf)，读取其中的哈夫曼编码，构建哈夫曼树，读取其中的数据，进行译码后，写入文件，完成解压缩。（4）程序使用命令行方式运行压缩命令：SZip A Test.Haf 1.doc 解压缩命令：SZip X Test.Haf 2.doc或SZip X Test.Haf 用户输入的命令不正确时，给出提示。（5）使用面向对象的思想编程，压缩/解压缩、哈夫曼构建功能分别构建类实现。 2．总体分析与设计（1）设计思想： 1、压缩准备：1> 读文件，逐个读取字符，统计频率 2> 建立哈夫曼树 3> 获得哈弗曼编码 2、压缩过程： 1> 建立一个新文件，将储存权值和字符的对象数组取存储在文件头

数据结构实验总结报告

数据结构实验总结报告一、调试过程中遇到哪些问题？（1）在二叉树的调试中，从广义表生成二叉树的模块花了较多时间调试。由于一开始设计的广义表的字符串表示没有思考清晰，处理只有一个孩子的节点时发生了混乱。调试之初不以为是设计的问题，从而在代码上花了不少时间调试。目前的设计是： Tree = Identifier(Node,Node) Node = Identifier | () | Tree Identifier = ASCII Character 例子：a(b((),f),c(d,e)) 这样便消除了歧义，保证只有一个孩子的节点和叶节点的处理中不存在问题。（2）Huffman树的调试花了较长时间。Huffman编码本身并不难处理，麻烦的是输入输出。①Huffman编码后的文件是按位存储的，因此需要位运算。 ②文件结尾要刷新缓冲区，这里容易引发边界错误。在实际编程时，首先编写了屏幕输入输出（用0、1表示二进制位）的版本，然后再加入二进制文件的读写模块。主要调试时间在后者。二、要让演示版压缩程序具有实用性，哪些地方有待改进？（1）压缩文件的最后一字节问题。压缩文件的最后一字节不一定对齐到字节边界，因此可能有几个多余的0，而这些多余的0可能恰好构成一个Huffman编码。解码程序无法获知这个编码是否属于源文件的一部分。因此有的文件解压后末尾可能出现一个多余的字节。解决方案： ①在压缩文件头部写入源文件的总长度（字节数）。需要四个字节来存储这个信息（假定文件长度不超过4GB）。 ②增加第257个字符（在一个字节的0~255之外）用于EOF。对于较长的文件，

会造成较大的损耗。 ③在压缩文件头写入源文件的总长度%256的值，需要一个字节。由于最后一个字节存在或不存在会影响文件总长%256的值，因此可以根据这个值判断整个压缩文件的最后一字节末尾的0是否在源文件中存在。（2）压缩程序的效率问题。在编写压缩解压程序时 ①编写了屏幕输入输出的版本 ②将输入输出语句用位运算封装成一次一个字节的文件输入输出版本 ③为提高输入输出效率，减少系统调用次数，增加了8KB的输入输出缓存窗口这样一来，每写一位二进制位，就要在内部进行两次函数调用。如果将这些代码合并起来，再针对位运算进行一些优化，显然不利于代码的可读性，但对程序的执行速度将有一定提高。（3）程序界面更加人性化。 Huffman Tree Demo (C) 2011-12-16 boj Usage: huffman [-c file] [-u file] output_file -c Compress file. e.g. huffman -c test.txt test.huff -u Uncompress file. e.g. huffman -u test.huff test.txt 目前的程序提示如上所示。如果要求实用性，可以考虑加入其他人性化的功能。三、调研常用的压缩算法，对这些算法进行比较分析（一）无损压缩算法 ①RLE RLE又叫Run Length Encoding，是一个针对无损压缩的非常简单的算法。它用重复字节和重复的次数来简单描述来代替重复的字节。尽管简单并且对于通常的压缩非常低效，但它有的时候却非常有用（例如，JPEG就使用它）。变体1：重复次数+字符文本字符串：A A A B B B C C C C D D D D，编码后得到：3 A 3 B 4 C 4 D。

数据结构课程设计报告模板

课程设计说明书课程名称：数据结构专业：班级：姓名：学号：指导教师：成绩：完成日期：年月日

任务书题目：黑白棋系统设计内容及要求： 1.课程设计任务内容通过玩家与电脑双方的交替下棋，在一个8行8列的方格中，进行棋子的相互交替翻转。反复循环下棋，最后让双方的棋子填满整个方格。再根据循环遍历方格程序，判断玩家与电脑双方的棋子数。进行大小判断，最红给出胜负的一方。并根据y/n选项，判断是否要进行下一局的游戏。 2.课程设计要求实现黑白两色棋子的对峙开发环境：vc++6.0 实现目标：（1）熟悉的运用c语言程序编写代码。（2）能够理清整个程序的运行过程并绘画流程图（3）了解如何定义局部变量和整体变量；（4）学会上机调试程序，发现问题，并解决（5）学习使用C++程序来了解游戏原理。（6）学习用文档书写程序说明

摘要本文的研究工作在于利用计算机模拟人脑进行下黑白棋，计算机下棋是人工智能领域中的一个研究热点，多年以来，随着计算机技术和人工智能技术的不断发展，计算机下棋的水平得到了长足的进步该程序的最终胜负是由棋盘上岗双方的棋子的个数来判断的，多的一方为胜，少的一方为负。所以该程序主要运用的战术有削弱对手行动战术、四角优先战术、在游戏开局和中局时，程序采用削弱对手行动力战术，即尽量减少对手能够落子的位置；在游戏终局时则采用最大贪吃战术，即尽可能多的吃掉对手的棋子；而四角优先战术则是贯穿游戏的始终，棋盘的四角围稳定角，不会被对手吃掉，所以这里是兵家的必争之地，在阻止对手进角的同时，自己却又要努力的进角。关键词：黑白棋；编程；设计

数据结构第三章习题18页word

第三章习题 1. 按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答： ⑴如进站的车厢序列为123，则可能得到的出站车厢序列是什么？ ⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。 2. 设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执行下列4步操作：（1）输出队首元素；（2）把队首元素值插入到队尾；（3）删除队首元素；（4）再次删除队首元素。直到队列成为空队列为止，得到输出序列：（1） A、C、E、C、C （2） A、C、E （3） A、C、E、C、C、C （4） A、C、E、C 3. 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？

4. 按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程： A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ 5. 试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1& 序列2’模式的字符序列。其中序列1和序列2中都不含字符’&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。 6. 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。 7. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。 8. 要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。 9. 简述以下算法的功能（其中栈和队列的元素类型均为int）：（1）void proc_1(Stack S) { int i, n, A[255]; n=0; while(!EmptyStack(S))

数据结构课程设计报告

编号课程设计题目 1、一元稀疏多项式计算器 2、模拟浏览器操作程序 3、背包问题的求解 4、八皇后问题二级学院计算机科学与工程学院专业计算机科学与技术班级 2011级 37-3班学生姓名 XX 学号 XXXXXXXXXX 指导教师 XXXXX 评阅教师时间 1、一元稀疏多项式计算器【实验内容】一元稀疏多项式计算器。

【问题描述】设计一个一元稀疏多项式简单计算器。【需求分析】其基本功能包括：（1）输入并建立多项式；（2）输出多项式，输出形式为整数序列为：n,c1,e1,c2,e2,……,cn,en,其中n 是多项式的项数，ci，ei分别是第i项的系数和指数，序列按指数降序排序；（3）多项式a和b相减，建立多项a+b；（4）多项式a和b相减，建立多项式a-b；（5）计算多项式在x处的值；（6）计算器的仿真界面（选做）；【概要设计】 -=ADT=- { void input(Jd *ha,Jd *hb)； void sort(dnode *h)

dnode *operate(dnode *a,dnode *b) float qiuzhi(int x,dnode *h) f",sum); printf("\n"); } 【运行结果及分析】（1）输入多项式：

（2）输出多项式（多项式格式为：c1x^e1+c2x^e2+…+cnx^en）：（3）实现多项式a和b相加：（4）实现多项式a和b相减：（5）计算多项式在x处的值：

2、模拟浏览器操作程序【实验内容】模拟浏览器操作程序【问题描述】标准Web浏览器具有在最近访问的网页间后退和前进的功能。实现这些功能的一个方法是：使用两个栈，追踪可以后退和前进而能够到达的网页。在本题中，要求模拟实现这一功能。【需求分析】需要支持以下指令： BACK：将当前页推到“前进栈”的顶部。取出“后退栈”中顶端的页面，使它成为当前页。若“后退栈”是空的，忽略该命令。 FORWARD：将当前页推到“后退栈”的顶部。取出“前进栈”中顶部的页面，使它成为当前页。如果“前进栈”是空的，忽略该命令。 VISIT：将当前页推到“后退栈”的顶部。使URL特指当前页。清空“前进栈”。 QUIT：退出浏览器。假设浏览器首先加载的网页URL是：http：

非结构化存储方案

非结构化数据存储方案一、存储类型体系： 1.1 存储类型体系结构图 1.2 存储类型体系描述（1）块存储：将存储区域划分为固定大小的小块，是传统裸存设备的存储空间对外暴露方式。块存储系统将大量磁盘设备通过SCSI/SAS或FC SAN与存储服务器连接，服务器直接通过SCSI/SAS或FC协议控制和访问数据。主要包括DAS和SAN两种存储方式。对比如下图：

（2）分布式文件存储：文件存储以标准文件系统接口形式向应用系统提供海量非结构化数据存储空间。分布式文件系统把分布在局域网内各个计算机上的共享文件夹集合成一个虚拟共享文件夹，将整个分布式文件资源以统一的视图呈现给用户。它对用户和应用程序屏蔽各个节点计算机底层文件系统的差异，提供用户方便的管理资源的手段和统一的访问接口。主要包括NAS 和HDFS 两种存储方式。 a) 网络附加存储NAS 结构如图：

b)HDFS分布式文件系统存储结构如图：（3）对象存储：对象存储为海量非结构化数据提供Key-Value这种通过键-值查找数据文件的存储模式，提供了基于对象的访问接口，有效地合并了NAS和SAN的存储结构优势，通过高层次的抽象具有NAS的跨平台共享数据优点，支持直接访问具有SAN的高性能和交换网络结构的可伸缩性。主要包括swift和ceph两种实现形式。 a)Swift，OpenStack Object Storage（Swift）是OpenStack项目的子项目之一，被称为对象存储。它构建在比较便宜的标准硬件存储基础设施之上，无需采用RAID（磁盘冗余阵列），通过在软件层面引入一致性散列技术和数据冗余性，牺牲一定程度的数据一致性来达到高可用性和可伸缩性，支持多租户模式、容器和对象读写操作，适合解决非结构化数据存储问题。 b)ceph，Linux下PB级分布式文件系统，可轻松扩展PB容量，提供了对多种工作负载的高性能和高可靠性。它大致分为四部分：客户端（数据用户），元数据服务器（缓存和同步分布式元数据），一个对象存储集群（包括数据和元数据），以及最后的集群监视器（执行监视功能）。

数据结构物流信息管理系统

2014-2015学年第一学期学号《数据结构》课程设计报告题目：物流信息管理系统专业：计算机科学与技术班级：姓名：学号：指导教师：成绩：目录摘要 (1) 1设计内容及要求 (1) 1.1内容描述 (1) 1.2基本要求 (1) 2详细设计 (1) 2.1概要设计 (1) 2.2功能模块详细设计 (1) 2.3程序流程图 (4) 3源代码 (5)

4程序结果 (9) 5总结 (12) 6参考文献 (12)

摘要物流信息管理系统是利用单链表实现信息管理，进而掌握C语言中的结构体，链表，指针，函数（系统函数，自定义函数）等C语言知识。本文通过利用模块化程序设计思想，使用单链表和结构体等编写出的创建，删除，查询等功能的物流信息管理系统。通过完成这个程序设计让我们熟悉并掌握c语言中使用结构体，单链表，指针，函数，和模块化设计思想。关键词结构体，链表，指针，函数 1设计内容及要求 1.1内容描述对客户的基本信息进行存储，利用取货号来查询顾客信息，核对信息后方可取货。 1.2基本要求 1.采用一定的存储结构进行客户信息的存储； 2.对客户的信息可以进行修改、删除、查询； 2详细设计 2.1概要设计本系统用到的主要数据结构为数组和文件。一个数组对应一个客户，里面用3个字符串分别存储着用户的客户号、姓名和电话号码。然后将数组写入文件，查询时读取文件，提取相应信息。 2.2功能模块详细设计本程序运用链表对客户信息进行存储，首先对结点进行定义，结点中的数据域分别定义了取货人的取货号、身份证、姓名、电话号码，其中身份证用了字符型数组进行定义，然后定义了客户取货链表，每添加一个取货人，先分配内存，再添加取货人的信息，之后将链表中最后一个指针指向该新的取货人，删除时，需先找到该取货人前面的取货人，直接将其指针指向删除取货人的下一个取货人，修改信息时，先找到该去人，选择修改的内容，再进行修改。 void create(Linklist &h){ Linklist s,t; int j=1; char x; h=(Listnode *)malloc(sizeof(Listnode)); h->next=NULL;t=h; while(j){ s=(Listnode*)malloc(sizeof(Listnode)); printf("顾客取货号为%d\n",i); s->customer.m=i; printf("请输入身份证号码："); scanf("%c",&x);

数据结构课程设计报告

数据结构课程设计设计说明书 TSP 问题起止日期：2016 年 6 月27 日至2016 年7 月 1 日学生姓名班级学号成绩指导教师( 签字) 2016 年7 月 1 日

目录第1 章需求分析.................................................................................1... 1.1 简介 (1) 1.2 系统的开发背景 (1) 1.3 研究现状 (1) 第2 章概要设计.................................................................................2... 2.1 系统开发环境和技术介绍 (2) 2.2 系统需求分析 (2) 2.2.1 总体功能分析 (2) 2.2.2 核心功能分析 (3) 第3 章详细设计...................................................................................4... 3.1 系统开发流程 (4) 3.2 系统模块设计 (4) 3.3 系统结构 (6) 3.2 系统流程图 (6) 第4 章调试分析...................................................................................7... 4.1 程序逻辑调试 (7) 4.2 系统界面调试 (8) 第5 章测试结果...................................................................................9... 5.1 测试环境 (9) 5.2 输入输出测试项目 (9) 5.3 测试结果 (10) 结论.....................................................................................................1..1.. 参考文献................................................................................................1..1. 附录.......................................................................................................1..2..

非结构化数据管理系统

非结构化数据管理系统 1 范围本标准规定了非结构化数据管理系统的功能性要求和质量要求。本标准适用于非结构化数据管理系统产品的研制、开发和测试。 2 符合性对于非结构化数据管理系统是否符合本标准的规定如下： a)非结构化数据管理系统若满足本标准基本要求中的所有要求，则称其满足本标准的基本要求； b)非结构化数据管理系统在满足所有基本要求的前提下，若满足某部分扩展要求，则称其满足本标准的基本要求和该部分扩展要求； c)非结构化数据管理系统若满足本标准基本要求和扩展要求中的所有要求，则称其满足本标准的所有要求。 3 规范性引用文件下列文件对于本文件的应用是必不可少的。凡是注日期的引用文件，仅注日期的版本适用于本文件。凡是不注日期的引用文件，其最新版本（包括所有的修改单）适用于本文件。 GB 18030—2005 信息技术中文编码字符集 GB/T AAAAA-AAAA 非结构化数据访问接口规范 4 术语和定义下列术语和定义适用于本文件。 4.1 非结构化数据unstructured data 没有明确结构约束的数据，如文本、图像、音频、视频等。 4.2 非结构化数据管理系统unstructured data management system 对非结构化数据进行管理、操作的大型基础软件，提供非结构化数据存储、特征抽取、索引、查询等管理功能。 5 缩略语下列缩略语适用于本文件。 IDF：逆向文件频率 (Inverse Document Frequency) MFCC：梅尔频率倒谱系数（Mel Frequency Cepstrum Coefficient）

PB：千万亿字节（Peta Byte） SIFT：尺度不变特征转换（Scale-invariant Feature Transform） TF：词频 (Term Frequency) 6 功能性要求 6.1 总体要求非结构化数据管理系统的总体要求如下： a)应包括存储与计算设施、存储管理、特征抽取、索引管理、查询处理、访问接口、管理工具七个基本组成部分； b)宜包括转换加载、分析挖掘、可视展现三个扩展组成部分。 6.2 存储与计算设施 6.2.1 基本要求存储与计算设施基本要求如下： a)应支持磁盘、磁盘阵列、内存存储、键值存储、关系型存储、分布式文件系统等一种或多种存储设施； b)应支持单机、并行计算集群、分布式计算集群等一种或多种计算设施。 6.2.2 扩展要求无。 6.3 存储管理 6.3.1 基本要求存储管理基本要求如下： a)应提供涵盖原始数据、基本属性、底层特征、语义特征的概念层存储建模功能； b)应提供逻辑层的存储建模功能； c)支持整型、浮点型、布尔型、字符串、日期、日期时间、二进制块等基本数据类型； d)支持向量、矩阵、关联等数据类型； e)应支持根据建好的逻辑层存储模型创建存储实例； f)应支持在创建好的存储实例上插入、修改、删除非结构化数据； g)应支持删除存储实例； h)应支持非结构化数据操作的原子性。 6.3.2 扩展要求存储管理扩展要求如下： a)应支持全局事务的定义并保证事务的原子性、一致性、隔离性和持久性； b)应支持数据类型的多值结构和层次结构； c)应支持在不同的存储设施上创建存储实例并实现自动映射； d)应支持PB级数据存储。 6.4 特征抽取

数据结构物流信息管理系统设计

数据结构物流信息管理系统设计 Revised on November 25, 2020

目录摘要...................................................1 1设计内容及要求...........................................................................1 内容描述..............................................................................1 基本要求..............................................................................1 2详细设计....................................................................................1 概要设计..............................................................................1 功能模块详细设计..................................................................1 程序流程图...........................................................................4 3源代码 .....................................................................................5 4程序结果....................................................................................9 5总结...........................................................................................12 6参考文献 (12) 数据结构物流信息管理系统设计【最新资料，WORD 文档，可编辑修改】

数据结构第三章习题

数据结构第三章习题 3．1 单项选择题 2.一个栈的入栈序列a, b, c, d, e, 则栈的不可能的输出序列是。 A. edcba B. Decba C. Dceab D. abcde 3. 若已知一个栈的入栈序列是1，2，3，………..n, 其输出序列为p1, p2, p3,……,pn, 若p1=n, 则pi为。 . B. n=I C. n- i+1 D.不确定4．栈结构通常采用的两种存储结构是。 A. 顺序存储结构和链表存储结构 B. 散链方式和索引方式 C.链表存储结构和数组 D. 线性存储结构和非线性存储结构5．判定一个栈ST（最多元素为m0）为空的条件是。 A. ST->top<>0 B. ST->top=0 >top<>m0 >top=m0 6．判定一个栈ST（最多元素为m0）为栈满的条件是。 A. ST->top!=0 >top==0 >top!=m0 >top==m0 7.栈的特点是，队列的特点是。 A先进先出 B. 先进后出 8. 一个队列的入栈序列是1，2，3，4，则队列的输出序列是。 A. 4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D. 3,2,4,1 9. 判定一个队列QU(最多元素为m0)为空的条件是。 >rear- QU->front==m0 >rear- QU->front-1==m0 >front== QU->rear D. QU->front== QU->rear+1

10.判定一个队列QU（最多元素为m0）为满队列的条件是。 >rear- QU->front==m0 >rear- QU->front-1==m0 >front== QU->rear >front== QU->rear+1 11. 判定一个循环队列QU(最多元素为m0)为空的条件是。 A. QU->front== （QU->rear+1）%m0 B. QU->front！= （QU->rear+1）%m0 >front== QU->rear >front！= QU->rear 12. 判定一个循环队列QU（最多元素为m0）为满队列的条件是。 A. QU->front== （QU->rear+1）%m0 B. QU->front！= （QU->rear+1）%m0 >front== QU->rear >front！= QU->rear+1 12. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行。 HS->next=s; A. s->next=HS->next; HS->next=s; B. s->next=HS; HS=s; C. s->next=HS; HS=HS->next; 13. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行。 A x=HS; HS=HS->next; B. x=HS->data; C. HS=HS->next; x=HS->data;

数据结构课程设计报告-学生成绩管理系统[]

武汉理工大学华夏学院课程设计报告书课程名称：数据结构课程设计题目：用C语言实现成绩统计程序的设计系名：信息工程系专业班级：计算机1121 姓名：吴涛学号：10210412104 指导教师:司晓梅 2016年3 月20日

武汉理工大学华夏学院信息工程系课程设计任务书课程名称：数据结构课程设计指导教师：司晓梅班级名称：计算机1121 开课系、教研室：信息系计算机一、课程设计目的与任务《数据结构》课程设计是为训练学生的数据组织能力和提高程序设计能力而设置的增强实践能力的课程。目的：学习数据结构课程，旨在使学生学会分析研究数据对象的特性，学会数据的组织方法，以便选择合适的数据的逻辑结构和存储结构以及相应操作，把现实世界中的问题转换为计算机内部的表示和处理，这就是一个良好的程序设计技能训练的过程。提高学生的程序设计能力、掌握基本知识、基本技能，提高算法设计质量与程序设计素质的培养就是本门课程的课程设计的目的。任务：根据题目要求，完成算法设计与程序实现，并按规定写出课程设计报告。二、课程设计的内容与基本要求设计题目：用C语言实现成绩统计程序的设计〔问题描述〕给出n个学生的m门课程的考试成绩信息，每条信息由姓名、课程代号与分数组成，要求设计算法：（1）输入每个人的各门课程的成绩，计算每人的平均成绩；（2）按平均成绩的高低次序，打印出个人的名次，平均成绩相同的为同一名次；（3）按名次列出每个学生的姓名和各科成绩；〔基本要求〕学生的考试成绩必须通过键盘输入，且需对输出进行格式控制；〔算法提示〕可以用选择排序、冒泡排序等多种排序算法求解；具体要完成的任务是： A. 编制完成上述问题的C语言程序、进行程序调试并能得出正确的运行结果。 B. 写出规范的课程设计报告书；三、课程设计步骤及时间进度和场地安排时间：1周地点：现代教育中心具体时间安排如下：第一天：布置题目，确定任务、查找相关资料第二天～第四天：功能分析，编写程序，调试程序、运行系统；第五天上午：撰写设计报告；第五天下午：程序验收、答辩。四、课程设计考核及评分标准

关于数据结构课程设计心得体会范文

关于数据结构课程设计心得体会范文心得体会是指一种读书、实践后所写的感受性文字。是指将学习的东西运用到实践中去，通过实践反思学习内容并记录下来的文字，近似于经验总结。下面是小编搜集的关于数据结构课程设计心得体会范文，希望对你有所帮助。关于数据结构课程设计心得体会(1) 这学期开始两周时间是我们自己选题上机的时间，这学期开始两周时间是我们自己选题上机的时间，虽然上机时间只有短短两个星期但从中确实学到了不少知识。上机时间只有短短两个星期但从中确实学到了不少知识。数据结构可以说是计算机里一门基础课程，据结构可以说是计算机里一门基础课程，但我觉得我们一低计算机里一门基础课程定要把基础学扎实，定要把基础学扎实，然而这次短短的上机帮我又重新巩固了 c 语言知识，让我的水平又一部的提高。数据结构这是一门语言知识让我的水平又一部的提高。数据结构这是一门知识，纯属于设计的科目，它需用把理论变为上机调试。纯属于设计的科目，它需用把理论变为上机调试。它对我们来说具有一定的难度。它是其它编程语言的一门基本学科。来说具有一定的难度。它是其它编程语言的一门基本学科。我选的上机题目是交叉合并两个链表，对这个题目，我选的上机题目是交叉合并两个链表，对这个题目，我觉得很基础。刚开始调试代码的时候有时就是一个很小的错觉得很基础。刚开始调试代码的时候有时就是一个很小的错调试代码的时候误，导致整个程序不能运行，然而开始的我还没从暑假的状导致整个程序不能运行，态转到学习上，每当程序错误时我都非常焦躁，态转到学习上，每当程序错误时我都非常焦躁，甚至想到了放弃，但我最终找到了状态，一步一步慢慢来，放弃，但我最终找到了状态，一步一步慢慢来，经过无数次的检查程序错误的原因后慢慢懂得了耐心是一个人成功的必然具备的条件! 同时，通过此次课程设计使我了解到，必然具备的条件! 同时，通过此次课程设计使我了解到，硬件语言必不可缺少，要想成为一个有能力的人，必须懂得件语言必不可缺少，要想成为一个有能力的人，硬件

数据结构课程设计报告

《数据结构课程设计》报告题目：课程设计题目2教学计划编制班级：700 学号：09070026 姓名：尹煜完成日期：2011年11月7日

一．需求分析本课设的任务是根据课程之间的先后的顺序，利用拓扑排序算法，设计出教学计划，在七个学期中合理安排所需修的所有课程。（一）输入形式：文件文件中存储课程信息，包括课程名称、课程属性、课程学分以及课程之间先修关系。格式：第一行给出课程数量。大于等于0的整形，无上限。之后每行按如下格式“高等数学公共基础必修6.0”将每门课程的具体信息存入文件。课程基本信息存储完毕后，接着给出各门课程之间的关系，把每门课程看成顶点，则关系即为边。先给出边的数量。大于等于0的整形。默认课程编号从0开始依次增加。之后每行按如下格式“1 3”存储。此例即为编号为1的课程与编号为3的课程之间有一条边，而1为3的前驱，即修完1课程才能修3课程。例：（二）输出形式：1.以图形方式显示有向无环图

2.以文本文件形式存储课程安排（三）课设的功能 1.根据文本文件中存储的课程信息（课程名称、课程属性、课程学分、课程之间关系）以图形方式输出课程的有向无环图。拓展：其显示的有向无环图可进行拖拽、拉伸、修改课程名称等操作。 2.对课程进行拓扑排序。 3.根据拓扑排序结果以及课程的学分安排七个学期的课程。 4.安排好的教学计划可以按图形方式显示也可存储在文本文件里供用户查看。 5.点击信息菜单项可显示本人的学好及姓名“09070026 尹煜” （四）测试数据（见六测设结果）

二．概要设计数据类型的定义： 1.Class Graph即图类采用邻接矩阵的存储结构。类中定义两个二维数组int[][] matrix 和Object[][] adjMat。第一个用来标记两个顶点之间是否有边，为画图服务。第二个是为了实现核心算法拓扑排序。 2.ArrayList list用来存储课程信息。DrawInfo类是一个辅助画图的类，其中包括成员变量num、name、shuxing、xuefen分别代表课程的编号、名称、属性、学分。ArrayList是一个DrawInfo类型的数组，主要用来在ReadFile、DrawG、DrawC、SaveFile、Window这些类之间辅助参数传递，传递课程信息。 3.Class DrawInfo, 包括int num;String name;String shuxing;float xuefen;四个成员变量。 4.Class Edge包括int from;int to;double weight;三个成员变量。 5.Class Vertex包括int value一个成员变量。主要程序的流程图： //ReadFile.java

Oracle非结构化数据解决方案

Oracle数据库11g管理非结构化数据 (2) 一、引言 (2) 二、在ORACLE 中管理非结构化数据的优势 (3) 三、打破了原来处理非结构化数据的“性能障碍” (4) 3.1 Oracle SecureFiles (4) 3.2 SecureFiles 中的存储优化 (5) 四、专用数据类型和数据结构 (6) 4.1 Oracle XML DB (6) 4.2 Oracle Text (7) 4.3 Oracle Spatial (8) 4.4 RDF、OWL 和语义数据库管理 (9) 4.5 Oracle Multimedia (9) 4.6 Oracle DICOM 医学内容管理 (9) 五结论 (10)

Oracle数据库11g管理非结构化数据一、引言公司、企业以及其他机构使用的绝大部分信息都可归类为非结构化数据。非结构化数据是计算机或人生成的信息，其中的数据并不一定遵循标准的数据结构（如模式定义规范的行和列），若没有人或计算机的翻译，则很难理解这些数据。常见的非结构化数据有文档、多媒体内容、地图和地理信息、人造卫星和医学影像，还有Web 内容，如HTML。根据数据的创建方式和使用方式的不同，非结构化数据的管理方法大不相同。 1.大量数据分布于桌面办公系统（如文档、电子表格和演示文稿）、专门的工作站和设备（如地理空间分析系统和医学捕获和分析系统）上。 2.政府、学术界和企业中数TB 的文档存档和数字库。 3.生命科学和制药研究中使用的影像数据银行和库。 4.公共部门、国防、电信、公用事业和能源地理空间数据仓库应用程序。 5.集成的运营系统，包括零售、保险、卫生保健、政府和公共安全系统中的业务或健康记录、位置和项目数据以及相关音频、视频和图像信息。 6.学术、制药以及智能研究和发现等应用领域中使用的语义数据（三元组）。自数据库管理系统引入后，数据库技术就一直用于解决管理大量非结构化数据时所遇到的特有问题。通常通过“基于指针的”方法使用数据库对存储在文件中的文档、影像和媒体内容进行编目和引用。为了在数据库表内存储非结构化数据，二进制大对象（或简称为BLOB）作为容器使用已经数十年了。除了简单的BLOB 外，多年以来，Oracle 数据库一直通过运算符合并智能数据类型和优化数据结构，以分析和操作XML 文档、多媒体内容、文本和地理空间信息。由于有了Oracle 数据库11g，Oracle 再次在非结构化数据管理领域开辟出一片新天地：大幅提升了通过数据库管理系统原生支持的非结构化数据的性能、安全性以及类型。

文档之家

数据结构《第4章 串存储与基本操作的实现》

数据结构课程设计报告模板

员工信息管理系统(数据结构)

数据结构课程设计报告

数据结构实验总结报告

数据结构课程设计报告模板

数据结构第三章习题18页word

数据结构课程设计报告

非结构化存储方案

最新数据结构实训总结

数据结构物流信息管理系统

数据结构课程设计报告

非结构化数据管理系统

数据结构物流信息管理系统设计

数据结构第三章习题

数据结构课程设计报告-学生成绩管理系统[]

关于数据结构课程设计心得体会范文

数据结构课程设计报告

Oracle非结构化数据解决方案

数据结构《第4章串存储与基本操作的实现》