数据结构上机作业

1、 实验一 线性表1、 实验题 线性表的应用多项式计算2、 程序设计思路包括每个函数的功能说明，及一些重要函数的算法实现思路一链式存储：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(LN

2、ode *&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) 多项式求值

3、6.bool DeleteList1(SeqList &L,int pos) 删除一项7.SeqList PolyAdd1(SeqList &L1,SeqList& L2) 多项式相加 三、源程序代码#include <stdio.h>#include <iostream.h>#include <stdlib.h>#include "Linkpoly.h"#include "Seqpoly.h"void main()cout<<"现在进行第一次测试。（链表表示）"

4、<<endl;double sum;int i,e,n,pos;float a,x;NodeType *pa,*pb,*pp;InitPoly(pa); /初始化多项式InitPoly(pb);cout<<"请输入要测试的项数:"cin>>n;cout<<"请依次输入要测试的各项的系数和指数:"for(i=0;i<n;i+)cin>>a;cin>>e;InsertPoly(pa, a, e); /插入一项pa=pa->next;pa=pa->next;cout<

5、;<"该多项式为:"TraversePoly(pa); /输出多项式cout<<endl;cout<<"现在进行删除测试，请输入要删除的项的系数和指数以及pos值:"cin>>a;cin>>e;cin>>pos;if(DeletetPoly(pa, a, e, pos)cout<<"删除成功！现在多项式为:"TraversePoly(pa);cout<<endl;elsecout<<"删除失败！"<<e

6、ndl;cout<<"请输入X的值，进行多项式计算:"cin>>x;sum=PolySum(pa, x);cout<<"该多项式的值为:"<<sum<<endl;cout<<"请输入另一个多项式的项数:"cin>>n;cout<<"请输入该多项式的各项系数和指数:"for(i=0;i<n;i+)cin>>a;cin>>e;InsertPoly(pb, a, e); /插入一项pb=pb-&g

7、t;next;pb=pb->next;pp=PolyAdd(pa, pb);cout<<"两多项式相加后得到的多项式为:"TraversePoly(pp);cout<<endl;ClearPoly(pa);ClearPoly(pb);ClearPoly(pp);cout<<endl;cout<<endl;cout<<"现在进行第二次测试。（顺序表表示）"<<endl;ListType s,t,q;InitPoly1(s);InitPoly1(t);InitPoly1(q);co

8、ut<<"请输入要测试的项数:"cin>>n;cout<<"请依次输入要测试的各项的系数和指数:"for(i=0;i<n;i+)cin>>a;cin>>e;InsertPoly1(s, a, e);cout<<"该多项式为:"TraversePoly1(s);cout<<endl;cout<<"现在进行删除测试，请输入要删除的项的系数和指数以及pos值:"cin>>a;cin>>e;cin&

9、gt;>pos;if(DeletetPoly1(s, a, e, pos)cout<<"删除成功！现在多项式为:"TraversePoly1(s);cout<<endl;elsecout<<"删除失败！"<<endl;cout<<"请输入X的值，进行多项式计算:"cin>>x;sum=PolySum1(s, x);cout<<"该多项式的值为:"<<sum<<endl;cout<<"

10、;请输入另一个多项式的项数:"cin>>n;cout<<"请输入该多项式的各项系数和指数:"for(i=0;i<n;i+)cin>>a;cin>>e;InsertPoly1(t, a, e); /插入一项q=PolyAdd1(s, t);cout<<"两多项式相加后得到的多项式为:"TraversePoly1(q);cout<<endl;ClearPoly1(s);ClearPoly1(t);ClearPoly1(q);Linkploy.h:struct NodeTy

11、pefloat coef;int exp;NodeType *next;bool InitPoly(NodeType *&p) /初始化多项式if(p=new NodeType)=NULL)return false;p->next=p;return true;void TraversePoly(NodeType *p) /输出多项式NodeType *h=p->next;if(h!=p)cout<<h->coef<<"*"<<"X"<<""<<h-&

12、gt;exp;h=h->next;while(h!=p)if(h->coef>0)cout<<"+"cout<<h->coef<<"*"<<"X"<<""<<h->exp;h=h->next;void ClearPoly(NodeType *&p) /清除多项式NodeType *cp,*np;cp=p->next;while(cp!=p)np=cp->next;delete cp;cp=

13、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|pos<-1)return false;NodeType

14、 *cp=p->next;NodeType *np=p;if(pos=0)while(cp!=p)if(cp->coef=a&&cp->exp=e)break;elsenp=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-&

15、gt;next;while(cp!=p)item=1;for(i=1;i<=cp->exp;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

16、->coef+b->coef;if(coef!=0)InsertPoly(pc, coef, a->exp);pc=pc->next;a=a->next;b=b->next;else if(a->exp<b->exp)InsertPoly(pc,a->coef,a->exp);pc=pc->next;a=a->next;elseInsertPoly(pc,b->coef,b->exp);pc=pc->next;b=b->next;while(a!=p1)InsertPoly(pc,a->

17、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 10000struct ListTypefloat *list;int size;void InitPoly1(ListType &p) /初始化多项式p.list=(float*)malloc(MaxSize*sizeof(float);if(p.list=NULL)cout&l

18、t;<"动态可分配的储存空间用完，退出运行！"<<endl;exit(1);p.size=0;for(int i=0;i<MaxSize;i+)p.listi=0;void TraversePoly1(ListType p) /输出多项式int i=0;if(p.listi!=0)cout<<p.listi<<"*"<<"X"<<""<<i;elsefor(i=1;i<MaxSize;i+)if(p.listi!=0)brea

19、k;cout<<p.listi<<"*"<<"X"<<""<<i;for(i=i+1;i<MaxSize;i+)if(p.listi>0)cout<<"+"cout<<p.listi<<"*"<<"X"<<""<<i;if(p.listi<0)cout<<p.listi<<"

20、*"<<"X"<<""<<i;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.liste=a;if(p.size<e)p.size=e;bool DeletetPoly1(ListType &p, float a, int e, int pos) /删除

21、一项int i,n;if(p.size=0)cout<<"多项式为空,删除无效!"<<endl;return false;if(pos=0)if(p.liste=a)p.liste=0;else if(pos=-1)p.listp.size=0;return true;double PolySum1(ListType p, float x) /多项式求值double sum=0,item;int i,j;for(i=0;i<=p.size;i+)item=1;for(j=1;j<=i;j+)item=item*x;sum=sum+item

22、*p.listi;return sum;ListType PolyAdd1(ListType p1, ListType p2) /多项式相加ListType p;InitPoly1(p);float coef;int i,j;for(i=0;i<=p1.size;i+)coef=p1.listi+p2.listi;InsertPoly1(p, coef, i);if(i<=p1.size)for(j=i;j<=p1.size;j+)InsertPoly1(p, p1.listj, j);if(i<=p2.size)for(j=i;j<=p2.size;j+)Ins

23、ertPoly1(p, p2.listj, j);return p;四实验结果分析5. 心得体会 对于结构体的认识增加了，对于动态存储也有了更多的认识，也是在不知不觉中提高了。实验二 字符串的操作1、 实验题目字符串的操作2、 程序设计思路 采用定长顺序存储表示，由用户创建串s和串t，实现在串s中下标为pos的字符之前插入串t。3、 源程序代码#define MAXLEN 10typedef struct /*串结构定义*/ char chMAXLEN; int len;SString;void createstring(SString *s) /*创建串s*/int i,j;char c;p

24、rintf("input the length of the string:"); scanf("%d",&j); for(i=0; i<j; i+) printf("input the %d:",i+1); fflush(stdin);scanf("%c",&c); s->chi = c; s->len = j;void output(SString *s) /*输出串s*/ int i;for (i=0;i<s->len;i+)printf("%c &qu

25、ot;,s->chi); printf("n");int StrInsert(SString *s, int pos, SString *t) /*在串s中下标为pos的字符之前插入串t */ int i;if (pos<0 | pos>s->len) /*插入位置不合法*/return(0); if (s->len + t->len<=MAXLEN) /*插入后串长MAXLEN*/for (i=s->len + t->len-1;i>=t->len + pos;i-)s->chi=s->chi-

26、t->len; /*将下标为pos的字符后的元素往后移动t->len个长度*/for (i=0;i<t->len;i+) s->chi+pos=t->chi; /*将串t从下标为pos位置开始插入到串s*/s->len=s->len+t->len;else if (pos+t->len<=MAXLEN) /*插入后串长>MAXLEN,但串t的字符序列可以全部插入*/for (i=MAXLEN-1;i>t->len+pos-1;i-)s->chi=s->chi-t->len;for (i=0;i

27、<t->len;i+)s->chi+pos=t->chi; /*将串t从下标为pos位置开始插入到串s*/s->len=MAXLEN;else /*插入后串长>MAXLEN,并且串t的部分字符也要舍弃*/ for (i=0;i<MAXLEN-pos;i+)s->chi+pos=t->chi; /*直接从下标为pos的位置按顺序插入串t*/s->len=MAXLEN;return(1);void main() SString *str1;SString *str2;int i,j,k,pos;int flag=0;str1 = (SSt

28、ring *)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("ins

29、ert error!");elseprintf("after insert:n");output(str1); 4、 实验结果5、 实验体会 通过本次实验，我加深了对串数据结构的理解。在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。在存储方式中，结点大小的选择和顺序存储方式的格式选择一样都很重要，它直接影响着串处理的效率。 实验三1、 实验题目非递归算法对二叉树进行中前序遍历2、 程序设计思路 创建一棵10个节点构造的完全二叉树，并对其进行前、中、后序遍历。3、 源程序代码 #define STUDENT EType#def

30、ine SType SType#define HeadEType int#include <iostream.h>#include <string.h>/定义数据结构类型struct STUDENTchar name8;int age;char number15;char address20;struct BinaryTreeNodeEType data;BinaryTreeNode *LChild;BinaryTreeNode *RChild;typedef BinaryTreeNode BinaryTree;typedef structBinaryTreeNode

31、*ptr;bool status;SType;typedef structSType *element;int top;int MaxSize;Stack;void CreatStack(Stack &S, int MaxStackSize)/ 构造一个最大容量为MaxStackSize 的堆栈S.MaxSize = MaxStackSize;S.element = new STypeS.MaxSize;S.top =-1;bool IsEmpty(Stack &S)/ 判断堆栈S是否为空if (S.top = -1) return true;return false;bool

32、 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.elementS.top = x;return true;bool Pop(Stack &S , SType &x)/ 将s栈顶的值取至x中，返回出栈后的状态值if (IsEmpty(S) return false;x = S.elementS

33、.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)/ 联接

34、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)cout<<q->data.na

35、me<<" "/访问“根”节点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

36、 *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;cout<<q->data.

37、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

38、=false;/进栈前标记为第一次进栈Push(S,ele);q=q->LChild;/指针继续向左推进elseif(!IsEmpty(S)/直到左子树为空时，退栈回溯Pop(S,ele);/从堆栈中弹出回溯节点（还未访问）q=ele.ptr;/q指向当前回溯节点if(ele.status)/判断节点进栈标志，是否对其进行访问cout<<q-><<" "/访问回溯节点q=NULL;/将q设为空，为了继续退栈elseele.status=true;/改变回溯节点的进栈标记，以便再次进栈Push(S,ele);q=q->

39、;RChild;/指针向该回溯节点的右孩子推进/主函数void main()BinaryTreeNode *ptr11; char Name8=" ","A","B","C","D","E","F","G","H","I","J"EType x11;for(int i=1;i<11;i+)strcpy(,Name11-i);ptr11-i=MakeNo

40、de(x11-i);/构造10个二叉树节点/将节点链接域填值，构造一个二叉树/这里构造的是一棵有10个节点的完全二叉树for(int j=1;j<5;j+)MakeBinaryTree(ptrj,ptr2*j,ptr2*j+1);MakeBinaryTree(ptr5,ptr10,NULL);/该完全二叉树构造完毕/*对已构造的完全二叉树进行前序非递归遍历*/cout<<"对该二叉树进行前序遍历结果："<<endl;PreOrderNoRecursive(ptr1);cout<<endl;/*对已构造的完全二叉树进行中序非递归遍历*

41、/cout<<endl;cout<<"对该二叉树进行中序遍历结果："<<endl;InOrderNoRecursive(ptr1);cout<<endl;/*对已构造的完全二叉树进行中序非递归遍历*/cout<<endl;cout<<"对该二叉树进行后序遍历结果："<<endl;PostOrderNoRecursive(ptr1);cout<<endl<<endl;4、 实验结果分析5、 实验总结 二叉树是一种非常重要的数据结构，很多其它数据结构都

42、是基于二叉树的基础演变而来的。对于二叉树，有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。 实验四1、 实验题目深度优先算法实现图的遍历2、 程序设计思路 以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先，并输出遍历的结点序列。首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先，并输出遍历的结果。

43、3、 源程序代码 #include<iostream.h>#define MaxVerNum 50 struct edgenodeint endver;int inform;edgenode* edgenext; ;struct vexnode char vertex;edgenode* edgelink;struct Graph vexnode adjlistsMaxVerNum;int vexnum;int arcnum;/队列的定义及相关函数的实现struct QueueNodeint nData;QueueNode* next;struct QueueList QueueN

44、ode* 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;elseQ->rear->next=q;Q->rear=Q->rear->next;void DeQueue(QueueList* Q,int* e)if (Q=NULL)return;if (Q->front

45、=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<<"请输入顶点数和边数:"<<endl;cin>>G->vexnum>>G->arcnum;cout<<&qu

46、ot;开始输入顶点表:"<<endl;for (i=0;i<G->vexnum;i+)cin>>G->adjlistsi.vertex;G->adjlistsi.edgelink=NULL;cout<<"开始输入边表信息:"<<endl;for (k=0;k<G->arcnum;k+)cout<<"请输入边<Vi,Vj>对应的顶点:"cin>>i>>j;p1=new edgenode;p1->endver=j;p1->edgenext=G->adjlistsi.edgelink;G->adjlistsi.edgelink=p1;p2=new edgenode;p2->endver=i;p2->edgenext=G->adjlistsj.edgelink;G->adjlistsj.edgelink=p2;/因为是无向图，所以有两次建立边表的过程/-深度优先遍历void DFS(Graph *G,int i,int visit)cout<<G->ad