实验报告 2.doc

第一次作业第一题#include#define N 10int main()int aN,i,t;printf(请输入线性表n:);for(i=0;iN;i+)scanf(%d,&ai);printf(逆转前的线性表为：n);for(i=0;iN;i+)printf(%dt,ai);for(i=0;iN/2;i+)t=ai;ai=aN-i-1;aN-i-1=t;printf(逆转后的线性表为：n);for(i=0;iN;i+)printf(%dt,ai);printf(n);return 0; 第一次作业第二题#include#includetypedef struct nodeint data;struct node *next;node,*linklist;linklist crelist();void sqinsert(linklist head,int j,int i);void sqdelete(linklist head,int i);void sqprint(linklist head);int sqlength(linklist head);int main()linklist head;int x,t,j,i,z;j=-1,t=1;printf(建立单链表：n); head=crelist();printf(建立的单链表为：);sqprint(head);printf(请选择操作：n1、插入n2、删除n3、求长度n0、退出n);while(t)printf(请选择操作n);scanf(%d,&j);switch(j)case 1:printf(请选择插入位置：n);scanf(%d,&i);printf(请输入插入的数据n);scanf(%d,&x);sqinsert(head,x,i);break;case 2:printf(请输入删除元素位置n);scanf(%d,&i);sqdelete(head,i);sqprint(head);break;case 3:z=sqlength(head);printf(此链表的长度为%dn,z);break;case 0:t=0;break;return 0;linklist crelist()linklist head,r,s;int x,flag=1;head=(linklist )malloc(sizeof(node);head-next=NULL;r=head;printf(请输入数据建立链表，以-1结束n);while(flag)scanf(%d,&x);if(x!=-1)s=(linklist )malloc(sizeof(node);s-data=x;r-next=s;r=s;elseflag=0;r-next=NULL;return head;void sqinsert(linklist head,int x,int i)linklist p,s;int k;p=head;k=0;while(p!=NULL&knext;k+;if(p=NULL|ki-1)printf(插入位置不合理n);s=(linklist )malloc(sizeof(node);s-data=x;s-next=p-next;p-next=s;sqprint(head);void sqdelete(linklist head,int i)linklist p,q;int j,e;p=head;j=0;while(p-next!=NULL&jnext;j+;if(p-next=NULL|ji-1)printf(删除位置不合理n);q=p-next;p-next=q-next;e=q-data;free(q);void sqprint(linklist head)linklist p;p=head-next;while(p)printf(%dt,p-data);p=p-next;printf(n);int sqlength(linklist head)linklist p,b;int n=0;b=head-next;p=b;while(p!=NULL)n+;p=p-next;return n; 第二次作业第一题#include#include#define maxsize 20typedef structint *base;int *top;int stacksize;sqstack;int initstack(sqstack &S);int enstack(sqstack &S);int delstack(sqstack &S);void tip();int main()int j,a,b,k=0,i=0,c,d;int x50,y50;sqstack S;initstack(S);tip();scanf(%d,&j);while(j)switch(j)case 1:a=enstack(S); if(!a)printf(栈已满且分配存储空间失败n);printf(进栈数为%dn,a);xk+=a;printf(操作完成n);tip(); scanf(%d,&j);break;case 2:b=delstack(S);if(!b)printf(栈为空n);printf(出栈数为%dn,b);yi+=b;printf(操作完成n);tip(); scanf(%d,&j);break;case 0:j=0;break;default :printf(输入有误，请重新输入n);tip();scanf(%d,&j);break;printf(进栈数的顺序为：n);for(c=0;ck;c+)printf(%d,xc);printf(出栈数的顺序为：n);for(d=0;di;d+)printf(%d,yd);return 0;int initstack(sqstack &S)S.base=(int *)malloc(maxsize*sizeof(int);if(S.base=NULL)return 0;S.top=S.base;S.stacksize=maxsize;return 1;int enstack(sqstack &S)int e,length=10;if(S.top-S.base=S.stacksize*sizeof(int)S.base=(int *)realloc(S.base,(S.stacksize+length)*sizeof(int);if(S.base=NULL)return 0;S.stacksize=S.stacksize+length;S.top=S.base+S.stacksize*sizeof(int);printf(请输入入栈数字：n);scanf(%d,&e);*S.top+=e;return e;int delstack(sqstack &S)int e;if(S.top=S.base)return 0;e=*-S.top;return e;void tip()printf(请输入操作：1、进栈n2、出栈n0、退出n); 第二次作业第二题#include#include#define maxsize 20typedef structint *base;int front;int rear;sqqueue;int initqueue(sqqueue &Q);int enqueue(sqqueue &Q);int delqueue(sqqueue &Q);void tip();int main()int j,a,b,k=0,i=0,c,d;int x50,y50;sqqueue Q;initqueue(Q);tip();scanf(%d,&j);while(j)switch(j)case 1:a=enqueue(Q); if(!a)printf(队列已满n);printf(进队数为%dn,a);xk+=a;printf(操作完成n);tip(); scanf(%d,&j);break;case 2:b=delqueue(Q);if(!b)printf(队列为空n);printf(出队数为%dn,b);yi+=b;printf(操作完成n);tip(); scanf(%d,&j);break;case 0:j=0;break;default :printf(输入有误，请重新输入n);tip();scanf(%d,&j);break;printf(进队数的顺序为：n);for(c=0;ck;c+)printf(%d,xc);printf(出队数的顺序为：n);for(d=0;di;d+)printf(%d,yd);return 0;int initqueue(sqqueue &Q)Q.base=(int *)malloc(maxsize*sizeof(int);if(!Q.base)return 0;Q.front=Q.rear=0;return 1;int initqueue(sqqueue &Q)Q.base=(int *)malloc(maxsize*sizeof(int);if(!Q.base)return 0;Q.front=Q.rear=0;return 1;int enqueue(sqqueue &Q)int e;if(Q.rear+1)%maxsize=Q.front)return 0;printf(请输入入队数字：n);scanf(%d,&e);Q.baseQ.rear=e;Q.rear=(Q.rear+1)%maxsize;return e;int delqueue(sqqueue &Q)int e;if(Q.front=Q.rear)return 0;e=Q.baseQ.front;Q.front=(Q.front+1)%maxsize;return e;void tip()printf(请输入操作：n1、进队n2、出队n0、退出n); 第三次作业#include#include#includetypedef structchar ch100;int length;seqstrin;seqstrin Substr(seqstrin s,int i,int j);seqstrin Instr(seqstrin s,int i,char s1);seqstrin Delstr(seqstrin s,int i,int j);int strIndex(seqstrin s,char t);void tip();int main()int j,p;seqstrin s,str1,str2,str3;char s1=xyz;char t=hijk;strcpy(s.ch,abcdefghijklmn);s.length=strlen(s.ch); tip();scanf(%d,&j);while(j)switch(j)case 1:str1=Substr(s,2,10);if(!(strcmp(str1.ch,s.ch)printf(位置不合理n);puts(str1.ch);tip();scanf(%d,&j);break;case 2:str2=Instr(s,9,s1);if(!(strcmp(str2.ch,s.ch)printf(位置不合理n);puts(str2.ch);tip();scanf(%d,&j);break;case 3:str3=Delstr(s,2,5);if(!(strcmp(str3.ch,s.ch)printf(位置不合理n);puts(str3.ch);tip(); scanf(%d,&j);break;case 4:p=strIndex(s,t);if(p=0)printf(长度太长或在s中找不到字符串tn);printf(t在s中出现的位置为第%d个字符处n,p);tip(); scanf(%d,&j);break;case 0:j=0;break;default :printf(输入错误，请重新输入n);tip(); scanf(%d,&j);break;return 0;seqstrin Substr(seqstrin s,int i,int j)seqstrin str;int k,h=0;str.length=0;if(is.length|js.length)return s;for(k=i-1;ki+j-1;k+)str.chh+=s.chk;str.chh=0;str.length=j;return str;seqstrin Instr(seqstrin s,int i,char s1)seqstrin str,*p;int k,l,j,c,t;p=&s;l=strlen(s1);if(is.length+1)return s;if(l)if(l+s.length=100)if(p=(seqstrin *)realloc(p,(s.length+l)*sizeof(char)=NULL)return s;for(k=s.length-1;k=i-1;k-)str.chk+l=s.chk;for(j=i-1,c=0;j=i+l-1,c=l-1;j+,c+)str.chj=s1c;for(t=0;ti-1;t+)str.cht=s.cht;str.length+=l;str.chs.length+l=0;return str;seqstrin Delstr(seqstrin s,int i,int j)seqstrin str;int k;if(is.length|i+js.length)return s;for(k=0;k=i-1;k+)str.chk=s.chk;for(k=i+j-1;ks.length;k+)str.chk-j=s.chk;str.length=s.length-j+1;str.chs.length-j=0;return str;int strIndex(seqstrin s,char t)seqstrin str;int j,k,n,m,y;n=s.length;m=strlen(t);str.length=m;if(m=n)for(j=0;j=n-m+1;j+)for(k=0;km;k+)str.chk=s.chj+k;str.chk+1=0;if(strcmp(str.ch,t)!=0)continue;elsereturn (j+1);return 0;void tip()printf(请输入操作：n1、求子串n2、插入串n3、串删除n4、子串定位n0、退出n);第四次作业#include#include#define MAXSIZE 100typedef structint i,j;int e;Triple;typedef structTriple dataMAXSIZE+1;int mu,nu,tu;TSMatrix;TSMatrix InitArray(TSMatrix T);TSMatrix Transpose(TSMatrix M,TSMatrix T1);int main()int i,j;TSMatrix M,T,T1,T2;T1=M=InitArray(T);printf(你输入的矩阵为：n);for(i=1;i=M.tu;i+)printf(%dn%dn%dn,M.datai.i,M.datai.j,M.datai.e);T2=Transpose(M,T1);printf(转置后的矩阵为：n);for(j=1;j=M.tu;j+)printf(%dn%dn%dn,M.dataj.i,M.dataj.j,M.dataj.e);return 0;TSMatrix InitArray(TSMatrix T)int i;&T=(TSMatrix *)malloc(sizeof(TSMatrix);printf(请输入此矩阵的行数、列数及非零元素个数:n);scanf(%d%d%d,T.mu,T.nu,T.tu);printf(请输入相关数据完成此矩阵:n);for(i=0;iT.tu;i+)printf(请输入此矩阵非零元素的行下标和列下标n);scanf(%d%d,T.datai.i,T.datai.j);printf(请输入此矩阵非零元素的值n);scanf(%d,T.datai.e);&T=(TSMatrix *)malloc(sizeof(TSMatrix);return T;TSMatrix Transpose(TSMatrix M,TSMatrix T1)int col,t,p,q;int num100,cpot100;T1.mu=M.mu,T1.nu=M.nu,T1.tu=M.tu;if(T1.tu)for(col=1;col=M.tu;+col)numcol=0;for(t=1;t=M.tu;+t)+numM.datat.j;cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;+p)col=M.datap.j;q=cpotcol;T1.dataq.i=M.datap.j;T1.dataq.j=M.datap.i;T1.dataq.e=M.datap.e;+cpotcol;return T1; 第五次作业#include#include#includetypedef struct nodechar data;struct node *lChild;struct node *rChild;BTnode,*BTtree;BTtree Creat_BT(BTtree T);void preorder(BTtree T1);void Inorder(BTtree T1);void Postorder(BTtree T1);int Leaf_Sum(BTtree T1);void tip();int main()BTtree T,T1;BTnode b;int t,j,z;t=1;T=&b;printf(建立二叉树：n); T1=Creat_BT(T);while(t)scanf(%d,&j);switch(j)case 1:preorder(T1);tip();break;case 2:Inorder(T1);tip();break;case 3: Postorder(T1);tip();break;case 4:z=Leaf_Sum(T1);printf(此二叉树的长度为:%dn,z);tip();break;case 0:t=0;break;default :printf(你输入的数据有误，请重新输入:n);tip();break;return 0;BTtree Creat_BT(BTtree T)char ch;ch=getchar();if(ch=#)T=NULL;elseif(!(T=(BTnode *)malloc(sizeof(BTnode)printf(error:n);T-data=ch;T-lChild=Creat_BT(T-lChild);T-rChild=Creat_BT(T-rChild);return T;void Preorder(BTtree T1)if(T1)printf(%cn,T1-data);Preorder(T1-lChild);Preorder(T1-rChild);void Inorder(BTtree T1)if(T1)Inorder(T1-lChild);printf(%cn,T1-data);Inorder(T1-rChild);void Postorder(BTtree T1)if(T1)Postorder(T1-lChild);Postorder(T1-rChild);printf(%cn,T1-data);int Leaf_Sum(BTtree T1)if(!T1)return 0;else if(T1-lChild=NULL&T1-rChild=NULL)return 1;else return Leaf_Sum(T1-lChild)+Leaf_Sum(T1-rChild);void tip()printf(1、先序遍历n2、中序遍历n3、后序遍历n4、叶子节点个数n0、退出n请输入操作：); 第六次作业#include#include#define INFINITY 32767#define MAX_VEX 20 #define QUEUE_SIZE (MAX_VEX+1) bool *visited;typedef structchar *base;int front;int rear;Queue;typedef structchar *vexs;int arcsMAX_VEXMAX_VEX;int vexnum,arcnum; Graph; void CreateUDN(Graph &G);void DFS(Graph G,int k);void BFS(Graph G);int Locate(Graph G,char c);int FirstVex(Graph G,int k);int NextVex(Graph G,int i,int j);void InitQueue(Queue Q);void EnQueue(Queue Q,int e);void DeQueue(Queue Q,int &e);void tip();int main()int j;Graph G;CreateUDN(G);tip();scanf(%d,&j);while(j)switch(j)case 1:printf(n深度优先遍历: );BFS(G);printf(操作完成n);tip(); scanf(%d,&j);break;case 2:printf(n广度优先遍历: ); DFS(G,-1);printf(操作完成n);tip(); scanf(%d,&j);break;case 0:j=0;break;default :printf(输入有误，请重新输入n);tip();scanf(%d,&j);break;printf(n程序结束.n);return 0;void CreateUDN(Graph &G)int i,j,w,s1,s2;char a,b,temp;printf(输入顶点数和弧数:);scanf(%d%d,&G.vexnum,&G.arcnum);temp=getchar();G.vexs=(char *)malloc(G.vexnum*sizeof(char);printf(输入%d个顶点.n,G.vexnum);for(i=0;iG.vexnum;i+) printf(输入顶点%d:,i);scanf(%c,&G.vexsi);temp=getchar(); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+)G.arcsij=INFINITY;printf(输入%d条弧.n,G.arcnum);for(j=0;jG.arcnum;j+) printf(输入弧%d:,j);scanf(%c %c %d,&a,&b,&w);temp=getchar();s1=Locate(G,a);s2=Locate(G,b);G.arcss1s2=G.arcss2s1=w;void DFS(Graph G,int k)int i;if(k=-1) for(i=0;i=0;i=NextVex(G,k,i)if(!G.vexsi) DFS(G,i); void BFS(Graph G)int k;Queue Q;InitQueue(Q);for(int i=0;i=0;w=NextVex(G,k,w)if(!visitedw)visitedw=true;printf(%c ,G.vexsw);EnQueue(Q,w);int Locate(Graph G,char c)for(int i=0;i=0&kG.vexnum) for(int i=0;i=0 & i=0 & jG.vexnum) for(int k=j+1;kG.vexnum;k+)if(G.arcsik!=INFINITY) return k;return -1;void InitQueue(Queue Q)Q.base=(char *)malloc(QUEUE_SIZE*sizeof(char);Q.front=Q.rear=0;void EnQueue(Queue Q,int e)Q.baseQ.rear=e;Q.rear=(Q.rear+1)%QUEUE_SIZE;void DeQueue(Queue Q,int &e)e=Q.baseQ.front;Q.front=(Q.front+1)%QUEUE_SIZE;void tip()printf(请输入操作：1、深度优先遍历n2、广度优先遍历n0、退出n); 第七次作业第一题#include#include#define MAXSIZE 100#define lth 10typedef structint dataMAXSIZE;int length;SStable;SStable createSS(SStable S);int Search_Bin(SStable T,int t);int main()SStable S,T;int j,t,k;S.length=0;S.data0=0;printf(请按要求创建顺序查找表：n);T=createSS(S);if(T.length=0)printf(创建顺序查找表失败：n);elseprintf(你建立的顺序表为：n);for(k=1;k=T.length;k+)printf(%dt,T.datak);printf(n);printf(请输入你要查找的数字:n);scanf(%d,&t);j=Search_Bin(T,t);if(!j)printf(你输入的数据不在顺序查找表中n);elseprintf(你要查找的数据在第%d个位置:n,j);return 0;SStable createSS(SStable S)SStable *p;p=&S;int i;printf(请输入你要创建的顺序查找表的长度：n);scanf(%d,&S.length);while(S.length=MAXSIZE)p=(SStable *)realloc(p,(MAXSIZE+lth)*sizeof(int);if(!p)S.length=0;return S;printf(请依次输入顺序查找表中的数据（注意大小及顺序）：n);for(i=1;i1)if(S.dataiS.datai-1)printf(输入顺序不对，请重新输入：n);i=i-1;return S;int Search_Bin(SStable T,int t)int low,high,mid;low=1;high=T.length;while(lowt)high=mid-1;else low=mid+1;return 0;第七次作业第二题#include#includetypedef struct nodeint data;struct node *lChild;struct node *rChild;BTnode,*BTtree;BTtree Creat_BT(BTtree T);int ser(BTtree T1,int a);void inorder(BTtree r);int main()BTtree T,T1;BTnode b;int t,i,k;t=1;T=&b;printf(建立二叉树：n); T1=Creat_BT(T);printf(输出二叉排序树：n);inorder(T1);printf(输入需要查找的数字:n);scanf(%d,&i);k=ser(T1,i);if (k) printf(已找到n); else printf(未找到n);return 0;BTtree Creat_BT(BTtree T)int ch;scanf(%d,&ch);if(ch=0)T=NULL;elseif(!(T=(BTnode *)malloc(sizeof(BTno