devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++常用数据结构_c++数据结构

作者：知新_RL | 2024-05-01 01:15:15

赞

踩

c++数据结构

                                                                                  常用数据结构

1.线性表

定义：

  • 由n个具有相同性质的数据元素组成的有穷序列。

特点：

（一对一的关系）

  • 存在唯一一个称为”第一个“的数据元素，它没有直接的前驱。
  • 存在唯一一个称为“最后一个”的元素，他没有直接后驱。
  • 除第一个数据元素以外，表中的每个数据元素有且仅有一个直接前驱。
  • 除第一个数据元素以外，表中的每个数据元素有且仅有一个直接后驱。

​1.1顺序表

定义：

  • 用一组地址连续的存储单元依次存储线性表中每个数据元素。

特点：

  •  逻辑关系相邻的两个元素在物理位置上也相邻。

Image result for 顺序表

​

实现：

  • c语言实现：
  1. typedef struct {
  2.     int items[LISTSIZE];
  3.     int length;
  4. } SqList;
  • length:线性表当前的长度。
  • LISTSIZE：最大容量。
  • c++实现：
  1. ​
  2. template <typename T>
  3. class sqlist{
  4. public:
  5.     sqlist(int maxsize=10):Maxsize(maxsize)
  6.     {
  7.         elements=new T[maxsize];
  8.         length=0;
  9.     }
  10. private:
  11.     int  Maxsize;//最大容量
  12.     T *elements;//元素初始地址
  13.     int length;//当前有效长度
  14. };
  15.  
  16. ​

基本操作：

  • 初始化顺序表

  1. //初始化顺序表，表的长度设置为0
  2. void InitList(SqList *L)
  3. {
  4.     L->length=0;
  5. }

  • 求顺序表中当前元素的个数

  1. //顺序表的长度
  2. int ListLength(SqList * L)
  3. {
  4.     return  L->length;
  5. }

  • 判断顺序表是否为空

  1. //判断顺序表是否为空
  2. bool ListEmpty(SqList *L)
  3. {
  4.     if(L->length==0)
  5.         return true;
  6.     else
  7.         return false;
  8. }

  • 向顺序表中插入数据元素

  1. //向顺序表中插入数据元素
  2. bool ListInsert(SqList *L,int pos,int item)
  3. {
  4.     int i;
  5.     if(L->length==LISTSIZE)
  6.     {
  7.         printf("顺序列表已满，无法进行插入操作");
  8.         return false;
  9.     }
  10.     if(pos<1||pos>L->length+1)
  11.     {
  12.         printf("插入位置不合法");
  13.         return false;
  14.     }
  15.     for(i=L->length-1;i>=pos-1;i--)
  16.     {
  17.         L->items[i+1]=L->items[i];
  18.     }
  19.     L->items[pos-1]=item;
  20.     L->length++;
  21.  
  22.     return true;
  23.  
  24. }

  • 删除顺序表中的元素

  1. //删除顺序表中的元素
  2. bool ListDelete(SqList *L,int pos,int *item)
  3. {
  4.     int i;
  5.     if(L->length==0)
  6.     {
  7.         printf("顺序表为空表");
  8.         return false;
  9.     }
  10.     if(pos<1||pos>L->length)
  11.     {
  12.         printf("删除位置无效");
  13.     }
  14.     *item=L->items[pos-1];
  15.     for(int i=pos-1;i<L->length-1;i++)
  16.     {
  17.         L->items[i]=L->items[i+1];
  18.     }
  19.     L->length--;
  20.     return true;
  21. }

  • 查找指定元素在顺序表中的位置

  1. //查找制定元素在顺序表中的位置
  2. int Find(SqList L,int item)
  3. {
  4.     int pos=0;
  5.     if(ListEmpty(&L))
  6.     {
  7.         printf("顺序表为空表，无法进行查找操作");
  8.         return 0;
  9.     }
  10.     while(pos<L.length&&L.items[pos]!=item)
  11.     {
  12.         pos++;
  13.     }
  14.     if(pos<L.length)
  15.         return pos+1;
  16.     else
  17.         return 0;
  18. }

  • 获取顺序表中指定位置上的数据元素

  1. //获得顺序表中指定位置上的数据元素
  2. int GetElem(SqList *L,int pos,int *item)
  3. {
  4.     if(ListEmpty(L))
  5.         return 0;
  6.     if(pos<1||pos>L->length)
  7.         return 0;
  8.     *item=L->items[pos-1];
  9.     return 1;
  10. }
  • 遍历顺序表
  1. //遍历顺序表
  2. void TravereList(SqList *L)
  3. {
  4.     int pos =0;
  5.     while(pos<L->length)
  6.     {
  7.         printf("item1: %d",L->items[pos]);
  8.         pos++;
  9.     }
  10. }

c语言版本： 

  1.  
  2. #include <iostream>
  3. using namespace std;
  4. #define LISTSIZE 100
  5.  
  6.  
  7. typedef struct {
  8.     int items[LISTSIZE];
  9.     int length;
  10. } SqList;
  11.  
  12. //初始化顺序表，表的长度设置为0
  13. void InitList(SqList *L)
  14. {
  15.     L->length=0;
  16. }
  17.  
  18. //顺序表的长度
  19. int ListLength(SqList * L)
  20. {
  21.     return  L->length;
  22. }
  23.  
  24. //判断顺序表是否为空
  25. bool ListEmpty(SqList *L)
  26. {
  27.     if(L->length==0)
  28.         return true;
  29.     else
  30.         return false;
  31. }
  32.  
  33. //向顺序表中插入数据元素
  34. bool ListInsert(SqList *L,int pos,int item)
  35. {
  36.     int i;
  37.     if(L->length==LISTSIZE)
  38.     {
  39.         printf("顺序列表已满，无法进行插入操作");
  40.         return false;
  41.     }
  42.     if(pos<1||pos>L->length+1)
  43.     {
  44.         printf("插入位置不合法");
  45.         return false;
  46.     }
  47.     for(i=L->length-1;i>=pos-1;i--)
  48.     {
  49.         L->items[i+1]=L->items[i];
  50.     }
  51.     L->items[pos-1]=item;
  52.     L->length++;
  53.  
  54.     return true;
  55.  
  56. }
  57.  
  58. //删除顺序表中的元素
  59. bool ListDelete(SqList *L,int pos,int *item)
  60. {
  61.     int i;
  62.     if(L->length==0)
  63.     {
  64.         printf("顺序表为空表");
  65.         return false;
  66.     }
  67.     if(pos<1||pos>L->length)
  68.     {
  69.         printf("删除位置无效");
  70.     }
  71.     *item=L->items[pos-1];
  72.     for(int i=pos-1;i<L->length-1;i++)
  73.     {
  74.         L->items[i]=L->items[i+1];
  75.     }
  76.     L->length--;
  77.     return true;
  78. }
  79.  
  80. //查找制定元素在顺序表中的位置
  81. int Find(SqList L,int item)
  82. {
  83.     int pos=0;
  84.     if(ListEmpty(&L))
  85.     {
  86.         printf("顺序表为空表，无法进行查找操作");
  87.         return 0;
  88.     }
  89.     while(pos<L.length&&L.items[pos]!=item)
  90.     {
  91.         pos++;
  92.     }
  93.     if(pos<L.length)
  94.         return pos+1;
  95.     else
  96.         return 0;
  97. }
  98.  
  99. //获得顺序表中指定位置上的数据元素
  100. int GetElem(SqList *L,int pos,int *item)
  101. {
  102.     if(ListEmpty(L))
  103.         return 0;
  104.     if(pos<1||pos>L->length)
  105.         return 0;
  106.     *item=L->items[pos-1];
  107.     return 1;
  108. }
  109.  
  110. //遍历顺序表
  111. void TravereList(SqList *L)
  112. {
  113.     int pos =0;
  114.     while(pos<L->length)
  115.     {
  116.         printf("item1: %d",L->items[pos]);
  117.         pos++;
  118.     }
  119. }
  120.  
  121. int main()
  122. {
  123.     SqList Fibonacci;
  124.     cout<<"建立顺序表"<<endl;
  125.     InitList(&Fibonacci);
  126.     for(int i=0;i<7;)
  127.     {
  128.         int num;
  129.         cin>>num;
  130.         if(ListInsert(&Fibonacci,i+1,num))
  131.             i++;
  132.     }
  133.     TravereList(&Fibonacci);
  134.     int item;
  135.     ListDelete(&Fibonacci,7,&item);
  136.     TravereList(&Fibonacci);
  137.     return 0;
  138. }

c++版本：

  1. #include<iostream>
  2. using namespace std;
  3. template <typename T>
  4. class sqlist{
  5. public:
  6.     sqlist(int maxsize=10):Maxsize(maxsize)
  7.     {
  8.         elements=new T[maxsize];
  9.         length=0;
  10.     }
  11.     //打印顺序表的长度
  12.     int listLength()
  13.     {
  14.         return length;
  15.     }
  16.     //判断顺序表是否为空
  17.     bool IsEmpty()
  18.     {
  19.         return length==0;
  20.     }
  21.     //顺序表中插入元素
  22.     void InsertElement(T elem,int position)
  23.     {
  24.         if(IsEmpty())
  25.         {
  26.             elements[length++]=elem;
  27.         }
  28.         else
  29.         {
  30.             for(int i=length;i>=position;i--)
  31.                 elements[i]=elements[i-1];
  32.             elements[position-1]=elem;
  33.             length++;
  34.         }
  35.     }
  36.     //顺序表中删除元素
  37.     void DelElement(T elem,int position)
  38.     {
  39.         T del_elem=elements[position-1];
  40.         for(int i=position-1;i<length-1;i++)
  41.             elements[i]=elements[i+1];
  42.         length--;
  43.     }
  44.     //查找元素的位置
  45.     int FindElement(T elem)
  46.     {
  47.         int i;
  48.         for(i=0;i<length;i++)
  49.         {
  50.             if(elements[i]==elem)
  51.             {
  52.                 std::cout<<"i: "<<i<<std::endl;
  53.                 break;
  54.             }
  55.         }
  56.         if(i==length)
  57.         {
  58.             std::cout<<"find not"<<std::endl;
  59.             return -1;
  60.         }
  61.         else
  62.         {
  63.             std::cout<<"find yes"<<std::endl;
  64.             return i;
  65.         }
  66.     }
  67.     //打印
  68.     void Printf()
  69.     {
  70.         for(int i=0;i<length;i++)
  71.             std::cout<<elements[i]<<" ";
  72.         std::cout<<std::endl;
  73.     }
  74. private:
  75.     int  Maxsize;//最大容量
  76.     T *elements;//元素初始地址
  77.     int length;//当前有效长度
  78. };
  79. int main()
  80. {
  81.     sqlist<int> sq(20);
  82.     sq.InsertElement(10,2);
  83.     sq.Printf();
  84.     sq.InsertElement(30,1);
  85.     sq.Printf();
  86.     sq.InsertElement(50,1);
  87.     sq.Printf();
  88.     sq.InsertElement(100,2);
  89.     sq.Printf();
  90.     sq.DelElement(30,3);
  91.     sq.Printf();
  92.     sq.FindElement(100);
  93.     return 0;
  94. }

1.2链表 

定义：

  • 用一组任意的存储单元存储线性表中的数据元素。

特点：

  • 相比顺序存储结构，链式存储结构中，除了需要存储数据元素信息之外，还需要存储它的后继元素的存储地址(指针)。
  • 单链表结点的物理位置不一定连续，单链表逻辑上通过指针实现连续。
  • 单链表有一个头结点和一个尾结点，并且只有尾结点没有后继结点，其他结点有且仅有一个后继结点。
  • 只要知道了链表的头结点，就可以遍历整个链表。
     

​

  • 单链表的每一个结点包含两部分：数据域和指针域。
  • 表头：用来存放第一个结点的地址。
  • 表尾：表尾没有后继，所以尾结点的指针域为空指针（NULL）。

 实现：

  • c语言定义：
  1. typedef struct node{
  2. 	int data;//数据域 
  3. 	node * next;//指针域 
  4. }LNode,*LinkList;//LinkList是指向LNode类型数据的指针类型定义
  • LinkList是指向LNode类型数据的指针类型定义 ，也就是说，在定义一个指向LNode类型数据的指针变量时，语句
LNode *L;

和

LinkList L;

是等价的。

  • c++定义：
  1. class ListNode{
  2. 	public:		
  3. 		ListNode * next;
  4. 		int data;
  5. };
  6. class LinkList
  7. {
  8. public:
  9. 	LinkList()
  10. 	{
  11. 		node=new ListNode;
  12. 		node->next=NULL;
  13. 	}
  14. 	~LinkList()
  15. 	{
  16. 		delete node;
  17. 	}
  18. 	void CreateLinkListBack(int n);
  19. 	void CreateLinkListHead(int n);
  20. 	void InsertNode(int position,int elem);
  21. 	void removeNode(ListNode* p); 
  22. 	ListNode* findNode(int value);
  23. 	void PrintLinkList();
  24. public:
  25. 		ListNode *node;
  26. };

基本操作：

  • 初始化链表
  1. //初始化链表 
  2. LinkList init_list() 
  3. {
  4. 	LinkList L=new LNode;
  5. 	if(!L)
  6. 		return NULL;
  7. 	L->next=NULL;//指针域置空 
  8. 	return L;	
  9. }
  • 打印链表
  1. //打印链表
  2. void Printf_list(LinkList &L)
  3. {
  4. 	LinkList temp=L->next;
  5. 	while(temp!=NULL)
  6. 	{
  7. 		cout<<temp->data<<"->";
  8. 		temp=temp->next;
  9. 	}
  10.  }
  •  插入数据（头插）

步骤：

  1. 先创建一个新节点s(LinkList),并给数据域赋值，
  2. 新节点的指针域指向L-next,
  3. L的指针域next指向s。

​

  1. //插入数据（头插）
  2. void create_LinkList(LinkList &L,int n)
  3. {	
  4. 	while(n--)
  5. 	{
  6. 		LinkList s=new LNode;
  7. 		cin>>s->data;
  8. 		s->next=L->next;
  9. 		L->next=s;	
  10. 	} 		
  11. }

 

注意：使用头插法插入数据后，链表中数据的顺序和插入前的数据顺序相反。 

  • 插入数据（尾插）

步骤：

  1. 先让r节点指向尾结点，
  2. 创建一个新节点s(LinkList),并给数据域赋值，且s->next为NULL，因为s为尾结点，
  3. r的指针域指向s,
  4. 更新尾节点，即r=s。

​

  1. //插入数据（尾插）
  2. void create_LinkList_back(LinkList &L,int n)
  3. {
  4. 	LinkList r=L;
  5. 	while(n--)
  6. 	{
  7. 		LinkList s=new LNode;
  8. 		cin>>s->data;
  9. 		s->next=NULL;
  10. 		r->next=s;
  11. 		r=s;
  12. 		
  13. 	}
  14. 	
  15. }

 注意：使用尾插法插入数据后，链表中数据的顺序和插入前的数据顺序相同。 

  • 在指定位置插入数据
  1.  //插入数据
  2. void InsertList(LinkList q,int e)
  3. {
  4. 	LinkList p=new LNode;
  5. 	p->data=e;
  6.  
  7. 	p->next=q->next;
  8. 	q->next=p;
  9. 		 	 	
  10. }

 

  • 查找相应数据
  1. LinkList Get_elem(LinkList &L,int e)
  2. {
  3. 	LinkList temp=L->next;
  4. 	while(temp!=NULL)
  5. 	{
  6. 		if(e==temp->data)
  7. 		{
  8. 			return temp;
  9. 		}
  10. 		temp=temp->next;		
  11. 	}
  12. 	return NULL;
  13. 		
  14. }

完整程序

  1. #include<iostream> 
  2.  
  3. using namespace std;
  4.  
  5. typedef struct node{
  6. 	int data;//数据域 
  7. 	struct node * next;//指针域 
  8. }LNode,*LinkList;//LinkList是指向LNode类型数据的指针类型定义 
  9.  
  10. //初始化链表 
  11. LinkList init_list()//引用 
  12. {
  13. 	LinkList L=new LNode;
  14. 	if(!L)
  15. 		return NULL;
  16. 	L->next=NULL;//指针域置空 
  17. 	return L;	
  18. }
  19. //插入数据（头插）
  20. void create_LinkList(LinkList &L,int n)
  21. {	
  22. 	while(n--)
  23. 	{
  24. 		LinkList s=new LNode;
  25. 		cin>>s->data;
  26. 		s->next=L->next;
  27. 		L->next=s;	
  28. 	} 		
  29. } 
  30. //插入数据（尾插）
  31. void create_LinkList_back(LinkList &L,int n)
  32. {
  33. 	LinkList r=L;
  34. 	while(n--)
  35. 	{
  36. 		LinkList s=new LNode;
  37. 		cin>>s->data;
  38. 		s->next=NULL;
  39. 		r->next=s;
  40. 		r=s;
  41. 		
  42. 	}
  43. 	
  44. } 
  45. //打印链表
  46. void Printf_list(LinkList &L)
  47. {
  48. 	LinkList temp=L->next;
  49. 	while(temp!=NULL)
  50. 	{
  51. 		cout<<temp->data<<"->";
  52. 		temp=temp->next;
  53. 	}
  54. 	cout<<endl;
  55.  } 
  56.  //插入数据
  57. void InsertList(LinkList q,int e)
  58. {
  59. 	LinkList p=new LNode;
  60. 	p->data=e;
  61.  
  62. 	p->next=q->next;
  63. 	q->next=p;
  64. 		 	 	
  65. }
  66. LinkList Get_elem(LinkList &L,int e)
  67. {
  68. 	LinkList temp=L->next;
  69. 	while(temp!=NULL)
  70. 	{
  71. 		if(e==temp->data)
  72. 		{
  73. 			return temp;
  74. 		}
  75. 		temp=temp->next;		
  76. 	}
  77. 	return NULL;
  78. 		
  79. } 
  80. int main()
  81. {
  82. 	LinkList L=init_list();
  83. 	if(!L)
  84. 	{
  85. 		cout<<"初始化失败"<<endl;
  86. 		return 0; 
  87. 	} 
  88. 	cout<<"初始化成功"<<endl;
  89. 	int num;
  90. 	cout<<"请输入插入的数量："<<endl;
  91. 	cin>>num;
  92. 	create_LinkList_back(L,num);	
  93. 	Printf_list(L);	
  94. 	int elem;
  95. 	LinkList elem_list;
  96. 	cout<<"请输入需要查找的数"<<endl; 	
  97. 	cin>>elem;
  98. 	elem_list=Get_elem(L,elem);
  99. 	while(!elem_list) 
  100. 	{
  101. 		cout<<"没有查找到，请重新输入"<<endl;
  102. 		cin>>elem; 
  103. 		elem_list=Get_elem(L,elem);
  104. 	}
  105. 	cout<<"找到相应数据，数据地址为："<<elem_list<<endl;
  106. 	if(elem_list!=NULL)
  107. 	{
  108. 		cout<<"请输入需要插入的数"<<endl;
  109. 		int elem_insert;
  110. 		cin>>elem_insert; 	
  111. 		InsertList(elem_list,elem_insert); 
  112. 		Printf_list(L);
  113. 	} 
  114. 	return 0;
  115. }

c++版本：

  1. #include <iostream>
  2. using namespace std;
  3. class ListNode{
  4. 	public:		
  5. 		ListNode * next;
  6. 		int data;
  7. };
  8. class LinkList
  9. {
  10. public:
  11. 	LinkList()
  12. 	{
  13. 		node=new ListNode;
  14. 		node->next=NULL;
  15. 	}
  16. 	~LinkList()
  17. 	{
  18. 		delete node;
  19. 	}
  20. 	void CreateLinkListBack(int n);
  21. 	void CreateLinkListHead(int n);
  22. 	void InsertNode(int position,int elem);
  23. 	void removeNode(ListNode* p); 
  24. 	ListNode* findNode(int value);
  25. 	void PrintLinkList();
  26. public:
  27. 		ListNode *node;
  28. };
  29. //头插 
  30. void LinkList::CreateLinkListHead(int n)
  31. {
  32. 	while(n--)
  33. 	{
  34. 		//插入的数据 
  35. 		ListNode* l=new ListNode;
  36. 		cin>>l->data;
  37. 		l->next=node->next;
  38. 		node->next=l;
  39. 	}
  40. }
  41. //尾插 
  42. void LinkList::CreateLinkListBack(int n)
  43. {
  44. 	ListNode* r=node;
  45. 	while(n--)
  46. 	{
  47. 		ListNode* l=new ListNode;
  48. 		cin>>l->data;
  49. 		l->next=NULL;
  50. 		r->next=l;
  51. 		r=l;
  52. 	}
  53. 	
  54. }
  55. //在第i个位置插入元素 
  56. void LinkList::InsertNode(int position,int elem)
  57. {
  58. 	int j;
  59. 	ListNode* p=node->next;
  60. 	for(j=1;j<position-1;j++)
  61. 	{
  62. 		p=p->next;
  63. 		if(p==NULL)
  64. 			break;
  65. 	}
  66. 	if(p==NULL &&j<(position-1))
  67. 		return ;
  68. //	while(p)
  69. //	{
  70. //		j++;
  71. //		if(j==position)
  72. //			break;
  73. //		p=p->next;
  74. //	}
  75. 	ListNode* q=new ListNode;
  76. 	q->data=elem;
  77. 	q->next=p->next;
  78. 	p->next=q;
  79. }
  80. //移除节点 
  81. void LinkList::removeNode(ListNode* p)
  82. {
  83. 	if(p==NULL)
  84. 		return;
  85. 	ListNode* temp=node;
  86. 	while(temp->next!=p)
  87. 	{
  88. 		temp=temp->next;		
  89. 	}
  90. 	temp->next=p->next;
  91. 	delete p;
  92. }
  93. //寻找某节点 
  94. ListNode* LinkList::findNode(int value)
  95. {
  96. 	ListNode* temp=node->next;
  97. 	while(temp)
  98. 	{
  99. 		if(temp->data==value)
  100. 			return temp;
  101. 		temp=temp->next;
  102. 	}
  103. 	return NULL;
  104. 	
  105. }
  106. //打印链表 
  107. void LinkList::PrintLinkList()
  108. {
  109. 	ListNode* temp=node->next;
  110. 	while(temp)
  111. 	{
  112. 		cout<<temp->data<<"->";
  113. 		temp=temp->next;
  114. 	}
  115. 	std::cout<<std::endl;
  116. }
  117.  
  118. int main()
  119. {
  120. 	LinkList list;
  121. 	list.CreateLinkListHead(5);
  122. 	list.PrintLinkList();
  123. 	list.InsertNode(4,9);
  124. 	list.PrintLinkList();
  125. 	ListNode* address=list.findNode(2);
  126. 	list.removeNode(address);
  127. 	list.PrintLinkList();
  128. 	return 0;
  129. }

2.栈

  • 定义：

栈（stack）是一种元素满足后进先出（Last in first out， LIFO）规则的线性表。

​

  • 特点：

  • 栈的本质是一种线性表， 但是具有其特殊的操作要求——元素后进先出。这种要求也决定了栈的操作是在表尾进行
  • 栈底（bottom）：栈的表头
  • 栈顶（top）：将栈的表尾，所以栈的所有操作都是在栈顶进行的。
  • 添加元素，称为入栈（push）；删除元素，称为出栈（pop）。

  • 实现：

栈可以用顺序存储实现，也可以用链式存储实现，分别成为顺序栈和链栈。但一般使用顺序存储实现，因为栈不允许在栈中间进行插入和删除，需要准寻栈特有的规则。

  • 动态实现 
  1. typedef struct SqStack_dynamic{
  2. 	int* base;//栈底 
  3. 	int* top;//栈顶 
  4. }SqStack_dynamic;
  • 静态实现
  1. typedef struct SqStack_static{
  2. 	int data[Maxsize];
  3. 	int top;//栈顶 
  4. }SqStack_static;
  • C++
  1. class stack_static{
  2. 	public:
  3. 		stack_static()
  4. 		{
  5. 			MaxSize=10;
  6. 			top=0;	
  7. 			data= new int[MaxSize];				
  8. 		}
  9. 		void push(int e);
  10. 		void pop(int &e);
  11. 		void GetTop(int &e);
  12. 	private:
  13. 		int MaxSize;
  14. 		int top;
  15. 		int *data;
  16. };

 操作： 

  • 初始化
  1. void InitStack(SqStack_dynamic &stack)
  2. {
  3. 	stack.base= new int[Maxsize];
  4. 	stack.top=stack.base;
  5. }
  • 入栈
  1. void push(SqStack_dynamic &stack,int e)
  2. {
  3. 	if((stack.top-stack.base)>=Maxsize)
  4. 		return;
  5. 	*stack.top=e;
  6. 	stack.top++;
  7. }
  1. void stack_static::push(int e)
  2. {
  3. 	data[top]=e;
  4. 	top++;
  5. }
  • 出栈
  1. void pop(SqStack_dynamic &stack,int &e)
  2. {
  3. 	if(stack.base==stack.top)
  4. 		return;
  5. 	stack.top--;
  6. 	e=*stack.top;	
  7. }
  1. void stack_static::pop(int &e)
  2. {
  3. 	top--;
  4. 	e=data[top];
  5. }
  •  栈顶元素
  1. int GetTop(SqStack_dynamic &stack)
  2. {
  3. 	if(stack.base!=stack.top)
  4. 		return *(stack.top-1);
  5. 	else
  6. 		return -1;
  7. }
  1. void stack_static::GetTop(int &e)
  2. {
  3. 	if(top!=MaxSize)
  4. 		e=data[top-1];
  5. 	else
  6. 		e=-1;
  7. }

 完整程序

  1. #include<iostream>
  2. using namespace std;
  3. #define Maxsize 100
  4. typedef struct SqStack_dynamic{
  5. 	int* base;//栈底 
  6. 	int* top;//栈顶 
  7. }SqStack_dynamic;
  8.  
  9. class stack_static{
  10. 	public:
  11. 		stack_static()
  12. 		{
  13. 			MaxSize=10;
  14. 			top=0;	
  15. 			data= new int[MaxSize];				
  16. 		}
  17. 		void push(int e);
  18. 		void pop(int &e);
  19. 		void GetTop(int &e);
  20. 	private:
  21. 		int MaxSize;
  22. 		int top;
  23. 		int *data;
  24. };
  25. void stack_static::push(int e)
  26. {
  27. 	data[top]=e;
  28. 	top++;
  29. }
  30. void stack_static::pop(int &e)
  31. {
  32. 	top--;
  33. 	e=data[top];
  34. }
  35. void stack_static::GetTop(int &e)
  36. {
  37. 	if(top!=MaxSize)
  38. 		e=data[top-1];
  39. 	else
  40. 		e=-1;
  41. }
  42. void InitStack(SqStack_dynamic &stack)
  43. {
  44. 	stack.base= new int[Maxsize];
  45. 	stack.top=stack.base;
  46. }
  47. void push(SqStack_dynamic &stack,int e)
  48. {
  49. 	if((stack.top-stack.base)>=Maxsize)
  50. 		return;
  51. 	*stack.top=e;
  52. 	stack.top++;
  53. }
  54. void pop(SqStack_dynamic &stack,int &e)
  55. {
  56. 	if(stack.base==stack.top)
  57. 		return;
  58. 	stack.top--;
  59. 	e=*stack.top;	
  60. }
  61. int GetTop(SqStack_dynamic &stack)
  62. {
  63. 	if(stack.base!=stack.top)
  64. 		return *(stack.top-1);
  65. 	else
  66. 		return -1;
  67. }
  68. int main()
  69. {
  70. 	SqStack_dynamic stack;
  71. 	InitStack(stack);
  72. 	push(stack,2);
  73. 	push(stack,5);
  74. 	push(stack,10);
  75. 	std::cout<<"------dynamic stack-----"<<std::endl;
  76. 	
  77. 	int num;
  78. 	pop(stack,num);
  79. 	std::cout<<num<<" ";
  80. 	pop(stack,num);
  81. 	std::cout<<num<<" ";
  82. 	pop(stack,num);
  83. 	std::cout<<num<<" ";
  84. 	
  85. 	stack_static stack_s;
  86. 	stack_s.push(5);
  87. 	stack_s.push(10);
  88. 	stack_s.push(20);
  89. 	std::cout<<std::endl;
  90. 	std::cout<<"------static stack-----"<<std::endl;
  91. 	int num_s;
  92. 	stack_s.pop(num_s);
  93. 	std::cout<<num_s<<" ";
  94. 	stack_s.pop(num_s);
  95. 	std::cout<<num_s<<" ";
  96. 	stack_s.pop(num_s);
  97. 	std::cout<<num_s<<" ";
  98. 	
  99. 	return 0;	
  100. }

 3.树

1.定义

树是指由 n(n≥0)个结点组成的有穷集合 D 与 D 上的关系的集合 R构成的结构，通常我们用 T 表示。树需要满足以下 3 个条件：

  • 当 n=0 时，该结点集合为空，该树被称为空树。
  • 在任意的非空树中，有且仅有一个根结点 root。
  • 当 n>1 时 ，除根结点以外的其余结点可以分为 m(m>0)个不相交的子集D1,D2,D3,…,Dm， 其中每一个这样的子集 Di(i≤m)本身又是一棵树， 称为根结点 root的子树

注意：

  • 树的定义是一个递归定义，因为树是由根结点和子树构成的，而每一个子树也是一棵树。
  • 从图中我们还了解，树结构在形式上最主要的特点就是分层特点和具有一定的排列顺序。
     

​

 2.树的表示方法

  • 树形表示法

​

  • 文氏图表示法

​

3.基本术语

  • 结点的度

结点拥有的直接子树数目。如图 A结点的度为3，B结点的度为2，c结点的度为1，D结点的度为3，E、F、G、H、I 以及J度都为0

​

  • 树的度

树中各结点度的最大值称为该树的度。如上图，树的度为3.

  • 分支结点

度不为 0 的结点称为分支结点或普通结点。

  • 叶子结点

度为 0 的结点称为叶子结点或终端结点。由此可知叶子结点没有子结点。

  • 结点的层次

从树的根结点开始，根结点为第 1 层，根结点的子结点为第 2 层，第 2 层结点的子结点为第 3 层……

  • 树的深度

树中结点的最大层次数被定义为该树的深度或高度。

  • 森林

n(n≥0)棵不相交的树的集合称为森林。

4.基本结构 

  • 二叉树具有的几种形态

​

5.性质 

6. 存储方式

  • 顺序存储

顺序存储将二叉树的每一个节点和数组的编号一一对应，根据这个编号，可以找到该结点的父结点和孩子结点

​

BinaryTree[0]表示该树的根结点，从根结点开始我们可以按照性质 6 去检索该树的所有结点，比如一个有 20 个结点的
二叉树， 根据性质 6 编号为 10 的结点的父结点为编号为 5 的结点，其左孩子结点为编号为20 的结点，其没有右孩子结点。

由此可以看出：

  • 如果二叉树是一棵完全二叉树的话，顺序结构的优点就非常明显，它能紧凑的存储二叉树，而且可以随机存取二叉树的某个结点，只需要根据性质 6 计算出该结点的元素下标即可；
  • 如果是非完全二叉树，则顺序存储结构就存在空间的浪费，它会为不存在的结点分配空间，而且如果二叉树规模很大，在实际应用中，内存里也很难找出相应的连续存储空间。
     
  • 链式存储

二叉树的节点一般定义为：数据部分、左子树指针和右子树指针，用指针将节点串起来，其中 l 表示左孩子指针， r 表示右孩子指针，∧表示空指针

优点：

  • 能够很直观地表示二叉树的逻辑结构；
  • 在二叉树不是完全二叉树的时候，链式结构不会像顺序存储结构一样产生空结点，而且链式存储结构能很好地利用内存中的碎片空间，提高内存空间利用效率。

缺点：

  • 链式存储结构不能随机存取某个结点，要找到某个结点，必须从根结点开始沿着指针往叶子结点遍历。
     

7.基本操作

参考：

  • 构建一棵树，即初始化操作
  1. #include<iostream>
  2. using namespace std;
  3. class BinaryTreeNode{
  4. public:
  5. 	//init
  6. 	BinaryTreeNode(){
  7. 		data=NULL;
  8. 		lchild=NULL;
  9. 		rchild=NULL;	
  10. 	}
  11. 	BinaryTreeNode(int n){
  12. 		data=new int;
  13. 		*data=n;
  14. 		lchild=NULL;
  15. 		rchild=NULL;
  16. 	}
  17. private:
  18. 	int *data;//data
  19. 	BinaryTreeNode* lchild;//left child tree 
  20. 	BinaryTreeNode* rchild;//right child tree
  21. };
  22. int main()
  23. {
  24. 	BinaryTreeNode bt(5);	
  25. 	return 0;	
  26. }
  • 前序遍历（根、左、右）
  1. //递归
  2. void preorderTraversal(BinaryTreeNode *node)
  3. {
  4. 	if(!node)
  5. 		return;
  6. 	std::cout<<node->data<<" ";
  7. 	preorderTraversal(node->lchild);
  8. 	preorderTraversal(node->rchild); 
  9. }
  10. //迭代
  11. void preoder(BinaryTreeNode *root)
  12. {
  13. 	BinaryTreeNode *cur=root;
  14. 	std::stack<BinaryTreeNode *>s;
  15. 		
  16. 	while(cur||!s.empty())
  17. 	{
  18. 		//遍历直到最左叶子节点 
  19. 		while(cur)
  20. 		{
  21. 			std::cout<<cur->data<<" "; 
  22. 			s.push(cur);
  23. 			cur=cur->lchild;
  24. 		}
  25. 		//while结束时，cur=NULL
  26. 		//cur为左子节点 
  27. 		cur=s.top();
  28. 		s.pop();
  29. 		cur=cur->rchild;
  30. 	}
  31. 		
  32. }
  • 中序遍历（左、根、右）
  1. 	void midorderTraversal(BinaryTreeNode *node)
  2. 	{
  3. 		if(!node)
  4. 			return;
  5. 		preorderTraversal(node->lchild);
  6. 		std::cout<<node->data<<" ";
  7. 		preorderTraversal(node->rchild); 
  8. 	}
  9. 	void midoder(BinaryTreeNode *root)
  10. 	{
  11. 		BinaryTreeNode *cur=root;
  12. 		std::stack<BinaryTreeNode *>s;
  13. 		
  14. 		while(cur||!s.empty())
  15. 		{
  16. 			//遍历直到最左叶子节点 
  17. 			while(cur)
  18. 			{
  19. 				s.push(cur);
  20. 				cur=cur->lchild;
  21. 			}
  22. 			//while结束时，cur=NULL
  23. 			//cur为左子节点 
  24. 			cur=s.top();
  25. 			std::cout<<cur->data<<" "; 
  26. 			s.pop();
  27. 			cur=cur->rchild;
  28. 		}
  29. 		
  30. 	}
  • 后序遍历（左、右、根）
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/516236
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号