《数据结构实验1线性表(顺序表)》由会员分享，可在线阅读，更多相关《数据结构实验1线性表(顺序表)（5页珍藏版）》请在金锄头文库上搜索。
1、实验 1 线性表（顺序表）一、实验目的1. 了解线性表的逻辑结构特性，以及这种特性在计算机内的顺序存储结构。通常称为顺序表。2. 重点是线性表的基本操作在顺序存储结构上的实现；其中以插入和删除的操作为侧重点；并进一步学习结构化的程序设计方法。3. 掌握使用 C语言中顺序表的程序设计方法，掌握阅读与补充源程序的方法。二、实例1. 线性表的顺序存储表示（结构）及实现。（1）关于线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素 ai-1, ai，在存储地址中也是相邻的,既地址连续。顺序存储结构也称“向量（vector） ”。在下列类设计中，采用静态一维数组 elem表示向量,同时用 leng
2、th 表示线性表长度。ElemType elemMAXSIZE;int length;有时可以采用动态一维数组来表示向量。ElemType *elem;int length;int MAXSIZE这要求在类的构造函数中，为其 elem 动态分配存储空间，而在析构函数中释放内存空间。在上机实验时，需要将数据结构的类定义（包括成员函数的定义）的程序代码，写入源程序。同时用户必须自己编写一段主函数 main()，在主函数中创建声明类的具体对象，通过这些对象调用类的公有函数。以便将一个典型数据结构类运用到实际问题中去。（2）下面是一个不太完整的的源程序，目的为学生提供一个示范，供学生参考。线性表的顺序
3、存储结构，顺序表类。本程序的特点是，数据元素的类型不再是简单类型（int,char,float） ，而是更加接近使实用的比较复杂的结构体类型。在数据元素输入输出时，情况比较复杂一些。#include #include #define MAXSIZE 10000typedef int ElemType;typedef struct listElemType *elem;int listsize; int length;Sqlist;void initlist_sq(Sqlist *L)L-elem=(ElemType *)malloc(MAXSIZE*sizeof(ElemType);if(!L
4、-elem) exit(0);L-length=0;L-listsize=MAXSIZE;void insert_sq(Sqlist *L,int n,ElemType x)int i;if(nL-length+1) printf(n is errorn); return ;for(i=L-length;i=n;i-)L-elemi+1=L-elemi;L-elemi-1=x;L-length+;/printf(*Sqlist inserted*n); void creat_sq(Sqlist *L)int tablen,i=0;ElemType temp;printf(please inpu
5、t the table lengthn); scanf(%d,&tablen);printf(please input a serial numbern);doscanf(%d,&temp);insert_sq(L,i,temp);i+;while(ilistsize );void display_sq(Sqlist *L)int i;i=0;dowhile(+ilength);printf(n*Sqlist diplay*n); int Search_sq(Sqlist *L,ElemType x)int i;i=0;dowhile(+ilength); return 0;ElemType
6、Search_sq_byV(Sqlist *L,int n)/ElemType temp;return 0 ;void delete_sq(Sqlist *L,int pos)int i;i=0;dowhile(+ilength);printf(n*%d deleted*n,pos); int main(void)Sqlist L1;ElemType temp; char cmd;int i=0;initlist_sq(&L1);printf(X=EXIT,C=CREATE,P=DISPLAY,I=INSERT,S=SEARCH,D=DELETEn );while(1)cmd=getchar(
7、);switch(cmd)case C:case c:creat_sq(&L1);printf(X=EXIT,C=CREAT,P=DISPLAY,I=INSERT,S=SEARCH,D=DELETE n);break;case I:case i:printf(please input the number to be inserted,D=DELETE n);scanf(%d,&temp);printf(please input the position to be inserted(1100)n);scanf(%d,&i);insert_sq(&L1,i-1,temp);printf(*Sq
8、list inserted*n); printf(X=EXIT,C=CREAT,P=DISPLAY,I=INSERT,S=SEARCH,D=DELETE n); break;case S:case s:printf(please input the number wantedn);scanf(%d,&temp);printf(%dn,Search_sq(&L1,temp);printf(X=EXIT,C=CREAT,P=DISPLAY,I=INSERT,S=SEARCH,D=DELETE n);break;case V:case v:printf(please input the pos wa
9、ntedn);scanf(%d,&i);printf(%dn,Search_sq_byV(&L1,i);printf(X=EXIT,C=CREAT,P=DISPLAY,I=INSERT,S=SEARCH,D=DELETE n);break;case D:case d:printf(please input the deleted pos n); scanf(%d,&i);printf(%dn,delete_sq(&L1,i);printf(X=EXIT,C=CREAT,P=DISPLAY,I=INSERT,S=SEARCH,D=DELETE n);break;case P:case p:display_sq(&L1);printf(X=EXIT,C=CREAT,P=DISPLAY,I=INSERT,S=SEARCH,D=DELETE n);break;case X:case x:free(L1.elem);return 1;default:break; return 1;实验内容：1 阅读代码。2 补充程序中没有实现的部分代码。3 完整显示出插入和删除元素时顺序表中元素的移动现象。4 使用随机函数方法产生 1 万个元素，同样随机生成插入（删除）元素位置循环 100 次，统计出平均需要多少时间。
