ãæ½è±¡æ°æ®ç±»å 循ç¯éå æä¼äºåæ é»æ¥ç©éµåé»æ¥è¡¨ 稳å®æåºåä¸ç¨³å®æåº
2ãåç§é»è¾ç»æçå驱åå继çå
³ç³»
3ã顺åºåå¨ç»æè¦æ±åå¨ç©ºé´æ¯è¿ç»çãå
ç´ ä¹é´çå
³ç³»ç¨ä¸æ 表示ï¼é¾å¼åå¨è¦æ±åå¨ç©ºé´æ¯ä¸è¿ç»çï¼å
ç´ ä¹é´çå
³ç³»ç¨æé表示ã
4ãT(n)åS(n)åå«è¡¨ç¤ºä»ä¹ï¼
5ãä½è°ä¸æº¢åä¸æº¢ã溢æ¯å½ä¸ä¸ªè¶
é¿çæ°æ®è¿å
¥å°ç¼å²åºæ¶ï¼è¶
åºé¨å被åå
¥ä¸çº§ç¼å²åºï¼ä¸çº§ç¼å²åºåæ¾çå¯è½æ¯æ°æ®ãä¸ä¸æ¡æ令çæéï¼æè
æ¯å
¶ä»ç¨åºçè¾åºå
容ï¼è¿äºå
容é½è¢«è¦çæè
ç ´åæãå¯è§ä¸å°é¨åæ°æ®æè
ä¸å¥æ令ç溢åºå°±å¯è½å¯¼è´ä¸ä¸ªç¨åºæè
æä½ç³»ç»å´©æºã
ä¸æº¢æ¯å½ä¸ä¸ªè¶
é¿çæ°æ®è¿å
¥å°ç¼å²åºæ¶ï¼è¶
åºé¨å被åå
¥ä¸çº§ç¼å²åºï¼ä¸çº§ç¼å²åºåæ¾çæ¯ä¸ä¸æ¡æ令çæéï¼æè
æ¯å
¶ä»ç¨åºçè¾åºå
容ã
5ã广ä¹è¡¨è¡¨é¿å深度æ±è§£
6ãæ åå®å
¨å¾ä¸è¾¹ç个æ°ä¸ºå¤å°
è¥ä¸ä¸ªå®å
¨æ åå¾å
·ænæ¡è¾¹ï¼å该å¾ç顶ç¹ä¸ªæ°ä¸º2n+1/4)+1/2
7ãæåæ¥æ¾çåææ¯ï¼ç´¢å¼æ¥æ¾ç表ç»æçææï¼
åææ¯å¿
é¡»ææåºè¡¨ãåªè½ç±äºéææ¥æ¾
8ãä»ä¹æåºçæ¯è¾æ¬¡æ°ä¸å
ç´ çåå§ç¶ææ å
³ã éæ©æåºåå½å¹¶æåº
9ãå¨ä¸ä¸ªé¿åº¦ä¸ºnç顺åºè¡¨ä¸ç¬¬i个å
ç´ ï¼1â¤iâ¤nï¼åæå
¥ä¸ä¸ªå
ç´ æ¶ï¼éåå移å¨å¤å°å
ç´ n-i-1
10ãheadåtailç综å使ç¨
11ãå¨æåå¾ä¸æ¯ä¸ªé¡¶ç¹ç度çäºè¯¥é¡¶ç¹ç( n(n-1)|2 )ã
12ãäºåæ ç深度æ±è§£
13ãäºåæ ç深度æ±è§£
14ãå°ä¸é¢å·²ç¥æ 转æ¢æäºåæ ï¼ååºååºéåçç»æã
#include "iostream.h"
#include "stdlib.h"
#define MaxSize 100
typedef char ElemType;
typedef struct Node
{
ElemType data;
struct Node *left,*right;
}BTree; //æ çåå
ç»æ
void creatree(BTree **BT,ElemType *str)
{
//æ ¹æ®æ¬å¼§è¡¨ç¤ºæ³å建ä¸æ£µäºåæ
BTree *stack[MaxSize],*p;
int top=-1,k,j=0; //top为æ æé,kæå®æ¯å·¦è¿æ¯å³å©å,j为stræé
char ch;
*BT=NULL;
ch=str[j];
while(ch!='\0')
{
switch(ch)
{
case '(':
top++;
stack[top]=p;
k=1; //æ 示为左å©å
break;//////////////////ä½ è¿éå°äºbreak;
case ')':
top--;
break;
case ',':
k=2;//æ 示为å³å©å
break;
default:
p=(BTree *)malloc(sizeof(BTree));
p->data=ch;
p->left=p->right=NULL;
if(*BT==NULL) //æ ¹ç»ç¹
*BT=p;
else{
switch(k)
{
case 1:
stack[top]->left=(BTree *)malloc(sizeof(BTree));
stack[top]->left=p;break;
case 2:
stack[top]->right=(BTree *)malloc(sizeof(BTree));
stack[top]->right=p;
}
}
}
j++;
ch=str[j];
}
}
void postorder(BTree *BT)
{ //ååºéå
if(BT!=NULL)
{
postorder(BT->left);
postorder(BT->right);
cout<<BT->data;
}
}
int BTreeDepth(BTree *BT)
{ //æ±äºåæ ç深度
int leftdep,rightdep;
if(BT==NULL)
return 0;
else
{
leftdep=BTreeDepth(BT->left);
rightdep=BTreeDepth(BT->right);
if(leftdep>rightdep)
return leftdep+1;
else
return rightdep+1;
}
}
int nodecount(BTree *BT)
{ //æ±ç»ç¹æ°
if(BT==NULL)
return 0;
else
{
return(nodecount(BT->left)+nodecount(BT->right)+1);
}
}
int leafcount(BTree *BT)
{ //å¶åç»ç¹
if(BT==NULL)
return 0;
else if(BT->left==NULL && BT->right==NULL)
return 1;
else
return (leafcount(BT->left)+leafcount(BT->right)+1);
}
int noleafcount(BTree *BT){ //éå¶åç»ç¹
if(BT==NULL)
return 0;
else if(BT->left==NULL && BT->right==NULL)
return 0;
else
return(noleafcount(BT->left)+noleafcount(BT->right)+1);
}
int main(){
char yumensi[100],tianla;
int i=0;
cout<<"请ç¨æ¬å·è¡¨ç¤ºæ³è¾å
¥ä¸æ£µäºåæ 并以ä¸ä¸ª.ç»æ,ä¾å¦"<<"'A(B(D,E(H,I)),C(G)).'"<<endl;
cout<<"请注ææ£ç¡®è¾å
¥å 为ç¨åºä¸è½å¤æè¾å
¥æ¯å¦æ£ç¡®!!å¦ååæèªè´!!"<<endl;
cin>>tianla;
while(tianla!='.')
{
yumensi[i]=tianla;
i++;
cin>>tianla;
}
yumensi[i]='\0';
BTree *tree;
creatree(&tree,yumensi);
cout<<"å
åºéåç»æ:";
preorder(tree); cout<<endl;
cout<<"ä¸åºéåç»æ:";
inorder(tree); cout<<endl;
cout<<"ååºéåç»æ:";
postorder(tree); cout<<endl;
cout<<"æ·±å¤ä¸º:"<<BTreeDepth(tree)<<endl;
cout<<"ç»ç¹ä¸ªæ°:"<<nodecount(tree)<<endl;
cout<<"å¶åç»ç¹ä¸ªæ°:"<<leafcount(tree)<<endl;
cout<<"éå¶åç»ç¹ä¸ªæ°:"<<noleafcount(tree)<<endl;
cout<<"BY: B.Lee çæ没æï¼ççä¸ç©¶"<<endl;
return 1;
}
15ãå·²ç¥æåå¾ï¼è¯·ç»åºè¯¥å¾çé»æ¥è¡¨ç表示å计ç®é¡¶ç¹ç度
16ãååºç´æ¥æå
¥æåºçæåºè¿ç¨ã
for(i = 1; i < n; ++i)
{
int temp = a[i];
for (j = i; j > 0 && temp < a[j - 1]; --j)
{
a[j] = a[j - 1];
}
a[j] = temp;
17ãç»å®å个ç»ç¹A,B,C,Dçæå¼æ¥æé ä¸æ£µå夫æ¼æ ï¼ååºå夫æ¼ç¼ç ï¼æ±åºå¹³åç¼ç é¿åº¦ã
18ã对ç»å®ç带ææ åå¾ç¨PRIMç®æ³æ±åºæå°çææ ï¼å¹¶ååºè®¡ç®è¿ç¨ã
PRIM(ç®åç) æå°çææ ç®æ³ (Minimum Spanning Tree)
* è¾å
¥ï¼å¾gï¼ // æåå¾æè
æ åå¾
* è¾åºï¼(1)æå°çææ é¿sumï¼
* (2)æå°çææ prevã
* ç»æ: å¾gç¨é»æ¥ç©éµè¡¨ç¤ºï¼æçè¾¹é¿distç¨æ°ç»è¡¨ç¤ºã
* ç®æ³ï¼Primç®æ³
* å¤æ度ï¼O(|V|^2)
*/
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;
int n; // n : 顶ç¹ä¸ªæ°
vector<vector<int> > g; // g : å¾(graph)(ç¨é»æ¥ç©éµ(adjacent matrix)表示)
vector<bool> known; // known : åç¹æ¯å¦å·²ç»éå
vector<int> dist; // dist : å·²éåç¹éå°æªéåç¹çæå°è¾¹é¿
vector<int> prev; // prev : æå°çææ ä¸åç¹çåä¸é¡¶ç¹
int s; // s : èµ·ç¹(start)
int sum; // sum : æå°çææ é¿
bool Prim() // è´ªå¿ç®æ³(Greedy Algorithm)
{
known.assign(n, false);
dist.assign(n, INT_MAX);
prev.resize(n); // åå§åknownãdistãprevã
dist[s] = 0; // åå§åèµ·ç¹å°èªèº«çè·¯å¾é¿ä¸º0ã
int i;
for (i = 0; i < n; ++i)
{
int min = INT_MAX, v;
for (int i = 0; i < n; ++i)
if (!known[i] && min > dist[i])
min = dist[i], v = i; // 寻æ¾æªç¥çæçè·¯å¾é¿ç顶ç¹vï¼
if (min == INT_MAX) break; // å¦ææ¾ä¸å°ï¼éåºï¼
known[v] = true; // å¦ææ¾å°ï¼å°é¡¶ç¹v设为已ç¥ï¼
sum += dist[v]; // è°æ´æå°çææ é¿
for (int w = 0; w < n; ++w) // éåæævæåç顶ç¹wï¼
if (!known[w] && g[v][w] < INT_MAX && dist[w] > g[v][w])
dist[w] = g[v][w], prev[w] = v; /* è°æ´é¡¶ç¹wçæçè·¯å¾é¿diståæçè·¯å¾çåä¸é¡¶ç¹ prevã */
}
return i == n; // å¦æéå顶ç¹ä¸ªæ°ä¸ºnï¼æåã
}
int main()
{
n = 7;
g.assign(n, vector<int>(n, INT_MAX));
g[0][1] = g[1][0] = 2; g[0][2] = g[2][0] = 4; g[0][3] = g[3][0] = 1;
g[1][3] = g[3][1] = 3; g[1][4] = g[4][1] = 10;
g[2][3] = g[3][2] = 2; g[2][5] = g[5][2] = 5;
g[3][4] = g[4][3] = 7; g[3][5] = g[5][3] = 8; g[3][6] = g[6][3] = 4;
g[4][6] = g[6][4] = 6;
g[5][6] = g[6][5] = 1;
s = 0; // èµ·ç¹ä»»é
sum = 0;
if (Prim())
{
cout << sum << endl;
for (int i = 1; i < n; ++i)
if(i != s) cout << prev[i] << "->" << i << endl;
}
else
{
cout << "Some vertex cann't be reached." << endl;
}
system("pause");
return 0;
}
19ã对äºç»å®7个æ°æ®å
ç´ çæåºè¡¨,éç¨é¡ºåºæ¥æ¾, å设æ¥æ¾è¡¨ä¸æ¯ä¸ªå
ç´ çæ¦çç¸å,æ±æ¥æ¾æåæ¶çå¹³åæ¥æ¾é¿åº¦ã
20ãååºä¸å¸¦å¤´ç»ç¹çåé¾è¡¨çå并ç®æ³,å é¤éå¤ç»ç¹ã
#include<stdio.h>
typedef struct node
{
int data;
struct node *next;
}LNode,*LinkList;
LinkList Create_LinkList()
{
LinkList L=NULL;
LNode *s,*h=NULL;
int x;
scanf("%d",&x);
while(x!=-1)
{
s=(LNode *)malloc(sizeof(LNode));
s->data=x;
if(L==NULL) L=s;
else h->next=s;
h=s;
scanf("%d",&x);
}
if(h!=NULL) h->next=NULL;
return L;
}
void pur_linklist(LinkList H)
{
LNode *q,*r;
q=H;
if(q==NULL) return;
while(q->next)
{
if(q->data==q->next->data)
{ r=q->next;
q->next=r->next;
free(r);
q=q->next;
}
else q=q->next;
}
}
main()
{
LinkList H;
LNode *p;
H=Create_LinkList();
pur_linklist(H);
p=H;
while(p)
{
printf("%d\n",p->data);
p=p->next;
}
}
#include<iostream>
#include<stdlib.h>
using namespace std;
#define MAXSIZE 100
typedef int DataType;
typedef struct
{
DataType * elem; //线æ§è¡¨çåºå°å
int length; //线æ§è¡¨å½åçé¿åº¦
int listsize; //线æ§è¡¨å½ååé
çæ大åå¨å
容容é
}SeqList;
void CreatList(SeqList *L)
{
cout<<"è¾å
¥çº¿æ§è¡¨å½åé¿åº¦ï¼";
cin>>L->length;
//åé
空é´
L->elem = (int*) malloc(L->length*sizeof(int));
cout<<"请æä»å°å°å¤§ååºè¾å
¥çº¿æ§è¡¨çå个å
ç´ ";
for(int i = 0;i< L->length;i++)
{
cin>>L->elem[i];
}
L->listsize = L->length;
}
void MergeSeqList(SeqList *A, SeqList *B, SeqList *C)
{
DataType *pa, *pb, *pc, *palast, *pblast;
pa = A->elem; pb = B->elem;
C->length = A->length + B->length;
C->elem = (DataType*)malloc(C->length*sizeof(DataType));
if(!C->elem) exit(-1);
palast = A->elem + A->length - 1;
pblast = B->elem + B->length - 1;
pc = C->elem;
while(pa <= palast && pb <= pblast)
{
if(*pa <= *pb)
{
*pc = *pa;
pc++;
pa++;
}
else
{
*pc=*pb;
pc++;
pb++;
}
}
while(pa<=palast) {
*pc=*pa;
pc++;
pa++;
}
while(pb<=pblast)
{
*pc=*pb;
pc++;
pb++;
}
}
void DisList(SeqList *L)
{
for(int i=0;i<L->length;i++)
{
cout<<L->elem[i]<<" ";
}
cout<<endl;
}
void main()
{
SeqList A,B,C;
cout<<"顺åºè¡¨Aï¼"<<endl;
CreatList(&A);
cout<<"顺åºè¡¨Bï¼"<<endl;
CreatList(&B);
MergeSeqList(&A,&B, &C);
cout<<"顺åºè¡¨Cï¼"<<endl;
DisList(&C);
}
温馨提示:答案为网友推荐,仅供参考