数据结构实验报告-线性顺序表剖析.doc

《数据结构》 实验报告 学生姓名 学生班级 学生学号 指导老师 雷大江 实验内容 1) 建立一个线性顺序表，要求从键盘输入10个整数，并将该线性顺序表的元素从屏幕显示出来； 2) 编写查找函数，在上面的线性顺序表中查找其中一个元素，如果找到，返回该元素在线性顺序表中的位置和该元素的值，否则提示无此元素。要求被查找元素从键盘输入。 3) 编写插入和删除函数，由用户输入待插入元素及插入位置，将完成插入后的线性顺序表输出；由用户输入删除第几个元素，将完成删除后的线性顺序表输出。 需求分析 1)?、?从键盘输入10个整数，产生顺序表。? 2)?、?从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置； 若找不到，则显示“找不到”。? 3)?、?从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x 插入在对应位置上，输出顺序表所有结点值，观察输出结果。? 4)?、?从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出 结果。 三、概要设计 1）初始化操作：为顺序表分配一个预定义大小的数组空间，并将线性表的当前长度length设为0。?（2）清空操作：将顺序表的长度设为0，是表为空表?（3）销毁操作：将顺序表所占用的空间释放? （4）定位操作：根据给定的数据元素e，在顺序表中找出和e相等的数据元素的位序，如果这样的数据元 素不存在，则返回0? （5）插入操作：在顺序表的第i个数据元素前插入一个新的数据元素e，注意，在插入前必须判断i的值 域)1)(1(???LListLengthi ，而在插入操作后必须使顺序表的长度增1.? （6）删除操作：删除顺序表中第i个数据元素，并且用e返回其值。注意，在删除操作前必须判断i的值 域)1)(1(???LListLengthi ，而在删除操作后必须使顺序表的长度减1。? （7）输出操作：即将顺序表中各个元素按下标次序输出。 详细设计 源代码： #includeiostream using namespace std; #includestdlib.h #includemalloc.h #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int ElemType; #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { ElemType *elem; int length; int listsize; }SqList; Status InitList(SqList L){ //构造一个空的线性表L。 L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem)exit(OVERFLOW);//存储分配失败 L.length=0; //空表长度为0 L.listsize=LIST_INIT_SIZE;//初始存储容量 return OK; }//InitList_Sq Status ListInsert(SqList L,int i,ElemType e){ //在顺序线性表L中第i个位置之前插入新的元素e, //i的合法值为1=i=ListLength_Sq(L)+1 int *q,*p,*newbase; if(i1||iL.length+1)return ERROR;//i的位置不合法 if(L.length=L.listsize){ newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase)exit(OVERFLOW);//存储分配失败 L.elem=newbase; //新基址 L.listsize+=LISTINCREMENT;//增加存储容量 } q=(L.elem[i-1]); for(p=(L.elem[L.length-1]);p=q;--p)*(p+1)=*p; // 插入位置及之后的元素右移 *q=e; //插入e ++L.length; //表的长度增加1