854之数据结构

一.线性表
1.顺序表

#include <iostream>
#include<stdlib.h>
using namespace std;
#define max 100
typedef struct
{int element[max];int last;
} List;
typedef int position ;
void Insert(int x, position p, List &L)
{position q;if (L.last >= max - 1)cout << 'full';else if (p > L.last + 1 || p < 1)cout << "error";else{for (q = L.last; q >= q; q--){L.element[q+1] = L.element[q];}L.element[p] = x;L.last++;}
}
void Delete(position p, List& L)
{position q;if (p > L.last + 1 || p < 1)cout << "error";else{L.last--;for (q = p; q <= L.last; q++)L.element[q] = L.element[q + 1];}}
position Locate(int x, List L)
{position q;for (q = 1; q <= L.last; q++)if (L.element[q] == x)return q;return -1;
}
int Retrieve(position p, List L)
{if (p > L.last || p < 1)cout << "error";else return L.element[p];
}
position Previous(position p, List L)
{if (p > L.last || p <= 1)cout << "error";else{return p-1;}
}

2.单链表

#include <iostream>
#include<stdlib.h>
using namespace std;typedef int ElemType;struct celltype
{ElemType data;celltype * next;
};//结点型
typedef celltype* List;
typedef celltype* position;
void Insert(ElemType x, position p, List& L)
{position q;q = new celltype;q->data = x;q->next = p->next;p->next = q;
}
void Delete(position p,List&L)
{   position q=NULL;if (p->next != NULL){q->next = p->next;p->next = q->next;delete q;}}
position Locate(ElemType x, List& L)
{position p;p = L;while (p->next != NULL){if (p->next->data == x)return p;elsep = p->next;}return p;
}
ElemType Retrieve(position p, List L)
{return p->next->data;
}position Previous(position p, List L)
{position q;if (p == L->next)cout << "error";else{q = L;while (q->next!=NULL){q = q->next;}return q;}
}
position Next(position p, List L)
{position q;if (p->next == NULL)cout << "error";else{q = p->next;return q;}
}
position MakeNull(List& L)
{   L = new celltype;L->next = NULL;return L;
}
position First(List L)
{return L;
}
position End(List L)
{position q;q = L;while (q->next != NULL)q = q->next;return q;
}
position Travel(List L)
{position q;q = L->next;while (q!=NULL){cout << q->data;q = q->next;}
}
int main()
{cout << "text";
}

3.线性表静态存储

#include <iostream>
#include<stdlib.h>
#define maxsize 12
using namespace std;
int avail;
typedef int ElemType;
typedef struct
{    ElemType data;int next;
}spacestr;
spacestr SPACE[maxsize];//储存池
typedef int position,Cursor;void Initialize()
{int j;for (j = 0; j < maxsize - 1; j++){SPACE[j].next = j + 1;}SPACE[maxsize].next = -1;avail = 0;
}
Cursor GetNode()
{Cursor p;if (SPACE[avail].next = -1)p = -1;else{p = SPACE[avail].next;SPACE[avail].next = SPACE[p].next;}return p;
}
void FreeNode(Cursor q)
{SPACE[q].next = SPACE[avail].next;SPACE[avail].next = q;
}
void Insert(ElemType x, position p, spacestr* SPACE)
{position q = GetNode();SPACE[q].data = x;SPACE[q].next = SPACE[p].next;SPACE[p].next = q;
}
void Delete(position p, spacestr* SPACE)
{position q;q = SPACE[p].next;SPACE[p].next = SPACE[q].next;FreeNode(q);
}int main()
{cout << "text";
}

4.双链表

#include <iostream>
#include<stdlib.h>
using namespace std;
typedef int ElemType;
struct dcelltype
{ElemType data;dcelltype* next,*prior;
};//结点型
typedef dcelltype* DList;
typedef dcelltype* position;void Insert(ElemType x, position p, DList& L)
{position s;s = new dcelltype;s->data = x;s->prior = p;s->next = p->next;p->next->prior = s;p->next = s;
}
void Delete(position p, DList& L)
{   //if(p->prior!=NULL) 不带头结点的情况下p->prior->next = p->next;//if(p->next!=NULL)p->next->prior = p->prior;delete(p);
}int main()
{cout << "text";
}

5.单向环形链表

#include <iostream>
#include<stdlib.h>
using namespace std;typedef int ElemType;struct celltype
{ElemType data;celltype* next;
};//结点型
typedef celltype* List;
typedef celltype* position;
void LInsert(ElemType x,  List& L)
{celltype* p;p = new celltype;p->data = x;if (L == NULL){p->next = p;L = p;}else{p->next = L->next;L->next = p;}
}
void RLnsert(ElemType x, List& L)
{LInsert(x, L);L= L->next ;
}void Josephus(List& Js, int n, int m)
{celltype* p = Js, * pre = NULL;for (int i = 0; i < n - 1; i++){for (int j = 0; j < m - 1; j++){pre = p; p = p->next;}cout << "出列的人是" << p->data << endl;pre->next = p->next;delete p;p = pre->next;}
}
int main()
{cout << "text";
}

6.多项式的加法

#include <iostream>
#include<stdlib.h>
using namespace std;typedef int ElemType;
// p(x)=3*x^14+2*x^8+1多项式
struct polynode {int coef;//系数int exp;//指数polynode* link;
};
typedef polynode* polypointer;
polypointer Attch(int c, int e, polypointer& d)
{polypointer x;x = new polynode;x->coef = c;x->exp = e;d->link = x;return x;
}
polypointer PolyAdd(polypointer a, polypointer b)
{polypointer p, q, d, c;int y;p = a->link;q = b->link;c = new polynode;d = c;while (p!=NULL&&q!=NULL){if (p->exp == q->exp){y = p->coef + q->coef;if (y)d = Attch(y, p->exp, d);p = p->link;q = q->link;}else if (p->exp<q->exp){d = Attch(q->coef, q->exp, d);q = q->link;}else if (p->exp > q->exp){d = Attch(p->coef, p->exp, d);p = p->link;}}while (p!=NULL){d = Attch(p->coef, p->exp, d);p = p->link;}while (q != NULL){d = Attch(q->coef, q->exp, d);q = q->link;}
}
int main()
{cout << "text";
}

二.栈
1.顺序表栈

#include <iostream>
#include<stdlib.h>
#define max 10
using namespace std;typedef int ElemType;
typedef struct
{ElemType elemtype[max];int top;
}STACK;
STACK s;
void MakeNull(STACK& s)
{s.top = -1;}
bool Empty(STACK& s)
{   if (s.top < 0)return true;elsereturn false;
}
ElemType Top(STACK s)
{if (Empty(s))cout << "error";elsereturn s.elemtype[s.top];
}
void Pop(STACK &s)
{if (Empty(s))cout << "error";elses.top = s.top - 1;
}
void Push(ElemType x, STACK& s)
{if (s.top == -1)cout << 'full';else{s.top++;s.elemtype[s.top] = x;}
}
int main()
{cout << "text";
}

2.栈的链式表

#include <iostream>
#include<stdlib.h>
#define max 10
using namespace std;typedef int ElemType;
struct Node
{ElemType data;Node* next;
};
typedef Node* STACK;
STACK MakeNull()
{STACK s;s = new Node;s->next = NULL;return s;
}
bool Empty(STACK s)
{if (s->next)return false;elsereturn true;
}
void Push(ElemType x, STACK s)
{STACK st;st = new Node;st->data = x;st->next = s->next;s->next = st;
}
void Pop(STACK s)
{STACK st;if (Empty(s))cout << "error";else{st = s->next;s->next = st->next;delete st;}
}
ElemType Top(STACK s)
{if (s->next)return s->next->data;else{return -1;}
}
int main()
{cout << "text";
}

3.递归应用

#include <iostream>
#include<stdlib.h>
#define max 10
using namespace std;long fact(int n)//计算n!
{if (n == 1)return 1;else return  n*fact(n - 1);
}
void Move(char a, char b)
{}
void Hanoi(int n, char a, char b, char c)
{if (n == 1) Move(a, c);else{Hanoi(n - 1, a, c, b);Move(a, c);Hanoi(n - 1, b,a,c);}
}
int main()
{cout << "text";
}

4.栈的应用

#include <iostream>
#include<stdlib.h>
#define max 10
using namespace std;typedef int ElemType;
struct Node
{ElemType data;Node* next;
};
typedef Node* STACK;
STACK MakeNull()
{STACK s;s = new Node;s->next = NULL;return s;
}
bool Empty(STACK s)
{if (s->next)return false;elsereturn true;
}
void Push(ElemType x, STACK s)
{STACK st;st = new Node;st->data = x;st->next = s->next;s->next = st;
}
void Pop(STACK s)
{STACK st;if (Empty(s))cout << "error";else{st = s->next;s->next = st->next;delete st;}
}
ElemType Top(STACK s)
{if (s->next)return s->next->data;else{return -1;}
}
void strol8()
{int n;STACK s;s = MakeNull();cin >> n;while (n){Push(n % 8, s);//输入十进制转为八进制n /= 8;}while (!Empty(s)){cout << Top(s);Pop(s);}
}void main()
{strol8();}

三.队列
1.链式队列

#include <iostream>
#include<stdlib.h>
#define max 10
using namespace std;typedef int ElemType;
struct celltype
{ElemType data;celltype* next;
};//结点型
struct QUEUE
{celltype* front;celltype* rear;
};
void MakeNull(QUEUE &Q)
{Q.front = new celltype;Q.front->next = NULL;Q.rear = Q.front;
}
bool Empty(QUEUE& Q)
{if (Q.rear == Q.front)return true;elsereturn false;
}
void EnQueue(ElemType x, QUEUE Q)
{celltype* q;q = new celltype;q->data = x;q->next = NULL;Q.rear->next = q;Q.rear = q;
}
void DeQueue(QUEUE& Q)
{celltype* q;if (Empty(Q))cout << "empty";q = Q.front->next;Q.front->next = q->next;if (q->next == NULL)Q.rear = Q.front;delete q;
}
ElemType Front(QUEUE& Q)
{if (Empty(Q))cout << "empty";elsereturn Q.front->next->data;
}void main()
{cout << 'test';}

2.循环数组队列

#include <iostream>
#include<stdlib.h>
#define maxlength 10
using namespace std;typedef int ElemType;struct QUEUE
{ElemType data[maxlength];int front;int rear;
};
void MakeNull(QUEUE& Q)
{Q.front = 0;Q.rear = maxlength - 1;
}
int addone(int i)
{return ((i + 1)% maxlength);
}
bool Empty(QUEUE Q)
{if (addone(Q.rear) ==Q.front)return true;elsereturn false;
}
ElemType Front(QUEUE Q)
{if (Empty(Q))return NULL;elsereturn (Q.data[Q.front]);
}
void EnQueue(ElemType x, QUEUE& Q)
{if (addone(addone(Q.rear)) == Q.front)cout<<"error";else {Q.rear = addone(Q.rear);Q.data[Q.rear] = x;}
}
void DeQueue(QUEUE& Q)
{ if (Empty(Q))cout<<"error";elseQ.front = addone(Q.front);
}
void main()
{cout << 'test';}

串

#include <iostream>
#include<stdlib.h>
#define maxlength 10
using namespace std;typedef int ElemType;int Index_BF(char* S, char* T, int post = 1)
{//S为主串，T为模式串;int i = post, j = 1;while (i<=S[0]&&j<=T[0]){if (S[i] == T[j]){i++;j++;}else{i = i - j + 2;j = 1;}}if (j > T[0])return i - T[0];elsereturn 0;
}
void main()
{cout << 'test';}

广义表

#include <iostream>
#include<stdlib.h>
#define maxlength 10
using namespace std;typedef int ElemType;typedef struct
{int i, j;ElemType v;
}Triple;
typedef struct
{Triple data[maxlength + 1];int mu, nu, tu;
}TSMatirx;
//广义表
struct listnode
{listnode* link;bool tag;union {char data;listnode* dlink;}element;
};
typedef listnode* listpointer;bool Equal(listpointer S, listpointer T)
{bool x, y;y = false;if ((S == NULL) && (T == NULL))y = true;else if ((S != NULL) && (T != NULL))if (S->tag == T->tag){if (S->tag == false){if (S->element.data == T->element.data)x = true;elsex = false;}elsex = Equal(S->element.dlink, T->element.dlink);if (x == true)y = Equal(S->link, T->link);}return y;
}
void main()
{    // 创建广义表1: [a, [b, c]]listpointer cNode = new listnode;cNode->tag = false;cNode->element.data = 'c';cNode->link = NULL;listpointer bNode = new listnode;bNode->element.data = 'b';bNode->link = cNode;listpointer aNode = new listnode;aNode->tag = true;aNode->element.dlink = NULL;aNode->link = bNode;listpointer list1 = aNode;// 创建广义表2: [a, [b, c]]listpointer cNode2 = new listnode;cNode2->tag = false;cNode2->element.data = 'c';cNode2->link = NULL;listpointer bNode2 = new listnode;bNode2->tag = false;bNode2->element.data = 'b';bNode2->link = cNode2;listpointer aNode2 = new listnode;aNode2->tag = true;aNode2->element.dlink = NULL;aNode2->link = bNode2;listpointer list2 = aNode2;bool isEqual = Equal(list1, list2);if (isEqual)printf("广义表相等\n");elseprintf("广义表不相等\n");// 释放内存free(cNode);free(bNode);free(aNode);free(cNode2);free(bNode2);free(aNode2);}

二叉树

#include <iostream>
#include<stdlib.h>
#define maxlength 10
using namespace std;typedef char ElemType;struct node
{ElemType data;node* Lchild;node* Rchild;
};
typedef node* BTREE;
void PreOrder(BTREE t)
{if (t == NULL)return;printf("%c", t->data);PreOrder(t->Lchild);PreOrder(t->Rchild);}
void InOrder(BTREE t)
{if (t == NULL)return;InOrder(t->Lchild);printf("%c", t->data);InOrder(t->Rchild);}
void PostOrder(BTREE t)
{if (t == NULL)return;PostOrder(t->Lchild);PostOrder(t->Rchild);printf("%c", t->data);}
BTREE create()
{BTREE t;char c = getchar();if (c == '#')return NULL;t = new node;t->data = c;t->Lchild = create();t->Rchild = create();return t;
}void main()
{  cout << "test";
}

用栈模拟二叉树遍历

#include <iostream>
#include<stdlib.h>
#define maxlength 10
using namespace std;typedef char ElemType;struct node
{ElemType data;node* Lchild;node* Rchild;
};typedef node* BTREE;
typedef node* elemType;
struct stack
{elemType ptr;int flag;
};
stack st[maxlength];
struct Node
{elemType data;Node* next;
};
typedef Node* STACK;
STACK MakeNull()
{STACK s;s = new Node;s->next = NULL;return s;
}
bool Empty(STACK s)
{if (s->next)return false;elsereturn true;
}
void Push(elemType x, STACK s)
{STACK st;st = new Node;st->data = x;st->next = s->next;s->next = st;
}
void Pop(STACK s)
{STACK st;if (Empty(s))cout << "error";else{st = s->next;s->next = st->next;delete st;}
}
elemType Top(STACK s)
{if (s->next)return s->next->data;else{return NULL;}
}
void PreOrder(BTREE t) 
{BTREE s[maxlength];int top = -1;while (t!=NULL||top!=-1){while (t != NULL){cout << t->data;s[++top] = t;t = t->Lchild;}if (top != -1){t = s[top--];t = t->Rchild;}}
}
void PreOrder(BTREE t)//栈模仿递归
{STACK S;S=MakeNull();BTREE p;p = new node;while (p!=NULL){cout << p->data << endl;if (p->Rchild != NULL)Push(p->Rchild,S);if (p->Lchild != NULL)p = p->Lchild;//进左子树else{p = Top(S);Pop(S);}}
}
void InOrder(BTREE t)
{BTREE s[maxlength];int top = -1;while (t != NULL || top != -1){while (t != NULL){top++;st[top].ptr = t;st[top].flag = 1;t = t->Lchild;}while (top!=-1&&st[top].flag==2){t = st[top--].ptr;cout << t->data << endl;}if (top != -1){st[top].flag = 2;t = st[top].ptr->Rchild;}}
}
void InOrder(BTREE t)
{BTREE p, pr;STACK S;S = MakeNull();p = t;while (p!=NULL||!Empty(S)){while (p != NULL){Push(p, S);pr = p->Rchild;p = p->Lchild;if (p == NULL)p = pr;}p = Top(S); Pop(S);cout << p->data << endl;if (!Empty(S) && Top(S)->Lchild == p)p = Top(S)->Rchild;elsep = NULL;}
}
BTREE create()
{BTREE t;char c = getchar();if (c == '#')return NULL;t = new node;t->data = c;t->Lchild = create();t->Rchild = create();return t;
}void main()
{  cout << "test";
}

父母结点实现后序遍历

#include <iostream>
#include<stdlib.h>
#define maxlength 10
using namespace std;typedef char ElemType;struct node
{ElemType data;node* Lchild;node* Rchild;int flag;node* parent;
};void PostOrder(node* t)
{node* p;p = t;while (p != NULL){switch (p->flag){case 0:p->flag = 1;if (p->Lchild != NULL)p = p->Lchild;break;case 1:p->flag = 2;if (p->Rchild != NULL)p = p->Rchild;break;case 2:p->flag = 0;cout << p->data << endl;p = p->parent;break;}}
}void main()
{  cout << "test";
}

遍历实现

#include <iostream>
#include<stdlib.h>
#define maxlength 10
using namespace std;typedef char ElemType;
int n=0;
int top;
struct node
{ElemType data;node* Lchild;node* Rchild;
};
typedef node* BTREE;
BTREE Q[maxlength];
BTREE S[maxlength];void LeverOrder(BTREE t)
{int front, rear;BTREE q;front = rear = 0;if (t == NULL)return;Q[++rear] = t;while (front!=rear){q = Q[++front];cout << q->data;if (q->Lchild != NULL)Q[++rear] = q->Lchild;if (q->Rchild != NULL)Q[++rear] = q->Rchild;}
}
int Count(BTREE t)//层次计数
{if (t == NULL)return 0;elsereturn 1 + Count(t->Lchild) + Count(t->Rchild);
}
int Count(BTREE t)//中序计数
{//n是初始变量，且为0if (t){Count(t->Lchild);n++;Count(t->Rchild);}
}
//求二叉树高度的算法
int Height(BTREE t)
{if (t == NULL)return 0;else{int m = Height(t->Lchild);int n = Height(t->Rchild);return (m > n) ? (m + 1) : (n + 1);}
}
//删除二叉树递归算法
void Destroy(BTREE t)
{if (t != NULL){Destroy(t->Lchild);Destroy(t->Rchild);delete t;//后序遍历}
}
//交换二叉树的所有子树的递归算法
void Exchange(BTREE t)
{node* p = t, * tmp;if (p != NULL){tmp = p->Lchild;p->Lchild = p->Rchild;p->Rchild = tmp;Exchange(t->Lchild);Exchange(t->Rchild);}}
//交换二叉树的所有子树的非递归算法void Exchange(BTREE t)
{	BTREE p , tmp;top = -1;if (t != NULL){S[++top] = t;while (top!=-1){p = S[top--];tmp = p->Lchild;p->Lchild = p->Rchild;p->Rchild = tmp;if (p->Lchild != NULL)S[++top] = p->Lchild;if (p->Rchild != NULL)S[++top] = p->Rchild;}}
}

线索二叉树

#include <iostream>
#include<stdlib.h>
#define maxlength 10
using namespace std;typedef char ElemType;
struct node
{ElemType data;struct  node* lchild;struct node *rchild;bool ltag, rtag; //表示其是否存在左右子树，若为空则另其指向前驱后继
};
typedef struct node* THTREE;//线索二叉树
THTREE pre = NULL;
THTREE InNext(THTREE P)//中序结点二叉树求结点p的中序后继
{THTREE Q;Q = P->rchild;if (P->rtag )while (Q->ltag)Q = Q->lchild;return Q;
}
THTREE InPre(THTREE P)//中序结点二叉树求结点p的中序前驱
{THTREE Q;Q = P->lchild;if (P->ltag)while (Q->rtag)Q = Q->rchild;return Q;
}
void ThInOrder(THTREE head)//通过InNext实现中序遍历
{THTREE tmp;tmp = head;do{tmp = InNext(head);if (tmp != head)cout << tmp->data <<endl ;} while (tmp!=head);
}
THTREE PreNext(THTREE p)//中序结点二叉树求结点p的先序后驱
{THTREE Q;if (p->ltag)Q = p->lchild;else{Q = p;while (!Q->rtag)Q = Q->rchild;Q = Q->rchild;}return Q;
}
void RInsert(THTREE S,THTREE R)
{THTREE W;R->rchild = S->rchild;R->rtag = S->rtag;R->lchild = S;//S是R的左线索R->ltag = false;S->rchild = R;//R是S的右子树S->rtag = true;if (R->rtag)//如果S还有右子树，则接上R{W = InNext(R);W->lchild = R;}
}
void InOrderTh(THTREE p)//二叉树中序线索化
{if (p){InOrderTh(p->lchild);//左子树线索化p->ltag = (p->lchild) ? true : false;//判断是否有左右子树，来给线索位置赋值p->rtag = (p->rchild) ? true : false;if (pre)//如果p的前驱存在{if (pre->rtag == false)//p的右标志为线索pre->rchild = p;//pre的右子树指向中序后继if (pre->ltag == false)//p的左标志为线索pre->lchild = p;//pre的左子树指向中序前驱}pre = p;//令pre为下一个中序前驱InOrderTh(p->rchild);//线索化右子树
}

二叉树的复制判断

#include <iostream>
#include<stdlib.h>
#define maxlength 10
using namespace std;typedef char ElemType;
struct node
{ElemType data;struct  node* lchild;struct node *rchild;
};
typedef struct node* BTREE;//线索二叉树int Equal(BTREE firstbt, BTREE secondbt)//二叉树是否等价
{int x;x = 0;if (firstbt == NULL && secondbt == NULL)return 1;else if(firstbt!=NULL&&secondbt!=NULL){if (firstbt->data == secondbt->data)if (Equal(firstbt->lchild, secondbt->lchild))x = Equal(firstbt->rchild, secondbt->rchild);}return x;
}
BTREE copy(BTREE oldtree)//复制二叉树
{BTREE temp;if (oldtree != NULL){temp = new node;temp->data = oldtree->data;temp->lchild = copy(oldtree->lchild);temp->rchild = copy(oldtree->rchild);return temp;}return NULL;
}

树的应用，集合

#include <iostream>
#include<stdlib.h>
#define maxlength 10
using namespace std;typedef char ElemType;
struct CTNode
{//孩子结点int child;CTNode* next;
};
struct CTBox
{//表头结点ElemType data;CTNode* firstchild;};
struct 
{CTBox nodes[maxlength];int n, r;
}CTree;
//顺序存储struct CSNode
{//链式存储长子制，树的最左子树为长子，他管理剩下的子树ElemType data;CSNode* firstchild;CSNode* rightsib;
};
typedef CSNode* CSTREE;
struct node
{ElemType data;node* lchild;node* rchild;
};
typedef node* bitree;bitree foresttobitree(CTNode *p)//森林变成二叉树
{bitree s;if (p == NULL)s = NULL;else{s = new node;s->data = CTree.nodes[p->child].data;s->lchild = foresttobitree(CTree.nodes[p->child].firstchild);s->rchild = foresttobitree(p->next);}return s;
}
typedef int MFSET[maxlength + 1];//集合定义
//集合∪操作
void Union(int i, int j, MFSET parent)
{parent[i] = j;
}
void Initial(int x,MFSET parent)
{parent[x] = 0;
}
//寻找结点子树
int Find(int i, MFSET parent)
{int tmp = i;while (parent[tmp] != 0)tmp = parent[tmp];//回溯return tmp;
}
typedef struct
{int father;int count;
}mfset[maxlength + 1];//加权集合void UNION(int a, int b, mfset c)
{if (c[a].count > c[b].count){c[b].father = a;c[a].count += c[b].count;}else{c[a].father = b;c[b].count += c[a].count;}}
void Initial(int x, mfset c)
{c[x].count = 1;c[x].father = 0;
}
int find1(int i, mfset parent)
{int tmp = i;while (parent[tmp].father != 0)tmp = parent[tmp].father;//回溯return tmp;
}
void Equivalence(mfset S)
{int i, j, k,m;for (int i = 1; i <= maxlength + 1; i++)Initial(i, S);cin >> i >> j;//读入等价对while (!(i==0&&j==0))//等价对未读完{k = find1(i, S);//求i和j的根m = find1(j, S);if (k != m)UNION(i, j, S);//合并cout << i << j;}
}

哈夫曼树

#include <iostream>
#include<stdlib.h>
#define maxlength 10
using namespace std;typedef char ElemType;typedef struct
{double weight;int lchild;int rchild;int parent;
}HTNODE;
typedef struct
{ElemType ch;char bits[maxlength+1];
}CodeNode;
typedef CodeNode HuffmanCode[maxlength];typedef HTNODE HuffmanT[2*maxlength-1];
void initHT(HuffmanT T)
{for (int i = 0; i < 2 * maxlength - 1; i++){T[i].lchild = -1;T[i].rchild = -1;T[i].parent = -1;T[i].weight = 0;}
}
void inputW(HuffmanT T)
{for (int i = 0; i < 2 * maxlength - 1; i++){cin >>T[i].weight;}
}
void SelectMin(HuffmanT T, int i, int* p1, int* p2)
{if (T[i].weight < T[i + 1].weight)*p2 = i,*p1=i+1;else*p2 = i + 1,*p1=i;
}
void CreatHT(HuffmanT T)
{int i, p1, p2;initHT(T);inputW(T);for (int i = 0; i < 2 * maxlength - 1; i++){SelectMin(T, i, &p1, &p2);T[p1].parent = T[p2].parent = i;T[i].lchild = p1;T[i].rchild = p2;T[i].weight = T[p1].weight + T[p2].weight;}
}
HuffmanT T;
//根据哈夫曼树求哈夫曼表
void CharSetHuffmanEncoding(HuffmanT T, HuffmanCode H)
{int c, p, i;//c，p分别表示指示T中孩子和双亲的位置char cd[maxlength + 1];//临时存放编码int start;//指示编码在cd中的位置cd[0] = '\0';//编码结束符for (i = 0; i < maxlength; i++)//依次求叶子[i]的编码{H[i].ch = getchar();//读入叶子结点T[i]对应的字符start = maxlength;//编码起始位置的初值c = i;//从叶子T[i]开始上溯while (p=T[c].parent>=0)//直到上溯T[c]是树根{cd[--start] = (T[p].lchild == c) ? '0' : '1';//如果T[c]是T[p]的左孩子，生成0，否则1c = p;//上溯}strcpy(H[i].bits, &cd[start]);//复制编码H}
}

图的构造

#include <iostream>
#include<stdlib.h>
#define NumVertices 100
using namespace std;typedef char VertexData;
typedef int EdgeData;
//线性表
typedef struct
{VertexData verlist[NumVertices];//顶点表EdgeData edge[NumVertices][NumVertices];//邻接矩阵int n, e;
}MTGraph;
void  CreateMGraph(MTGraph *G)
{int i, j, k, w;cin >> G->n >> G->e;//输入顶点数和边数for (i = 0; i < G->n; i++)G->verlist[i] = getchar();for (i = 0; i < G->n; i++)for (j = 0; j < G->n; j++)G->edge[i][j]=0;for (k = 0; k < G->e; k++){cin >> i >> j >> w;//输入边的权值G->edge[i][j] = w;}}
typedef struct node//边表结点
{int adjvex;//邻接点域EdgeData cost;//边上权值node* next;
}EdgeNode;
typedef struct//顶点表结点
{VertexData vertex;//顶点数据域node* firstedge;//边表头指针;}VertexNode;
typedef struct//图的邻接表
{VertexNode vexlist[NumVertices];int n, e;
}AdjGraph;
//建立邻接链表
void CreateGraph(AdjGraph* G)
{int i, head,tail,weight;cin >> G->n >> G->e;for (i = 0; i < G->n; i++){cin >> G->vexlist[i].vertex;//输入顶点信息G->vexlist[i].firstedge = NULL;}for (i = 0; i < G->e; i++){cin >> head >> tail >> weight;//输入边的信息EdgeNode* p = new EdgeNode;//建立边结点p->adjvex = head;p->cost = weight;p->next = G->vexlist[tail].firstedge;//链入第head号的链表前段,头插法插入边G->vexlist[tail].firstedge = p;}
}

深度优先算法

#include <iostream>
#include<stdlib.h>
#define NumVertices 100
using namespace std;typedef char VertexData;
typedef int EdgeData;
//线性表
typedef struct
{VertexData verlist[NumVertices];//顶点表EdgeData edge[NumVertices][NumVertices];//邻接矩阵int n, e;
}MTGraph;
void  CreateMGraph(MTGraph *G)
{int i, j, k, w;cin >> G->n >> G->e;//输入顶点数和边数for (i = 0; i < G->n; i++)G->verlist[i] = getchar();for (i = 0; i < G->n; i++)for (j = 0; j < G->n; j++)G->edge[i][j]=0;for (k = 0; k < G->e; k++){cin >> i >> j >> w;//输入边的权值G->edge[i][j] = w;}}
typedef struct node//边表结点
{int adjvex;//邻接点域EdgeData cost;//边上权值node* next;
}EdgeNode;
typedef struct//顶点表结点
{VertexData vertex;//顶点数据域node* firstedge;//边表头指针;}VertexNode;
typedef struct//图的邻接表
{VertexNode vexlist[NumVertices];int n, e;
}AdjGraph;
//建立邻接链表
void CreateGraph(AdjGraph* G)
{int i, head,tail,weight;cin >> G->n >> G->e;for (i = 0; i < G->n; i++){cin >> G->vexlist[i].vertex;//输入顶点信息G->vexlist[i].firstedge = NULL;}for (i = 0; i < G->e; i++){cin >> head >> tail >> weight;//输入边的信息EdgeNode* p = new EdgeNode;//建立边结点p->adjvex = head;p->cost = weight;p->next = G->vexlist[tail].firstedge;//链入第head号的链表前段,头插法插入边G->vexlist[tail].firstedge = p;}
}
bool visited[NumVertices];//是否访问过
int dfn[NumVertices];//顶点的先深编号
int Count ;
void DFSX(AdjGraph* G, int i)
{EdgeNode* p;cout << G->vexlist[i].vertex;visited[i] = true;//已经被访问过了，不可再被访问dfn[i] = Count++;//编号p = G->vexlist[i].firstedge;//取边表头指针while (p){if (!visited[p->adjvex])//依次搜索邻接结点，如果尚未访问，则遍历深搜DFSX(G, p->adjvex);p = p->next;}}
void DFSY(MTGraph* G, int i)
{//邻接矩阵实现深度优先搜索int j;EdgeNode* p;cout << G->verlist[i];visited[i] = true;//已经被访问过了，不可再被访问dfn[i] = Count++;//编号for (j = 0; j < G->n; j++)if ((G->edge[i][j] == 1) && !visited[i])DFSY(G, i);
}
void DFSTraverse(AdjGraph G)
{int i, Count = 1;for (i = 0; i < G.n; i++)visited[i] = false;//初始化for (i = 0; i < G.n; i++){if (!visited[i])DFSX(&G, i);}
}

广度优先算法

#include <iostream>
#include<stdlib.h>
#define NumVertices 100
using namespace std;typedef char VertexData;
typedef int EdgeData;
//线性表
typedef struct
{VertexData verlist[NumVertices];//顶点表EdgeData edge[NumVertices][NumVertices];//邻接矩阵int n, e;
}MTGraph;typedef struct node//边表结点
{int adjvex;//邻接点域EdgeData cost;//边上权值node* next;
}EdgeNode;
typedef struct//顶点表结点
{VertexData vertex;//顶点数据域node* firstedge;//边表头指针;}VertexNode;
typedef struct//图的邻接表
{VertexNode vexlist[NumVertices];int n, e;
}AdjGraph;
//建立邻接链表
void CreateGraph(AdjGraph* G)
{int i, head,tail,weight;cin >> G->n >> G->e;for (i = 0; i < G->n; i++){cin >> G->vexlist[i].vertex;//输入顶点信息G->vexlist[i].firstedge = NULL;}for (i = 0; i < G->e; i++){cin >> head >> tail >> weight;//输入边的信息EdgeNode* p = new EdgeNode;//建立边结点p->adjvex = head;p->cost = weight;p->next = G->vexlist[tail].firstedge;//链入第head号的链表前段,头插法插入边G->vexlist[tail].firstedge = p;}
}
bool visited[NumVertices];//是否访问过
int dfn[NumVertices];//顶点的先深编号
int Count ;
typedef int ElemType;
struct celltype
{ElemType data;celltype* next;
};//结点型
struct QUEUE
{celltype* front;celltype* rear;
};
void MakeNull(QUEUE& Q)
{Q.front = new celltype;Q.front->next = NULL;Q.rear = Q.front;
}
bool Empty(QUEUE& Q)
{if (Q.rear == Q.front)return true;elsereturn false;
}
void EnQueue(ElemType x, QUEUE Q)
{celltype* q;q = new celltype;q->data = x;q->next = NULL;Q.rear->next = q;Q.rear = q;
}
void DeQueue(QUEUE& Q)
{celltype* q;if (Empty(Q))cout << "empty";q = Q.front->next;Q.front->next = q->next;if (q->next == NULL)Q.rear = Q.front;delete q;
}
ElemType Front(QUEUE& Q)
{if (Empty(Q))cout << "empty";elsereturn Q.front->next->data;
}
//广度优先算法
void BFS1(AdjGraph* G, int k)
{int i; EdgeNode* p;QUEUE Q;MakeNull(Q);cout << G->vexlist[k].vertex;visited[k] = true;EnQueue(k, Q); //进队列while (!Empty(Q))//队空则结束{i = Front(Q);DeQueue(Q); //vi出队p = G->vexlist[i].firstedge;//取出vi的边表头指针while (p)//遍历vi邻接点{if (!visited[p->adjvex])//如果邻接点vj没有被访问国{cout << G->vexlist[p->adjvex].vertex;visited[p->adjvex] = true;//访问结束EnQueue(p->adjvex, Q);//访问过的vj入队列}p = p->next;//vi的下一个邻接点}}}
void BFS2(MTGraph* G, int k)
{int i,j;QUEUE Q; MakeNull(Q);cout << G->verlist[k];visited[k] = true;EnQueue(k, Q);while (!Empty(Q)){i = Front(Q);for (j = 0; j < G->n; j++){if (G->edge[i][j] == 1 && !visited[j]){cout << G->verlist[j];visited[i] = true;EnQueue(j, Q);}}}
}
void BFSTraverse(AdjGraph G)
{int i,Count=1;for (i = 0; i < G.n;i++)visited[i] = false;for (i = 0; i < G.n; i++)if (!visited[i])BFS1(&G, i);
}

最小生成树prim算法

#include <iostream>
#include<stdlib.h>
#define NumVertices 100
using namespace std;
typedef int Costtype;
int infinity = 10000000;
void Prim(Costtype C[NumVertices + 1][NumVertices + 1])
{Costtype LOWCOST[NumVertices + 1];int CLOSEST[NumVertices + 1];int i, j, k;Costtype min;for (i = 2; i <= NumVertices; i++){LOWCOST[i] = C[1][i];CLOSEST[i] = 1;}for (i = 2; i <= NumVertices; i++){min = LOWCOST[i];k = i;for(j=2;j<=NumVertices;j++)if (LOWCOST[j] < min){min = LOWCOST[j];k = j;}cout << "(" << k << "," << CLOSEST[k] << ")" << endl;LOWCOST[k] = infinity;for (j = 2; j <= NumVertices; j++)if (C[k][j] < LOWCOST[j] && LOWCOST[j] < infinity){LOWCOST[j] = C[k][j];CLOSEST[j] = k;}}
}

kraskal算法

#include <iostream>
#include<stdlib.h>
#define NumVertices 100
using namespace std;typedef struct edge
{int wgn, end, wet;}Edge;
int Find(int father[],int v )
{int f = v;while (father[f]>0){f = father[f];return f;}
}
void Kraskal(Edge edges[], int e)
{int father[NumVertices];int bnf, edf, i;for (i = 1; i <= e; i++)father[i] = 0;for (i = 1; i <= e; i++){bnf = Find(father, edges[i].wgn);edf = Find(father, edges[i].end);if (bnf != edf)father[bnf] = edf;}
}
void main()
{int n;Edge edges[NumVertices];cin >> n;Sort(edges, n);Kraskal(edges, n);
}

Dijkstra

#include <iostream>
#include<stdlib.h>
#define NumVertices 100
using namespace std;
typedef int Costtype;
int infinity = 10000000;Costtype Mincost(Costtype D[NumVertices + 1], bool S[NumVertices + 1])
{int temp = infinity;int w = 2;for(int i=2;i<=NumVertices;i++)if (!S[i] && D[i] < temp){temp = D[i];w = i;}return w;
}
void Dijkstra(int C[NumVertices][NumVertices], Costtype D[NumVertices + 1], int P[NumVertices], bool S[NumVertices + 1])
{int w; int sum;for (int i = 2; i <= NumVertices; i++){D[i] = C[1][i];S[i] = false;P[i] = 1; }S[1] = true;for (int i = 1; i <= NumVertices-1; i++){w = Mincost(D, S);for(int v=0;v<=NumVertices;v++)if (S[v] != true){sum = D[w] + C[w][v];if (sum < D[v]){D[v] = sum;P[v] = w;}}}
}

floyd

#include <iostream>
#include<stdlib.h>
#define NumVertices 100
using namespace std;
typedef int costtype;
int infinity = 10000000;void Floyd(costtype D[NumVertices][NumVertices], costtype C[NumVertices][NumVertices], int P[NumVertices][NumVertices], int n)
{int i, j, k;for (i = 0; i < n; i++)for (j = 0; j < n; i++){D[i][j] = C[i][j];P[i][j] = -1;}for (k = 0; k < n; k++)for (i = 0; i < n; i++)for (j = 0; j < n; j++)if (D[i][k] + D[k][i] < D[i][j]){D[i][j] = D[i][k] + D[k][i];P[i][j] = k;}}

拓扑排序

typedef struct NODE //每个链表类型
{int adjvex;  //根据邻接表很容易找到指向的顶点struct NODE* next;
}*Node;
typedef struct 
{Elevement data;int count;Node firstadj;
}VNode;  //邻接表存储
void topsort(VNode adj[],int n)
{int i,j，m=0;int St[maxv],top=-1;Node p;for(i=0;i<n;i++) //先把入度为0的元素进栈{if(adj[i].degree==0){top++;St[top]=i}  }while(top>-1){i=St[top--];printf("%d",i);p=adj[i].firstadj;  //p指向 i 的第一个节点m++;  //m用于计算出栈的元素个数while(p!=NULL){j=p->adjvex;  // j 为 p 指向的节点再adj[]里面的下标adj[j].degree--;if(adj[j].degree==0) //如果入度为0则进栈，否则p向后移动，指向下一个与i 连接的顶点信息；{top++; St[top]=j; //栈内存储的只是一个下标}p=p->next;}}if(m<n){printf("有环");}}

查找

#include <iostream>
#include<stdlib.h>
#define maxsize 100
using namespace std;
typedef int keytype;
typedef int fields;struct records
{keytype key;fields other;
};
typedef records List[maxsize];
List F;int SEARCH(List F, keytype k, int last)
{int i;F[0].key = k;i = last;while (F[i].key!=k)i = i - 1;return i;
}struct celltype
{records data;celltype* next;
};
typedef celltype* list;list search(keytype k, list F)
{list p = F;while (p!=NULL){if (p->data.key == k)return p;elsep = p->next;}return p;
}
//折半查找
int BinSearch1(keytype k, List F,int last)
{int low, up,mid;low = 1; up = last;while (low<up){mid = (low + up) / 2;if (F[mid].key == k)return mid;else if (F[mid].key > k)up = mid - 1;elselow = mid + 1;}return 0;
}
//递归折半
int BinSearch2(keytype k, List F, int low,int up)
{int mid;if (low > up)return 0;else{mid = (low + up) / 2;if (k < F[mid].key)return BinSearch2(k, F, low, mid - 1);else if (k > F[mid].key)return BinSearch2(k, F, mid + 1, up);elsereturn mid;}
}

二叉查找树

#include <iostream>
#include<stdlib.h>
#define maxsize 100
using namespace std;
typedef int keytype;
typedef int fields;struct records
{keytype key;fields other;
};
struct celltype
{records data;celltype* rchild,*lchild;
}BSTNode;
typedef celltype* BST;
BST SearchBST(keytype k, BST F)
{BST p = F;if (p == NULL || k == p->data.key)return p;if (k < p->data.key)return SearchBST(k, p->lchild);elsereturn SearchBST(k, p->rchild);
}
void InsertBST(records R, BST F)
{if (F == NULL){F = new celltype;F->data = R;F->lchild = NULL;F->rchild = NULL;}else if (R.key < F->data.key)InsertBST(R, F->lchild);else if (R.key > F->data.key)InsertBST(R, F->rchild);
}
BST CreatBST()
{	BST F=NULL;keytype k;cin >> k;while (k){InsertBST(R, F);cin >> k;}return F;
}
records deletemin(BST& F)
{records tmp; BST P;if (F->lchild == NULL){P = F;tmp = P->data;F = F->rchild;delete P;return tmp;}elsereturn deletemin(F->lchild);
}
void DeleteB(keytype k, BST& F)
{if (F != NULL)if (k < F->data.key)DeleteB(k, F->lchild);else if (k > F->data.key)DeleteB(k, F->rchild);elseif (F->lchild == NULL)F = F->rchild;else if (F->rchild == NULL)F = F->lchild;elseF->data = deletemin(F->rchild);
}