学习线性表的顺序表

妖狐艹你老母 2022-07-14 09:43 174阅读 0赞

今天学了线性表的顺序表，了解了顺序表的含义，熟悉一下头插尾插的方法，通过一些插入方式，对顺序表的认识更加深入了一些。

#include <stdio.h>
    #include <stdlib.h>
    
    #define INIT_SIZE 100           //顺序表初始化大小
    #define INCESS_SIZE 20          //顺序表满后的每次扩充大小
    
    #define ok 0
    #define error -1
    #define mallc_error -2
    
    typedef int Elementtype;         //顺序表元素类型
    typedef struct _sqlist           
    {
    	Elementtype *list;           //指向顺序表的指针
    	int leng;                    //当前顺序表的长度
    	int max_len;                //顺序表的最大长度
    } Sqlist;                        //重命名结构体类型
    
    
    //初始化顺序表
    int Init_list(Sqlist *sqlist)
    {
    	if(sqlist == NULL)
    	{
    		return error;
    	}
    	
    	//创建顺序表空间
    	sqlist->list = (Elementtype*) malloc(INIT_SIZE*sizeof(Elementtype)/sizeof(char));
    	if(sqlist->list ==NULL)
    	{
    		return mallc_error;
    	}
    	
    	sqlist->leng = 0;
    	sqlist->max_len = INCESS_SIZE;
    	
    	return ok;
    }
    
    //扩充空间
    int Againmalloc(Sqlist *sqlist)
    {
    	if(sqlist == NULL)
    	{
    		return error;
    	}
    	
    	Elementtype *newbase = (Elementtype*)realloc(sqlist->list,(sqlist->max_len+INCESS_SIZE)*sizeof(Elementtype)/sizeof(char));
    	if(newbase == NULL)
    	{
    		return mallc_error;
    	}
    	
    	sqlist->list = newbase;
    	sqlist->max_len = sqlist->max_len + INCESS_SIZE;
    	
    	return ok;
    }
    
    //尾插
    int Insert_last(Sqlist *sqlist,Elementtype newdata)
    {
    	if (sqlist == NULL)
    	{
    		return error;
    	}
    	
    	//判断顺序表有没有满
    	if (sqlist->leng == sqlist->max_len)
    	{
    		if(Againmalloc(sqlist) != ok)
    		{
    			return mallc_error;
    		}
    		
    	}
    	
    	sqlist->list[sqlist->leng] = newdata;
    	sqlist->leng++;
    	
    	return ok;
    }
    
    //头插
    int Insert_head(Sqlist *sqlist,Elementtype newdata)
    {
    	if(sqlist == NULL)
    	{
    		return error;
    	}
    	
    	//判断顺序表有没有满
    	if (sqlist->leng == sqlist->max_len)
    	{
    		if(Againmalloc(sqlist) != ok)
    		{
    			return mallc_error;
    		}
    	}
    	
    	//将从1位置开始的数据后移一位
    	int i;
    	for(i = sqlist->leng-1; i >= 0; i--)
    	{
    		sqlist->list[i+1] = sqlist->list[i];
    	}
    	
    	//在1位置插入新数据
    	sqlist->list[0] = newdata;
    	sqlist->leng++;
    }
    
    //在第pos位置插入新数据
    int Insert_pos(Sqlist *sqlist,int pos, Elementtype data)
    {
    	//入口参数检查
    	if(sqlist == NULL || pos <= 0 || pos > sqlist->leng+1)
    	{
    		return error;
    	}
    	
    	if(sqlist->leng == sqlist->max_len)
    	{
    		if (Againmalloc(sqlist) != ok)
    		{
    			return mallc_error;
    		}
    	}
    	
    	//将从pos位置开始的数据后移一位
    	int i;
    	for(i = sqlist->leng-1; i > pos - 1; i--)
    	{
    		sqlist->list[i+1] = sqlist->list[i];
    	}
    	
    	//在pos位置插入新数据
    	sqlist->list[pos-1] = data;
    	sqlist->leng++;
    	
    	return ok;
    }
    
    //删除数据
    int Delete_pos(Sqlist *sqlist, int pos)
    {
    	if(sqlist == NULL || pos < 1 || pos > sqlist->leng)
    	{
    		return error;
    	}
    	
    	int i;
    	for (i = pos; i < sqlist->leng; i++)
    	{
    		sqlist->list[i-1] = sqlist->list[i];
    	}
    	sqlist->leng--;
    	
    	return ok;
    }
    
    //查找元素
    int Search_Element(Sqlist *sqlist, Elementtype data)
    {
    	if (sqlist == NULL)
    	{
    		return error;
    	}
    	
    	int i;
    	for (i = 0; i < sqlist->leng; i++)
    	{
    		if(sqlist->list[i] == data)
    		{
    			return i+1;
    		}
    	}
    	
    	return ok;
    }
    
    //将顺序表倒序
    int Inverse_list(Sqlist *sqlist)
    {
    	if(sqlist == NULL)
    	{
    		return error;
    	}
    	
    	int front = 0;
    	int latter = sqlist->leng-1;
    	int temp;
    	
    	while (front < latter)
    	{
    		temp = sqlist->list[front];
    		sqlist->list[front++] = sqlist->list[latter];
    		sqlist->list[latter--] = temp;
    	}
    	
    	return ok;
    }
    
    //顺序表合并
    int Merge_list(Sqlist *s1,Sqlist *s2,Sqlist *s3)
    {
    	if(s1 == NULL || s2 == NULL)
    	{
    		return error;
    	}
    	s3->list = (Elementtype*)malloc((s1->leng+s2->leng)*sizeof(Elementtype)/sizeof(char));
    	if(s3->list == NULL)
    	{
    		return mallc_error;
    	}
    	s3->leng = s2->leng + s1->leng;
    	s3->max_len =s2->leng + s1->leng;
    	
    	int i = 0;          //s1
    	int j = 0;          //s2
    	int k = 0;          //s3
    	while (i < s1->leng && j < s2->leng)
    	{
    		if(s1->list[i] < s2->list[j])
    		{
    			s3->list[k++] = s1->list[i++];
    		}
    		else
    		{
    			s3->list[k++] = s2->list[j++];
    		}
    	}
    	
    	// 判断s1是否结束
    	while(i < s1->leng)
    	{
    		s3->list[k++] = s1->list[i++];
    	}
    	
    	// 判断s2是否结束
    	while (j < s2->leng)
    	{
    		s3->list[k++] = s2->list[j++];
    	}
    	
    	return ok;
    }
    
    //打印顺序表数据
    void Display(Sqlist *sqlist)
    {
    	if(sqlist == NULL)
    	{
    		return ;
    	}
    	
    	int i;
    	for (i = 0; i < sqlist->leng; i++)
    	{
    		printf("%4d",sqlist->list[i]);
    	}
    	
    	printf("\n");
    }
    
    int main()
    {
    	
    	Sqlist sqlist;               //定义一个顺序表结构变量
    	sqlist.list = NULL;
    	
    	//初始化顺序表
    	if(Init_list(&sqlist) != ok)
    	{
    		return error;
    	}
    	
    	int i;
    	for (i = 0; i < 10; i++)
    	{
    		//尾插
    		Insert_last(&sqlist,i);
    	}
    	printf("sqlist初始化：\n");
    	Display(&sqlist);
    	
    	//在第pos位置插入新数据
    	if(Insert_pos(&sqlist,4,22) != ok)
    	{
    		return error;
    	}
    	printf("在4位置插入新数据后：\n");
    	Display(&sqlist);
    	
    	//将第pos位置数删除
    	if(Delete_pos(&sqlist,4) != ok)
    	{
    		return error;
    	}
    	printf("将4位置数据删除后：\n");
    	Display(&sqlist);
    	
    	
    	Sqlist sqlist2;
    	sqlist2.list = NULL;
    	
    	//初始化顺序表
    	if(Init_list(&sqlist2) != ok)
    	{
    		return error;
    	}
    	
    	for (i = 0; i < 10; i++)
    	{
    		//头插
    		Insert_head(&sqlist2,i);
    	}
    	printf("sqlist2初始化：\n");
    	Display(&sqlist2);
    
    	//查找元素
    	int pos = Search_Element(&sqlist2,7);
    	printf("pos = %d\n",pos);
    
    	//将顺序表倒序
    	if(Inverse_list(&sqlist) != ok)
    	{
    		return error;
    	}
    	printf("sqlist倒序：\n");
    	Display(&sqlist);
    	
    	//将s1和s2合并从小到大放到s3中
    	Sqlist s1;
    	s1.list = NULL;
    	
    	//初始化顺序表
    	if(Init_list(&s1) != ok)
    	{
    		return error;
    	}
    	for (i = 0;i < 20; i = i + 2)
    	{
    		Insert_last(&s1,i);
    	}
    	printf("s1初始化：\n");
    	Display(&s1);
    	
    	Sqlist s2;
    	s2.list = NULL;
    	//初始化顺序表
    	if(Init_list(&s2) != ok)
    	{
    		return error;
    	}
    	for (i = 1;i < 20; i = i + 2)
    	{
    		Insert_last(&s2,i);
    	}
    	printf("s2初始化：\n");
    	Display(&s2);
    		
    	Sqlist s3;
    	if(Merge_list(&s1,&s2,&s3) != ok)
    	{
    		return error;
    	}
    	printf("s1和s2合并后的s3：\n");
    	Display(&s3);
    	
    	return 0;
    }