数据结构课程设计+串的基本操作演示

3.4串的基本操作演示

一、需求分析

1．用堆分配存储表示实现Hstring 串类型的最小操作子集。

2．实现串抽象类型的其余基本操作（如联接、删除等），且不能使用c语言本身提供的串函数，必须自己构造新的函数实现串的基本操作。

3．本演示系统是一个命令解释程序，循环往复的处理用户输入的每一条命令，直至终止程序的命令为止。

4．参数的合法性必须严格检查，要严格按照命令的输入格式进行输入，否则程序可能无法正确执行指令。

二、概要设计

实现串的抽象数据类型和实现其基本操作，程序中将涉及下列抽象数据类型：1．定义串的基本主结构

ADT String{

数据对象：D={ai| ai∈charcaterset,i=1,2,…,n,n>=0}

数据关系：R1={|ai-1,ai∈D, i=1,2,…,n}

基本操作：

StrCompare(HString S,HString T)

初始条件：S和T是已存在的Hstring类型。

操作结果：比较其值，显示结果“UNEQUAL”或“EQUAL”。

StrLength(HString S)

初始条件：S是已存在的Hstring类型。

操作结果：返回该串的长度。

Concat(HString S1,HString S2)

初始条件：S1和S2是已存在的Hstring类型。

操作结果：由S1和S2联接成新串。

Index(HString S,HString t)

初始条件：S和T是已存在的Hstring类型。

操作结果：显示第二个串在第一个串中首次出现的起始位置。

Replace(HString M, HString t, HString v)

初始条件：M、t和v是已存在的Hstring类型。

操作结果：将第一个串中所有出现的第二个串用第三个串替换，显示

结果串的内部名和串值，原串不变。

SubString(HString S,int pos,int len)

初始条件：S是已存在的Hstring类型。

操作结果：如果参数合法，则显示子串的内部名和串值。

Strprint(HString S)

初始条件：S是已存在的Hstring类型。

操作结果：显示串S的内部名和串值。

getin(int n)

初始条件：处理命令串S1,

操作结果：把串值存入串头表中

Insert(int n)

初始条件：要给指定的串赋值,n为指定的串的内部名

操作结果：为指定内部名的串赋值

show()

初始条件：要求查看输入格式

操作结果：输出各种命令的输入格式

}ADT String

二．存储结构及相应的类型定义

公用头文件header.h

#include

#include

#include

#include

#include

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define OVERFLOW -2

#define MAXLEN 100

#define MAXSIZE 50

typedef int Status;

（1）顺序存储结构

typedef struct ResultType

{

int CmdNo; //命令号或命令符

int s[3]; //命令的串参数的内部名（最多3）

int num[2]; //命令的数值参数（最多2个）

}ResultType,*Result ;

typedef struct

{ char * ch; //若为非空串，则按串长分配存储区，否则ch为NULL int length; //串长度

int state; //状态量

}HString,*String;

typedef struct

{HString StrHead[100]; //串头数组

int CurNum; //系统中现有的串的数目

}StrHeadList,*StrHead;

三、详细设计

void StrCompare(HString S,HString T)

{//比较两串的串值，显示结果“UNEQUAL”或“EQUAL”

int i;

if(S.length!=T.length) //先判长度是否相等，若不相等则显示

“UNEQUAL”

{printf("“UNEQUAL”\n");return;}

else

{ for(i=0;i

if(S.ch[i]!=T.ch[i]) {printf("“UNEQUAL”\n");return;}

}

printf("“EQUAL”\n"); //比较完后，相等则显示“EQUAL”

}

void Concat(HString S1,HString S2) //由S1和S2联接成新串

{int i,j;

j=KK->CurNum++; //为串头指针分配位置，申请(S1.length+S2.length)大小空间if((KK->StrHead[j].ch=(char*)malloc((S1.length+S2.length)

*sizeof(char)))==NULL) exit(OVERFLOW);

for(i=0;i

KK->StrHead[j].ch[i]=S1.ch[i];

for(i=0;i

KK->StrHead[j].ch[S1.length+i]=S2.ch[i];

KK->StrHead[j].length=S1.length+S2.length; //(S1.length+S2.length)赋值给新串printf("结果串的内部名和串值为：\n");//显示结果串名和串值

printf("%5d",j);

printf("%c",' ');

printf("'");

for(i=0;iStrHead[j].length;i++)

printf("%c",KK->StrHead[j].ch[i]);

printf("'");

printf("\n");

}

int StrLength(HString S)//返回S串的长度

{

return S.length;

}

void Strprint(HString S)

{

int i;

printf("%c",' ');

printf("'");

for(i=0;i

printf("%c",S.ch[i]);

printf("'");

printf("\n");

}

Status SubString(HString S,int pos,int len)//求串S的子串

{int i,n;

n=KK->CurNum++;//为串头指针分配位置

if(pos<0||pos>S.length||len<0||len>S.length-pos+1)//判断参数是否合法{

printf("ERROR: 参数不合法\n");

return ERROR;

}

if(!len) //当子串长度为空

{

KK->StrHead[n].ch=NULL;

KK->StrHead[n].length=0;

}

else

{//申请len长度的空间存储新串

KK->StrHead[n].ch=(char *)malloc(len *sizeof(char));

for(i=0;i<=len-1;i++)

KK->StrHead[n].ch[i]=S.ch[pos-1+i];

KK->StrHead[n].length=len;

}

printf("子串的内部名和串值为：\n");//显示新串的内部名和串值printf("%5d",n);

Strprint(KK->StrHead[n]);

printf("\n");

return OK;

}

Status Index(HString S,HString t)

{ //显示第二个串在第一个串中首次出现的起始位置

int m,i,j;

if(t.length==0)//若t串的长度为0，则参数非法

printf("参数非法\n");

else{

for(i=0;i<=S.length-t.length+1;i++)//查找第二个串在第一个串中首次出现的

起始位置

{for(j=i,m=0;m

if(m==t.length)

{ printf("第二个串在第一个串中首次出现的起始位置：\n");

printf("%d\n",i+1);

return OK;

}

}

}

if(i>=0) printf("该位置不存在\n");//若找不到

return ERROR;

}

Status Replace(HString M, HString t, HString v)

{//将第一个串中所有出现的第二个串用第三个串替换，显示结果串的内部名和串值，原串不变。

int i,j,m,n,k,y=0;

n=KK->CurNum++;//为串头指针分配位置

if(M.length<0) return ERROR;//判断

if((KK->StrHead[n].ch=(char*)malloc((M.length)*sizeof(char)))==NULL)

exit(OVERFLOW);//申请空间

for(i=0;i

KK->StrHead[n].ch[i]=M.ch[i];

KK->StrHead[n].length=M.length;

for(i=0;i<=KK->StrHead[n].length-t.length;i++)//新串与串t比较

{for(j=i,m=0;mStrHead[n].ch[j]==t.ch[m];m++,j++);

if(m==t.length)//在新串中找到和串t相等的子串

{y=1;

if(t.length>v.length)//串t的长度大于串v，修改新串内容

{

for(k=i,m=0;m

KK->StrHead[n].ch[k]=v.ch[m];

for(k=i+v.length;kStrHead[n].length-t.length+v.length;k++)

KK->StrHead[n].ch[k]=KK->StrHead[n].ch[k-v.length+t.length];

}

else if(t.length==v.length) //串t的长度等于串v，修改新串内容

{for(j=i,m=0;m

KK->StrHead[n].ch[j]=v.ch[m];}

else //串t的长度小于串v，修改新串内容

{if((KK->StrHead[n].ch=(char*)realloc(KK->StrHead[n].ch,(KK->StrHead[n].length

-t.length+v.length) *sizeof(char)))==NULL) exit(OVERFLOW);

for(k=KK->StrHead[n].length-t.length+v.length-1,m=KK->StrHead[n].length-1;k>=v. length+i;k--,m--) KK->StrHead[n].ch[k]=KK->StrHead[n].ch[m];

for(k=v.length+i-1,m=v.length-1;m>=0;k--,m--)

KK->StrHead[n].ch[k]=v.ch[m];

}

KK->StrHead[n].length+=v.length-t.length;

i=i+v.length-1;

}

}

printf("结果串的内部名和串值为：\n");//显示新串内容

printf("%5d",n);

Strprint(KK->StrHead[n]);

printf("\n");

if(y==1) return TRUE;

else return FALSE;

}

void show()//命令输入格式

{printf("输入格式如下：\n");

printf("(1)赋值。格式例子：A 'hello'\n");

printf("(2)判相等。格式例子：E 'hello' 'hi' 或只输入E然后根据提示操作。\n");

printf("(3)联接。格式例子：C 'hello' 'hi' 或只输入C然后根据提示操作。\n");

printf("(4)求长度。格式例子：L 'hello' 或只输入L然后根据提示操作。\n");

printf("(5)求子串。格式例子：S 'hello'然后根据提示操作或只输入E提示操作.\n");

printf("(6)子串定位。格式例子：I 'hello' 'll' 或只输入I然后根据提示操作。\n");

printf("(7)串替换。格式例子：R 'hello' 'll' 'hli'或只输入R然后根据提示操作。\n");

printf("(8)显示。格式例子：只输入P然后根据提示操作。\n");

printf("(9)删除。格式例子：只输入D然后根据提示操作。\n");

printf("(Q)退出。格式例子：只输入Q然后根据提示操作。\n");

}

Status Insert(int n) //为指定内部名的串赋值

{int i,j,k=0;

char s2[50];

if(s[k]=='\'')

{i=0;

k++;

while(s[k]!='\'') s2[i++]=s[k++];

}

else {printf("格式输入错误！\n");return ERROR;}

if(KK->StrHead[n].ch)

{KK->StrHead[n].ch=NULL;

KK->StrHead[n].length=0;

KK->StrHead[n].state=0;

}

if(!(KK->StrHead[n].ch=(char *)malloc(i*sizeof (char)))) exit(OVERFLOW);

KK->StrHead[n].length=i;

KK->StrHead[n].state=1;

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

KK->StrHead[n].ch[j]=s2[j];

return OK;

}

void getin(int n) //处理命令串，n为要存入的串内部名

{int i,j;

while(s1[m]==' ') m++; //s1为从键盘接收到的字符串，s1,m为局部变量，在

getorder（）函数内有效，减少需要传递的参数

if(s1[m]=='\'')

{i=0;

m++;

while(s1[m]!='\'') s[i++]=s1[m++];

}

if(!(KK->StrHead[n].ch=(char *)malloc(i*sizeof (char)))) exit(OVERFLOW);

KK->StrHead[n].length=i;

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

KK->StrHead[n].ch[j]=s[j]; //将命令中的串值存入相应的串头表

}

函数的调用关系图（只列出部分）

四、调试分析

#include"header.h"

StrHead KK; //定义StrHead类型的全局变量

void main()

{ char c;

int i;

Result p;

Status InitResult(Result p); //命令分析函数的初始化

Status getorder(Result p); //命令处理函数

void getin(int n); //命令串处理函数

void Strprint(); //输出串值

void show(); //显示输入格式

void StrCompare(HString S,HString T); //串比较函数

void Concat(HString S1,HString S2); //串联接函数

int StrLength(HString S); //取串长度

Status SubString(HString S,int pos,int len); //取子串

Status Replace(HString M, HString t, HString v); //子串替换

Status Index(HString S,HString T); //子串定位

Status Insert(int n) //为指定内部名的串赋值KK=(StrHead )malloc(sizeof(StrHeadList)); //申请空间

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

{KK->StrHead[i].ch=NULL;

KK->StrHead[i].length=0;

KK->StrHead[i].state=0;

}

KK->CurNum=0;

p=(Result )malloc(sizeof(ResultType)); //申请空间

do{

printf("*********************************************\n");

printf("* 串的基本操作演示系统*\n");

printf("* A.进入系统*\n");

printf("* B.输入格式*\n");

printf("* C.退出系统*\n");

printf("*********************************************\n");

scanf("%c",&c);

getchar();

switch(c)

{case'A':InitResult(p);getorder(p);break;

case'B': show();break;

case'C': break;

default: printf("输入错误，请重新输入！\n"); break;

}

}while(c!='C');

}

char s1[100],s[50]; //定义局部变量

int m; //定义局部变量

Status getorder(Result p)

{

char s1[100],s[50];

int i,j,n,m;

do{

printf("请输入指令：\n");

gets(s1);

m=0;

switch(s1[m]) //判断指令类型

{case'A':{while(KK->StrHead[KK->CurNum].state==1) KK->CurNum++;

p->s[0]=KK->CurNum++;

m++;

getin(p->s[0]); //将串值赋入串头表中

printf("新串的内部名和串值为：\n");

printf("%5d",p->s[0]);

Strprint(KK->StrHead[p->s[0]]); //回显新串

break

}

case 'E':{ m++; //串比较

if(s1[m]=='\0') //比较内部已保存的串

{printf("输入第一个串的内部名：\n");

scanf("%d",&p->s[0]);

getchar();

printf("输入第一个串的内部名：\n");

scanf("%d",&p->s[1]);

getchar();

if(p->s[0]<0||p->s[0]>=KK->CurNum||p->s[1]<0||p->s[1]>=KK->CurNum)

printf("超出当前串的范围\n");

else

{StrCompare(KK->StrHead[p->s[0]],KK->StrHead[p->s[1]]);}

}

else {while(KK->StrHead[KK->CurNum].state==1) KK->CurNum++;

p->s[0]=KK->CurNum++;

while(KK->StrHead[KK->CurNum].state==1) KK->CurNum++;

p->s[1]=KK->CurNum++;

getin( p->s[0]);

m++;

getin(p->s[1]);

StrCompare(KK->StrHead[p->s[0]],KK->StrHead[p->s[1]]);

}

break;

}

case 'C':{ m++; //串联接

if(s1[m]=='\0') //联接内部已存在的串

{printf("输入第一个串的内部名：\n");

scanf("%d",&p->s[0]);

getchar();

printf("输入第二个串的内部名：\n");

scanf("%d",&p->s[1]);

getchar();

if(p->s[0]<0||p->s[0]>=KK->CurNum||p->s[1]<0||p->s[1]>=KK->CurNum)

printf("超出当前串的范围\n");

else

{Concat(KK->StrHead[p->s[0]],KK->StrHead[p->s[1]]);}

}

else

{ while(KK->StrHead[KK->CurNum].state==1) KK->CurNum++;

p->s[0]=KK->CurNum++;

while(KK->StrHead[KK->CurNum].state==1) KK->CurNum++;

p->s[1]=KK->CurNum++;

getin( p->s[0]);

getin(p->s[1]);

Concat(KK->StrHead[p->s[0]],KK->StrHead[p->s[1]]);

}

break;

}

case 'L': { m++; //求长度

if(s1[m]=='\0') //求内部已存在的串长度

{printf("输入第一个串的内部名：\n");

scanf("%d",&p->s[0]);

getchar();

if(p->s[0]<0||p->s[0]>=KK->CurNum)

printf("超出当前串的范围\n");

else

{j=StrLength(KK->StrHead[p->s[0]]);

printf("串长度为：%d\n",j);

}

}

else //求新输入的串长度

{ while(KK->StrHead[KK->CurNum].state==1) KK->CurNum++;

p->s[0]=KK->CurNum++;

getin( p->s[0]);

j=StrLength(KK->StrHead[p->s[0]]);

printf("串长度为：%d\n",j);

}

break;

}

case 'S':{ m++;

if(s1[m]=='\0') //求内部已存在的串的子串

{printf("输入第一个串的内部名：\n");

scanf("%d",&p->s[0]);

getchar();

if(p->s[0]<0||p->s[0]>=KK->CurNum)

printf("超出当前串的范围\n");

else

{ printf("请输入pos位置：\n");

scanf("%d",&p->num[0]);

getchar();

printf("请输入len长度：\n");

scanf("%d",&p->num[1]);

getchar();

SubString(KK->StrHead[p->s[0]],p->num[0],p->num[1]);

}

}

{ while(KK->StrHead[KK->CurNum].state==1) KK->CurNum++;

p->s[0]=KK->CurNum++;

getin( p->s[0]);

printf("请输入pos位置：\n");

scanf("%d",&p->num[0]);

getchar();

printf("请输入len长度：\n");

scanf("%d",&p->num[1]);

getchar();

SubString(KK->StrHead[p->s[0]],p->num[0],p->num[1]);

}

break;

}

case 'I': { m++; //子串定位

if(s1[m]=='\0') //求内部已存在的串的子串的位置

{printf("输入第一个串的内部名：\n");

scanf("%d",&p->s[0]);

getchar();

printf("输入第二个串的内部名：\n");

scanf("%d",&p->s[1]);

getchar();

if(p->s[0]<0||p->s[0]>=KK->CurNum||p->s[1]<0||p->s[1]>=KK->CurNum)

printf("超出当前串的范围\n");

else

{Index(KK->StrHead[p->s[0]],KK->StrHead[p->s[1]]);}

}

else

{while(KK->StrHead[KK->CurNum].state==1) KK->CurNum++;

//求新输入的串的子串的位置

p->s[0]=KK->CurNum++;

while(KK->StrHead[KK->CurNum].state==1)

KK->CurNum++;

p->s[1]=KK->CurNum++;

getin( p->s[0]);

m++;

getin(p->s[1]);

Index(KK->StrHead[p->s[0]],KK->StrHead[p->s[1]]);

}

break;

}

case 'R': { m++; / /替换串

if(s1[m]=='\0') //求内部已存在的串的替换

{printf("输入第一个串的内部名：\n");

scanf("%d",&p->s[0]);

getchar();

printf("输入第二个串的内部名：\n");

scanf("%d",&p->s[1]);

getchar();

printf("输入第三个串的内部名：\n");

scanf("%d",&p->s[2]);

getchar();

if(p->s[0]<0||p->s[0]>=KK->CurNum||p->s[1]<0||p->s[1]>=KK->CurNum||p->s[2]<0 ||p->s[2]>=KK->CurNum)

printf("超出当前串的范围\n");

else

{Replace(KK->StrHead[p->s[0]],KK->StrHead[p->s[1]],

KK->StrHead[p->s[2]]);}

}

else

{

while(KK->StrHead[KK->CurNum].state==1)

KK->CurNum++;

p->s[0]=KK->CurNum++;

while(KK->StrHead[KK->CurNum].state==1)

KK->CurNum++;

p->s[1]=KK->CurNum++;

while(KK->StrHead[KK->CurNum].state==1)

KK->CurNum++;

p->s[2]=KK->CurNum++;

getin(p->s[0]);

m++;

getin(p->s[1]);

m++;

getin(p->s[2]);

Replace(KK->StrHead[p->s[0]],KK->StrHead[p->s[1]], KK->StrHead[p->s[2]]);

}

break;

}

case 'P': { printf("所有串的内部名和串值为：\n");//显示所有保留的串

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

{if(KK->StrHead[i].ch!=NULL)

{ printf("%5d",i);

Strprint(KK->StrHead[i]) ;

}

}

break;

}

case 'D': {printf("请输入要删除的串的内部名：\n"); //删除串

scanf("%d",&p->num[0]);

getchar();

if(p->num[0]<0||p->num[0]>=KK->CurNum)

printf("无此串！\n");

else{ printf("删除的串名和串值为：\n");

printf("%5d",p->num[0]);

printf("%c",' ');

Strprint(KK->StrHead[p->num[0]]);

KK->StrHead[p->num[0]].ch=NULL;

KK->StrHead[p->num[0]].length=0;

}

break;

}

case 'W': { printf("请输入要赋值的串的内部名和串值（以空格隔开）：\n");

scanf("%d%s",&p->num[0],s);

getchar();

if(p->num[0]<0||p->num[0]>=100)

printf("无此串！\n");

else{ Insert(p->num[0]);

printf("新串的内部名和串值为：\n");

printf("%5d",p->num[0]);

Strprint(KK->StrHead[p->num[0]]);

}

break;

}

case 'Q': break;

default: printf("输入错误！可返回上一界面查看输入格式\n");

}

}while(s1[0]!='Q');

return OK;

}

（2）

测试数据：

①赋值：A …hello?

A …nice to meet you!?

A …too?

②显示：P //回显刚才输入的三条语句

③判相等：E 'hello' 'hi' 或只输入E然后根据提示操作

④联接： C 'hello' 'hi' 或只输入C然后根据提示操作

⑤求长度：L 'hello' 或只输入L然后根据提示操作

⑥求子串：S 'hello'然后根据提示操作或只输入E提示操作.

⑦子串定位：I 'hello' 'll' 或只输入I然后根据提示操作

⑧删除：输入D然后根据提示操作

Eg. E …?…?,显示“EQUAL”

E …dad?…?,显示“UNEQUAL”

C …?…?,显示…?

C …hello,?…nice to meet you? ,显示…hello,nice to meet you?

I …a?…?,应报告：参数非法

I …hello?…ll? ,显示:3

S …hello? ,然后根据提示输入pos和len的值

R …aaa?…aa?…b? ,显示: …ba?

R …aaabc?…a?…aab? ,显示: …aabaabaabbc?

R …aaaaaaaa?…aaaa?…ab? ,显示: …abab?

五、用户手册

1．本程序的运行环境为DOS操作系统，执行文件为project.exe。

2．进入程序后即显示用户欢迎界面，用户可根据文字提示进行操作，本程序有两种命令输入格式（如E 'hello' 'hi' 或只输入E然后根据提示操作），具体可查看程序的输入格式。

3．本程序区分大小写，输入指令时请注意。

4. 本程序支持内部名操作，如在联接串的时候，可以先输入C,然后按提示输入内部名，即可完成操作。或者可以直接输入 C 'hello' ' nice to meet you',结果串为'hello nice to meet you '；其它的函数也可以进行类似操作。5．本程序是命令解释程序，循环往复地处理用户键入的每一条指令，直至终止程序的命令为止（本程序退出指令为Q）。

六、测试结果

下面是运行程序的操作流程（从运行窗口复制的）：project.exe

注释：上图为书本上测试数据的运行效果图，可见运行结果正确。

1．比较串相等时，因为要比较的两个串都已存入串头表中。因此，开始可以先比较两串的长度，若不等则马上显示“UNEQUAL”并返回。长度相等则逐个比较串值，遇到不等则马上显示“UNEQUAL “并返回，比较完相等则显示“UNEQUAL”。

2．在串联接时，方法挺简单。只需申请两串长度之和的空间，然

后按顺序赋值到新串即可。

注释：上图为执行各项基本操作的效果图，可见验证结果的正确性。

1．上图是直接输入串值的命令，这样可以方便的一次性输入完指令。满足了程序的基本要求。

2．在子串定位函数中，要注意检查参数的合法性，当第二个串是空串时要正确处理这种情况。

3．在子串替换时，要注意设置循环结束的条件，如果设置不对，曾出现过R?aaa?…aa?…b?,结果却为…b?的错误结果，改正后结果正确。

注释：上图为各项操作的效果图

1．在这里可以看出，本程序增加了Insert（）函数，可以在指定的内部名插入串值，这样就可以实现自由给范围内的串赋值，而不是仅仅依靠系统的自动增加功能，这样就增强了系统的灵活性和可用性。

2．本程序还支持内部名操作，如上图所示，可以根据要求输入内部名，即可完成相应的串操作，这样可以对已存入的串进行联接、

比较等操作，这样就大大增强了程序的实用性和可操作性。

七、附录

源程序文件名菜单：

header.h //类型和变量说明

main.c //主程序文件

八、时间复杂度分析

1．由于本程序采用数组的顺序存储结构，虽然要开始定义一个较大的存储空间（如定义：HString StrHead[100]），但由于每个Hstring类型的结构体才两个元素，花费的整体空间并不比链式存储结构（要开辟指针域，花费一定空间）大多少，更重要的是采用数组的顺序存储结构执行串的基本操作非常方便，不必如链式那样从头指针出发查找，时间复杂度为O（n）,可以通过内部名直接找到某一个串，时间复杂度为O（1）。因此在执行诸如串的基本操作上很方便。

2．假设串值的平均长度为n，则StrCompare的时间复杂度为o（n）；Concat的时间复杂度为o（n+n）；Index的时间复杂度为o（n*n）；Replace的时间复杂度为o（n*n*n）；SubString的时间复杂度为o（n）；3．在错误处理方面，本程序在几个方面做了考虑。比如在赋值指令时，如果输入的命令为A ad?as?，这样虽然可以知道是赋值指令，但串值不能正确赋入相应的串中，这时系统应该报错；再者，在支持内部名操作的指令中，如果输入的内部名超出范围，则应该报错，其它类似的地方也应采取相应的处理方式。

4．由于本程序采用字符数组s1来接收输入的命令，为了处理数据的方便，采用了定义局部变量的方法，这样可以减少需要传递的参数个数。比如在一条替换指令中有三个串，在赋值的时候采用同一个函数getin（int n）函数就可以完成三个串的赋值，而且只需传递目的串的内部名一个参数就足够啦。因为s1是在getorder函数的，把s1[m]定义为局部变量后就可以直接在getin函数调用，减少传递的参数，还可以使m增加到相应的位置，为下个getin函数取用方便且正确。另外，由于s1被定义为字符类型，如果将内部名连同指令号（如E 0 1），这样在取内部名的时候结果会不正确，若内部名为双位数，则判断上有很大难度，为了方便起见，可以先输入指令号，然后根据提示操作。

5．在特色功能方面，本程序除了增加支持内部名的功能外，考虑人性化要求，增加了串复制函数。可以直接定位内部名，给指定的串赋值，实现这个功能有很大的作用。且实现这个功能也挺简单的，只需在Hstring类型里面增加state状态量，有串值状态就为1，这样避免了因为有些指令系统的自动加一功能把原本赋入串的值冲掉。

九、思考和小结

本次课程设计是对我们这一学期来数据结构课程学习成果的一次实践检验，是对我们的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节，本次课程设计的的问题比平时的习题复杂的多，也更接近实际。是软件设计的综合训练，包括问题分析、总体结构分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。培养我们养成一整套软件工作规范的训练和科学作风的培养。

在这次课程设计的实践过程中，刚开始时候由于对问题的认识还不是很清楚和对c语言一些知识的遗忘，遇到问题解决不了。通过向老师和同学请教，还有自己重新复习了c语言那本书。然后又重新对问题进行分析，设计和调试。实现串操作的基本函数，可以借鉴我们在作业系统中遇到的相类似的题目，进行思考和总结，便很容易实现串的基本操作函数；在接受命令的输入格式方面，试了很多种方法。开始时尝试过用getchar（）函数来接收命令，并根据接受到的指令进行操作，但遇到了问题，于是有用gets（）函数一次就将整条指令存入一个一维数组中，然后再对数组进行操作，这样容易且方便很多。在调试程序的过程中，遇到一些结果不正确或超出范围的情况，又要重新返回相应的函数进行检查和修改补充，才能使程序更加健壮和完整，才能做出一个更加实用的软件

本次的课程设计经过自己的努力和老师的帮助，顺利的完成了程序设计要求的基本内容和要求，对自己的编程水平有了很大程度的提高，让我们继续努力，努力做一个优秀的软件设计者。

数据结构《第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。

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

《数据结构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

数据结构课程设计题目2010

一、数据结构课程设计要求 1.学生必须仔细阅读《数据结构》课程设计方案，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。 2.学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时向教师汇报。 3.课程设计按照教学要求需要两周时间完成，两周中每天（按每周5天）至少要上2小时的上机来调试C 或C++语言设计的程序，总共至少要上机调试程序20小时。属教师安排上机时间学生不得缺席。 二、数据结构课程设计题目 1. 运动会分数统计（限1 人完成） 任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20） 功能要求： 1) 可以输入各个项目的前三名或前五名的成绩； 2) 能统计各学校总分， 3) 可以按学校编号或名称、学校总分、男女团体总分排序输出； 4) 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 5) 数据存入文件并能随时查询 6) 规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称 输出形式：有中文提示，各学校分数为整形 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构； 测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明； 2. 飞机订票系统（限1 人完成） 任务：通过此系统可以实现如下功能： 录入： 可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）

串的基本操作

串的基本操作 一、实验目的、意义 （1）理解串的堆分配存储结构。 （2）理解用它们表示时插入，生成串，联接串与求子串的算法。 （3）根据具体问题的需要，能够设计出相关算法。 二、实验内容及要求 说明1：学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。 具体要求： 定义串的堆分配存储，完成串的基本操作：插入，生成串，联接串，求子串等。 三、实验所涉及的知识点 C语言算法、循环算法、串的堆分配存储结构、插入，生成串，联接串与求子串的算法。 四、实验结果及分析 （所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。） 五、总结与体会

（调试程序的心得与体会，若实验课上未完成调试，要认真找出错误并分析原因等。） 调试程序时，出现了许多错误。如：串的堆分配存储结构、串的联接等。另外还有一些语法上的错误。由于对所学知识点概念模糊，试验课上未能完成此次上机作业。后来经过查阅教材，浏览网页等方式，才完成试验。这次试验出现错误最重要的原因就是对课本知识点理解不深刻以及编写代码时的粗心。以后要都去练习、实践，以完善自己的不足。 六、程序清单(包含注释) #include #include #include typedef char Status; int strlen(char *p) { int i=0; while(*p++)i++; return i; } typedef struct { char *ch; // 若是非空串,则按串长分配存储区,否则ch为NULL int length; // 串长度 }HString; // 初始化(产生空串)字符串T void InitString(HString *T) { (*T).length=0; (*T).ch=NULL; } // 生成一个其值等于串常量chars的串T Status StrAssign(HString *T, char *chars) { int i,j; if((*T).ch) free((*T).ch); // 释放T原有空间 i = strlen(chars); // 求chars的长度i if(!i)

串的基本操作

1上机实训3：串的基本操作 一、实训目的 通过实训，掌握串的运算（赋值，比较，联结，插入子串，模式匹配……等） 二、实验理论知识 1)串的基本概念及其含义 串( string)是由零个或多个字符组成的有限序列，一般记作: s='a1a2…an'(n≥0)，其中s为串的名字，用单引号括起来的字符序列为串的值；ai(1≤i≤n)可以是字母、数字或其它字符（取决于程序设计语言所使用的字符集）；n为串中字符的个数，称为串的长度。 2)串的存储表示及其实现 ●顺序存储 可以用一组地址连续的存储单元依次存放串的各个字符，这是串的顺序 存储结构，也称为顺序串 ●链式存储 和线性表的链式存储结构相类似，也可采用链表方式存储串值。串的这 种链式存储结构简称为链串。用链表存储字符串，每个结点需要有两个 域：一个数据域（data）和一个指针域(Next)，其中数据域存放串中的 字符，指针域存放后继结点的地址。 3)模式匹配问题 三、实训案例与分析 【实例1】串的存储与基本运算 【实例分析】在本实例中练习计算字符串的长度、字符串的复制、字符串的比较、字符串的连接、字符串的插入等基本操作。在设计时 1)编写一个菜单函数，根据不同情况做（1-5）不同选择。 2)如果选择1，即要求计算输入字符串的长度。 3)如果选择2，完成字符串的复制。 4)如果选择3，完成字符串的比较。 5)如果选择4，完成两个字符串的连接。 6)如果选择5，字符串的插入。 【参考程序】 #include #define MAX 128

typedef enum {fail,success} status; typedef enum {false,true} boolean; main() { int strlen(); void strass(); boolean strcmp(); status strcat( ); status strins(); int t,n,i; boolean b; status st; char s[MAX],s1[MAX],s2[MAX]; printf("\n1. The length of string\n"); printf(" 2. The assignment of string\n"); printf(" 3. A string compare with another string:\n"); printf(" 4. A string connect with another string:\n"); printf(" 5. A string to be inserted into another string\n"); printf(" Please input a operation:");/*输入操作选项*/ scanf("%d",&t); switch(t) { case 1: printf("please input a string:\n"); getchar(); gets(s); n=strlen(s); printf("the length is: %d",n); break; case 2: printf("please input the first string:\n"); getchar(); gets(s1); printf("please input the second string:\n"); getchar(); gets(s2);

数据结构课程设计报告

《数据结构与算法》课程设计报告 学号： 班级序号： 姓名： 指导教师： 成绩： 中国地质大学信息工程学院地理信息系统系 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.综合应用 2.折半查找 3.快速排序 专业：软件工程 班级：1101 座号：3110305129 姓名：潘聪 2012 年 6 月26 日

设计题目1：综合应用 一、问题描述 有N名学生，每名学生含有如下信息：学号、姓名、某四门课的成绩，并计算其总分，用一结构数组表示之。然后实现以下功能： （1）将这些数据存放至文件stuf.dat中； （2）将文件中的数据读出至结构数组中，并显示之； （3）输出总分最高分和最低分的名字； （4）输出总分在340分，单科成绩不低于80分的名单； （5）求出各科平均分数； （6）按总分排名； （7）输出补考名单。 二、解决问题的算法思想描述 （1）子函数：首先确定需要的子函数，总共7个，对应的功能分别是题目要求的七项（2）主函数：主函数中，要设计出易于使用的人机界面，就必须要用到switch 。 （3）文件的存放读取，必须要用到文件的函数，fopen，fread，fclose等。 （4）把每个学生的信息定义在一个结构数组中，利用结构数组更加方便。 （5）各科成绩排名用冒泡排序即可。 （6）输出总分，补考名单，各科的平均分都比较简单。 三、设计 1. 数据结构的设计和说明 //定义结构体 typedef struct { int num; //学号 char name[10]; //姓名 int score1; //语文 int score2; //数学 int score3; //物理 int score4; //化学 }student; student stu[MAX]; //结构数组 2．模块结构图及各模块的功能：

(完整版)Excel表格的基本操作[初学者专用]超级技能

目录 技巧1、单元格内强制换行 技巧2、锁定标题行 技巧3、打印标题行 技巧4、查找重复值 技巧5、删除重复值 技巧6、快速输入对号√ 技巧7、万元显示 技巧8、隐藏0值 技巧9、隐藏单元格所有值。 技巧10、单元格中输入00001 技巧11、按月填充日期 技巧12、合并多个单元格内容 技巧13、防止重复录入 技巧14、公式转数值 技巧15、小数变整数 技巧16、快速插入多行 技巧17、两列互换 技巧18、批量设置求和公式 技巧19、同时查看一个excel文件的两个工作表。技巧20：同时修改多个工作表 技巧21：恢复未保存文件 技巧22、给excel文件添加打开密码 技巧23、快速关闭所有excel文件 技巧24、制作下拉菜单 技巧25、二级联动下拉 技巧27、删除空白行 技巧28、表格只能填写不能修改 技巧29、文字跨列居中显示 技巧30、批注添加图片 技巧31、批量隐藏和显示批注 技巧32、解决数字不能求和 技巧33、隔行插入空行 技巧34、快速调整最适合列宽 技巧35、快速复制公式 技巧36、合并单元格筛选

技巧1、单元格内强制换行 在单元格中某个字符后按alt+回车键，即可强制把光标换到下一行中。 技巧2、锁定标题行 选取第2行，视图 - 冻结窗格 - 冻结首行（或选取第2行 - 冻结窗格）冻结后再向下翻看时标题行始终显示在最上面。 技巧3、打印标题行 如果想在打印时每一页都显示标题，页面布局 - 打印标题 - 首端标题行：选取要显示的行

技巧4、查找重复值 选取数据区域 - 开始 - 条件格式 - 突出显示单元格规则 - 重复值。 显示效果：

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

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

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

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

数据结构课程设计

<<数据结构>> 课 程 设 计 班级:111004 姓名:董丽美 学号:111004122 指导教师:史延新 完成日期:2013 _07 _10

题目一:约瑟夫环问题 【问题描述】约瑟夫（Joseph）问题的一种描述是：编号为1,2，…,n 的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m 的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出列顺序。【基本要求】利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号。 【测试数据】m的初值为20；n=7,7个人的密码依次为：3,1,7,2，4,8,4，首先m值为6（正确的出列顺序应为：6,1,4,7,2,3,5） 一 .需求分析 1．用单循环链表存储并遍历及删除节点的方法，计算并输出约瑟夫环的问题。 2．环中总人数和节点信息由用户输入，且均为正整数。3．在窗口界面输出出列顺序的编号。 二．概要设计

1.设定链表的抽象数据类型定义： ADT List{ 数据对象：D={a(i)|a(i)∝Elemset,i=1,2,…,n,n>=0} 数据关系：R1={|a(i-1),a(i)∝D,i=2,…,n}基本操作： InitList(&L) 操作结果：构造一个空的线性表 ListInsert(&L,i,e) 初始条件：线性表L已经存在。 操作结果：在L中第i个位置之前插入新的数据元素 e,L的长度增加1。 ListDelete(&L,i,&e) 初始条件：线性表L已经存在且非空，1<=i<=ListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L 的长度减1 。 } 2.算法的基本思想： 根据题目要求，采用单循环线性表的基本操作来实现约瑟夫环问题。首先根据所给信息生成链表节点并插入，根据节点记录密码及其所在链表中的顺序，由给出的初始访问值进行遍历，当变量i增量等于所给的值（即关键字）时，指针所指的节点处的顺序值即为所需输出的顺序号。每输出一次顺

实验三 串基本操作的实现

实验三串基本操作的实现 专业：计算机科学与技术班级：10计本1班学号：姓名： 实验地点： B102 实验时间： 2011.11.2 指导教师：王润鸿 实验目的 1 理解定长顺序串的存储结构及基本操作的定义； 2掌握定长顺序串的基本操作； 3学会设计实验数据验证程序。 实验环境 计算机，window xp操作系统，VC++6.0 实验内容 1. 存储结构定义： ＃define MAXSTRLEN 255 //串的长度最大为255 typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存放串的长度，其最大值刚好是255 2. 实现的基本操作： StrAssign (&T, chars) 初始条件：chars 是串常量。 操作结果：赋于串T的值为chars。 StrCopy (&T, S) 初始条件：串S 存在。 操作结果：由串S 复制得串T。 DestroyString (&S) 初始条件：串S 存在。 操作结果：串S 被销毁。 StrEmpty (S) 初始条件：串S 存在。 操作结果：若S 为空串，则返回TRUE，否则返回FALSE。 StrCompare (S, T) 初始条件：串S 和T 存在。 操作结果：若S>T，则返回值=0；若S=T，则返回值<0；若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、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。从刚开始得觉得很难，到最后把这个做出来，付出了很多，也得到了很多，以前总以为自己对编程的地方还不行，现在，才发现只要认真做，没有什么不可能。 编程时要认真仔细，出现错误要及时找出并改正，（其中对英语的要求也体现出来了，因为它说明错误的时候都是英语）遇到问题要去查相关的资料。反复的调试程序，最好是多找几个同学来对你的程序进行调试并听其对你的程序的建议，在他们不知道程序怎么写的时候完全以一个用户的身份来用对你的用户界面做一些建议，正所谓当局者迷旁观者清，把各个注意的问题要想到；同时要形成自己的编写程序与调试程序的风格，从每个细节出发，不放过每个知识点，注意与理论的联系和理论与实践的差别。另外，要注意符号的使用，注意对字符处理，特别是对指针的使用很容易出错且调试过程是不会报错的，那么我们要始终注意指针的初始化不管它怎么用以免不必要麻烦。 通过近两周的学习与实践，体验了一下离开课堂的学习，也可以理解为一次实践与理论的很好的连接。特别是本组所做的题目都是课堂上所讲的例子，在实行之的过程中并不是那么容易事让人有一种纸上谈兵的体会，正所谓纸上得来终觉浅绝知此事要躬行。实训过程中让我们对懂得的知识做了进一步深入了解，让我们的理解与记忆更深刻，对不懂的知识与不清楚的东西也做了一定的了解，也形成了一定的个人做事风格。 通过这次课程设计，让我对一个程序的数据结构有更全面更进一步的认识，根据不同的需求，采用不同的数据存储方式，不一定要用栈，二叉树等高级类型，有时用基本的一维数组，只要运用得当，也能达到相同的效果，甚至更佳，就如这次的课程设计，通过用for的多重循环，舍弃多余的循环，提高了程序的运行效率。在编写这个程序的过程中，我复习了之前学的基本语法，哈弗曼树最小路径的求取，哈弗曼编码及译码的应用范围，程序结构算法等一系列的问题它使我对数据结构改变了看法。在这次设计过程中，体现出自己单独设计模具的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，也从中发现自己平时学习的不足和薄弱环节，从而加以弥补。 精品文档

数据结构课程设计

郑州工业应用技术学院 课程设计说明书 题目：手机信息数据检索 姓名：王港 院（系）：信息工程学院 专业班级：16级计算机科学与技术6班 学号：1601110241 指导教师：王礼云 成绩： 时间：2018 年 1 月 2 日至2018 年 1 月12

郑州工业应用技术学院 课程设计任务书 题目手机信息数据检索 专业、班级16级计算机科学与技术6班学号1601110241姓名王港 主要内容： 开发一个手机信息数据检索，使管理员可以很好的管理回收的手机，避免平时废旧手机没有作用，不知道如何去处理旧的手机等问题。减轻废旧手机资源的浪费。本废旧手机回收系统利用单链表实现了基本信息的添加。管理员能够对各种信息进行修改，例如手机信息添加，手机信息删除，密码修改，退出系统。 基本要求： 1、巩固并加深学生对数据结构基本算法的理解； 2、认识面向过程和面向对象两种设计方法的区别； 3、进一步掌握和应用VC++6.0 集成开发环境； 4、提高运用对于数据结构的理解，增强了我解决实际问题的能力； 5、初步掌握开发小型实用软件的基本方法。 主要参考资料： [1]谭浩强. C语言基础课程[M].北京:清华大学出版社,2009. [2]刘振安. C程序设计课程设计[M].北京:机械工业出版社,2016. [3]滕国文. 数据结构课程设计[M].北京:清华大学出版社, 2010. [4]吴伟民. 数据结构[M].北京:清华大学出版社, 2017. 完成期限：2018.1.2-2018.1.12 指导教师签名： 课程负责人签名： 2018 年1 月12 日

摘要 21世纪以来，经济高速发展，人们生活发生了日新月异的变化，特别是手机普及到每个人生活的各个领域。但对于手机的回收越来越不适应现在社会的发展。计算机技术的飞速发展，也为我们带来了巨大的便利。为了适应现代人们回收旧手机方便的愿望。手机信息管理系统软件能够为我们现如今手机回收带来巨大的便利。 我国现如今已经成为手机产品的生产消费大国，伴随着通信技术的迅猛发展，手机更新换代的速度不断提高。特别是追求时尚潮流的大学生群体手机的更换频率增加更快。随着智能手机产品不断推陈出新，手机更新换代的周期也在缩短。据业内人士估计，我国存量闲置手机至少以亿计，但旧手机的回收率却不到2%，旧手机的处置成为一大问题。 中国目前废旧手机的回收现状和回收模式，造成我国手机回收效率低下，更是对垃圾回收产业带来了巨大的冲击，同时目前，我国年废旧手机产生量约上亿部，大部分闲置家中，未能有效回收利用。既浪费了资源，又威胁居民身心健康，造成环境污染。在分析我国废旧手机回收利用现状的基础上，提出了完善废旧手机回收的法律制度、增强消费者环保意识、构建绿色环保废旧手机回收利用新模式等建议。本手机信息数据检索为回收手机的人管理废旧的手机使用，使用单链表实现，对于信息的增加删除效率比较高，可以很方便的进行各种信息管理，对于数据的管理可以让我们更好的面对管理手机的繁杂工作。 关键字：信息检索；冒泡算法；单链表

数据结构课程设计报告

数据结构课程设计 设计说明书 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..

数据结构课程设计报告

《数据结构课程设计》报告 题目：课程设计题目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

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

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

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