东莞理工学院城市学院《算法与数据结构》课程设计

东莞理工学院城市学院《算法与数据结构》课程设计

东莞理工学院城市学院

《算法与数据结构》课程设计

题 目： 广义表的操作 专 业： 计算机科学与技术（本） 年 级： 2005级 计科 专业 2 班 姓 名： 陈嘉威 指导教师： 张娟 老师 时 间： 2006-2007 学年第18周 地 点： 4号楼7楼C号机房

东莞理工学院城市学院计算机与信息科学系制

2007年 6 月

东莞理工学院城市学院《算法与数据结构》课程设计

实习报告的内容

引言：广义表是N（N>0）个元素的有限序列:A=(a1,a2,….an)，其中，A是广义表的名称，n是它的长度，ai（1<i<n）或者是数据元素，或者是广义表。广义表的定义是一个递归的定义，广义表中包含广义表。对于广义表A中的某个元素ai是一个数据元素，称为A的一个原子；当其不是一个数据元素时，则称它为广义表的一个子表。试求广义表的广度和深度。 基本要求程序能遍历广义表，并求出深度和广度。

(1) 问题描述。

广义表的四个基本操作，创建，遍历，长度，深度。广义表如何创建？广义表如何遍历？广义表如何算其长度？广义表入如何算其深度？

我在这次工程设计中负责各同学负责的程序的连接，和最终调试。还有程序的调用。

(2) 设计。

设计思想：

（1） 存储结构。

对于广义表中的数据元素可以具有不同的结构，或者是原子，或者是列表，因此难以用顺序存储结构表示，所以通常采用链式存储结构，每个元素可用一个结点表示。包括4个域，标志域 tag，数据域 data，*next指向后继结点的指针域 , *subList 指向后继列表的指针域.

（2） 主要算法基本思想

广义表允许递归，所以通过自身调用自身，然后通过判断条件，判断递归调用完成。 广义表的深度定义为广义表中括弧的重数，是广义表的一种量度。若ai是原子，则由定义可以知道深度为零。空表也是广义表，并且定义可以知道空表的深度为1。

1． 在计算广义表长度的时候，通过语句：return 1 + lenthGList(gl->next);递归调用，然后通过if(gl != NULL)语句，跳出循环。

2． 在计算广义表深度的时候，通过语句：int dep = depthGList(gl->a.subList);递归调用，然后通过if(gl->tag == 1)，在while(gl!= NULL)前，利用if(dep > max)，不断比较dep与max，查找出dep最大的数。

设计表示：

东莞理工学院城市学院《算法与数据结构》课程设计

实现注释：完成了基本的功能，通过递归调用实现程序。

(2) 调试报告。

在这次的项目制作中，我负责的地方是连接其他组员所做的小程序，并负责最终调试程序。

在调试的过程中，我遇到了指针的调用，有时调用数值无法传递到我想要传值的地方。导致调用时，无法达到理想的答案。所以需要细心的分析整体程序，逐步在脑中进行运算。 了解整体程序的运行过程，尤其是在传值的地方。每个同学在做程序的时候，都会用自己的喜好来定义变量名，这对于我后来的连接人为制造了一个很大的困难。所以要做要需求分析时，在做程序以前要订立好每个人的目标和工作事项。有用到与别人有相关联的地方，要详细相讨论，并把讨论的结果列表写好，供其他组员参阅和理解。

(4) 系统环境（源代码和运行结果）抓图。

东莞理工学院城市学院《算法与数据结构》课程设计

(5) 结果分析。

输入：((a),b,(c,(d,f)),(u))；

东莞理工学院城市学院《算法与数据结构》课程设计

运行结果：

输出广义表：((a),b,(c,(d,f)),(u))

广义表长度：4

广义表深度：3

(6) 附录。

详细程序如下：

#include <stdio.h>

#include <stdlib.h>

typedef char elemType;

/************************************************************************/ /* 以下是关于广义表操作的4个简单算法 */ /************************************************************************/ typedef struct GNode{

int tag; /* 标志域：取0表示单元素结点；取1时表示子表结点 */ union{

elemType data; /*数据域*/

struct GNode *subList; /* 指向后继列表的指针域 */

}a;

struct GNode *next; /* 指向后继结点的指针域 */

};

/* 1.求广义表的长度 */

int lenthGList(struct GNode *gl)

{

if(gl != NULL){

return 1 + lenthGList(gl->next);

}else{

return 0;

东莞理工学院城市学院《算法与数据结构》课程设计

}

}

/* 2.求广义表的深度 */

int depthGList(struct GNode *gl)

{ int dep;

int max = 0;

/* 遍历每个结点，求出所以子表的最大深度 */ while(gl!= NULL){

if(gl->tag == 1){

/* 递归求出一个子表的深度 */

int dep = depthGList(gl->a.subList);

/* 让max始终为同一个所求子表中深度的最大值 */ if(dep > max){

max = dep;

}

}

gl = gl->next; /* 让gl指向下一个结点 */

}

return (max+1); /* 返回表的深度 */

}

/* 3.建立广义表的存储结构 */

void creatGList(struct GNode **gl)

{

char ch; /* 读入一个字符，此处可能读入'＃'，'（'，'）'，','或者英文字母 */ scanf("%c", &ch);

/* 若输入为＃，则置表头指针为空 */

if(ch == '#'){

*gl = NULL;

}

/* 若输入左括号则建立由*gl所指向的子表结点并递归构造子表 */

else if(ch == '('){

*gl = malloc(sizeof(struct GNode));

东莞理工学院城市学院《算法与数据结构》课程设计

(*gl)->tag = 1;

creatGList(&((*gl)->a.subList));

}

/* 若输入为字符则建立由*gl所指向的单元素结点 */

else{

*gl = malloc(sizeof(struct GNode));

(*gl)->tag = 0;

(*gl)->a.data = ch;

}

/* 此处读入的字符必为逗号或右括号或分号 */ scanf("%c", &ch);

/* 若*gl为空，则什么都不做 */

if(*gl == NULL){

;

}

/* 若输入为逗号则递归构造后继表 */

else if(ch == ','){

creatGList(&((*gl)->next));

}

/* 若输入为右括号或分号则置*gl的后继指针域为空 */ else if((ch == ')') || (ch == ';')){

(*gl)->next = NULL;

}

return;

}

/* 4.打印广义表 */

void printGList(struct GNode *gl)

{

if(gl->tag == 1){ /* 对于表结点的处理 */

/* 存在子表，先输出左括号 */

printf("(");

/* 若子表为空，则输出'#'字符 */

if(gl->a.subList == NULL){

东莞理工学院城市学院《算法与数据结构》课程设计

printf("#");

}

/* 若子表非表，则递归输出子表 */

else{

printGList(gl->a.subList);

}

/* 当一个子表输出结束后，再输出右括号 */ printf(")");

}

/* 对单元素结点，则输出该结点的值 */ else{

printf("%c", gl->a.data);

}

/* 输出该结点的后继表 */

if(gl->next != NULL){

/* 先输出逗号分隔 */

printf(",");

/* 再递归输出后继表 */

printGList(gl->next);

}

return;

}

int main()

{

struct GNode *gl;

printf("输入一个广义表， 以右括号结束 ");

creatGList(&gl);

printf("输出广义表：");

printGList(gl);

printf(" \n");

printf("广义表的长度：");

printf("%d\n", lenthGList(gl->a.subList));

printf("广义表的深度：");

printf("%d\n", depthGList(gl->a.subList));

东莞理工学院城市学院《算法与数据结构》课程设计

system("pause");

return(0) ;

}

(7) 设计心得：

在这次设计我获益良多，我与同学一起完成了一个小程序，满足感很充足。看着自己完成的程序。设计的过程中我们遇到了调用上的问题，因为我们是分开完成总程序中的各个小程序，每个人的命名都各不相同，在调用的时候，遇到不知道调用哪个变量。所以要在设计程序阶段，定义好每个变量。

组长的责任很大，从需求分析，到基本的规划设计，再到详细的设计，每个阶段都要详细掌握，明确需要制作的目标，在脑中有清晰的程序结构。在分配工作的时候，要仔细分析每个人的能力水平，再认真定制每人的任务，避免有人没工做，有人忙到晕；有工不会做，工作太简单的情况。

总体来说，设计程序的时候，要把设计当成工程项目，用工程的理念和方法来管理和指导我们的工作。要时常保持心情平静，不慌不忙，要用耐心和细心来面对发生的问题和困难。

(8) 参考文献

如：[1] 赛奎春、张雨 编著，《Visual C++ 工程应用与项目实践》，海洋出版社，2005.1

[2] 杨秀金、张红梅 编著 《数据结构（第二版）》，西安电子科技大学出版社，2000.6

本文来源：https://www.bwwdw.com/article/llbi.html