pointers - 通用树指针 ada 的实例化
问题描述
我尝试在 Ada 中构建一个通用的二叉搜索树模块，树将是通用参数，所以，我这样做：
-- Spécification du module ABR.
-- Mettre T_ABR comme un pointeur générique.
Generic
type T_Noeud(<>);
type T_ABR is access T_Noeud; -- Pointeur sur T_Noeud.
package ABR is
Cle_Presente_Exception : Exception; -- une clé est déjà présente dans un ABR
Cle_Absente_Exception : Exception; -- une clé est absente d'un ABR
-- Initialiser un Abr. Abr est vide.
-- Param Abr : L'arbre qu'on va initialiser.
procedure Initialiser(Abr: out T_ABR) with
Post => Est_Vide (Abr); -- Abr := Null.
-- Est-ce qu'un Abr est vide ?
-- Param Abr : L'arbre qu'on vaudra savoir si elle est vide.
-- Retrun Boolean : Retourne True si Abr est vide, sinon False.
function Est_Vide (Abr : T_Abr) return Boolean;
-- Obtenir le nombre d'éléments d'un Abr.
-- Param Abr : L'arbre qu'on vaudra calculer sa taille.
-- Retrun Integer : Retourne la taille de Abr.
function Taille (Abr : in T_ABR) return Integer with
Post => Taille'Result >= 0 -- Retourne une taille positive.
and (Taille'Result = 0) = Est_Vide (Abr); -- If taille (Abr) = 0 then Abr := Null
-- Insérer une clé associée à un nouveau noeud dans Abr.
-- Param Abr : L'arbre où on veut insérer un noeud.
-- Param Cle : La Clé correspondante au noeud qu'on veut insérer.
-- Exception : Cle_Presente_Exception si la clé est déjà dans l'Abr.
procedure Inserer (Abr : in out T_ABR ; Cle : in Integer) with
Post => Taille (Abr) = Taille (Abr)'Old + 1; -- Un élément de plus.
-- Supprimer la donnée associée à la clé Clé dans l'ABR Abr.
-- Param Abr : L'arbre où on veut supprimer un noeud.
-- Param Cle : La Clé correspondante au noeud qu'on veut supprimer.
-- Exception : Cle_Absente_Exception si Clé n'est pas utilisée dans l'Abr
procedure Supprimer (Abr : in out T_ABR ; Cle : in Integer) with
Post => Taille (Abr) = Taille (Abr)'Old - 1; -- Un élément de moins.
-- Supprimer tous les éléments d'un ABR.
-- Doit être utilisée dès qu'on sait qu'un ABR ne sera plus utilisé.
-- Param Abr : L'arbre à détruire.
procedure Vider (Abr : in out T_ABR) with
Post => Est_Vide (Abr);
-- Afficher un ABR Abr dans l'ordre croissant des clés (parcours infixe)
-- Param Abr : L'arbre à afficher.
procedure Afficher (Abr : in T_Abr);
-- Afficher un ABR Abr (en faisant apparaître la strucre grâce à une
-- indendation et un signe '<', '>', '/' pour indiquer la sous-arbre
-- gauche, '>' pour un sous arbre droit et '/' pour la racine)
-- Exemple :
--
-- / Cle1 : Valeur1
-- < Cle2 : Valeur2
-- > Cle3 : Valeur3
-- > Cle4 : Valeur 4
-- < Cle5 : Valeur 5
-- Param Abr : L'arbre à afficher.
procedure Afficher_Debug (Abr : in T_Abr);
private
type T_Noeud is
record
Cle: Integer;
Sous_Arbre_Gauche : T_ABR;
Sous_Arbre_Droit : T_ABR;
-- Invariant
-- Pour tout noeud N dans Sous_Arbre_Gauche, N.Cle < Cle.
-- Pour tout noeud N dans Sous_Arbre_Droit, N.Cle > Cle.
end record;
end ABR;
然后，我在 abr.adb 中实现了这个模块的主体：
-- Implantation du module ABR.
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Unchecked_Deallocation;
package body ABR is
-- Libérer la mémoire.
procedure Free is
new Ada.Unchecked_Deallocation (Object => T_Noeud, Name => T_ABR);
procedure Initialiser(Abr: out T_ABR) is
begin
Abr := Null;
end Initialiser;
function Est_Vide (Abr : T_Abr) return Boolean is
begin
return Abr = Null;
end;
function Taille (Abr : in T_ABR) return Integer is
begin
if Est_Vide (Abr) then
return 0;
else
return 1 + Taille (Abr.all.Sous_Arbre_Gauche) + Taille (Abr.all.Sous_Arbre_Droit);
end if;
end Taille;
procedure Inserer (Abr : in out T_ABR ; Cle : Integer) is
begin
if (Est_Vide(Abr)) then
Abr := New T_Noeud'(Cle, Null, Null);
elsif (ABR.all.Cle = Cle) then
raise Cle_Presente_Exception;
elsif (Cle < Abr.all.Cle) then
Inserer(Abr.all.Sous_Arbre_Gauche, Cle);
elsif (Cle > Abr.all.Cle) then
Inserer(Abr.all.Sous_Arbre_Droit, Cle);
end if;
end Inserer;
procedure Supprimer (Abr : in out T_ABR ; Cle : in Integer) is
tmp1 ,tmp2 : T_ABR;
begin
if (Abr = Null) then
Null;
else
if (Cle < Abr.all.Cle) then
Supprimer (Abr.all.Sous_Arbre_Gauche, Cle);
elsif (Cle > Abr.all.Cle) then
Supprimer (Abr.all.Sous_Arbre_Droit, Cle);
else
if (Abr.all.Sous_Arbre_Gauche = Null) then
tmp1 := Abr.all.Sous_Arbre_Droit;
Free (Abr);
Abr := tmp1;
elsif (Abr.all.Sous_Arbre_Droit = Null) then
tmp1 := Abr.all.Sous_Arbre_Gauche;
Free (Abr);
Abr := tmp1;
else
tmp2 := Abr.all.Sous_Arbre_Droit;
while (not Est_Vide (tmp2) and tmp2.all.Sous_Arbre_Gauche /= Null) loop
tmp2 := tmp2.all.Sous_Arbre_Gauche;
end loop;
tmp1 := tmp2;
Abr.all.Cle := tmp1.all.Cle;
Supprimer (Abr.all.Sous_Arbre_Droit, tmp1.all.Cle);
end if;
end if;
end if;
end Supprimer;
procedure Vider (Abr : in out T_ABR) is
begin
if not Est_Vide (ABR) then
Vider (ABR.all.Sous_Arbre_Gauche);
Vider (ABR.all.Sous_Arbre_Droit);
free (ABR);
end if;
end Vider;
procedure Afficher (ABR : in T_Abr) is
begin
if Est_Vide (ABR) then
Afficher( Abr.all.Sous_Arbre_Gauche);
Put_Line(Integer'Image(ABR.all.Cle));
Afficher( ABR.all.Sous_Arbre_Droit);
end if;
end Afficher;
procedure Afficher_Debug (Abr : in T_Abr) is
begin
if not Est_Vide (ABR) then
Put_Line (Integer'Image(ABR.all.Cle));
Afficher_Debug ( ABR.all.Sous_Arbre_Gauche);
Afficher_Debug ( ABR.all.Sous_Arbre_Droit);
end if;
end Afficher_Debug;
end ABR;
我为 ABR 模块创建了一个测试文件，但我不知道如何实例化前一个模块：
-- Programme de test du module ABR.
with Ada.Text_IO; use Ada.Text_IO;
with ABR; use ABR;
procedure Test_ABR is
-- Instantiation du package ABR.
package ABR_Test is
new ABR (T_Noeud => xxx);
use ABR_Test;
-- Initialisation des variables.
Nb_Donnees : constant Integer := 10; -- Taille du tableau Cles.
Cles : constant array (1..Nb_Donnees) of Integer -- Cles est un tableau
:= (56, 78, 76, 27, 90, 23, 12, 43, 24, 39); -- contenant des clés.
-- Initialise l'ABR Abr commen un ABR vide dans lequel ont été insérées
-- les cles Cles ci-dessus.
procedure Construire_Exemple_Arbre (Annuaire : out T_ABR) is
begin
Initialiser (Annuaire);
pragma Assert (Est_Vide (Annuaire));
pragma Assert (Taille (Annuaire) = 0);
for i in 1..Nb_Donnees loop
Inserer (Annuaire, Cles (i));
Put_Line ("Après insertion de la clé " & Cles (i));
Afficher_Debug (Annuaire);
New_Line;
pragma Assert (not Est_Vide (Annuaire));
pragma Assert (Taille (Annuaire) = i);
end loop;
Vider (Annuaire);
pragma Assert (Est_Vide (Annuaire));
pragma Assert (Taille (Annuaire) = 0);
Put_Line ("Procédure Construire_Exemple_Arbre est exécuté avec succès.");
New_Line;
end Construire_Exemple_Arbre;
procedure Tester_Exemple_Arbre is
Annuaire : T_ABR;
begin
Construire_Exemple_Arbre (Annuaire);
Vider (Annuaire);
pragma Assert (Est_Vide (Annuaire));
pragma Assert (Taille (Annuaire) = 0);
Put_Line ("Procédure Tester_Exemple_Arbre est exécuté avec succès.");
New_Line;
end Tester_Exemple_Arbre;
-- Tester suppression en commençant par supprimer les feilles.
procedure Tester_Supprimer_Inverse is
Annuaire : T_ABR;
begin
Put_Line ("Tester_Supprimer_Inverse...");
New_Line;
Construire_Exemple_Arbre (Annuaire);
for i in reverse 1..Nb_Donnees loop
Supprimer (Annuaire, Cles (i));
Put_Line ("Après suppression de " & Cles (i) & " :");
Afficher_Debug (Annuaire);
New_Line;
end loop;
Vider (Annuaire);
Put_Line ("Procédure Tester_Supprimer_Inverse est exécuté avec succès.");
New_Line;
end Tester_Supprimer_Inverse;
-- Tester suppression. Suppression de noeuds avec deux fils.
procedure Tester_Supprimer is
Annuaire : T_ABR;
begin
Put("Tester_Supprimer...");
New_Line;
Construire_Exemple_Arbre (Annuaire);
for i in 1..Nb_Donnees loop
Put_Line ("Suppression de " & Cles (i) & " :");
Supprimer (Annuaire, Cles (i));
Afficher_Debug (Annuaire);
New_Line;
end loop;
Vider (Annuaire);
Put_Line ("Procédure Tester_Supprimer est exécuté avec succès.");
New_Line;
end Tester_Supprimer;
begin
Tester_Exemple_Arbre;
--Tester_Supprimer_Inverse;
--Tester_Supprimer;
end Test_ABR;
请帮我解决这个问题
解决方案
你没有说编译器在你的代码中抱怨什么。但是，编译器报告表明您的设计存在严重错误
hamza.ada:82:09: generic type cannot have a completion
（它抱怨你T_Noeud在 package 的私有部分有一个完整的声明ABR）。
你的通用包应该至少有一个形式参数（也许是英文Item）来对应你想要存储在其中的对象的类型。您可能希望有一个相等的形式参数，通常
with function "=" (L, R : Item) return Boolean is <>;
然后，您的通用包应声明一个公共类型以对应于树实例，例如
type Tree (<>) is private;
（或者也许Arbre），然后在私有部分中，您应该声明构建所需的所有支持类型（ T_Noeud， ） 。T_ABRTree
永远不应该由包的用户来声明用于实现抽象的类型。
就目前而言，在代码中实例化的部分问题ABR是完整的声明T_Noeud彻底混淆了编译器，以至于它拒绝实例化，说
designated type of actual does not match that of formal "T_ABR"