2021级本数据结构实验教案.docx
《2021级本数据结构实验教案.docx》由会员分享,可在线阅读,更多相关《2021级本数据结构实验教案.docx(29页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、数据结构实验教案授课教师:祁文青适用专业:计算机科学与技术使用班级:08计科1、2,08网工授课时间:2009年春季授课学时:16学时使用教材:数据结构 严蔚敏 主编实验指导书:数据结构实验指导书,计算机学院编,2008年版黄石理工学院计算机学院实 验 安 排 表周次 日期实验课题学时实验报告次数94.13-4.17实验一线性表的顺序存储实验2学时1104.20-4.24实验二单链表实验2学时114.27-5.1实验二单链表实验2学时1125.4-5.8实验三栈、队列的实现及应用2学时1135.11-5.15实验四二叉树的操作及应用2学时145.18-5.22实验四二叉树的操作及应用2学时11
2、55.25-5.29实验五查找与排序2学时166.1-6.5实验五查找与排序2学时1实验一 线性表的顺序存储实验一、实验目的及要求1、掌握在TC环境下调试顺序表的基本方法2、掌握顺序表的基本操作,插入、删除、查找、以及有序顺序表的合并等算法的实现。二、实验学时2学时三、实验任务1、 生成一个顺序表并动态地删除任意元素和在任意位置插入元素。2、 将两个有序表合并成一个有序表。四、实验重点、难点1、 在顺序表中移动元素。2、 在顺序表中找到正确的插入位置。五、操作要点 (一)顺序表基本操作的实现问题描述 当我们要在顺序表的第i个位置上插入一个元素时,必须先将顺序表中第i个元素之后的所有元素依次后移
3、一个位置,以便腾空一个位置,再把新元素插入到该位置。若是欲删除第i个元素时,也必须把第i个元素之后的所有元素前移一个位置。基本要求 要求生成顺序表时,可以键盘上读取元素,用顺序存储结构实现存储。实现提示 要实现基本操作,可用实现的基本操作,也可设计简单的算法实现。程序实现#include #include typedef int DataType ;# define maxnum 20typedef structint datamaxnum;int length;SeqList;/*插入函数*/int insert(SeqList *L , int i , DataType x)/* 将新结点
4、x插入到顺序表L第i个位置 */ int j ;if( i(*L).length +1) printf( n i 值不合法 ! ); return 0;if(* L).length =maxnum-1) printf( n 表满不能插入!); return 0; for(j=(*L).length;j=i;j-) (*L).dataj+1=(*L).dataj;(*L).datai = x;(*L).length+;return 1;/*删除函数*/int delete( SeqList *L ,int i) /*从顺序L中删除第i个结点*/ int j ;if( i(*L).length )
5、 printf( n 删除位置错误 ! ) ;return 0;for(j=i+1;j=(*L).length;j+)(*L).dataj-1 =(*L).dataj;(*L).length-;return 1;/*生成顺序表*/void creatlist(SeqList * L) int n , i , j ;printf(请输入顺序表 L 的数据个数:n) ;scanf(%d , &n) ;for(i=0 ; in ; i+) printf(data%d = , i) ; scanf(%d,&(*L).datai);(*L).length=n-1;printf(n) ;/*creatli
6、st */*输出顺序表 L*/printout(SeqList * L) int i ;for (i=0 ; i=(* L).length ; i+) printf( data%d=, i) ; printf(%d, (*L).datai);/*printout */printf(n);main() SeqList *L ;char cmd ;int i , t , x;clrscr() ;creatlist(L);doprintf(ni , I - 插入n) ;printf(d , D - 删除n) ;printf(q , Q - 退出n) ;docmd=getchar() ;while(c
7、md!=i)&(cmd!=I)&(cmd!=d)&(cmd!=D)&(cmd!=q)&(cmd!=Q);switch(cmd) case i: case I:printf(nPlease input the DATA: );scanf(%d,&x) ;printf(nWhere? );scanf(%d,&i) ;insert(L,i,x) ;printout(L);break ;case d:case D :printf(nWhere to Delete? );scanf(%d,&i);delete(L,i);printout(L);break ;while(cmd!=q)&(cmd!=Q);
8、(二)有序顺序表的合并问题描述 已知顺序表la和lb中的数据元素按非递减有序排列,将la和lb表中的数据元素,合并成为一个新的顺序表lc基本要求 lc中的数据元素仍按非递减有序排列,并且不破坏la和lb表程序实现# include # define maxnum 20typedef int DataType ;typedef struct DataType datamaxnum ; int length ;SeqList ;int MergeQL(SeqList la , SeqList lb , SeqList *lc) int i , j , k ;if (la.length+1 + lb
9、.length+1maxnum) printf(narray overflow!) ;return 0;i=j=k=0;while(i=la.length & j=lb.length) if (la.dataidatak+=la.datai+ ;else lc-datak+=lb.dataj+;/* 处理剩余部分 */while (idatak+=la.datai+;while (jdatak+=lb.dataj+;lc-length=k-1;return 1;main() SeqList la=3,4,7,12,15,4 ;SeqList lb=2,5,7,15,18,19,5 ;SeqLi
10、st lc ;int i ;if (MergeQL(la,lb,&lc) printf(n) ;for(i=0;i=lc.length ; i+)printf(%4d,lc.datai); 六、注意事项1、 删除元素或插入元素表的长度要变化。2、 在合并表中当某一个表到表尾了就不用比较了,直接将另一个表的元素复制到总表去即可。实验二 单链表实验一、实验目的及要求1、掌握用在TC环境下上机调试单链表的基本方法2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现3、进一步掌握循环单链表的插入、删除、查找算法的实现二、实验学时4学时三、实验任务1、在带头结点的单链表h中第i个数据元
11、素之前插入一个数据元素。2、将两个有序单链表合并成一个有序单链表。四、实验重点、难点1、 在单链表中寻找到第i-1个结点并用指针p指示。2、 比较两个单链表的节点数据大小。 五、操作要点 (一)单链表基本操作的实现问题描述要在带头结点的单链表h中第i个数据元素之前插入一个数据元素x ,首先需要在单链表中寻找到第i-1个结点并用指针p指示,然后申请一个由指针s 指示的结点空间,并置x为其数据域值,最后修改第i-1个结点,并使x结点的指针指向第i个结点,要在带头结点的单链表h中删除第i个结点,首先要计数寻找到第i个结点并使指针p指向其前驱第i-1个结点,然后删除第i个结点并释放被删除结点空间。基本
12、要求用链式存储结构实现存储实现提示链式存储结构不是随机存储结构,即不能直接取到单链表中某个结点,而要从单链表的头结点开始一个一个地计数寻找。程序实现# include # include typedef char DataType ;typedef struct node DataType data; /*结点的数据域*/ struct node *next; /*结点的指针域*/ListNode;void Init_List(ListNode *L)(*L)=(ListNode *)malloc(sizeof(ListNode);/*产生头结点*/(*L)-next=NULL;int Lis
13、t_Length(ListNode *L )int n=0;ListNode *p=L-next;while(p!=NULL)n+;p=p-next;return n;ListNode* GetNode(ListNode *L,int i) int j; ListNode *p; p=L;j=0; /*从头结点开始扫描*/ while(p-next&j!=i) /*顺指针向后扫描,直到p-next为NULL或i=j为止*/ p=p-next; j+; if(i=j) return p; /*找到了第i个结点*/ else return NULL; /*当i0时,找不到第i个结点*/ void
14、InsertList(ListNode *L,DataType x,int i) ListNode *p,*s; p=GetNode(L,i-1); /*寻找第i-1个结点*/ if (p=NULL) /*in+1时插入位置i有错*/ printf(position error); return ; s=(ListNode *)malloc(sizeof(ListNode); s-data=x;s-next=p-next;p-next=s; void DeleteList(ListNode *L ,int i)ListNode *p,*r;p=GetNode(L,i-1); /*找到第i-1个
15、结点*/if (p=NULL|p-next=NULL) /*in时,删除位置错*/ printf(position error); return ; r=p-next; /*使r指向被删除的结点a*/p-next=r-next; /*将ai从链上删除*/free(r); /*使用头插法建立带头结点链表算法*/ListNode * CreatListF(void)char ch;ListNode *head=(ListNode *)malloc(sizeof(ListNode); /*生成头结点*/ListNode *s; /*工作指针*/head-next=NULL; ch=getchar()
16、; /*读入第1个字符*/while(ch!=n) s=(ListNode *)malloc(sizeof(ListNode); /*生成新结点*/ s-data=ch; /*将读入的数据放入新结点的数据域中*/ s-next=head-next; head-next=s; ch=getchar(); /*读入下一字符*/return head; /*使用尾插法建立带头结点链表算法*/ListNode * CreatListR1(void) char ch; ListNode *head=(ListNode *)malloc(sizeof(ListNode); /*生成头结点*/ ListNo
17、de *s,*r; /*工作指针*/ r=head; /*尾指针初值也指向头结点*/ while(ch=getchar()!=n) s=(ListNode *)malloc(sizeof(ListNode); s-data=ch; r-next=s; r=s; r-next=NULL; /*终端结点的指针域置空,或空表的头结点指针域置空*/ return head; /*复制链表A中的内容到表B中*/ void copy(ListNode *a, ListNode *b) ListNode *pa=a-next; ListNode *u; ListNode *rb=b; while(pa!=N
18、ULL) u=( ListNode *)malloc(sizeof(ListNode); u-data=pa-data; rb-next=u; rb=u; pa=pa-next;rb-next=NULL;/*输出带头结点的单链表*/ ListNode *p ; p=la-next ; while(p)printf(%4c,p-data);p=p-next; printf(n) ;/*主函数*/main( ) ListNode *la ,*lb,*lc, *p ;int n,x,i;printf(n用头插法建立链表la,请输入节点内容:);la=CreatListF();DisplaySL(la
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2021 数据结构 实验 教案
限制150内