《数据结构》实验教学大纲.doc

此文档收集于网络，如有侵权，请联系网站删除 数据结构实验教学大纲实验学时：32 实验个数：7 实验学分： 1课程性质：专业必修课 适用专业： 计算机科学与技术教材及参考书：1. 数据结构（C语言版），严蔚敏 吴伟民，北京：清华大学出版社，20042. 数据结构题集（C语言版）实习题部分，北京：清华大学出版社，2004；3. 数据结构实验教程，王玲 刘芳等著，成都：四川大学出版社，2002大纲执笔人：刘芳 大纲审定人：郭涛一、实验课的性质与任务本课程实验大纲是面向计算机相关专业学生开设的数据结构实验课计划指导大纲，是依据数据结构课程教学计划指导大纲编制。计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习编写计算机程序仅仅了解计算机语言是不够的，还必须掌握数据组织、存储和运算的一般方法，这是数据结构课程中学习和研究的内容。由于数据结构的原理和算法较抽象，而该课程一般在本科低年级开设，对于计算机程序设计知识的初学者，理解和掌握其中的原理就显得较为困难。数据结构实验课程着眼于数据结构原理和应用的结合点，使读者学会如何将书上学到的知识用于解决实际问题，培养软件工作需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。本实验课程主要结合数据结构课程的教学大纲的相应内容，设计了7个实验（包括验证型、综合型、设计型实验），力求提高学生的动手能力，做到理论和实践相结合。使学生在实验过程中进一步掌握典型数据结构的逻辑结构、存储结构及算法的程序实现，并训练问题的综合分析能力和编程能力，形成良好的编程风格，为后续课程的学习奠定坚实的理论和实践基础。二、实验课程目的与要求1. 实验目的根据数据结构课程的任务与要求，帮助学生拓宽知识面。并达到以下教学要求：（1） 学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术；掌握各种基本数据结构的逻辑结构和存储结构及相应算法。（2） 本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚、正确易读，符合软件过程的规范，从而培养学生的数据抽象能力；（3） 通过若干数据结构应用实例，引导学生学习数据类型的使用，为今后学习面向对象的程序做一些铺垫。2. 实验要求（1） 熟悉各种基本数据结构的定义，性质和特点，初步掌握算法分析的基本技巧以及如何根据实际问题设计一个有效的算法。（2） 会书写类C语言的算法，并将算法转变为程序实现。（3） 正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现，有较强的逻辑分析能力。（4） 针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的技能。三、实验内容安排：实验一 抽象数据类型的表示与实现（基本操作、验证型实验 2学时）1.目的要求：（1） 熟悉类C语言的描述方法，学会将类C语言描述的算法转换为C源程序实现；（2） 理解抽象数据类型的定义，编写完整的程序实现一个抽象数据类型（如三元组）；（3） 认真阅读和掌握本实验的参考程序，上机运行程序，保存和打印出程序的运行结果，并结合程序进行分析。2.实验内容：（1） 编程实现对一组从键盘输入的数据，计算它们的最大值、最小值、平均值等，并输出。要求：将计算过程写成一个函数，并采用引用参数实现值的求解。#include#define N 100float Average(int numbleN,int a) float sum=0;int i;for(i=0;ia;i+)sum=sum+numblei;return sum/a;int Max(int numbleN,int a) int i;int max= numble0;for(i=1;ia;i+) if(max numble i) max= numble i;return max;int Min(int numble N,int a) int i;int min= numble 0;for(i=1;i numble i) min = numble i;return min;int main() int i=0; int numbleN; printf(请输入数字(-1结束)n ); scanf(%d,&numblei); while(numblei!=-1) i+; scanf(%d,&numblei); printf(平均值是: );printf(%fn, Average(numble,i); printf(最大值是: ); printf(%dn,Max(numble,i); printf(最小值是: ); printf(%dn,Min(numble,i);（2） 编程实现抽象数据类型三元组的定义、存储和基本操作，并设计一个主菜单完成各个功能的调用。 #include h1.htypedef int ElemType;typedef ElemType *Triplet;Status InitTriplet (Triplet &t,ElemType v1,ElemType v2,ElemType v3)t=(ElemType *)malloc(3*sizeof(ElemType);if(!t) return OVERFLOW;t0=v1;t1=v2;t2=v3; return OK;Status DestroyTriplet(Triplet &t)free(t); t=NULL;return OK;ElemType get(Triplet &t,int i)ElemType e;if (i3) printf(i值不合法n);e=ti-1;return e;Status put(Triplet &t,int i,ElemType e) if (i3) printf(i值不合法n);ti-1=e;return OK;Status IsAscending(Triplet t)return (t0=t1)&(t1=t1)&(t1=t2);ElemType Max(Triplet t)ElemType e;e=(t0=t1)?(t0=t2)?t0:t2):(t1=t2)?t1:t2);return e;ElemType Min(Triplet t)ElemType e;e=(t0=t1)?(t0=t2)?t0:t2):(t1=t2)?t1:t2);return e;void main()Triplet p;ElemType x;ElemType v1,v2,v3;int select,i;printf(输入三个数，建立一个三元组n);scanf(%d%d%d,&v1,&v2,&v3);if (InitTriplet(p,v1,v2,v3)=OVERFLOW) printf(分配失败，退出程序！);else do printf(1:取三元组第i个元素n);printf(2:判断三元组元素是否递增n);printf(3:求最大值n);printf(4:求最大值n);printf(5:置换第i个元素n);printf(0:结束！n);printf(请输入选择！n);scanf(%d,&select);switch (select)case 1: printf(ni=); scanf(%d,&i); printf(第%d个元素的值为：%dn,i,get(p,i); break;case 2: if (IsAscending(p)=1) printf(三元组递增有序n); else printf(三元组非递增有序n); if (IsDescending(p)=1) printf(三元组递减有序n); else printf(三元组非递减有序n); break;case 3: printf(最大值是：%dn,Max(p); break;case 4: printf(最小值是：%dn,Min(p); break;case 5: printf(ni=); scanf(%d,&i); printf(nx=); scanf(%d,&x); put(p,i,x); printf(置换第%d个元素后的3个元素分别为：%d,%d,%dn,i,p0,p1,p2); break;case 0: printf(操作结束！); break;default:printf(输入选择出错！n);/ 结束switch while(select!=0); / 结束whileDestroyTriplet(p);/ 结束main3.主要仪器设备及软件（1） PC机（2） Turbo C 2.0 或Visual C+实验二 线性表及其实现（基本操作、验证型实验 4学时）1.目的要求：（1） 熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现，以线性表的各种操作（建立、插入、删除等）的实现为实验重点；（2） 通过本次实验帮助学生加深对顺序表、链表的理解，并加以应用；（3） 掌握循环链表和双链表的定义和构造方法2. 实验内容：（1） 编程实现线性表两种存储结构（顺序存储、链式存储）中的基本操作的实现（线性表的创建、插入、删除和查找等），并设计一个菜单调用线性表的基本操作。 链式存储：#include#includeint initList(LinkList &L);void listElemOutput_L(LinkList &L);int listInsert_L(LinkList &L,int i,ElemType e);int listDelete_L(LinkList &L,int i);int locateElem_L(LinkList &L,int i );int menu();int main()LinkList La; int mchioce; mchioce=menu(); while ( mchioce!=0) switch(mchioce) case 1: initList(La); break; break; case 2: int i,j; printf(请输入插入的位置和元素：); scanf(%d%d,&i,&j); listInsert_L(La, i, j); break; case 3: int k; printf(请输入删除元素的位置：); scanf(%d,&k); listDelete_L(La, k); break; case 4: int a; printf(请输入所查找元素的位置：); scanf(%d,&a); locateElem_L(La,a ); break; case 5: listElemOutput_L(La); break; default: printf(输入错误！); break; system(cls); mchioce=menu(); system(PAUSE); int initList(LinkList &L) /*构造一个空的线形链表L。*/Link tempp=NULL;if(!(tempp=(Link)malloc(sizeof(LNode)printf(allocation of memory fail!);return ERROR;tempp-data=0;/*初始化头结点*/tempp-next=NULL;L.len=0;L.head=tempp;L.tail=tempp;printf(链表创建成功！n);int j ,i;int q;printf(输入线性表的元素个数：n); scanf(%d,&j);printf(输入新的元素：n); for(i=1;idata = q; p -next=L.tail-next;L.tail-next =p;L.tail=L.tail-next;+L.len; return OK; void listElemOutput_L(LinkList &L) /*int i=1; for(;inext-data);p.head=p.head-next; */ Link q; q=L.head-next; while(q) printf(t %d,q-data); q=q-next; printf(n); system(PAUSE);return; int listInsert_L(LinkList &L,int i,ElemType e)/*在带头结点的单链表L的第i 个元素之前插入元素e。*/ LinkList p=L; Link s; int j=0; while (p.head&jnext;+j; if (!p.head|ji-1) return ERROR; s= (Link)malloc(sizeof(LNode); s-data =e; s-next = p.head-next;/插入新的元素 p.head-next =s; +L.len;return OK; int listDelete_L(LinkList &L,int i) LinkList p=L;Link q;q=(Link)malloc(sizeof(LNode); int j=0; while (p.head-next&jnext） p.head = p.head-next;+j; if (!p.head-next|ji-1) return ERROR; q=p.head-next; p.head-next=q-next; free(q);-L.len;return OK; int locateElem_L(LinkList &L,int i ) LinkList p=L; int j=0;printf(你要查找的元素是:); while (p.head&jnext;+j; printf(t%d,p.head-data); printf(n); system(PAUSE); /*if (!p.head) printf(t%d,p.head-data); else return ERROR; printf(n); system(PAUSE);*/return OK; int menu() int i; printf(ttt菜单n); printf(t1.创建顺序链表n);printf(t2.插入n);printf(t3.删除n);printf(t4.查找n);printf(t5.打印所有元素n);printf(t0.退出n);printf(n);printf(请输入正确的序号：);scanf(%d,&i);if(i=0)exit(0); elsereturn i;顺序存储：#include#includevoid listElemOutput_Sq(SqList *L);int listInsert_Sq(SqList *L,int i,ElemType e);int listDelete_Sq(SqList *L,int i );int initList_Sq(SqList *L);int locateElem_Sq(SqList L,int i );int menu(); void main() int mchioce; int a=1; SqList La; mchioce=menu(); while ( mchioce!=0) switch(mchioce) case 1: initList_Sq(&La); break; break; case 2: int i,j; printf(请输入插入的位置和元素：); scanf(%d%d,&i,&j); listInsert_Sq(&La,i,j); break; case 3: int k; printf(请输入删除元素的位置：); scanf(%d,&k); listDelete_Sq(&La, k); break; case 4: int a; printf(请输入所查找元素的位置：); scanf(%d,&a); locateElem_Sq(La,a); break; case 5: listElemOutput_Sq(&La); break; default: printf(输入错误！); break; system(cls); mchioce=menu(); system(PAUSE); void listElemInput_Sq(SqList &L) int la_len;int i; printf(输入线性表LA元素个数：); scanf(%d,& la_len); printf(请输入A的元素：); for(i=1;i=la_len;i+) scanf(%d, &L.elemi);L.length+;void listElemOutput_Sq(SqList *L) int i=1;printf(nt输出:nt);for(;ilength;i+)printf(t %d,L-elemi); printf(n); system(PAUSE);return;int listInsert_Sq(SqList *L,int i,ElemType e) /*在顺序表L中第i个位置之前插入新的元素 e */ /* i的合法值为1= i = ListLength_Sq(L)+1 */ ElemType *p,*q,*newbase; if(iL-length+1) return ERROR; /* i值不和法*/ if(L-length=L-listsize) /*当前存储空间已满，增加分配*/ newbase=(ElemType *)realloc(L-elem,(L-listsize+LISTINCREMENT)*sizeof(ElemType);/重新分配新的内存空间 if(!newbase) exit(OVERFLOW); /*存储空间分配失败*/ L-elem=newbase; /* 新基址 */ L-listsize+=LISTINCREMENT; q=&(L-elemi); /* q为插入位置*/ for(p=&L-elemL-length;p=q;-p) *(p+1)=*p; *q=e; +(L-length); return OK;/*ListInset_Sq*/int listDelete_Sq(SqList *L,int i) /*在顺序表L中删除第i个元素，并用 e返回其值 */ /* i的合法值为1= i = ListLength_Sq(L)*/ ElemType *p,*q; if(iL-length) return ERROR; /* i值不和法*/ p=&(L-elemi); /* p为删除元素的位置*/ /*被删除元素值赋给e */q=L-elem+L-length; /* 表尾元素的位置 */for(+p; plength; /* 表长减1 */ return OK;/*ListDelete_Sq*/int initList_Sq(SqList *L) L-elem=(ElemType *) malloc(LIST_INIT_SIZE *sizeof(ElemType);if(!L-elem) exit(OVERFLOW); /* 存储分配失败*/L-length=0; /* 空表长度为0 */L-listsize=LIST_INIT_SIZE; int la_len;int i; printf(创建成功！n); printf(输入元素的个数：); scanf(%d,& la_len); printf(请输入新的元素：n); for(i=1;ielemi);L-length+; return OK;int locateElem_Sq(SqList L,int i )printf(你要查找的元素是:n); printf(%d,L.elemi);printf(n); system(PAUSE);return OK;int menu() int i; printf(ttt菜单n); printf(t1.创建顺序链表n);printf(t2.插入n);printf(t3.删除n);printf(t4.查找n);printf(t5.打印所有元素n);printf(t0.退出n);printf(n);printf(请输入正确的序号：);scanf(%d,&i);if(i=0)exit(0); elsereturn i;（2） 建立一个按元素递增有序的单链表L，并编写程序实现：将x插入其中后仍保持L的有序性；将数据值介于min和max之间的结点删除，并保持L的有序性；（选做）将单链表L逆置并输出； #include int initList(LinkList &L) /*构造一个空的线形链表L。*/Link tempp=NULL;if(!(tempp=(Link)malloc(sizeof(LNode)printf(allocation of memory fail!);return ERROR;tempp-data=0;/*初始化头结点*/tempp-next=NULL;L.len=0;L.head=tempp;L.tail=tempp;printf(链表创建成功！n);int j ,i;int q;printf(输入线性表的元素个数：n); scanf(%d,&j);printf(输入新的元素：n); for(i=1;idata = q; p -next=L.tail-next;L.tail-next =p;L.tail=L.tail-next;+L.len; return OK;int fun1(LinkList &L,int i)/插入一个数仍保证递增性 Link s1=L.head-next; Link s2=L.head; Link p; while(s1) if(s1-datanext; s2=s2-next; else p= (Link)malloc(sizeof(LNode); p-data = i;p-next=s2-next;s2-next=p; +L.len;break; p= (Link)malloc(sizeof(LNode); p-data = i;p-next=s2-next;s2-next=p;L.tail=L.tail-next; return OK;int fun2(LinkList &L)/保留数字最大和最小的结点，删除其余的 Link s=L.head-next-next; Link p=s; while(p!=L.tail) s=s-next; free(p);p=s; L.head-next-next=L.tail; return OK;int fun3(LinkList L)/链表的逆置 Link p=L.head-next; free(L.head);/释放原来的头结点 Link q=p-next; Link s=q-next; Link tempp;/建立新的结点 tempp=(Link)malloc(sizeof(LNode); tempp-next=L.tail; L.head=tempp; L.tail=p; if(p=L.head-next) p-next=NULL; return OK; p-next=NULL; while(1) if(q=L.head-next)/三个指针循环，当有一个指针指向L.head-next表示结束，退出循环 q-next=p; break;q-next=p; p=s-next;if(s=L.head-next) s-next=q; break;s-next=q;q=p-next;if(p=L.head-next) p-next=s; break;p-next=s;s=q-next; return OK;void listElemOutput_L(LinkList &L) Link q; q=L.head-next; while(q) printf(t %d,q-data); q=q-next; printf(n);return;int main() LinkList La; initList(La); fun1(La,100);/插入100； fun2(La); fun3(La);/逆置 listElemOutput_L(La);（3） （选做）编程实现将两个按元素递增有序的单链表合并为一个新的按元素递增的单链表。 #includeint initList(LinkList &L) /*构造一个空的线形链表L。*/Link tempp=NULL;if(!(tempp=(Link)malloc(sizeof(LNode)printf(allocation of memory fail!);return ERROR;tempp-data=0;/*初始化头结点*/tempp-next=NULL;L.len=0;L.head=tempp;L.tail=tempp;printf(链表创建成功！n);int j ,i;int q;printf(输入线性表的元素个数：n); scanf(%d,&j);printf(输入新的元素：n); for(i=1;idata = q; p -next=NULL;L.tail-next =p;L.tail=L.tail-next;+L.len; return OK;int function(LinkList &L,LinkList S) L.len+=S.len; Link p=L.head; Link q=L.head-next; Link s=S.head-next; Link k; while(s) while(s-dataq-data) q=q-next; p=p-next;if(q=NULL)break; if(q=NULL) while(s) k=s-next; s-next=NULL; p-next=s; p=s; s=k; else k=s-next; s-next=p-next;p-next=s; p=s; s=k; return OK;int main() LinkList Sa,Sb; initList(Sa); initList(Sb); function(Sa,Sb); int i; Link p=Sa.head-next; for(i=0;idata); p=p-next;3.主要仪器设备及软件（1） PC机（2） Turbo C 2.0 或Visual C+实验三 栈和队列及其应用（验证型、设计型实验 6学时）1.目的要求：（1） 掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们；（2） 本实验训练的要点是“栈”的观点及其典型用法；（3） 掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化方法。2.实验内容：（1） 编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）；栈的链式存储：#includetypedef structLinkbase,top; /*链表的头指针和尾指针*/intlen; /*链表的长度*/LinkStack; int InitStack(LinkStack &S);int Push(LinkStack &S,ElemType e);int Pop(LinkStack &S,ElemType &e);int InitStack(LinkStack &S) Link tempp=NULL;if(!(tempp=(Link)malloc(sizeof(LNode)printf(allocation of memory fail!);return ERROR;tempp-data=0;/*初始化头结点*/tempp-next=NULL;S.base=tempp;S.top=tempp; S.len= 0;return OK;int Push(LinkStack &S,ElemType e) Link s; s= (Link)malloc(sizeof(LNode); s-data =e; S.top-next=NULL; S.top-next =s;S.top=S.top-next;/尾指针移动+S.len;/长度加1 return OK;int Pop(LinkStack &S,ElemType &e) LinkStack p=S; int j=0; while (p.base-next&jnext;+j; if (!p.base-next) return ERROR;/说明为空 e=p.base-next-data; p.base-next=p.base-next-next;-S.len; return OK;int main()LinkStack Sa; InitStack(Sa); int a,i,j,k; /*for (i=1;i=4;i+) printf(%请写出要插入的数：n); scanf(%d,&a); Push(Sa,a); Pop(Sa,k); LinkStack p=Sa; for(j=1;jnext-data); p.base=p.base-next; */ while(1) printf(ttt菜单n); printf(tt1.建立新的栈n); printf(tt2.压栈n); printf(tt3.出栈n); printf(tt0.退出n); printf(tt请选择操作的序号：); int j; scanf(%d,&j); switch(j) case 1: InitStack(Sa);printf(链表创建成功！n);break; case 2:printf(请输入需要压栈的数：); scanf(%d,&a); Push(Sa,a);break; case 3: Pop(Sa,k);pri