【数据结构】线性表的顺序存储结构（c语言实现）

心已赠人 2021-11-27 01:46 387阅读 0赞

最近在复习数据结构，参考资料为王道数据结构  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]

/*********************************************************/
    
    /*
        Project: sequence_list(数据结构-顺序表) 
        Date:    2019/07/22
        Author:  CWS
    	CreatList(SqList &L,int n) 参数：顺序表L，顺序表长度n 功能：创建长度为的顺序表 时间复杂度：O(n)
    	InitList(SqList &L) 参数：顺序表L 功能：初始化 时间复杂度:O(1)
    	InsertList(SqList &L,int i,ElemType e) 参数:顺序表L,位置i,元素e 功能：位置i处插入元素e 时间复杂度:O(n)
    	ListDelete(SqList &L,int i) 参数:顺序表L,位置i 功能：删除位置i处元素 时间复杂度:O(n)
    	LocateElem(SqList L,ElemType e) 参数:顺序表L,元素e 功能：返回第一个等于e的元素的位置 时间复杂度:O(n)
    	PrintList(SqList L) 参数:顺序表L 功能：遍历L，并输出
    */
    
    #include<stdio.h>
    #include<string.h>
    #define MaxSize 100  //定义线性表的最大长度
    #define ElemType int //假定表中元素类型是int
    #define Status int
    
    //定义一个结构体，表示了顺序表的类型
    //数组是静态分配的（大小固定）
    typedef struct
    {
    	ElemType data[MaxSize];  //顺序表的元素（开辟int类型的数组，数组名叫data，数组名就是数组的起始位置，数组大小就是MaxSize）
    	int length;				 //顺序表的当前长度
    }SqList;					 //顺序表的类型定义
    
    
    //*******基本操作函数*********//
    
    //初始化顺序表函数，构造一个空的顺序表
    Status InitList(SqList &L)
    {
    	
    	memset(L.data,0,sizeof(L));  //初始化数据为0
    	L.length=0;
    	return 0;
    }
    
    //创建顺序表函数 初始化前n个数据
    bool CreatList(SqList &L,int n)
    {
    	if(n<0||n>MaxSize)
    		return false; //非法
    	for(int i=0;i<n;i++)
    	{
    		scanf("%d",&L.data[i]);
    		L.length++;
    	}
    	return true;
    }
    
    //插入  顺序表插入算法的平均时间复杂度为O(n)
    /*
    算法流程：
    在顺序表L的第i(1<=i<=length+1 )个位置插入新元素e，如果i的输入不合法，则返回false，表示插入失败；
    否则，将顺序表的第i个元素以及其后的所有元素向右移一个位置，腾出一个空位置插入新元素e，顺序表长度增加1，插入成功，返回true
    
     算法思路：
    1.判断i的值是否正确
    2.判断表长是否超过数组长度
    3.从后向前到第i个位置，分别将这些元素都向后移动一位
      
    返回类型 函数名 参数列表(&L 带引用符号& 因为要对这个表进行修改)
    */
    
    bool InsertList(SqList &L,int i,ElemType e)
    {
    	if(i<1||i>L.length+1)		//判断i的范围是否有效
    	{
    		printf("位置无效！\n");
    		return false;
    	}
    	if(L.length>=MaxSize)		//当前存储空间已满，不能插入
    	{
    		printf("当前存储空间已满！！！\n");
    		return false;
    	}
    	//表中最后一个元素的下标是length-1，再后一位是length			
    	for(int j=L.length;j>=i;j--)
    		L.data[j]=L.data[j-1];
    	L.data[i-1]=e;				//在位置i处放入e
    	L.length++;					//线性表长度加1
    	return true;
    }
    
    //删除
    /*
    算法流程：
    删除顺序表L中第i(1<=i<=L.length)个位置的元素，成功则返回true,否则返回false
    算法思路：
    1.判断i的值是否正确
    2.取删除的元素
    3.将被删元素后面的所有元素都依次向前移动一位  
    4.修改表长
    */
    bool ListDelete(SqList &L,int i)
    {
    	if(i<1||i>L.length)
    	{
    		printf("位置无效！");
    		return false;
    	}
    	for(int j=i;j<=L.length-1;j++)
    	{
    		L.data[j-1]=L.data[j];
    	}
    	L.length--;
    	return true;
    }
    //查找函数
    int LocateElem(SqList &L,ElemType e)
    {
    	for(int i=0;i<L.length;i++) //从低位置查找
    	{
    		if(e==L.data[i]) 
    			return i+1;			//下标为i的元素值等于e，返回其位序i+1
    	}
    	return 0;					//退出循环，说明查找失败
    }
    
    //*******功能函数**********//
    
    //输出功能函数，按位置从小到大输出顺序表所有元素
    void PrintList(SqList L)
    {
    	printf("当前顺序表所有元素:");
    	for(int i=0;i<L.length;i++)
    	{
    		printf("%d ",L.data[i]);		//依次输出
    	}
    	printf("\n");
    }
    
    //创建顺序表函数
    void Create(SqList &L)
    {
    	int n;
    	bool flag;
    	printf("请输入要创建的顺序表长度(>1):");
    	scanf("%d",&n);
    	printf("请输入%d个数（空格隔开）:",n);
    	flag=CreatList(L,n);
    	if(flag){
    		printf("创建成功！\n");
    		PrintList(L);
    	}else 
    		printf("输入长度非法！\n");
    }
    
    //插入功能函数 调用InsertList完成顺序表元素插入 调用PrintList函数显示插入成功后的结果
    void Insert(SqList &L)
    {
    	int place;
    	ElemType e;
    	bool flag;
    	printf("请输入要插入的位置(从1开始)及元素:\n");
    	scanf("%d%d",&place,&e);
    	flag=InsertList(L,place,e);
    	if(flag)
    	{
    		printf("插入成功！\n");
    		PrintList(L);
    	}
    }
    
    //删除功能函数 调用ListDelete函数完成顺序表的删除 调用PrintList函数显示插入成功后的结果
    void Delete(SqList &L)
    {
    	int place;bool flag;
    	printf("请输入要删除的位置(从1开始):\n");
    	scanf("%d",&place);
    	flag=ListDelete(L,place);
    	if(flag)
    	{
    		printf("删除成功！！！\n");
    		PrintList(L);
    	}
    }
    
    //查找功能函数 调用LocateElem查找元素
    void Search(SqList L)
    {
    	ElemType e;int flag;
    	printf("请输入要查找的值：");
    	scanf("%d",&e);
    	flag=LocateElem(L,e);
    	if(flag){
    		printf("该元素位置为：%d\n",flag);
    	}else{
    		printf("未找到该元素！\n");
    	}
    }
    
    //菜单
    void menu()
    {
       printf("********1.创建    2.插入*********\n");
       printf("********3.删除    4.查找*********\n");
       printf("********5.输出    6.退出*********\n");
    }
    
    int main()
    {
    	
    	SqList L;
    	int choice;
    	InitList(L);	//初始化顺序表
    	while(1)
    	{
    		menu();
    		printf("请输入菜单序号：\n");
    		scanf("%d",&choice);
    		if(6==choice) break;	//退出
    		switch(choice)
    		{
    			case 1:
    				Create(L);		//创建
    				break;
    			case 2:
    				Insert(L);		//插入
    				break;
    			case 3:
    				Delete(L);		//删除
    				break;
    			case 4:
    				Search(L);		//查找
    				break;
    			case 5:
    				PrintList(L);	//输出
    				break;
    			default:
    				printf("输入错误！\n");
    
    		}
    
    	}
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]: /images/20211126/d815747effd7431c86f73d117b7ea851.png