《数据结构与算法》实验指导V2017
常熟理工学院
《数据结构与算法》实验指导与报告书
__2017_学年 第__1__ 学期
专 业： 物联网工程___________________________ __ 学 号： __________________________ ____ 姓 名： ________________________________ __ 实验名称：顺序表与链表_______________________________ 实验地点：N6-210_____________________________ ____ 指导教师：聂盼红__________________________ ___
计算机科学与工程学院
2017
常熟理工学院计算机科学与工程学院
1
《数据结构与算法》实验指导V2017 实验二 顺序表与链表
【实验目的】
1、掌握线性表中元素的前驱、后续的概念。
2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。 3、对线性表相应算法的时间复杂度进行分析。 4、理解顺序表、链表数据结构的特点（优缺点）。
【实验学时】
4学时
【实验预习】
回答以下问题：
1、顺序表的存储表示
在顺序表中，任一数据元素的存放位置是从起始位置开始、与该数据元素的位序成正比的对应存储位置，借助LOC(ai)=LOC(a1)+(i-1)*1 确定，则顺序表是一种随机存取的存储结构。
2、单链表的存储表示
线性链表也称单链表，在每一个结点中只包含一个指针，用于指示该结点的直接后继结点，整个链表通过指针相连，最后一个结点因为没有后继结点，其指针置为空（NULL）。这样，链表中所有数据元素（结点）构成一对一的逻辑关系，实现线性表的链式存储。
【实验内容和要求】
1、按照要求完成程序exp2_1.c，实现顺序表的相关操作。以下函数均具有返回值，若操作完成，返回OK，操作失败返回ERROR。函数需返回的其他数据，使用函数参数返回。exp2_1.c部分代码如下：
#include
#define MAXSIZE 100 #define OK 1
typedef int ElemType; /*定义表元素的类型*/
typedef struct slist{ ElemType *list; int listsize; int length; }Sqlist;
常熟理工学院计算机科学与工程学院
2
《数据结构与算法》实验指导V2017
Sqlist *L;
/*（1）---补充顺序表的存储分配表示，采用定长和可变长度存储均可*/ /*函数声明*/
int InitList_sq(Sqlist *L); int CreateList_sq(Sqlist *L);
int ListInsert_sq(Sqlist *L,int i,ElemType e); int PrintList_sq(Sqlist *L);
int ListDelete_sq(Sqlist *L,int i,ElemType *e); int ListLocate(Sqlist *L,ElemType e,int *pos); int menu_select();
/*（2）---顺序表的初始化*/ int InitList_sq(Sqlist *L) {
L->list=(ElemType *)malloc(MAXSIZE*sizeof(ElemType)); if(L->list==NULL)
return ERROR; else {
L->length=0;
L->listsize=MAXSIZE; }
return 0; }/*InitList*/
/*（3）---创建具有n个元素的顺序表*/ int CreateList_sq(Sqlist *L) {
int a,b,c;
printf(\请输入输入数据的个数n:\ scanf(\
printf(\请输入输入的数据:\ for(b=0;b
scanf(\ L->list[b]=c; }
L->length=L->length+a; return 0; }/*CreateList*/
/*（4）---输出顺序表中的元素*/ int PrintList_sq(Sqlist *L)
常熟理工学院计算机科学与工程学院
3
《数据结构与算法》实验指导V2017 {
int a;
printf(\输出数据:\
for(a=0;a
printf(\ \ return 0; }/*PrintList*/
/*（5）---在顺序表的第i个位置之前插入新元素e*/ int ListInsert_sq(Sqlist *L,int i,ElemType e) {
int a=L->length-1; for(;a>=i-1;a--)
L->list[a+1]=L->list[a]; L->list[i-1]=e; L->length+=1; return OK; }/*ListInsert*/
/*（6）---在顺序表中删除第i个元素，e返回删除的元素*/ int ListDelete_sq(Sqlist *L,int i,ElemType *e) {
int a=i-1;
*e=L->list[i-1];
for(;a
L->list[a]=L->list[a+1]; L->length-=1; return OK; }/* ListDelete_sq */
/*（7）---在顺序表中查找指定值元素，pos为返回其位置序号*/ int ListLocate(Sqlist *L,ElemType e,int *pos) {
int a,b=0;
for(a=0;a
if(e==L->list[a]) {
b=0;
*pos=a+1; break; } else
b=1; }
常熟理工学院计算机科学与工程学院
4
《数据结构与算法》实验指导V2017 if(b==1)
return 0; else
return OK; }/* ListLocate */
/*定义菜单字符串数组*/ int menu_select() {
char *menu[]={\ \ /*创建顺序表*/
\ /*查找顺序表中的元素*/ \ /*插入数据*/ \ /*删除数据*/ \ /*退出*/
\ };
char s[3]; /*以字符形式保存选择号*/ int c,i; /*定义整形变量*/
for (i=0;i<7;i++) /*输出主菜单数组*/ printf(\ do {
printf(\ /*在菜单窗口外显示提示信息*/ scanf(\ /*输入选择项*/
c=atoi(s); /*将输入的字符串转化为整形数*/ }
while (c<0||c>4); /*选择项不在0~4之间重输*/
return c; /*返回选择项，主程序根据该数调用相应的函数*/ }
/*主函数*/ int main() {
Sqlist sl;
InitList_sq(&sl); int m,k;
for (;;) /*无限循环*/ {
switch (menu_select()) /*调用主菜单函数，返回值整数作开关语句的条件*/ {
case 1:
printf(\ CreateList_sq(&sl);
常熟理工学院计算机科学与工程学院
5
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库实验二 顺序表与链表在线全文阅读。
相关推荐：