西安交通大学数据结构与算法1实验报告

《西安交通大学数据结构与算法1实验报告》由会员分享，可在线阅读，更多相关《西安交通大学数据结构与算法1实验报告（26页珍藏版）》请在装配图网上搜索。

1、本文格式为Word版，下载可任意编辑西安交通大学数据结构与算法1实验报告 数据结构与算法课内试验设计 A. 数据结构与算法课内试验设计 （1）线性表及栈与队列操作实现 题目： 针对线性表或栈或队列（三者中任取一种规律结构），编程实现挨次或链式（两者中任选一种存储方式）存储结构下数据结构建立、元素插入、删除等基本操作。要求解释实现过程，演示实际例子及运行结果。 算法描述： 为使主函数简洁，创建五个函数模板，分别为头结点的建立，单链表的遍历，单链表的插入，单链表的删除以及求单链表的表长。创建单链表即先用(LinkList)malloc(sizeof(LNode)给头结点安排存储空间，再对头结点进行

2、插入操作，形成单链表。单链表遍历采纳 while 循环，若 p 指针的值不为空，则输出其存储的值并指向下一个结点，直到 p指针为空。单链表插入先将 p 指向第 i 个结点，再创建 s 结点，s 结点存储的值为插入的值，s 结点的 next 指针指向原来 p 的 next 指针，再将 p 的 next 指针指向 s，完成插入操作。删除操作为将 p 指向第 i-1个元素，创建 q 指向 p 的 next，再将 p 指向第 i+1 个元素。然后释放q，完成删除操作。表长类似遍历操作，只是遍历是从零开头，表长 留意要加 1. 源代码：#include stdio.h #include stdlib.h

3、 / 编程实现挨次存储结构和链式存储结构线性表的建立、查找、插入、删除等基本操作 typedef struct LNode int data; struct LNode* next; LNode,*LinkList; LinkList HeadCreate(LinkList la) int num; la=(LinkList)malloc(sizeof(LNode); la-next=NULL; void TravelList(LinkList la) LinkList p=la-next; while(p!=NULL) printf(%d-,p-data); p=p-next; printf

4、(n); bool InsertList(LinkList la,int i,int e) int j=0; LinkList p=la,s; while(p ji) p=p-next; j+; if(p=NULL) return false; if(s=(LinkList)malloc(sizeof(LNode)=NULL) return false; s-data=e; s-next=p-next; p-next=s; return true; bool DeleteList(LinkList la,int i) int j=1; LinkList p=la,q; while(p ji)

5、/p 指向第 i-1 个元素 p=p-next; j+; if(p=NULL | p-next=NULL) /表示不存在第i-1个和第i的元素 return false; q=p-next; p-next=q-next; free(q); return true; int LengthList(LinkList la) int nLen=0; LinkList p=la-next; while(p) p=p-next; nLen+; return nLen; int main() int i,m,n,a; LNode la; LinkList p; printf(输入元素个数：n) ; sca

6、nf(%d,a) ; p=HeadCreate(la); printf(输入元素的值:n); for(i=0;ia;i+) scanf(%d,m); InsertList(p,i,m); TravelList(p); printf(输入删除元素的位置：n); scanf(%d,i); DeleteList(p,i); TravelList(p); printf(获得链表长度 %dn,LengthList(p); return 0; 试验结果： （2）二叉树与树的操作实现 题目： 编程实现二叉查找树的建立（如先序序列作为输入）、中序遍历、层序遍历、元素查找等功能，要求解释实现程序并演示实际例子中

7、的运行结果。 算法描述： 对插入算法，由二叉查找树的定义，比较数据大小，数据小的做左孩子 ， 数 据 大 的 做 右 孩 子 ； 创 建 二 叉 查 找 树 时 ， 先 用 (BiTree)malloc(sizeof(BiNode);安排存储空间给结点，该结点的左右孩子均为空值，即初始化。再对每个元素使用定义的插入算法。中序遍历即先遍历左子树，再遍历中间结点，最终遍历右子树。查找算法用while 循环不断与结点值比较大小，若比当前结点值小则到该结点的左子树结点连续比较，若比当前结点值大则到该结点的右子树结点连续比较，直到遇到和要求值相同为止。删除算法类似查找算法，查找胜利后进行后继结点的变化，

8、然后释放要删除的结点。 源代码： #include stdio.h / 编程实现二叉查找树的建立、中序遍历、元素查找 #include stdlib.h typedef struct tree struct tree *lchild,*rchild; int data; *BiTree,BiNode; void Insert(BiTree bt,int data) BiTree p,s,parent; p=bt; while(p) if(datap-data) parent=p; p=p-lchild; else if(datap-data) parent=p; p=p-rchild; els

9、e return ; s=(BiTree)malloc(sizeof(BiNode); s-data=data; s-lchild=s-rchild=NULL; if(s-dataparent-data) parent-lchild=s; else parent-rchild=s; void InitTree(BiTree bt,int n) /建立二叉排序树 int data,i; scanf(%d,data); bt=(BiTree)malloc(sizeof(BiNode); bt-data=data; bt-lchild=bt-rchild=NULL; for(i=1;in;i+) s

10、canf(%d,data); Insert(bt,data); void InOrder(BiTree bt) if(!bt) return ; InOrder(bt-lchild); printf(%d ,bt-data); InOrder(bt-rchild); int Search(BiTree bt,int key) BiTree p; p=bt; while(p) if(keyp-data) p=p-lchild; else if(keyp-data) p=p-rchild; else printf(数字%d 查找胜利。n,key); return 1; printf(未找到数据%d

11、。n,key); return 0; void Delete_BiTree(BiTree bt,int key) BiTree p,cur,par; p=bt; while(p) if(key=p-data) break; else if(keyp-data) par=p; p=p-lchild; else par=p; p=p-rchild; if(!p) printf(该数据不存在.n); return ; if(!p-lchild) /没有左子树 if(p=bt) bt=p-rchild; else if(par-lchild=p) par-lchild=p-rchild; else p

12、ar-rchild=p-rchild; free(p); else cur=p-lchild; par=cur; while(cur-rchild) par=cur; cur=cur-rchild; if(par=p-lchild) /p 的左孩子没有右子树 p-data=par-data; p-lchild=par-lchild; free(par); else /p 的左孩子有右子树 p-data=cur-data; par-rchild=cur-lchild; free(cur); printf(删除胜利.n); int main() BiTree bt; int n,key,selet

13、; while(1) printf( -n); printf( 1、建立二叉排序树n); printf( 2、输出中序遍历结果n); printf( 3、搜寻数据n); printf( 4、删除数据n); printf( 5、插入数据n); printf( 6、退出n); printf( -n); scanf(%d,selet); switch(selet) case 1: printf(输入数字的个数:); scanf(%d,n); printf(请输入每个数字:); InitTree(bt,n); break; case 2: printf(中序遍历结果为：); InOrder(bt);

14、putchar(n); break; case 3: printf(请输入查找的关键字：); scanf(%d,key); Search(bt,key); break; case 4: printf(请输入删除的关键字：); scanf(%d,key); Delete_BiTree(bt,key); break; case 5: printf(请输入要插入的数据：); scanf(%d,key); Insert(bt,key); printf(插入胜利.n); break; default: return 0; 试验结果： 数据结构与算法专题试验设计 （1）背包问题的求解 问题描述： 假设有一

15、个能装入总体积为 T 的背包和 n 件体积分别为 w1，w2，w3，wn 的物品，能否从 n 件物品中选择若干件恰好装满背包，即使 w1+w2+wm=T,要求找出所以满意上述条件的解。进一步考虑： 假如每件物品都有体积和价值，背包又有大小限制，求解背包中存放物品总价值。 设计思想： 利用回溯法来解决背包问题，将物品排成一列，挨次选取物品装入背包，若已选取第 i 件物品后未满，则连续选取第 i+1 件，若该物品体积不满意，则舍弃，连续选取下一件，直至背包装满。假如在剩余物品中找不到合适的物品填满背包，则说明之前装入的物品不合适，应当将其取出舍弃，从它之后的物品中选取，如此往复，直到求得满意条件的

16、解，或者无解。 算法分析： 首先创建数组来存储待输入的各个物体的体积，通过结构体类型定义栈，把数组中的元素逐一入栈，若目前的体积比预定的体积小，则连续入栈，等于预定体积则输出，若输入元素后大于预定体积，说明该元素不是合适解，先舍弃；连续输入元素考察。当第一个元素做栈底完全满意就考虑下一个元素的状况，直至全部元素都做栈底，结束。 源程序： #includeiostream #includestdio.h #includealgorithm #includestack #includevectorusing namespace std;#define maxx 1024int count1=0;

17、typedef struct int last; int datamaxx; seqlist; typedef struct int top; int sum; int datamaxx; seqstack; seqstack *init_seqstack() /栈初始化 seqstack *s; s=new seqstack; if(!s) printf(空间不足); return 0; else s-top=-1; s-sum=0; return s; int empty_seqstack(seqstack *s) if(s-top=-1) return 1; else return 0;

18、 int push_seqstack(seqlist *l,int i,seqstack *s) if(s-top=maxx-1) return 0; else s-top+; s-datas-top=i; /挨次表中第 i 个元素，i 入栈 s-sum=s-sum+l-datai; /栈中 sum 加和 return 1; int pop_seqstack(seqlist *l,seqstack *s,int *x) if(empty_seqstack(s) return 0; else *x=s-datas-top; s-sum=s-sum-l-datas-datas-top; s-top

19、-; return 1; seqlist *init_seqlist() seqlist *l; int x=1; l=new seqlist; l-last=0; printf(-n 请依次输入物品的大小，输入 0 结束n); scanf(%d,x); while(x!=0) l-datal-last=x; l-last+; scanf(%d,x); return l; void knapsk(int n,seqlist *l) /创建数组，存储物品体积 seqstack *s; int flag=1; int i=0; int t; s=init_seqstack(); while(fla

20、g!=0) while(i=l-last) push_seqstack(l,i,s); if(s-sum=n) printf(-n 可行的解有：); count1+; for(t=0;t=s-top;t+) printf(%d ,l-datas-datat); printf(n); pop_seqstack(l,s,i); i+; else if(s-sumn) pop_seqstack(l,s,i); i+; else i+; while(i=l-last+1) flag=pop_seqstack(l,s,i); i+; if(flag=0) if(count1=0) printf(无解n)

21、; printf(-n执行完毕); int main() int n; seqlist *l; printf(请输入背包体积 n 的大小，n=n); scanf(%d,n); l=init_seqlist(); knapsk(n,l); return 1; 试验结果： （2）农夫过河问题的求解 问题描述: 一个农夫带着一只狼、一只羊和一颗白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。假如农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请给

22、出农夫将全部的东西运过河的方案。 设计思想：实行步步摸索的方法，每一步搜寻可能的选择，对前一步进行合适的选择后再选择下一步的各种方案。实行 4 位二进制的挨次分别表示农夫、狼、白菜和羊的位置。用 0 表示在南岸，1 表示在北 岸。将问题转化为：从初始的状态二进制 0000 动身，查找一种平安状态的状态序列，以二进制 1111 为最终目标。 算法分析： 该问题可以采纳广度优先和深度优先，我考虑用深度优先搜寻策略。实现深度优先搜寻策略的前提是建立图或邻接表进行存储，我选择用邻接表存储，那么问题就转化成如何建立邻接表的节点并构建相邻节点。邻接表的每个元素表示一个可以平安到达的中间状态。 一开头建立结

23、点，f、w、s、c 分别代表农夫、狼、羊、白菜，最初状态均是 0。设 visited 数组对已访问的顶点进行标记，visited 的每个重量初始化值均为-1，每当在队列中加入一个新状态时，就把挨次表中以该状态作下标的元素的值改为达到这个状态的路径上前一状态的下标值。visited 的一个元素具有非负值表示这个状态已访问过，或是正被考虑。最终利用 visited 挨次表元素的值建立起正确的状态路径。isSafe 函数是确定状态的平安性的。危急状况为当农夫与羊不在一起时，狼与羊或羊与白菜在一起返回 0，否则返回 1。为避开重复，要求在序列中不消失重复的状态。用数组 retPath 保存 DFS 搜

24、寻到的路径，即与某顶点到下一顶点的路径。 源代码： #include stdio.h #include stdlib.h #define MAX_LEN 30 typedef struct int farmer; int wolf; int sheep; int vegetable; Vertexdata; int visitedMAX_LEN = 0; /设置访问状态 int pathMAX_LEN = 0; /保存 DFS 搜寻到的路径，数组元素的值为数组编号的下一状态 typedef struct /邻接矩阵 Vertexdata verlistMAX_LEN; int edgesMAX

25、_LENMAX_LEN; int vertexnum; MTGraph; int Safe(int f,int w,int s,int v) if(f!=s)(s=w|s=v) return 0; else return 1; int Cancross(MTGraph *G, int i, int j) /推断两种状态是否可切换 int flag=0; if(G-verlisti.wolf!=G-verlistj.wolf) flag +; if(G-verlisti.sheep!=G-verlistj.sheep) flag +; if(G-verlisti.vegetable!=G-ver

26、listj.vegetable) flag +; if(G-verlisti.farmer!=G-verlistj.farmerflag=1) return 1; else return 0; void Creategraph(MTGraph *G) /生成全部平安的图的顶点 int i=0,j=0,f,w,s,v; for(f=0;f=1;f+) for(w=0;w=1;w+) for(s=0;s=1;s+) for(v=0;v=1;v+) if(Safe(f,w,s,v) G-verlisti.farmer=f; G-verlisti.wolf=w; G-verlisti.sheep=s;

27、 G-verlisti.vegetable=v; i+; G-vertexnum = i ; /平安的顶点个数 for(i=0;iG-vertexnum;i+) for(j=0;jG-vertexnum;j+) if(Cancross(G,i,j) G-edgesij=1; /无向图 G-edgesji=1; else G-edgesij=0; G-edgesji=0; int Location(MTGraph *G,int f,int w,int s,int v) /查找某顶点在顶点表中的位置 int i; for(i=0;iG-vertexnum;i+) if(G-verlisti.far

28、mer= fG-verlisti.sheep=s G-verlisti.vegetable =v G-verlisti.wolf=w) return i; return -1; void DFS(MTGraph *G, int start ,int end) int m=0; visitedstart=1; for(m=0;mG-vertexnum;m+) if(G-edgesstartm !visitedm !visitedend) /假如二者可转换且另一个顶点未被访问过,直到终点 pathstart=m; /此时 m 为 start 的下一种状态 DFS(G,m,end); void Pr

29、intpath(MTGraph G,int start,int end) int p=start; while(p!=end) printf( 过 河 情 况 ： 农 夫 %d 狼 %d 羊 %d 菜%dn,G.verlistp.farmer,G.verlistp.wolf, G.verlistp.sheep,G.verlistp.vegetable); p = pathp; printf( 过 河 情 况 ： 农 夫 %d 狼 %d 羊 %d 菜%dn,G.verlistp.farmer,G.verlistp.wolf, G.verlistp.sheep,G.verlistp.vegetab

30、le); int main() int start,end; MTGraph G; Creategraph(G); start = Location(G,0,0,0,0); end = Location(G,1,1,1,1); printf(农夫过河问题具体步骤：(0 表示在河彼岸，1 表示在河对岸)n); DFS(G,start,end); if(visitedend) Printpath(G,start,end); return 0; 试验结果： （3）八皇后问题 问题描述： 设在初始状态下在国际象棋的棋盘上没有任何棋子（这里的棋子指皇后棋子）。然后挨次在第一行，其次行，第八行上布放棋子。

31、在每一行中共有 8 个可选择的位置，但在任一时刻棋盘的合法布局都必需满意 3 个限制条件：1.任意两个棋子不得放在同一行； 2. 任意两个棋子不得放在同一列 3.任意棋子不得放在同一正斜线和反斜线上。 设计思想： 在第 i 行布放棋子时，从第一列到第八列逐列考察。当在第 i 行第 j列布放棋子时，需要考察布放棋子后在行方向、列方向、正斜线和反斜线方向上的布局状态是否合法，若该棋子布放合法，再递归求解在 第 i+1 行布放棋子；若该棋子布放不合法，移去这个棋子，恢复布放该棋子前的状态，然后再摸索在第 i 行第 j+1 列布放棋子. 算法分析： 棋盘 8 行 8 列，用 define N 8 定义

32、棋盘大小，int place(int k);确定某一位置皇后放置与否，放置则返回 1，反之返回 0。定义 backtrack(int i)为递归函数，搜寻解空间中第 i 层子树。定义 chessboard()，每找到一个解,打印当前棋盘状态。用 xN; 记录皇后的位置,xi表示皇后 i放在棋盘的第 i 行的第 xi列，先放置一个皇后，再推断另一个皇后 k在第 k 行第 xk列时是否与前面已放置好的皇后相攻击。xj = xk 时，两皇后在同一列上；abs(k - j) = abs(xj - xk) 时，两皇后在同一斜线上。两种状况两皇后都可相互攻击，故返回 0 表示不符合条件。 源代码： #in

33、clude stdio.h #include windows.h #define N 8 int place(int k); void backtrack(int i); void chessboard(); static int sum, xN; int main(void) backtrack(0); system(pause); return 0; int place(int k) for (int j = 0; j k; j +) if (abs(k - j) = abs(xj - xk) | (xj = xk) return 0; return 1; void backtrack(i

34、nt t) if (t = N) chessboard(); else for (int i = 0; i N; i +) xt = i; if (place(t) backtrack(t + 1); void chessboard() printf(第%d 种解法:n, + sum); for (int i = 0; i N; i +) for (int j = 0; j N; j +) if (j = xi) printf( ); else printf(* ); printf(n); printf(n); 试验结果： （4）约瑟夫环问题仿真 问题描述： 设编号为 1,2，n 个人按顺时针

35、方向围坐一圈，每人持有一个正整数密码。开头时任意一个报数上限 m，从第一个人开头顺时针方向自 1 起挨次报数，报到 m 时停止报数，报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人起重新自 1 报数；直到全部人全部出列为止。 算法分析： 建立一个带头结点的具有 n 个结点的约瑟夫问题循环链表。在循环链表中查找、密码为 m 的结点，将其输出，并取出该结点的密码赋值 给 m，将该结点从约瑟夫环链表中删除，直到输出循环链表中全部元素为止。 源代码： #ifndef LIST_H #define LIST_H typedef struct node int xuhao; in

36、t password; struct node * next; Node, *List; #endif #includestdio.h #includestdlib.h #includestdbool.h int main() List head = (List)malloc(sizeof(Node); head-next = head; /用来保存上一个节点，即 previous 英文 List prev = head; int numbers, firstPassword; /临时数字 int password; printf(输入总人数以及初始密码:mn); scanf(%d%d, nu

37、mbers, firstPassword); printf(输入各个人所持有的密码：n); for (int i = 1; i = numbers; i+) scanf(%d, password); /申请一个新节点 List pnew = (List)malloc(sizeof(Node); prev-next = pnew; /赋值 pnew-xuhao = i; pnew-password = password; pnew-next = head; prev = pnew; List p = head-next; prev = head; printf(输出出队是第几个人:n); /当它

38、还没有指向自己时，说明链表中还有数据存在 while (head-next != head) if (firstPassword != 0) password = firstPassword; firstPassword = 0; /依据 password 找到要删除的节点 for (int i = 0; i password - 1; i+) if (p-next = head) p = p-next; prev = prev-next; p = p-next; prev = prev-next; if (p-next = head) List t = p; password = p-next-password; printf(%d , p-xuhao); prev-next = head; prev = head; p = head-next; free(t); /假如目标的下一个节点不是 head，那么直接输出+删除 else password = p-password; printf(%d , p-xuhao); prev-next = p-next; List t = p; p = p-next; free(t); printf(n); return 0; 试验结果： 第 26 页 共 26 页