【数据结构】线性表顺序存储（合并非递减表）代码实现c语言

雨点打透心脏的1/2处 2021-09-20 14:28 350阅读 0赞

虽然是c语言的语法，但事实是需要用c++的(&符)，来表示引用与返回e值的效果

运行效果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyMjA5Mw_size_16_color_FFFFFF_t_70]  
下面是源代码

#include <stdio.h>
    #include <malloc.h>
    #include <iostream>
    #define LIST_INIT_SIZE 100 //线性表存储空间的初始量分配
    #define LISTINCREMENT 10 //线性表存储空间的分配量
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -1
    
    typedef float ElemType;
    typedef int Status;
    typedef struct{ 
    	ElemType *elem;//存储空间基址 
    	Status length;//当前长度
    	Status listsize;//当前分配的存储容量 
    }SqList;
    
    //函数原型
    Status InitList_Sq(SqList &L);
     
    //初始化空表
    Status InitList_Sq(SqList &L){ 
    	L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    	//判断内存是否分配失败 
    	if(!L.elem)
    	{ 
    		exit(OVERFLOW);
    	}
    	L.length=0;//空表的长度为零 
    	L.listsize=LIST_INIT_SIZE;//初始存储容量 
    	return OK; 
    } 
    //在第i个元素之前插如一个数e 
    Status ListInsert_Sq(SqList &L,Status i,ElemType e){ 
    	ElemType *newbase,*p,*q;
    	//判断i值是否合法 
    	if(i<1||i>L.length)
    	{ 
    		return ERROR;
    	}
    	//判断存储空间是否已满 
    	if(L.length>=L.listsize)
    	{ 
    		newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
    		//判断是否重新分配成功 
    		if(!newbase)
    		{ 
    			exit(OVERFLOW);
    		}
    		L.elem=newbase;
    		L.listsize+=LISTINCREMENT;
    	}
    	//q为插入位置 
    	q=&(L.elem[i-1]);
    	for(p=&(L.elem[L.length-1]);p>=q;--p)
    	{ 
    		*(p+1)=*p;//插入位置及之后的元素右移
    	} 
    	*q=e;
    	L.length++;
    	return OK; 
    }
    
    //删除第i个数,并用e返回其值 
    Status ListDelete_Sq(SqList &L,Status i,ElemType &e){ 
    	ElemType *p,*q; 
    	//在顺序表中删除第i个元素并用e返回结果
    	if(i<1||i>L.length)//判断i值是否合法 
    	{ 
    		return ERROR;
    	} 
    	p = &(L.elem[i-1]);//p为删除的位置 
    	e = *p;//把删除的元素的值给e 
    	q = L.elem+L.length-1; //表尾元素的位置
    	for(++p;p<=q;++p)
    	{ 
    		*(p-1)=*p;//被删除的元素之后左移 
    	}
    	L.length--;
    	return OK;
    } 
    
    //查找元素，返回其位序，没找到返回0
    Status LocateElem_Sq(SqList L,ElemType e){ 
    	//在顺序表中查询第一个满足判定条件的数据元素
    	//若元素存在则返回它的位序，否则则返回0
    	int i=1;
    	//i的初始值为第一个元素的位序
    	while(i<=L.length&&L.elem[i-1]!=e)
    	{ 
    		i++;
    	}
    	if(i<=L.length)
    	{ 
    		return i;
    	}
    	else
    	{  	
    		return 0;
    	}
    } 
    
    //对两表进行有序合并
    void MergeList_Sq(SqList La,SqList Lb,SqList &Lc){ 
    	ElemType *pa,*pb,*pc,*pa_last,*pb_last;
    	//已知表ab都是非递减序列
    	//归并ab量表为c，c表也是非递减
    	pa=La.elem;
    	pb=Lb.elem;
    	Lc.listsize=Lc.length=La.length+Lb.length;
    	pc=Lc.elem=(ElemType *)malloc(Lc.listsize*sizeof(ElemType));
    	if(!Lc.elem)//判断是否分配失败 
    	{ 
    		exit(OVERFLOW); 
    	}
    	pa_last=La.elem+La.length-1;
    	pb_last=Lb.elem+Lb.length-1;
    	while((pa<=pa_last)&&(pb<=pb_last))
    	{ 
    		if(*pa<=*pb)
    		{ 
    			*pc++=*pa++;
    		}
    		else
    		{ 
    			*pc++=*pb++;
    		}
    	}
    	while(pa<=pa_last)//将a中剩余的元素复制到c中 
    	{ 
    		*pc++=*pa++;
    	}
    	while(pb<=pb_last)//将b中剩余的元素复制到c中 
    	{ 
    		*pc++=*pb++;
    	} 
    } 
    int main(void){  
    	printf(" |$$$线性表的顺序存储\n");
    	printf(" |本程序有以下几种功能：\n");
    	printf(" |1.创建顺序表\n");
    	printf(" |2.顺序表插入\n");
    	printf(" |3.顺序表删除\n");
    	printf(" |4.顺序表查找\n");
    	printf(" |5.合并两个非递减顺序表\n\n\n\n");
    	
    	SqList La,Lb,Lc;//定义3个表
    	ElemType e;
    	int i=0,a,b;
    	
    	//初始化空表
    	InitList_Sq(La);
    	InitList_Sq(Lb);
    	InitList_Sq(Lc);
    	
    	//给a表和b表赋值
    	printf("请输入你想在a表中输入的元素的个数：\n"); 
    	scanf("%d",&a);
    	La.length=a;
    	for(i=0;i<a;i++)
    	{ 
    		scanf("%f",&La.elem[i]);
    	}
    	printf("请输入你想在b表中输入的元素的个数：\n"); 
    	scanf("%d",&b);
    	Lb.length=b;
    	for(i=0;i<b;i++)
    	{ 
    		scanf("%f",&Lb.elem[i]);
    	}
    	
    	//插入元素
    	printf("请输入你想在a表插入的元素位置和元素:\n");
    	scanf("%d%f",&i,&e); 
    	ListInsert_Sq(La,i,e);
    	printf("此时的a表为：");
    	for(i=0;i<La.length;i++)
    	{ 
    		printf("%4.2f ",La.elem[i]);
    	}
    	printf("\n"); 
    	
    	//删除元素
    	printf("请输入你想在b表删除的元素位置:\n");	 
    	scanf("%d",&i); 
    	ListDelete_Sq(Lb,i,e);
    	for(i=0;i<Lb.length;i++)
    	{ 
    		printf("%4.2f ",Lb.elem[i]);
    	}
    	printf("\n");
    	printf("删除的元素为%f:\n",e);
    	
    	//查找元素 
    	printf("请输入要在a表中找到的元素：\n");
    	scanf("%f",&e); 
    	i=LocateElem_Sq(La,e);
    	printf("元素的位置为%d\n",i);
    	printf("\n");
    	
    	//对ab两表进行有序合并
    	MergeList_Sq(La,Lb,Lc);
    	printf("合成之后的c表为:\n");
    	for(i=0;i<Lc.length;i++)
    	{ 	
    		printf("%4.2f ",Lc.elem[i]);	
    	}
    	return 0; 
    }

吾王美滋滋！！！  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyMjA5Mw_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyMjA5Mw_size_16_color_FFFFFF_t_70]: /images/20210920/e6c138087b1743ae99601d28f5755f4f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyMjA5Mw_size_16_color_FFFFFF_t_70 1]: /images/20210920/80923729be2a42478731a46e6f692030.png