本文目录
数据结构教程第二十六课图的定义与术语
教学目的： 掌握图的定义及常用术语 教学重点： 图的常用术语 教学难点： 图的常用术语 授课内容： 一、图的定义 图是一种数据元素间为多对多关系的数据结构，加上一组基本操作构成的抽象数据类型。ADT Graph{ 数据对象V ：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R： R={VR} VR={ |v,w(-V且P(v,w), 表示从v到w的弧，谓词P(v,w)定义了弧 的意义或信息} 基本操作P： CreateGraph(&G,V,VR); 初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和VR的定义构造图G DestroyGraph(&G); 初始条件：图G存在 操作结果：销毁图G LocateVex(G,u); 初始条件：图G存在，u一G中顶点有相同特征 操作结果：若G中存在顶点u, 则返回该顶点在图中位置；否则返回其它信息。 GetVex(G,v); 初始条件：图G存在，v是G中某个顶点 操作结果：返回v的值。 PutVex(&G,v,value); 初始条件：图G存在，v是G中某个顶点 操作结果：对v赋值value FirstAdjVex(G,v); 初始条件：图G存在，v是G中某个顶点 操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空” NextAdjVex(G,v,w); 初始条件：图G存在,v是G中某个顶点,w是v的邻接顶点。 操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”
数据结构教程第二课抽象数据类型的表示与实现
本课主题： 抽象数据类型的表示与实现 教学目的： 了解抽象数据类型的定义、表示和实现方法 教学重点： 抽象数据类型表示法、类C语言语法 教学难点： 抽象数据类型表示法 授课内容： 一、抽象数据类型定义（ADT） 作用：抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树或图描述遗传关系。 定义：一个数学模型以及定义在该模型上的一组操作。 关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。 例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，每个元素有的前趋和的后继。可以有这样一些操作：插入一个元素、删除一个元素等。 抽象数据类型分类 原子类型 值不可分解，如int 固定聚合类型 值由确定数目的成分按某种结构组成，如复数 可变聚合类型 值的成分数目不确定如学生基本情况 抽象数据类型表示法： 一、 三元组表示：（D，S，P） 其中D是数据对象，S是D上的关系集，P是对D的基本操作集。 二、书中的定义格式： ADT 抽象数据类型名{ 数据对象：数据对象的定义》 数据关系：数据关系的定义》 基本操作：基本操作的定义》 }ADT 抽象数据类型名 例：线性表的表示 名称 线性表 数据对象 D={ai| ai(-ElemSet,i=1,2,...,n,n》=0} 任意数据元素的集合 数据关系 R1={ | ai-1,ai(- D,i=2,...,n} 除第一个和最后一个外，每个元素有的直接前趋和的直接后继 基本操作 ListInsert(&L,i,e) L为线性表，i为位置，e为数据元素。 二、类C语言语法 类C语言语法示例 1、预定义常量和类型 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef in Status; //Status是函数的类型，其值是函数结果状态代码。 2、数据结构的存储结构 typedef ElemType first; 3、基本操作的算法 函数类型 函数名（函数参数表）{ //算法说明 语句序列 }//函数名 4、赋值语句 简单赋值： 变量名=表达式； 串联赋值： 变量名1=变量名2=...=变量名k=表达式； 成组赋值: （变量名1，...,变量名k）=（表达式1，...,表达式k); 结构名=结构名； 结构名=（值1，...，值k); 变量名=表达式； 变量名； 交换赋值： 变量名变量名； 条件赋值： 变量名=条件表达式？表达式？表达式T：表达式F 5、选择语句 1、if（表达式） 语句； 2、if（表达式） 语句； else 语句； 3、switch(表达式）{ case 值1：语句序列1；break; ... case 值n：语句序列n；break; default:语句序列n+1；break; } 4、switch{ case 条件1：语句序列1；break; ... case 条件n：语句序列n；break; default:语句序列n+1；break; } 6、循环语句 for（赋初值表达式；条件；修改表达式序列）语句； while（条件）语句； do{ 语句序列}while（条件）； 7、结束语句 return ； return; //函数结束语句 break; //case结束语句 exit(异常代码); //异常结束语句 8、输入和输出语句 scanf（，变量1，...,变量n）； 9、注释 //文字序列 10、基本函数 max（表达式1，...，表达式n） min,abs,floor,ceil,eof,eoln 11、逻辑运算 &&与运算；||或运算 例：线性表的实现： ADT List{ 数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n》=0} 数据关系: R1={ | ai-1,ai(- D,i=2,...,n} 基本操作： InitList(&L) DestroyList(&L) ListInsert(&L,i,e) ListDelete(&L,i,&e) }ADT List ListInsert(List &L,int i,ElemType e) {if(iL.length+) return ERROR; q=&(L.elem); for(p=&(L.elem);p》=q;--p) *(p+1)=*p; *q=e; ++L.length; return OK; }
C++数据结构 上机实验 图的建立与遍历 公交线路咨询
#include《stdio.h》#include《malloc.h》#define FALSE 0#define TRUE 1#define max 10typedef char vextype;typedef int adjtype;typedef struct { vextype vexs; adjtype arcs;}graph;graph g;int n,e;int visited;int Q;//建立无向图的邻接矩阵;void creategraph(graph *ga){ int i,j,k; printf("输入顶点数和边数:"); scanf("%d%d",&n,&e); printf("输入顶点信息:"); getchar(); for(i=0;i《n;i++) ga-》vexs=getchar(); getchar(); for(i=0;i《n;i++) for(j=0;j《n;j++) ga-》arcs=0; printf("输入边的两个顶点\n"); for(k=0;k《e;k++) { scanf("%d%d",&i,&j); ga-》arcs=1; } }//深度优先搜索;void DFS(int i){ int j; printf("node:%c\n",g.vexs); visited=1; for(j=0;j《n;j++) if((g.arcs)) DFS(j);}//广度优先搜索;void BFS(int m){ int i,j; int rear=-1,front=-1; printf("node:%c\n",g.vexs); visited=1; rear++; Q=m; while(front!=rear) { front++; i=Q; for(j=0;j《n;j++) if((g.arcs)) { printf("node:%c\n",g.vexs); visited=1; rear++; Q=j; } }}//主函数;int main(){ int i,j,k,m; creategraph(&g); printf("顶点信息: "); for(i=0;i《n;i++) printf("%c",g.vexs); printf("\n"); printf("图的邻接矩阵是:\n"); for(i=0;i《n;i++) { for(j=0;j《n;j++) printf(" %d",g.arcs); printf("\n"); } for(i=0;i《n;i++) visited=0; printf("请输入深度优先搜索的开始结点序号:\n"); scanf("%d",&k); printf("深度优先搜索的结果是:\n"); DFS(k); for(i=0;i《n;i++) visited=0; printf("请输入广度优先搜索的开始结点序号:\n"); scanf("%d",&m); printf("广度优先搜索的结果是:\n"); BFS(m); system("pause"); }#include《iostream.h》#include《stdlib.h》#define defaultvertices 30typedef char T;typedef int E;const E maxweight=999;class graphmtx{public: graphmtx(int sz=defaultvertices);// ~graphmtx(){delete edge;} bool isempty()//图空 { if(numedges==0)return true; else return false; } bool isfull()//图满 { if(numvertices==maxvertices||numedges==maxvertices*(maxvertices-1)/2)return true; else return false; } int numofvertices(){return numvertices;}//顶点数 int numofedges(){return numedges;}//边数 T getvalue(int i){return i》=0&&i《=numvertices?verticeslist:NULL;}//取顶点值 E getweight(int v1,int v2){return v1!=-1&&v2!=-1?edge:0;} int getfirstneighbor(int v); int getnextneighbor(int v,int w); bool insertvertex(const T&vertex); bool insertedge(int v1,int v2,E cost); bool removevertex(int v); bool removeedge(int v1,int v2); int getvertexpos(T vertex)//取顶点在图中的位置 { int i; for(i=0;i《numvertices;i++) { // cout《《vertex; // cout《《verticeslist; if(verticeslist==vertex) { return i; } } return -1; } int maxvertices; int numedges; int numvertices;private: T *verticeslist; E **edge;};//构造graphmtx::graphmtx(int sz){ maxvertices=sz; numvertices=0; numedges=0; int i,j; verticeslist=new T; edge=(E**)new E*; for(i=0;i《maxvertices;i++) edge; for(i=0;i《maxvertices;i++) for(j=0;j《maxvertices;j++) edge=(i==j)?0:maxweight;}//插入顶点bool graphmtx::insertvertex(const T &vertex){ if(numvertices==maxvertices) return false; verticeslist=vertex; return true;}//删除顶点bool graphmtx::removevertex(int v){ if(v《0||v》numvertices) return false; if(numvertices==1) return false; int i,j; verticeslist; for(i=0;i《numvertices;i++) { if(edge《maxweight) numedges--;} for(i=0;i《numvertices;i++) edge; numvertices--; for(j=0;j《numvertices;j++) edge; for(i=0;i《numvertices;i++) edge=maxweight; return true;}//插入边bool graphmtx::insertedge(int v1,int v2,E cost){ if(v1》-1&&v1《numvertices&&v2》-1&&v2《numvertices&&edge==maxweight) { edge=cost; numedges++; return true; } else return false;}//删除边bool graphmtx::removeedge(int v1,int v2){ if(v1》-1&&v1《numvertices&&v2》-1&&v2《numvertices&&edge《maxweight) { edge=maxweight; numedges--; return true; } else return false;}//取第一个邻接点int graphmtx::getfirstneighbor(int v){ if(v!=1) { for(int col=0;col《numvertices;col++) {if(edge《maxweight) return col;} } return -1;}//取第二个邻接点int graphmtx::getnextneighbor(int v,int w){ if(v!=-1&&w!=-1) { for(int col=w+1;col《numvertices;col++) { if(edge《maxweight) return col;} } return -1;}istream& operator》》(istream& in,graphmtx& g){ int i,j,k,n,m; T e1,e2; E weight; cout《《"请输入区域内场所数以及路线数"《《endl; cin》》n》》m; cout《《"请输入场所（以一个字母表示）"《《endl; for(i=0;i《n;i++) { cin》》e1; g.insertvertex(e1); } i=0; cout《《"请输入有公交线路的两地及时间"《《endl; while(i《m) { in》》e1》》e2》》weight; j=g.getvertexpos(e1); k=g.getvertexpos(e2); if(j==-1||k==-1) cout《《"error"《《endl; else{ g.insertedge(j,k,weight); i++;} } return in;}//求最短路径长度void shortespath(graphmtx& g,int& v,int &vv,E dist最短路径中前一顶点{ int n=g.numofvertices(); bool * s=new bool;//true表示顶点的最短路径已确定 int i,j,k,m=vv; E w,min;//min未确定的点中 路径最短的顶点的距离 for(i=0;i《n;i++) { dist=g.getweight(v,i); s=false; if(i!=v&&dist=v; else path=-1; } s=true; dist=0; int u;//确定最短路径的顶点 for(i=0;i《n-1;i++) { min=maxweight; u=v; for(j=0;j《n;j++) { if(s《min) { u=j; min=dist; } s=true; for(k=0;k《n;k++) { w=g.getweight(u,k); if(s) { dist+w; path=u; } } } } for(m=vv;m!=v;m=path) { cout《《g.getvalue(m)《《"→"; } cout《《g.getvalue(m)《《endl; }int main(){ graphmtx graph(10); int k,n,v,vv; T v0,v00; E *dist; int *path; cout《《"请建立公交线路网"《《endl; cin》》graph; cout《《"求两地最短路径"《《endl《《"继续请输入1,退出请输入0"《《endl; while(1) { cin》》k; switch(k) { case 1: cout《《"请输入起点"《《endl; cin》》v00;// cout《《v00; vv=graph.getvertexpos(v00);// cout《《vv; cout《《"请输入终点"《《endl; cin》》v0;// cout《《v0; v=graph.getvertexpos(v0);// cout《《v; cout《《"乘车方法如下"《《endl; n=graph.numofvertices(); dist=new E; path=new int; shortespath(graph,v,vv,dist,path); cout《《"最短时间为："《《dist《《endl; cout《《"继续请输入1,退出请输入0"《《endl;// printshortestpath(graph,v,vv,dist,path); break; case 0: exit(0); default: break; } } return 0;}
数据结构完整版实验报告
(一)实验目的和要求实验目的：熟练掌握线性表的基本操作在顺序存储结构上的实现。实验要求：任选一种高级程序语言编写源程序，并调试通过，测试正确。(二)实验主要内容1.建立n个元素的顺序表SqList，实现顺序表的基本操作；2.在SqList的元素i之后插入一个元素，实现顺序表插入的基本操作；3.在sqList中删除指定位置i上的元素，实现顺序表删除的操作。4.(三)主要仪器设备PC机，Windows XP操作平台，Visual C++(四)实验原理顺序表操作：定义一个顺序表类，该类包括顺序表的存储空间、存储容量和长度，以及构造、插入、删除、遍历等操作的方法(五)实验步骤与调试分析：顺序表操作：先构造有四个数据的顺序表，在第4个位置插入9，再读取并删除第3个元素。(六)实验结果与分析：顺序表操作：（七）附录（源程序）：#include《iostream》using namespace std;const int LIST_INIT_SIZE=10;//顺序表初始长度const int LISTINCREMENT=5;//顺序表长度增值class SqList{int *L;//定义存储空间起始地址int length;//顺序表当前长度int listsize;//顺序表当前存储容量bool flag;//设立标志值记录操作成败public:SqList(int v1,int v2,int v3,int v4);//构造函数构造并初始化顺序表void ListInsert(int i,int e);//实现将e插入到顺序表中第i个位置void ListDelete(int i,int &e);//实现删除顺序表第i个元素void ListVisit();//实现顺序表的遍历};SqList::SqList(int v1,int v2,int v3,int v4)//构造并初始化顺序表{L=new int;if(!L)//分配失败{flag=false;cout《《"ERROR"《《endl;}else//分配成功，进行初始化{*L=v1;*(L+1)=v2;*(L+2)=v3;*(L+3)=v4;length=4;listsize=LIST_INIT_SIZE;flag=true;}}void SqList::ListInsert(int i,int e)//插入元素{int *p,*q;int t;if(i《1||i》length+1)cout《《"ERROR"《《endl;//插入位置错误else {if(length==listsize)//空间不足，增加分配{p=new int;if(!p)cout《《"ERROR"《《endl;//分配失败else//分配成功，复制顺序表{for(t=0;t《length;t++)*(p+t)=*(L+t);q=L;L=p;p=q;delete q;listsize+=LISTINCREMENT;}}for(t=length;t》=i;t--)*(L+length)=*(L+length-1);*(L+i-1)=e;length++;//插入成功，表长加1}}void SqList::ListDelete(int i,int &e){if(i《1||i》length)cout《《"ERROR"《《endl;//删除位置错误else {e=*(L+i-1);while(i《length){*(L+i-1)=*(L+i);i++;}length--;//删除成功表长减1}}void SqList::ListVisit()//遍历{int i;for(i=0;i《length;i++)cout《《" "《《*(L+i);cout《《endl;}int main(){int e=0;SqList list(2,3,4,5);list.ListVisit();list.ListInsert(4,9);list.ListVisit();list.ListDelete(3,e);list.ListVisit();cout《《"e="《《e《《endl;return 0;}
数据结构上机实验（单链表）~
东西真么多才10分啊。。。。 这个程序主要是单链表的操作！ #include《iostream》 #include《iomanip》 using namespace std; struct node{ double data; struct node *next; }; struct node *create(); struct node *rescreate(); void printlist(struct node *head); int len(struct node *head); void insertnode(struct node *head,int i,double x) ; void delnode(struct node *head,double x); void delnode2(struct node *head,int i); void sort(struct node *head); int main() { struct node *p; p=rescreate(); printlist(p); //cout《《endl《《len(p)《《endl; insertnode(p,3,-100); cout《《endl; printlist(p); delnode2(p,4); cout《《endl; printlist(p); sort(p); cout《《endl《《"After sort\n"; printlist(p); system("pause"); return 0; } struct node *create() { struct node *head,*oldp,*p,*s; double newnum; head=new struct node; oldp=head; cin》》newnum; while(newnum!=-32768){ p=new struct node; p-》data=newnum; oldp-》next=p; oldp=p; cin》》newnum; } s=head; head=head-》next; delete s; p-》next=head; return head; } struct node *rescreate() { struct node *tail,*oldp,*p; double newnum; tail=NULL; oldp=tail; cin》》newnum; while(newnum!=-32768){ p=new struct node; p-》data=newnum; p-》next=oldp; oldp=p; cin》》newnum; } return p; } void printlist(struct node *head) { while(head){ cout《《setw(5)《《head-》data; head=head-》next; } } int len(struct node *head) { int n=0; while(head){ n++; head=head-》next; } return n; } //在单链表第 i(0=《i《=len(head)) 个结点之后插入一个新结点，其值为 x void insertnode(struct node *head,int i,double x) { struct node *p,*s; int j; s=new struct node; s-》data=x; if(i《0 || i》len(head)) cout《《"插入位置错误\n"; if(i==0){ s-》next=head; head=s; } else{ p=head; j=1; while(p && j《i){ j++; p=p-》next; } if(p){ s-》next=p-》next; p-》next=s; } } } //删除单链表中一个 值为 x 的结点 void delnode(struct node *head,double x) { struct node *p,*s; if(head-》data==x){ p=head; head=head-》next; delete p; } else{ s=head; p=head-》next; while(p && p-》data!=x){ s=p; p=p-》next; } if(p){ s-》next=p-》next; delete p; } else cout《《"找不到\n"; } } //删除单链表中 第 i 的结点 void delnode2(struct node *head,int i) { struct node *p,*s; int j; if(i==1){ p=head; head=head-》next; delete p; } else{ s=head; p=head-》next; j=2; while(p && j《i){ j++; s=p; p=p-》next; } if(p){ s-》next=p-》next; delete p; } else cout《《"找不到\n"; } } //单链表排序---起泡 void sort(struct node *head) { int i; struct node *p,*s1,*s2; double temp; int n; n=len(head); p=head; for(i=1;i《n;i++){ s1=p; s2=p-》next; while(s2){ if(s1-》data》s2-》data){ temp=s1-》data; s1-》data=s2-》data; s2-》data=temp; } s1=s1-》next; s2=s2-》next; } } } 还有一个主要是单链表的建立，插入，排序等！ #include《iostream》 #include《iomanip》 using namespace std; struct node{ float data; node *next; }; //正序建立单链表，数据依次插入链表头之后 node * create() { node *head,*p,*s; float newnum; head=new node;; p=head; cin》》newnum; while(newnum》=0){ s=new node; s-》data=newnum; p-》next=s; p=s; cin》》newnum; } head=head-》next; //删除头结点 p-》next=NULL; //若为p-》next=head; 则为循环单链表 return(head); } //逆序建立单链表，数据依次插入链表尾之前 node * reversecreate() { node *tail,*oldptr,*ptr; float newnum; ptr=NULL; tail=ptr; cin》》newnum; while(newnum》=0){ oldptr=ptr; ptr=new node; ptr-》data=newnum; ptr-》next=oldptr; cin》》newnum; } return(ptr); } //打印链表 void printlist(node *listhead) { while(listhead!=NULL){ cout《《setw(5)《《listhead-》data; listhead=listhead-》next; } } //查找某个结点 void find(node *head,float x) { node *p; p=head; while(p-》data!=x && p!=NULL) p=p-》next; if(p!=NULL) cout《《"找到了!\n"; else cout《《"未找到!\n"; } //求单链表的长度（结点个数） int length(node *head) { int n=0; node *p; p=head; while(p!=NULL){ p=p-》next; n++; } return n; } //在单链表中插入一个结点，其值为x，插入第i(i》=0)个结点之后 void insertnode(node *head,int i,float x) { node *s,*p; int j; s=new node; s-》data=x; if(i==0){ s-》next=head; head=s; } else{ p=head; j=1; //查找第i个结点，由p指向 while(p!=NULL && j《i){ j++; p=p-》next; } if(p!=NULL){ s-》next=p-》next; p-》next=s; } else cout《《"未找到!\n"; } } //在单链表中删除一个结点，其值为x void deletenode(node *head,float x) { node *p,*s; if(head==NULL) cout《《"链表下溢!\n"; if(head-》data==x){ p=head; head=head-》next; delete p; } else{ s=head; p=head-》next; while(p!=NULL && p-》data!=x) if(p-》data!=x){ s=p; p=p-》next; } if(p!=NULL){ s-》next=p-》next; delete(p); } else cout《《"未找到!\n"; } } int main( ) { node *linktable; cout《《"Input positive values, ends with a negative one\n"; cout《《"The list of input values:\n"; printlist(create()); printlist(reversecreate()); cout《《length(create()); linktable=create(); insertnode(linktable,2,100); printlist(linktable); cout《《endl《《length(linktable)《《endl; deletenode(linktable,3); printlist(linktable); cout《《endl《《length(linktable)《《endl; cin.get(); cin.get(); return 0; }
