// 1_4.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdlib.h>
//struct node
//{
// int data;
// node* next;
//};
struct linklist
{
node* head; //表头指针
int n; //线性表的长度
};
int main(int argc, char* argv[])
{
printf("Hello World!/n");
return 0;
}
//定位
node* loc(linklist L,int i)
{
if(i<0 || i>L.n)
{
return NULL;
}
else
{
int j=0;
node* temp = L.head; //指向第一个元素
while(j<i)
{
temp = temp->next;
j++;
}
return temp;
}
}
//往第i个节点的后面，插入值为x的接点
void ins(linklist &L,int i,int x)
{
//如果i的范围<0 或 >L.n
if(i<0 || i>L.n)
{
return; //出错，不进行插入
}
node* prevNode = loc(L,i); //找到第i个节点
node q = new node();
q.data = x;
q.next = prevNode->next;
prevNode->next = q;
L.n++;
}
//删除第i个元素
void del(linklist& L,int i)
{
if(i<1 || i>L.n)
{
return;
}
node* prevNode = loc(L,i-1);
node* q = prevNode->next;
prevNode->next = q->next;
L.n--;
delete q;
}
//静态数组
struct element
{
int data; //数值字段
int next; //指针字段
};
struct element S[101]; //
int head; //静态链表的数据链表表头的位置
int avail; //静态链表的备用链表的表头
//打印静态链表
void Print(struct element[] S)
{
int temp = head; //头指针
while(temp)
{//如果当前元素不为空
cout(S[temp].data);
temp = S[temp].next;
}
}
//p : 在数据链表中地址为p的节点，后面插入一个值为x的新节点
void insert(int p,int x)
{
if(p的位置不对)
{
cout<<"x的插入位置不对"<<endl;
}
if(avail == 0)
{
cout<<"内存没了"<<endl;
return;
}
int q = avail;
avail = S[avail].next; //avail为新的备用链的头
S[q].data = x;
if(p == head)
{//如果要在第一个位置上插入
S[q].next = head;
head = q;
}
else
{//如果不是要插到第一个位置
S[q].next = S[p].next;
S[p].next = q;
}
}
//多项式加法
//struct node
//{
// int coef; //系数
// int expn; //指数
// node* next; //
//};
void attach(int c,int e,node* &p)
{//在p接点的后面增加一个新节点，令p指向新节点
//在新节点的系数字段c，指数字段为e
node temp = new node();
temp.coef = c;
temp.expn = e;
p->next = temp;
p = temp;
}
//两个多项式相加
//ha，hb ： 第1，2个多项式
//hc相加后的多项式
void addpolyn(node* ha,node* hb,node* &hc)
{
node* pa,pb,pc;
hc = new node();
pa = ha->next;
pb = hb->next;
pc = hc;
while((pa != NULL) && (pb != NULL))
{//当两个多项式都不为空时候
if(pa->expn == pb->expn)
{//如果两者的指数相同
int temp = pa->coef + pb->coef;
if(temp != 0)
{//如果相加不为0,新建一个node节点
attach(temp,pa->expn,pc);
}
else
{//如果为0就什么都不做
}
pa = pa->next;
pb = pb->next;
}
else if(pa->expn < pb->expn)
{//如果pa的指数比较小，把pc后面加上pa的内容
attach(pa->coef,pa->expn,pc);
pa++
}
else
{//如果pb的指数比较小
attach(pb->coef,pb->expn,pc);
pb++
}
}
//如果pa，pb至少有一个为空
if(pa != NULL)
{
pc.next = pa;
}
if(pb != NULL)
{
pc.next = pb;
}
}
//顺序栈，使用数组为存储介质
struct stack
{
int s[101]; //存储数据的介质
int t; //t当前的栈顶位置
};
//顺序栈入栈
void push(stack& st,int x)
{
if(st.t == 101)
{//101表示最大的栈的容量
return;
}
t++ ; //t向下移动
st.s[t] = x;
}
//顺序栈出栈
//返回值为出栈的元素的值
int pop(stack &st)
{
if(st.t == 0)
{//如果没有元素
return -1;
}
else
{
return st.s[--st.t];
}
}
//链接栈
struct node
{
int data;
node* next;
};
//向t指向的链接栈，入栈x
void push(node* &t,int x)
{
node temp = new node();
temp.data = x;
temp.next = t;
t = &temp;
}
//返回值为出栈的元素的值
int pop(node* &t)
{
if(t == NULL)
{
return -1;
}
else
{
node* p = t;
t = t->next;
int iReturn = p->data;
delete p;
return iReturn;
}
}
#define n0 30
int s1[n0]; //运算数栈
char s2[n0]; //运算符号栈
int t1,t2; //t1 : 指向运算数栈s1栈顶，t2：指向运算符栈s2栈顶
//一次运算操作
void calcu()
{
char p; //运算符
int x1,x2,x;//运算数
p = s2[t2--]; //运算符出栈
x2 = s1[t1--];
x1 = s1[t1--];
switch (p)
{
case '+':
x = x1 + x2;
break;
case '-':
x = x1 - x2;
break;
case '*':
x = x1 * x2;
break;
case '/':
x = x1 / x2;
break;
}
//运算结果入栈
s1[++t1] = x;
}
//表达式求值
void calculator()
{
char c; //操作符号
int v; //操作数
t1 = t2 = 0; //栈清空
cin>>c
while(c != ';')
{
switch(c)
{
case '(':
// ( 入栈
s2[t2++] = c;
cin>>c;
break;
case '+':case '-':
//如果栈顶不是（，计算
while(t2 && s2[t2] != '(')
{//当t2不为0，并且...
calcu();
}
else
{
}
s2[t2++] = c; //当前的运算符进栈
cin>>c;
break;
case '*':case '/':
//如果栈顶为*//,计算
if(t2 && s2[t2] == '/' || s2[t2] == '*')
{
calcu();
}
else
{//如果栈顶为空或者不是*//,入栈
}
s2[t2++] = c;
cin>>c;
break;
case ')':
//if栈顶是（，弹出
while(s2[t2] != '(')
{
calcu();
}
t2--;
cin>>c;
break;
default: //所有的default都认为是数字
//注意数字也是一个一个输入进去的 1234
v = 0;
do
{
v = v*10 + c-'0';
cin>>c;
} while (c>='0'&& c<='9');
s1[t1++] = v;
break;
}
}
//遇到了;
while(t2)
{
calcu();
}
if(t2 == 0)
{//如果运算符栈里空了
return s1[t1];
}
else
{
return -1;//表示错误，很不严谨
}
}
//顺序队列
#define n0 100
struct queue
{
int q[n0+1]; //队列长度
int f; //头 front
int r; //尾 rear
};
//插入
void enq(queue& qu,int x)
{
if((qu.r + 1) % (no + 1) == qu.f)
{//队列已经满
return;
}
else
{//注意是循环队列
qu.q[qu.r] = x;
qu.r = (qu.r + 1) % (no + 1);
}
return;
}
//删除
int deq(queue &qu)
{
if(qu.r == qu.f)
{//队列为空
return -1;
}
else
{
int iReturn = qu.q[f];
qu.f = (qu.f + 1) % (no + 1);
}
return iReturn;
}
//链接队列
struct node
{
int data;
node* next;
};
void enq(node* &f,node* &r,int x)
{
node* pNewNode = new node();
pNewNode->data = x;
pNewNode->next = NULL;
if(f == NULL)
{
f = pNewNode;
}
else
{
r->next = pNewNode;
}
r = pNewNode;
}
//删除链接队列
int deq(node *&f,node *&f)
{
if(f == NULL)
{//如果链接队列为空
return -1;
}
else
{
int iReturn = f->data;
node* p = f;
f = f->next;
free(p);
return iReturn;
}
}
//报数问题
//解题思路：引入数组p[0..n],把数字保存到1..n,看成一个静态循环队列，f=1 队首，r=0 队尾
//反复执行如下的操作：
//输出队首元素，删除队首元素
//把队首元素插入到队尾，删除队首元素
#define n 20
void numberoff()
{
int f = 1; //队首
int r = 0; //队尾
//构造数组
int[] q = new int(n);
for(int i=1;i<=19)
{
q[i] = i;
}
//报数
bool bFirst = true; //判断是操作1还是操作2
while(q[f] != -1)
{//我们在删除的时候的操作是把当时的元素赋值为-1.当q[f]=-1表示头元素没有了。
if(bFirst)
{//如果是操作1 输出队首元素，删除队首元素
cout<<q[f]<<",";
q[f] = -1 ;//删除队首元素
}
else
{//如果是操作2,把队首元素插入到队尾，删除队首元素
q[r] = q[f];
q[f] = -1;
r = (r + 1) % 20 ;
}
f = (f + 1) % 20 ;
bFirst = !bFirst;
}
}
//4.4 二叉树的遍历方法
#define n0 100
struct node
{
int data;
int llink,rlink;
};
node tree[n0+1];
int root; //树的根节点位置
//递归方式实现前序，中序，后序遍历
void preorder(int p)
{
if(!p)
{//如果根节点不为空
cout<<tree[p].data;
preorder(tree[p].llink);
preorder(tree[p].rlink);
}
}
void inorder(int p)
{
if(!p)
{//如果根节点不为空
inorder(tree[p].llink);
cout<<tree[p].data;
inorder(tree[p].rlink);
}
}
void postorder(int p)
{
if(!p)
{//如果根节点不为空
postorder(tree[p].llink);
postorder(tree[p].rlink);
cout<<tree[p].data;
}
}
//非递归算法的前序，中序，后序遍历
//前序列的算法思想 ：从二叉树的根节点开始，令指针变量P指向根节点，访问当前节点p，并将p压入栈中。
//然后令p指向当前指向节点的左孩子节点。若p不为空，继续访问当前节点p，并将p压入栈中。如此反复直到p为空
//从栈中弹出栈顶元素赋给指针变量p，并令p指向它的右孩子节点，重复上述过程，当p为空，并且栈也为空时候，遍历结束。
void preorder()
{
int s[n0+1]; //栈
int t; //栈指针
int p = root;//树指针
while(p||t)
{//当p不为空或者栈不为空时
if(p)
{//当期指针不为空时候
cout<<tree[p].data; //访问当前节点
s[++t] = p; //当前地址入栈
p = tree[p].llink; //p指向p的左孩子
}
else
{//如果p指向的p的左孩子为空，就是没有左孩子
p = s[t--];//p返回到它的父亲节点
p = tree[p].rlink; //p指向它的父亲节点的右孩子
}
}
}
//中序算法：和前序算法基本上一致，但是数据访问在出栈的时候
//前序列的算法思想 ：从二叉树的根节点开始，令指针变量p指向根节点，访问当前节点p，并将p压入栈中。
//然后令p指向当前指向节点的左孩子节点。若p不为空，继续访问当前节点p，并将p压入栈中。如此反复直到p为空
//从栈中弹出栈顶元素赋给指针变量p，并令p指向它的右孩子节点，重复上述过程，当p为空，并且栈也为空时候，遍历结束。
void preorder()
{
int s[n0+1]; //栈
int t; //栈指针
int p = root;//树指针
while(p||t)
{//当p不为空或者栈不为空时
if(p)
{//当期指针不为空时候
s[++t] = p; //当前地址入栈
p = tree[p].llink; //p指向p的左孩子
}
else
{//如果p指向的p的左孩子为空，就是没有左孩子
p = s[t--];//p返回到它的父亲节点
cout<<tree[p].data; //访问当前节点
p = tree[p].rlink; //p指向它的父亲节点的右孩子
}
}
}
//后序遍历
//算法思路：当遇到非空的二叉树时候，首先将根节点地址和该节点的“右子树没有遍历”标记压入栈，然后沿
//左子数下降去遍历根节点的左子树，当遇到空二叉树时候，也就是这个节点没有左子树了，弹出栈顶元素，
//取得这个节点根节点的位置和，该根节点的右子树是否已经遍历的标记。
//1如果右子树已经遍历，就访问这个根节点。
//2如果右子树没有遍历，就把这个根节点的地址和这个根节点的“右子树已经遍历”的标记，压入栈中。然后沿
//右子树去遍历这个根节点的右子树。
//s[t] > 0 ：此节点右子树没有遍历
//s[t] < 0 : 此节点右子树已经遍历
void postorder()
{
int s[n0+1]; //栈
int t = 0; //栈指针
int p = root;//p指向当前节点
while(p||t)
{//当当前指针不为空 或者 栈不为空的时候
if(p)
{//如果当前指针不为空
s[++t] = p ;//同时p>0表示这个节点的右孩子还没有被遍历
p = tree[p].llink; //沿着左孩子向下遍历
}
else
{//如果当期指针为空了，表示栈顶节点的左孩子为空
if(s[t]<0)
{//如果这个栈顶节点的右孩子被访问过了
p = -s[t--]; //出栈，得到当前节点的父亲节点的地址
cout<<tree[p].data; //访问根节点
}
else
{//如果栈顶节点的右孩子没有被访问过
s[t] = -s[t]; //表示栈顶节点的右孩子已经被遍历过了
p = s[t]; //
p = tree[s[t]]->rlink;
}
}
}
}
//4.4.3 根据“扩展后序序列”建立二叉树的二叉链表存储结构
//算法基本思想：
//读入扩展后序序列，从左往右检测每一个符号。
//1 如果是小圆点，就把空地址压入栈.
//2 如果是字母，就首先为新节点分配存储空间，将读到的字母存入新节点的数字字段中，然后从栈顶弹出两个元素，分别作为新节点的右孩子和左孩子指针。
//最后把新节点地址入栈
void settree()
{
int s[n0+1]; //栈
int t = 0; //栈顶指针
int i = 0; //tree上面的指针
char c; // 每次读入的元素
cin>>c;
while(c != '')
{//如果录入的不为空
if(c == '.')
{//如果是.,直接把空地址入栈
s[++t] = 0;
}
else
{//如果是一个字母
i++; //为新节点分配存储
tree[i].data = c;
tree[i].rlink = s[t--]; //右孩子
tree[i].llink = s[t--]; //左孩子
s[++t] = i; //新节点地址入栈
}
cin>>c;
}
root = i;
}
//4.5.2 利用线索_中序_找前驱和后续
//找前驱节点
int prior(int p)
{
p = tree[p].llink ; //得到当前节点的左孩子 或者 前驱
if(p > 0)
{//如果是左孩子
while(tree[p].llink>0)
{
p = tree[p].llink; //如果有左孩子左孩子肯定是前驱里面的
}
//一直找到p的左孩子为0为止
return (p);
}
else
{//如果是前驱
return -p; //因为前驱为负数
}
}
//给二叉树加中序线索
//要得到中序线索二叉树，则只要对二叉树进行一次中序遍历，在遍历的过程中使用线索地带空的指针就可以
//实现思路 ：先实现中序遍历，然后再添加 添加线索的代码
void inthread()
{
int s[n0+1] ; //栈
int t;//栈指针
int p = root; //当前节点的指针，被初始化为root
int q = 0;
while(p || t)
{//当前节点不为空 或者 栈不为空
if(p)
{//如果当前节点不为空，把当前节点入栈，节点指到当前节点的左孩子
s[++t] = p;
p = tree[p].llink;
}
else
{//如果当前节点为空
p = s[t--]; //p为当前节点的父亲节点
//cout<<tree[p].data ;//如果是中序遍历，就输出了
//现在是加上线索
if(q)
{//q现在是p的前驱
if(tree[q].rlink == 0)
{//如果前驱的右节点为0，那么线索话
tree[q].rlink = -p; //后续
}
if(tree[p].llink == 0)
{//如果当前节点的左节点为0.那么线索话
tree[p].llink = -q;
}
}
q = p; //q也是当前节点的父亲节点
p = tree[p].rlink ; //p是当前节点的父亲节点的右孩子
}
}
}
//5.2.3 建立图的存储结构 ：邻接表 和 邻接矩阵
const int n0 = 100;
const int infinity = 32767;
struct arcnode
{//边节点
int vertext; //边上另外一个节点的存储位置
int weight; //边的权值
arcnode* next; //指向下一条边
};
struct node
{//存储节点的结构
int degree; //每个节点的度 或 入度
arcnode* first; //每个几点连接的第一条边
};
node adjlist[n0+1] ; //存储节点的列表
int adjmatrix[n0+1][n0+1]; //邻接矩阵
int n; //定点数
//设置连接矩阵 和 邻接链表
void setgraph()
{
int i; //开始点
int j; //终点
int k; //表示 有向/无向
int w; //权值
arcnode *p;
cout<<"1 无向图，2 有向图";
cin>>k;
cout<<"顶点数:";
cin>>n;
//邻接矩阵初始化
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
adjmatrix[i][j] = infinity; //infinity 表示不可达
}
adjmatrix[i][i] = 0; //
}//说明这个是一个带有权值的网络
//邻接表初始化
for(i=1;i<=n;i++)
{
adjlist[i].degree = 0;
adjlist[i].first = NULL;
}
cout<<"请输入边的集合";
cout<<"始点，终点，权值";
cin>>i>>j>>w; //
while((i>=1)&&(i<=n)&&(j>=1)&&(j<=n))
{//当i,j的范围都是正确的
//存入邻接矩阵
adjmatrix[i][j] = w;
if(k == 1)
{//如果是无向图
adjmatrix[j][i] = w;
}
//存入邻接表
p = adjlist[i].first ;//得到 指向 邻接表第1个边节点的指针
while((p)&&(p->vertext != j))
{//如果这条边不为空，并且这条边不是已经存储的话,继续向下寻找
p = p->next;
}
if(p == NULL)
{//如果p为空，说明这条边没有被存储过，如果p不为空，说明这条边已经被存储过
//插入一个边的节点，并且是逆向插入
p = new arcnode;
p->vertext = j;
p->weight = w;
p->next = adjlist[i]->first;
adjlist[i]->first = p;
++(adjlist[i].degree);
}
if(k == 1)
{//如果是无向图，也要把j,i,w录入到邻接表
p = adjlist[j].first ;//得到 指向 邻接表第1个边节点的指针
while((p)&&(p->vertext != i))
{//如果这条边不为空，并且这条边不是已经存储的话,继续向下寻找
p = p->next;
}
if(p == NULL)
{//如果p为空，说明这条边没有被存储过，如果p不为空，说明这条边已经被存储过
//插入一个边的节点，并且是逆向插入
p = new arcnode;
p->vertext = i;
p->weight = w;
p->next = adjlist[j]->first;
adjlist[j]->first = p;
++(adjlist[j].degree);
}
}
cin>>i>>j>>w;
}
}
//图的 深度遍历
//预先定义好的数据结构
//s : 表示顺序栈
//t : 表示栈顶指针
void dfs(int x)
{//从第x元素还是深度遍历
int mark[n0+1]; //mark[i] = 0 表示这个点还没有被访问过
int k; //用于遍历
int s[n0+1],t;
arcnode *p;
//初始化
for(k=0;k<=n;k++)
{
mark[k] = 0;
}
cout<<x<<" ";
mark[x] = 1;
//初始化栈
t=1;
s[1] = x; //
do
{
k = s[t]; //得到栈顶元素所指节点
p = adjlist[k].first; //p为与k连接的边的节点
while(p && mark[p->vertext])
{//如果p不空，而且当前p所指节点已经被访问，就继续找和k连接的节点。
p = p->next;
}
if(p == NULL)
{//如果和k邻接的节点都已经被访问过了，出栈
t--;
}
else
{//如果和k邻接的节点还有没有被访问的，就访问
x = p->vertext; //x是这个没被访问过的节点
cout<<x<<" "; //访问x
mark[x] = 1 ; //标记x也被访问过
s[++t] = x; //x被入栈
}
} while (t);
}
//图的 广度遍历
//预先定义好的数据结构
//q : 顺序队列
// f,r :队列首指针，队列尾指针
void bfs(int x)
{//从第x节点开始访问
int mark[n0+1]; //标志点是否被访问过
int k;
int q[n0+1]; //队列
int f; //队列头
int r; //队列尾
arcnode* p; //临时的边节点
//初始化mark数组
for(k=1;k<=n;k++)
{
mark[k] = 0;
}
cout<<x<<" "; //从x节点开始广度遍历
mark[x] = 1;
f = 1; //头指针，删除的位置
r = 2; //尾指针，插入的位置
q[f] = x; //插入队列
do
{
k = q[f++]; //k为当前正在访问的节点，f头指针移动到正确的位置
p = adjlist[k].first; //得到跟当前节点连接的第一条边
while(p)
{//当这条边不为空
x = p->vertext; //得到这条边上的节点
if(mark[k] == 0)
{//如果这个节点还没有被访问
cout<<x<<" "; //访问这个节点
mark[x] = 1; //设置这个节点被访问
q[r++] = x; //插入队列
}
p = p->next;
}
} while (f!=r); //当队列不为空
}
//从顶点Vx出发，开始深度遍历求连通图或有根有向图的生成树的算法
//Vx是连通图中任意一个顶点，或有根有向图中任意一个根
void dfstree(int x)
{//从x开始深度遍历
int mark[n0+1]; //标记某个节点是否被访问过了
int k;
int s[n0+1]; //栈
int t; //栈指针
arcnode* p;
//初始化访问列表
for(k=1;k<=n;k++)
{
mark[k] = 0;
}
t = 1;
s[t] = x;
do
{
k = s[t]; //k为当前访问的节点
p = adjlist[k].first; //p为与k节点邻接的第一条边
while(p && mark[p->vertext])
{//如果p存在，并且p这个节点已经被访问过
p = p->next; //继续找
}
if(p == NULL)
{//如果k所有邻接的边都访问过，就出栈
t--;
}
else
{//否则，这时候p指向没有被访问过的边
x = p->vertext;
cout<<"("<<k<<","<<x<<")"<<endl; //输出这条边
mark[k] = 1 ;//标志这个节点被访问过了
s[++t] = x; //入栈
}
} while (t); //如果栈不为空
}
//构造最小生成树的 prim 算法
//算法思想：
//1 从n个顶点中任选一个顶点Vx加入到原来为空的生成树
//2 重复做如下动作：
//从一个顶点已经进入生成树，而另一个顶点还没有进入生成树的那些边中，选取一个权值最小的边，并将这条边以及他所关联的目前还没有在生成树中的那个节点加入到生成树中。
//当生成树的顶点个数达到n时，整个构造过程结束
//使用两个辅助数组：
//1 lowcost : 记录个顶点到生成树的最近距离，若Vi已经进入生成树，则lowcost[i] = 0;
//否则，lowcost[i] = 边(Vi,Vj)的权值，其中
//j = closest[i]; 在所有与Vi关联的另一个顶点不再生成树的边中，(Vi,Vj)具有最小的权值
//算法具体操作：
//1 closet数组中的每个元素都设置为x，其中x为进入节点，lowcost数组中的值：如果(Vx,Vi)是边，就是这条边的权值，如果(Vx,Vi)不是边，而且i!=x就是正无穷大。
//2 每次从lowcost中找一个最小的i,lowcost(i)设置为0， 然后检查lowcost数组中所有的大于0的元素lowcost[k],如果(Vi,Vk)<lowcost[k],则把lowcost[k] = (Vi,Vk)
//并且closet[k] = i
//最后当网络中n个顶点全部进入生成树，整个构造过程结束，此时，所有的lowcost都是0，最小生成树的所有边都在closet中，他们是(Vi,closet[i]),当Vi和 closet[i]不是一个点
//如果n个顶点的连通无向网络，用邻接矩阵adjmatrix表示，并且假设已经建立好了
void prim(int x)
{//从x进入的，adjmatrix的最小生成树算法
int i; //用来记录最小lowcost的位置
int j;
int k;
int closet[n0+1]; //记录节点
float min; //整个lowcost中，非0元素的最小值
float lowcost[n0+1]; //记录最短边
//初始化
for(j=1;j<=n;j++)
{//得到所有点到x点的距离，并且设置所有点的closet[j] = x
closet[j] = x;
lowcost[j] = adjmatrix[x][j];
}
for(j=2;j<=n;j++)
{
min = infinity; //
for(k=1;k<=n;k++)
{//一趟下来找到最小的lowcost
if((lowcost[k]<min)&&(lowcost[k]!=0))
{
min = lowcost[k];
i = k;
}
}
//现在min是最小的lowcost,i是对应的位置
lowcost[i] = 0;
for(k=1;k<=n;k++)
{//修改所有lowcost[i]和所有closet[i]的遍历
if(lowcost[k]>adjmatrix[i][k])
{
lowcost[k] = adjmatrix[i][k];
closet[k] = i;
}
}
}
//现在得到了图的最小生成树，输出
for(j=1;j<=n;j++)
{
if(j!=closet[j])
{
cout<<"("<<j<<","<<"closet[j]"<<")"<<endl;
}
}
}
//迪杰特斯拉算法: 按最短路径长度由小到大的顺序,逐步求得每一条最短路径.
//有下面几个假设:
//1 n个顶点的有向网络用adjmatrix表示,其存储结构已建立.
//2 把网络中的所有顶点分成两个部分: 1 源点到他们的最短路径已经最终确定的. 2 源点到他们的最短路径还没有确定.
//有3个辅助数组
// dist[i] : Vx->Vi的"当前最短的"路径的长度
// path[i] : Vx->Vi的"当前最短的"路径上倒数第二个顶点的序号
// mark[i] : 1 : Vx->Vi 的最短路径已经确定,Vi进入第一组
// 0 : Vx->Vi 的最短路径没有确定,Vi还在第二组
//算法思路:
//1 初始化: 第一组中只有Vx,其他节点都在第二组,3个辅助数组的初始化
// mark[x] = 1 ;//进入点是x
// 对于所有的i(i!=x), mark[i] = 0;//表示没有进入第一组
// 对于所有的i,令dist[i] = Wxi,path[i] = x;
//2 从第二组的顶点中,选一个距离源点Vx最近的顶点Vk,将Vk加入到第一组.
// 检查第二组中其余顶点距离Vx的长度,若Vk加入到第一组后,可以使长度变短,就修正.
void dijkstra(int x)
{//进入点是x
int i; //index而已
int j;
int k;
int path[n0+1];//到结果的前一个节点的位置
int mark[n0+1]; //0不确定,1确定
float min; //目前最短的路径
float dist[n0+1]; //i到x的目前的最短路径
//初始化
for(i=1;i<=n;i++)
{
mark[i] = 0;
dist[i] = adjmatrix[x][i];
path[i] = x;
}
mark[x]=1; //x已经在第一组
do
{
min = infinity;
k=0;
for(i=1;i<=n;i++)
{
if((mark[i]==0)&&(dist[i]<min))
{//如果它的路径比min小,并且这个节点还没有进第一组,就替换min和index
min = dist[i];
k = i;//目前最小的距离的点的位置,也就是要加入到第一组的点的位置
}
}
if(k)
{//如果找到了这样的点,就是k!=0
mark[k]=1; //把k点加入到第一组
//修改其他的路径
for(i=1;i<=n;i++)
{
if(dist[i]>(min+adjmatrix[k][i]))
{//min:已经确定的Vx->Vk的最短距离, 就是说: 如果 目前Vx->Vi 的最短距离比 Vx->Vk的最短距离+(Vk,Vi),那么换路径好了,走k节点到i
dist[i] = min+adjmatrix[k][i];
path[i] = k;
}
}
}
} while (k); //当k为0时候说明,dijkstra算法结束
//现在输出
for(i=1;i<=n;i++)
{
if((i!=k)&&(dist[i]<infinity))
{//i!=k : 本身路径不用输出, dist[i]<infinity : 这个点是可达的
k = i;
do
{
cout<<k<<"--";
k = path[k]; //找前一个节点
} while (k!=x); //当找到源头的时候,这个路径得到
cout<<x<<endl;
cout<<"value : "<<dist[i]<<endl;
}
}
}
//拓扑排序,使用邻接表来存储图
void toposort()
{//
int s[n0+1]; //存储入度为0的节点的栈
int t; //栈点指针
int i; //仅仅是Index
int j;
arcnode* p; //
for(i=1;i<=n;i++)
{
if(adjlist[i].degree == 0)
{//如果i节点的入度为0
s[++t] = i;//入栈
}
}//得到了所有入度为0的节点
while(t)
{//当入度为0的节点栈不为空
i=s[t--];//出栈
cout<<i<<","; //就是topo序列的输出
p = adjlist[i].first;//得到i邻接的第一个节点
//下面是把所有i邻接的节点的入度都减1
while(p)
{//如果这个边存在
j = p->vertext;
adjlist[j].degree--;
if(adjlist[j].degree == 0)
{//如果这个节点的入度也为0了,也入栈
s[++t] = j;
}
p = p->next;
}
}
}
//关键路径
//E(i): 事件Vi可能的最早发生时间,它等同于从源点V1到Vi的最长路径长度
//L(i): 在保证结束点Vn在E(n)时刻发生的前提下,事件Vi允许的最晚发生时间,它等于E(n)-从顶点Vi到Vn的最长路径长度
//计算下面这两个两
//1 E(1)=0,然后沿着正向路径求E(j), E(j)=max{E(i)+Wij} , i<j<=n
//把所有的E(1..n) 都求出来.
//2 L(n)=E(n),然后反向求L(i), L(i)=min{L(j)-Wij} , i<j<=n
//关键路径的算法思路:
//1 从源点出发对网中顶点进行拓扑排序,在排序过程中,计算每个顶点的可能的最早发生时间
// 同时随时把入度为0的点的序号入栈,以便在排序结束后得到一个顶点的拓扑逆序.
// 当网中所有顶点都输出后,从保存顶点逆拓扑序列的栈中,依次弹出每个顶点的序号,计算各个顶点的最迟发生事件.以及各个活动的时间余量
//约定:
//1 AOE使用 邻接表
//2 E[1..n] : 每个顶点的最早发生时间
//3 L[1..n] : 每个顶点的最晚发生时间
//4 s 栈,t1 入栈的栈顶, t2 出栈的栈顶
//求关键路径
void criticalpath()
{
float E[n0+1]; //节点的最早发生时间
float L[n0+1]; //节点的最晚发生时间
int s[n0+1]; //栈
int t1 = -1; //入栈栈顶
int t2 = n0+1; //出栈栈顶
arcnode* p;
//求E[1..n]
//初始化
for(i=1;i<=n;i++)
{
E[i]=0;
}
s[++t1]=1; //入度为0的顶点入栈
while(t1 >-1)
{//如果栈不为空
i=s[t1--];//出栈
s[--t2]=i;//逆序的入栈
p=adjlist[i].first; //得到第i个节点关联的边
while(p)
{//如果第i个节点关联的边不为空,把这些边对应的点的入度-1
j=p->vertext; //边对应的点, i,j是有边相连接的
adjlist[j].degree--;
if(adjlist[j].degree == 0)
{//如果j点的入度为0,入t1栈
s[++t]=j;
}
if(E[j]<E[i]+p->weight)
{//得到max的E[j]
E[j] = E[i]+p->weight;
}
p=p->next;
}
}
//到这里构造E[1..n]结束,构造s[t2]结束.
//求L[1..n]
//初始化
for(i=1;i<=n;i++)
{
E[i]=L[n];
}
//一个拓扑逆序的过程
while(t2<n0+1)
{//当t2栈不为空,注意t2栈是一个逆序
i=s[t2++]; //t2栈出栈
p=adjlist[i].first; //这里的adjlist[i] 和上面的 adjlist[j]是 逆序的存储
while(p)
{
j = p->vertext;
if(L[i]>L[j]-p->weight)
{//求最小的
L[i]=L[j]-p->weight;
}
p=p->next;
}
}
//到这里就得到了L[1..n]
//下面输出所有的关键节点
for(i=1;i<=n;i++)
{
p= adjlist[i].first; //p是i节点连接的边
while(p)
{//如果这个边存在,要判断这个边是不是关键边,关键边就是关键路径
j=p->vertext;//j是这个边的另外一个节点,这条边是(i,j)
if(L[j] == E[i]+p->weight)
{//如果最晚结束时间 = 最早开始时间 + 需要时间 -> 这条边就是关键的
cout<<"<"<<i<<","<<j<<">"<<endl;
}
p = p->next;
}
}
}
//稀疏矩阵的转置
//使用了两个辅助数组
//num : num[j] : 矩阵A中第j列非零元素的个数
//cpot : cpot[j]: 矩阵A中第j列的第一个非零元素在其转置矩阵B的三元组顺序表的位置。
//推出2个规则：
//1 cpot[1] = 1；
//2 cpot[j] = cpot[j-1]+num[j-1];
//算法思路:
//根据1,2规则计算num数组和cpot数组
//根据cpot数组的指示求转置,将A的三元组顺序表中每个元素直接放入B的三元组顺序表中的适当位置.
#define max 100
struct element
{
int row,col; //行下标,列下标
int value; //值
};
struct triple
{
int m; //行数
int n; //列数
int t; //非0元素个数
element list[max+1]; //存放的位置
};
void transpos(triple &A,triple &B)
{//求A的转置数组B
int num[max+1]; //A每列非0元素的个数
int cpot[max+1];//A的某列非0元素在B的三元组中的位置
//基本信息的复制
B.m = A.n;
B.n = A.m;
B.t = A.t;
if(B.t>0)
{//如果存在非0的元素,这个时候才需要转置
//初始化num数组 num[j] : j列中非0元素的个数
//初始化
for(j=1;j<=A.n;j++)
{
num[j] = 0;
}
//求A中每一列中非0元素的个数
for(j=1;j<=A.t;j++)
{
num[A.list[j].col]++; //
}
//num已经初始化好了
//初始化cpot;
cpot[1] = 1;
for(j=2;j<=A.n;j++)
{
cpot[j] = cpot[j-1] +num[j-1];
}
//cpot也初始化好了
//求转置
for(p=1;p<=A.t;p++)
{
j = A.list[p].col; //j是某元素的列数
i = cpot[j]; //i是A的j列应该存储在B的三元组的首位
B.list[i].row = A.list[p].col;
B.list[i].col = A.list[p].row;
B.list[i].data =A.list[p].value;
cpot[j]++;
}
}
}
//对稀疏矩阵的十字链表的表示形式,进行插入一个非0节点
#define m0 100
#define n0 100
struct node
{
int row,col; //行列下标
int val; //值
node* down; //指向同列的 下一个 元素
node* right; //指向同行的 右边的元素
}
struct crosslist
{//十字链表
node* chead[m0+1]; //col列 的 头指针列表
node* rhead[n0+1]; //row行 的 头指针列表
int m; //行?
int n; //列?
int t; //非0元素的个数
}
crosslist A;
void insert(crosslist &A,int i,int j,int x)
{//给十字链表A的(i,j)位置上设置为x
node *s;
node *p;
node *q;
p = NULL;
q = A.rhead[i] ;//q指向第i行的第一个元素
while(q&&(q->col<j))
{//如果q存在,并且列比要插入的小,就继续向右移动
p = q; //p是上一个
q = q->right; //q是下一个
}
if((q==NULL)||(q->col>j))
{//不管是把整行都遍历完了,还是没有遍历完就找到了正确的位置
s = new node; //s为新增加了节点
A.t++;
s->row = i;
s->col = j;
s->val = x;
if(p==NULL)
{//说明i行原来就没有一个节点
s->right = A.rhead[i]; //要循环回去
A.rhead[i] = s;
}
else
{
s->right = q;
p->right = s;
}
//调整j列上的位置
p=NULL;
q = A.chead[j];
while(q&&(q->row<j))
{
p = q;
q = q->down;
}
if(p == NULL)
{//说明j列原来就没有一个元素
s->down = A.chead[j];
A.chead[j] = s;
}
else
{
s->down = q;
p->down = s;
}
}
}
//广义表
struct node
{
node* next;
int tag; //0 表示元素，1 表示指针
union
{
char atom; //值
node* head; //指针
};
};
//创建广义表
//算法思路: 从字符序列中分离出左部,右部,依次为左部和右部建立存储
char s[61]; //设字符序列长度不超过60
//eg:
// (a,b),(c),d,((e,f),g)
// | | |
// a i b
int sever(int a,int b)
{//从Sa->Sb中分离出左部,函数值为左部后面一个字符的下标
int i,k;
if(a>b) return 0; //a,b的大小弄错了
k=0;
i=a; //i是遍历的指针
do
{
switch(s[i])
{
case '(': k++;break; //k=1
case ')': k--; //K=0 .这个时候while可以结束
}
i++;
} while (!((k==0)&&(s[i]==',')||(i>b)));
return i;
}
//eg:
// ((a,b),(c),d,((e,f),g))
// | |
// i j
void create(node* &p,int i,int j)
{//根据Si~Sj 创建链表,返回表头指针p
int k;
node *q;
if(i>j)
{
return NULL;//如果i,j的大小的不对.
}
else
{//生成一个新的节点
p=new node();
if(i==j)
{//如果i,j指向一个原子节点,生成的节点存放原子值
p->tag=0;
p->atom=s[i];
}
else
{//新生成的节点作表头节点
p->tag=1;
p->next=NULL;
//去掉左右括号
i++;
j--;
//分离出左部和右部
k=sever(i,j); //k 左部的下一个字符
//递归处理左部
create(p->head,i,k-1); //p->head为返回的左部建立的链表的头指针
//递归处理右部
q=p->head; //q为左部的指针
while(q!=NULL)
{
i=k+1;
k=sever(q->next,i,k-1);
q=q->next;
}
}
}
}
//判断两个广义表是否相等
//算法思路:使用递归的方法,设Si是广义表S的第i个元素,Ti是广义表T的第i个元素
int equal(node* s,node* t)
{//s t是两个广义表的表头指针
int r=0;
if((s==NULL)&&(t==NULL))
{//如果两个广义表都是空的,就相等
r=1;
}
else
{
if((s!=NULL)&&(t!=NULL))
{//如果两个广义表都不是空的
if(s->tag == t->tag)
{
switch(s->tag)
{
case 0: //如果都是原始节点,并且值相等,next相等,就是相等的
r=((s->atom==t->atom)&&(equal(s->next,t->next)==1));
break;
case 1: //如果是子表,就判断head(它的下一级节点),next(它的同级别节点)是否相同.
r=(equal(s->head,t->head)==1)&&(equal(s->next,t->next)==1);
}
}
}
}
return r;
}
//查找
//约定 : 关键字字段名 key, 关键字类型 keytype
// 如果查找成功,就返回待查元素的地址,查找失败返回空
//查找类型:顺序查找,折半查找,分块查找,树型查找,散列查找,
//顺序查找
#define n 20
struct element
{
int key;
};
element v[n+1];
//顺序查找值为k的元素,
int seqsrch(int k)
{
int i=n;
v[0].key = k;//监视哨
while(v[i].key != k)
{
i--;
}
return i; //如果返回0表示没有找到
}
//折半查找k,时间复杂度O(log2(n))
int binsrch(int k)
{
int low; //查找范围的最低
int hig; //查找范围的最好
int mid; //查找范围的中间
low=1;
hig=n;
mid=(low+hig)/2;
while((v[mid].key!=k)&&(low<=hig))
{//如果没有查找成功 v[mid].key!=k
//或者可以继续查找下去 low<=hig
//退出while的条件:
//如果查找成功 v[mid].key==k
//如果查找失败 low>hig
if(v[mid].key>k)
{
low=mid+1;
}else if(v[mid].key<k)
{
hig=mid-1;
}
mid=(low+hig)/2;
}
if(low>hig) {mid=0;} //查找失败
return mid;
}
//分块查找
int
//树型查找
struct node
{
int key;
node* llink,node* rlink;
};
node* root;
//二叉树查找
node* bstsrch(int k)
{
node* q;
q=root;
while(q&&(q->key!=k))
{
if(k<q->key)
{
q=q->llink;
}
else
{
q=q->rlink;
}
}
return q;
}
//二叉树插入
void bstins(int k)
{
node* p;
node* q;
p=NULL;
q=root;
//首先进行查找，如果找到了就不进行插入，如果没有找到再进行插入
while(q&&q->key!=k)
{//如果没有找到叶子节点以下，并且没有找到
p = q;//p保存着q的父亲节点
if(k<q->key)
{
q=q->llink;
}
else
{
q=q->rlink
}
}
//插入
if(q==NULL)
{//说明没有找到要插入，而p是q的父亲节点
q = new node();
q->key=k;
q->llink=NULL;
q->rlink=NULL;
if(k<p->val)
{
p->llink = q;
}
else
{
p->rlink=q;
}
}
}
//二叉树的删除算法：
//1 如果被删除的节点没有左子树，则使用右孩子代替它。
//2 如果被删除的节点有左子树，则在其左子树，中找到中序遍历下的最后一个节点r，使被删除的节点的右子树成为r的右子树。并使用被删除节点的左孩子代替被删除节点
void bstdel(int k)
{
node *p;
node* q;
node* r;
node* s;
p=NULL;
q=root;
//先查找，如果找不到就不删除了
while(q&&(q->key!=k))
{//如果q不为空，如果还没有找到
p=q; //p是q的父节点
if(k<q->key)
{
q=q->llink;
}
else
{
q=q->rlink;
}
}
if(q!=NULL)
{//如果找到了，开始删除
//1 ，如果q没有左子树，直接使用q的右子树，作为q
if(q->llink==NULL)
{
//if(p->llink==q)
//{//如果q是p的左孩子
// p->llink=q->rlink;
//}
//else
//{//if p->rlink==q,如果q是p的右孩子
// p->rlink=q->rlink;
//}
//仅仅是保留q的右子树
s=q->rlink;
}
else
{//2 如果被删除的节点有左子树
s=q->llink;
r=s;
while(r->rlink)
{
r=r->rlink;
}
r->rlink=q->rlink;
}
if(p==NULL) root=s;
else
{
if(q==p->llink)
{
p->llink=s;
}
else
{
p->rlink=s;
}
}
delete q;
}
else
{//没找到就不删除了
}
}
//平衡二叉树插入
//插入思路：
//1 将新节点q作为树叶插入到合适的位置，并且令q的平衡因子为0，在找插入位置的同时，记下离新节点最近，而且平衡因子不为0的祖先节点s，
//若新节点的所有祖先节点的平衡因子都是0，则s指根节点
//2 修改从s到q的路径上的每个节点的平衡因子，不包括s和q节点。
//例如p是路径上的某个节点，若新节点插在p的左子树，就把p的平衡因子修改为-1，否则为1
//3 根据s的平衡因子，分三种情况处理
//a 若s平衡因子为0，说明s为根节点。只要修改s的平衡因子就可以。
//b 若s的平衡因子为-1/1，把q插到的反方向，就修改s的平衡因子为0。
//c 若s的平衡因子为-1/1，把q插到了正方向，就对以s为根的子树进行，左重组/右重组。
struct node
{
int key; //值
int bf; //平衡因子
node *llink,*rlink;
};
node *root;
node *t;
node *s;
node *r;
node *p; //子树的定点指针
node *q;
//左重组单旋转，左左
void LL()
{
p = r; //
s->llink = r->rlink;
r->rlink = s;
r->bf=0;
s->bf=0;
}
//左重组双旋转，左右
void LR()
{
p=r->rlink;
r->rlink=p->llink;
s->llink=p->rlink;
p->llink=r;
p->rlink=s;
switch(p->bf)
{
case -1:
//看不明白
case 1:
case 0:
}
}
void RR()
{//和LL一样，不管
}
void RL()
{
}
//在用线性探测开地址法处理冲突的散列表上进行查找和插入
#define m 15
#define nullrec 0 //标记空单元
struct element
{
int key; //键
int value; //值
};
element ht[m+1]; //散列表的存储
int n; //散列表中已有的节点的个数
//散列表中查找和插入,找到了就算查找,找不到就算插入
void hash_a(int k)
{//k是待查找或插入的节点的关键字
int i;
i=h(k); //散列函数,得到的k要存储的位置i
while((ht[i].key!=k)&&(ht[i].key!=nullrec))
{//如果ht[i]已经有值,但是不是k,并且ht[i]也不是空元素
i=(i+1)%(m+1);
//结束条件:1, key=k表示这个节点已经存在. 2,key=nullrec,表示这个位置是空的,可以插入.
}
if(ht[i].key==k)
{//表示已经存在
}
else if(n==m)
{//表示超了
}
else
{//表示ht[i].key=nullrec;表示这个节点可以插入
ht[i].key=k;
n++;
}
}
//散列表中的查找和插入,散列表的存储为链式的
struct node
{
int key;
int data;
node *next;
};
node *ht[m+1]; //表头节点
int n; //散列表上已经存储的元素的数量
void hash_b(int k)
{//k为要查找和插入的关键字
int i;
node *p;
i=h(k); //i是根据k计算出来的要插入的位置
p=ht[i]; //p指向这个位置的第一个元素或者是空
while(p&&(p->key!=k))
{//当p不为空,并且当前节点不是要插入的那个
p=p->next;
}
if(p)
{//如果p不为空,p->key==k 为结束条件,说明找到了
cout>>p->data;
}
else
{//说明p为空,说明没有找到,可以插入,
cout<<"插入";
node *temp=new node();
temp->key=k;
temp->next=ht[i];
ht[i]=temp;
n++;
}
}
//排序
//约定: 待排序的n个元素几经存放在整数数组的R[1..n]中,并且排序码是int类型,字段为key.
//排序后,n个元素依然在R[1..n]中,并按照顺序排序了.
#define n 20
struct element
{
int key;
};
element R[n+1];
//直接插入排序
void insertsort()
{
int i;
int j;
for(i=2;i<=n;i++)
{//要插入n-2+1= n-1次,n-1次插入操作
R[0]=R[i]; //R[i] 是要插入的值
j=i-1; //i-1是已经排序好了的最后一个元素
while(R[0].key<R[j].key)
{//如果顺序不对,R[j]向后移动
R[j+1]=R[j];
j--;
}
//到这里,移动结束
R[j+1]=R[0];
}
}
//简单选择排序
//从R[i..n]中,选择最小的元素,并与R[i]交换位置.
//实现思路:引入变量j,k
//j=i+1
//k=i
//反复比较R[k]和R[j],如果R[k].key>R[j].key ; k=j;j++;
//当j比较结束时候,交换R[i]和R[k]
void selectsort()
{//[i..n]
int i;
int j;
int k;
for(i=1;i<=n-1;i++)
{//所有的遍历遍数
k=i;
j=i+1;
while(j<=n)
{
if(R[k].key>R[j].key)
{
k=j;
}
j++;
}
if(i!=k)
{
int temp=R[i];
R[i]=R[k];
R[k]=temp;
}
}
}
//气泡排序
void bubblesort()
{
int i;
int j;
int swap;
int i=n;
do
{
swap=0;
for(j=1;j<=i-1;j++)
{
if(R[j].key>R[j+1].value)
{
swap=1;
int temp=R[j].key;
R[j].key=R[j+1].key;
R[j+1].key=temp;
}
}
i--;
} while ((i>1)&&swap); //i,每次气泡操作的最后一个元素,swap上一趟是否交换了
}
//堆排序
//把元素序列调整为堆
//在以R[i+1],R[i+2],...,R[m]为根的子树已经是堆的情况下,可按"筛选法",将R[i]为根的子树调整为堆
//从R[2i],R[2i+1]中选择排序码比较大的,不妨假设R[2i]的排序码大,比较R[2i]和R[i],如果R[i]大,说明以R[i]为根的子树,已经是堆.不做任何调整.
//否则,交换R[i]和R[2i],交换以后,R[2i+1]肯定是堆,但R[2i]可能变得不是堆了,需要对以R[2i]为根的子树调整,如此一层一层下去,最多到叶子节点.
//i是要调整的头部
//m是节点的末尾
void sift(int i,int m)
{
int k;
R[0]=R[i];
k=2*i;
while(k<=m)
{//如果2i都出了节点的末尾,说明没有这个节点
if((k<m)&&(R[k].key<R[k+1].key))
{//如果存在k+1节点,并且k+1节点的值>k节点的值
k++;
}
//这个时候k已经指向2i和2i+1的节点中,比较大的那个节点
if(R[0].key<R[k].key)
{//说明以i开头的二叉树不符合堆的条件
R[i]=R[k];//i和k 的值进行交换
i=k; //这个时候以k为根的二叉树不一定是堆了,有可能需要调整
k=2*i;
}
else
{
k=m+1; //推出循环
}
R[i]=R[0]; //这个时候i就是原来的2i和2i+1中比较大的那个
}
}
//堆排序的算法
void heapsort()
{
int j;
//堆的初始化
//从二叉树的最后一个"分支节点"R[i],i=n/2,调用算法sift(j,n) (其中j=i,i-1,...,1),依次以R[i],R[i-1],...,R[1]为根节点把书调整为对
for(j=n/2;j>=1;j--)
{
sift(j,n);
}
//到这里 堆 建立好了
//下面是堆排序,排序思想
//1 交换R[1]..R[n],把R[1]-R[n-1]重新调整为堆
//2 一直到交换R[1]R[2]为止
for(j=n;j>=2;j--)
{
temp=R[0];
R[0]=R[j];
R[j]=R[0];
//调整到n-1
sift(1,j-1);
}
}
//快速排序
//分组算法:Partition(i,j,k),以R[i]为标准,对R[i..j]进行分组,
//结果: R[1..k-1]都小于R[k]. R[k+1..j]都大于R[k]
void partition(int i,int j,int k)
{
R[0]=R[j];
while(i<j)
{//当i==j
while((i<j)&&(R[j].key>=R[0].key))
{//j的比k的大,这个是正常现象
j--;
}
//到这里说明R[j].key<R[0].key
R[i].key=R[j].key;
i++;
while((i<j)&&(R[i].key<=R[0].key))
{//i的比k的小,这个是正常现象
i++;
}
//到这里说明R[i].key>R[0].key
R[j]=R[i];
j--;
}
//说明i==j
R[i].key=R[k].key;
k=i;
}
//快速排序的思想:设一个栈,用于暂存待分组序列首尾元素的下表.在每次分组操作之前,先从栈中弹出待分组的元素序列首尾元素的下标.
//进行一次分组后,若某个子序列中有两个或两个以上的元素,就将该子序首尾元素的下标压入栈中.
//如此反复,直到栈空了为止
void quicksort()
{
struct
{
int low;
int hig;
} s[n+1]; //s用来存储上下标指针的数组
int t;
int i;
int j;
int k;
t=1; //t栈顶指针
s[t].low=1;
s[t].hig=n;//初始化
do
{
i=s[t].low;
j=s[t].hig;
t--; //出栈一个
partition(i,j,k);
if(k+1<j)
{//[k+1..j]这段元素个数>1
t++; //入栈
s[t].low=k+1;
s[t].hig=g;
}
if(i<k-1)
{//[i..k-1]这段元素个数大于1
t++; //入栈
s[t].low=i;
s[t].hig=k-1;
}
} while (t); //如果栈不为空,就继续
}
//归并排序
//把两个相邻的有序表归并的算法merge(R,S,a,b,c).
//该算法将有序表R[a..b]和R[b+1..c],归并到S[a..c]
//S是为了完成排序而引入的辅助数组,S和R具有相同的类型
void merge(element R[],element S[],int a,int b,int c)
{//这里的前提是R[a..b],R[b+1,c]都已经是有序的了，因为他们就是一点一点归并出来的
int i; //R的前部分的指针
int j; //R的后部分的指针
int k; //S的指针
i=a;
j=b+1;
k=a;
while((i<=b)&&(j<=c))
{//当R的前部分和R的后部分都有元素
if(R[i].key<R[j].key)
{
S[k++]=R[i++];
}
else
{
S[k++]=R[j++];
}
}
while(i<=b)
{
S[k++]=R[i++];
}
while(j<=c)
{
S[k++]=R[j++];
}
}
//一趟归并
void mergepass(element R[],element S[],int &m)
{
int i=1;
int j;
while(i+2*m-1<=n)
{//当i+2m还在n的范围内
merge(R,S,i,i+m-1;i+2*m-1);
i=i+2*m;
}
//到这里后面剩下的不够2m个
if(i+m-1<n)
{//如果剩下的还够合并一次
merge(R,S,i,i+m-1,n);
}
else
{//如果连一次都不够合并了,直接copy过去了
for(j=i+1;j<=n;j++)
{
S[j]=R[j];
}
}
m=2*m;
}
//整个归并排序的排序过程
void mergesort()
{
element S[n+1];
int i;
int m=1; //从1个单位开始归并
while(m<n)
{//如果2m>n说明所有的元素都归并过了
mergepass(R,S,m);
mergepass(R,S,m);
}
}
//基数排序
#define d 3
#define n 20
struct node
{
char key[d+1]; //排序码 89 d[0]=9,d[1]=8
int index; //下一个元素
};
node R[n+1]; //存储数据的
//各种排序算法的的特点
//1 时间复杂度: 直接插入排序,简单选择排序,起泡排序 : O(N2)
// 堆排序,快速排序,归并排序 : O(nLog2(n)),最差为O(N2)
// 基数排序 : O(d(n+b)) d:每个数的位数,n:要排序的元素的个数,b:基数
//2 稳定性: 简单选择排序,堆排序,快速排序 : 不稳定
// 其他 : 稳定
//从source中找到第一个dest的位置,以index返回
//return : -1失败,否则就是"开始位置"
strstr_self(char source[],char dest[],int index)
{
int i = 0; //source位置指针
int j = 0; //dest位置指针
index = -1;
while(i < source->length)
{
index = i; //index是要返回的值
while(source[i]&&dest[i]&&(source[i]==dest[j]))
{
i++;
j++
}
if(!dest[i])
{//表示找到了,返回
return index;
}else if(!source[i])
{
return -1;
}else
{//有不匹配的,需要重新比较
j=0;
i=index+1; //从下一个元素开始比较.
}
}
return -1;
}
//B- 树
//1 每个节点最多有m棵子树
//2 根节至少有2棵子树
//3 除根节点外，每个非终端的节点是少有m/2棵子树
//4 树叶都在最低层
//5 有k棵子树的非终端节点中恰好包含k-1个关键字以及指向相应记录的指针
//抽象数据类型
class base{}; //不包含任何信息的base
//对于单项链表
struct node
{
base *info;
node *next;
};
//抽象顺表类型
class adtsqlist
{
int n; //顺序表当前的元素个数
int n0; //顺序表的容量
base **v;
public:
void init(int m);
void clear();
int len();
void ins(int i,base *x);
void del(int i);
void store(base *x,int i);
base *recall(int i);
void sort();
int srch(base *p);
void trav();
virtual int compare(base *p,base *q)=0;//虚方法
virtual void visit(base *p)=0;//
};
class adtlinklist
{
int n; //链表中元素的个数
node *head; //指向头结点的指针
node *loc(int i);
public :
void init(); //初始化链表
void clear();
void ins(int i,base *x);
void del(int i);
void store(base *x,int i);
base *recall(int i);
void trav();
virtual void visit(base *p)=0;
};
//抽象顺序表类的实现
void adtsqlist::init(int m)
{
v=(base**)malloc(m*sizeof(base*));
n0=m;
n=0;
}
void adtsqlist::clear()
{
free(v);
n0=0;
n=0;
}
int adtsqlist::len()
{
return n;
}
void adtsqlist::ins(int i,base *x)
{//在第i个元素的后面插入x，就是从i+1个位置上插入
int j;
if((i>n)&&(i<0))
{//n代表元素的个数
cout<<"参数错";
return;
}
else if(n=n0-1)
{//最后一个元素不让存储
cout<<"溢出";
return;
}
else
{
for (j=n;j>i;j--)
{
v[j+1]=v[j];
}
v[i+1]=x;
n++;
}
}
void adtsqlist::del(i)
{//删除第i个元素
if((i>n)&&(i<0))
{
cout<<"位置错";
return;
}
else
{
for(j=i+1;j<=n;j++)
{
v[j-1]=v[j];
}
n--;
}
}
void adtsqlist::sort(base *x,int i)
{//把第i个位置上存储x
if((i>n)&&(i<0))
{
cout<<"位置错";
return;
}
else
{
delete(v[i]);
v[i]=x;
}
}
base *adtsqlist::recall(int i)
{
if((i>n)&&(i<0))
{
cout<<"位置错";
return NULL;
}
else
{
return v[i];
}
}
void adtsqlist::sort()
{
}
int adtsqlist::srch(base *p)
{
int i=n;
v[0]=p; //v[0]就是哨兵,到v[0]肯定会相等的
while(compare(v[i],p))
{//如果没有找到
i--;
}
return i;
}
void adtsqlist::trav()
{
int i;
for (i=1;i<=n;i++)
{
visit(v[i]);
}
}
//抽象单项链表
void adtlinklist::init()
{
head=new node;
head->info=NULL;
head->next=NULL;
n=0;
}
node* adtlinklist::loc(int i)
{//定位到链表的第i个元素
int j;
node *p;
if((i<0)&&(i>n))
{//如果要定位的范围不对
p=NULL;
}
else
{
p=head;
for (j=1;j<=i;j++)
{
p=p->next;
}
}
return p;
}
void adtlinklist::ins(int i,base* x)
{//在第i个位置以后插入x
node *q;
node *p=head;
if((i<0)&&(i>n))
{
return;
}
else
{
if(i>0)
{
p=loc(i);
}
//p现在是d第i个节点
q=new node();
q->info=x;
q->next=p->next;
p->next=q;
n++;
}
}
void adtlinklist::del(int i)
{
node *q;
node *p=head;
if((i<0)&&(i>n))
{
return;
}
else
{
if(i>1)
{
p=loc(i-1);
}
//p现在指向第i-1个节点
q=p->next;
p->next=q->next;
free(q->info);
n--;
}
}
void adtlinklist::store(base *x,int i)
{
node* p;
if((i<0)&&(i>n))
{
return;
}
else
{
p=loc(i);
del(p->info);
p->info=x;
}
}
base *adtlinklist::recall(int i)
{
node *p;
if((i<0)&&(i>n))
{
return NULL;
}
else
{
p=loc(i);
return p->info;
}
}
void adtlinklist::trav()
{
node *p;
p=head->next;
while(p)
{
visit(p->info);
p=p->next;
}
}
//使用刚才定义过的抽象数据类型
//定义实际的顺序表
class element:public base
{
public:
int key;
//其他字段
};
class sqlist: public adtsqlist
{//定义实际的顺序链表
virtual int compare(base *p,base *q);
virtual void visit(base *p);
};
int sqlist::compare(base *p,base *q)
{
if(((element*)p)->key>((element*)q)->key)
{
return 1;
}
else if(((element*)p)->key<((element*)q)->key)