《数据结构上机报告1》由会员分享，可在线阅读，更多相关《数据结构上机报告1（5页珍藏版）》请在金锄头文库上搜索。
1、1实 验 报 告姓名周亮学号2011444541专业 班级计科 2011-02课程 名称数据结构指导 教师黄永文机房 名称I515上机 日期2012 年 3 月 10 日上机项目名称线性顺序表和线性链表上机步骤及内容： 一、实验目的一、实验目的 1. 了解线性表的逻辑结构特性，以及这种特性在计算机内的顺序存储结构。通常称为顺序表。 2. 重点是线性表的基本操作在顺序存储结构上的实现；其中以插入和删除的操作为侧重点；并进 一步学习结构化的程序设计方法。 3. 掌握使用 C 语言中顺序表的程序设计方法，掌握阅读与补充源程序的方法。 二、实验内容、实验内容 1 阅读代码。 2 补充程序中没有实现的部
2、分代码。 3 完整显示出插入和删除元素时顺序表中元素的移动现象。 4 使用随机函数方法产生 1 万个元素，同样随机生成插入（删除）元素位置循环 100 次，统计出 平均需要多少时间。 实例实例 1. 线性表的顺序存储表示（结构）及实现。 （1）关于线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素 ai-1, ai，在存储地 址中也是相邻的,既地址连续。顺序存储结构也称“向量（vector） ” 。在下列类设计中，采用静态 一维数组 elem表示向量,同时用 length 表示线性表长度。 ElemType elemMAXSIZE;int length; 有时可以采用动态一维数组来表示向
3、量。 ElemType *elem;int length;int MAXSIZE 这要求在类的构造函数中，为其 elem 动态分配存储空间，而在析构函数中释放内存空间。 在上机实验时，需要将数据结构的类定义（包括成员函数的定义）的程序代码，写入源程序。 同时用户必须自己编写一段主函数 main()，在主函数中创建声明类的具体对象，通过这些对象调 用类的公有函数。以便将一个典型数据结构类运用到实际问题中去。1 建立一个顺序存储结构的线性表 完整显示出插入和删除元素时顺序表中元素的移动现象 #define MAXSIZE 1000 typedef int ElemType; typedef str
4、uct list 定义结构体和初始化常数变量 ElemType *elem;int listsize;2int length; Sqlist; void initlist_sq(Sqlist *L) L-elem=(ElemType *)malloc(MAXSIZE*sizeof(ElemType); 为 L 动态分配存储空间if(!L-elem) 分配失败后退出 exit(0);L-length=0;L-listsize=MAXSIZE; 初始化一个长度为零 内存空间为 1000 的线性顺序表 void display_sq(Sqlist *L) int i=0; do printf(“%d
5、 “,L-elemi );while( +i length ); 通过 do while 循环显示完线性表中的元素 void creat_sq(Sqlist *L) 创建一个线性表int tablen,i=1;ElemType temp; 顶一个结构体变量 为产生的元素分派一个内存空间printf(“please input the table lengthn“); 输入线性表的长度scanf(“%d“, L-length = tablen;printf(“please input a serial numbern“);do 通过 do 循环逐个输入线性表中的值scanf(“%d“,inser
6、t_sq(L,i,temp);i+;while( ( i listsize ) );system(“cls“);printf(“ the liner list you creat follows n“);L-length = L-length - tablen;display_sq( L ); int Search_sq_byv(Sqlist *L,ElemType x)int i=0;do 通过输入的值搜索该值再线性表中的位置if( L-elemi = x ) return i; 当找到该值时返回其位置while(+i length); return -1; ElemType Search_
7、sq(Sqlist *L,int n) 通过位置查找值 if( n length else return 0 ; 当输入的位置小于线性表的长度时返回零 int delete_sq(Sqlist *L,int j)int m; if( j L-length) 如果删除的位置大于或小于线性表的长度时返回 0return 0;3m = L-elemj-1;doL-elemj-1 = L-elemj ; 通过 do while 把后面的数统一向前移动一位while(+j length);L-length -;return m;在主函数中通过 switch 语句来调用各个函数 printf(“X=EXI
8、T,C=CREATE,P=DISPLAY,I=INSERT,S=SEARCH,D=DELETEn “);cmd=getchar(); 当从键盘中输入 C 时则开始调用 creat-sq 函数switch(cmd) case C:case c:creat_sq(printf(“X=EXIT,C=CREAT,P=DISPLAY,I=INSERT,S=SEARCH,D=DELETE n“);break;case I:case i:其中函数 display 调用示例如下2 使用随机函数方法产生 1 万个元素，同样随机生成插入（删除）元素位置循环 100 次，统计出 平均需要多少时间。在主函数中依然通过
9、 switch 来选择各个函数 但是多了一些 int main(void)Sqlist L1;char cmd;int i,j,n,k,temp,flage = 1;long double dis; clock_t start,finish; 用于计算时间的变量srand( time(NULL); 用于随机产生不同的种子其中创建线性型表的示例如下在主函数中4switch(cmd)case C:case c:system(“cls“); printf(“nn*Sqlist creat *nn“);printf(“通过随机函数将在线性表中产生 10000 个数(1 - 10000)，如下 ：n“)
10、; start = clock(); creat-sq 函数运行时的起始时间creat_sq(finish = clock(); creat-sq 函数运行后的时间 dis = (finish - start) / Clocksize ; 计算运行时间printf(“nn 该算法共用了%lf s“,dis);void creat_sq(Sqlist *L) creat-sq 函数的定义如下int tablen,i=1;ElemType temp;tablen = 10000; L-length = tablen; 把线性表的长度设置为 10000do temp = rand() % table
11、n + 1; 随机产生一个数insert_sq(L,i,temp); 通过 insert-sq 向线性表中插入数i+;while( ( i listsize ) ); 通过 do-while 循环随机插入 10000 个数printf(“ the liner list you creat follows n“);L-length = L-length - tablen;display_sq( L ); 运行示例如下5结果分析与体会： 起初刚运行后发现很多不足很缺陷，后来经过调试和修改后，逐个改掉了不足，而且在 原本复杂的基础上简单化了一些运算，而且通过模块化编写程序，使程序运行更快和更具可读性。 在编写中难免有些地方不懂和不会，比如怎样计算某个函数的运行时间，后来经过上网查询找到 了 clock_t 类型变量，经过实际操作，发现很符合要求。 这一点让我对网络资源有了很好地理解， 在我们不会时，要学会利用网络给我们带来的方便，来帮助我们学习。还有我们要经常编一些程 序，来熟练一些函数的用法，加深我们的理解。上机成绩， 评语指导教师批改日期
