C语言抽象数据类型
/*-------以下为atd.c文件--------*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stackheader.h"
//定义一种数据类型涉及：数据的存储（数据应包含什么信息、信息及数据整体应使用什么C类型存储）、数据的操作（可以对数据进行什么运算）
//ADT（abstract data type）抽象数据类型，是对一种类型属性集及可以对该类型进行的操作的正式定义。ADT应该用一般语言而非计算机语言表示，不应包含实现细节
void films2(void);
void reverse_pr(struct film* ps);
#define TSIZE 45
#define GETTITLE(X) fgets((X),45,stdin)
#define CLEAN() while(getchar()!='\n')continue
struct film { //使用结构实现单向链表
char title[TSIZE];
int rating;
struct film* next; //指向链表中的下一个结构/后继结点
};
void films2(void)
{
struct film* head = NULL; //指向链表的头结点
struct film * prev = NULL, * current = NULL;
char input[TSIZE]="";
puts("Enter first movie title:");
while (GETTITLE(input))
{
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", ¤t->rating);
CLEAN();
puts("Enter next movie title (Ctrl+Z to stop):");
prev = current;
}
if (head == NULL)
puts("No data entered.");
else
reverse_pr(head);
for (current = head; current != NULL; current = head)
{
head = current->next;
free(current);
}
puts("Bye!");
}
void reverse_pr(struct film* ps) //逆序打印
{
if (ps->next)
reverse_pr(ps->next); //递归
printf("Movie: %s\tRating: %d\n", ps->title, ps->rating); //在递归操作之后的代码逆序执行
}
/*-------以下为stackheader.h文件--------*/
#pragma once
#ifndef STACKHEADER_H
#define STACKHEADER_H //整个头文件包在ifndef内，避免重复
#include <stdbool.h>
/*栈stack的ADT：
类型名：栈
类型属性：可以从栈顶压入或弹出项
类型操作：创建一个空栈，从栈顶压入项，从栈顶弹出项，显示栈中项的数量，清空栈，确认栈为空，确认栈已满
*/
typedef int Dataunit; //设定Dataunit为实际存放数据的数据类型，根据使用场景重新构造Dataunit，所有直接处理数据的函数原型都使用Dataunit别名而非实际类型，在实际使用时只需要更改Dataunit的定义，而不用更改每一个函数的参数类型
//即便这里将Dataunit设定为int，用户在使用该栈时也应该使用Dataunit类型变量
typedef struct item { //栈中由项组成，这里设计为项包含实际数据和指向下侧的项的指针
Dataunit value;
struct item* below;
} Item;
typedef struct stack { //使用结构定义栈，栈包括记录栈顶项地址的指针和记录项数的字段
Item* top;
int size;
}Stack;
Stack newstack(void); //返回一个栈结构的值，应将栈顶指针指向NULL，将项数设为0，函数中产生的自动类型结构变量会释放，如果使用动态类型需要额外用来释放栈的函数，再或者接收一个栈的地址，只将栈初始化。操作：初始化栈。前提条件：无。后置条件：返回空栈的值
bool push(const Dataunit* pi, Stack* ps); //将数据封装成项（动态内存分配）压栈，需要传入数据和栈的地址，返回操作是否成功
bool pop(Dataunit* pi, Stack* ps); //对栈的操作都需要知道是哪个栈，所以都需要传入栈的地址，弹栈将栈顶的项的数据放入接收的地址中并释放该项的动态内存并返回true，空栈返回false
int size(const Stack* ps); //返回项数，如果栈结构没有包含size，则需要从栈顶遍历栈来计数
void clearstack(Stack* ps); //清空栈，从栈顶逐个释放项，最后设置栈顶指针为NULL，size为0
bool empty(const Stack* ps); //返回size==0
bool full(const Stack* ps); //返回size==MAX（如果有设置上限）或者可用内存满了无法再动态分配额外的内存。操作：检查栈是否已满。前提条件：ps指向之前已被初始化的栈。后置条件：如果已满返回true否则返回false
//头文件中声明的函数原型为供用户使用的接口，用户应只通过这里规定的函数来使用这个栈
#endif // !STACKHEADER_H
/*-------以下为stackC.c文件--------*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include "stackheader.h" //根据头文件的函数原型实现的一种函数接口
static Item* generate_item(const Dataunit* pi);
Stack newstack(void)
{
return (Stack) { NULL, 0 };
}
bool push(const Dataunit* pi, Stack* ps)
{
if (full(ps))
return false;
Item* ptri = generate_item(pi); //使用局部函数来完成接口函数中的部分内容
ptri->below = ps->top;
ps->top = ptri; //栈顶始终指向最新添加的一项
ps->size++;
return true;
}
static Item* generate_item(const Dataunit* pi) //内部链接，局部函数为文件私有，不应暴露给用户使用，只在内部供接口函数调用
{
Item* ptri = (Item*)malloc(sizeof(Item));
ptri->value = *pi;
return ptri;
}
bool pop(Dataunit* pi, Stack* ps)
{
if (empty(ps))
return false;
Item* ptri = ps->top;
ps->top = ptri->below;
*pi = ptri->value;
free(ptri);
ps->size--;
return true;
}
int size(const Stack* ps)
{
return ps->size;
}
void clearstack(Stack* ps)
{
for (Item* ptri; ps->top; ps->top = ptri)
{
ptri = ps->top->below;
free(ps->top);
}
ps->size = 0;
}
bool empty(const Stack* ps)
{
return ps->size <= 0;
}
bool full(const Stack* ps)
{
Item* ptri = (Item*)malloc(sizeof(Item));
if (ptri)
{
free(ptri);
return false;
}
return true;
}
bool binary_search(int* arr, int size, int target)
{
if (size <= 0)
return false;
int low = 0;
int high = size - 1;
int mid;
while (high >= low)
{
mid = (high + low) / 2;
if (arr[mid] == target)
{
return true;
}
if (arr[mid] > target)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return false;
}
