数据结构串的操作
1.头文件：
//串类的定义
class AString
{
private:
char *ch; //串存放数组
int curLength; //串的实际长度
int maxSize; //存放数组的最大长度.
void CheckMem(); //检测内存是否申请成功
public:
AString();
AString(int sz); //构造函数,构造一个最大长度为sz,实际长度为0的字符串
AString(const char *init); //构造函数,构造一个最大长度为maxSize,由init 初始化的新字符串对象
AString(const AString &ob); //复制构造函数,由一个已有的字符串对象ob 构造一个新字符串
~AString(){delete[] ch;} //析构函数,释放动态分配的串空间并撤销该字符串对象
//与字符串对象的比较运算
int operator == (AString &ob)const {return strcmp(ch,ob.ch) == 0;} //判断当前实例是否与ob串相等,若相等则返回1,否则返回0
int operator != (AString &ob)const {return strcmp(ch,ob.ch) != 0;} //判断当前实例是否与ob串不等,若不等则返回1,否则返回0
int operator < (AString &ob)const {return strcmp(ch,ob.ch)<0;} //判断当前实例串是否小于ob串,若小于则返回1,否则为0
int operator > (AString &ob)const {return strcmp(ch,ob.ch)>0;}//判断当前实例串是否大于ob串,若小于则返回1,否则为0
int operator <= (AString &ob)const {return strcmp(ch,ob.ch)<=0;}//判断当前实例串是否小于等于ob串,若小于等于则返回1,否则为0
int operator >= (AString &ob)const {return strcmp(ch,ob.ch)>=0;}//判断当前实例串是否大于等于ob串,若大于等于则返回1,否则为0
//与字符串的比较运算
int operator == (char *str)const{return strcmp(ch,str) == 0;} //判断当前实例是否与C++串相等,若相等则返回1,否则返回0
int operator != (char *str)const{return strcmp(ch,str) != 0;}//判断当前实例是否与C++串不相等,若不等则返回1,否则返回0
int operator < (char *str)const {return strcmp(ch,str)<0;}//判断当前实例是否与小于C++串,若小于则返回1,否则返回0
int operator > (char *str)const{return strcmp(ch,str)>0;}//判断当前实例是否与大于C++串,若小于则返回1,否则返回0
int operator <= (char *str)const{return strcmp(ch,str)<=0;}//判断当前实例是否与小于等于C++串,若小于等于则返回1,否则返回0
int operator >=(char *str)const {return strcmp(ch,str)>=0;}//判断当前实例是否与大于等于C++串,若大于等于则返回1,否则返回0
AString& operator = (AString &ob); //将串ob赋值给当前实例.
AString& operator = (const char *str); //将字符串赋值给字符串对象
AString& operator +=(AString &ob); //若当前实例串长度与ob串长度之和不超过maxSize则把ob串接在当前实例的后面.
AString& operator +=(const char *str); //若当前实例串长度与str串长度之和不超过maxSize,则把str串接到串对象后面.
char& operator[](int i); //取当前实例的第i个字符返回.
bool IsEmpty()const{return curLength == 0;} //判空函数
int Length() const{return curLength;} //返回当前实例的实际字符长度.
//下面主要是常用函数的重载等等，方便各种调用方法
void SubString(AString &subs,int index,int length); //从索引index开始截取length长度的字符串返回.
AString& Remove(int startIndex,int length); //以索引startIndex开始删除length个字符
AString& Insert(int pos,const char *value);
void Clear(); //清空当前字符串对象
void Output(); //输出
};
//串类的实现
void AString::CheckMem()
{
if(ch == NULL)
{
cerr<<"内存分配失败!\n";
exit(1);
}
}
AString::AString()
{
maxSize = defaultSize;
curLength = 0;
ch = new char[maxSize];
CheckMem();
ch[0] = '\0';
}
AString::AString(int sz)
{//串构造函数
maxSize = sz;
ch = new char[maxSize+1];
CheckMem();
curLength = 0;
ch[0] = '\0';
}
AString::AString(const char *init)
{//串构造函数
int initLength = strlen(init);
maxSize = (initLength > defaultSize) ? initLength : defaultSize;
ch = new char[maxSize+1];
CheckMem();
curLength = initLength;
strcpy(ch,init);
}
AString::AString(const AString &ob)
{//串对象复制构造函数
maxSize = ob.maxSize;
ch = new char[maxSize+1];
CheckMem();
strcpy(ch,ob.ch);
curLength = ob.curLength;
}
AString& AString::operator =(AString &ob)
{
if(&ob != this)//若两个串相等为自我赋值
{
Clear();
curLength = ob.curLength;
strcpy(ch,ob.ch);
}
else
cout<<"字符串自身赋值出错!\n";
return *this;
}
AString& AString::operator =(const char *str)
{//字符串赋值
int strLength = strlen(str);
maxSize = strLength>maxSize?strLength:maxSize;
Clear();
strcpy(ch,str);
curLength = strLength;
return *this;
}
AString& AString::operator +=(AString &ob)
{//字符串对象连接
char *tempCH = ch;
char *tempOb = ob.ch;
int addLength = curLength+strlen(tempOb);
maxSize = maxSize>addLength?maxSize:addLength;
char *temp = new char[maxSize+1];
char *tempT = temp;
while(*tempCH!='\0')
*tempT++=*tempCH++;
while(*tempOb!='\0')
*tempT++=*tempOb++;
*tempT++='\0';
Clear();
strcpy(ch,temp);
curLength=strlen(ch);
delete[] temp;
return *this;
}
AString& AString::operator +=(const char *str)
{//字符串连接到字符串对象
char *tempCH = ch;
int addLength = curLength+strlen(str);
maxSize = maxSize>addLength?maxSize:addLength;
char *temp = new char[maxSize+1];
char *tempT = temp;
while(*tempCH!='\0')
*tempT++=*tempCH++;
while(*str!='\0')
*tempT++=*str++;
*tempT++='\0';
Clear();
strcpy(ch,temp);
curLength=strlen(ch);
delete[] temp;
return *this;
}
char& AString::operator [](int i)
{//读取索引位置上的字符
if(i<0||i>curLength)
{
cerr<<"字符下标越界\n";
exit(1);
}
return ch[i];
}
void AString::SubString(AString &subs,int index,int length) {
if(index<0||index+length>maxSize||length<0)
{
cerr<<"或索引或者长度越界\n";
exit(1);
}
if(IsEmpty())
cerr<<"字符串对象为空\n",exit(1);
else
{
char *temp = new char[length+1];
if(temp==NULL)
{
cerr<<"内存分配错误！\n";
exit(1);
}
for(int i=0,j=index;i { temp[i] = ch[j]; } temp[length] = '\0'; subs=temp; } } AString& AString::Remove(int startIndex,int length) { if(startIndex<0||startIndex+length>maxSize||length<0) { cerr<<"索引或长度越界\n"; exit(1); } if(IsEmpty()) cerr<<"字符串对象为空\n",exit(1); for(int i=0;i { ch[i+startIndex] = ch[i+length+startIndex]; } ch[curLength-length] = '\0'; curLength=strlen(ch); return *this; } AString& AString::Insert(int pos,const char *value) { if(pos>curLength||pos<0) { cerr<<"试图插入的位置越界\n"; exit(1); } int addLength = strlen(value) + curLength; maxSize = addLength>maxSize?addLength:maxSize; char *temp = new char[maxSize+1]; char *tempCH = ch; char *tempH = temp; for(int i=0;i *temp++ = *tempCH++;//先将当前对象中插入位置之前的字符复制到tempH指向的内存中 while(*value!='\0') *temp++=*value++;//再将待插入的字符串连接到tempH指向的内存中while(*tempCH!='\0') *temp++=*tempCH++;//最后将当前对象插入位置之后的字符连接到tempH指向的内存中 *temp='\0'; Clear(); //清空当前对象 strcpy(ch,tempH);//将拼接好的字符串复制到实例中 curLength=strlen(ch); return *this; } void AString::Clear() { delete[] ch; ch = new char[maxSize+1]; CheckMem();//释放内存并重新申请 ch[0] = '\0';//将串对象置为空 curLength = 0; } void AString::Output() { if(IsEmpty()) cerr<<"字符串对象为空"< else cout< } 2.主程序： #include #include"stdio.h"//EOF,NULL #include const int defaultSize = 128; using namespace std; #include"AString.h" int main() { cout<<"------------------------------------------------------------------------"< cout<<"请输入初始化对象的大小："; int len; cin>>len; char *str = new char[len+1]; cout<<"\n请输入要初始化字符串(不能含有空格)："; cin>>str; AString string(len); string = str; int tag=0; while(1) { cout<<"1-删除操作\n" <<"2-插入操作\n" <<"3-连接操作\n" <<"4-截取字符串\n" <<"5-字符比较\n" <<"6-输出字符串对象\n" <<"7-清空字符对象(清空后可选择序号8来重新赋值)\n" <<"8-字符串对象赋值\n" <<"9-退出程序\n"; cout<<"\n请输入要操作的方法的序号："; cin>>tag; switch(tag) { case 1: {int index,length; cout<<"请输入要删除的起始位置："; cin>>index; cout<<"\n请输入要删除的长度："; cin>>length; string.Remove(index,length); cout<<"\n删除后的字符串："< string.Output(); break;} case 2: {int index; char *input = new char[defaultSize]; cout<<"\n请输入要插入的字符串："; cin>>input; //cout<<" 输入的串长为："< cout<<"\n请输入要插入的位置："; cin>>index; string.Insert(index,input); cout<<"\n插入字符串后的字符对象："< string.Output(); delete[] input; break;} case 3: {char *value = new char[defaultSize+1]; cout<<"\n请输入要连接的字符串："; cin>>value; AString astr = value; string+=astr; cout<<"\n连接字符串后的字符对象："< string.Output(); delete[] value; break;} case 4: {int len,i; AString subs; cout<<"\n请输入要截取的字符串长度："; cin>>len; cout<<"\n请输入开始截取的位置："; cin>>i; string.SubString(subs,i,len); cout<<"\n下面为截取后的字符串对象："; subs.Output(); break;} case 5: {char *value = new char[128]; cout<<"\n请输入要比较的字符串："; cin>>value; cout<<"\n字符串比较结果如下所示："; string.Output(); if(string>value) cout<<">"; if(string==value) cout<<"="; if(string cout< break;} case 6: cout<<"\n当前字符串对象的值如下所示："; string.Output(); break; case 7: string.Clear(); cout<<"\n字符串对象已清空！\n"; break; case 8: {char *str = new char[128]; cout<<"\n请输入要赋值的字符串(不能有空格)："; cin>>str; string = str; cout<<"\n赋值后的字符串对象为："; string.Output(); break;} case 9: cout<<"运行结束"< return 0; break; default: cout<<"选择非法，请重选!"; break; } } } 数据结构实验指导书 一、实验目的 《数据结构》是计算机学科一门重要的专业基础课程，也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法，并做了相应的性能分析和比较，课程内容丰富，理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： 1）理论艰深，方法灵活，给学习带来困难； 2）内容丰富，涉及的知识较多，学习有一定的难度； 3）侧重于知识的实际应用，要求学生有较好的思维以及较强的分析和解决问题的能力，因而加大了学习的难度； 根据《数据结构》课程本身的特性，通过实验实践内容的训练，突出构造性思维训练的特征，目的是提高学生分析问题，组织数据及设计大型软件的能力。 课程上机实验的目的，不仅仅是验证教材和讲课的内容，检查自己所编的程序是否正确，课程安排的上机实验的目的可以概括为如下几个方面： （1）加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变" 活" ，起到深化理解和灵活掌握教学内容的目的。 不少学生在解答习题尤其是算法设计时，觉得无从下手。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出 现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 (2) 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的" 小" 算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。 通过实验使学生不仅能够深化理解教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点，使学生学会如何把书本上和课堂上学到的知识用于解决实际问题，从而培养计算机软件工作所需要的动手能力。 (3) 熟悉程序开发环境，学习上机调试程序一个程序从编辑，编译，连接到运行，都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件，软件条件，只有学会使用这些环境，才能进行 程序开发工作。通过上机实验，熟练地掌握程序的开发环境，为以后真正编写计算机程序解决实际问题打下基础。同时，在今后遇到其它开发环境时就会触类旁通，很快掌握新系统的使用。 完成程序的编写，决不意味着万事大吉。你认为万无一失的程序，实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误，也能够顺利运行，但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误，只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作，尽快掌握程序调试方法是非常重要的。分析问题，选择算法，编好程序，只能说完成一半工作，另一半工作就是调试程序，运行程序并得到正确结果。 二、实验要求 常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高，但为了培养一个软件工作者所应具备的科学工作的方法和作风，也应遵循以下五个步骤来完成实验题目： 1) 问题分析和任务定义 在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的 数据结构家谱管理 系统 宁波大红鹰学院 信息工程学院 课 程 设 计 报 告 项目名 家谱查询系统 称： 白钰琦 项目组 长： 徐程凯、徐海域、项鸿伟 项目成 员： 10计科1班 班级名 称： 计算机科学与技术 专业名 称： 完成时间: 12月1日 信息工程学院制 目录 一、案例描述 ............................................................ 错误!未定义书签。 1、总体描述 ....................................................... 错误!未定义书签。 2、模块描述 ....................................................... 错误!未定义书签。 二、设计思路 ............................................................ 错误!未定义书签。 三、程序设计 ............................................................ 错误!未定义书签。 1、数据结构描述................................................ 错误!未定义书签。 2、主函数及其流程图........................................ 错误!未定义书签。 3、源程序 ........................................................... 错误!未定义书签。 四、调试与分析 ........................................................ 错误!未定义书签。 1、主菜单 ........................................................... 错误!未定义书签。 2、显示家谱信息................................................ 错误!未定义书签。 3、显示家谱中第n代人所有信息 .................... 错误!未定义书签。 4、按姓名查找某人并相应输出 ........................ 错误!未定义书签。 5、按出生日期查找家谱成员信息 .................... 错误!未定义书签。 6、为家谱中成员添加孩子信息 ........................ 错误!未定义书签。 7、为家谱中成员添加妻子信息 ........................ 错误!未定义书签。 8、删除家谱中成员及其后代信息 .................... 错误!未定义书签。 9、修改家谱中成员信息.................................... 错误!未定义书签。 10、确定家谱中两个成员关系 .......................... 错误!未定义书签。 11、按出生年月排序家谱 .................................. 错误!未定义书签。 五、设计总结 ............................................................ 错误!未定义书签。 1、完成情况 ....................................................... 错误!未定义书签。 2、心得体会 ....................................................... 错误!未定义书签。 实验九串的基本操作 #include 7.22③试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。注意：算法中涉及的图的基本操作必须在此存储结构上实现。 实现下列函数： Status DfsReachable(ALGraph g, int i, int j); /* Judge if it exists a path from vertex 'i' to */ /* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/ 图的邻接表以及相关类型和辅助变量定义如下：Status visited[MAX_VERTEX_NUM]; typedef char VertexType; typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; } ArcNode; typedef struct VNode { V ertexType data; ArcNode *firstarc; } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; Status DfsReachable(ALGraph g, int i, int j) /* Judge if it exists a path from vertex 'i' to */ /* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/ { int k; ArcNode *p; visited[i]=1; for(p=g.vertices[i].firstarc;p;p=p->nextarc) { if(p) { k=p->adjvex; if(k==j)return 1; if(visited[k]!=1) 线性表 代码一 #include "stdio.h" #include "malloc.h" #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { int * elem; int length; int listsize; }SqList; int InitList_Sq(SqList *L) { L->elem = (int*)malloc(LIST_INIT_SIZE*sizeof(int)); if (!L->elem) return ERROR; L->length = 0; L->listsize = LIST_INIT_SIZE; return OK; } int ListInsert_Sq(SqList *L, int i,int e) { int *p,*newbase,*q; if (i < 1 || i > L->length+1) return ERROR; if (L->length >= L->listsize) { newbase = (int *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof (int)); if (!newbase) return ERROR; L->elem = newbase; L->listsize += LISTINCREMENT; } q = &(L->elem[i-1]); //插入后元素后移for(p=&(L->elem[L->length-1]);p>=q;p--) *(p+1)=*p; *q=e; L->length++; return OK; } int ListDelete_Sq(SqList *L, int i, int *e) { 1数据结构课程研究的主要内容包括（）（）（） 2一个完整的算法应该具有_____ _____ ______ ______ ______五个特性 3数据的逻辑结构可分为_____ ______两大类 4数据的逻辑结构是指而存储结构是指 5逻辑上相邻的数据元素在物理位置上也相邻是存储结构的特点之一 6为了实现随机访问线性结构应该采用存储结构 7链式存储结构的主要特点是 8算法分析主要从和这两个方面对算法进行分析 （1）数据 （2）数据元素 （3）数据类型 （4）数据结构 （5）逻辑结构 （6）存储结构 （7）线性结构 （8）非线性结构 第二章作业 一、判断题(在你认为正确的题后的括号中打√，否则打X)。 1．线性表的逻辑顺序与存储顺序总是一致的。 2．顺序存储的线性表可以按序号随机存取。 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。7．线性表的链式存储结构优于顺序存储结构。 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 二、单项选择题。 1．线性表是( ) 。 (A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（）个元素。 (A) n/2 (B) n+1/2 (C) n -1/2 (D) n 3．线性表采用链式存储时，其地址( ) 。 #include return q; } void Delete_m(Link &L, Link p, Link q)//删除第m个{ p->next = q->next; free(q); } void main() { Link L, p, q; int n, m; L = NULL; InitList(L);//构造出一个只有头结点的空链表 printf("请输入初始密码人数每个人的密码：\n"); scanf("%d", &m);//初始密码为m scanf("%d", &n);// Creatlinklist(n, L);//构建 p = L; for (int i = 1; i <= n; i++) { q = Locate_m(p, m);//找到第m个 printf("%d", q->num); Delete_m(L, p, q);//删除第m个 } system("pause"); } 家谱管理系统 姓名：田鑫磊 学号：1514020421 (1)功能部分： 本程序共实现了6个功能分别为： 1.读出家谱并显示 2.确定指定成员在家族中的辈份 3.输出指定辈的所有成员 4.在家谱中添加新成员，并追加到文件中 5.输出指定家庭的所有成员 6. 退出本系统 (2)各功能的算法思想： 1.读出家谱并显示 存储结构用栈，按照先显示双亲，然后显示其所有孩子的顺序显示所有的家庭成员。 2.确定指定成员在家族中的辈份 用求成员所在的二叉树中的层数（按层遍历二叉树）来确定，这里采用的是递归算法3.输出指定辈的所有成员 此处定义了一个新的结构体类型（增加存储节点所在的层数），定义如下： struct { BTNode *q; int loc; //存结点所在的层数 }qu[10]; 并用一个队列来比较显示同辈分的所有成员。 4.在家谱中添加新成员，并追加到文件中 首先，输入一个新成员的名字； 然后，输入其双亲； 之后，再添加到整个存储二叉链表中。 然后，再将新的存储结构写回到文件中。 二叉链表的结点类型为：typedef struct node { ElemType data[10]; //存放成员的名字 struct node *child; //其孩子指针 struct node *brother; //其兄弟指针 }BTNode; 5.输出指定家庭的所有成员 首先，设一个栈，并设一个标记位，先置1； 然后，找到输入的要待显示的成员，将标记位置0； 再次，显示其孩子和兄弟，依次下去直到显示完其所有的亲戚。 6.退出本系统 通过一个输入字符q来控制，每完成一个功能，系统提示是否要继续操作： 实验五图的遍历及其应用实现 一、实验目的 1．熟悉图常用的存储结构。 2．掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。 3．会用图的遍历解决简单的实际问题。 二、实验内容 [题目一] ：从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。该程序包括图类型以及每一种操作的具体的函数定义和主函数。 提示： 输入示例 上图的顶点和边的信息输入数据为： 5 7 DG A B C D E AB AE BC CD DA DB EC [题目二]：在图G中求一条从顶点 i 到顶点 s 的简单路径 [题目三]：寻求最佳旅游线路（ACM训练题） 在一个旅游交通网中，判断图中从某个城市A到B是否存在旅游费用在s1-s2元的旅游线路，为节省费用，不重游故地。若存在这样的旅游线路则并指出该旅游线路及其费用。 输入： 第一行：n //n-旅游城市个数 第2行：A B s1 s2 //s1,s2-金额数 第3行---第e+2行 ( 1≤e≤n(n-1)/2 ) 表示城市x,y之间的旅行费用，输入0 0 0 表示结束。 输出： 第一行表示 A到B的旅游线路景点序列 第二行表示沿此线路，从A到B的旅游费用 设计要求： 1、上机前，认真学习教材，熟练掌握图的构造和遍历算法,图的存储结 构也可使用邻接矩阵等其他结构. 2、上机前，认真独立地写出本次程序清单，流程图。图的构造和遍历算法 分别参阅讲义和参考教材事例 图的存储结构定义参考教材 相关函数声明： 1、/* 输入图的顶点和边的信息,建立图*/ void CreateGraph(MGraph &G) 2、/* 深度优先搜索遍历图*/ void DFSTraverse(Graph G, int v) 3、/*广度优先搜索遍历图 */ void BFSTraverse(Graph G, int v)4、 4、/* 其他相关函数 */…… 三、实验步骤 ㈠、数据结构与核心算法的设计描述 ㈡、函数调用及主函数设计 （可用函数的调用关系图说明） ㈢程序调试及运行结果分析 ㈣实验总结 四、主要算法流程图及程序清单 1、主要算法流程图： 2、程序清单 （程序过长，可附主要部分） 顺序表的基本操作 #include int j=0; while(L.data[j]!=x) j++; if(j==https://www.doczj.com/doc/4d16841169.html,st) { cout<<"所查找值不存在！"< 第四章串 重点难点 理解"串"类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作；掌握串类型的各种存储表示方法；理解串的两种匹配算法。 典型例题 1、简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；【解】 （1）空串是指不包含任何字符的串，它的长度为零。 空白串是指包含一个或多个空格的串，空格也是字符。 （2）串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。 （3）主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。 （4）静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。 动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。 2、以HString为存储表示，写一个求子串的算法。 【解】HString 是指以动态分配顺序串为存储表示，其定义为： typedef struct { char *ch; int length; }HString; void *substr( HString *sub,HString *s,int pos,int len) {//用sub返回串s的第pos个字符起长度为len的子串。sub初始时为一空串 //pos的合法位置为0<=pos<=s->length-1 int i; if (pos<0||pos>s->length-1||len<=0) Error("parameter error!");//参数不合法，子串为空串 if (s->length 数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include >验目的 掌握顺序栈的基本操作：初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以及程序实现方法。 2.实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）分析问题的要求，编写和调试完成程序。 （3）保存和打印出程序的运行结果，并分析程序的运行结果。 3.实验内容 利用栈的基本操作实现一个判断算术表达式中包含圆括号、方括号是否正确配对的程序。具体完成如下： （1）定义栈的顺序存取结构。 （2）分别定义顺序栈的基本操作（初始化栈、判栈空否、入栈、出栈等）。 （3）定义一个函数用来判断算术表达式中包含圆括号、方括号是否正确配对。其中，括号配对共有四种情况：左右括号配对次序不正确；右括号多于左括号；左括号多于右括号；左右括号匹配正确。 （4）设计一个测试主函数进行测试。 （5）对程序的运行结果进行分析。 实验代码： #include < > #define MaxSize 100 typedef struct { ??? int data[MaxSize]; ??? int top; }SqStack; void InitStack(SqStack *st) 验目的 （1）进一步掌握指针变量的用途和程序设计方法。 （2）掌握二叉树的结构特征，以及链式存储结构的特点及程序设计方法。 （3）掌握构造二叉树的基本方法。 （4）掌握二叉树遍历算法的设计方法。 3．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）掌握一个实际二叉树的创建方法。 （3）掌握二叉链存储结构下二叉树操作的设计方法和遍历操作设计方法。 4．实验内容 （1）定义二叉链存储结构。 //////////////////////////////////////////////////////////// /////////////////// //题目：家谱资料管理 //要求：家谱用于记录某家族历代家族成员的情况与关系。现编制一个家谱资料管理软件， //实现对一个家族所有的资料进行收集整理。支持对家谱的增加，删除，更新，统计等。 //////////////////////////////////////////////////////////// /////////////////// #include int Num; //记录这个人拥有几个儿女 char Name[20]; //记录这个人的姓名 char Kind; //标示节点的种类有女G男B struct TreeNode * NextNode[20]; //记录这个人的儿女struct TreeNode * Parent; //记录这个节点的父节点 }TreeNode; void CreatTree(TreeNode *Tree); void OutPutAll(TreeNode *Tree); TreeNode * SearchTree(TreeNode *Tree,char name[],int length); void MainMenue(TreeNode *Tree); void SubMenue1(TreeNode * Tree); void SubMenue2(TreeNode *Tree); void Change(TreeNode * Tree); void AddNew(TreeNode * Tree); 实验三串 //串的基本操作 #include "stdio.h" #include "stdlib.h" #define MAXSTRLEN 255 typedef unsigned char SString[MAXSTRLEN+1]; void strlength(SString S)//求字串并放到 S[0] 中 { int m; for(m=1;S[m]!='\0';m++); S[0]=m-1; } void insert(SString S,int n,char a)//是插入的位置 a 是插入的字符{ strlength(S); int i; for(i=S[0];i>=n;i--) S[i+1]=S[i]; S[n]=a; S[S[0]+2]='\0'; } int compare(SString S,SString T) { strlength(S); strlength(T); int i; for(i=1;i<=S[0]&&i<=T[0];i++) { if(S[i]>T[i]) return 1; if(S[i] else if(S[0] 浙江大学城市学院实验报告 课程名称数据结构 实验项目名称实验十三/十四图的基本操作 学生姓名专业班级学号 实验成绩指导老师（签名）日期2014/06/09 一.实验目的和要求 1、掌握图的主要存储结构。 2、学会对几种常见的图的存储结构进行基本操作。 二.实验内容 1、图的邻接矩阵定义及实现： 建立头文件test13_AdjM.h，在该文件中定义图的邻接矩阵存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时建立一个验证操作实现的主函数文件test13.cpp（以下图为例），编译并调试程序，直到正确运行。 2、图的邻接表的定义及实现： 建立头文件test13_AdjL.h，在该文件中定义图的邻接表存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时在主函数文件test13.cpp中调用这些函数进行验证（以下图为例）。 3、填写实验报告，实验报告文件取名为report13.doc。 4、上传实验报告文件report13.doc到BB。 注: 下载p256_GraphMatrix.cpp(邻接矩阵)和 p258_GraphAdjoin.cpp(邻接表)源程序，读懂程序完成空缺部分代码。 三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路） 四. 实验结果与分析 （包括运行结果截图、结果分析等） 五.心得体会 程序比较难写，但是可以通过之前的一些程序来找到一些规律 （记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。） 【附录----源程序】 256: //p-255 图的存储结构以数组邻接矩阵表示, 构造图的算法。 #include #include 数学与计算机学院 课程设计说明书 课程名称: 数据结构与算法课程设计 课程代码: 题目: 二叉树生成家谱 年级/专业/班: 学生姓名: 学号: 开始时间: 2015 年 12 月 09 日 完成时间: 2015 年 12 月 29 日 课程设计成绩： 指导教师签名：年月日目录（小三黑体，居中） 1 需求分析 (6) 1.1任务与分析 (6) 1.2测试数据 (6) 2 概要设计 (7) 2.1 ADT描述 (7) 2.2程序模块结构 (8) 2.3各功能模块 (9) 3 详细设计 (10) 3.1结构体定义 (10) 3.2 初始化 (11) 3.3 插入操作 (13) 3.4 查询操作 (15) 4 调试分析 (18) 5 用户使用说明 (18) 6 测试结果 (18) 结论 (23) 附录 (24) 参考文献 (25) 随着计算机科学技术、计算机产业的迅速发展，计算机的应用普及也在以惊人的速度发展，计算机应用已经深入到人类社会的各个领域。 计算机的应用早已不限于科学计算，而更多地应用在信息处理方面。 计算机可以存储的数据对象不再是纯粹的数值，而扩展到了字符、声 音、图像、表格等各种各样的信息。对于信息的处理也不再是单纯的 计算，而是一些如信息存储、信息检索等非数值的计算。那么，现实 世界的各种数据信息怎样才能够存储到计算机的内存之中，对存入计 算机的数据信息怎样进行科学处理，这涉及计算机科学的信息表示和 算法设计问题。为解决现实世界中某个复杂问题，总是希望设计一个 高效适用的程序。这就需要解决怎样合理地组织数据、建立合适的数 据结构，怎样设计适用的算法，以提高程序执行的时间效率和空间效 率。“数据结构”就是在此背景下逐步形成、发展起来的。 在各种高级语言程序设计的基本训练中，解决某一实际问题的步骤一般是：分析实际问题；确定数学模型；编写程序；反复调试程序直 至得到正确结果。所谓数学模型一般指具体的数学公式、方程式等，如牛顿迭代法解方程，各种级数的计算等。这属于数值计算的一类问 题。而现实生活中，更多的是非数值计算问题，如手机中的通讯录，人们对它的操作主要是查找、增加、删除或者修改电话记录。再如，人们经常在互联网上查阅各种新闻，或查阅电子地图，人们可以在某 城区地图上查找自己所需的街道或店铺，其操作主要是搜索和查询。 下面再来分析几个典型实例，它们的主要特点是：不同实例的数据元 素之间存在不同的关系；对数据信息的处理主要有插入、删除、排序、 检索等。 关键词：网络化；计算机；对策；二叉树数据结构课程实验指导书
数据结构家谱管理系统范本
C语言数据结构串的基本操作
数据结构作业系统第七章答案
数据结构实验报告代码
数据结构作业电子版
数据结构实验一的源代码
数据结构家谱课程设计报告
数据结构 图的基本操作实现
数据结构实验程序
数据结构C语言版第四章 串
数据结构实验报告全集
数据结构家谱管理系统
数据结构串基本操作代码
数据结构实验图的基本操作
数据结构上机实验线性表单链表源代码
数据结构(二叉树)家谱管理系统
相关主题
文本预览