《数据结构(邹永林版)实验报告2顺序表与链表》由会员分享，可在线阅读，更多相关《数据结构(邹永林版)实验报告2顺序表与链表（19页珍藏版）》请在金锄头文库上搜索。
1、实验二 顺序表与链表【实验目的】1、掌握线性表中元素的前驱、后续的概念。2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。3、对线性表相应算法的时间复杂度进行分析。4、理解顺序表、链表数据结构的特点（优缺点）。【实验学时】2学时【实验预习】回答以下问题：1、顺序表的存储表示在顺序表中，任一数据元素的存放位置是从起始位置开始、与该数据元素的位序成正比的对应存储位置，借助LOC(ai)=LOC(a1)+(i-1)*1确定，则顺序表是一种随机存取的存储结构。2、单链表的存储表示线性链表也称单链表，在每一个结点中只包含一个指针，用于指示该结点的直接后继结点，整个链表通过指针相连，最后一个结点
2、因为没有后继结点，其指针置为空（NULL）。这样，链表中所有数据元素（结点）构成一对一的逻辑关系，实现线性表的链式存储。【实验内容和要求】1、按照要求完成程序exp2_1.c，实现顺序表的相关操作。以下函数均具有返回值，若操作完成，返回OK，操作失败返回ERROR。函数需返回的其他数据，使用函数参数返回。exp2_1.c部分代码如下：#include#include#include#define ERROR 0#define MAXSIZE 100#define OK 1typedef int ElemType; /*定义表元素的类型*/typedef struct slist ElemTyp
3、e *list; int listsize; int length;Sqlist;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,ElemTy
4、pe 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:); scan
5、f(%d,&a); printf(请输入输入的数据:); for(b=0;blistb=c; L-length=L-length+a; return 0;/*CreateList*/*（4）-输出顺序表中的元素*/int PrintList_sq(Sqlist *L) int a; printf(输出数据:); for(a=0;alength;a+) printf(%d ,L-lista); return 0;/*PrintList*/*（5）-在顺序表的第i个位置之前插入新元素e*/int ListInsert_sq(Sqlist *L,int i,ElemType e) int a=L-l
6、ength-1; for(;a=i-1;a-) L-lista+1=L-lista; L-listi-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-listi-1; for(;alength;a+) L-lista=L-lista+1; L-length-=1; return OK;/* ListDelete_sq */*（7）-在顺序表中查找指定值元素，pos为返回其位置序号
7、*/int ListLocate(Sqlist *L,ElemType e,int *pos) int a,b=0; for(a=0;alength;a+) if(e=L-lista) b=0; *pos=a+1; break; else b=1; if(b=1) return 0; else return OK;/* ListLocate */*定义菜单字符串数组*/int menu_select() char *menu=n*MENU*n, 1. Create Listn, /*创建顺序表*/ 2. Get Elementn, /*查找顺序表中的元素*/ 3. Insert datan,
8、/*插入数据*/ 4. Delete datan, /*删除数据*/ 0. Quitn, /*退出*/ n*MENU*n ; char s3; /*以字符形式保存选择号*/ int c,i; /*定义整形变量*/ for (i=0;i7;i+) /*输出主菜单数组*/ printf(%s,menui); do printf(nEnter you choice(04):); /*在菜单窗口外显示提示信息*/ scanf(%s,s); /*输入选择项*/ c=atoi(s); /*将输入的字符串转化为整形数*/ while (c4); /*选择项不在04之间重输*/ return c; /*返回选
9、择项，主程序根据该数调用相应的函数*/*主函数*/int main() int m,k; int pos;int deldata;Sqlist sl; InitList_sq(&sl); for (;) /*无限循环*/ switch (menu_select() /*调用主菜单函数，返回值整数作开关语句的条件*/ case 1: printf(n1-Create Sqlist:n); CreateList_sq(&sl); printf(nPrint Sqlist:n); PrintList_sq(&sl); break; case 2: printf(n3-GetElem from Sql
10、ist:n); printf(please input search data:); scanf(%d,&k); if (!ListLocate(&sl,k,&pos) printf(Not found); else printf(found the element, position is %dn,pos); printf(nPrint Sqlist:n); PrintList_sq(&sl); break; case 3: printf(n4-Insert from Sqlist:n); printf(n input insert location and data:(location,data)n); scanf(%d,%d,&m,&k); if (ListInsert_sq(&sl,m,k) printf(nOKn); printf(nPrint Sqlist:n); PrintList_sq(&sl); else printf(nERROR!); break;
