C語言抽象數(shù)據(jù)類型
/*-------以下為atd.c文件--------*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stackheader.h"
//定義一種數(shù)據(jù)類型涉及：數(shù)據(jù)的存儲(chǔ)（數(shù)據(jù)應(yīng)包含什么信息、信息及數(shù)據(jù)整體應(yīng)使用什么C類型存儲(chǔ)）、數(shù)據(jù)的操作（可以對(duì)數(shù)據(jù)進(jìn)行什么運(yùn)算）
//ADT（abstract data type）抽象數(shù)據(jù)類型，是對(duì)一種類型屬性集及可以對(duì)該類型進(jìn)行的操作的正式定義。ADT應(yīng)該用一般語言而非計(jì)算機(jī)語言表示，不應(yīng)包含實(shí)現(xiàn)細(xì)節(jié)
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 {????//使用結(jié)構(gòu)實(shí)現(xiàn)單向鏈表
???? char title[TSIZE];
???? int rating;
???? struct film* next; //指向鏈表中的下一個(gè)結(jié)構(gòu)/后繼結(jié)點(diǎn)
};
void films2(void)
{
???? struct film* head = NULL; //指向鏈表的頭結(jié)點(diǎn)
???? struct film * prev = NULL, * current = NULL;
???? char input[TSIZE]="";
???? puts("Enter first movie title:");
???? while (GETTITLE(input))
???? {
???????? current = (struct film*)malloc(sizeof(struct film)); //增加結(jié)點(diǎn)
???????? if (head==NULL)
???????? {
???????? ????head = current;
???????? }
???????? else
???????? {
???????? ????prev->next = current;
???????? }
???????? current->next = NULL; //初始化結(jié)點(diǎn)
???????? 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); //在遞歸操作之后的代碼逆序執(zhí)行
}
/*-------以下為stackheader.h文件--------*/
#pragma once
#ifndef STACKHEADER_H
#define STACKHEADER_H //整個(gè)頭文件包在ifndef內(nèi)，避免重復(fù)
#include <stdbool.h>
/*棧stack的ADT：
類型名：棧
類型屬性：可以從棧頂壓入或彈出項(xiàng)
類型操作：創(chuàng)建一個(gè)空棧，從棧頂壓入項(xiàng)，從棧頂彈出項(xiàng)，顯示棧中項(xiàng)的數(shù)量，清空棧，確認(rèn)棧為空，確認(rèn)棧已滿
*/
typedef int Dataunit; //設(shè)定Dataunit為實(shí)際存放數(shù)據(jù)的數(shù)據(jù)類型，根據(jù)使用場景重新構(gòu)造Dataunit，所有直接處理數(shù)據(jù)的函數(shù)原型都使用Dataunit別名而非實(shí)際類型，在實(shí)際使用時(shí)只需要更改Dataunit的定義，而不用更改每一個(gè)函數(shù)的參數(shù)類型
//即便這里將Dataunit設(shè)定為int，用戶在使用該棧時(shí)也應(yīng)該使用Dataunit類型變量
typedef struct item { //棧中由項(xiàng)組成，這里設(shè)計(jì)為項(xiàng)包含實(shí)際數(shù)據(jù)和指向下側(cè)的項(xiàng)的指針
???? Dataunit value;
???? struct item* below;
} Item;
typedef struct stack { //使用結(jié)構(gòu)定義棧，棧包括記錄棧頂項(xiàng)地址的指針和記錄項(xiàng)數(shù)的字段
???? Item* top;
???? int size;
}Stack;
Stack newstack(void); //返回一個(gè)棧結(jié)構(gòu)的值，應(yīng)將棧頂指針指向NULL，將項(xiàng)數(shù)設(shè)為0，函數(shù)中產(chǎn)生的自動(dòng)類型結(jié)構(gòu)變量會(huì)釋放，如果使用動(dòng)態(tài)類型需要額外用來釋放棧的函數(shù)，再或者接收一個(gè)棧的地址，只將棧初始化。操作：初始化棧。前提條件：無。后置條件：返回空棧的值
bool push(const Dataunit* pi, Stack* ps); //將數(shù)據(jù)封裝成項(xiàng)（動(dòng)態(tài)內(nèi)存分配）壓棧，需要傳入數(shù)據(jù)和棧的地址，返回操作是否成功
bool pop(Dataunit* pi, Stack* ps); //對(duì)棧的操作都需要知道是哪個(gè)棧，所以都需要傳入棧的地址，彈棧將棧頂?shù)捻?xiàng)的數(shù)據(jù)放入接收的地址中并釋放該項(xiàng)的動(dòng)態(tài)內(nèi)存并返回true，空棧返回false
int size(const Stack* ps); //返回項(xiàng)數(shù)，如果棧結(jié)構(gòu)沒有包含size，則需要從棧頂遍歷棧來計(jì)數(shù)
void clearstack(Stack* ps); //清空棧，從棧頂逐個(gè)釋放項(xiàng)，最后設(shè)置棧頂指針為NULL，size為0
bool empty(const Stack* ps); //返回size==0
bool full(const Stack* ps); //返回size==MAX（如果有設(shè)置上限）或者可用內(nèi)存滿了無法再動(dòng)態(tài)分配額外的內(nèi)存。操作：檢查棧是否已滿。前提條件：ps指向之前已被初始化的棧。后置條件：如果已滿返回true否則返回false
//頭文件中聲明的函數(shù)原型為供用戶使用的接口，用戶應(yīng)只通過這里規(guī)定的函數(shù)來使用這個(gè)棧
#endif // !STACKHEADER_H
/*-------以下為stackC.c文件--------*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include "stackheader.h" //根據(jù)頭文件的函數(shù)原型實(shí)現(xiàn)的一種函數(shù)接口
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); //使用局部函數(shù)來完成接口函數(shù)中的部分內(nèi)容
???? ptri->below = ps->top;
???? ps->top = ptri; //棧頂始終指向最新添加的一項(xiàng)
???? ps->size++;
???? return true;
}
static Item* generate_item(const Dataunit* pi) //內(nèi)部鏈接，局部函數(shù)為文件私有，不應(yīng)暴露給用戶使用，只在內(nèi)部供接口函數(shù)調(diào)用
{
???? 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;
}
