【C语言学习】——————数据结构之链表

一道数据结构题来认识链表

其实用数组也可以来实现该题，但是题目要求链表结构实现，正好浅学一下数据结构。

尾部插入实现单链表

链表由多个结点链接而成，前一个结点中包含着下一个结点的地址，还包含所存储的数据；由此知，每个结点应该是结构体变量，可根据要存储多少数据，来动态开辟内存空间，这里我们使用malloc函数。 结构体和动态内存开辟代码如下:

struct a
{
          
   
	int data;
	struct a* next;
};
struct a* p = (struct a*)malloc(sizeof(struct a));

实现尾端插入结点

代码如下：

int n = 0,i=0,data=0;
	scanf("%d", &n);
	struct a* list = NULL;//如何找到这个链表，用list指向第一个结点
	struct a* tail = NULL;//用tail指向链表的最后一个结点
	for (i = 0; i < n; i++)
	{
          
   
		scanf("%d", &data);
		struct a* p = (struct a*)malloc(sizeof(struct a));
		p->data = data;
		p->next = NULL;//每插入一个结点，把指针域赋为空指针,当为最后一个结点时，指针域为空指针
		if (list==NULL)//将第一个结点的地址赋给list
		{
          
   
			list = p;
			tail = p;
		}
		else//不为第一个结点时，在结点指针域后存入新结点地址
		{
          
   
			tail->next = p;//第一个结点的指针域放入下一个结点的地址
			tail = p;//再将tail指向当前最后一个结点
		}
	}

存储数据后如何删除指定结点

这步实现的代码太low了就，钻了空子，下次详写如何删除结点。

int del = 0;
	struct a* s = list;
	scanf("%d", &del);
		while (s)
		{
          
   
			if (s -> data == del)
			{
          
   
				s->data = 0;
			}
			s = s->next;
		}
	struct a* d = list;
	int count = 0;
	while (d)
	{
          
   
		if (d->data != 0)
		{
          
   
			count++;
		}
		d = d->next;
	}
	printf("%d
", count);
	struct a* b = list;
	while (b)
	{
          
   
		if (b->data!=0)
		{
          
   
			printf("%d ", b->data);
		}
		b = b->next;
	}

把指定删除数据更改为0，然后限制输出，太low了… 下面是整块代码：

#include <stdio.h>
#include <stdlib.h>
struct a
{
          
   
	int data;
	struct a* next;
};
int main()
{
          
   
	int n = 0,i=0,data=0;
	scanf("%d", &n);
	struct a* list = NULL;//如何找到这个链表，用list指向第一个结点
	struct a* tail = NULL;//用tail指向链表的最后一个结点
	for (i = 0; i < n; i++)
	{
          
   
		scanf("%d", &data);
		struct a* p = (struct a*)malloc(sizeof(struct a));
		p->data = data;
		p->next = NULL;//每插入一个结点，把指针域赋为空指针,当为最后一个结点时，指针域为空指针
		if (list==NULL)//将第一个结点的地址赋给list
		{
          
   
			list = p;
			tail = p;
		}
		else//不为第一个结点时，在结点指针域后存入新结点地址
		{
          
   
			tail->next = p;//第一个结点的指针域放入下一个结点的地址
			tail = p;//再将tail指向当前最后一个结点
		}
	}
	int del = 0;
	struct a* s = list;
	scanf("%d", &del);
		while (s)
		{
          
   
			if (s -> data == del)
			{
          
   
				s->data = 0;
			}
			s = s->next;
		}
	struct a* d = list;
	int count = 0;
	while (d)
	{
          
   
		if (d->data != 0)
		{
          
   
			count++;
		}
		d = d->next;
	}
	printf("%d
", count);
	struct a* b = list;
	while (b)
	{
          
   
		if (b->data!=0)
		{
          
   
			printf("%d ", b->data);
		}
		b = b->next;
	}
	return 0;
}

数据在内存中的存储分析

实现更有效的内存分配，“现取现用”，如果用数组代替，开辟更多空间，只会白白浪费