数组、链表、队列和栈，C语言实现

亦凉 2023-03-01 05:53 171阅读 0赞

这一章主要学习数组和链表，并分别用数组和链表实现队列及栈的功能。  
在学习C语言的时候，我们已经学习过了数组，那时对数组的操作主要是生成数组、对数组的元素赋值、读取数组中的元素等内容，并没有对数组中的元素进行删除、插入操作。在本章内容中，我们将对数组的其它方面进行讲解。链表是一个全新的概念，里面要用到指针。这是C语言的一个特色，也是比较难的一部分内容。  
数组和链表是所有数据结构中最基础的两种，同时，它们也是队列、栈、以及以后要学习到的 (二叉) 树、堆、图、串 (我们不讨论串) 等数据结构的基础，几乎所有的算法都是在数组和链表上实现的。可以这么说，如果没有数组和链表，整个数据结构和算法就没法实现了。

1 数组  
好了，我们就从最简单的一维数组开始吧。  
C语言中，申明数组有两种方式：  
① 自动申请，例如int arr \[10\]; 表示让C语言自动申请一段长度够10个int类型数据存放的空间，也就是10 \* 4 = 40个字节。这种方式的好处是不需要让开发者申请内存空间，而且用完之后编译器自动回收内存，不需要开发者手动回收。缺点是数组大小一定要在申请的时候指定，且一定要用常量指定，不能用变量指定。这个缺点是很明显的，我们常常申请一个足够大的空间，从而保证数组的空间够用。这样经常会出现浪费的情况。

② 手动向操作系统申请内存空间。这种方式与自动申请就刚好相反。好处是可以用一个变量临时确定需要申请多大的内存空间，这样就可以不浪费。缺点是需要开发者手动申请，用完之后又需要手动回收内存。对C语言比较熟悉的朋友一定知道，C语言最容易出问题的就是指针，其实也就是内存问题。所以用这种方式时一定要比较当心才行。关于手动向操作系统申请内存空间并建立数组的方式我们在用到的时候再讨论。

注：只有C语言存在两种方式申请数组的情况，其它语言 (C++、Java、C\#、Python等) 都可以用变量在申请数组时确定数组大小，且都可以让语言本身回收垃圾。

好，我们让编译器帮我们申请一个数组：int arr \[10\];

你看，这个数组中每一个元素都是int类型的，占用的内存空间都是4个字节。这样的话，我们如果要找第n个元素，只需要知道arr的首地址，然后计算首地址 + n \* 4，它就是存放第n个元素的地址了。这样是不是很容易？C语言的编译器甚至帮我们做的更好：我们只需要输入arr\[n\]就可以获得第n个元素了，如果用指针的方式，那就是\*(arr + n)。也就是说，随机读取、设置数组中一个元素的时间复杂度为O(1)。代码如下：

int arr[10] = {
        1, 2, 3, 4, 5};
    printf("%d <--> %d\r\n", arr[3], *(arr + 3));

下面我们看一下在数组中插入一个数据的情况：如果要在第二个位置插入数据9，我们需要分三步走：  
第一步，计算数组中有几个元素：5  
第二步，从最后一个元素开始，每一个元素都往后移动一个位置。一共移动4个元素。这样就把第二个的位置空出来了。  
第三步，在第二个的位置放置元素9。

用这种方式，对于一个有n个元素的数组，如果要在最前面插入一个数据，需要移动n个元素，然后再插入一个数据。总的时间复杂度为O(N / 2) = O(N)。

void insertNumAt(int index, int num) 
    {
        
    	for(int i = size; i >= index; i--)
    	{
        
    		arr[i] = arr[i - 1]; //每个元素都往后移动一个位置 
    	}
    	arr[index] = num; //插入新数据 
    	size++; //数组中的元素个数 + 1 
    	
    	show(); //依次显示所有数据
    }

如果要删除第二个位置的数据，我们需要分三步走：  
第一步，计算数组中有几个元素：5  
第二步，从第三个元素开始，每一个元素都往后移动一个位置。一共移动了3个元素。这样就把第二个的位置的数据覆盖掉了。  
第三步，总的size - 1。这样才能避免下次访问到不该访问到的数据 (原先最后一个数据5)。

用这种方式，对于一个有n个元素的数组，如果要在删除最前面的数据，需要移动n - 1个元素。总的时间复杂度为O(N)。

删除第index个数据：用后面的数据覆盖前面的数据即可

void removeNumAt(int index)
    {
        
    	for(int i = index; i < size; i++)
    	{
        
    		arr[i] = arr[i + 1]; //每个元素都往前移动一个位置 
    	}
    	size--; //删除完之后，总的元素个数-1 
    	show(); //依次显示所有数据
    }

至此，我们介绍完了数组的随机读取/修改、添加、删除操作。数组的随机读取/修改的效率很高，时间复杂度为O(1)；但是添加、删除操作的效率就比较低了，时间复杂度为O(N)。  
至于用手动方式申请到的数组，它的读取/修改、添加、删除操作也是一样的，时间复杂度也一样。

总的代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    //申请了10个位置的数组，但只存放了5个元素。
    //剩余5个位置的值都是默认值：0
    int arr[10] = {
        1, 2, 3, 4, 5};  
    int size = 5; //目前数组中一共有5个元素 
    
    void show() //依次显示所有数据
    {
        
    	for(int i = 0; i < size; i++)
    	{
        
    		printf("%d, ", arr[i]);  
    	}
    	printf("\r\n\r\n");  
    }
    
    //1、读取数组中的一个元素的时间复杂度为O(1) 
    void getNum(int index)
    {
        
    	printf("数组方式访问数据: %d \r\n", arr[index]); //数组方式访问数据 
    	printf("指针方式访问数据: %d \r\n\r\n",*(arr + index)); //指针方式访问数据 
    }
    
    //2、修改数组中的一个元素的时间复杂度为O(1) 
    void setNum(int index, int n)
    {
        
    	arr[index] = n; //数组方式修改数据
    	printf("数组方式修改数据: %d \r\n", arr[3]);  
    
    	*(arr + index) = n; //指针方式修改数据
    	printf("指针方式修改数据: %d \r\n\r\n", *(arr + index));  
    }
    
    //3、在数组指定位置插入一个数据，时间复杂度为O(N) 
    void insertNumAt(int index, int n) 
    {
        
    	for(int i = size; i >= index; i--)
    	{
        
    		arr[i] = arr[i - 1]; //每个元素都往后移动一个位置 
    	}
    	arr[index] = n; //插入新数据 
    	size++; //数组中的元素个数 + 1 
    	
    	show(); //依次显示所有数据
    }
    
    //4、在数组最前面插入一个数
    void insertNumAtFirst(int n) 
    {
        
    	insertNumAt(0, n);
    }
    
    //5、在数组最后面插入一个数
    void appendNum(int n) 
    {
        
    	insertNumAt(size, n);
    }
    
    //6、删除指定位置的数据：用后面的数据覆盖前面的数据即可
    //时间复杂度为O(N)
    void removeNumAt(int index)
    {
        
    	for(int i = index; i < size; i++)
    	{
        
    		arr[i] = arr[i + 1]; //每个元素都往前移动一个位置 
    	}
    	size--; //删除完之后，总的元素个数-1 
    	show(); //依次显示所有数据
    }
    
    //7、删除数组的首元素 
    void removeNumAtFirst()
    {
        
    	removeNumAt(0);
    }
    
    //8、删除数组的最后一个元素 
    void removeNumAtLast()
    {
        
    	removeNumAt(size - 1);
    }
    
    int main()
    {
        
    	getNum(3); //读取数组中的一个元素
    	
    	setNum(3, 99); //修改数组中的一个元素
    	
    	printf("在数组指定位置插入一个数据: ");
    	insertNumAt(3, 7); //在数组指定位置插入一个数据
    	
    	printf("在数组最前面插入一个数据: ");
    	insertNumAtFirst(66);
    	
    	printf("在数组最后面插入一个数据: ");
    	appendNum(89);
    	
    	printf("删除数组指定位置的数据: ");
    	removeNumAt(4);
    
    	printf("删除数组的首元素: ");
    	removeNumAtFirst();
    	
    	printf("删除数组的最后一个元素: ");
    	removeNumAtLast();
    	return 0;
    }

运行结果如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]  
上面就是关于一维数组的所有内容了。数组的随机读取/修改的效率很高，但是添加和删除数据的效率很低。

下一小节讲链表。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230209/f2c1e610154544ea9321f1e782a8e9de.png