数据结构实验指导书与答案(徐州工程学院).doc

1、.数据结构实验实验指导书及答案信电工程学院计算机科学和技术教研室编2011.12学习资料.数据结构实验所有代码整理作者郑涛声明：在这里我整理了数据结构实验的所有代码，希望能对大家的数据结构实验的考试有所帮助，大家可以有选择地浏览，特别针对一些重点知识需要加强记忆（ ps: 重点知识最好让孙天凯给出） ，希望大家能够在数据结构实验的考试中取得令人满意的成绩，如果有做的不好的地方请大家谅解并欢迎予以指正。实验一熟悉编程环境实验预备知识：1熟悉本课程的语言编译环境（ TC 或 VC），能够用 C 语言编写完整的程序，并能够发现和改正错误。2能够灵活的编写C 程序，并能够熟练输入C 程序。一、实验目的

2、1熟悉 C 语言编译环境，掌握C程序的编写、编译、运行和调试过程。2能够熟练的将C 程序存储到指定位置。二、实验环境 硬件：每个学生需配备计算机一台。 软件： Windows 操作系统 +Turbo C ；三、实验要求1将实验中每个功能用一个函数实现。2每个输入前要有输入提示（如：请输入2 个整数当中用空格分割：），每个输出数据都要求有内容说明（如：280 和 100 的和是： 380。）。3函数名称和变量名称等用英文或英文简写（每个单词第一个字母大写）形式说明。四、实验内容1在自己的U 盘中建立“姓名+学号”文件夹，并在该文件夹中创建“实验1”文件夹（以后每次实验分别创建对应的文件夹），本次

3、实验的所有程序和数据都要求存储到本文件夹中（以后实验都按照本次要求）。2编写一个输入某个学生10 门课程成绩的函数（10 门课程成绩放到结构体数组中，结构体包括：课程编号，课程名称，课程成绩）。3编写一个求 10 门成绩中最高成绩的函数， 输出最高成绩和对应的课程名称， 如果有多个最高成绩，则每个最高成绩均输出。学习资料.4编写一个求10 门成绩平均成绩的函数。5编写函数求出比平均成绩高的所有课程及成绩。#include#includestruct subjectint subject_id;char subject_name20;double subject_grades;struct su

4、bject sub10;void input()int i;printf(please input:n);for(i=0;i10;i+)scanf(%d %s %lf,&subi.subject_id,&subi.subject_name,&subi.subject_g rades);printf(you just input:n);for(i=0;i3;i+)printf(%d %s %lfn,subi.subject_id,subi.subject_name,subi.subject_g rades);void subject_max()int i,flag;double max=sub0

5、.subject_grades;for(i=0;imax)max=subi.subject_grades;flag=i;printf(Thehighscoreofsubject学习资料.is %s %lfn,subflag.subject_name,max);void subject_average()int i;double average,sum=sub0.subject_grades;for(i=1;i10;i+)sum+=subi.subject_grades;average=sum/10;printf(subjects average is %lfn,average);void su

6、bjct_gtaverage()int i,flag;double average,sum=sub0.subject_grades;for(i=1;i10;i+)sum+=subi.subject_grades;average=sum/10;for(i=0;iaverage)flag=i;printf(subject greater than average is %s %lfn,subflag.subject_name,subflag.subject_grades);int main()input();subject_max();subject_average();subjct_gtaver

7、age();return 0;学习资料.实验二顺序表的基本操作实验预备知识：1熟练运用数组进行程序设计，掌握数组名和指针作为函数参数。2掌握结构体和结构体数组的访问与使用。3熟练实现顺序表类型和变量（如下所示） 定于、 熟悉顺序表的访问原理（顺序存储、随机访问）。一、实验目的1掌握顺序表的建立、数据元素的插入和删除、掌握数据元素的访问。2能够熟练的使用函数来实现顺序表的各种操作。二、实验环境 硬件：每个学生需配备计算机一台。 软件： Windows 操作系统 +Turbo C ；三、实验要求1定义一顺序表类型，并定义顺序表。2将教材中顺序表的建立、初始化、插入、删除等函数实现。3顺序表能够存储

8、10 名学生的基本信息（包括姓名、学号和成绩）。4由主函数按照用户要求对各个顺序表操作访问。5每次操作之前要有明确的说明，操作后要输出操作结果。6分析顺序表的插入、删除、查找的时间和空间复杂度。四、实验内容1在自己的U 盘的“姓名 +学号”文件夹中创建“实验2”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。2完成顺序表操作的如下函数：建立，初始化，增加，插入，删除。学习资料.#include stdio.h#include malloc.h#include string.h#define LIST_INIT_SIZE 1#define LISTINCREMENT 1struct st

9、uchar name6;char num3;int cj;struct sqliststruct stu *elem;int length;int listsize;void main()struct sqlist* initlist_hc();void cshlist_hc(struct sqlist *l);void listinsert_hc(struct sqlist *l);void listdelete_hc(struct sqlist *l);void listhb_hc(struct sqlist *l1,struct sqlist *l2,struct sqlist *l3)

10、;struct sqlist *l1,*l2,*l3;char f;int i, k=0;printf(请选择对顺序表的操作，操作菜单如下：n);for(i=0;i80;i+)printf(*);printf(建立顺序表 (C)n);printf(初始化顺序表 (N)n);printf(顺序表中插入元素(I)n);printf(顺序表中删除元素(D)n);printf(合并顺序表 (H)n);printf(退出系统 (E)n);for(i=0;ielem=(struct stu*)malloc(LIST_INIT_SIZE*sizeof(struct stu);if(!l-elem)print

11、f(出错 !n);l-length=0;l-listsize=LIST_INIT_SIZE;printf(请输入信息以 -1 结束 :n);scanf(%s %s %d,x,y,&z);while(z!=-1)if(l-length=l-listsize)newbase=(struct stu*)realloc(l-elem,(l-listsize+LISTINCREMENT)*sizeof(structstu);if(!newbase)printf(出错 !n);l-elem=newbase;l-listsize+=LISTINCREMENT;strcpy(l-eleml-length.na

12、me,x);strcpy(l-eleml-length.num,y);l-eleml-length.cj=z;scanf(%s %s %d,x,y,&z);if(z!=-1)l-length+;printlist_hc(l);void listinsert_hc(struct sqlist *l)int i,j;struct stu *newbase;void printlist_hc(struct sqlist *l);if(l-length=l-listsize)newbase=(struct stu*)realloc(l-elem,(l-listsize+LISTINCREMENT)*s

13、izeof(struct stu);学习资料.if(!newbase)printf(出错 !n);l-elem=newbase;l-listsize+=LISTINCREMENT;printf(输入要插入信息的位置:);scanf(%d,&j);j-;for(i=l-length;i=j;i-)strcpy(l-elemi+1.name,);strcpy(l-elemi+1.num,l-elemi.num);l-elemi+1.cj=l-elemi.cj;printf(输入插入信息 :n);scanf(%s %s %d,,l-elemj.num,

14、&l-elemj.cj);l-length+;printlist_hc(l);void listdelete_hc(struct sqlist *l)void printlist_hc(struct sqlist *l);int i,j;printf(输入删除信息的位置:);scanf(%d,&j);j-;printf(删除的信息为 :%s,%s,%dn,,l-elemj.num,l-elemj.cj);for(i=j+1;ilength;i+)strcpy(,);strcpy(l-elemi-1.num,l-elem

15、i.num);l-elemi-1.cj=l-elemi.cj;l-length-;printlist_hc(l);void listhb_hc(struct sqlist *l1,struct sqlist *l2,struct sqlist *l3)void printlist_hc(struct sqlist *l);struct stu *p1,*p2,*p3;struct stu *p1_last,*p2_last;p1=l1-elem;p2=l2-elem;l3-length=l1-length+l2-length+1;l3-listsize=l1-length+l2-length+

16、2; p3=l3-elem=(struct stu*)malloc(l3-listsize*sizeof(struct stu);if(!l3-elem)printf(出错 !n);p1_last=l1-elem+l1-length;p2_last=l2-elem+l2-length;while(p1=p1_last&p2cjp2-cj)strcpy(p3-name,p1-name);strcpy(p3-num,p1-num);p3-cj=p1-cj;p1+;p3+;elsestrcpy(p3-name,p2-name);学习资料.strcpy(p3-num,p2-num);p3-cj=p2-

17、cj;p2+;p3+;while(p1name,p1-name);strcpy(p3-num,p1-num);p3-cj=p1-cj;p1+;p3+;while(p2name,p2-name);strcpy(p3-num,p2-num);p3-cj=p2-cj;p2+;p3+;printlist_hc(l3);void printlist_hc(struct sqlist *l)int i;printf(当前表中信息如下:n);for(i=0;ilength;i+)printf(%s,%s,%dn,,l-elemi.num,l-elemi.cj);实验三单链表的基本操作

18、实验预备知识：1熟练运用指针进行程序设计，掌握结构体指针。2掌握使用结构体指针访问结构体变量。3掌握指针作为函数的参数使用。4理解单链表的含义、目的和处理方法。一、实验目的1掌握线性表的链式存贮结构及基本操作，深入了解链表的基本特性，以便在实际问题背景下灵活运用它们。2巩固该存贮结构的构造方法，深入理解和灵活掌握链表的插入、删除等操作。二、实验环境 硬件：每个学生需配备计算机一台。操作系统：DOS或 Windows； 软件： DOS或 Windows 操作系统 +Turbo C ；三、实验要求1定义一链表类型，并定义带有头结点的单链表。2将教材中链表的建立、初始化、插入、删除等函数实现。3链表

19、能够存储10 名学生的基本信息（包括姓名、学号和成绩）。学习资料.4由主函数按照用户要求对各个链表操作访问。5每次操作之前要有明确的说明，操作后要输出操作结果。6分析顺序表链表的插入、删除、查找的时间和空间复杂度。四、实验内容1在自己的U 盘的“姓名 +学号”文件夹中创建“实验3”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。2完成链表操作的如下函数：建立，初始化，增加，插入，删除。/ 链表插入、删除、合并#include stdio.h#includestring.h#includemalloc.h#define LEN sizeof(struct lnode_hc)#define

20、 LEN1 sizeof(struct hc_stu)struct hc_stuchar name3;char num3;int cj;struct lnode_hcstruct hc_stu *data;struct lnode_hc *next;void main()struct lnode_hc *jll();void cshl(struct lnode_hc *head);void crl(struct lnode_hc *head);void scl(struct lnode_hc *head);void hbl(struct lnode_hc *h1,struct lnode_hc

21、 *h2,struct lnode_hc *h3); struct lnode_hc *h1,*h2,*h3;char f;int i, k=0;printf(请选择对链表的操作，操作菜单如下：n);for(i=0;i80;i+)printf(*);printf(建立链表 (C)n);printf(初始化链表 (N)n);printf(链表中插入元素(I)n);printf(链表中删除元素(D)n);printf(合并链表 (H)n);printf(退出系统 (E)n);for(i=0;inext=NULL;return (head);void cshl(struct lnode_hc *he

22、ad)void printl(struct lnode_hc *head);char x3,y3;int z;struct lnode_hc *p1=head,*p2;printf(请输入信息以 -1 结束 :n);scanf(%s %s %d,x,y,&z);while(z!=-1)p2=(struct lnode_hc*)malloc(LEN);if(!p2)printf(出错 !n);p2-data=(struct hc_stu*)malloc(LEN1);if(!p2-data)printf(出错 !n);strcpy(p2-data-name,x);strcpy(p2-data-nu

23、m,y);p2-data-cj=z;p2-next=NULL;p1-next=p2;p1=p2;scanf(%s %s %d,x,y,&z);学习资料.printl(head);void crl(struct lnode_hc *head)void printl(struct lnode_hc *head);int j;struct lnode_hc *p,*p1=head;printf(请输入要插入信息的位置:);scanf(%d,&j);while(j-1)p1=p1-next;p=(struct lnode_hc*)malloc(LEN);if(!p)printf(出错 !n);p-da

24、ta=(struct hc_stu*)malloc(LEN1);if(!p-data)printf(出错 !n);printf(请输入要插入的信息:n);scanf(%s %s %d,p-data-name,p-data-num,&p-data-cj); p-next=p1-next;p1-next=p;printl(head);void scl(struct lnode_hc *head)void printl(struct lnode_hc *head);int j;struct lnode_hc *p1=head,*p2=head-next;printf(请输入要删除信息的位置:);sc

25、anf(%d,&j);while(j1)p1=p1-next;p2=p2-next;j-;printf(删除的信息为 :%s,%s,%dn,p2-data-name,p2-data-num,p2-data-cj);p1-next=p2-next;free(p2);printl(head);void hbl(struct lnode_hc *h1,struct lnode_hc *h2,struct lnode_hc *h3)struct lnode_hc *p1,*p2,*p3;p1=h1-next;p2=h2-next;h3=p3=h1;while(p1&p2)if(p1-data-cjp2

26、-data-cj)p3-next=p1;p3=p1;p1=p1-next;elsep3-next=p2;p3=p2;p2=p2-next;p3-next=p1?p1:p2;free(h2);printl(h3);void printl(struct lnode_hc *head)学习资料.struct lnode_hc *p=head-next;printf(当前表中元素如下:n);while (p-next!=NULL)printf(%s,%s,%dn,p-data-name,p-data-num,p-data-cj);p=p-next;printf(%s,%s,%dn,p-data-nam

27、e,p-data-num,p-data-cj);实验四栈的基本操作实验预备知识：1熟练运用线性结构进行数据处理，熟练使用指针进行数据访问。2掌握递归程序设计思想。3掌握堆栈和队列的应用背景与场合。4理解堆栈和队列的数据类型。一、实验目的1掌握栈的抽象数据类型。2掌握实现栈的各种操作的算法。3理解栈与递归的关系。二、实验环境 硬件：每个学生需配备计算机一台。操作系统：DOS或 Windows； 软件： DOS或 Windows 操作系统 +Turbo C ；三、实验要求1用描述栈的每种操作在顺序栈或链栈上的实现。2. 将建栈、 初始化栈、判断栈是否非空、 求栈的长度、输出从栈顶到栈底的元素分别定

28、义为 5 个子函数，通过主函数实现对上述子函数的调用。3. 输入数据：数据域（ data ）设定为整型。四、实验内容1在自己的U 盘的“姓名 +学号”文件夹中创建“实验4”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。2定义两个堆栈：数据栈和操作栈。3实现如下堆栈处理函数。建栈、初始化栈、判断栈是否非空、求栈的长度、输出从栈顶到栈底的元素#include stdio.h#include stdlib.h#include malloc.h学习资料作者 : 黄晨 );.#include string.h#define STACK_INIT_SIZE 1#define STACKINCRE

29、MENT 1#define ERROR 0typedef structchar *base;char *top;int stacksize;hc_sqstack;void main()hc_sqstack *initstack_hc();void cshstack_hc(hc_sqstack *s);void push_hc(hc_sqstack *s);void pop_hc(hc_sqstack *s);void printstack_hc(hc_sqstack *s);hc_sqstack *s;char f;printf(建立栈 (C)n);printf(初始化栈 (N)n);prin

30、tf(入栈元素 (I)n);printf(出栈元素 (D)n);printf(退出 (E)nn);doprintf(输入要做的操作:);flushall();f=getchar();if(f=C)s=initstack_hc();else if(f=I)push_hc(s);printstack_hc(s);else if(f=N)cshstack_hc(s);printstack_hc(s);else if(f=D)pop_hc(s);printstack_hc(s); while(f!=E);printf(nhc_sqstack *initstack_hc()hc_sqstack *s;s

31、=(hc_sqstack*)malloc(sizeof(hc_sqstack);if(!s)exit(ERROR);return(s);void cshstack_hc(hc_sqstack *s)学习资料.char e;s-base=(char*)malloc(STACK_INIT_SIZE*sizeof(char);if(!s-base)exit(ERROR);s-top=s-base;s-stacksize=STACK_INIT_SIZE;printf(输入要栈的元素以#结束 :n);flushall();e=getchar();while(e!=#)if(s-top-s-base=s-

32、stacksize)s-base=(char*)realloc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(char);if(!s-base)exit(ERROR);s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;*s-top+=e;flushall();e=getchar();void push_hc(hc_sqstack *s)char e;printf(输入要入栈顶元素:);flushall();e=getchar();if(s-top-s-base=s-stacksize)s-base=

33、(char*)realloc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(char); if(!s-base)exit(ERROR);s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;*s-top+=e;void pop_hc(hc_sqstack *s)if(s-top=s-base) exit(ERROR);printf(出栈的元素为 :%cn,*-s-top);void printstack_hc(hc_sqstack *s)char *t=s-top-1;printf(当前栈中元素为:n)

34、;while(t!=s-base)printf(%cn,*t-);printf(%cn,*t);栈的操作1、入栈学习资料.#include stdio.h#include stdlib.h#include malloc.h#include string.h#define STACK_INIT_SIZE 1#define STACKINCREMENT 1#define ERROR 0typedef structchar *base;char *top;int stacksize;hc_sqstack;void main()hc_sqstack *initstack_hc();void cshst

35、ack_hc(hc_sqstack *s);void push_hc(hc_sqstack *s);void printstack_hc(hc_sqstack *s);hc_sqstack *s;char f;printf(建立栈 (C)n);printf(初始化栈 (N)n);printf(入栈元素 (I)n);printf(退出 (E)nn);doprintf(输入要做的操作:);flushall();f=getchar();if(f=C)s=initstack_hc();else if(f=I)push_hc(s);printstack_hc(s);else if(f=N)cshstac

36、k_hc(s);printstack_hc(s);while(f!=E);hc_sqstack *initstack_hc()hc_sqstack *s;s=(hc_sqstack*)malloc(sizeof(hc_sqstack);if(!s)exit(ERROR);return(s);void cshstack_hc(hc_sqstack *s)char e;学习资料.s-base=(char*)malloc(STACK_INIT_SIZE*sizeof(char);if(!s-base)exit(ERROR);s-top=s-base;s-stacksize=STACK_INIT_SI

37、ZE;printf(输入要栈的元素以#结束 :n);flushall();e=getchar();while(e!=#)if(s-top-s-base=s-stacksize)s-base=(char*)realloc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(char);if(!s-base)exit(ERROR);s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;*s-top+=e;flushall();e=getchar();void push_hc(hc_sqstack *s)char

38、e;printf(输入要入栈顶元素:);flushall();e=getchar();if(s-top-s-base=s-stacksize)s-base=(char*)realloc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(char); if(!s-base)exit(ERROR);s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;*s-top+=e;void printstack_hc(hc_sqstack *s)char *t=s-top-1;printf(当前栈中元素为:n);whil

39、e(t!=s-base)printf(%cn,*t-);printf(%cn,*t);实验五队列的基本操作实验预备知识：1熟练运用线性结构进行数据处理，熟练使用指针进行数据访问。2掌握递归程序设计思想。3掌握堆栈和队列的应用背景与场合。4理解堆栈和队列的数据类型。学习资料.一、实验目的1掌握队列的抽象数据类型。2掌握队列的各种操作的算法。3. 掌握队列的链式存贮结构及基本操作，深入了解链队列的基本特性，以便在实际问题背景下灵活运用它们。二、实验环境 硬件：每个学生需配备计算机一台。操作系统：DOS或 Windows； 软件： DOS或 Windows 操作系统 +Turbo C ；三、实验要求

40、1用描述栈的每种操作在顺序栈或链栈上的实现。2用描述每种操作在链队列上的实现。3将建队列、初始化队列、判断队列是否非空、求队列的长度、输出队列的元素分别定义为 5 个子函数，通过主函数实现对上述子函数的调用。4. 输入数据：数据域（ data ）设定为整型。四、实验内容1在自己的U 盘的“姓名 +学号”文件夹中创建“实验4”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。4实现如下链队列处理函数。建队列、初始化队列、判断队列是否非空、求队列的长度、输出队列的元素#include stdio.h#include stdlib.h#include malloc.h#include stri

41、ng.h#define MAXQSIZE 5#define ERROR 0#define OK 1typedef structchar *base;int front;int rear;int length;hc_sqqueue;void main()hc_sqqueue *initqueue_hc();int cshqueue_hc(hc_sqqueue *q);int enqeue_hc(hc_sqqueue *q,char e);学习资料.int deqeue_hc(hc_sqqueue *q);int printqueue_hc(hc_sqqueue *q);hc_sqqueue *q;char f,e;printf(建立队列 (C)n);printf(初始化队列