手记

C语言数据结构(7)--链式线性表

顺序线性表的缺点

上一篇讲了顺序线性表,实际上就是用数组的顺序来表达一个有顺序的一维数据集合。

但是数据这种存储结构存在一些问题:

  1. 容量有限,数组属于连续存储空间,不能太大,如果申请太大的连续数组空间,可能会GG,至于具体能申请多大,请大家试试,猫哥比较懒,此处就不试了…
  2. 插入与删除,速度慢。这个是肯定的啦,比如插入一个元素,后面所有的元素都得往后移动,删除一个元素,前面的元素都得往前移动。

咋办捏,有一个很朴素的想法就是,让前面一个人记住后面一个人,不用关心整体,只要前后关联就OK。这种数据结构我称之为链式线性表,为啥是我称之为,因为网上有各种各样的叫法,我觉得我这个叫法比较准确,哈哈。

链式线性表的实现原理

因为C语言支持指针啊,让前面一个记住后面一个,太简单了啊,直接让前面一个的指针指向后面一个完事。那第一个咋办捏,第一个没有前面一个啊,那也么事,我们直接定义一个头部指向第一个元素,也就是说头部实际上不是线性表的数据部分,但是它能把链式线性表印出来。

就像火车头,虽然不拉乘客,但是能带着乘客去他们想去的地方。这个比喻实在太形象了,厉害炸了~

链式线性表的操作

此处跟顺序线性表一模一样,因为都是线性表嘛,功能一样,只是存储结构不一样。

  1. 显示线性表元素个数
  2. 列出线性表的所有元素
  3. 获取指定位置元素
  4. 在指定位置插入元素
  5. 删除指定位置元素
  6. 清空线性表

链式线性表代码实现

话不多说,说多了上头。酒不多喝,喝多了会难受,直接上代码~

PS:我自己测试没发现BUG,但是不能保证肯定没有BUG…保佑我~!

/*
 * 链式线性表
 * 作者:熊猫大大
 * 时间:2019-09-25
*/
#include<stdio.h>

// 链式线性表的一个节点
typedef struct {
	int data;//保存节点数据
	struct Node *next;//指向下一个节点
}Node;

// 获取元素个数
int getCount(Node *head)
{
	int count = 0;
	Node* p = head;//定义一个指针首先指向头结点
	while (p->next!= NULL)//还有数据元素
	{
		count++;
		p = p->next;
	}
	return count;
}

// 显示所有元素
void printList(Node *head)
{
	int i;
	printf("\n所有元素:");
	Node* p = head;//定义一个指针首先指向头结点
	while (p->next != NULL)
	{
		p = p->next;
		printf("%d ", p->data);
	}
}

// 获取指定位置元素,返回值放入result指向元素,注意位置从0开始
int getData(Node *head, int index, int *result)
{
	int i=0;//当前位置
	if (index < 0) 
	{
		return 0;////位置不存在
	}
	Node* p = head;//定义一个指针首先指向头结点

	while (p->next != NULL) 
	{
		p = p->next;
		if (i == index) {
			*result = p -> data;
		}
		i++;
	}
	if (i >= index) //位置超限
	{
		return 0;
	}
	return 1;//1表示成功
}

// 插入元素
int insertData(Node *head, int index, int input)
{
	int i=0;//当前位置
	Node* temp = (Node*)malloc(sizeof(Node));//临时节点
	if (index < 0)
	{
		return 0;////位置不存在
	}
	if (index == 0) //第一个位置插入元素
	{
		temp->data = input;
		temp->next = head->next;
		head->next= temp;
		return;
	}
	Node* p = head;//定义一个指针首先指向头结点
	while (p->next != NULL)
	{
		p = p->next;
		i++;
		if (i == index) {//找到插入位置
			temp->data = input;
			temp->next = NULL;
			p -> next = temp;
			return;
		}
	}
	if (i == index) //最后一个后面追加
	{
		return 1;
	}
	else {
		return 0;//位置超限
	}
	return 1;
}

// 删除指定位置元素
int deleteData(Node *head, int index)
{
	int i = 0;//当前位置
	if (index < 0)
	{
		return 0;////位置不存在
	}
	Node* p = head;//定义一个指针首先指向头结点
	Node* front = head;//记录前一个元素
	while (p->next != NULL)
	{
		front = p;
		p = p->next;
		if (i == index) {//删除该元素
			front->next = p -> next;//跳过被删除元素
			free(p);//释放
			return;
		}
		i++;
	}
	if (i >= index) //位置超限
	{
		return 0;
	}
	return 1;//1表示成功
}

// 清空所有元素
int clearData(Node *head)
{
	Node* p = head -> next;
	Node* temp;
	while (p != NULL) 
	{
		temp = p->next;
		free(p);
		p = temp;
	}
	head->next = NULL;
	return 1;
}

// 入口
int main()
{
	Node head;//头部节点实际上就代表了一个链表
	head.data = 0;//头部节点存储的数据没意义
	head.next = NULL;//刚开始没有数据节点
	int count = getCount(&head);
	printf("初始长度:%d\n",count);
	insertData(&head,0,1);
	insertData(&head, 1, 2);
	insertData(&head, 2, 3);
	count = getCount(&head);
	printf("新增后长度:%d\n", count);
	printList(&head);
	int result = 0;
	getData(&head,2,&result);
	printf("位置2元素:%d\n", result);
	deleteData(&head,0);
	printList(&head);
	clearData(&head);
	count = getCount(&head);
	printf("清空后长度:%d\n", count);
	return 1;
}
0人推荐
随时随地看视频
慕课网APP