没有合适的资源?快使用搜索试试~ 我知道了~
数据结构c语言版实验及源代码.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
5星 · 超过95%的资源 3 下载量 27 浏览量
2021-09-30
21:14:28
上传
评论 15
收藏 135KB PDF 举报
温馨提示
试读
22页
数据结构c语言版实验及源代码.pdf
资源详情
资源评论
资源推荐
实验 1 求两个多项式的相加运算(线性表)
编写一个程序用单链表存储多项式,并实现两个多项式相加的函数。
/* 文件名 :实验 1.cpp*/
#include <stdio.h>
#include <malloc.h>
#define MAX 20 /* 多项式最多项数 */
typedef struct /* 定义存放多项式的数组类型 */
{
float coef; /* 系数 */
int exp; /* 指数 */
} PolyArray[MAX];
typedef struct pnode /* 定义单链表结点类型 */
{
float coef; /* 系数 */
int exp; /* 指数 */
struct pnode *next;
} PolyNode;
void DispPoly(PolyNode *L) /* 输出多项式 */
{
PolyNode *p=L->next;
while (p!=NULL)
{
printf("%gX^%d ",p->coef,p->exp);
p=p->next;
}
printf("");
}
void CreateListR(PolyNode *&L,PolyArray a,int n) /* 尾插法建表 */
{
PolyNode *s,*r;int i;
L=(PolyNode *)malloc(sizeof(PolyNode)); /* 创建头结点 */
L->next=NULL;
r=L; /*r 始终指向终端结点 ,开始时指向头结点 */
for (i=0;i<n;i++)
{
s=(PolyNode *)malloc(sizeof(PolyNode));/* 创建新结点 */
s->coef=a[i].coef;
s->exp=a[i].exp;
r->next=s; /* 将*s 插入 *r 之后 */
r=s;
}
r->next=NULL; /* 终端结点 next 域置为 NULL*/
}
void Sort(PolyNode *&head) /* 按 exp 域递减排序 */
{
PolyNode *p=head->next,*q,*r;
if (p!=NULL) /* 若原单链表中有一个或以上的数据结点 */
{
r=p->next; /*r 保存 *p 结点后继结点的指针 */
p->next=NULL; /* 构造只含一个数据结点的有序表 */
p=r;
while (p!=NULL)
{
r=p->next; /*r 保存 *p 结点后继结点的指针 */
q=head;
while (q->next!=NULL && q->next->exp>p->exp)
q=q->next; /* 在有序表中找插入 *p 的前驱结点 *q*/
p->next=q->next; /* 将*p 插入到 *q 之后 */
q->next=p;
p=r;
}
}
}
void Add(PolyNode *ha,PolyNode *hb,PolyNode *&hc) /*求两有序集合的并 */
{
PolyNode *pa=ha->next,*pb=hb->next,*s,*tc;
float c;
hc=(PolyNode *)malloc(sizeof(PolyNode)); /*创建头结点 */
tc=hc;
while (pa!=NULL && pb!=NULL)
{
if (pa->exp>pb->exp)
{
s=(PolyNode *)malloc(sizeof(PolyNode)); /* 复制结点 */
s->exp=pa->exp;s->coef=pa->coef;
tc->next=s;tc=s;
pa=pa->next;
}
else if (pa->exp<pb->exp)
{
s=(PolyNode *)malloc(sizeof(PolyNode)); /* 复制结点 */
s->exp=pb->exp;s->coef=pb->coef;
tc->next=s;tc=s;
pb=pb->next;
}
else /*pa->exp=pb->exp*/
{
c=pa->coef+pb->coef;
if (c!=0) /* 系数之和不为 0 时创建新结点 */
{
s=(PolyNode *)malloc(sizeof(PolyNode)); /* 复制结点 */
s->exp=pa->exp;s->coef=c;
tc->next=s;tc=s;
}
pa=pa->next;
pb=pb->next;
}
}
if (pb!=NULL) pa=pb; /* 复制余下的结点 */
while (pa!=NULL)
{
s=(PolyNode *)malloc(sizeof(PolyNode)); /*复制结点 */
s->exp=pa->exp;s->coef=pa->coef;
tc->next=s;tc=s;
pa=pa->next;
}
tc->next=NULL;
}
void main()
{
PolyNode *ha,*hb,*hc;
PolyArray a={{1.2,0},{2.5,1},{3.2,3},{-2.5,5}};
PolyArray b={{-1.2,0},{2.5,1},{3.2,3},{2.5,5},{5.4,10}};
CreateListR(ha,a,4);
CreateListR(hb,b,5);
printf(" 原多项式 A: ");DispPoly(ha);
printf(" 原多项式 B: ");DispPoly(hb);
Sort(ha);
Sort(hb);
printf(" 有序多项式 A: ");DispPoly(ha);
printf(" 有序多项式 B: ");DispPoly(hb);
Add(ha,hb,hc);
printf(" 多项式相加 : ");DispPoly(hc);
}
实验 2 求解迷宫问题的所有路径
及最短路径程序(堆栈)
改进教材中 3.2.4 节中的求解迷宫问题程序,要求输出如图所示的迷宫的所有路径,并求出
最短路径成都及最短路径。
/* 文件名 :实验 2.cpp*/
#include <stdio.h>
#define M 6 /* 行数 */
#define N 6 /* 列数 */
#define MaxSize 100 /* 栈最多元素个数 */
int mg[M+1][N+1]={ /* 一个迷宫 ,其四周要加上均为 1 的外框 */
{1,1,1,1,1,1},
{1,0,0,0,1,1},
{1,0,1,0,0,1},
{1,0,0,0,1,1},
0 1 2 3 4
0
1
2
3
4
5
5
入口
出口
{1,1,0,0,0,1},
{1,1,1,1,1,1}
};
struct
{
int i;int j;int di;
} Stack[MaxSize],Path[MaxSize]; /* 定义栈和存放最短路径的数组 */
int top=-1; /* 栈指针 */
int count=1; /* 路径数计数 */
int minlen=MaxSize; /* 最短路径长度 */
void mgpath() /* 路径为 :(1,1)->(M-2,N-2)*/
{
int i,j,di,find,k;
top++; /* 进栈 */
Stack[top].i=1;
Stack[top].j=1;
Stack[top].di=-1;mg[1][1]=-1; /* 初始结点进栈 */
while (top>-1) /* 栈不空时循环 */
{
i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;
if (i==M-2 && j==N-2) /* 找到了出口 ,输出路径 */
{
printf("%4d: ",count++);
for (k=0;k<=top;k++)
{
printf("(%d,%d) ",Stack[k].i,Stack[k].j);
if ((k+1)%5==0) printf("\n\t"); /* 输出时每 5 个结点换一行 */
}
printf("\n");
if (top+1<minlen) /*比较找最短路径 */
{
for (k=0;k<=top;k++)
Path[k]=Stack[k];
minlen=top+1;
}
mg[Stack[top].i][Stack[top].j]=0; /* 让该位置变为其他路径可走结点 */
top--;
i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;
}
find=0;
while (di<4 && find==0) /* 找下一个可走结点 */
{ di++;
switch(di)
{
剩余21页未读,继续阅读
资料大全
- 粉丝: 14
- 资源: 26万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论13