4、利用线性表的顺序存储结构解决实际问题二、实验内容（一）验证实验1、定义顺序表类型typedef int datatype;typedef structdatatype elem[MAX];int Last,List,*SeqList,2、完成顺序表中的基本操作的实现初始化、插入、删除、求表长、按值查找、按位置查找。实验程序：#include<stdio.h>#include<stdlib.h>#define MAX 100typedef int datatype,typedef structdatatype elem[MAX];int Last,//定义顺序表类型List,*SeqList,1初始化顺序表SeqList InitList()SeqList L;L=(SeqList)malloc(sizeof(List));L->Last=-1;return L,2
2 4、利用线性表的顺序存储结构解决实际问题。 二、实验内容 （一）验证实验 1、定义顺序表类型 typedef int datatype; typedef struct { datatype elem[MAX]; int Last; }List,*SeqList; 2、完成顺序表中的基本操作的实现 初始化、插入、删除、求表长、按值查找、按位置查找。 实验程序： #include <stdio.h> #include<stdlib.h> #define MAX 100 typedef int datatype; typedef struct { datatype elem[MAX]; int Last; }List,*SeqList; //定义顺序表类型 SeqList InitList() //初始化顺序表 { SeqList L; L=(SeqList)malloc(sizeof(List)); L->Last=-1; return L; }
voidCreateList(SeqListL）//创建顺序表int i,n,printf("请输入你要创建的顺序表元素个数n=");scanf("%d",&n);printf("请输入你要创建的顺序表："),for(i=0;i<n;i++)1scanf("%d",&L->elem[i]);L->Last++;intLocation(SeqListL,datatypex）//查找某元素所在位置1int i=0,while(L->elem[i]!=x&&i<L->Last)i++;if(i>L->Last)return -1;elsereturn i,voidInsertelem(SeqListL,datatypem）1/插入元素int i,n,printf("请输入你要插入的位置n=");scanf("%d",&n);if(L->Last+1)>MAX)printf("表已满，不能插入");3
3 void CreateList(SeqList L) //创建顺序表 { int i,n; printf("请输入你要创建的顺序表元素个数 n= "); scanf("%d",&n); printf("请输入你要创建的顺序表:"); for(i=0;i<n;i++) { scanf("%d",&L->elem[i]); L->Last++; } } int Location(SeqList L,datatype x) //查找某元素所在位置 { int i=0; while(L->elem[i]!=x&&i<L->Last) i++; if(i>L->Last) return -1; else return i; } void Insertelem(SeqList L,datatype m) //插入元素 { int i,n; printf("请输入你要插入的位置 n="); scanf("%d",&n); if((L->Last+1)>MAX) printf("表已满,不能插入");
elseL->Last++;for(i=L->Last;i>=n-1;i--)L->elem[i+1]=L->elem[i];L->elem[n-1]=m;void Deleteelem(SeqList L,datatype m)/删除表中某元素int i.j;i=Location(L,m);while(i---1)datatype n;printf("你所查找的元素不在表中,请重新输入你要删除的元素")scanf("%d",&n),i=Location(L,n);for(j=ij<-L->Last:j++)L->elem[i]=L->elem[i+1];L->Last--;voidShowList(SeqListL）//显示当前顺序表( int i,printf("当前顺序表元素为：");for(i=0;i<=L->Last;i++)printf("%5d",L->elem[i]);4
4 else { L->Last++; for(i=L->Last;i>=n-1;i-) L->elem[i+1]=L->elem[i]; L->elem[n-1]=m; } } void Deleteelem(SeqList L,datatype m) //删除表中某元素 { int i,j; i=Location(L,m); while(i==-1) { datatype n; printf("你所查找的元素不在表中,请重新输入你要删除的元素"); scanf("%d",&n); i=Location(L,n); } for(j=i;j<=L->Last;j++) L->elem[j]=L->elem[j+1]; L->Last-; } void ShowList(SeqList L) //显示当前顺序表 { int i; printf("当前顺序表元素为:"); for(i=0;i<=L->Last;i++) printf("%5d",L->elem[i]);
/主函数void mainOint Opration;SeqList L,L=InitListO);CreateList(L);printf("输入操作：1为删除某元素2为插入某元素3为查找某元素4为输出当前顺序表5为退出n");while(Opration<=5)(scanf("%d",&Opration);if(Opration=-1)int n,printf("请输入你要删除的元素n=")scanf("%d",&n)Deleteelem(L,n);子if(Opration=--2)1int n;printf("请输入你要插入的元素n=");scanf("%d",&n),Insertelem(L,n);子if(Opration==3)datatype x,printf("请输入你要查找的元素x=");5
5 } void main() //主函数 { int Opration; SeqList L; L=InitList(); CreateList(L); printf("输入操作:1 为删除某元素 2 为插入某元素 3 为查找某元素 4 为输出当前 顺序表 5 为退出\n"); while(Opration<=5) {scanf("%d",&Opration); if(Opration==1) { int n; printf("请输入你要删除的元素 n="); scanf("%d",&n); Deleteelem(L,n); } if(Opration==2) { int n; printf("请输入你要插入的元素 n="); scanf("%d",&n); Insertelem(L,n); } if(Opration==3) { datatype x; printf("请输入你要查找的元素 x=");
scanf("%d",&x);printf("此元素在顺序表中的位置为%d\n:",Location(L,x)+1)7if(Opration==4)ShowList(L);if(Opration=--5)break;11（二）设计实验1、编写一个算法实现两个有序（从小到大）顺序表合并成为一个顺序表，合并后的结果放在第一个顺序表中，不另设新的顺序表存储（假设这两个有序顺序表中没有相同的元素）2、设有一个顺序表A，包含n个元素，要求写出一个将该表逆置的算法，并只允许在原表的存储空间外再增加一个附加的工作单元3、有一个已按递增次序排好序的线性表，今输入一个数，要求按原来的排序规律将它插入到线性表中。实验程序：1、文件名：sq.c#include<stdio.h>#define MaxLen 50typedef int elemtype;typedefelemtypesqlist[MaxLen];int create(sqlist A)1/创建顺序表1int i,n;printf("建立顺序表：");printf("输入元素个数：");scanf("%d",&n);6
6 scanf("%d",&x); printf("此元素在顺序表中的位置为%d\n:",Location(L,x)+1); } if(Opration==4) ShowList(L); if(Opration==5) break; } } （二）设计实验 1、编写一个算法实现两个有序（从小到大）顺序表合并成为一个顺序表，合并后 的结果放在第一个顺序表中，不另设新的顺序表存储（假设这两个有序顺序表中 没有相同的元素） 2、设有一个顺序表 A，包含 n 个元素，要求写出一个将该表逆置的算法， 并只允许在原表的存储空间外再增加一个附加的工作单元 3、有一个已按递增次序排好序的线性表，今输入一个数，要求按原来的排序规律 将它插入到线性表中。 实验程序： 1、文件名：sq.c #include<stdio.h> #define MaxLen 50 typedef int elemtype; typedef elemtype sqlist[MaxLen]; int create(sqlist A) //创建顺序表 { int i,n; printf("建立顺序表:"); printf("输入元素个数:"); scanf("%d",&n);