实验一 顺序表的基本操作1
- 格式：doc
- 大小：170.00 KB
- 文档页数：8
实验一：顺序表的基本操作一、实验目的1．掌握线性表的顺序存储结构的表示和实现方法。
2．掌握顺序表基本操作的算法实现。
3．了解顺序表的应用。
二、实验环境硬件环境要求：PC 机（单机）使用的软件名称、版本号以及模块：Visual C++ 6.0 或 Turbo C 或 Win-TC 等。
三、实验内容编写一个程序，实现顺序表的各种基本运算（假设顺序表的元素类型为 char），并在此基础上设计一个主程序完成如下功能：（1）初始化顺序表L;（2）依次采用尾插法插入a、b、c、d、e元素;（3）输出顺序表L;（4）输出顺序表L的长度；（5）判断顺序表L是否为空；（6）输出顺序表L的第3个元素；（7）输出元素a的位置；（8）在第4个元素位置上插入f元素；（9）输出顺序表L；（10）删除L的第3个元素；（11）输出顺序表L；（12）释放顺序表L;四、实验要求1、用 Visual C++ 6.0 或 Turbo C 或 Win-TC 工具创建文件或程序，输入代码后，进行编译运行或在控制台执行。
2、观看程序运行结果，并根据结果进行思考，对程序进行修改和总结。
3、请在实验报告上写上实验要求、规范的程序代码、运行结果和你的总结体会。
【核心算法提示】1．顺序表插入操作的基本步骤：要在顺序表中的第 i 个数据元素之前插入一个数据元素 x，首先要判断插入位置 i 是否合法，假设线性表的表长为 n，则 i 的合法值范围：1≤i≤n+1，若是合法位置，就再判断顺序表是否满，如果满，则增加空间或结束操作，如果不满，则将第 i 个数据元素及其之后的所有数据元素都后移一个位置，此时第 i 个位置已经腾空，再将待插入的数据元素 x 插入到该位置上，最后将线性表的表长增加 1。
2．顺序表删除操作的基本步骤：要删除顺序表中的第 i 个数据元素，首先仍然要判断i 的合法性，i 的合法范围是1≤i≤n，若是合法位置，则将第i 个数据元素之后的所有数据元素都前移一个位置，最后将线性表的表长减 1。
3．顺序表查找操作的基本步骤：要在顺序表中查找一个给定值的数据元素，则可以采用顺序查找的方法，从顺序表中第1 个数据元素开始依次将数据元素值与给定值进行比较，若相等则返回该数据元素在顺序表中的位置，否则返回 0 值。
【核心算法描述】线性表的动态分配顺序存储结构—C语言实现#define MaxSize 50 //存储空间的分配量Typedef char ElemType；Typedef struct{ElemType data[MaxSize];int length; //表长度（表中有多少个元素）}SqList;动态创建一个空顺序表的算法void InitList(SqList *&L) //初始化线性表{L=(SqList *)malloc(sizeof(SqList)); //分配存放线性表的空间L->length=0; //置空线性表长度为 0}线性表的插入：status Sqlist_insert(Sqlist &L,int i,Elemtype x)/*在顺序表 L 中第 i 个元素前插入新元素 x*/ { if (i<1||i>L.length+1) return ERROR; /*插入位置不正确则出错*/if (L.length>=MAXLEN) return OVERFLOW;/*顺序表 L 中已放满元素，再做插入操作则溢出*/ for(j=L.length-1;j>=i-1;j--)L.elem[j+1]=L.elem[j];/*将第 i 个元素及后续元素位置向后移一位*/L.elem[i-1]=x; /*在第 i 个元素位置处插入新元素 x*/L.length++; /*顺序表 L 的长度加 1*/return OK;}线性表的删除：status Sqlist_delete(Sqlist &L,inti,Elemtype &e) /*在顺序表 L 中删除第 i 个元素*/{ if (i<1||i>L.length)return ERROR; /*删除位置不正确则出错*/for(j=i;j<=L.length-1;j++)L.elem[j-1]=L.elem[j]; /*将第 i+1 个元素及后继元素位置向前移一位*/ L.length--; /*顺序表 L 的长度减 1*/return OK；}线性表元素的查找：int LocateElem(SqList *L, ElemType e) //按元素值查找{int i=0;while (i<L->length && L->data[i]!=e)i++; //查找元素 eif (i>=L->length) //未找到时返回 0return 0;elsereturn i+1; //找到后返回其逻辑序号}输出线性表：void DispList(SqList *L) //输出线性表{int i;if (ListEmpty(L))return; for (i=0;i<L->length;i++)printf("%c ",L->data[i]); printf("\n");}输出线性表第 i 个元素的值：bool GetElem(SqList *L,int i,ElemType &e) //求线性表中某个数据元素值{if (i<1 || i>L->length)return false; //参数错误时返回 falsee=L->data[i-1]; //取元素值return true; //成功找到元素时返回 true}规范的程序代码；#include<stdio.h>#define MAXLEN 30typedef struct {int elem[MAXLEN];int length; }Sqlist;void Create(Sqlist &L)//创建 {int n,i=0;printf("请输入线性表元素个数（小于30）\n");while(scanf("%d",&n)&&n>30||n<0){printf("数据不合法，请重新输入\n");}printf("请输入%d个数，用空格分开\n",n);while(n--) {scanf("%d",&L.elem[i]); i++; L.length++;}}void Show(Sqlist L)//显示{printf("当前顺序表中元素有:\t");for(int i=0;i<L.length;i++){printf("%d ",L.elem[i]);}printf("\n"); } int Insert(Sqlist &L,int i,int x)//插入 {int key=1; if (i<1||i>L.length+1){ printf("插入位置不正确\n");key=0; return key;}for(int j=L.length-1;j>=i-1;j--)L.elem[j+1]=L.elem[j];L.elem[i-1]=x;L.length++; return key;}int Delete(Sqlist &L,int i)//删除{int key=1;if (i<1||i>L.length){printf("删除位置不正确\n");key=0; return key;}for(int j=i;j<=L.length-1;j++)L.elem[j-1]=L.elem[j];L.length--; return key;}int Search(Sqlist L,int e)//查找{int i,key=1;for (i=0;i<L.length&&L.elem[i]!=e;i++);if (i<L.length) { printf("查找成功，%d在",e);for(;i<L.length;++i)if(e==L.elem[i]) printf("第%d",i+1);printf("的位置\n");return key;}else {printf("查找失败\n");key=0;return key;}}void DelSqlist(Sqlist &L)//去重{int i,j,temp;for (j=0;j<L.length;j++)for (i=0;i<L.length-1-j;i++){ if(L.elem[i]>L.elem[i+1]){ temp=L.elem[i];L.elem[i]=L.elem[i+1];M.elem[i+1]=temp;}}i=0; while(i<L.length-1)if (L.elem[i]==L.elem[i+1]){for (j=i+1;j<L.length;j++)L.elem[j-1]=L.elem[j]; L.length--;}else i++;}int main() {int i,x,e,slect,key;Sqlist L;length=0; Create(L);Show(L);printf("请选择操作:\t 1.插入元素\t2.删除元素\t3.查找元素\t4.删除重复元素\n"); while(~scanf("%d",&slect)){key=0;switch (slect) {case 1:if (L.length>=MAXLEN) {printf("顺序表中已放满元素，无法插入新元素\n");break;}while(key==0){printf("请输入要插到的位置和元素值\n");scanf("%d%d",&i,&x); key=Insert(L,i,x);Show(L);}break;case 2:while(key==0){printf("请输入要删除的位置\n");scanf("%d",&i);key=Delete(L,i); Show(L);}break;case 3: while(key==0){printf("请输入要查找的元素\n");scanf("%d",&e); key=Search(L,e);}break;case 4:DelSqlist(L);Show(L);break;default:printf("输入错误，请重新输入\n"); break; } printf("请选择操作:\t 1.插入\t2.删除\t3.查找\t4.删除重复元素\n"); } }运行结果：总结体会1.考虑问题要全面，尽可能增强程序的健壮性；2.将程序模块化，能使其更加可读、易找错、易修改；3.函数和变量的命名要能一眼看出来它的意思；4.错误很多，调试很烦，要有耐心。
