期末了，赶紧复习一波，手打一份书上的代码以便随时查阅

---

//顺序表存储结构
#define MAXSIZE 100
typedef struct
{
Elemtype *elemt;
int length;
}Sqlist;
Status InitList(Sqlist &L)
{
L.elemt=new Elemtype[MAXSIZE];
if(!L.elemt) exit(OVERFLOW);
// L.length=MAXQSIZE;
L.length=0;
return OK;
}
Status GetElemt(Sqlist &L,int i,Elemtype &e)
{
if(i<1||i>L.length) return ERROR;
// [错了]e=L->elemt[i];
e=L->elemt[i-1];
return OK;
}
Status LocateElem(Sqlist &L,Elemtype e)
{
for(i=0;i<L.length;++i)
{
if(L.elemt[i]==e) return i+1;
}
return 0;

}
//Status SearchElemt(Sqlist &L,int &j,Elemtype e)
//{
// if(j<1||j>L.length) return ERROR;
// for(int i=0;iL.length) return ERROR;//忘记了
if(L.length==MAXSIZE)return ERROR;//又忘记了
for(j=L.length-1;j>=i-1;--j)
{
L.elemt[j+1]=L.elemt[j];
}
L.elemt[i-1]=e;
L.length++;
return OK;
}

Status ListDelete(Sqlist &L,int i)
{
if(i<1||i>L.length) return ERROR;//忘了
// for(j=i-1;j<L.length-1;++j)
// {
// L.elemt[j]=L.elemt[j+1];
// }
for(j=i;j<=L.length-1;++j)
L.elemt[j-1]=L.elemt[j];
L.length--;
return OK;
}
//单链表的存储
typedef struct LNode
{
ElemType data;
struct LNode * next;
}LNode,*Linklist;

Status InitLink(Linklist &L)
{
L=new LNode;
// if(!L) exit(OVERFLOW);
L->next=NULL;
return OK;
}
//单链表的取值
Status GetElemt(Linklist &L,int i,Elemtype &e)
{
p=L->next;
j=1;
while(p&&jnext;++j;
}
if(!p||j>i) return ERROR;
e=p->data;
return OK;
}
//单链表的按值查找
LNode LocateElem(Linklist &L,Elemtype e)
{
p=L->next;j=1;
// while(p->data!=e)
// {
// p=p->next;
// }
// return p;
while(p&&p->data!=e)
p=p->next;
return p;
}
//单链表的插入
Status ListInsert(Linklist &L,int i,Elemtype e)
{
// p=L->next;j=1;
p=L;j=0;
while(p&&jnext;++j;
}
if(!p||j>i-1) return ERROR;
s=new LNode;
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
//删除
Status DeleteElemt(Linklist &L,int i)
{
p=L;j=0;
while(p->next&&jnext;++j;
}
if(!p->next||j>i-1) return ERROR;
s=p->next;
p->next=s->next;
delete s;
return OK;
}
//单链表的创建--前插
void CreateList_H(Linklist &L,int n)
{
L=new LNode;
L->next=NULL;
for(i=-0;i>p->data;
p->next=L->next;
L->next=p;
}
}
//单链表的创建——尾插
void CreateList_T(Linklist &L,int n)
{
L=new LNode;
L->next=NULL;
r=L;
for(i=0;i>p->data;
p->next=NULL;
r->next=p;
r=p;
}
}
//双向链表
typedef struct DuLNode
{
Elemtype data;
struct DuLNode *ptr;
struct DuLNode *next;
}DulNode,*DuLinkList;
//双向链表的插入
Status ListInsert_Dul(DuLinkList &L，int i,Elemtype e)
{

// p=L;j=1;
// while(p&&jnext;++j;
// }
// if(!p||j>i-1) return ERROR;
//
// s=new DulNode;
// s->data=e;
// s->next=p->next;
// s->ptr=p->ptr;
// p->next->ptr=s;
// p->next=s;
if(!(p=GetElem_Dul(L,i)))
return ERROR;
s=new LNode;
s->data=e;
s->ptr=p->ptr;
s->next=p;
p->ptr->next=s;
p->ptr=s;
return OK;
}
//双向链表的删除
Status ListDelete_Dul(Linklist &L,int i)
{
if(!(p=GetElemt_Dul(L,i)))
return ERROR;
p->next->ptr=p->ptr;
p->ptr->next=p->next;
delete p;
return OK;
}

#define MAXSIZE
typedef struct
{
SElemtTpye *base;
SElemtTpye *top;
int stacksize;
}SqStack ;

Status InitStack(SqStack &S)
{
S.base=new SElemtTpye[MAXSIZE];
// [危阻]if(!S.basa)return ERROR;
if(!S.base) exit(OVERFLOW);
S.top=S.base;
S.stacksize=MAXSIZE;
return OK;
}

Status Push(SqStack &S,SElemtTpye e)
{
if(S.top-S.base==S.stacksize) return ERROR;
*S.top=e;
S.top++;
// S.stacksize++;
return OK;
}

Status Pop(SqStack &S,SElemtTpye &e)
{
if(S.top==S.base) return ERROR;
S.top--;
e=*S.top;
// S.stacksize--;
return Ok;
}

SElemtTpye GetTop(SqStack &S)
{
if(S.top==S.base) return ERROR;
// S.top--;
// return *S.top;
return *(S.top-1);
}
//全媚

typedef struct StackNode
{
struct StackNode *next;
ElemtTpye data;
}StackNode,*LinkStack;

Status InitStack(LinkStack &S)
{
S=NULL;
return OK;
// S=new StackNode;
// if(!S) return ERROR;
// S.next=NULL;
// return OK;
}
Status Push(LinkStack &S,ElemtTpye e)
{
p=new StackNode;
if(!p) return ERROR;
p->data=e;
p->next=S;
S=p;
return OK;
}

Status Pop(LinkStack &S,ElemtTpye &e)
{
if(!S)return ERROR;
e=S.data;
p=S;
S=S->next;
delete p;//梨芝瞥慧阻
return OK;
}

ElemtTpye GetTop(LinkStack &S)
{
if(!S) return ERROR;
return S->data;
}

#define MAXQSIZE 100
typedef struct
{
QElemtype *base;
int front;
int rear;
}SqQueue;

Status InitQueue(SqQueue &Q)
{
Q.base=new QElemtype[MAXQSIZE];
if(!Q.base) exit(OVERFLOW);
Q.front=Q.rear=0;
return OK;
}
Status EnQueue(SqQueue &Q,Elemtype e)
{
if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXQSIZE;
return OK;
}

Status DeQueue(SqQueue &Q,Elemtype &e)
{
if(Q.rear==Q.front) return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return OK;
}

Elemtype GetTop(SqQueue &Q)
{
if(Q.front==Q.base) return ERROR;
return Q.base[Q.front];
}
//全錦
typedef struct QNode
{
Elemtype data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuPtr front;
QueuePtr rear;
}*LinkQueue;

Status InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=new QNode;
Q.front->next=NULL;
return OK;
}

Status EnQueue(LinkQueue &Q,Elemtype e)
{
p=new QNode;
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
Status DeQueue(LinkQueue &Q,Elemtype &e)
{
if(Q.front==Q.rear)return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(p==Q.rear) Q.rear=Q.front;
delete p;
return OK;
}

//串的顺序定义
#define MAXSIZE 100
typedef struct
{
char ch[MAXSIZE];
int length;
}SString;
//串的链式定义--完全没记住Orz
//typedef struct a
//{
// char ch[MAXQSIZE];
// int length;
// struct a * next;
//}*c;
//typedef struct
//{
// c
//}LString;
#define CHUNKSIZE 100
typedef struct Chunk
{
char ch[CHUNKSIZE];
struct Chunk * next;
}Chunk;
typedef struct
{
Chunk *head,*tail;
int length;

}LString;

//二叉树的顺序存储结构
#define MAXTSIZE 100
typedef TElemtype SqBiTree[MAXSIZE];
SqBiTree Bt;
//二叉树的链式存储表示
typedef struct BiTNode
{
Elemtype data;
struct BiTNode * rchild,*lchrild;
}BiTNode,*BiTree;
//中序遍历的递归算法
void InOrderTraverse(BiTree &T)
{
if(T)
{
InOrderTraverse(T->lchild);
cout<data;
InOrderTraverse(T->rchild);
}
}
//先序遍历的顺序建立二叉链表
void CreateBiTree(BiTree &T)
{
cin>>ch;
if(ch=='#')
{
T=NULL;
}
else
{
T=new BiNode;
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
//复制二叉树
void Copy(BiTree &T,Bi &NewT)
{
if(!T)
{
NewT=NULL;
return;
}
else
{
NewT=new BiNode;
NewT->data=T->data;
Copy(T->lchild,NewT->lchild);
Copy(T->rchild,NewT->rchild);
}
}
//计算二叉树深度
void Depth(BiTree &T)
{
if(!T) return 0;
else
{
m=Depth(T->lchild);
n=Depth(T->rchild);
if(m>n)
{
return m+1;
}
else
{
return n+1;
}
}
}
//统计二叉树结点个数
int NodeCount(BiTree &T)
{
if(!T) return 0;
else
{
return NodeCount(T->rchild)+NodeCount(T->lchild)+1;
}
}
//二叉树的二叉线索存储表示
typedef struct BiThrNode
{
Elemtype data;
struct BiThrNode *lchild,*rchild;
int ltag,rtag;
}BiThrNode,*BiThrTree;
//以节点p为根的子树中序线索化
//1代表是线索，0代表是子树
void InThreading(BiThrTree p)
{
if(p)
{
InThreading(p->lchild);
if(!p->lchild)
{
p->ltag=1;
p->lchild=pre;
}
else
{
p->ltag=0;
}
if(!pre->rchild)
{
p->rtag=1;
pre->rchild=p;
}
else
{
pre->rtag=0;
}
InThreading(p->rchild);
}
}
//带头节点的二叉树中序线索化
void InOrderThread(BiThrTree &Thrt,BiTree T)
{
Thrt=new BiThrNode;
Thrt->ltag=0;
// Thrt->lchild=T;
Thrt->rtag=1;
Thrt->rchild=Thrt;
if(!T)
{
Thrt->lchild=Thrt;
}
else
{
Thrt->lchild=T;pre=Thr;
InThreading(T);
pre->rchild=Thrt;
pre->rtag=1;
Thrt->rchild=pre;//忘了
}
}
//遍历中序线索二叉树
//输出左边->输出自己->输出右边
void InOrderTravese_Thr(BiThrTree &T)
{
p=T->lchild;
while(p!=T)
{
while(!p->ltag) p=p->lchild;
cout<data;//输出左边
while(p->rchild&&p->rchild!=T)
{
p=p->rchild;
cout<data;//输出自己
}
p=p->rchild;//往右边走
}
}
//————————哈夫曼树的存储结构
typedef struct
{
int weight;
int parent,lchild,rchild;
}HNode,*HuffmanTree;

//构造哈夫曼树
void CreateHuffmanTree(HuffmanTree &HT,int n)
{
if(n<=1)return; m=2*n-1; HT=new HTNode[m+1]; for(i=1;i<=m;++i) { HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0; } for(int i=1;i<=n;++i) { cin>>HT[i].weight;
}
for(i=n+1;i<=m;++i)
{
Select(HT,i-1,s1,s2);
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[s1].parent=i;
HT[s2].p79d7;iiarent=i;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
}
//------------------哈夫曼编码表的存储表示
typedef char **HuffmanCode;
//根据哈夫曼树求哈夫曼编码
void CreateHuffmanNode(HuffmanTree HT,HuffmanCode &HC,int n)
{
HC=new char*[n+1];
cd =new char[n];
cd[n-1]='\0';
for(i=1;i<=n;++i)
{
start=n-1;
c=i;f=HT[i].parent;
while(!f)
{
start--;
if(HT[f].lchild==c)cd[start]='0';
else cd[start]='1';
c=f;
f=HT[f].parent;
}
HC[i]=new char[n-start];
strcpy(H[i],&cd[start]);
}
delete cd;

}

//#define MAXINT
//typedef struct
//{
// ELemtype vertice[MAXQSIZE];
// int arc[MAXSIZE][MAXSIZE];
// int vernum,arcnum;
//}AMGraph;

#define MaxInt 32767 //表示极大值，即∞
#define MVNum 100 //最大顶点数
typedef char VerTexType; //假设顶点的数据类型为字符型
typedef int ArcType; //假设边的权值类型为整型
typedef struct
{
VerTexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum]; //邻接矩阵
int vexnum,arcnum; //图的当前点数和边数
}AMGraph;

//采用邻接矩阵表示法，创建无向网G
Status CreateUDN(AMGraph &G)
{
cin>>G.vexnum>>G.arcnum; //输入总顶点数，总边数
for(i = 0; i>G.vexs[i]; //依次输入点的信息
for(i = 0; i>v1>>v2>>w; //输入一条边依附的顶点及权值
i = LocateVex(G, v1);
j = LocateVex(G, v2); //确定v1和v2在G中的位置
G.arcs[i][j] = w; //边的权值置为w
G.arcs[j][i] = G.arcs[i][j]; //置的对称边的权值为w
}
return OK;
}
int LocateVex(MGraph G,VertexType u)
{ /* 初始条件:图G存在,u和G中顶点有相同特征 */
/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(u==G.vexs[i])
return i;
return -1;
}
///邻接表的存储表示
#define MVNum 100 //最大顶点数
typedef struct ArcNode{//边结点
int adjvex; //该边所指向的顶点的位置
struct ArcNode * nextarc; //指向下一条边的指针
OtherInfo info; //和边相关的信息
}ArcNode;

typedef struct VNode{
VerTexType data; //顶点信息
ArcNode * firstarc; //指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum]; //AdjList表示邻接表类型

typedef struct{
AdjList vertices; //邻接表
int vexnum, arcnum; //图的当前顶点数和边数
}ALGraph;
　
///采用邻接表表示法，创建无向图G
Status CreateUDG(ALGraph &G){
　
　 cin>>G.vexnum>>G.arcnum; //输入总顶点数，总边数
for(i = 0; i> G.vertices[i].data; //输入顶点值
G.vertices[i].firstarc=NULL; //初始化表头结点的指针域为NULL
}//for
for(k = 0; k>v1>>v2; //输入一条边依附的两个顶点
i = LocateVex(G, v1);
j = LocateVex(G, v2);
p1=new ArcNode; //生成一个新的边结点*p1
　　 p1->adjvex=j; //邻接点序号为j
　 　 p1->nextarc= G.vertices[i].firstarc; G.vertices[i].firstarc=p1;
//将新结点*p1插入顶点vi的边表头部
p2=new ArcNode; //生成另一个对称的新的边结点*p2
　　 p2->adjvex=i; //邻接点序号为i
　 　 p2->nextarc= G.vertices[j].firstarc; G.vertices[j].firstarc=p2;
//将新结点*p2插入顶点vj的边表头部
}
return OK;
}//CreateUDG

void DFS(Graph G, int v)
{
cout<0; w=NextAdjVex(G,v,w))
if(!visited[w])
DFS(G, w);
//w是v的邻接点，如果w未访问，则递归调用DFS
}
void DFS(AMGraph G, int v)
{
cout<adjvex; //表示w是v的邻接点
if(!visited[w])
DFS(G, w); //如果w未访问，则递归调用DFS
p=p->nextarc; //p指向下一个边结点
}
}
void BFS (Graph G, int v)
{
//按广度优先非递归遍历连通图G
cout<=0; w = NextAdjVex(G, u, w))
if(!visited[w])
{ //w为u的尚未访问的邻接顶点
cout<<w;
visited[w] = true;
EnQueue(Q, w); //w进队
}//if
}//while
}//BFS

void DFSTraverse(Graph G)
{
// 对图 G 作深度优先遍历。
for (v=0; v<G.vexnum; ++v)
visited[v] = FALSE; // 访问标志数组初始化
for (v=0; v<G.vexnum; ++v)
if(!visited[v])
DFS(G, v);
// 对尚未访问的顶点调用DFS
}

///无向网G用邻接矩阵存储
///普里姆算法从顶点u出发构造的最小生成树
void MiniSpanTree_Prim(AMGraph G, VertexType u)
{
k = LocateVex ( G, u ); //U的下标k
for( j=0; j<G.vexnum; ++j ) // 辅助数组初始化
if (j!=k) closedge[j] = { u, G.arcs[k][j] };
closedge[k].lowcost = 0; // 初始，U＝{u}

for (i=1; i<G.vexnum; ++i)
{
k = Min(closedge);
// 求出加入生成树的下一个顶点(k)
printf(closedge[k].adjvex, G.vexs[k]);
// 输出生成树上一条边
closedge[k].lowcost = 0; // 第k顶点并入U集
for (j=0; j<G.vexnum; ++j)
//修改其它顶点的最小边
if (G.arcs[k][j] < closedge[j].lowcost)
closedge[j] = { G.vexs[k], G.arcs[k][j]};
}
///克鲁斯卡尔（Kruscal）算法
struct
{
VerTexType Head; //边的始点
VerTexType Tail; // 边的终点
ArcType lowcost; // 边上的权值
}Edge[arcnum];
void MiniSpanTree_Kruskal(AMGraph G)
{
sort(Edge);
for(i=0;i<G.Vexnum;i++)
Vexset[i]=i;
for(i=1;i<G.Vexnum;i++)
{
v1=LocateVex(G,Edge[i].Head);
v2=LocateVex(G,Edge[i].Tail);
vs1=Vexset[v1];
vs2=Vexset[v2];
if(vs1!=vs2)
{
cout<<Edge[i].Head<<Edge[i].Tail;
for(i=0;i<G.Vexnum;i++)
if(Vexset[i]==vs2)
Vexset[i]=vs1;
}
}
}
///用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径
void ShortestPath_DIJ(AMGraph G, int v0)
{
n=G.vexnum; //n为G中顶点的个数
for(v = 0; v<n; ++v)
{ //n个顶点依次初始化
S[v] = false; //S初始为空集
D[v] = G.arcs[v0][v]; //将v0到各个终点的最短路径长度初始化
if(D[v]< MaxInt)
Path [v]=v0; //v0和v之间有弧，将v的前驱置为v0
else
Path [v]=-1; //如果v0和v之间无弧，则将v的前驱置为-1
}//for

S\[v0\]=true;     //将v0加入S  
D\[v0\]=0;  //源点到源点的距离为0  
/\*―  
    开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集  
―\*/  
for(i=1;i<n; ++i)  
{ //对其余n−1个顶点，依次进行计算  
    min= MaxInt;  
    for(w=0;w<n; ++w)  
        if(!S\[w\]&&D\[w\]<min)  
        {  
            v=w;  
            min=D\[w\];  
        }  
    //选择一条当前的最短路径，终点为v  
    S\[v\]=true; //将v加入S  
    //更新从v0出发到集合V−S上所有顶点的最短路径长度  
    for(w=0;w<n; ++w)  
        if(!S\[w\]&&(D\[v\]+G.arcs\[v\]\[w\]<D\[w\])  
        {  
            D\[w\]=D\[v\]+G.arcs\[v\]\[w\];//更新D\[w\]  
            Path\[w\]=v; //更改w的前驱为v  
        }//if  
}//for  

}//ShortestPath_DIJ
///用Floyd算法求有向网G中各对顶点v和w之
///间的最短路径
Void ShortestPath_Floyed(AMGraph G)
{
for(i=0;i<G.vexnum;++i)//各对结点之间初始已知路径及距离
for(j=0;j<G.vexnum;++j)
{
D[i][j]=G.arcs[i][j];
if(D[i][j]<MaxInt) path[i][j]=i; //从v到w有直接路径
else path[i][j]=-1;
}//for

for(k=0;k<G.vexnum;++k)  
    for(i=0;i<G.vexnum;++i)  
        for(j=0;j<G.vexnum;++j)  
            if(D\[i\]\[k\]+D\[k\]\[j\]<D\[i\]\[j\])  
            {  
                //从v经u到w的一条路径更短  
                D\[i\]\[j\]=D\[i\]\[k\]+D\[k\]\[j\];  
                path\[i\]\[j\]=path\[k\]\[j\];  
            }//if  

}//ShortestPath_FLOYD
///拓扑排序AOV-网
//有向图G采用邻接表存储结构
//若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则ERROR。
Status TopologicalSort( ALGraph G , int top[])
{
FindInDegree(G,indegree);//对各顶点求入度indegree[0..vernum-1]
InitStack(S);
for( i=0; inextarc)
{
k=p->adjvex; // 对i号顶点的每个邻接点的入度减一
--indegree[k];
if(!indegree[k]) Push(S,k); //若入度为零，则入栈
}//for
}//while
if(count<G.vexnum )
return ERROR;//该有向图有回路
else
return OK;
}//TopologicalSort

///拓扑排序
Status TopologicalOrder(ALGraph G,int topo[])
{
FindInDegree(G,indegree);//对各顶点求入度indegree[0..vernum-1]，建零入度顶点栈S;
InitStack(S);
for(i=0;iadjvex; // 对j号顶点的每个邻接点的入度减1
--indegree[k];
if(indegree[k]==0)
Push(S,k); //若入度减为零则入栈
p=p->nextarc;
}//for

}//while  
if (m<G.vexnum )  
    return ERROR;//该有向网有回路  
else  
    return OK;  

}//TopologicalOrder
///关键路径算法
Status CriticalPath(ALGraph G)
{
if(!TopologicalOrder(G,topo)) return ERROR;//有回路
n=G.vexnum;
for(i =0 ;iadjvex;
if(ve[j]weight)
ve[j]=ve[k]+p->weight;
p=p->nextarc;
}
}
for(i=0;o=0;--i)
{
k=topo[i];
p=G.vertices[k].firstarc;
while(!p)
{
j=p->adjvex;
if(vl[k]>vl[j]-p->weight)
vl[k]=vl[j]-p->weight;
p=p->nextarc;
}
}
// /*判断每一活动是否为关键活动*/
for(i=0;iadjvex;
e=ve[i];
l=vl[j]-p->weight;
if(e==l)
cout<nextarc;
}
}
}//CriticalPath