c学习笔记第17章：高级数据表示 20210331_c高级数据表示很难-CSDN博客

本文链接：https://blog.csdn.net/Nexas/article/details/115359302

c将指针和int类型都储存为整数，但两种类型可进行有效操作不同。

数据表示

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#include <string.h>

#define TSIZE 45
#define FMAX 5

struct film {
	char title[TSIZE];
	int rating;
};
int main(void)
{
	struct film movies[FMAX];
	int i = 0, j;

	puts("Enter first movie title:");
	while (i < FMAX && s_gets(movies[i].title, TSIZE) != NULL && movies[i].title[0] != '\0')
	{
		puts("Enter your rating <0-10>:");
		scanf("%d", &movies[i++].rating);
		while (getchar() != '\n')
			continue;
		puts("Enter next movie ftitl (empty line to stop):");
	}
	if (i == 0)
		printf("No data entered.");
	else
		printf("Here is the movie list:\n");
	for (j = 0; j < i; j++)
	{
		printf("Movies: %s Rating: %d\n", movies[j].title, movies[j].rating);
	}
	printf("Bye!\n");
	return 0;
}

电影的数量，片名的长度，都不确定，如此的数据表示太过死板，不够灵活。
可以使用动态内存分配来表示数据，但用户必须为元素个数提供正确的值。

从数组到链表

可以通过在每个结构中包含指向next结构的指针，当创建结构时，即可把该结构的地址储存在上一个结构之中。

#define TSIZE 45
struct film{
	char tirtle[TSIZE];
	int rating;
	struct film * next;
};

该种定义是定义链表（linked list）的基础。
单独储存第一个结构的指针称为头指针（head pointer），指向链表的第一项。

#define TSIZE 45
struct film{
	char tirtle[TSIZE];
	int rating;
	struct film * next;
};
struct film * head;

先将next设置为NULL，除非有下一次输入。

使用链表

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TSIZE 45

struct film {
	char title[TSIZE];
	int rating;
	struct film* next;
};
int main(void)
{
	struct film * head = NULL;
	struct film* prev, * current;
	char input[TSIZE];

	puts("Enter first movie title:");
	while (s_gets(input, TSIZE) != NULL && input[0] != '\0')
	{
		current = (struct film*)malloc(sizeof(struct film));
		if (head == NULL)  // 第一个结构
			head = current;
		else
			prev->next = current;
		current->next = NULL;
		strcpy(current->title, input);
		puts("Enter your rating <0-10>:");
		scanf("%d", &current->rating);
		while (getchar() != '\n')
			continue;
		puts("Enter next movie ftitl (empty line to stop):");
		prev = current;
	}
	if (head == NULL)
		printf("No data entered.");
	else
		printf("Here is the movie list:\n");
	current = head;
	while (current != NULL)
	{
		printf("Movies: %s Rating: %d\n", current->title, current->rating);
		current = current->next;
	}
	/*释放已分配内存*/
	current = head;
	while (current != NULL)
	{
		free(current);
		head = current->next;
	}
	printf("Bye!\n");
	return 0;
}

创建链表

使用malloc()为结构分配空间
储存结构的地址
将当前信息拷贝入结构
注意必须先将next指针设置为NULL，保证链表有确定的结尾

释放链表

大多环境程序结束时都会自动释放malloc()分配的内存，但保险起见，还是成对调用malloc()与free()

current = head;
	while (current != NULL)
	{
		free(current);
		head = current->next;
	}

抽象数据类型（ADT）

类型特指两类信息：属性和操作
科学计算机领域已开发出一种定义新类型的好方法，用3个步骤完成从抽象到具体的过程。

提供类型属性和相关操作的抽象描述。
开发一个实现ADT的编程接口，即指明如何储存数据和执行所需操作的函数。
编写代码，实现接口。

建立抽象

链表可用操作：

初始化空链表
末尾添加新项
确认是否为空
确认是否已满
确认项数
访问每一项并执行某些操作
任意位置插入一个项
移除其中一个项
检索一个项
以一个项替换另一个项
搜索一个项

该类型总结如下：
类型名：简单链表
类型属性：可以储存一系列项
类型操作：初始化链表为空
确定链表为空
确定链表中的项数
在链表末尾添加项
遍历链表，处理链表中的项
清空链表
下一步是为开发简单链表ADT开发一个C接口