1、实验报告学生数 据 结 构实验报告班级学号： 11214030236 姓名： 庄彦兴 数 据 结 构实验报告学院：信息科学与技术学院 专业： 信息系统与信息管理 学期：20132014学年第一学期 班级： 信A1232班 学号： 1124030236 姓名： 庄彦兴 实验1 函数、指针、结构体复习院（系）：信息科学与技术学院 课程名称：数据结构 教师签名：班级信A1232学号11214030236实验室专业信息系统与信息管理姓名庄彦兴计算机号实验名称所用软件实验成绩1.1 实验目的 1掌握C语言的语法并由算法形成相应的程序。2熟练掌握C语言函数调用的相关知识点。3熟练掌握C语言的指针和结构体相
2、关知识点。4理解数据结构的基本概念。1.2 实验准备1复习C语言的函数调用、指针、结构体的相关知识点。2算法的概念和算法分析等知识。3C语言程序设计有关函数及数组等的知识及编程环境的使用方法。4复习课堂讲解的理论内容。1.3 实验任务1在提示/*blank*/下面填写合适的内容完成程序设计。编写一个程序，判断一个字符串是否为“回文”（顺序和倒读都一样的字符串称为“回文”），并分析算法的时间复杂度。提示：实现本程序需要设计两个函数。主函数main，数据的输入和输出在该函数中完成。自定义函数func，判断串s是否为回文。采用的方法是：用flag表示是否为回文。用i从左向右扫描字符串s，用j从右向左
3、扫描字符串s，若si与sj不相等，则flag=0（表示不是回文）并退出循环，否则，继续比较直到ij不成立。/*判断指定字符串是否回文*/#include #include int func(char *str)int i,j,t,flag; t=strlen(str); for(i=0,j=t-1;i=t/2) flag=1; return flag;void main()/*blank*/_; /*填空位置1：变量定义*/_; /*填空位置2：从键盘输入需要判定的字符串*/_; /*填空位置3：调用func函数*/_; /*填空位置4：根据返回值flag的值，输出判定结果*/该算法的时间复杂
4、度是：_。2定义函数int f(char *x, char y)判断x所指的字符串是否包含字符y，若是则函数返回1，否则返回0。写出完整的源程序代码。#include #include int f(char *x,char y) /*写出自定义函数f的函数体部分，实现函数功能*/void main() char str10,ch; int t; gets(str); scanf(%c,&ch); t=f(str,ch); printf(t=%dn,t);3用结构体类型编写一个程序，输入一个学生的学号、姓名及3门课的成绩，计算并输出其平均成绩。写出完整的源程序代码。#include struct
5、 student int id; char name10; float score3;s;main() /*写出main函数的函数体部分，实现函数功能*/实验2 线性表院（系）：信息科学与技术学院 课程名称：数据结构 教师签名：班级信1232学号11214030236实验室专业信息管理与信息系统姓名庄彦兴计算机号实验名称所用软件实验成绩2.1 实验目的1掌握顺序表的基本特点。2熟练掌握顺序表的建立、查找、插入和删除等操作。3掌握单链表的基本特点。4熟练掌握单链表的建立、插入、删除等基本操作。5理解循环链表、双向链表的含义及其特点。6了解循环链表、双向链表的基本操作。2.2 实验准备 1线性表顺
6、序存储结构的表示。2顺序表的基本操作：顺序表的建立、查找、插入、删除。3线性表链式存储结构的表示。4链表的基本操作：链表的建立、查找、插入、删除。2.3 实验任务1实现顺序表的各种基本操作。（1）源程序代码。#include #define Maxsize 100typedef int datatype;typedef struct seqnode /*顺序表的类型定义*/ datatype listMaxsize; /*定义一个存放顺序表的一维数组list*/ int last; /*定义线性表的最后一个元素的下标*/seqlist;void create(seqlist *L) /*建立一
7、个顺序存储的线性表*/ int i; printf(Please input the len of the seqlist:); /*从键盘输入当前顺序表的实际长度*/ scanf(%d,&(*L).last); printf(Please input the every element of the seqlist:); for(i=0;i=(*L).last;i+) /*从键盘输入顺序表的每个元素*/ scanf(%d,&(*L).listi); printf(Output the every element of the seqlist:n); for(i=0;i=(*L).last;i
8、+) /*顺序表建立成功后，输出整个顺序表*/ printf(%5d,(*L).listi); /*运行结果（1）*/ printf(n);void access(seqlist *L,int i) /*根据指定位置访问线性表*/ if(i(*L).last) /*判断给定位置是否为合法取值*/ printf(The place is not correct!n); else printf(%dn,(*L).listi); /*运行结果（2）*/void before_after(seqlist *L,int i) /*根据指定位置寻找其前趋元素和后继元素*/ if(i(*L).last) p
9、rintf(The place is not correct!n); else if(i=0) printf(%dn,(*L).listi+1); else if(i=(*L).last) printf(%dn,(*L).listi-1); else if(i0)&(i(*L).last) printf(%d,%dn,(*L).listi-1,(*L).listi+1); /*运行结果（3）*/void search(seqlist *L,int key) /*根据给定元素key查找顺序表*/ int m; for(m=0;m(*L).last) printf(The seqlist has
10、no the key!n); /*运行结果（4）*/void delete(seqlist *L,int i) /*删除顺序表的元素*/ int m; printf(Output the every element of the seqlist before deleting:n); /*删除前输出顺序表中的所有元素*/ for(m=0;m=(*L).last;m+) printf(%5d,(*L).listm); /*运行结果（5）*/ printf(n); for(m=i;m=(*L).last;m+) /*删除位置之后的所有元素依次左移一位*/ (*L).listm=(*L).listm
11、+1; (*L).last -; printf(Output the every element of the seqlist after deleting:n); /*删除后输出顺序表中的所有元素*/ for(m=0;m(*L).last;m+) printf(%5d,(*L).listm); /*运行结果（6）*/ printf(n);void insert(seqlist *L,int i,int e) /*在顺序表指定位置i后插入元素e*/ int m; printf(Output the every element of the seqlist before inserting:n)
12、; /*插入前输出顺序表中的所有元素*/ for(m=0;m=i;m-) /*插入位置之后的元素依次右移一位*/ (*L).listm+1=(*L).listm; (*L).listi=e; /*在指定位置i上插入元素e*/ printf(Output the every element of the seqlist after inserting:n); /*插入后输出顺序表中的所有元素*/ for(m=0;m(*L).last;m+) printf(%5d,(*L).listm); /*运行结果（8）*/ printf(n);void main() seqlist *L,l; /*注意：l
13、是字母L的小写*/ int i,e; L=&l; printf(n-function:create-n); create(L); /*调用函数create建立一个顺序表*/ printf(n-function:access-n); printf(Please input the position:); scanf(%d,&i); /*从键盘输入访问位置i*/ access(L,i); /*调用函数access根据指定位置访问顺序表*/ printf(n-function:before_after-n); printf(Please input the position:); scanf(%d,
14、&i); /*从键盘输入指定位置i*/ before_after(L,i); /*调用函数before_after根据位置i确定前趋元素和后继元素*/ printf(n-function:search-n); printf(Please input the search key:); scanf(%d,&e); /*从键盘输入查找元素e*/ search(L,e); /*调用函数search根据关键字e查找顺序表*/ printf(n-function:delete-n); printf(Please input the delete position:); scanf(%d,&i); /*从
15、键盘输入删除位置i*/ delete(L,i); /*调用函数delete删除指定位置i的元素*/ printf(n-function:insert-n); printf(Please input the insert position:); scanf(%d,&i); /*从键盘输入插入位置i*/ printf(Please input the insert element:); scanf(%d,&e); /*从键盘输入插入元素e*/ insert(L,i,e); /*调用函数insert在插入位置i上插入元素e*/（2）上机调试上面的源程序，并根据下列原始数据记录程序的运行结果。原始数据
16、顺序表的实际长度10顺序表的元素1，2，3，4，5，6，7，8，9，10访问顺序表的位置i5寻找前趋、后继元素的指定位置i7查找关键字e58删除位置i5插入位置i7插入元素e28（3）运行结果记录。Output the every element of the seqlist:Output the every element of the seqlist before deleting:Output the every element of the seqlist after deleting:Output the every element of the seqlist before ins
17、erting:Output the every element of the seqlist after inserting:2在提示/*blank*/下面填写合适的内容完成程序设计。已知一个有序（升序）的顺序表，现有一个数据e，请将e插入到该顺序表中并要求插入后顺序表依然有序。提示：（1）顺序表中原有数据个数为10个，依次是1,3,5,7,12,45,67,89,92,99。（2）需要插入的数据e值为25。（3）注意表长的变化。（4）有序表的插入，需要分两步完成：第一步确定插入位置，第二步在插入位置上插入指定的数据。（5）程序运行结果如图2-1所示。图2-1 实验运行结果#define Ma
18、xsize 100#include typedef int datatype;typedef struct seqnode /*顺序表的类型定义*/ datatype listMaxsize; /*定义一个存放顺序表的一维数组list*/ int last; /*定义线性表的最后一个元素的下标*/seqlist;void create(seqlist *L) /*根据已知条件建立一个有序的顺序表*/ int i; printf(nnPlease input the length of the ordered seqlist:); /*blank*/ _; /*从键盘输入有序表的实际长度，已知(
19、*L).len=10*/ printf(nnPlease input the every element of the ordered seqlist:); for(i=0;i=(*L).last;i+) /*blank*/ _;/*功能：从键盘输入有序表中的每个元素，1,3,5,7,12,45,67,89,92,99*/void insert(seqlist *L,int e) /*在顺序表指定位置i后插入元素e*/ int i,j,m,n; printf(nnOutput the every element of the seqlist before inserting:n); /*插入前
20、输出顺序表中的所有元素*/ for(n=0;n=0;i-) /* i变量自减 */ /*blank*/ if(_) /*确定插入位置*/ /*blank*/ _; /*插入位置之后的元素依次右移一位*/ j=i; /*blank*/ _; /*在确定的插入位置j上插入元素e*/ printf(nnOutput the every element of the seqlist after inserting:n); /*插入后输出顺序表中的所有元素*/ for(n=0;nnext=NULL; /*从头结点开始建立单链表*/ q=H; printf(Please input the length
21、of the linklist:); /*根据实际情况从键盘输入表长*/ scanf(%d,&n); printf(Please input the every element:); /*从键盘输入线性表的每个元素*/ for(i=1;idata=e; /*指向结点的指针变量p指向当前要插入的结点*/ q-next=p; /*指向结点的指针变量q指向当前插入结点的前趋结点，将p作为其后继赋值，完成当前结点的插入*/ q=p; /*当前结点完成插入之后，修改指针变量q，为下一次插入做好准备*/ q-next=NULL; return H;void search(NODE * H,DataType
22、 e) /*在单链表中查找指定数据元素e*/ NODE * p; int i=1; p=H-next; /*指针变量p赋值为头结点的后继，从该位置开始查找整个单链表*/ while(p) /*当p不为空时，执行循环*/ if(p-data!=e) /*指针变量p当前指向结点的数据域不等于查找元素e*/ p=p-next; /*指针后移，继续向下查找*/ i+; continue; else /*否则，查找成功，输出该结点的位置*/ printf(Searching is successful!n); printf(The place of the search key in the memory is:%dn,p); /*输出该结点在内存中的存储地址，（2）*/ printf(The place of the search key in the list is:%dn,i); /*输出该结点在线性表中的位置，（3）*/ break; if(p-next=NULL) printf(The linklist has
