数据结构上机作业_数据结构上机作业答案
数据结构上机作业由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构上机作业答案”。
实验一 线性表
一、实验题
线性表的应用———多项式计算
二、程序设计思路
包括每个函数的功能说明，及一些重要函数的算法实现思路一链式存储：
1.void InitPoly(LNode *&p)初始化多项式 2.void TraversePoly(LNode *&p)遍历多项式 3.void ClearPoly(LNode *&p)清除多项式
4.void InsertPoly(LNode *&p, double a, int e)插入一项 5.void DeletetPoly(LNode *&p,int pos)
删除一项
6.double PolySum(LNode *&p, double x)
多项式求值 7.LNode * PolyAdd(LNode *&p1,LNode *& p2)
多项式相加 顺序存储：
1.void InitPoly1(SeqList &L)初始化多项式 2.void ClearPoly1(SeqList &L)清除多项式 3.void TraversePoly1(SeqList L)
遍历多项式
4.bool InsertPoly1(SeqList &L, ElemType item)插入一项 5.double PolySum1(SeqList L,double x)
多项式求值 6.bool DeleteList1(SeqList &L,int pos)
删除一项
7.SeqList PolyAdd1(SeqList &L1,SeqList& L2)
多项式相加
三、源程序代码
#include #include #include #include “Linkpoly.h” #include “Seqpoly.h” void main(){ cout>n;cout>a;cin>>e;InsertPoly(pa, a, e);//插入一项 pa=pa->next;} pa=pa->next;cout>a;cin>>e;cin>>pos;if(DeletetPoly(pa, a, e, pos)){ cout>x;sum=PolySum(pa, x);cout>n;cout>a;cin>>e;InsertPoly(pb, a, e);//插入一项 pb=pb->next;} pb=pb->next;pp=PolyAdd(pa, pb);cout>n;cout>a;cin>>e;InsertPoly1(s, a, e);} cout>a;cin>>e;cin>>pos;if(DeletetPoly1(s, a, e, pos)){ cout>x;sum=PolySum1(s, x);cout>n;cout>a;cin>>e;InsertPoly1(t, a, e);//插入一项 } q=PolyAdd1(s, t);coutnext=p;return true;} void TraversePoly(NodeType *p)//输出多项式 { NodeType *h=p->next;if(h!=p){ coutcoefexp;h=h->next;} while(h!=p){ if(h->coef>0)coutcoefexp;h=h->next;} } void ClearPoly(NodeType *&p)//清除多项式 { NodeType *cp,*np;cp=p->next;while(cp!=p){ np=cp->next;delete cp;cp=np;} p->next=p;} bool InsertPoly(NodeType *&p, float a, int e)//插入一项 { NodeType *h;if((h=new NodeType)==NULL)return false;h->coef=a;h->exp=e;h->next=p->next;p->next=h;return true;} bool DeletetPoly(NodeType *&p, float a, int e, int pos)//一项
{ if(pos>1||posnext;NodeType *np=p;if(pos==0){ while(cp!=p){ if(cp->coef==a&&cp->exp==e)break;else{ np=cp;cp=cp->next;} } } else if(pos==-1)while(cp!=p){
删除np=cp;cp=cp->next;} np->next=cp->next;delete cp;return true;} double PolySum(NodeType *p, float x)//多项式求值 { int i;double sum=0,item;NodeType *cp=p->next;while(cp!=p){ item=1;for(i=1;iexp;i++)item=item*x;sum=sum+item*cp->coef;cp=cp->next;} return sum;} NodeType *PolyAdd(NodeType *p1, NodeType *p2)//多项式相加 { float coef;NodeType *a=p1->next,*b=p2->next,*c,*pc;InitPoly(c);pc=c;while(a!=p1&&b!=p2){ if(a->exp==b->exp){ coef=a->coef+b->coef;if(coef!=0){ InsertPoly(pc, coef, a->exp);pc=pc->next;} a=a->next;b=b->next;} else if(a->expexp){ InsertPoly(pc,a->coef,a->exp);pc=pc->next;a=a->next;} else{ InsertPoly(pc,b->coef,b->exp);pc=pc->next;b=b->next;} } while(a!=p1){ InsertPoly(pc,a->coef,a->exp);pc=pc->next;a=a->next;} while(b!=p2){ InsertPoly(pc,b->coef,b->exp);pc=pc->next;b=b->next;} return c;} Seqploy.h: #define MaxSize 10000 struct ListType{ float *list;int size;};void InitPoly1(ListType &p)//初始化多项式 { p.list=(float*)malloc(MaxSize*sizeof(float));if(p.list==NULL){ cout0){ cout
输出多项式 } void ClearPoly1(ListType &p)//清除多项式 { if(p.list!=NULL){ delete []p.list;p.list=NULL;} p.size=0;} void InsertPoly1(ListType &p, float a, int e)//项
{ p.list[e]=a;if(p.size
{ int i,n;if(p.size==0){ cout
插入一if(p.list[e]==a)p.list[e]=0;else if(pos==-1)p.list[p.size]=0;return true;} double PolySum1(ListType p, float x)//值
{ double sum=0,item;int i,j;for(i=0;i
{ ListType p;InitPoly1(p);float coef;
多项式求多int i,j;for(i=0;i
五.心得体会 对于结构体的认识增加了，对于动态存储也有了更多的认识，也是在不知不觉中提高了。
实验二 字符串的操作
一、实验题目——字符串的操作
二、程序设计思路
采用定长顺序存储表示，由用户创建串s和串t，实现在串s中下标为pos的字符之前插入串t。
三、源程序代码
#define MAXLEN 10 typedef struct {
/*串结构定义*/
char ch[MAXLEN];
int len;}SString;void createstring(SString *s)
/*创建串s*/ { int i,j;char c;printf(“input the length of the string:”);
scanf(“%d”,&j);
for(i=0;i
{
printf(“input the %d:”,i+1);
fflush(stdin);
scanf(“%c”,&c);
s->ch[i] = c;
} s->len = j;} void output(SString *s)
/*输出串s*/ {
int i;for(i=0;ilen;i++)
printf(“%c
”,s->ch[i]);
printf(“n”);} int StrInsert(SString *s, int pos, SString *t)/*在串s中下标为pos的字符之前插入串t */ {
int i;if(poss->len)
/*插入位置不合法*/
return(0);
if(s->len + t->len
/*插入后串长≤MAXLEN*/ {
for(i=s->len + t->len-1;i>=t->len + pos;i--)
s->ch[i]=s->ch[i-t->len];/*将下标为pos的字符后的元素往后移动t->len个长度*/
for(i=0;ilen;i++)
s->ch[i+pos]=t->ch[i];
/*将串t从下标为pos位置开始插入到串s*/
s->len=s->len+t->len;} else { if(pos+t->lenMAXLEN,但串t的字符序列可以全部插入*/
{
for(i=MAXLEN-1;i>t->len+pos-1;i--)
s->ch[i]=s->ch[i-t->len];
for(i=0;ilen;i++)
s->ch[i+pos]=t->ch[i];
/*将串t从下标为pos位置开始插入到串s*/
s->len=MAXLEN;
}
else
/*插入后串长>MAXLEN,并且串t的部分字符也要舍弃*/
{
for(i=0;i
s->ch[i+pos]=t->ch[i];
/*直接从下标为pos的位置按顺序插入串t*/
s->len=MAXLEN;
}
return(1);} } void main(){
SString *str1;SString *str2;int i,j,k,pos;int flag=0;str1 =(SString *)malloc(sizeof(SString));str1->len = 0;printf(“creat the string 1:n”);createstring(str1);printf(“creat the string 2:n”);createstring(str2);printf(“input the insert local:”);scanf(“%d”,&pos);flag=StrInsert(str1,pos,str2);if(flag == 0)
printf(“insert error!”);else {
printf(“after insert:n”);
output(str1);} }
四、实验结果
五、实验体会
通过本次实验，我加深了对串数据结构的理解。在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。在存储方式中，结点大小的选择和顺序存储方式的格式选择一样都很重要，它直接影响着串处理的效率。
实验三
一、实验题目——非递归算法对二叉树进行中前序遍历
二、程序设计思路
创建一棵10个节点构造的完全二叉树，并对其进行前、中、后序遍历。
三、源程序代码
#define STUDENT EType #define SType SType
#define HeadEType int
#include #include
//定义数据结构类型
struct STUDENT { char name[8];int age;char number[15];char addre[20];};
struct BinaryTreeNode { EType data;BinaryTreeNode *LChild;BinaryTreeNode *RChild;};typedef BinaryTreeNode BinaryTree;
typedef struct { BinaryTreeNode *ptr;bool status;}SType;
typedef struct { SType *element;int top;int MaxSize;}Stack;
void CreatStack(Stack &S, int MaxStackSize){// 构造一个最大容量为MaxStackSize 的堆栈
S.MaxSize = MaxStackSize;
S.element = new SType[S.MaxSize];
S.top =-1;}
bool IsEmpty(Stack &S){// 判断堆栈S是否为空
if(S.top ==-1)
return true;
return false;}
bool IsFull(Stack &S){// 判断堆栈S是否为空
if(S.top == MaxSize-1)
return true;
return false;}
bool Push(Stack &S , SType &x){// x进s栈，返回进栈后的状态值
if(IsFull(S))
return false;
S.top++;
S.element[S.top] = x;
return true;}
bool Pop(Stack &S , SType &x){// 将s栈顶的值取至x中，返回出栈后的状态值
if(IsEmpty(S))
return false;
x = S.element[S.top];
S.top--;
return true;}
BinaryTreeNode
*MakeNode(EType &x)
{//构造结点
BinaryTreeNode *ptr;
ptr = new BinaryTreeNode;
if(!ptr)return NULL;
ptr->data = x;
ptr-> LChild = NULL;
ptr-> RChild = NULL;
return
ptr;}
void MakeBinaryTree(BinaryTreeNode *root, BinaryTreeNode *left, BinaryTreeNode *right){// 联接root，left, right所指的结点指针为二叉树
root->LChild=left;
root->RChild=right;}
void PreOrderNoRecursive(BinaryTreeNode *BT){//二叉树前序遍历非递归的算法
Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假设堆的空间足够大，即MaxStackSize值足够大
CreatStack(S,MaxStackSize);//产生一个空栈
while(q||!IsEmpty(S)){
if(q)
{
coutdata.name
ele.ptr=q;
Push(S,ele);//节点指针进栈，以后回溯时在退栈
q=q->LChild;//指针指向刚刚被访问的“根”节点的左子树
}
else
//当左子树为空时，利用堆栈回溯
if(!IsEmpty(S))
{
Pop(S,ele);//退栈回溯
q=ele.ptr;//指针重新指向刚刚被访问的“根”节点
q=q->RChild;//指针指向该回溯节点的右子树
} } }
void InOrderNoRecursive(BinaryTreeNode *BT){//二叉树的中序遍历非递归的算法
Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假设堆的空间足够大，即MaxStackSize值足够大
CreatStack(S,MaxStackSize);//产生一个空栈
while(q ||!IsEmpty(S)){
while(q)//找到最左边的子树
{
ele.ptr=q;
Push(S,ele);//指针非空时，将当前的“根”节点指针进栈，用于以后回溯
q=q->LChild;//指针继续指向该“根”节点的左子树
}
if(!IsEmpty(S))//当左子树为空时，进行退栈回溯
{
Pop(S,ele);//从堆栈中回溯节点指针（节点还未访问）
q=ele.ptr;
coutdata.name
q=q->RChild;//指针向回溯的节点右子树推进
} } }
void PostOrderNoRecursive(BinaryTreeNode *BT){//二叉树的后序遍历非递归的算法
Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假设堆的空间足够大，即MaxStackSize值足够大
CreatStack(S,MaxStackSize);//产生一个空栈
while(q ||!IsEmpty(S)){
if(q)//找最左边的子树
{
ele.ptr=q;
ele.status=false;//进栈前标记为第一次进栈
Push(S,ele);
q=q->LChild;//指针继续向左推进
}
else
if(!IsEmpty(S))//直到左子树为空时，退栈回溯
{
Pop(S,ele);//从堆栈中弹出回溯节点（还未访问）
q=ele.ptr;//q指向当前回溯节点
if(ele.status)//判断节点进栈标志，是否对其进行访问
{
coutdata.name
q=NULL;//将q设为空，为了继续退栈
}
else
{
ele.status=true;//改变回溯节点的进栈标记，以便再次进栈
Push(S,ele);
q=q->RChild;//指针向该回溯节点的右孩子推进
}
} } }
//主函数 void main(){ BinaryTreeNode *ptr[11];
char Name[][8]={“ ”,“A”,“B”,“C”,“D”,“E”,“F”,“G”,“H”,“I”,“J”};EType x[11];for(int i=1;i
strcpy(x[11-i].name,Name[11-i]);
ptr[11-i]=MakeNode(x[11-i]);//构造10个二叉树节点
}
//将节点链接域填值，构造一个二叉树
//这里构造的是一棵有10个节点的完全二叉树
for(int j=1;j
MakeBinaryTree(ptr[j],ptr[2*j],ptr[2*j+1]);} MakeBinaryTree(ptr[5],ptr[10],NULL);//该完全二叉树构造完毕
//***********对已构造的完全二叉树进行前序非递归遍历************// cout
//***********对已构造的完全二叉树进行中序非递归遍历************// cout
//***********对已构造的完全二叉树进行中序非递归遍历************// cout
四、实验结果分析
五、实验总结
二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。
实验四
一、实验题目——深度优先算法实现图的遍历
二、程序设计思路
以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先，并输出遍历的结点序列。首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先，并输出遍历的结果。
三、源程序代码
#include #define MaxVerNum 50 struct edgenode { int endver;int inform;edgenode* edgenext;
};struct vexnode
{ char vertex;edgenode* edgelink;};struct Graph
{ vexnode adjlists[MaxVerNum];int vexnum;int arcnum;};//队列的定义及相关函数的实现 struct QueueNode { int nData;QueueNode* next;};struct QueueList { QueueNode* front;QueueNode* rear;};void EnQueue(QueueList* Q,int e){ QueueNode *q=new QueueNode;q->nData=e;q->next=NULL;if(Q==NULL)
return;if(Q->rear==NULL)
Q->front=Q->rear=q;else {
Q->rear->next=q;
Q->rear=Q->rear->next;} } void DeQueue(QueueList* Q,int* e){ if(Q==NULL)
return;if(Q->front==Q->rear){
*e=Q->front->nData;
Q->front=Q->rear=NULL;} else {
*e=Q->front->nData;
Q->front=Q->front->next;} } //创建图
void CreatAdjList(Graph* G){ int i,j,k;edgenode* p1;edgenode* p2;cout>G->vexnum>>G->arcnum;coutvexnum;i++){
cin>>G->adjlists[i].vertex;
G->adjlists[i].edgelink=NULL;} coutarcnum;k++){
cout对应的顶点:“;
cin>>i>>j;
p1=new edgenode;
p1->endver=j;
p1->edgenext=G->adjlists[i].edgelink;
G->adjlists[i].edgelink=p1;
p2=new edgenode;
p2->endver=i;
p2->edgenext=G->adjlists[j].edgelink;
G->adjlists[j].edgelink=p2;
//因为是无向图，所以有两次建立边表的过程
} }
//------------------------------深度优先遍历 void DFS(Graph *G,int i,int visit[]){ coutadjlists[i].vertexadjlists[i].edgelink;if(G->adjlists[i].edgelink&&!visit[p->endver]){
DFS(G,p->endver,visit);} } void DFStraversal(Graph *G,char c)//深度优先遍历 { coutvexnum;i++){
visit[i]=0;//全部初始化为0，即未访问状态
} int m;for(i=0;ivexnum;i++){
if(G->adjlists[i].vertex==c)//根据字符查找序号
{
m=i;
DFS(G,i,visit);
break;
} } //继续访问未被访问的结点
for(i=0;ivexnum;i++){
if(visit[i]==0)
DFS(G,i,visit);} coutfront=Q->rear=NULL;EnQueue(Q,v);while(Q->rear!=NULL){
int e=0;
DeQueue(Q,&e);
coutadjlists[e].vertex
visit[e]=1;
edgenode* p=new edgenode;
p=G->adjlists[e].edgelink;
if(p)
{
int m=p->endver;
if(m==0)
{
EnQueue(Q,m);
while(visit[m]==0)
{
p=p->edgenext;
if(p==NULL)
break;
m=p->endver;
EnQueue(Q,m);
}
}
}
} } void BFStraversal(Graph *G,char c){ coutvexnum;i++){
visited[i]=0;} int m;for(i=0;ivexnum;i++){
if(G->adjlists[i].vertex==c)
{
m=i;
BFS(G,i,visited);
break;
} } //继续访问未被访问的结点
for(i=0;ivexnum;i++){
if(visited[i]==0)
BFS(G,i,visited);} cout>ch;DFStraversal(G,ch);BFStraversal(G,ch);}
四、实验结果及分析
五、实验总结
本次试验采用的是邻接表的方式实现图的深度优先遍历和。对于深度优先遍历，主要是采用递归的方式。试验本身问题不是太大，但要注意输入的问题，什么时候用空格，什么时候用回车，这一点是需要注意的，因为一旦数据的输入有问题，结果当然也就不可能正确了。只有正确的输入数据，建立图，才能得出正确的遍历结果。
