线性表、栈和队列、串.doc

本科生实验报告（一）姓名:学院:计算机科学学院专业:信息管理与信息系统班级:信息管理与信息系统班实验课程名称:数据结构实验日期:2011年9月 日指导教师及职称: 实验成绩:开课时间：2011-2012学年 第一 学期实验题目线性表、栈和队列、串小组合作否姓名班级信管班学 号一、实验目的了解线性表、栈和队列、串的存储结构,实现线性表、栈和队列、串的各种基本运算。二实验环境Visual C+ 6.0三、实验内容与步骤1、 实现表一表二的自然连接。主要代码：void CreateTable(HList *&h)int i,j;DList *r,*s;h=(HList *)malloc(sizeof(HList);h-next=NULL;printf(表的行数,列数:);scanf(%d%d,&h-Row,&h-Col);for (i=0;iRow;i+)printf( 第%d行:,i+1);s=(DList *)malloc(sizeof(DList);for (j=0;jCol;j+)scanf(%d,&s-dataj);if (h-next=NULL)h-next=s;elser-next=s;r=s;r-next=NULL;void DispTable(HList *h)int j;DList *p=h-next;while (p!=NULL)for (j=0;jCol;j+)printf(%4d,p-dataj);printf(n);p=p-next;void LinkTable(HList *h1,HList *h2,HList *&h)int f1,f2,i;DList *p=h1-next,*q,*s,*r;printf(连接字段是:第1个表位序,第2个表位序:);scanf(%d%d,&f1,&f2);h=(HList *)malloc(sizeof(HList);h-Row=0;h-Col=h1-Col+h2-Col;h-next=NULL;while (p!=NULL)q=h2-next;while (q!=NULL)if (p-dataf1-1=q-dataf2-1)s=(DList *)malloc(sizeof(DList);for (i=0;iCol;i+)s-datai=p-datai;for (i=0;iCol;i+)s-datah1-Col+i=q-datai;if (h-next=NULL)h-next=s;elser-next=s;r=s;h-Row+;q=q-next;p=p-next;r-next=NULL;void main()HList *h1,*h2,*h;printf(表1:n);CreateTable(h1);printf(表2:n); CreateTable(h2);LinkTable(h1,h2,h);printf(连接结果表:n);DispTable(h);运行结果如下：图一2、 迷宫问题。主要代码：struct int i,j;int pre; QuMaxSize;int front=-1,rear=-1;void print(int front)int k=front,j,ns=0;printf(n);doj=k;k=Quk.pre;Quj.pre=-1; while (k!=0);printf(迷宫路径如下:n);k=0;while (kMaxSize)if (Quk.pre=-1)ns+;printf(t(%d,%d),Quk.i,Quk.j);if (ns%5=0) printf(n);k+;printf(n);int mgpath(int xi,int yi,int xe,int ye)int i,j,find=0,di;rear+;Qurear.i=xi;Qurear.j=yi;Qurear.pre=-1;mg11=-1;while (front=rear & !find)front+;i=Qufront.i;j=Qufront.j;if (i=xe & j=ye)find=1;print(front);return(1);for (di=0;di4;di+)switch(di)case 0:i=Qufront.i-1;j=Qufront.j;break;case 1:i=Qufront.i;j=Qufront.j+1;break;case 2:i=Qufront.i+1;j=Qufront.j;break;case 3:i=Qufront.i,j=Qufront.j-1;break;if (mgij=0)rear+;Qurear.i=i;Qurear.j=j;Qurear.pre=front; mgij=-1; return(0);运行结果如下：图二3、串：寻找主串中与主串匹配的字串的位置主要代码：int index(SqString s,SqString t)int i=0,j=0;while (is.len & j=t.len) return(i-t.len); else return(-1); void main()SqString s,t;StrAssign(s,ababcabcacbab);StrAssign(t,abcac);printf(s:);DispStr(s);printf(t:);DispStr(t);printf(位置:%dn,index(s,t);实验结果：图三四、实验过程与分析(1) 理解线性表的逻辑结构特性。(2) 深入掌握线性表的两种存储方法,即顺序表和链表。体会这两种存储结构之间的差异。(3) 重点掌握顺序表和链表上各种基本运算的实现。(4) 理解栈和队列的特性以及它们之间的差异,知道在何时使用哪种数据结构。(5) 重点掌握在顺序栈上和链栈上实现栈的基本运算算法,注意栈满和栈空的条件。(6) 重点掌握在顺序队上和链队上实现队列的基本运算算法,注意循环队上队满和队空的条件。(7) 理解串和一般线性表之间的差异。(8)重点掌握在顺序串上和链串上实现串的基本运算算法。(9) 掌握串的模式匹配算法。五、实验总结这次实验是为了了解和运用线性表，栈和队列，串解决问题，虽然至今为止解决的都是书面上的问题，但是随着认识的加深，往后一定能运用到实际中去。六、指