数据结构程序设计实验.doc

1、电 子 科 技 大 学实 验 报 告学生姓名： 学 号： 指导教师：实验地点：主楼A2-412 实验时间：2011.11.12一、实验室名称： 二、实验项目名称：单链表中表头、表尾及表的中间插入删除操作 三、实验学时：2学时四、实验原理：单链表的插入、删除算法五、实验目的：学会对单链表的各种操作六、实验内容：采用链式存储结构存储a,b,c,d,e,f六个字符，并完成如下操作：l (a) 显示第3个数据；l (b) 在第2个数据后插入el (c) 删除第3个数据并打印整个链表l (d) 删除链表七、实验器材（设备、元器件）：PC机一台，C语言编译环境八、实验步骤：#include #includ

2、e typedef struct nodeint data;struct node *next;node,ListNode; char List_Data(ListNode *L) int i; for(i=0;inext; printf(L-data/n,L-data);/*输出第三个数*/ /*在位置pos后面插入值为elem的一个数*/ void List_Insert(ListNode *L,int pos,char elem) int i; ListNode *s; for(i=0;inext; s-data=elem; s-next=L-next; L-next=s; /*删除位置

3、为pos的值*/ char List_Remove(ListNode *L,int pos) int i; ListNode *q; for(i=0;inext; q=L-next; L-next=q-next; free(q); if(L) printf(L-data/n,L-data); L=L-next; int main() ListNode *L; int i; char A=a,b,c,d,e; if(L) L-data=Ai; L=L-next; i+; List_Data(L); List_Insert(L,2,e); List_Remove(L,3); return 0; 九

4、、实验数据及结果分析：十、实验结论：该实验程序可实现对单链表插入和删除操作十一、总结及心得体会：通过本实验，我们学会了对单链表的各种操作，熟悉了如何编译和调试程序。 报 告 评 分： 指导教师签字：电 子 科 技 大 学实 验 报 告学生姓名： 学 号： 指导教师：实验地点：主楼A2-412 实验时间：2011.11.12一、实验室名称： 二、实验项目名称：二叉树的左右子树交换 三、实验学时：2学时四、实验原理：对二叉树的左右子树指针的交换操作和算法五、实验目的：学会对二叉树的各种操作六、实验内容：构建如图所示的二叉树；l 编写递归算法，交换二叉树的左右子树；l 输出按先序遍历得到的新二叉树结

5、果。七、实验器材（设备、元器件）：PC机一台，C语言编译环境八、实验步骤：#includetypedef struct TreeNodeint data;struct TreeNode *lchild,*rchild,*parent;TreeNode,*Tree;void Tree_Order(TreeNode *bt)if(bt!=0&bt-lchild-lchild!=0)bt=bt-lchild;void Tree_Change1(TreeNode *bt)/*交换左右子树的值*/ int k; TreeNode *s,*t; s=bt-lchild; t=bt-rchild;k=s-d

6、ata;s-data=t-data;t-data=k;void Tree_Change2(TreeNode *bt) if(bt-parent!=NULL)bt=bt-parent;Tree_Change1(bt); else bt=bt-rchild; Tree_Change1(bt);void PreOrder(TreeNode *bt)/*先序遍历并输出值*/ if(bt!=NULL) printf(bt-data/n,bt-data); PreOrder(bt-lchild); PreOrder(bt-rchild); int main() TreeNode *bt; Tree_Ord

7、er(bt); Tree_Change1(bt); Tree_Change2(bt); PreOrder(bt); return 0;九、实验数据及结果分析：十、实验结论：该实验程序可实现对二叉树左右子树的交换操作十一、总结及心得体会：通过本实验，我们学会了对二叉树左右子树的交换操作，熟悉了对程序的编译和和调试工作。 报 告 评 分： 指导教师签字：电 子 科 技 大 学实 验 报 告学生姓名： 学 号： 指导教师：实验地点：主楼A2-412 实验时间：2011.11.25一、实验室名称： 二、实验项目名称：图的最短路径 三、实验学时：2学时四、实验原理：图的邻接矩阵存储算法和Dijkstra

8、算法五、实验目的：学会对图的各种操作六、实验内容：用邻接矩阵存储并显示;l 用Dijkstra算法编程找出从a到其余顶点的最短路径（要求显示这条路径并显示相应的最短路径值）.七、实验器材（设备、元器件）：PC机一台，C语言编译环境八、实验步骤：#include#include#define MAX 7 typedef struct Cell int adj; int vertex1; int vertex2; Cells; typedef struct Graph int adj1; int vernum1; int vernum2; Graphs;void Map(Cells* C,Grap

9、hs* R,int m,int n) int i,j,t; printf(输入图中总的顶点数和边数分别为:%dt%dn,7,11); for(i=0;im;i+) printf(请输入边Ci的vertex1,vertex2和边上的权值adj:n); scanf(%dt%dt%dn,&Ci.vertex1,&Ci.vertex2,&Ci.adj); for(i=0;in;i+) for(j=0;jn;j+) for(t=0;tm;t+) Rij.vernum1=i; Rij.vernum2=j; if(i=Ct.vertex1&j=Ct.vertex2) Rij.adj1=Ct.adj; for

10、(i=0;in;i+) for(j=0;jn;j+) printf( Rij.adj=:%dt,Rij.adj1); void shortpath_DIJ(Graphs* R,int CostMAX,int n,int v0,int Distance)/求第k个顶点到各顶点最短距离 int flagMAX; int mindis,dis; int i,j,u; for(i=0;in;i+) for(j=0;jn;j+) Costij=Rij.adj1; for(i=0;in;i+) Distancei=Costv0i; flagi=0; flagv0=1; for(i=1;in;i+) min

11、dis=27; for(j=1;j=n;j+) if(flagj=0&Distancejmindis) u=j; mindis=Distancej; flagu=1; for(j=1;jn;j+) if(flagj=0) dis=Distanceu+Costuj; Distancej=(Distancejdis)?Distancej:dis; int main() Cells* C = new Cells11; Graphs* R =(Graphs*)malloc(sizeof(Graphs77); int Distance7; int Cost77; Map(C,R,11,7); short

12、path_DIJ(R,Cost,7,1,Distance); return 0;九、实验数据及结果分析：十、实验结论：该实验可实现对图的矩阵存储操作和用Dijkstra算法实现图的最短路径操作十一、总结及心得体会：通过本实验，我们学会了对图的存储操作和算出最短路径操作，熟悉了对程序的编译和调试操作。 报 告 评 分： 指导教师签字：电 子 科 技 大 学实 验 报 告学生姓名： 学 号： 指导教师：实验地点：主楼A2-412 实验时间：2011.11.25一、实验室名称： 二、实验项目名称：图书管理（检索，插入和删除） 三、实验学时：2学时四、实验原理：结构算法、二分法算法等查找算法，图的插入

13、、删除等算法五、实验目的：学会编写程序实现对图书的管理操作六、实验内容：创建一个图书管理系统（包括每本书的编号、书名、作者、分类信息），程序采用交互式工作方式，流程如下：1、 书籍管理：完成增加新书籍和删除功能，并在完成操作之后按关键字（编号、书名、作者、种类）进行排序（插入、冒泡、快速、堆排序、归并排序等任选一种）； 2、 书籍查找：用二分法实现下述功能l 按编号查找l 按书名查找l 按作者查找l 按分类查找七、实验器材（设备、元器件）：PC机一台，C语言编译环境八、实验步骤：#include#includetypedef struct Book int Number; char BookN

14、ame21; char Writer21; char Type21;Books;void Book_1(Books B,int m,int n) int i,j,t,t1,t2,T; int L1,L2,L3,L4,L5,L6,L7; int Num; char Name21,Wri21,Ty21; printf(增加新书籍n); for(i=0;im;i+) if(Bi.Number=0) scanf(%dt%st%st%sn,&Bi.Number,&Bi.BookName,&Bi.Writer,&Bi.Type); printf(删除书籍n); if(n=m) Bn.Number=0; f

15、or(i=0;i21;i+) Bn.BookNamei=0; Bn.Writeri=0; Bn.Typei=0; /* for(i=0;im;i+) printf(%dt%st%st%sn,Bi.Number,Bi.BookName21,Bi.Writer21,Bi.Type21); */ printf(按关键字排序n); for(i=0;im;i+) for(j=i+1;jm;j+) L1=strlen(Bj.BookName); L2=strlen(Bi.BookName); L3=strlen(Bj.Writer); L4=strlen(Bi.Writer); L5=strlen(Bj.

16、Type); L6=strlen(Bi.Type); if(Bj.NumberBi.Number&L1L2&L3L4&L5L6) Num=Bj.Number; Bj.Number=Bi.Number; Bi.Number=Num; for(t=0;t21;t+) Namet=Bj.BookNamet; Writ=Bj.Writert; Tyt=Bj.Typet; Bj.BookNamet=Bi.BookNamet; Bj.Writert=Bi.Writert; Bj.Typet=Bi.Typet; Bi.BookNamet=Namet; Bi.Writert=Writ; Bi.Typet=Ty

17、t; for(i=0;im;i+) printf(%dt%st%st%sn,Bi.Number,Bi.BookName21,Bi.Writer21,Bi.Type21); printf(按二分法查找n); Book s; scanf(%d%s%s%sn,&s.Number,&s.BookName,&s.Writer,&s.Type); while(Tm) t1=0; t2=m-1; T=(t1+t2)/2; L1=strlen(Bj.BookName); L2=strlen(Bi.BookName); L3=strlen(Bj.Writer); L4=strlen(Bi.Writer); L5

18、=strlen(Bj.Type); L6=strlen(Bi.Type); if(BT.Number=s.Number|BT.BookName=s.BookName|BT.Writer=s.Writer|BT.Type=s.Type) printf(%dt%st%st%sn,BT.Number,BT.BookName,BT.Writer,BT.Type); else if(BT.Numbers.Number|L1L2|L3L4|L5L6) t2=T; else t1=T; if(t1=t2) break; int main() Books B8; Book_1(B,8,4); return 0;九、实验数据及结果分析：十、实验结论：该实验程序可实现对图书的插入和删除操作，可实现用二分法来查找书籍。十一、总结及心得体会：通过本实验，我们学会了编写程序来实现对图书的管理工作，熟悉了对程序的编译和调试。 报 告 评 分： 指导教师签字：35