《大数据结构实验报告材料顺序表与链表》由会员分享，可在线阅读，更多相关《大数据结构实验报告材料顺序表与链表（18页珍藏版）》请在金锄头文库上搜索。
1、word实验二 顺序表与链表【实验目的】1、掌握线性表中元素的前驱、后续的概念。2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。3、对线性表相应算法的时间复杂度进展分析。4、理解顺序表、链表数据结构的特点优缺点。【实验学时】4学时【实验预习】回答以下问题：1、顺序表的存储表示假设线性表中每一个数据元素的存储空间大小为1个字节，并且以其所占存储空间的第一个字节的地址作为该元素的存储位置，如此线性表中任一个数据元素的存储位置为：LOC(Ai)=LOC(A1)+(i-1)*1其中，LOC(A1)为线性表中第一个数据元素a1的存储位置，也称为线性表的起始位置首地址。typedef stru
2、ct Sqlist ElemType *slist;/存储空间的基地址 int length;/表长度 int listsize;/当前分配的存储空间容量Sqlist;2、单链表的存储表示线性链表也称单链表，在每一个结点中只包含一个指针，用于指示该结点的直接后继结点，整个链表通过指针相连，最后一个结点因为没有后继结点，其指针置为空NULL。这样，链表中所有数据元素结点构成一对一的逻辑关系，实现线性表的链式存储。【实验内容和要求】1、按照要求完成程序，实现顺序表的相关操作。以下函数均具有返回值，假如操作完成，返回OK，操作失败返回ERROR。函数需返回的其他数据，使用函数参数返回。局部代码如下：
3、#include#include#define ERROR 0#define OK 1#define INIT_SIZE 100#define INCREM 10typedef int ElemType; /*定义表元素的类型*/*1-补充顺序表的存储分配表示，采用定长和可变长度存储均可*/typedef struct Sqlist ElemType *slist;/基地址 int length;/表长度 int listsize;/分配的空间Sqlist;/*函数声明*/int InitList_sq(Sqlist *L);int CreateList_sq(Sqlist *L,int n)
4、;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-slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType); if(!L-slist) return
5、ERROR; L-length=0; L-listsize=INIT_SIZE;/初始空间容量 return OK;/*InitList*/*3-创建具有n个元素的顺序表*/int CreateList_sq(Sqlist *L,int n) ElemType e; int i; for(i=0;in;i+) printf(input data %d:,i+1); scanf(%d,&e); if(!ListInsert_sq(L,i+1,e) return ERROR; return OK;/*CreateList*/*4-输出顺序表中的元素*/int PrintList_sq(Sqlist
6、 *L) int i; for(i=1;ilength;i+) printf(%5d,L-slisti-1); return OK;/*PrintList*/*5-在顺序表的第i个位置之前插入新元素e*/int ListInsert_sq(Sqlist *L,int i,ElemType e) int k; if(iL-length+1) return ERROR; if(L-length=L-listsize)/当前空间已满，申请新的空间 L-slist=(ElemType *)realloc(L-slist,(L-listsize+INCREM)*sizeof(ElemType); if(
7、!L-slist) return ERROR; L-listsize+=INCREM; for(k=L-length-1;k=i-1;k-) L-slistk+1=L-slistk; L-slisti-1=e; L-length+; return OK;/*ListInsert*/*6-在顺序表中删除第i个元素，e返回删除的元素*/int ListDelete_sq(Sqlist *L,int i,ElemType *e) int j; if(iL-length) return ERROR; *e=L-slisti-1; for(j=i;ilength;j+) L-slistj-1=L-sli
8、stj; L-length-; return OK;/* ListDelete_sq */*7-在顺序表中查找指定值元素，pos为返回其位置序号*/int ListLocate(Sqlist *L,ElemType e,int *pos) ElemType *end=L-slist+L-length; ElemType *p=L-slist; int i; for(i=1;p=end) return ERROR; else return OK; /* ListLocate */*定义菜单字符串数组*/int menu_select() char *menu=n*MENU*n, 1. Creat
9、e Listn, /*创建顺序表*/ 2. Get Elementn, /*查找顺序表中的元素*/ 3. Insert datan, /*插入数据*/ 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=ato
10、i(s); /*将输入的字符串转化为整形数*/ while (c4); /*选择项不在04之间重输*/ return c; /*返回选择项，主程序根据该数调用相应的函数*/*主函数*/int main() Sqlist sl; InitList_sq(&sl);int n;int m,k; printf(please input n:); /*输入顺序表的元素个数*/ scanf(%d,&n); if(n=0)printf(ERROR); for (;) /*无限循环*/ switch (menu_select() /*调用主菜单函数，返回值整数作开关语句的条件*/ case 1: printf(n1-Create Sqlist:n); CreateList_sq(&sl,n); printf(nPrint Sqlist:n); PrintList_sq(&sl); break; case 2: printf(n3-GetElem from Sqlist:n); printf(please input search data:); scanf(%d,&k); int pos; if (!ListLocate(&sl,k,&pos) printf(Not found); else printf(found the element, position is %dn,pos);
