当前位置：文档之家 › 数据结构与运算广义表的运算设计程序

数据结构与运算广义表的运算设计程序

  • 格式：doc
  • 大小：260.00 KB
  • 文档页数：20

合肥学院 计算机科学与技术系

课程设计报告 2008 ～2009 学年第 二 学期

课程 数据结构与算法 课程设计名称 广义表的运算 学生姓名 汪阳 学号 0704032047 专业班级 07网络工程（2）班 指导教师 李红 1

2009 年 5 月 题目： 广义表的运算。本设计要求实现广义表的建立、查找、输出、取表尾、以及求深度、求逆表等。 一、问题分析与任务定义： 此程序需要完成以下几个任务：首先要将输入的用数组存储的广义表转化成以广义表的存储结构存储的广义表，这个过程也就是生成广义表；查找广义表，查找广义表要返回一个值mark，当mark=1时，程序查找到待查的元素，当mark=0时，程序没有找到待查元素；输出广义表，遍历广义表，输出广义表的遍历结果；取表尾，将广义表从第二个元素开始复制到另一个广义表中；求广义表的深度，遍历每一层广义表，将广义表内每层广义表深度最大的广义表相加为同一层所求过的子表中深度的最大值；求逆表，将广义表逆向输出。 实现本程序需要解决以下问题： 1、如何根据广义表的特点建立广义表。 2、用什么方法才能查找到广义表中每一个元素，如何标志是否找到待查元素。 3、建立广义表，如何根据广义表的存储结构的特点建立广义表。 4、求广义表的深度的依据是什么。 5、运用什么方法才能将广义表逆序。 二、概要设计和数据结构选择： 1、广义表的存储结构： 由于广义表中的元素本身又可以具有结构，是一种带有层次的非线性结构，因此难以用顺序存储的结构表示。通常采用链式存储结构，每个元素可用一个结点表示，结点结构如图1、图2所示：

图1原子结点的存储结构

图2结点的存储结构

每个结点由三个域构成。其中tag是一个标志位，用来区分当前结点是原子结点还是子表。当tag为1时，该结点是子表，第二个域为hp，用以存放子表的地址；当tag为0时，该结点是原子结点，第二个域为atom，用以存放元素值。tp域是用来存放与本元素同一层的下一个元素对应结点的地址，当该元素是所在

tag=0 atom *tp tag=1 *hp *tp 2

层的最后一个元素时，tp的值为NULL。广义表及结点类型描述如下： typedef char ElemType; typedef struct GLode//广义表结构体的定义 { int tag; /*结点类型标识*/ union { ElemType atom; /*原子值*/ struct GLode *hp; /*指向子表的指针*/ } val; struct GLode *tp; /*指向下一个元素*/ } GList; 例如：建立广义表：（a，b（c，d），e） ，如图3

图3 广义表的存储图示

2、求广义表的逆表需要用堆栈存储广义表的元素，栈的数据类型如下： typedef char ElemType; typedef struct { ElemType data[maxlen] ; int top; }SeqStack;

1 ^ 0 a 0 b 1 ^

0 c 0 d 1 ^ 0 e 1 ^ ^ 3

3、程序流程图如图4。 创建一个新结点；

main() 建立一个用字符数组存储的广义表，用字符指针s指向它

输入广义表 生成数组广义表结构 遍历广义表 建立堆栈

查找待查元素，mark=1，找到待查元素，反之，没有查到。 求广义表的逆表，并输出 求广义表的深度，并输出 求广义表的表尾，并输出 清屏 输出 “再见”

2 3 4 1

输出 结果

再见 欢迎使用 输出

0 4

图4 程序流程图

三、详细设计与编码 1、建立广义表CreateGL(char *&s)。在生成广义表之前，用一个数组存储广义表，并用指针s指向数组，通过数组中的元素生成广义表。基本思想是：在广义表表达式中，遇到左括号”(”时递归构造子表，否则构造原子结点；遇到逗号时递归构造后续广义表，直到字符串数组结束，以"\0"作为结束标志。实现过程如下： GList *CreateGL(char *&s) { 读入广义表的一个字符给ch； if (ch!=空格') {

if (ch=='(') { 递归构造子表； } else if (ch==')') 遇到')'字符,子表为空 else { 构造原子结点； } } else 串结束,子表为空 读入广义表的一个字符给ch； if (ch==',') 递归构造后续子表； else 处理表的最后一个元素 返回广义表指针 } 2、遍历广义表DispGL(GList *g)。输出广义表采用的算法思想是：若遇到tag=1的结点，这是一个子表的开始，先打印输出一个左括号”(”。如果该子表为空，则输出一个空格符；否则递归调用输出该子表。子表打印输出完后，再打印一个右括号”)”。若遇到tag=0的结点，则直接输出其数据域的值。若还有后续元素，则递归调用打印后续每个元素，直到遇到tp=NULL。其实现过程如下： 5

void DispGL(GList *g) { if (g!=NULL) { if (g->tag==1) { 输出左括号'('； if (g->val.hp==NULL) 输出一个空格； else 递归调用子表； } else 输出数据域； if (g->tag==1) 打印有括号“）”； if (g->tp!=NULL) 输出逗号“，”，递归调用输出下一个结点。 } } 3、广义表的查找：FindGListX() 在给定的广义表种查找数据域为x的结点，采用的算法思想是：若遇到tag=0的原子结点，如果是要查找的结点，则查找成功1；否则，若还有后续元素，则递归调用本过程在孩子表中查找，若还有后续元素，则递归调用本过程查找后续每个元素，直到遇到hp域为NULL的元素。 设置mark标志查找结果；mark=1；表示查找成功，否则查找失败。 本函数实现过程如下： FindGListX(GList *g,char x,int &mark) { if(g!=NULL){ if (g->tag == 0 && g->val.atom ==x) { 查找成功mark = 1; } else if(g->tag == 1) 递归调用查找后续元素； 递归查找调用后续元素； } 6

} 4、求广义表的表尾：tail(GList *s) 一个广义表的表尾指的是除去该广义表的第一个元素剩下的部分。求表尾实现过程如下： GList *tail(GList *g) { if (g==NULL) { 空表不能求表尾； } else if (g->tag==0) { 原子不能求表尾； } 将广义表除去第一个元素，其余的元素复制的广义表q中，既为该广义表的表尾。 return q; } 5.求广义表的深度GLDepth(GList *g)。 广义表的深度的递归定义是它等于所有子表中表的最大深度加1，若一个表为空或仅由单个元素所组成，则深度为1。求广义表深度的递归函数GLDepth（）如

实现过程如下：

int GLDepth(GList *g) { if (g->tag==0) 为原子时返回； g=g->val.hp; if (g==NULL) 为空表时返回1； while (g!=NULL) { if (g->tag==1) { 递归调用求出子表的深度；

GLDepth（） 1 若h为空表 max{GLDepth(sh)|sh为h的子表}+1 其他情况 7

if (dep>max) max为同一层所求过的子表中深度的最大值； } 使g指向下一个元素； } 返回表的深度(max+1) 。 } 6、求广义表的逆表NIGList(GList *g,SeqStack *s) 求广义表的逆表的算法思想是：利用广义表的遍历将广义表的元素存入一个堆栈中，然后在将栈中所有的元素出栈打印，函数的实现如下： 将广义表中的元素存入堆栈中： void NIGList(GList *g,SeqStack *s) { if(g!=NULL) { if (g->tag==1) { 将广义表中的“(”以“)”存入栈中； else 递归调用，将子表中的元素存入栈中； } else 将广义表中的元素存入栈中； if (g->tag==1) 将广义表中的")"以"("存入栈中； if (g->tp!=NULL) 将广义表中的","存入栈中； 递归将后续表的内容存入栈中。 } } 将栈中所有元素输出： void Pop(SeqStack *s) { 打印栈中元素。 }

合集下载

第1章 绪论 数据结构第2版李冬梅

第1章 绪论 数据结构第2版李冬梅


S01 L01 S01 S02 ……
索引表
分类号： 001，003…… 樊映川 出版单位： 002，…….. 华罗庚 出版时间： 004，…… 栾汝书 价格： ……..
…….
按作者名
001,… 002,…. 004,…. …….
按分类号
L S …… 002,… 001,003, ……
北京林业大学信息学院
存储内容 元素1 元素4 …….. 元素2 ……..
指针 1400 ∧ ……. 1536 …….
1536
北京林业大学信息学院
元素3
1346
数据的运算 • 逻辑结构和存储结构都相同, 但运算不同, 则 数据结构不同. 例如, 栈与队列 • 对于一种数据结构, 常见的运算
–插入 –删除 –修改 –查找 –排序
人机对奕问题
树
……..
……..
…...
…...
…...
…...
文件系统的系统结构图
树
/ (root)
bin
lib
user
etc
math
ds
sw
yin
tao
xie
Queue.cpp Stack.cpp
北京林业大学信息学院
Tree.cpp
多叉路口交通灯管理问题
C AB BA BC AC BD AD B
北京林业大学信息学院
数据结构课程的形成和发展：
形成阶段： 60年代初期，“数据结构”有关的内容散见于操作系 统、编译原理和表处理语言等课程。1968年，“数据 结构”被列入美国一些大学计算机科学系的教学计划 。 发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论 、关系等“离散数学结构”的内容。 70年代后期，我国高校陆续开设该课程。
数据结构教程与题解 (1)

数据结构教程与题解 (1)


1.2.7 数据结构
由一个逻辑结构S和定义在S上的一个基本运算集Δ构成的整体 (S,Δ) 由一个逻辑结构S、一个定义在S上的基本运算集Δ和S的一个 存储实现D所构成的整体(S,Δ,D) 数据结构(Data Structure)是指相互间存在着一种或多种关系的数据元 素的集合，它们按照某种逻辑关系组织起来，并用计算机语言 ，按一定的存储方式存储在计算机的存储器中，同时在这些数 据上定义了一个运算的集合。 简单地说，一个数据结构就是一类数据的表示及其相关操作， 它一般包括三个方面的内容：数据的逻辑结构、数据的存储结 构、数据的运算。 不混淆时，常将逻辑结构简称数据结构。
例
求3个数a，b, c中的最大值
(1)若 a>b 则 max=a, 否则 max=b (2)若 c>max 则 max=c
算法的基本特征： (1)输入：0个或多个输入； (2)输出：1个或多个输出； (3)有穷性：在有限步内结束； (4)确定性：每步清晰无二义性。 (5)可行性：每步可执行，并且执行时间是有限的。
第1章 概论
不论计算机作何用途，每一项应用总是某个程序的运行，用计 算机解决任何问题都离不开程序设计。程序设计的实质就是数 据的表示和数据的处理。 数据结构就是研究这两个方面的一些基本问题的，包括如何组 织数据、数据元素之间是什么关系、数据在计算机中如何表示 以及如何对数据进行操作等。
1.1 引言 1.2 数据结构的概念 1.3 算法分析
算法＝程序？ 程序不一定满足有穷性，即不一定是算法。如操作系统。 程序中的指令必须是机器可执行的，而算法中的指令虽要求 可执行，但不一定是“机器可执行”。
中国的煤都是＿＿? 图形描述：如流程图、N−S图 算法描述
语言描述
自然语言：非形式算法，可结合其它语言 不严格，易二义性
数据结构与算法实验报告

数据结构与算法实验报告

《数据结构与算法》综合实验报告系别：专业：学生姓名：指导教师：2011年 11月 25日实验目的掌握线性表的建立、插入、删除算法；掌握查找算法；掌握排序算法；实验要求使用C语言（环境任意）开发程序，能够对用户输入的任意一组数据，建立一个线性表，可以输出此线性表。

并且能够对此线性表进行插入、删除、查找、排序等操作。

程序流程建表如下：定义一个整型的数据类型data和next指针：定义头指针和当前结点指针，申请连续空间将单个字节大小复制给头指针，把头指针赋值给当前节点指针：若输入的数是0，则若输入不为0，把输入的数赋值给已申请的新结点，把新结点赋给当前节点的next域，再把新结点赋值给当前结点，以此方法重复执行得到如下链表：输出函数：把头指针赋值给当前结点指针，当当前节点的next域不为空时输出当前节点所指向的数据，把当前结点的next域赋值给当前节点，否则输出链表为空对此线性表进行插入、删除、查询、排序操作把已申请的结点数据域指向所输入的数再把插入w结点赋值头结点，是插入的位置，如果w=0则插入结点的next域赋值给头结点否则如果w>表长，则输出超出范围代码及运行结果（主要语句要求有注释）#include"stdafx.h"#include<stdio.h>#include<malloc.h>#define NULL 0typedef struct linknode{int data;struct linknode *next;}node;node *head;node *creat(){node *currnode,*newnode;int x;head=(node*)malloc(sizeof(node));currnode=head;do{scanf("%d",&x);newnode=(node*)malloc(sizeof(node));newnode->data=x;currnode->next=newnode;currnode=newnode;}while(x!=NULL);head=head->next;currnode->next=NULL;return head;};int length(){node *currnode;int i=0;currnode=head;while(currnode->data!=NULL){currnode=currnode->next;i++;};return i;};void print(){node *currnode;currnode=head;printf("链表如下....linklist");while(currnode->data!=NULL){printf("%d-->",currnode->data);currnode=currnode->next;};printf("NULL\n");printf("链表长度为........linklist length%d\n",length());};void delete1(){int x;node *delnode,*currnode;printf("输入要删除的数据......input delete data：");scanf("%d",&x);if(head->data==NULL) printf("此链表为空无法删除.....this linklist empty！\n"); if(head->data==x){delnode=head;head=head->next;free(delnode);if(head==NULL) printf("此链表为空.......this linklist enpty！");}else{currnode=head;delnode=currnode->next;while(delnode->data!=x&&delnode!=NULL){currnode=currnode->next;delnode=currnode->next;};if(delnode==NULL)printf("无此数据......no this data！\n");else{currnode->next=delnode->next;free(delnode);};};};void find(){node *currnode;int count=1,x;currnode=head;printf("输入要查找的数据.......input search data:");scanf("%d",&x);while(currnode->data!=NULL&&currnode->data!=x) {currnode=currnode->next;count++;};if(currnode->data!=NULL){printf("\n%d为第........is no.",currnode->data);printf("%d个数据........data。

数据结构教案

数据结构教案

数据结构教案(总32页) -CAL-FENGHAI.-(YICAI)-Company One1-CAL-本页仅作为文档封面，使用请直接删除2015 至2016 学年第二学期数据结构课程教案课程编码： 1261D03总学时／周学时： 80 / 5开课时间： 2016年2 月 24日第 1 周至第 16 周授课年级、专业、班级： 15级网工程2班使用教材严蔚敏. 数据结构（C语言版）[M] 北京：清华大学出版社，2011.系别/教研室：信息工程学院 / 物联网工程授课教师：刘波教学目标：《数据结构》是物联网工程专业的一门专业必修课。

用计算机解决任何问题都需要进行数据表示和数据处理，而数据表示和数据处理正是《数据结构》要研究的内容。

主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。

通过本课程教学，使学生了解数据结构的基本概念，理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，掌握算法描述及算法的评价标准，熟悉在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会，旨在培养学生基本的、良好的程序设计技能，编制高效可靠的程序，并为学生日后学习操作系统和数据库等后续课程奠定基础。

教学要求:本课程主要是以抽象数据类型的观点来组织和讲解线性表、栈、队列、树、二叉树、图等各种主要的数学模型并定义为相应的抽象数据类型，给出各种物理表示法和有关算法，关于数据处理技术介绍几种主要的排序和查找算法。

学生通过学习该课程后主要应掌握以下内容：1．了解数据结构及有关的基本概念；2．了解各种抽象数据类型的性质；3．掌握各种抽象数据类型的实现和基本算法；4．对算法的时间和空间复杂性有一定的分析能力；5．能够选择适当的数据结构和存储结构以及设计有效的算法，解决实际问题；6．掌握数据结构在排序和查找等常用算法中的应用。

教学重点：抽象数据类型、顺序表、单链表、循环链表、栈、队列、数组、特殊矩阵、树和二叉树、最小生成树、拓扑排序、查找、内部排序教学难点：单链表、栈、循环队列、特殊矩阵、二叉树、关键路径、最短路径教学方法与手段：1．理论部分以讲授法为主，结合讨论及课堂练习实现教学目的。