c语言：顺序表基本操作

秒速五厘米 2022-05-26 23:25 190阅读 0赞

//*************************************************************************************************
    //                                   顺序表基本操作
    //该程序的功能是对元素类型为整型的顺序表进行一些操作。该程序包括顺序表结构类型的定义以及对顺序表
    //操作的具体的函数定义和主函数。
    //                                                      8/4/2018   1:15 ...史博辉
    //*************************************************************************************************
    #include <stdlib.h>         //C标准函数库的头文件，声明了数值与字符串转换函数，伪随机数
                                //生成函数，动态内存分配函数，进程控制函数等公共函数。
    
    #include <stdio.h>          //标准输入输出函数
    typedef int ElemType;       //给int换个新名字ElemType
    
    struct LinearList		    //定义一个结构体类型struct LinearList，LinearList为结构体名。
    {						    //成员表列
    	ElemType* list;
    	int size;
    	int MaxSize;          
    };                        
    						  
    void InitList(LinearList &L,int ms);      //线性表初始化，第一个参数为结构体变量L的引用，也就是L
                                              //的地址，第二个参数为线性表大小ms，也就是元素个数
    void ClearList(LinearList &L);            //清空线性表，形参为结构体变量L的引用
    int ListSize(LinearList &L);              //求线性表长度，形参为结构体变量L的引用
    bool ListEmpty(LinearList &L);            //判断线性表是否空，形参为结构体变量L的引用
    bool ListFull(LinearList &L);             //判断线性表是否满，形参为结构体变量L的引用
    void TravelList(LinearList &L);           //遍历线性表，形参为结构体变量L的引用
    bool FindList(LinearList &L,ElemType &m); //判断是否能在线性表中找到要查找的元素
    bool InsertList(LinearList &L,const ElemType &m,int mark);
                                              //判断是否能够插入元素
    bool DeleteList(LinearList &L,ElemType &item,int mark);
                                              //判断是否能够删除元素
    void OrderOutputList(LinearList &L,int mark);
                                              //对线性表进行有序输出
    
    void InitList(LinearList &L,int ms)
    {
    	L.list = new ElemType[ms];            //用new运算符开辟一个ElemType类型的数组空间（大小为ms），
    	                                      //将返回该空间的地址赋给指针变量L.list
    	if(!L.list)                           //判断是否分配成功
    	{
    		printf("初始化失败!\n");
    		exit(1);
    	}
    	L.size = 0;
    	L.MaxSize = ms;
    }
    
    void ClearList(LinearList &L)
    {
    	L.size = 0;                            //置L.size为0。
    	printf("线性表已清空！\n");
    }
    
    int ListSize(LinearList &L)
    {
    	return L.size;                         //返回一个int类型的L.size的值
    }
    
    bool ListEmpty(LinearList &L)
    {
    	return L.size == 0;                    //返回一个bool类型，如果L.size为0，返回true，
    	                                       //否则返回false
    }
    
    bool ListFull(LinearList &L)
    {
    	return L.size == L.MaxSize;            //如果L.size = L.MaxSize，返回true，否则返回false
    }
    
    void TraverList(LinearList &L)
    {
    	for(int i=0;i<L.size;i++)
    		printf("%d ",L.list[i]);           //遍历线性表L
    	printf("\n");
    }
    
    bool FindList(LinearList &L,ElemType &item)
    {
    	for(int i=0;i<L.size;i++)
    	{
    		if(L.list[i]==item)
    		{
    			item = L.list[i];               //找到item并将其赋值。
    			return true;
    		}	
    	}
    	return false;
    }
    
    bool InsertList(LinearList &L,const ElemType &item,int mark)
    {
    	int i,j;
    	if(ListFull(L))
    		return false;
    	if(mark > 0)
    	{
    		for(i=L.size-1;i>=0;i--)
    			L.list[i+1]=L.list[i];           //表中元素依次后移一位
    		L.list[0]=item;                      //表头插入元素
    	}
    	else if(mark < 0)
    		L.list[L.size]=item;                 //表尾插入元素
    	else
    	{
    		for(i=0;i<L.size;i++)
    			if(item<L.list[i])               //在一个比item大的数前面的位置i中插入
    				break;
    		for(j=L.size-1;j>=i;j--)
    			L.list[j+1] = L.list[j];         //把i位置空出来（i位置以及后面的元素后移）
    		L.list[i] = item;
    	}
    	L.size++;
    	return true;
    }
    
    bool DeleteList(LinearList &L,ElemType &item,int mark)
    {
    	int i,j; 
    	if(ListEmpty(L))                         //判断线性表是否为空
    		return false;
    	if(mark > 0)
    	{
    		item = L.list[0];                    //取出表头元素
    		for(i=0;i<L.size-1;i++)
    			L.list[i] = L.list[i+1];         //后面元素依次前移
    	}
    	else if(mark < 0)
    		item = L.list[L.size-1];             //取出表尾元素
    	else
    	{
    		for(i=0;i<L.size;i++)
    			if(L.list[i]==item)
    			{
    				item = L.list[i];            //取出值为item的元素，并找到其位置为i
    				break;
    			}
    		if(i>=L.size)                        //判断是否未找到与item相同的值
    			return false;
    		for(j=i;j<L.size-1;j++)
    			L.list[j] = L.list[j+1];         //i后面的元素依次前移
    	}
    	L.size--;
    	return true;
    }
    
    void OrderOutputList(LinearList &L,int mark)
    {
    	int *b = new int[L.size];                //开辟一个存放整数的数组（大小为L.size），并将
    	                                         //返回的地址赋给指针变量b。
    	int i,j,k;
    	for(i=0;i<L.size;i++)
    		b[i] = i;                            //给数组b各元素赋值（数组L.list的下标）。
    	for(i=1;i<L.size;i++)
    	{
    		k=i-1;
    		for(j=i;j<L.size;j++)           
    		{                        
    			if(mark == 1 && L.list[b[j]]<L.list[b[k]])
    				k=j;                         //如果mark为1则决定按升序排序
    			if(mark != 1 && L.list[b[k]]<L.list[b[j]])
    				k=j;                         //如果mark非1则决定按降序排序
    		}
    		if(k!=i-1)                           //如果i-1不是最大/小值的下标
    		{                                    //交换b[k]和b[i-1]
    			int x=b[i-1];
    			b[i-1]=b[k];
    			b[k]=x;
    		}
    	}
    	for(i=0;i<L.size;i++)
    		printf("%d ",L.list[b[i]]);          //直接根据排好元素的下标输出
    	printf("\n");
    }
    
    void main()
    {
    	printf("* * * * * * * * * * * * * * * * * * * * * *\n");
    	printf("* 1.线性表初始化                          *\n");
    	printf("* 2.清空线性表                            *\n");
    	printf("* 3.求线性表长度                          *\n");
    	printf("* 4.判断线性表是否空                      *\n");
    	printf("* 5.判断线性表是否满                      *\n");
    	printf("* 6.遍历线性表                            *\n");
    	printf("* 7.从线性表中查找元素                    *\n");
    	printf("* 8.先线性表中插入元素                    *\n");
    	printf("* 9.从线性表中删除元素                    *\n");
    	printf("* 0.线性表升序/降序遍历                   *\n");
    	printf("* * * * * * * * * * * * * * * * * * * * * *\n");
    	int a,b,c;
    	b=0;
    	c=0;
    	LinearList L;
    	printf("请选择操作：\n");
    	scanf("%d",&a);
    	while(a>=0 && a<=9)
    	{
    		switch(a)
    		{
    		case 1:
    			printf("请输入线性表长度：");
    			scanf("%d",&b);
    			InitList(L,b);
    			printf("请输入%d个线性表元素：",b);
    			for(c=0;c<b;c++)
    			{
    				int h;
    				scanf("%d",&h);
    				InsertList(L,h,-1);
    			}
    			printf("初始化完毕！\n");
    			break;
    		case 2:
    			ClearList(L);
    			break;
    		case 3:
    			b=ListSize(L);
    			printf("线性表长度为：%d\n",b);
    			break;
    		case 4:
    			if(ListEmpty(L))
    				printf("线性表为空！\n");
    			else
    				printf("线性表非空！\n");
    			break;
    		case 5:
    			if(ListFull(L))
    				printf("线性表已满！\n");
    			else
    				printf("线性表未满！\n");
    			break;
    		case 6:
    			printf("遍历结果：");
    			TraverList(L);
    			break;
    		case 7:
    			printf("请输入想要查找的元素：");
    			scanf("%d",&b);
    			if(FindList(L,b))
    				printf("查找成功！\n");
    			else
    				printf("查找失败！\n");
    			break;
    		case 8:
    			printf("请输入要插入的元素和位置，表头请输1，表尾请输-1，有序请输0：");
    			scanf("%d%d",&b,&c);
    			if(InsertList(L,b,c))
    				printf("插入成功！\n");
    			else
    				printf("插入失败！\n");
    			break;
    		case 9:
    			printf("请输入要删除的元素和位置，表头请输1，表尾请输-1，删除此元素请输0：");
    			scanf("%d%d",&b,&c);
    			if(DeleteList(L,b,c))
    				printf("删除成功！\n");
    			else
    				printf("删除失败！\n");
    			break;
    		default:
    			printf("升序请输1，降序请输-1：");
    			scanf("%d",&b);
    			if(b==1)
    			{
    				printf("升序排序为：");
    				OrderOutputList(L,b);
    			}
    			else if(b==-1)
    			{
    				printf("降序排序为：");
    				OrderOutputList(L,b);
    			}
    			else
    				printf("error!\n");
    		}
    		scanf("%d",&a);
    	}
    	if(a<0 || a>9)
    		printf("error!\n");
    }

1.线性表初始化：

在这里我用了自定义函数InitList(Linear &L,ElemType ms);和函数InsertList(LinearList &L,const ElemType &item,int mark);

在第一函数里，我用new来分配一个数组空间并将返回数组的起始地址赋给L.list。

接着，在第二个函数中，我用mark作为标记，控制要插入元素的位置，因为是初始化所以我选择在表尾插入（InsertList(L,h,-1)这一句）。而形参&item被const修饰为常指针，是防止在程序执行期间&item指向其他位置（即&item总是指向最后一个插入的元素），这样在函数再次调用时就知道&item在哪。

2.线性表清空：

这里使用L.size = 0; 这样线性表虽然存在，但是无法显示出线性表元素，因为后面的操作都依赖于L.size，它就像开关一样。

3.求线性表长度：

直接返回 L.size 的值，再用一个整型变量接收。

4.判断线性表是否为空：

即判断L.size是否为0。

5.判断线性表是否为满：

即判断L.size是否与最大空间L.MaxSize相等。

6.遍历线性表：

直接按下标输出即可。

7.线性表中查找元素：

bool类型，若返回true，则查找成功，否则失败。