有趣的数据结构算法6——动态顺序表的建立

浅浅的花香味﹌ 2021-12-01 14:14 208阅读 0赞

### 有趣的数据结构算法6——动态顺序表的建立 ###

*  本例子所用函数
 *  示例
 *  GITHUB下载连接

听说平常的数组不能扩充，那数据溢出怎么办？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center]  
不要慌，本次教程主要讲述如何进行动态顺序表的建立。

# 本例子所用函数 #

#include <stdlib.h>
    //头文件
    void *malloc(size_t size);
    //malloc函数是一种分配长度为size_bytes字节的内存块的函数。
    //可以向系统申请分配指定size个字节的内存空间。
    //在本例中malloc函数用于初始化顺序表时的内存申请
    void *realloc(void *ptr, size_t new_size );
    //realloc函数用于修改一个已经分配完成的内存块的大小,可以使一块内存的扩大或缩小。
    //realloc将会为*ptr重新分配一块nuw_size大小的内存块，同时把原先那块内存的内容复制到新的内存块上。
    //使用realloc后就应该改用realloc返回的新指针。
    //在本例中realloc函数用于原顺序表内存不足时的内存申请。

# 示例 #

本例子主要讲述了当动态顺序表内存不足时，如何动态申请内存空间的过程。

#include <stdio.h>
    #include <stdlib.h>
    #include <conio.h>
    
    #define MaxSize 10
    typedef int Ele;
    
    typedef struct
    {
        
    	Ele *data;
    	int length;
    	int listSize;
    }sqList;
    
    
    void init(sqList *L)	//初始化一个顺序表，length代表当前顺序表长度，listSize表示最大长度
    {
        
    	L->data = (Ele *)malloc(MaxSize * sizeof(Ele));
    
    	if (!L->data){
        
    		printf("内存分配失败\n");
    		exit(0);
    	}
    	L->length = 0;
    	L->listSize = MaxSize;
    }
    
    void Insertdata(sqList *L, int i, Ele x) //向顺序表中插入元素，i代表插入元素的位置，x代表待插入的元素值。
    {
        
    	Ele *base;
    
    	int p, insertPtr;
    
    	if (i<1 || i>L->length + 1)
    	{
        
    		printf("插入位置错误\n");
    		exit(0);
    	}
    
    	if (L->length >= L->listSize)	//顺序表长度不足，调用realloc()函数重新分配空间
    	{
        
    		base = (Ele *)realloc(L->data, (L->listSize + MaxSize)*sizeof(Ele));
    		L->data = base;
    		L->listSize = L->listSize + MaxSize;
    	}
    
    	insertPtr = i - 1;						//找到指定索引
    
    	for (p = L->length - 1; p >= i - 1; p--)	//位置i后所有数据向后移动一格
    	{
        
    		L->data[p] = L->data[p - 1];
    	}
    	L->data[insertPtr] = x;					//指定位置						
    	L->length++;							//表长加1
    }
    
    
    
    void Deldata(sqList *L, int i)// 在顺序表中删除元素，i代表要删除的元素位置
    {
        
    	int delItem;
    
    	if (i<1 || i>L->length)
    		exit(0);
    
    	for (delItem = i - 1; delItem < L->length-1; ++delItem)	// 每个数据向前移一格
    	{
        
    		L->data[delItem] = L->data[delItem+1];
    	}
    
    	L->length--;
    }
    
    int main()
    {
        
    	sqList l;
    	int i,num;
    	Ele e;
    
    	init(&l);
    	printf("当前表的数据个数是：%d,最大容量是：%d\n", l.length, l.listSize);
    	printf("向顺序表插入11个元素\n");
    	for (i = 0; i < 11; i++)
    	{
        
    		scanf("%d", &e);
    		Insertdata(&l, i + 1, e);
    	}
    	printf("\n\n");
    	printf("完成插入后，表中的内容是：");
    	for (i = 0; i < l.length; i++)
    	{
        
    		printf("%d ", l.data[i]);
    	}
    	printf("\n\n");
    	printf("请指定要删除的元素的位置\n");
    	scanf("%d", &num);
    	Deldata(&l, num);
    
    	printf("完成删除后，表中的内容是：");
    	for (i = 0; i < l.length; i++)
    	{
        
    		printf("%d ", l.data[i]);
    	}
    	printf("\n\n");
    	printf("当前表的数据个数是：%d,最大容量是：%d\n", l.length, l.listSize);
    
    	return 0;
    }

# GITHUB下载连接 #

[https://github.com/bubbliiiing/Data-Structure-and-Algorithm][https_github.com_bubbliiiing_Data-Structure-and-Algorithm]

希望得到朋友们的喜欢。  
有问题的朋友可以提问噢。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70_pic_center]: /images/20211201/73f9e65f8b404f28b429f6bdada3294b.png
[https_github.com_bubbliiiing_Data-Structure-and-Algorithm]: https://github.com/bubbliiiing/Data-Structure-and-Algorithm