【C语言】模拟实现链表

迷南。 2022-06-14 10:46 225阅读 0赞

链表(Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer）访问特定编号的节点则需要O(n）的时间，而顺序表相应的时间复杂度分别是O(logn）和O⑴。

链表一般是数据结构中要实现的，接下来我们来看一下如何用C语言来实现链表：定义两个数组data和right，一个数组data来存储每序列中的每一个数，再用一个数组 right  来存放序列中每一个数右边的数。

代码的实现：

#define _CRT_SECURE_NO_DEPRECATE
    #include<stdio.h>
    #include<stdlib.h>
    
    
    void ListAdd()
    {
    	int data[101], right[101];
    	int i, n, t, len;
    	printf("请输入数据的个数-> ");
    	scanf("%d", &n);
    	for (i = 1; i <= n; i++)//循环读入n个数
    	{
    		scanf("%d", &data[i]);//将读入的数据存入data里面
    	}
    	len = n;
    	for (i = 0; i <= n; i++)//初始化数组right
    	{
    		if (i != n)
    		{
    			right[i] = i + 1;
    		}
    		else
    		{
    			right[i] = 0;
    		}
    	}
    	//直接在数组data的末尾增加一个数
    	len++;
    	scanf("%d", &data[len]);
    	t = 1;
    	while (t != 0)
    	{
    		if (data[right[t]] > data[len])//如果当前节点的下一个数字大于要插入的数字，则直接插入到中间数字
    		{
    			right[len] = right[t];//新插入的数的下一个节点标号等于当前节点的下一个编号
    			right[t] = len;//当前节点的下一个编号就是新插入节点的编号
    			break;
    		}
    		t = right[t];
    	}
    	t = 1;
    	while (t != 0)
    	{
    		printf("%d ", data[t]);
    		//printf(" ");
    		t = right[t];
    	}
    }
    int main()
    {
    	
    	ListAdd();
    	system("pause");
    	return 0;
    }

运行的结果：

![Center][]

[Center]: /images/20220614/17a0bcb920c242fc86231422f49c6c5d.png