数据结构(邹永林版)实验报告2顺序表与链表.doc

实验二 顺序表与链表【实验目的】1、掌握线性表中元素的前驱、后续的概念2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法3、对线性表相应算法的时间复杂度进行分析4、理解顺序表、链表数据结构的特点（优缺点）实验学时】2学时【实验预习】回答以下问题：1、顺序表的存储表示在顺序表中，任一数据元素的存放位置是从起始位置开始、与该数据元素的位序成正比的对应存储位置，借助LOC(ai)=LOC(a1)+(i-1)*1确定，则顺序表是一种随机存取的存储结构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{ ElemType *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,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("%d",&a); printf("请输入输入的数据:"); for(b=0;blist[b]=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->list[a]); 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(;alength;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;alength;a++) { if(e==L->list[a]) { 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 List\n", /*创建顺序表*/ " 2. Get Element\n", /*查找顺序表中的元素*/ " 3. Insert data\n", /*插入数据*/ " 4. Delete data\n", /*删除数据*/ " 0. Quit\n", /*退出*/ "\n***************MENU******************\n" }; char s[3]; /*以字符形式保存选择号*/ int c,i; /*定义整形变量*/ for (i=0;i<7;i++) /*输出主菜单数组*/ printf("%s",menu[i]); do { printf("\nEnter you choice(0~4):"); /*在菜单窗口外显示提示信息*/ scanf("%s",s); /*输入选择项*/ c=atoi(s); /*将输入的字符串转化为整形数*/ } while (c<0||c>4); /*选择项不在0~4之间重输*/ return c; /*返回选择项，主程序根据该数调用相应的函数*/}/*主函数*/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 Sqlist:\n"); printf("please input search data:"); scanf("%d",&k); if (!ListLocate(&sl,k,&pos)) printf("Not found"); else { printf("found the element, position is %d\n",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("\nOK\n"); printf("\nPrint Sqlist:\n"); PrintList_sq(&sl); } else printf("\nERROR!"); break; 。