数据结构与算法实验报告 姓名：孙瑞霜
一、实验目的
1、复习线性表的逻辑结构、存储结构及基本操作；
2、掌握建立空的顺序表（代码3.1）、往顺序表中输入元素、输出顺序表中的元素、往顺序表中插入元素、从顺序表中删除元素等操作的实现。
二、实验要求：
1． 认真阅读和掌握教材上和本实验相关的内容和算法。
2． 上机将相关算法实现。
3． 实现上面实验目的要求的功能，并能进行简单的验证。
三、实验内容
1、#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
//顺序表的表示
typedef int ElementType;
typedef int Position;
typedef struct LNode * PtrToLNode;
struct LNode
{
ElementType Data[MAXSIZE];
Position last;
};
typedef PtrToLNode List;
/*顺序表操作的实现*/
List MakeEmpty()
{//创建空的顺序表
}
void Createlist(List L)
{//往顺序表中输入元素
int i,n;
printf("请输入要输入元素的个数：");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("请输入第%d个数",i+1);
scanf("%d",&(L->Data[i]));
}
L->last=n-1;
}
void Printlist(List L)
{//输出顺序表中的各个元素
}
Position Find(List L ,ElementType X)
{//在L表示的顺序表中查找X，不存在返回-1，存在返回其位置
}
bool Insert(List L ,ElementType X,int i)
{//在L表示的顺序表中第i位置插入X
}
bool Delete(List L, int i)
{//删除L表示的顺序表的第i元素
}
int main()
{
List L;
L=MakeEmpty();//创建空的顺序表，并让PtrL指向表示它的结构体变量
Createlist(L);//往顺序表中插入元素
Printlist(L);//输出该顺序表
/*
尝试调用其他子函数如插入删除后再输出看下效果
*/
return 0;
}
三、算法描述
该算法共涉及六个操作，分别是顺序表的建立，输出元素，查找，插入和删除指定位置的元素等操作。创建一个空的线性表，往表中输入元素。查找元素时，若找不到所给元素则返回ERROR,若找到则返回元素的存储位置；将X插入第i位置时，若空间已满，则打印“FULL”并返回false，不满则插入元素；将顺序表中位置i的元素删除时，若删除位序非法则返回false，否则正常进行删除操作。
四、详细设计
程序流程图如下：
五、程序代码
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
//顺序表的表示
typedef int ElementType;
typedef int Position;
typedef struct LNode * PtrToLNode;
struct LNode
{
ElementType Data[MAXSIZE];
Position last; // 保存线性表中最后一个元素的位置 */
};
typedef PtrToLNode List;
/*顺序表操作的实现*/
List MakeEmpty(){ //创建空的顺序表的操作
List L;
L = (List)malloc(sizeof(struct LNode)); //申请动态内存空间
L->last = -1;
return L;
}
void Createlist(List L){ //往顺序表中输入元素
int i,n;
printf("请输入要输入元素的个数：");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("请输入第%d个数:",i+1);
scanf("%d",&(L->Data[i]));
}
L->last=n-1;
}
void Printlist(List L) //输出顺序表中的各个元素
{
int i;
for(i=0;i<=L->last;i++)
printf("%d\n",L->Data[i]);
}
Position Find( List L, ElementType X )
{ //在L表示的顺序表中查找X的操作
Position i=0;
while(i<=L->last&&L->Data[i]!=X)
i++;
if(i>L->last)
return -1; //如果没找到，返回错误信息
else
return i; //若找到则返回存储位置
}
bool Insert(List L ,ElementType X,int i){ //在L表示的顺序表中第i位置插入X的操作
Position p;
if(L->last==MAXSIZE-1){ //表示空间已满，不能插入
printf("FULL");
return false;
}
if(i<1||i>L->last+2){ //检查插入位序的合法性是否在1~n+1之间
printf("位序不合法");
return false;
}
for(p = L->last; p >= i-1; p--)
L->Data[p+1] = L->Data[p];
L->Data[i-1] = X;
L->last++;
printf("\n");
Printlist(L); //Last仍指向最后元素
return true;
}
bool Delete(List L, int i){ //删除L表示的顺序表的第i元素的操作
Position p;
if(i<1||i>L->last+1){
return false;
}
for(p=i; p< L->last; p++){
L->Data[p-1] = L->Data[p]; //将元素向前移
}
L->last--;
printf("\n");
Printlist(L); //Last仍指向最后元素
return true;
}
int main()
{
List L;
L = MakeEmpty();//创建空的顺序表，并让PtrL指向表示它的结构体变量
Createlist(L);//往顺序表中插入元素
Printlist(L);//输出该顺序表
/*
尝试调用其他子函数如插入删除后再输出看下效果
*/
int N,X,W; //N为元素个数，X为元素，W为元素位置
printf("插入元素个数：");
scanf("%d", &N);
while ( N-- ) {
printf("插入元素及位置：");
scanf("%d %d", &X,&W);
if ( Insert(L,X,W)==false )
printf(" Insertion Error.");
}
/*此为插入操作的输入与输出*/
printf("查找元素个数：");
scanf("%d", &N);
while ( N-- ) {
printf("查找的元素：");
scanf("%d", &X);
W= Find(L, X);
if ( W == -1 )
printf("Finding Error: %d is not in.\n", X);
else
printf("%d is at position %d.\n", X, W);
}
/*查找操作的输入与输出*/
printf("删除元素个数:");
scanf("%d", &N);
while ( N-- ) {
printf("删除元素位置：");
scanf("%d", &W);
if ( Delete(L,W)==false )
printf(" Deletion Error.\n");
}
return 0;
}
/*删除操作的输入与输出*/
五、测试和结果
测试用例：1 2 3 4 5
七、用户手册
打开devC++，新建一个源程序，拷贝5部分的代码进去，点击运行，在出现的界面中按照提示输入数据，一步步按下回车键即可运行该程序，最后测试完毕，关闭界面。