《南邮通达数据结构b存储结构比较实验报告》由会员分享，可在线阅读，更多相关《南邮通达数据结构b存储结构比较实验报告（13页珍藏版）》请在金锄头文库上搜索。
1、实实 验验 报报 告告（ 2015/2015/ 20162016 学年学年 第一学期）第一学期）课程名称数 据 结 构 B实验名称存储结构的比较实验时间2015年 11 月 12日指导单位计算机学院计算机科学与技术系指导教师 徐鹤学生姓名陈世骏班级学号14110212学院(系)通达学院专 业信息工程实实 验验 报报 告告实验名称实验名称存储结构的比较指导教师指导教师徐鹤实验类型实验类型设计实验学时实验学时2实验时间实验时间2015.11.12一、实验目的和要求一、实验目的和要求1. 理解线性表数据结构，掌握线性表的顺序和链接这两种存储表示方法。2. 分别用顺序存储和链接存储实现线性表的基本操作
2、。3. 比较两者的优缺点，并说明两者的应用场合。二、实验内容二、实验内容: :（一）分别用顺序存储和链接存储实现线性表的基本操作（基本操作见P58 线性表 ADT） 。参考教材 4.1.2 线性表的顺序表示和 4.1.3 线性表的链接表示。（二）顺序表操作：具体要求见课本 P295 实习 5 的实习内容和要求（1） 。三、实验环境三、实验环境( (实验设备实验设备) )Visual C+ 6.0（一）顺序存储实现线性表的基本操作#include #include #define MAX 20typedef struct int elementMAX;int size;List;void Cre
3、atelist(List *lst,int n)/创建一个顺序表 int i;printf(“nInput the values of the list:n“);for(i=0;ielementi);lst-size+;void Insert(List *lst,int pos,int x)/在顺序表中第 pos 的位置上插入 xint i;if(lst-size=MAX)/上溢出判断printf(“nOverflow!n“);if(poslst-size)/合法性验证printf(“nOut of bounds!n“);for(i=lst-size-1;i=pos;i-)/插入从后面开始，移
4、动数据元素lst-elementi+1=lst-elementi;lst-elementpos=x;lst-size+;/长度变化void Remove(List *lst,int pos)/删除顺序表中第 pos 个数据元素int i;if(lst-size=lst-size)/合法性验证printf(“nOut of bounds!n“);for(i=pos;isize;i+)/删除从前面开始，移动数据元素lst-elementi=lst-elementi+1;lst-size-;/长度变化void Output(List *lst)/输出顺序表中的数据元素int i;printf(“nT
5、he result is:n“);for(i=0;isize;i+)printf(“%d “,lst-elementi);void main()int n,pos1,x,pos2;List *lst;lst=(List *)malloc(sizeof(List);/定义空顺序表lst-size=0;printf(“nInput the size of the list:n“);scanf(“%d“,Createlist(lst,n);Output(lst);printf(“nInput pos scanf(“%d%d“,Insert(lst,pos1,x);Output(lst);printf
6、(“nInput pos:“);scanf(“%d“,Remove(lst,pos2);Output(lst);（二）链接存储实现线性表的基本操作#include#include#include#includetypedef int T; T* InputElement()static T a; scanf(“%d“, return typedef struct nodeT Element; struct node* Link; Node;void PrintElement(T x)printf(“%d “, x); #define IS_FULL(ptr) (!(ptr)Node* NewN
7、ode()Node* p=(Node*)malloc(sizeof(Node); if (IS_FULL(p)fprintf(stderr, “The memery is fulln“); exit(1); p-Link=NULL; return p; Node* NewNode1()Node* p=(Node*)malloc(sizeof(Node); if (IS_FULL(p)fprintf(stderr, “The memery is fulln“); exit(1); p-Element=*InputElement(); p-Link=NULL; return p; Node* Ne
8、wNode2(T x) Node* p=(Node*)malloc(sizeof(Node); if (IS_FULL(p)fprintf(stderr, “The memery is fulln“); exit(1); p-Element=x; p-Link=NULL; return p; typedef Node*List;List BuildList() Node* p, *r=NULL, *first=NULL; char c; printf(“Another element? y/n“); while (c= getchar() = n); while (tolower(c)!=n)
9、p=NewNode1(); if(first!=NULL) r-Link=p; else first=p; r=p; printf(“Another element? y/n“); while (c= getchar() = n); return first; void PrintList(List first)printf(“nThe list contains: n“); for (; first; first=first-Link)PrintElement(first-Element); printf(“nn“); void Clear(List * first)Node *p=*fir
10、st; while (*first)p=(*first)-Link; free(*first); *first=p; int main()List lst;lst=BuildList();PrintList(lst);Clear(PrintList(lst);四、实验过程描述与结果分析四、实验过程描述与结果分析（一）.线性表的顺序存储表示 1.建立2.插入3、删除（二）.线性表的顺序存储表示 1.建立2.插入3、删除数据4、查找数据：5、修改数据：实实 验验 报报 告告五、实验小结五、实验小结（包括问题和解决方法、心得体会、意见与建议等）顺序表的优点是可以随机存取元素，查找指定位置的元素非常方便，但在其上的插入和删除操作需要移动大量元素，效率不高。此外，顺序表所用空间必须预先分配，难以临时扩大。采用链接方式实现线性表，可动态申请结点空间，线性表的长度一般来说只受内存大小的限制。对于数据元素包含的信息量较大，表的长度事先难以确定，在实际应用中需要频繁执行插入和删除操作的线性表，宜采用链接存储方式。相反，如果数据元素包含的信息量较小，表长已知，实际应用中较少需要插入和删除操作，但需经常根据元素在表中的位置访问该元素，那么采用顺序表是较好的选择。六、指导教师评语六、指导教师评语成成 绩绩批阅人批阅人日日 期期
