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

时间：2020-11-02 11:44:35 来源：蒲公英阅读网 本文已影响人

相关热词搜索：数据结构 算法 西安交通大学

　“数据结构与算法”课内实验设计

　A. “数据结构与算法”课内实验设计 （1）线性表及栈与队列操作实现

　题目：

　针对线性表或栈或队列（三者中任取一种逻辑结构），编程实现顺序或链式（两者中任选一种存储方式）存储结构下数据结构建立、元素插入、删除等基本操作。要求解释实现过程，演示实际例子及运行结果。

　算法描述：

　为使主函数简洁，创建五个函数模板，分别为头结点的建立，单链表的遍历，单链表的插入，单链表的删除以及求单链表的表长。创建单链表即先用(LinkList)malloc(sizeof(LNode))给头结点分配存储空间，再对头结点进行插入操作，形成单链表。单链表遍历采用 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>

　 // 编程实现顺序存储结构和链式存储结构线性表的建立、查找、插入、删除等基本操作 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("\n"); } bool InsertList(LinkList la,int i,int e) {

　int j=0;

　LinkList p=la,s;

　while(p && j<i)

　{

　 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 && j<i)

　//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") ;

　scanf("%d",&a) ;

　p=HeadCreate(&la);

　 printf("输入元素的值:\n");

　 for(i=0;i<a;i++)

　{scanf("%d",&m);

　InsertList(p,i,m);

　 }

　TravelList(p);

　printf("输入删除元素的位置：\n");

　scanf("%d",&i);

　 DeleteList(p,i);

　TravelList(p);

　printf("获得链表长度 %d\n",LengthList(p));

　 return 0; }

　实验结果：

　（2）二叉树与树的操作实现

　题目：

　编程实现二叉查找树的建立（如先序序列作为输入）、中序遍历、层序遍历、元素查找等功能，要求解释实现程序并演示实际例子中的运行结果。

　算法描述：

　对插入算法，由二叉查找树的定义，比较数据大小，数据小的做左孩子 ， 数 据 大 的 做 右 孩 子 ； 创 建 二 叉 查 找 树 时 ， 先 用

　(BiTree)malloc(sizeof(BiNode));分配存储空间给结点，该结点的左右孩子均为空值，即初始化。再对每个元素使用定义的插入算法。中序遍历即先遍历左子树，再遍历中间结点，最后遍历右子树。查找算法用while 循环不断与结点值比较大小，若比当前结点值小则到该结点的左子树结点继续比较，若比当前结点值大则到该结点的右子树结点继续比较，直到遇到和要求值相同为止。删除算法类似查找算法，查找成功后进行后继结点的变化，然后释放要删除的结点。

　源代码：

　#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(data<p->data)

　{

　parent=p;

　p=p->lchild;

　 }

　 else if(data>p->data)

　 { parent=p;

　p=p->rchild;

　 }

　 else

　return ;

　}

　s=(BiTree)malloc(sizeof(BiNode));

　s->data=data;

　s->lchild=s->rchild=NULL;

　if(s->data<parent->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;i<n;i++)

　{

　 scanf("%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(key<p->data)

　p=p->lchild;

　 else if(key>p->data)

　p=p->rchild;

　 else

　 {

　printf("数字%d 查找成功。\n",key);

　return 1;

　 }

　}

　printf("未找到数据%d。\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(key<p->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

　par->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;

　 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);

　 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）背包问题的求解 问题描述：

　假设有一个能装入总体积为 T 的背包和 n 件体积分别为 w1，w2，w3…，wn 的物品，能否从 n 件物品中挑选若干件恰好装满背包，即使 w1+w2+…wm=T,要求找出所以满足上述条件的解。进一步考虑：

　如果每件物品都有体积和价值，背包又有大小限制，求解背包中存放物品总价值。

　设计思想：

　利用回溯法来解决背包问题，将物品排成一列，顺序选取物品装入背包，若已选取第 i 件物品后未满，则继续选取第 i+1 件，若该物品体积不满足，则舍弃，继续选取下一件，直至背包装满。如果在剩余物品中找不到合适的物品填满背包，则说明之前装入的物品不合适，应该将其取出舍弃，从它之后的物品中选取，如此往复，直到求得满足条件的解，或者无解。

　算法分析：

　首先创建数组来存储待输入的各个物体的体积，通过结构体类型定义栈，把数组中的元素逐一入栈，若目前的体积比预定的体积小，则继续入栈，等于预定体积则输出，若输入元素后大于预定体积，说明该元素不是合适解，先舍弃；继续输入元素考察。当第一个元素做栈底完全满足就考虑下一个元素的情况，直至所有元素都做栈底，结束。

　源程序：

　#include<iostream> #include<stdio.h> #include<algorithm> #include<stack> #include<vector>using namespace std;#define maxx 1024int count1=0;

　typedef struct{

　int last;

　 int data[maxx]; }seqlist; typedef struct{

　int top;

　 int sum;

　 int data[maxx]; }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; }int push_seqstack(seqlist *l,int i,seqstack *s){

　 if(s->top==maxx-1)

　 return 0;

　 else{

　 s->top++;

　 s->data[s->top]=i; //顺序表中第 i 个元素，i 入栈

　s->sum=s->sum+l->data[i]; //栈中 sum 加和

　return 1;

　 } }int pop_seqstack(seqlist *l,seqstack *s,int *x){

　 if(empty_seqstack(s))

　 return 0;

　 else{

　 *x=s->data[s->top];

　 s->sum=s->sum-l->data[s->data[s->top]];

　 s->top--;

　 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->data[l->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(flag!=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->data[s->data[t]]);

　 }

　 printf("\n");

　 pop_seqstack(l,s,&i);

　 i++;

　 }

　 else{

　 if(s->sum>n){

　 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");

　 printf("-------------------------\n执行完毕");

　}

　 }

　 }

　 }

　 } } int main(){

　 int n;

　 seqlist *l;

　 printf("请输入背包体积 n 的大小，n=\n");

　 scanf("%d",&n);

　 l=init_seqlist();

　 knapsk(n,l);

　 return 1; }

　实验结果：

　 （2）农夫过河问题的求解 问题描述: 一个农夫带着一只狼、一只羊和一颗白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请给出农夫将所有的东西运过河的方案。

　设计思想：采取步步试探的方法，每一步搜索可能的选择，对前一步进行合适的选择后再选择下一步的各种方案。采取 4 位二进制的顺序分别表示农夫、狼、白菜和羊的位置。用 0 表示在南岸，1 表示在北

　岸。将问题转化为：从初始的状态二进制 0000 出发，寻找一种安全状态的状态序列，以二进制 1111 为最终目标。

　算法分析：

　该问题可以采用广度优先和深度优先，我考虑用深度优先搜索策略。实现深度优先搜索策略的前提是建立图或邻接表进行存储，我选择用邻接表存储，那么问题就转化成如何建立邻接表的节点并构建相邻节点。邻接表的每个元素表示一个可以安全到达的中间状态。

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

　源代码：

　#include <stdio.h> #include <stdlib.h> #define MAX_LEN 30

　typedef struct

　{

　 int farmer;

　int wolf;

　int sheep;

　int vegetable; }Vertexdata;

　int visited[MAX_LEN] = {0};

　//设置访问状态 int path[MAX_LEN] = {0};

　//保存 DFS 搜索到的路径，数组元素的值为数组编号的下一状态

　typedef struct

　//邻接矩阵 {

　 Vertexdata verlist[MAX_LEN];

　 int edges[MAX_LEN][MAX_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->verlist[i].wolf!=G->verlist[j].wolf)

　 flag ++;

　 if(G->verlist[i].sheep!=G->verlist[j].sheep)

　 flag ++;

　 if(G->verlist[i].vegetable!=G->verlist[j].vegetable)

　 flag ++;

　 if(G->verlist[i].farmer!=G->verlist[j].farmer&&flag<=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->verlist[i].farmer=f;

　 G->verlist[i].wolf=w;

　 G->verlist[i].sheep=s;

　 G->verlist[i].vegetable=v;

　 i++;

　 }

　 }

　 }

　 }

　 }

　 G->vertexnum = i ;

　 //安全的顶点个数

　 for(i=0;i<G->vertexnum;i++)

　 {

　 for(j=0;j<G->vertexnum;j++)

　 {

　 if(Cancross(G,i,j))

　 {

　 G->edges[i][j]=1;

　 //无向图

　G->edges[j][i]=1;

　 }

　 else

　 {

　 G->edges[i][j]=0;

　 G->edges[j][i]=0;

　 }

　 }

　 } }

　int Location(MTGraph *G,int f,int w,int s,int v) //查找某顶点在顶点表中的位置 {

　 int i;

　 for(i=0;i<G->vertexnum;i++)

　 {

　 if(G->verlist[i].farmer== f&&G->verlist[i].sheep==s \

　&&G->verlist[i].vegetable ==v &&G->verlist[i].wolf==w)

　 return i;

　 }

　 return -1; }

　void DFS(MTGraph *G, int start ,int end)

　{

　 int m=0;

　 visited[start]=1;

　 for(m=0;m<G->vertexnum;m++)

　 {

　if(G->edges[start][m] && !visited[m] && !visited[end]) //如果二者可转换且另一个顶点未被访问过,直到终点

　 {

　 path[start]=m;

　//此时 m 为 start 的下一种状态

　 DFS(G,m,end);

　 }

　 } }

　void Printpath(MTGraph G,int start,int end)

　{

　 int p=start;

　 while(p!=end)

　 {

　 printf(" 过 河 情 况 ：

　农 夫 %d 狼 %d 羊 %d 菜%d\n",G.verlist[p].farmer,G.verlist[p].wolf,\

　G.verlist[p].sheep,G.verlist[p].vegetable);

　 p = path[p];

　}

　 printf(" 过 河 情 况 ：

　农 夫 %d 狼 %d 羊 %d 菜%d\n",G.verlist[p].farmer,G.verlist[p].wolf,\

　G.verlist[p].sheep,G.verlist[p].vegetable); }

　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(visited[end])

　 Printpath(G,start,end);

　 return 0; } 实验结果：

　（3）八皇后问题 问题描述：

　设在初始状态下在国际象棋的棋盘上没有任何棋子（这里的棋子指皇后棋子）。然后顺序在第一行，第二行，…，第八行上布放棋子。在每一行中共有 8 个可选择的位置，但在任一时刻棋盘的合法布局都必须满足 3 个限制条件：1.任意两个棋子不得放在同一行； 2. 任意两个棋子不得放在同一列 3.任意棋子不得放在同一正斜线和反斜线上。

　设计思想：

　在第 i 行布放棋子时，从第一列到第八列逐列考察。当在第 i 行第 j列布放棋子时，需要考察布放棋子后在行方向、列方向、正斜线和反斜线方向上的布局状态是否合法，若该棋子布放合法，再递归求解在

　第 i+1 行布放棋子；若该棋子布放不合法，移去这个棋子，恢复布放该棋子前的状态，然后再试探在第 i 行第 j+1 列布放棋子. 算法分析：

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

　源代码：

　#include "stdio.h"

　#include "windows.h"

　#define N 8 int place(int k); void backtrack(int i); void chessboard();

　static int sum,

　x[N];

　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(x[j] - x[k]) || (x[j] == x[k])) return 0;

　return 1;

　}

　void backtrack(int t)

　{

　if (t == N) chessboard();

　else

　for (int i = 0; i < N; i ++) {

　x[t] = 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 == x[i]) printf("@ ");

　else printf("* ");

　printf("\n");

　}

　printf("\n");

　} 实验结果：

　 （4）约瑟夫环问题仿真 问题描述：

　设编号为 1,2，…，n 个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意一个报数上限 m，从第一个人开始顺时针方向自 1 起顺序报数，报到 m 时停止报数，报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人起重新自 1 报数；直到所有人全部出列为止。

　算法分析：

　建立一个带头结点的具有 n 个结点的约瑟夫问题循环链表。在循环链表中查找、密码为 m 的结点，将其输出，并取出该结点的密码赋值

　给 m，将该结点从约瑟夫环链表中删除，直到输出循环链表中所有元素为止。

　源代码：

　#ifndef LIST_H #define LIST_H typedef struct node {

　int xuhao;

　int password;

　struct node * next; }Node, *List; #endif #include<stdio.h> #include<stdlib.h> #include<stdbool.h> int main() {

　List head = (List)malloc(sizeof(Node));

　head->next = head;

　//用来保存上一个节点，即 previous 英文

　List prev = head;

　int numbers, firstPassword; //临时数字

　 int password; printf("输入总人数以及初始密码:m\n");

　 scanf("%d%d", &numbers, &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");

　 //当它还没有指向自己时，说明链表中还有数据存在

　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; }

　实验结果：