数据结构整理

admin
admin
admin
102326
文章
87
评论
2022年1月6日01:31:22评论36 views字数 28972阅读96分34秒阅读模式

已经一年半没有碰过c语言了，c语言编程这块，有点荒废。最近有点想要去学习一下linux的内核，挺高深的，感觉自己有点儿自不量力。不过，趁现在还空闲，就折腾一下吧，准备将数据结构重新再学习一下，将知识点整理成思维导图，让自己好记一些。

思维导图

0x1 概述

0x2线性表

0x3栈

0x4队列

0x5递归

0x6树和二叉树

代码实现

线性表

0x1 顺序表

0x1.1基本操作 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
#include<stdio.h>
#include<stdlib.h> 
#include<malloc.h>
#define MaxSize 50
typedef int ElemType; 
//ElemType类型实际上是int
typedef struct{
    ElemType data[MaxSize];  //存放顺序表中的元素
    int length;              //顺序表的长度
}SqList;             //SequenceList,顺序表
//建议： ;
typedef SqList *List; 
void InitList(SqList *&L)   //初始化
{    L=(SqList *)malloc(sizeof(SqList));	//分配存放线性表的空间
     L->length=0;
} 
void DestroyList(SqList *&L)//销毁线性表
  {
     free(L);
  }
 
bool ListEmpty(SqList *L)//判断是否为空
  {   return(L->length==0); }
  
int ListLength(SqList *L) //求线性表的长度
  {   return(L->length); }
  
void DispList( SqList *L)//输出线性表
  {	int i;
	if (ListEmpty(L)) return;
	for (i=0;i<L->length;i++)
       printf("%d",L->data[i]);
	printf("\n");
  } 
 
bool GetElem(SqList *L,int i,ElemType &e)//获取第i个元素 
{ 
    if (i<1 || i>L->length)
        return false;
    e=L->data[i-1]; 
    return true;
}

int LocateElem(SqList *L, ElemType e)//按元素查找
{
    for(int i=0; i<L->length;i++)
        if(L->data[i]==e)
            return i+1;       //返回元素的逻辑位序
    return 0;
}
bool ListInsert(SqList *&L,int i,ElemType e)//插入元素e
{  	int j;
    if (i<1 || i>L->length+1)
 		return false;	//参数错误时返回false
    i--;	//将顺序表逻辑序号转化为物理序号
    for(j=L->length;j>i;j--)	//将data[i..n]元素后移一个位置
    	L->data[j]=L->data[j-1];
 	L->data[i]=e;			//插入元素e
    L->length++;			//顺序表长度增1
    return true;			//成功插入返回true
}

bool ListDelete(SqList *&L,int i,ElemType &e)//删除元素e
{  
   if (i<1 || i>L->length) //删除位置不合法
        return false;
   i--;		    //将顺序表逻辑序号转化为物理序号
   e=L->data[i];
   for (int j=i;j<L->length-1;j++)         
      L->data[j]=L->data[j+1];
   L->length--;	    //顺序表长度减1
   return true;			
}


void CreateList(SqList *&L,int n)//创建 顺序表 
{
    int i;
    L->length=n;
    printf("请输入线性表la的元素共%d个\n",n);
	for(i=0;i<n;i++)
	{
	  scanf("%d",&L->data[i]);
	}
}

int main()
{   List la;
    int i,j;
    int e,m;
	printf("初始化线性表\n");
	InitList(la);
	printf("请输入线性表的长度:");
	scanf("%d",&m);
    CreateList(la,m); 
	DispList(la);
	printf("请输入你要查找的元素位置:"); 
	scanf("%d",&j);
	GetElem(la,j,e);
	printf("第%d处的元素为%d\n",j,e);
	
	printf("输入你要查找的元素:");
	scanf("%d",&e);
	j=LocateElem(la,e);
	printf("%d元素在%d处\n",e,j); 
	
	printf("请输入要插入的元素以及元素位置:");
	scanf("%d%d",&e,&j);
	ListInsert(la,j,e);
	
	DispList(la);
	printf("请输入要删除的元素位置:") ;
	scanf("%d",&j);
	ListDelete(la,j,e);
	printf("删除%d元素成功!",e);
	system("pause"); 
	return 0;
	
}

0x1.2 题型
0x1.2.1 已知长度为n的线性表A采用顺序存储结构，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除元素值在[x,y] 之间的所有元素
解法一:

1
2
3
4
5
6
7
8
9
10
11
 
void delnode(SqList *&L,ElemType x，ElemType y)
{  int k=0,i;		 //k记录值不在[x,y]元素个数
   for (i=0;i<L->length;i++)
	if (!(L->data[i]>=x && L->data[i]<=y ))
               //若当前元素不在[x,y],将其插入L中
	{ 
         L->data[k]=L->data[i];
	   k++;		 //不在[x,y]的元素增1
	}
   L->length-=k;		 //顺序表L的长度等于k
}

解法二

1
2
3
4
5
6
7
8
9
10
 
void delnode1(SqList *&L,ElemType x，ElemType y)
{  
   int i,k;
    for(i=0;i<L->Lenth;i++)
	{   
        if(x<=L->data[i] && L->data[i]<=y)	k++；
	    else  L->data[i-k]=L->data[i];
	}
	L->Lenth-=k;
}

0x1.2.2 有一个顺序表L，元素类型为整型。设计一算法，以第一个元素为轴，所有小于等于它的元素移到该元素前面，所有大于它的元素移动到该元素后面
解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
void move1(SqList *&L)
{  int i=0,j=L->length-1;
   ElemType pivot=L->data[0];	//以data[0]为基准
   ElemType tmp;
   while (i<j)	//从区间两端交替向中间扫描,直至i=j为止
   {	while (i<j && L->data[j]>pivot)
	   j--;	//从右向左扫描,找一个小于等于pivot的元素
      while (i<j && L->data[i]<=pivot)
	   i++;	//从左向右扫描,找一个大于pivot的元素
	if (i<j)
	{   tmp=L->data[i];//将L->data[i]和L->data[j]交换
	    L->data[i]=L->data[j];
	    L->data[j]=tmp;
	}
   }
   tmp=L->data[0];  //将L->data[0]和L->data[j]进行交换
   L->data[0]=L->data[j];
   L->data[j]=tmp;
   printf("i=%d\n",i);
}

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
void move2(SqList *&L)
{  int i=0,j=L->length-1;
   ElemType pivot=L->data[0];	//以data[0]为基准
   while (i<j) //从顺序表两端交替向中间扫描,直至i=j为止
   {  while (j>i && L->data[j]>pivot)
	  j--;   //从右向左扫描,找一个小于等于pivot的data[j]
	L->data[i]=L->data[j];	//将其放入data[i]处
	i++;
	while (i<j && L->data[i]<=pivot)
	  i++;  //从左向右扫描,找一个大于pivot的记录data[i]
	L->data[j]=L->data[i];	//将其放入data[j]处
	j--;
   }
   L->data[i]=pivot;
   printf("i=%d\n",i);
}

0x2 单链表

0x2.1基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
 
#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct LNode  		//定义单链表结点类型
{
	ElemType data;
	struct LNode *next;		//指向后继结点
} LNode,*LinkList;
void InitList(LinkList &L);
void CreateListF(LinkList &L,int n); 
void CreateListR(LinkList &L,int n);
bool ListEmpty(LinkList L);
void DispList(LinkList L);
void DestroyList(LinkList &L);
bool ListInsert(LinkList &L,int i,ElemType e);
bool ListDelete_L(LinkList &L,int i,ElemType &e);
void sort(LinkList &L);
void split(LinkList &L,LinkList &L1,LinkList &L2);
int Find(LinkList L, int m );
bool GetElem(LinkList L,int i,ElemType &e);
int main() {
	LinkList L,L1,L2;
	int n,m;
	ElemType e;
	cout<<"请输入要创建链表元素个数:"<<endl; 
	cin>>n;
	cout<<"请输入"<<n<<"个链表元素。"<<endl; 
	CreateListR(L,n);
	cout<<"请输入要查找的元素位置:"<<endl; 
	cin>>m;
    GetElem(L,m,e);
    cout<<"该元素为:"<<e<<endl;
    cout<<"请输入要插入的元素以及元素位置:"<<endl;
    cin>>e>>m;
    ListInsert(L,m,e); 
    DispList(L);
    cout<<endl; 
    cout<<"请输入要删除的元素位置:"<<endl;
    cin>>m;
    ListDelete_L(L,m,e);
    DispList(L);
	DestroyList(L);
	//DispList(L);
	system("pause");
	return 0;
}
void InitList(LinkList &L)
{
	L=new LNode; 	//创建头结点
	L->next=NULL;
}
void CreateListF(LinkList &L,int n){
	int i;
	LinkList s;
	L=new LNode;
	L->next=NULL; 
	for(i=1;i<=n;i++){
		s=new LNode;
		cin>>s->data;
		s->next=L->next;
		L->next=s;
	}
}
void CreateListR(LinkList &L,int n){
	int i;
	LinkList s,r;
	L=new LNode;
	L->next=NULL;
	r=L; 
	for(i=1;i<=n;i++){
		s=new LNode;
		cin>>s->data;
		r->next=s;
		r=s;
	}
	r->next=NULL;
}
void DispList(LinkList L){
	LinkList p;
	int flag=1;
	p=L->next;
	while(p){
		if(flag) {
			cout<<p->data;flag=0;
		}
		else {
			cout<<" "<<p->data;	
		}
		p=p->next;
		
	}
}
void DestroyList(LinkList &L){
	LinkList p=L;
	while(L){
	    p=L;
		L=L->next;	
		delete p;	
		
	}
}
bool ListInsert(LinkList &L,int i,ElemType e)//在第i处插入e元素 
{
  int j=0;
  LinkList p=L,s;
  while(p&&j<i-1){
  	p=p->next;j++;
  }
  if(p==NULL) return false;
  s=new LNode;
  s->data=e;
  s->next=p->next;
  p->next=s;	
  return true;
}
bool ListDelete_L(LinkList &L,int i,ElemType &e)
{
  int j=0;
  LinkList p=L,s,q;
  while(p&&j<i-1){
  	p=p->next;j++;
  }
  if(p==NULL) return false;
	q=p->next;
	e=q->data;
	p->next=q->next;
	delete q;
	return true;
}
void split(LinkList &L,LinkList &L1,LinkList &L2){
	LinkList p=L->next,r,q;//r为L1尾指针，q为L2指针 
	L1=L;r=L1;
	L1->next=NULL; //重构L1 
	L2=new LNode;//初始化L2 
	L2->next=NULL;
	while(p){  
     r->next=p;//尾插插入L1  
     r=p;  //修改尾指针 
	 p=p->next;		
	 q=p;//b节点
	 if(p){
	 	p=p->next;  //保存后继节点 
	    q->next=L2->next; 
	    L2->next=q;//头结点插入s 
	 }
	}
	r->next=NULL; //L1尾部指针为空 
}
void sort(LinkList &L){
	LinkList p,pre,q;
	p=L->next->next;
	L->next->next=NULL;
	while(p){
	    q=p->next; //p指针保存下，后面要插入链表中，后续关系会变更。 
		pre=L;
		while(pre->next&&pre->next->data<p->data) pre=pre->next;
		p->next=pre->next;//将*pre之后插入*p
	    pre->next=p; 
		p=q;
	}
}

bool GetElem(LinkList L,int i,ElemType &e)
{  int j=0;
   LinkList p=L;	//p指向头节点,j置为0(即头节点的序号为0)
   while (j<i && p!=NULL)	//找第i个节点
   {	j++;
	p=p->next;
   }
   if (p==NULL)	//不存在第i个数据节点,返回false
	return false;
   else		//存在第i个数据节点,返回true
   {  e=p->data;
	return true;
   }
}

0x2.2例题
有一个带头节点的单链表L={a1,b1,a2,b2,…,an,bn}，设计一个算法将其拆分成两个带头节点的单链表L1和L2 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
void split(LinkList &L,LinkList &L1,LinkList &L2){
	LinkList p=L->next,r,q;//r为L1尾指针，q为L2指针 
	L1=L;r=L1;
	L1->next=NULL; //重构L1 
	L2=new LNode;//初始化L2 
	L2->next=NULL;
	while(p){  
     r->next=p;//尾插插入L1  
     r=p;  //修改尾指针 
	 p=p->next;		
	 q=p;//b节点
	 if(p){
	 	p=p->next;  //保存后继节点 
	    q->next=L2->next; 
	    L2->next=q;//头结点插入s 
	 }
	}
	r->next=NULL; //L1尾部指针为空 
}

有一个带头节点的单链表L（至少有一个数据节点），设计一个算法使其元素递增有序排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
void sort(LinkList &L)
{  LinkList p,pre,q;
   p=L->next->next;	//p指向L的第2个数据节点
   L->next->next=NULL;	//构造只含一个数据节点的有序表
   while (p!=NULL)
   {	q=p->next;		//q保存p节点后继节点的指针
	pre=L;  //从有序表开头进行比较,pre指向插入p的前驱节点
	while (pre->next!=NULL && pre->next->data<p->data)
	   pre=pre->next;	//在有序表中找插入*p的前驱节点*pre
	p->next=pre->next;//将pre之后插入p
	pre->next=p;
	p=q;			//扫描原单链表余下的节点
   }
}

0x3 双链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
typedef struct DNode       //声明双链表节点类型
{  	ElemType data;
   	struct DNode *prior;    //指向前驱节点
	struct DNode *next;     //指向后继节点
 }DLinkList;

//在*p结点之后插入结点*s
s->next = p->next
p->next->prior = s
s->prior = p
p->next = s

//删除*p结点之后的一个结点 
p->next->next->prior = p
p->next = p->next->next

//头插法 
void CreateListF(DLinkNode *&L，ElemType a[]，int n)
{　 DLinkNode *s; int i;
       L=(DLinkNode *)malloc(sizeof(DLinkNode));	//创建头结点
       L->prior=L->next=NULL;	//前后指针域置为NULL
       for (i=0;i<n;i++)		//循环建立数据结点
       {	s=(DLinkNode *)malloc(sizeof(DLinkNode));
	s->data=a[i];		//创建数据结点*s
	s->next=L->next;	//将*s插入到头结点之后
	if (L->next!=NULL)      	//若L存在数据结点，修改前驱指针
  	       L->next->prior=s;
	L->next=s;
	s->prior=L;
 }
} 

//尾插法 
void CreateListR(DLinkNode *&L，ElemType a[]，int n)
{     DLinkNode *s，*r;
       int i;
       L=(DLinkNode *)malloc(sizeof(DLinkNode));    //创建头结点
       L->prior=L->next=NULL;	//前后指针域置为NULL
       r=L;			//r始终指向尾结点，开始时指向头结点
       for (i=0;i<n;i++)		//循环建立数据结点
       {      s=(DLinkNode *)malloc(sizeof(DLinkNode));
	s->data=a[i];		//创建数据结点*s
	r->next=s;     
              s->prior=r;	//将*s插入*r之后
	r=s;			//r指向尾结点
      }
      r->next=NULL;		//尾结点next域置为NULL
}

0x4有序表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 

//为假设有序表元素是以递增方式排列了简单 
//有序顺序表
void ListInsert(SqList *&L，ElemType e)
{     int i=0，j;
      while (i<L->length && L->data[i]<e)
	i++;			//查找值为e的元素
      for (j=ListLength(L);j>i;j--)	//将data[i..n]后移一个位置
	L->data[j]=L->data[j-1]; 
      L->data[i]=e;
      L->length++;		//有序顺序表长度增1
}

//有序单链表的ListInsert() 
void ListInsert(LinkNode *&L，ElemType e)
{     LinkNode *pre=L，*p;

      while (pre->next!=NULL && pre->next->data<e)
	pre=pre->next; 	//查找插入结点的前驱结点*pre

      p=new LinkNode;
      p->data=e;		//创建存放e的数据结点*p
      p->next=pre->next;	//在*pre结点之后插入*p结点
      pre->next=p;

}

//采用顺序表存放有序表时，二路归并算法
void UnionList(SqList *LA，SqList *LB，SqList *&LC)
{     int i=0，j=0，k=0;//i、j分别为LA、LB的下标，k为LC中元素个数
      LC=new SqList; 		//建立有序顺序表LC
      while (i<LA->length && j<LB->length)
      {	if (LA->data[i]<LB->data[j])
	{     LC->data[k]=LA->data[i];
	       i++;k++;
	}
	else	//LA->data[i]>LB->data[j]
	{     LC->data[k]=LB->data[j];
	      j++;k++;
	}
   }  
   
      while (i<LA->length)		//LA尚未扫描完，将其余元素插入LC中
     {	LC->data[k]=LA->data[i];
	i++;k++;
     }
     while (j<LB->length)		//LB尚未扫描完，将其余元素插入LC中
     {	LC->data[k]=LB->data[j];
	j++;k++;
     }
     LC->length=k;
}

栈

0x1顺序栈

0x1基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct 
{	
	ElemType data[MaxSize];
	int top;				//栈指针
} SqStack;					//顺序栈类型定义
void InitStack(SqStack *&s)
{
	s=(SqStack *)malloc(sizeof(SqStack));
	s->top=-1;
} 
void DestroyStack(SqStack *&s)
{
	free(s);
}
bool StackEmpty(SqStack *s)
{
	return(s->top==-1);
}
bool Push(SqStack *&s,ElemType e)
{
	if (s->top==MaxSize-1)    //栈满的情况，即栈上溢出
		return false;
	s->top++;
	s->data[s->top]=e;
	return true;
}
bool Pop(SqStack *&s,ElemType &e)
{
	if (s->top==-1)		//栈为空的情况，即栈下溢出
		return false;
	e=s->data[s->top];
	s->top--;
	return true;
} 
bool GetTop(SqStack *s,ElemType &e)
{
	if (s->top==-1) 		//栈为空的情况，即栈下溢出
		return false;
	e=s->data[s->top];
	return true;
}
bool symmetry(ElemType str[])
{  int i;  ElemType e;
   SqStack *st;
   InitStack(st);			//初始化栈
   for (i=0;str[i]!='\0';i++)	//将串所有元素进栈
	Push(st,str[i]);		//元素进栈
   for (i=0;str[i]!='\0';i++)
   {	Pop(st,e);		  //退栈元素e
	if (str[i]!=e)	  //若e与当前串元素不同则不是对称串
	{  DestroyStack(st);//销毁栈
	   return false;
	}
   }
   DestroyStack(st);	  //销毁栈
   return true;
}
int main(){
	char str[10]="heterh";
	if(symmetry(str))
		printf("true");
	else
 		printf("false");
		
	return 0;
}

题型
0x1
编写一个算法利用顺序栈判断一个字符串是否是对称串。所谓对称串是指从左向右读和从右向左读的序列相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
bool symmetry(ElemType str[])
{  int i;  ElemType e;
   SqStack *st;
   InitStack(st);			//初始化栈
   for (i=0;str[i]!='\0';i++)	//将串所有元素进栈
	Push(st,str[i]);		//元素进栈
   for (i=0;str[i]!='\0';i++)
   {	Pop(st,e);		  //退栈元素e
	if (str[i]!=e)	  //若e与当前串元素不同则不是对称串
	{  DestroyStack(st);//销毁栈
	   return false;
	}
   }
   DestroyStack(st);	  //销毁栈
   return true;
}

0x2中缀表达式转换成后缀表达式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
char trans(char *exp, char postexp[])		
{   char e;  
    SqStack *Optr;		//定义运算符栈指针
    InitStack(Optr);		//初始化运算符栈
    int i=0;			//i作为postexp的下标
	while (*exp!='\0')		//exp表达式未扫描完时循环
	{ 	switch(*exp)
		{
		case '(':			//判定为左括号
				Push(Optr,'('); //左括号进栈
				exp++;		//继续扫描其他字符
				break;
		case ')':		    //判定为右括号
				Pop(Optr,e);	    //出栈元素e
				while (e!='(')	    //不为'('时循环
				{	postexp[i++]=e;	    //将e存放到postexp中
					Pop(Optr,e);	    //继续出栈元素e
				}
				exp++;		     //继续扫描其他字符
				break;
		case '+':				//判定为加或减号
		case '-':
				while (!StackEmpty(Optr))	//栈不空循环
				{    
					GetTop(Optr,e);		//取栈顶元素e
					if (e!='(')			//e不是'('
					{   postexp[i++]=e;	//将e存放到postexp中
						Pop(Optr,e);		//出栈元素e
					}
					else			//e是'(时退出循环
						break;
				}
				Push(Optr,*exp);		//将'+'或'-'进栈
				exp++;				//继续扫描其他字符
				break;
		case '*':				//判定为'*'或'/'号
		case '/':
				while (!StackEmpty(Optr))	//栈不空循环
				{   GetTop(Optr,e);		//取栈顶元素e
					if (e=='*' || e=='/')
					{   postexp[i++]=e;	//将e存放到postexp中
						Pop(Optr,e);	//出栈元素e
					}
					else			//e为非'*'或'/'运算符时退出循环
						break;
				}
				Push(Optr,*exp);		//将'*'或'/'进栈
				exp++;			//继续扫描其他字符
				break;
		default:			//处理数字字符
				while (*exp>='0' && *exp<='9')      //判定为数字字符
				{   postexp[i++]=*exp;
					exp++;
				}
				postexp[i++]='#';	//用#标识一个数值串结束
		}
    }
    while (!StackEmpty(Optr))	//此时exp扫描完毕,栈不空时循环
    {   Pop(Optr,e);		//出栈元素e
		postexp[i++]=e;		//将e存放到postexp中
    }
    postexp[i]='\0';		//给postexp表达式添加结束标识
    DestroyStack(Optr);	//销毁栈
    //return postexp;
}

后缀表达式求值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
double compvalue(char *postexp)	
{   double d, a ,b, c, e;	
    SqStack *Opnd;					//定义操作数栈
    InitStack(Opnd);				//初始化操作数栈
    while (*postexp!='\0')			//postexp字符串未扫描完时循环
    {	 
		switch (*postexp)
		{
			case '+':				//判定为'+'号
				Pop(Opnd,a);		//出栈元素a
				Pop(Opnd,b);		//出栈元素b
				c=b+a;				//计算c
				Push(Opnd,c);		//将计算结果c进栈
				break;
			case '-':				//判定为'-'号
				Pop(Opnd,a);		//出栈元素a
				Pop(Opnd,b);		//出栈元素b
				c=b-a;				//计算c
				Push(Opnd,c);		//将计算结果c进栈
				break;
			case '*':				//判定为'*'号
				Pop(Opnd,a);		//出栈元素a
				Pop(Opnd,b);		//出栈元素b
				c=b*a;				//计算c
				Push(Opnd,c);		//将计算结果c进栈
				break;
			case '/':				//判定为'/'号
				Pop(Opnd,a);		//出栈元素a
				Pop(Opnd,b);		//出栈元素b
				if (a!=0)
				{	c=b/a;			//计算c
					Push(Opnd,c);		//将计算结果c进栈
					break;
				}
				else
				{		printf("\n\t除零错误!\n");
					exit(0);			//异常退出
				}
				break;
			default:			//处理数字字符
				d=0;		//转换成对应的数值存放到d中
				while (*postexp>='0' && *postexp<='9')
				{	d=10*d+*postexp-'0';
					postexp++;
				}
				Push(Opnd,d);	//将数值d进栈
				break;
		}
		postexp++;		//继续处理其他字符
    }
    GetTop(Opnd,e);		//取栈顶元素e
    DestroyStack(Opnd);	//销毁栈
    return e;			//返回e
}

0x3迷宫问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
#include<stdio.h>
#define MaxSize 200
//1代表无路，0代表有路 

int mg[10][10]=
{
	{1,1,1,1,1,1,1,1,1,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,0,0,1,1,0,0,1},
	{1,0,1,1,1,0,0,0,0,1},
	{1,0,0,0,1,0,0,0,0,1},
	{1,0,1,0,0,0,1,0,0,1},
	{1,0,1,1,1,0,1,1,0,1},
	{1,1,0,0,0,0,0,0,0,1},
	{1,1,1,1,1,1,1,1,1,1}
};
typedef struct{
	int i; //当前方块的行号 
	int j; //当前方块的列号 
	int di; //下一个可走的相邻方块的方位号 
}Box;
typedef struct
{
	Box data[MaxSize];
	int top;
}StType;
bool mgpath(int xi,int yi,int xe,int ye){
	int i,j,k,di,find;
	StType st; 
	st.top=-1;
	st.top++; 
	st.data[st.top].i=xi; //初始方块进栈 
	st.data[st.top].j=yi;
	st.data[st.top].di=-1;
	mg[xi][yi]=-1;
	while(st.top>-1){
		i=st.data[st.top].i;
		j=st.data[st.top].j;
		di=st.data[st.top].di;
		if(i==xe&&j==ye){ //找到了出口输出路径 
			printf("迷宫的路径如下:\n");
			for(k=0;k<=st.top;k++){
				printf("\t(%d,%d)",st.data[k].i,st.data[k].j);
				if((k+1)%5==0)
					printf("\n");
			}
			printf("\n");
			return true; 
		} 
		find=0;
		while(di<4&&find==0){ //找下一个可走的方位 
			di++;
			switch(di)
			{
				case 0: i=st.data[st.top].i-1;j=st.data[st.top].j;break;
				case 1: i=st.data[st.top].i;j=st.data[st.top].j-1;break;
				case 2: i=st.data[st.top].i;j=st.data[st.top].j+1;break;
				case 3: i=st.data[st.top].i+1;j=st.data[st.top].j;break; 
			}
			if(mg[i][j]==0) find=1;
		}
	   if(find==1){
   		st.data[st.top].di=di; //修改原栈顶元素di的值 
   		st.top++;  //下一个可走方块进栈 
   		st.data[st.top].i=i; st.data[st.top].j=j;
   		st.data[st.top].di=-1;
		mg[i][j]=-1;  //避免重复走该方块 
   	  }
   	  else{   //没有路劲可走，则退栈 
  	   	 mg[st.data[st.top].i][st.data[st.top].j]=0;
  	   	 st.top--;
  	   }
	} 
	return false;
}

int  main(){
	
	if(!mgpath(1,1,5,5)){
		
		printf("该迷宫问题没有解"); 
	}
	return 0;
}

0x2共享栈

0x3 链栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct linknode
{	
	ElemType data;				//数据域
	struct linknode *next;		//指针域
} LiStack;						//链栈类型定义
void InitStack(LiStack *&s)
{
	s=(LiStack *)malloc(sizeof(LiStack));
	s->next=NULL;
}
void DestroyQueue(LiStack *&s)
{
	LiStack *p=s->next;
	while (p!=NULL)
	{	
		free(s);
		s=p;
		p=p->next;
	}
	free(s);	//s指向尾结点,释放其空间
}
int StackLength(LiStack *s)
{
	int i=0;
	LiStack *p;
	p=s->next;
	while (p!=NULL)
	{	
		i++;
		p=p->next;
	}
	return(i);
}
bool StackEmpty(LiStack *s)
{
	return(s->next==NULL);
}
void Push(LiStack *&s,ElemType e)
{	LiStack *p;
	p=(LiStack *)malloc(sizeof(LiStack));
	p->data=e;				//新建元素e对应的节点*p
	p->next=s->next;		//插入*p节点作为开始节点
	s->next=p;
}
bool Pop(LiStack *&s,ElemType &e)
{	LiStack *p;
	if (s->next==NULL)		//栈空的情况
		return false;
	p=s->next;				//p指向开始节点
	e=p->data;
	s->next=p->next;		//删除*p节点
	free(p);				//释放*p节点
	return true;
}
bool GetTop(LiStack *s,ElemType &e)
{	if (s->next==NULL)		//栈空的情况
		return false;
	e=s->next->data;
	return true;
}

队列

0x1 顺序队列

基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
#include<stdio.h>
#define MaxSize 200
#include<iostream>
using namespace std;
typedef int ElemType;

typedef struct 
{     ElemType data[MaxSize];
      int front,rear;      //队首和队尾指针
}Queue;
typedef Queue *SqQueue;
void InitQueue(SqQueue &q)
{	q=new Queue;
	q->front=q->rear=-1;
}
void DestroyQueue(SqQueue &q) //删除队列 
{
  delete q;
}
bool QueueEmpty(SqQueue q)
{
   return(q->front==q->rear);
}
bool enQueue(SqQueue &q,ElemType e)
{  if (q->rear+1==MaxSize)	   return false;
                                       //队满上溢出
	q->rear=q->rear+1;
	q->data[q->rear]=e;
	return true;
}

bool deQueue(SqQueue &q,ElemType &e)
{	if (q->front==q->rear)  //队空下溢出
		return false;
	q->front=q->front+1;
	e=q->data[q->front];
	return true;
}

0x2 循环队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
#include <iostream>
#include<queue>
#define MaxSize 100
using namespace std;
typedef char ElemType;
typedef struct 
{	
	ElemType data[MaxSize];
	int front,rear;		//队首和队尾指针
} Queue;
typedef Queue *SqQueue;
void InitQueue(SqQueue &q)
{	q=new Queue;
	q->front=q->rear=0;
}
//销毁队列 
void DestroyQueue(SqQueue &q)
{
	delete q;
}
//判断队列是否为空 
bool QueueEmpty(SqQueue q)
{
	return(q->front==q->rear);
}
//进环形队列 
bool enQueue(SqQueue &q,ElemType e)
{	if ((q->rear+1)%MaxSize==q->front)	//队满上溢出
		return false;
	q->rear=(q->rear+1)%MaxSize;
	q->data[q->rear]=e;
	return true;
}
//出环形队列 
bool deQueue(SqQueue &q,ElemType &e)
{	if (q->front==q->rear)		//队空下溢出
		return false;
	q->front=(q->front+1)%MaxSize;
	e=q->data[q->front];
	return true;
}
void number1(int n){
    int i;
    ElemType e;
    
}
void number(int n){
    int i;
    ElemType e;
    SqQueue q; 
    InitQueue(q);
    for(i=1;i<=n;i++) enQueue(q,i);
    i=1;
    while(!QueueEmpty(q)){
    	deQueue(q,e);
    	cout<<e<<" ";
    	if(!QueueEmpty(q)) {
    		deQueue(q,e);
    	    enQueue(q,e); //剩下一个元素不进队 
		}
	}
}

 int main()
 {
 	/*int n;
 	cin>>n;
 	number(n);
 	*/
 	SqQueue Q;

    InitQueue(Q);

    char x= 'e', y= 'c';

    enQueue(Q, 'h');

    enQueue(Q, 'r');

    enQueue(Q, y);

    deQueue(Q, x);

    enQueue(Q, x);

    deQueue(Q, x);

    enQueue(Q, 'a');

    while(!QueueEmpty(Q)){

        deQueue(Q,y);

        cout<<y;

    }

    cout<<x;
  return 0;
}

题目
n个人站成一排，从左到右编号分别为1–n，现从左到右报数“1,2,1,2,…”,数到1的人出列，数到“2”的立即站到队伍最右端，报数过程反复进行，直到n个人都出列为止。给出他们的出列顺序
C语言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
void number(int n){
    int i;
    ElemType e;
    SqQueue q; 
    InitQueue(q);
    for(i=1;i<=n;i++) enQueue(q,i);
    i=1;
    while(!QueueEmpty(q)){
    	deQueue(q,e);
    	cout<<e<<" ";
    	if(!QueueEmpty(q)) {
    		deQueue(q,e);
    	    enQueue(q,e); //剩下一个元素不进队 
		}
	}
}

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
#include <string>    //  使用 string 类时须包含这个文件
#include <iostream>
#include <queue>     //调用c++中的类：queue 
using namespace std; 
void number(int n)
{ int i;
  queue<int> q1;  //初始化队列，包含类型 
  for(i=1;i<=n;i++){
	  	q1.push(i);  //入队列 }
  while(!q1.empty())   //判断队列是否为空，是返回true; 
	{ cout<<q1.front()<<" ";  
        //获取队首元素 ；访问队尾元素：q1.back() 
	  q1.pop();
        if(!q1.empty())
	   {
		q1.push(q1.front());
		q1.pop();         //出队列，不返回元素 
	   }
	}
	}
}
int main(){
	number(8);
}

打印杨辉三角

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
void triangle(SqQueue &q,int n){
	ElemType x,y;
	InitQueue(q);
	enQueue(q,0);
	enQueue(q,1);
	enQueue(q,0);//处理第一行
	cout<<1<<endl;
	for(int i=2;i<=n;i++) //第二行开始处理
	{  for(int j = 1; j<= i ; j++)//每行出队入队次数
  		{    
       		deQueue(q,x);//出队
      		y = GetFront(q);   //获得队首元素
      		enQueue(q,x+y); //前2个元素相加，再入队
            cout<<x+y;//输出x+y值；  
 		 } 
 	 	enQueue(q,0);//入队0
   		cout<<endl;//输出回车换行；
	}
			
}

迷宫

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
#include<stdio.h>
#define MaxSize 200
//1代表无路，0代表有路 


int mg[10][10]=
{
	{1,1,1,1,1,1,1,1,1,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,0,0,1,1,0,0,1},
	{1,0,1,1,1,0,0,0,0,1},
	{1,0,0,0,1,0,0,0,0,1},
	{1,0,1,0,0,0,1,0,0,1},
	{1,0,1,1,1,0,1,1,0,1},
	{1,1,0,0,0,0,0,0,0,1},
	{1,1,1,1,1,1,1,1,1,1}
};

typedef struct 
{
	int i,j;
	int pre;
}Box;
typedef struct
{
	Box data[MaxSize];
	int front,rear; 
}QuType;
bool  mgpath(int xi,int yi,int xe,int ye);
void print(QuType qu,int front);
bool  mgpath(int xi,int yi,int xe,int ye){
	int i,j ,find=0,di;
	QuType qu;
	qu.front=qu.rear=-1;
	qu.rear++; //xi,yi进队 
	qu.data[qu.rear].i=xi;
	qu.data[qu.rear].j=yi;
	qu.data[qu.rear].pre=-1;
	mg[xi][yi]=-1; //将其赋值为-1,以避免回过来重复搜索
	while(qu.front!=qu.rear&&!find)
	{
		qu.front++;
		i=qu.data[qu.front].i;
		j=qu.data[qu.front].j;
		if(i==xe&&j==ye){
			find=1;
			print(qu,qu.front);
			return true;
		}
		for(di=0;di<4;di++){
			switch(di){
				case 0: i=qu.data[qu.front].i-1;j=qu.data[qu.front].j;break;
				case 1: i=qu.data[qu.front].i;j=qu.data[qu.front].j+1;break;
				case 2: i=qu.data[qu.front].i+1;j=qu.data[qu.front].j;break;
				case 3: i=qu.data[qu.front].i;j=qu.data[qu.front].j-1;break;
			}
			if(mg[i][j]==0)
			{
				qu.rear++;
				qu.data[qu.rear].i=i;
				qu.data[qu.rear].j=j;
				qu.data[qu.rear].pre=qu.front;//指向路径中上一个方块的下标 
				mg[i][j]=-1;//将其赋值-1，以避免回过来重复搜索 
			}
		}
	
	} 
	 
		return false;
} 
void print(QuType qu,int front){
	int k=front,j,ns=0;
	printf("\n");
	do
	{
		j=k;
		k=qu.data[j].pre;
		qu.data[j].pre=-1;
	}while(k!=0);
	printf("迷宫的路径如下:\n");
	k=0;
	while(k<MaxSize)
	{
		if(qu.data[k].pre==-1)
		{
			ns++;
			printf("\t(%d,%d)",qu.data[k].i,qu.data[k].j);
			if(ns%5==0)printf("\n");
		}
		k++;
	}
	printf("\n");
}
int main(){
	if(!mgpath(1,1,5,5))
		printf("该迷宫问题没有解"); 
}

0x3 链表队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
#include <iostream>
using namspace std;
typedef char ElemType;
typedef struct qnode
{	
	ElemType data;
	struct qnode *next;
} QNode;		//链队数据结点类型定义
typedef struct
{	
	QNode *front;
	QNode *rear;
} Queue;//链队类型定义
typedef struct Queue *LiQueue;
void InitQueue(LiQueue &q)
{	
	q=new Queue;
	q->front=q->rear=NULL;
}
void DestroyQueue(LiQueue &q)
{
	QNode *p=q->front,*r;	//p指向队头数据节点
	if (p!=NULL)			//释放数据节点占用空间
	{	r=p->next;
		while (r!=NULL)
		{	delete p;
			p=r;r=p->next;
		}
	}
	delete p;delete q;				//释放链队节点占用空间
}
bool QueueEmpty(LiQueue *q)
{
	return(q->rear==NULL);
}
void enQueue(LiQueue &q,ElemType e)
{	QNode *p;
	p=new QNode ;
	p->data=e;
	p->next=NULL;
	if (q->rear==NULL)		//若链队为空,则新节点是队首节点又是队尾节点
		q->front=q->rear=p;
	else
	{	q->rear->next=p;	//将*p节点链到队尾,并将rear指向它
		q->rear=p;
	}
}
bool deQueue(LiQueue &q,ElemType &e)
{	QNode *t;
	if (q->rear==NULL)		//队列为空
		return false;
	t=q->front;				//t指向第一个数据节点
	if (q->front==q->rear)  //队列中只有一个节点时
		q->front=q->rear=NULL;
	else					//队列中有多个节点时
		q->front=q->front->next;
	e=t->data;
	delete t;
	return true;
}

串

串的模式匹配算法
Brute-Force算法 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
#include<stdio.h>
#define MaxSize 200
typedef struct{
	char data[MaxSize];
	int length;
}SqString;
strAssign(SqString &s,char cstr[]){
	int i;
	for(i=0;cstr[i]!='\0';i++){
		s.data[i]=cstr[i];
	}
	s.length=i;
}
int index(SqString s,SqString t)
{     int i=0,  j=0;
     while (i<s.length && j<t.length) 
    {       if (s.data[i]==t.data[j])	//继续匹配下一个字符
			{     i++;			//主串和子串依次匹配下一个字符
	     	  	  j++;
			}
			else			//主串、子串指针回溯重新开始下一次匹配
			{    i=i-j+1;		//主串从下一个位置开始匹配
	    		 j=0; 			//子串从头开始匹配
			}
    }
    if (j>=t.length)
		return(i-t.length);	//返回匹配的第一个字符的下标
    else
		return(-1);		//模式匹配不成功
}
int main(){
	char a[20]="aaabcde",b[20]="abcde";
	int i;
	SqString q,p;
	strAssign(q,a);
	strAssign(p,b);
	i=index(q,p);
	printf("%d",i);
		
}

KMP算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
//Brute-Force算法
#include<stdio.h>
#define MaxSize 200
typedef struct{
	char data[MaxSize];
	int length;
}SqString;
strAssign(SqString &s,char cstr[]){
	int i;
	for(i=0;cstr[i]!='\0';i++){
		s.data[i]=cstr[i];
	}
	s.length=i;
}

void GetNext(SqString t,int next[])	 
{  int j,k;
   j=0;k=-1;next[0]=-1;
   while (j<t.length-1)
   {	if (k==-1 || t.data[j]==t.data[k])
		{   j++;k++;
	   		 next[j]=k;
		}
		else k=next[k];
   }
}
int KMPIndex(SqString s,SqString t) 
{  int next[MaxSize],i=0,j=0;
   GetNext(t,next);
   while (i<s.length && j<t.length) 
   {  if (j==-1 || s.data[i]==t.data[j]) 
	{  i++;
	   j++;			//i,j各增1
	}
	else j=next[j]; 		//i不变,j后退
   }
   if (j>=t.length)
	return(i-t.length);	//匹配模式串首字符下标
   else
	return(-1);			//返回不匹配标志
}
int main(){
	char a[20]="aaabaaaab",b[20]="aaaab";
	int next[20];
	int i;
	SqString s,t;
	strAssign(s,a);
	strAssign(t,b);
	i=KMPIndex(s,t); 
	printf("%d",i);

	
	
}

树

0x1 二叉树创建、遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
#include<stdio.h>
#include<iostream>
using namespace std;
#include<queue>
typedef char ElemType;
#define MaxSize 200
typedef struct node
{     ElemType data;
       struct node *lchild, *rchild;
}BTNode;    
typedef BTNode *BTree;


  
//创建树 
//输入序列:A,  B,  C,  D,  F,  G,  I,  0,  0,  E,  0,  0,  H,  0,  0,  0,  0,  0,  0
void CreateBTree(BTree &BT,string str)
{     BTree  T;int i=0;
      queue<BTree> Q;//队列 	
	if( str[0]!='0' ){ /*分配根结点单元，并将结点地址入队*/
		BT =new BTNode;
		BT->data = str[0];
		BT->lchild=BT->rchild=NULL;
		Q.push(BT);
	}
	else BT=NULL; /* 若第1个数据就是0，返回空树 */
	while( !Q.empty())
	{
		T = Q.front();/*从队列中取出一结点地址*/
		Q.pop();
		i++;
		if(str[i]=='0' ) T->lchild = NULL;
		else 
		{  /*生成左孩子结点；新结点入队*/
			T->lchild = new BTNode;
			T->lchild->data = str[i];
			T->lchild->lchild=T->lchild->rchild=NULL;
			Q.push(T->lchild);
		}
        i++; /* 读入T的右孩子 */
		if(str[i]=='0') T->rchild = NULL;
		else 
		{  /*生成右孩子结点；新结点入队*/
			T->rchild = new BTNode;;
			T->rchild->data = str[i];
		T->rchild->lchild=T->rchild->rchild=NULL;
			Q.push(T->rchild);
		}
	} /* 结束while */
}


//先序遍历 
 void PreOrder(BTree bt)
{     if (bt!=NULL)  
      {     printf("%c ",bt->data); 	//访问根结点
             PreOrder(bt->lchild);
             PreOrder(bt->rchild);
      }
}

//中序遍历 
void InOrder(BTree bt)
{       if (bt!=NULL)  
        {      InOrder(bt->lchild);
	 printf("%c ",bt->data); 	//访问根结点
	 InOrder(bt->rchild);
       }
}		
//后序遍历 
void PostOrder(BTree bt) 
{      if (bt!=NULL)  
        {      PostOrder(bt->lchild);
	 PostOrder(bt->rchild);
	 printf("%c ",bt->data); 	//访问根结点
       }
}
//求所有节点的值 
int FindSum(BTree  bt)
{
   if(bt==NULL)   return 0;
  else 
   return (bt->data+FindSum(bt->lchild)
                              +FindSum(bt->rchild));
}
//访问所有的叶子节点 
void DispLeaf(BTNode *b)
{      if (b!=NULL)
        {	if (b->lchild==NULL && b->rchild==NULL)
	        printf("%c ",b->data);    //访问叶子结点
	DispLeaf(b->lchild);	        //输出左子树中的叶子结点
	DispLeaf(b->rchild);	        //输出右子树中的叶子结点
      }
}
//输出值为x节点所有祖先
bool ancestor(BTree bt,ElemType x)
{    if(bt==NULL) return false;
     else if(bt->lchild!=NULL && bt->lchild->data==x || bt->rchild!=NULL && bt->rchild->data==x) {
			cout<<bt->data<<" ";  //找到孩子为x结点
			return true;
	}
	else if(ancestor(bt->lchild,x) || ancestor(bt->rchild,x)){
	   		 	cout<<bt->data;//先序遍历
	   			return true;
	}
	else return false;
}
//层次遍历 
void LevelOrder(BTree bt)
{  queue<BTree> q;    //初始化队列，元素为树节点
  BTree p;                 //树指针p
  if(bt!=NULL) q.push(bt);  //根节点入队列
  while(!q.empty())
  {      p=q.front();  //访问队头节点
  	q.pop();
  	cout<<p->data<<" ";
  	if(p->lchild) q.push(p->lchild);//左右孩子入队
  	if(p->rchild) q.push(p->rchild);
  }}
  
 //求高度 
int BTNodeHeight(BTNode *b)
{
	int lchildh,rchildh;
	if(b==NULL) return 0;
	else{
		lchildh=BTNodeHeight(b->lchild);
		rchildh=BTNodeHeight(b->rchild);
		return (lchildh>rchildh)?(lchildh+1):(rchildh+1); 
	}
 } 

int main(){
	char str[100]={'A','B', 'C','D', 'F', 'G', 'I','0','0','E', '0', '0', 'H', '0', '0', '0', '0', '0', '0'};
	char a='E';
	int height;
	BTree BT;
	CreateBTree(BT,str);
	cout<<"先序遍历:";
	PreOrder(BT);
	cout<<endl;
	cout<<"中序遍历:";
	InOrder(BT);
	cout<<endl;
	cout<<"后序遍历:";
	PostOrder(BT);
	cout<<endl;
	cout<<"叶子节点:";
	DispLeaf(BT); 
	cout<<endl;
	cout<<a<<"的祖先结点:";
	ancestor(BT,a);
	cout<<endl;
	cout<<"层次遍历:";
	LevelOrder(BT); 
	cout<<endl;
	cout<<"高度为:";
	height=BTNodeHeight(BT);
	cout<<height;
	 
}

0x2 二叉树构造、线索二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
#include<stdio.h>
#include<iostream>
#include<malloc.h> 
using namespace std;
#include<queue>
typedef char ElemType;
#define MaxSize 200
typedef struct node
{     ElemType data;
       struct node *lchild, *rchild;
}BTNode;    
typedef BTNode *BTree;



//层次遍历 
void LevelOrder(BTree bt)
{  queue<BTree> q;    //初始化队列，元素为树节点
  BTree p;                 //树指针p
  if(bt!=NULL) q.push(bt);  //根节点入队列
  while(!q.empty())
  {      p=q.front();  //访问队头节点
  	q.pop();
  	cout<<p->data<<" ";
  	if(p->lchild) q.push(p->lchild);//左右孩子入队
  	if(p->rchild) q.push(p->rchild);
  }}
  

//先序中序构造二叉树 
BTNode *CreateBT1(char *pre,char *in,int n)
{  BTNode *s;  char *p;  int k;
   if (n<=0) return NULL;
   s=new BTNode;
   s->data=*pre;                                                                   //创建根节点              
   for (p=in;p<in+n;p++)      //在中序中找为*ppos的位置k
	 if (*p==*pre)
	      break;
   k=p-in;
   s->lchild=CreateBT1(pre+1,in,k);   //构造左子树
   s->rchild=CreateBT1(pre+k+1,p+1,n-k-1); //右子树                                                                                                                                            //右子树
   return s;
} 
//中序和后序构造二叉树 
BTNode *CreateBT2(char *post,char *in,int n)
{  BTNode *s;  char *p;  int k;
   if (n<=0) return NULL;
   s=(BTNode *)malloc(sizeof(BTNode));//创建节点
   s->data=*(post+n-1);        //构造根节点。
   for (p=in;p<in+n;p++)//在中序中找为*ppos的位置k
	 if (*p==*(post+n-1))
	      break;
   k=p-in;
   s->lchild=CreateBT2(post,in,k);	//构造左子树
   s->rchild=CreateBT2(post+k,p+1,n-k-1);//构造右子树
   return s;
} 
//ABCD#EF#G######顺序存储结构转成二叉链 有点问题，以后再探索 
BTree CreateBTree(string str,int i)
{
   int len;
   BTree bt;
   bt=new BTNode;
   len=str.size();
   if(i>len || i<=0) return NULL;
   if(str[i]=='#') return NULL;
   bt->data =str[i];
   bt->lchild =CreateBTree(str,2*i); 
   bt->rchild =CreateBTree(str,2*i+1); 
   return bt;
}
int main(){
	char str[100]={'A','B', 'C','D', 'F', 'G', 'I','0','0','E', '0', '0', 'H', '0', '0', '0', '0', '0', '0'};
	char pre[40]="ABDFCEGH";
	char in[40]="BFDAGEHC";
	char in1[40]="BDCEAFHG";
	char ord[40]="DECBHGFA";
	string seq="ABCD#EF#G######";
	int height;
	BTree BT;
	BTree BT1;
	BTree BT2; 
	BT=CreateBT1(pre,in,8);
	LevelOrder(BT);
	cout<<endl;
    BT1=CreateBT2(ord,in1,8);
    LevelOrder(BT1);
    cout<<endl;
    BT2=CreateBTree(seq,0);
    LevelOrder(BT2); 
}

0x3哈夫曼编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
typedef struct
{	char data;		//节点值
	float weight;	//权重
	int parent;		//双亲节点
	int lchild;		//左孩子节点
	int rchild;		//右孩子节点
} HTNode; 

//初始化哈夫曼编码 
void CreateHT(HTNode ht[],int n)
{  int i,j,k,lnode,rnode; float min1,min2;
   //此处补充叶子节点相关设置
   for (i=0;i<2*n-1;i++)	  	//所有节点的相关域置初值-1
      ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
   for (i=n;i<2*n-1;i++)		//构造哈夫曼树
   {  min1=min2=32767; lnode=rnode=-1;
	for (k=0;k<=i-1;k++)
	  if (ht[k].parent==-1)		//未构造二叉树的节点中查找
	  {  if (ht[k].weight<min1)
	     {  min2=min1;rnode=lnode;
		  min1=ht[k].weight;lnode=k;  }
	     else if (ht[k].weight<min2)
	     {  min2=ht[k].weight;rnode=k;  }   
        } //if
	  ht[lnode].parent=i;ht[rnode].parent=i;
        ht[i].weight=ht[lnode].weight+ht[rnode].weight;
	  ht[i].lchild=lnode;ht[i].rchild=rnode;
   }
} 

typedef struct{  
	 char cd[10];  //存放当前节点的哈夫曼码   
	 int start;//哈夫曼码在cd中的起始位置
}HCode;


//根据哈夫曼树求对应的哈夫曼编码的算法如下：
void CreateHCode(HTNode ht[],HCode hcd[],int n)
{  int i,f,c; HCode hc;
   for (i=0;i<n;i++)		//根据哈夫曼树求哈夫曼编码
   {  hc.start=n;c=i; f=ht[i].parent;
	while (f!=-1)   //循环直到无双亲节点即到达树根节点
	{  if (ht[f].lchild==c)	//当前节点是左孩子节点
	      hc.cd[hc.start--]='0';
	   else	  		//当前节点是双亲节点的右孩子节点
	      hc.cd[hc.start--]='1';
	   c=f;f=ht[f].parent; //再对双亲节点进行同样的操作
 	 }
	 hc.start++;		//start指向哈夫曼编码最开始字符
       hcd[i]=hc;
   }
}

FROM :blog.cfyqy.com | Author:cfyqy

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年1月6日01:31:22
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出)：
                   数据结构整理http://cn-sec.com/archives/721737.html

发表评论

匿名网友 填写信息