C++若何完成狹義表詳解。本站提示廣大學習愛好者：（C++若何完成狹義表詳解）文章只能為提供參考，不一定能成為您想要的結果。以下是C++若何完成狹義表詳解正文
以下給出幾種簡略的狹義表模子：
由上圖我們可以看到，狹義表的節點類型不過head、value、sub三種，這裡設置列舉類型，應用列舉變量來記載每一個節點的類型：
enum Type
{
HEAD, //頭節點
VALUE, //值節點
SUB, //子表節點
};
每一個節點都有本身的類型和next指針，除此以外，假如該節點是VALUE類型還要分派空間存儲該節點的有用值；然則若該節點是SUB類型，就需界說一個指針指向子表的頭。
這裡我們可以用結合來處理這個成績。
（結合（或配合體）是一種分歧數據類型成員之間同享存儲空間的辦法，而且結合體對象在統一時光只能存儲一個成員值）
結構節點：
struct GeneralizedNode
{
Type _type; // 1.類型
GeneralizedNode* _next; //2.指向同層的下一個節點
union
{
char _value; // 3.有用值
GeneralizedNode* _subLink; // 3.指向子表的指針
};
GeneralizedNode(Type type = HEAD, char value = '0')
:_value(value)
,_type(type)
, _next(NULL)
{
if (_type == SUB)
{
_subLink = NULL;
}
}
};
狹義表的界說及根本操作：
class Generalized
{
public:
//無參的結構函數,樹立空的狹義表
Generalized();
//建造狹義表，有參數的結構函數
Generalized(const char* str);
//打印狹義表
void Print();
//獲得值節點的個數
size_t Amount();
//獲得狹義表的深度
size_t Depth();
//拷貝結構
Generalized(const Generalized& g);
////賦值運算符的重載
Generalized& operator=(const Generalized& g);
////析構函數
~Generalized();
protected:
void _Print(GeneralizedNode* head);
GeneralizedNode* _CreatList(const char*& str);
size_t _Amount(GeneralizedNode* head);
GeneralizedNode* _Copy(GeneralizedNode* head);
void _Destory(GeneralizedNode* head);
protected:
GeneralizedNode* _head; //記載狹義表頭指針
};
初始化樹立狹義表停止輪回遞歸。遍歷字符串時碰到字符就樹立值節點，碰到'('就停止遞合並樹立子表；碰到')'就停止以後子表的樹立，並前往以後子表的頭指針。
GeneralizedNode* _CreatList(const char*& str)
{
assert(*str == '(');
GeneralizedNode* head = new GeneralizedNode(HEAD,'0');
GeneralizedNode* cur = head;
str++;
while (str != '\0')
{
if ((*str >= '0'&&*str <= '9') || (*str >= 'a'&&*str <= 'z') || (*str >= 'A'&&*str <= 'Z'))
{
cur->_next = new GeneralizedNode(VALUE, *str);
cur = cur->_next;
}
else if (*str == '(')
{
cur->_next = new GeneralizedNode(SUB);
cur = cur->_next;
cur->_subLink = _CreatList(str);
}
else if (*str == ')')
{
return head;
}
str++;
}
return head;
}
打印狹義表：當節點的類型為SUB時停止遞歸，最初不要忘了每打印完一層要打印一個後括號。
void _Print(GeneralizedNode* head)
{
if (head == NULL)
{
cout << "Generalized table is NULL" << endl;
return;
}
GeneralizedNode* cur = head;
while (cur)
{
if (cur->_type == HEAD)
{
cout << '(';
}
else if (cur->_type == VALUE)
{
cout << cur->_value;
if (cur->_next)
{
cout << ',';
}
}
else if (cur->_type == SUB)
{
_Print(cur->_subLink);
if (cur->_next)
{
cout << ',';
}
}
cur = cur->_next;
}
cout << ')';
}
獲得值節點的個數：設置count變量，碰到值節點就加1，碰到SUB節點停止遞合並將前往值加給count
size_t _Amount(GeneralizedNode* head)
{
GeneralizedNode* begin = head;
size_t count = 0;
while (begin)
{
if (begin->_type == VALUE)
{
count++;
}
if (begin->_type == SUB)
{
count += _Amount(begin->_subLink);
}
begin = begin->_next;
}
return count;
}
狹義表的深度：設置變量dp和max分離用來記載以後子表即以後SUB節點指向的子表深度，和本層一切的SUB節點中深度最年夜的子表的深度。
size_t _Depth(GeneralizedNode* head)
{
if (_head == NULL)
{
return 0;
}
size_t dp=0;
GeneralizedNode* cur = head;
size_t max = 0;
while (cur)
{
if (cur->_type == SUB)
{
dp=_Depth(cur->_subLink);
if (max < dp)
{
max = dp;
}
}
cur = cur->_next;
}
return max+1;
}
燒毀狹義表：順次遍歷節點，碰到子表遞歸，將子表的節點delete完成後，再回到以後層持續遍歷。
void _Destory(GeneralizedNode* head)
{
if (head == NULL)
{
return;
}
while (head)
{
GeneralizedNode* begin = head->_next;
if (head->_type == SUB)
{
_Destory(head->_subLink);
}
delete head;
head = begin;
}
}
實例演示
界說：
狹義表是n(n≥0)個元素a1，a2，…，ai，…，an的無限序列。
個中：
①ai--或許是原子或許是一個狹義表。
②狹義表平日記作：
Ls=( a1，a2，…，ai，…，an)。
③Ls是狹義表的名字，n為它的長度。
④若ai是狹義表，則稱它為Ls的子表。
留意：
①狹義表平日用圓括號括起來，用逗號分隔個中的元素。
②為了辨別原子和狹義表，書寫時用年夜寫字母表現狹義表，用小寫字母表現原子。
③若狹義表Ls非空(n≥1)，則al是LS的表頭，其他元素構成的表(a1，a2，…，an)稱為Ls的表尾。
④狹義表是遞歸界說的
繪圖舉例：
代碼完成：
[cpp] view plain copy
#include <iostream>
using namespace std;
//表現狹義表的結點類型
enum NodeType
{
HEAD_TYPE,//頭結點類型
VALUE_TYPE,//值結點類型
SUB_TYPE//子表類型
};
//表現狹義表結點的構造體
struct GeneraListNode
{
NodeType _type;//結點類型
GeneraListNode *_next;//寄存結點的下一個元素的地址
//一個結點要末是值結點要末是子表，故用結合體來寄存節儉必定的空間
//若是值結點則寄存的是值，是子表結點的話寄存的是子表結颔首結點的地址
union{
char _value;
GeneraListNode *_subLink;
};
GeneraListNode(NodeType type = HEAD_TYPE, char value = '\0')
:_type(type)
,_next(NULL)
{
if (type == VALUE_TYPE)
{
_value = value;
}else if(type == SUB_TYPE)
{
_subLink = NULL;
}
}
};
class GeneraList
{
private:
GeneraListNode *_link;//用來寄存狹義表頭結點地址
public:
GeneraList(const char *str)
:_link(NULL)
{
_CreateGeneraList(_link, str);//依據指定序列創立狹義表
}
~GeneraList()
{}
public:
void Print();//對外供給的打印狹義表的接口
int Size();//狹義表中值結點的數量的對外獲得接口
int Depth();//狹義表的最深條理的對外獲得接口
private:
void _CreateGeneraList(GeneraListNode *& link, const char *& str);
bool _IsValue(const char ch);//斷定指定字符能否為值結點所許可的類型
int _Size(GeneraListNode *head);//盤算狹義表中值結點的數量的完成
int _Depth(GeneraListNode *head);//盤算狹義表的最深條理的完成
void _Print(GeneraListNode *link);//打印狹義表的接口的底層完成
};
//創立狹義表
void GeneraList::_CreateGeneraList(GeneraListNode *& link, const char *& str)
{
//狹義表最前端有一個頭結點，用來記載完成狹義表鏈表的首地址
//故每次挪用該創立狹義表的函數起首創立一個頭結點
GeneraListNode* head = new GeneraListNode(HEAD_TYPE, NULL);
head->_next = NULL;
link = head;
GeneraListNode* cur = link;//用來記載創立狹義表鏈表時以後創立出的結點地位游標指針
str++;//將狹義表序列後移,相當於跳過了'('
while(*str != '\0')
{
if(_IsValue(*str)){//假如以後掃描到的字符是值
//創立一個值結點
GeneraListNode* newNode = new GeneraListNode(VALUE_TYPE, *str);
newNode->_next = NULL;
cur->_next = newNode;//將該值結點參加到鏈表中
cur = cur->_next;//游標後移
str++;//將狹義表序列後移
}else if(*str == '('){//假如掃描到'('創立子表結點
GeneraListNode* subLink = new GeneraListNode(SUB_TYPE, NULL);
subLink->_next = NULL;
cur->_next = subLink;//將子表結點參加到鏈表中
cur = cur->_next;
_CreateGeneraList(cur->_subLink, str);//遞歸創立子表
}else if(*str == ')'){
str++;
return;//若掃描到')'表現狹義表創立停止
}else{
str++;//空格等其他有效字符跳過
}
}
}
int GeneraList::Size()
{
return _Size(_link);
}
//盤算狹義表值結點的個數
int GeneraList::_Size(GeneraListNode *head)
{
int size = 0;
GeneraListNode *cur = head;
while(cur != NULL){
if(cur->_type == VALUE_TYPE){
++size;//碰到值結點則將size加一
}else if(cur->_type == SUB_TYPE){
size += _Size(cur->_subLink);//碰到子表停止遞歸
}
cur = cur->_next;
}
return size;
}
int GeneraList::Depth()
{
return _Depth(_link);
}
int GeneraList::_Depth(GeneraListNode *head)
{
int depth = 1,maxDepth = 1;//depth表現以後表的深度，maxDepth表現今朝最年夜的深度
GeneraListNode *cur = head;
while(cur != NULL){
if(cur->_type == SUB_TYPE){
depth += _Depth(cur->_subLink);
}
if(depth > maxDepth){//更新最年夜深度
maxDepth = depth;
depth = 1;//將以後深度復位
}
cur = cur->_next;
}
return maxDepth;
}
void GeneraList::Print()
{
_Print(_link);
cout<<endl;
}
//打印狹義表
void GeneraList::_Print(GeneraListNode *link)
{
GeneraListNode *cur = link;//遍歷狹義表的游標
while(cur != NULL){
if(cur->_type == VALUE_TYPE){
cout<<cur->_value;
if(cur->_next != NULL)
{
cout<<',';
}
}else if(cur->_type == HEAD_TYPE){
cout<<"(";
}else if(cur->_type == SUB_TYPE){
_Print(cur->_subLink);//碰到子表遞歸打印
if(cur->_next != NULL)//假如打印完子表後狹義表未停止則打印','
{
cout<<",";
}
}
cur = cur->_next;
}
cout<<")";
}
bool GeneraList::_IsValue(const char ch)
{
if(ch >= 'a' && ch <= 'z' ||
ch >= 'A' && ch <= 'Z' ||
ch >= '0' && ch <= '(')
{
return true;
}
return false;
}
測試代碼
[cpp] view plain copy
#include"GeneraList.hpp"
//測試空表
void Test1()
{
GeneraList genList("()");
genList.Print();
cout<<"Size is :"<<genList.Size()<<endl;
cout<<"Depth is :"<<genList.Depth()<<endl<<endl;
}
//測試單層表
void Test2()
{
GeneraList genList("(a,b)");
genList.Print();
cout<<"Size is :"<<genList.Size()<<endl;
cout<<"Depth is :"<<genList.Depth()<<endl<<endl;
}
//測試雙層表
void Test3()
{
GeneraList genList("(a,b,(c,d))");
genList.Print();
cout<<"Size is :"<<genList.Size()<<endl;
cout<<"Depth is :"<<genList.Depth()<<endl<<endl;
}
//測試多層表
void Test4()
{
GeneraList genList("(a,b,(c,d),(e,(f),h))");
genList.Print();
cout<<"Size is :"<<genList.Size()<<endl;
cout<<"Depth is :"<<genList.Depth()<<endl<<endl;
}
//測試多層空表
void Test5()
{
GeneraList genList("(((),()),())");
genList.Print();
cout<<"Size is :"<<genList.Size()<<endl;
cout<<"Depth is :"<<genList.Depth()<<endl<<endl;
}
int main()
{
Test1();
Test2();
Test3();
Test4();
Test5();
return 0;
}
運轉成果
總結
以上就是關於C++若何完成狹義表詳解的全體內容，願望對有須要的人能有所贊助，假如有疑問迎接年夜家留言評論辯論。
