数据结构–顺序表的c语言实现（超详细注释/实验报告）
知识小回顾
线性表是一种最基本、最常用的数据结构，它有两种存储结构——顺序表和链表。顺序表是由地址连续的的向量实现的，便于实现随机访问。顺序表进行插入和删除运算时，平均需要移动表中大约一半的数据元素，容量难以扩充。
实验题目
实现顺序表各种基本运算
实验目的
- 熟悉将算法转换为程序代码的过程；
- 了解顺序表的逻辑结构特性，熟练掌握顺序表存储结构的C语言描述方法；
- 熟练掌握顺序表的基本运算：查找、插入、删除等，掌握顺序表的随机存取特性。
实验要求
- 以顺序表作为存储结构；
- 实现顺序表上的数据元素的插入运算；
- 实现顺序表上的数据元素的删除运算；
- 实现顺序表上的数据元素的查找运算。
实验内容和实验步骤
1.需求分析
以菜单的形式作为用户与程序的接口，用户输入菜单号来实行相应的操作。
2. 概要设计
设计几个函数来实现初始化、插入、删除和查找的功能，然后再主函数中调用函数来实现操作。
3. 详细设计
导入一些库，并定义表的大小以及表中元素的类型。
#include<stdio.h>
#include<stdlib.h>
//#include<malloc.h>
//定义表的大小
#define MaxSize 20
//用typedef 给int定义个名字为ElemType，意思是表中元素的type
typedef int ElemType;
线性表的顺序存储结构借助于高级程序设计语言中的一维数组来表示，一维数组的下表与元素再线性表中的序号相对应。
//顺序表结构定义，包括了表的长度和一个数组
typedef struct Seqlist
{
ElemType elem[MaxSize];
int length;
}SeqList;
将线性表L初始化为空表，即长度length为0.
//定义顺序表初始化函数
int Init_SeqList(SeqList *L)
{
L->length=0; //设置长度为0，空表
//printf("%d",L->length);
return 1;
}
返回输入元素的位置
//定义查找某个元素位置的函数
int Locate_SeqList(SeqList *L,int x)
{
int i=0;
//从第0个开始到最后结束，结束条件是①索引到了length了②在表中找到值与输入的值相等了
for(i=0;i<L->length&&L->elem[i]!=x;i++)
{
;;
}
/* while(i<L->length&&L->elem[i]!=x)
i++;*/
//结束循环，第一种情况
if(i>=L->length)
{
printf("顺序表中不存在该元素！\n");
return 0;
}
//第二种情况，因为这是数组，所以返回的序数应该加1
else
return i+1;
}
定义插入顺序表的函数：在第i个元素之前插入。
在写的时候要注意：对用户来说第1个是数组的第0个。
//定义插入顺序表的函数：在第i个元素之前插入x
//注意：对用户来说第1个是数组的第0个
int Insert_SeqList(SeqList *L,int i,int x)
{
int j;
//printf("MaxSize\n");
//printf("%d",MaxSize);
//printf("%d",L.length);
if(L->length>=MaxSize)
{
printf("顺序表已满，无法进行插入操作！");
return 0;
}
else if(i<=0||i>L->length+1)
{
printf("插入的位置不正确！");
return 0;
}
//从最后一个元素开始，一个一个地往后移一位，给要插入的元素留出空间
for(j=L->length-1;j>=i-1;j--)
{
L->elem[j+1]=L->elem[j];
}
//在第i个元素之前插入就是把从i开始的元素往后移，然后赋值给第i个元素，在数组中就是i-1了
L->elem[i-1]=x;
L->length++; //插入完之后数组长度+1
return 1;
}
删除顺序表元素函数，删除第i个元素。
//定义删除顺序表元素函数，删除第i个元素
int Delete_SeqList(SeqList *L,int i)
{
int j;
if((i<1)||(i>L->length))//和插入是一样的判断条件
{
printf("删除位置不正确！");
return 0;
}
//删除第i个元素就是从第i个元素开始一个一个地从后向前覆盖
for(j=i;j<L->length;j++)
{
L->elem[j-1]=L->elem[j];
}
L->length--;//数组长度-1
return 1;
}
显示线性表的函数。
//定义显示线性表的函数
int Display_SeqList(SeqList *L)
{
int i;
//一个一个地打印出来
for(i=0;i<L->length;i++)
{
printf("%d",L->elem[i]);
//return 1; 严重错误，其实插入也已经插入了，只是显示出来1个 (之前的一个小bug)
}
return 1;
}
主函数部分，用一种“菜单”的形式使线性表的操作更加地清晰地展示出来。
int main()
{
SeqList L;
ElemType e,x;
int i=1,k,j,n,ii;
Init_SeqList(&L);
//printf("%d",Init_SeqList(&L));
//printf("初始化\n建立顺序表如下：");
//printf("%d",L.length);
//插入元素5201314
Insert_SeqList(&L,1,5);
Insert_SeqList(&L,2,2);
Insert_SeqList(&L,3,0);
Insert_SeqList(&L,4,1);
Insert_SeqList(&L,5,3);
Insert_SeqList(&L,6,1);
Insert_SeqList(&L,7,4);
//printf("\n");
while(i)//保证一直进行
{
printf("当前的顺序表如下： ");
Display_SeqList(&L);
printf("\n------------------------------------\n");
printf(" Main Menu \n");
printf(" 1 查找指定元素 \n");
printf(" 2 插入元素到指定位置 \n");
printf(" 3 删除某一指定位置元素 \n");
printf(" 4 清屏 \n");
printf(" 0 结束程序 \n");
printf("------------------------------------\n");
printf("请输入你选择的菜单号<1, 2, 3, 0>:\n");
scanf("%d",&i);
switch(i)
{
case 1:
printf("请输入查找元素：");
scanf("%d",&x);
j=Locate_SeqList(&L,x);
if(j!=0)//找到元素返回的是i+1,可以看看前面函数
{
printf("指定元素位置是 %d",j);
}
printf("\n\n");
break;
case 2:
printf("请输入插入元素位置：");
scanf("%d",&k);
printf("请输入插入元素值：");
scanf("%d",&x);
j=Insert_SeqList(&L,k,x);
if(j!=0)
{
printf("插入后顺序表如下显示：\n");
Display_SeqList(&L);
printf("\n");
}
printf("\n\n");
break;
case 3:
printf("请输入删除元素位置：");
scanf("%d",&k);
j=Delete_SeqList(&L,k);
if(j!=0)
{
printf("插入后顺序表如下显示：\n");
Display_SeqList(&L);
printf("\n");
}
printf("\n\n");
break;
case 4:
system("cls");
break;
case 0:
exit(0);
break;
default:
printf("输入有误~");
}
}
return 0;
}
}
4. 调试分析
遇到的问题及解决方法
- 实验指导书上给出的代码在code blocks环境下会报错，有的语句书写规范不一样。不过改正后就好了。
算法的时空分析
- 顺序表比较简单，都是依托着数组来实现的，值得改进的地方就是插入函数，用户自己来输入顺序表的元素会更好一些。
实验结果
实验结果很不错，所有操作都能正常执行，并且自己加入了“清屏”选项，使得界面更加的整洁。
实验总结
这是第一个数据结构的代码实现，主要还是跟着实验指导书上写，原创性不足，不过也学到了很多知识，也为之后的程序编写搭建了一个不错的框架！多多重复，百炼成钢！
最后附上完整的代码
#include<stdio.h>
#include<stdlib.h>
//#include<malloc.h>
//定义表的大小
#define MaxSize 20
//用typedef 给int定义个名字为ElemType，意思是表中元素的type
typedef int ElemType;
//顺序表结构定义，包括了表的长度和一个数组
typedef struct Seqlist
{
ElemType elem[MaxSize];
int length;
}SeqList;
//定义顺序表初始化函数
int Init_SeqList(SeqList *L)
{
L->length=0; //设置长度为0，空表
//printf("%d",L->length);
return 1;
}
//定义查找某个元素位置的函数
int Locate_SeqList(SeqList *L,int x)
{
int i=0;
//从第0个开始到最后结束，结束条件是①索引到了length了②在表中找到值与输入的值相等了
for(i=0;i<L->length&&L->elem[i]!=x;i++)
{
;;
}
/* while(i<L->length&&L->elem[i]!=x)
i++;*/
//结束循环，第一种情况
if(i>=L->length)
{
printf("顺序表中不存在该元素！\n");
return 0;
}
//第二种情况，因为这是数组，所以返回的序数应该加1
else
return i+1;
}
//定义插入顺序表的函数：在第i个元素之前插入x
//注意：对用户来说第1个是数组的第0个
int Insert_SeqList(SeqList *L,int i,int x)
{
int j;
//printf("MaxSize\n");
//printf("%d",MaxSize);
//printf("%d",L.length);
if(L->length>=MaxSize)
{
printf("顺序表已满，无法进行插入操作！");
return 0;
}
else if(i<=0||i>L->length+1)
{
printf("插入的位置不正确！");
return 0;
}
//从最后一个元素开始，一个一个地往后移一位，给要插入的元素留出空间
for(j=L->length-1;j>=i-1;j--)
{
L->elem[j+1]=L->elem[j];
}
//在第i个元素之前插入就是把从i开始的元素往后移，然后赋值给第i个元素，在数组中就是i-1了
L->elem[i-1]=x;
L->length++; //插入完之后数组长度+1
return 1;
}
//定义删除顺序表元素函数，删除第i个元素
int Delete_SeqList(SeqList *L,int i)
{
int j;
if((i<1)||(i>L->length))//和插入是一样的判断条件
{
printf("删除位置不正确！");
return 0;
}
//删除第i个元素就是从第i个元素开始一个一个地从后向前覆盖
for(j=i;j<L->length;j++)
{
L->elem[j-1]=L->elem[j];
}
L->length--;//数组长度-1
return 1;
}
//定义显示线性表的函数
int Display_SeqList(SeqList *L)
{
int i;
//一个一个地打印出来
for(i=0;i<L->length;i++)
{
printf("%d",L->elem[i]);
//return 1; 严重错误，其实插入也已经插入了，只是显示出来1个 (之前的一个小bug)
}
return 1;
}
int main()
{
SeqList L;
ElemType e,x;
int i=1,k,j,n,ii;
Init_SeqList(&L);
//printf("%d",Init_SeqList(&L));
//printf("初始化\n建立顺序表如下：");
//printf("%d",L.length);
//插入元素5201314
Insert_SeqList(&L,1,5);
Insert_SeqList(&L,2,2);
Insert_SeqList(&L,3,0);
Insert_SeqList(&L,4,1);
Insert_SeqList(&L,5,3);
Insert_SeqList(&L,6,1);
Insert_SeqList(&L,7,4);
//printf("\n");
while(i)//保证一直进行
{
printf("当前的顺序表如下： ");
Display_SeqList(&L);
printf("\n------------------------------------\n");
printf(" Main Menu \n");
printf(" 1 查找指定元素 \n");
printf(" 2 插入元素到指定位置 \n");
printf(" 3 删除某一指定位置元素 \n");
printf(" 4 清屏 \n");
printf(" 0 结束程序 \n");
printf("------------------------------------\n");
printf("请输入你选择的菜单号<1, 2, 3, 0>:\n");
scanf("%d",&i);
switch(i)
{
case 1:
printf("请输入查找元素：");
scanf("%d",&x);
j=Locate_SeqList(&L,x);
if(j!=0)//找到元素返回的是i+1,可以看看前面函数
{
printf("指定元素位置是 %d",j);
}
printf("\n\n");
break;
case 2:
printf("请输入插入元素位置：");
scanf("%d",&k);
printf("请输入插入元素值：");
scanf("%d",&x);
j=Insert_SeqList(&L,k,x);
if(j!=0)
{
printf("插入后顺序表如下显示：\n");
Display_SeqList(&L);
printf("\n");
}
printf("\n\n");
break;
case 3:
printf("请输入删除元素位置：");
scanf("%d",&k);
j=Delete_SeqList(&L,k);
if(j!=0)
{
printf("插入后顺序表如下显示：\n");
Display_SeqList(&L);
printf("\n");
}
printf("\n\n");
break;
case 4:
system("cls");
break;
case 0:
exit(0);
break;
default:
printf("输入有误~");
}
}
return 0;
}