求顺序表最大值
int GetMax(SqList L){
int i,maxx;
for(i=0;i<L.length;i++){
if(maxx<L.elem[i]){
maxx=L.elem[i];
}
}
return maxx;
}
单链表逆置(*)
void LListReverse(LLIST *list){
NODE *p, *q;
NODE *zc=list->head;
p = zc->next;
zc->next = NULL;
while(p != NULL)
{
q = p;
p = p->next;
q->next = zc->next;
zc->next = q;
}
}
十进制转二进制（顺序栈设计和应用）
bool isEmpty()
{
if(top==-1)
return 1;
else
return 0;
}
void Push(int x)
{
mystack[++top]=x;
}
int getTop()
{
return mystack[top];
}
void Pop()
{
top--;
}
求二叉树高度
int GetHeight(BinTree BT)
{
int high=0;//节点总数
int depthleft,depthright;
if(BT==NULL)
{
return 0;
}
else
{
depthleft=GetHeight(BT->Left);
depthright=GetHeight(BT->Right);
if(depthleft>=depthright)
{
high=1+depthleft;
}
else
{
high=1+depthright;
}
}
//先将二叉树层次遍历一遍，求出节点总数
return high;
}
二叉树的遍历
void InorderTraversal( BinTree BT )
{
if(BT){
InorderTraversal(BT->Left);
printf(" %c",BT->Data);
InorderTraversal(BT->Right);
}
}
void PreorderTraversal( BinTree BT )
{
if(BT){
printf(" %c",BT->Data);
PreorderTraversal(BT->Left);
PreorderTraversal(BT->Right);
}
}
void PostorderTraversal( BinTree BT )
{
if(BT){
PostorderTraversal(BT->Left);
PostorderTraversal(BT->Right);
printf(" %c",BT->Data);
}
}
void LevelorderTraversal( BinTree BT )
{
BinTree a[1000];
int front=0,tail=0;
BinTree T;
if(BT) a[++tail]=BT;
while(front!=tail){
T=a[++front];
printf(" %c",T->Data);
if(T->Left) a[++tail]=T->Left;
if(T->Right) a[++tail]=T->Right;
}
}
先序输出叶结点
void PreorderPrintLeaves( BinTree BT )
{
if(BT)
{
if(!BT->Left&&!BT->Right)
printf(" %c",BT->Data);
PreorderPrintLeaves(BT->Left);
PreorderPrintLeaves(BT->Right);
}
}
邻接矩阵存储图的深度优先遍历
void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) )
{
Visit(V);
Visited[V]=true;
for(int i=0;i<Graph->Nv;i++)
{
if((Graph->G[V][i]==1)&&(!Visited[i]))
{
DFS(Graph,i,(*Visit));
}
}
}
邻接表存储图的广度优先遍历
void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) )
{
int queue[1010];
int l=0,r=0;
queue[r++]=S;
(*Visit)(S);
Visited[S]=true;
PtrToAdjVNode tmp;
while(l!=r)
{
tmp=Graph->G[queue[l++]].FirstEdge;
while(tmp)
{
Vertex pos=tmp->AdjV;
if(!Visited[pos])
{
Visit(pos);
Visited[pos]=true;
queue[r++]=pos;
}
tmp=tmp->Next;
}
}
}
二分查找
Position BinarySearch( List L, ElementType X )
{
int left,right;
left=1;
right=L->Last;
while(left<=right)
{
int mid=(left+right)/2;
if(X>L->Data[mid])
{
left=mid+1;
}
else if(X<L->Data[mid])
{
right=mid-1;
}
else
return mid;
}
return NotFound;
}
快速排序
int Partition(SqList &L, int low, int high)
{
int base = L.r[low].key;
while(low < high){
while(low < high && L.r[high].key >= base){
high --;
}
L.r[low].key= L.r[high].key;
while(low < high && L.r[low].key <= base){
low ++;
}
L.r[high].key = L.r[low].key;
}
L.r[low].key = base;
return low;
}
void QuickSort(SqList &L, int low, int high){
if(low < high){
int base = Partition(L,low,high);
QuickSort(L,low,base - 1);
QuickSort(L, base + 1, high);
}
}
冒泡排序
void bubbleSort(int arr[], int n){
int t,flag=1;
int m=n-1;
while((m>0)&&(flag==1)){
flag=0;
for(int i=0;i<m;i++){
if(arr[i]>arr[i+1]){
flag=1;
t=arr[i];
arr[i]=arr[i+1];
arr[i+1]=t;
}
}
m--;
}
}
求素数个数
include<iostream>
include<vector>
using namespace std;
int a[10000020]={0};
int main(int argc, char const *argv[])
{
int n,sum=0;
cin >> n;
int i,j;
for(i=2;i*i<n;i++){
if(a[i]==0){
for(j=2*i;j<=n;j+=i){
if(a[j]!=1){
a[j]=1;
sum++;
}
}
}
}
/*for(i=2;i<=n;i++){
if(a[i]!=1){
sum++;
}
}*/
cout << n-sum-1 << endl;
return 0;
}
两个有序链表合并（新表不含重复元素）
#include<iostream>
using namespace std;
typedef struct LNode{
int data;
struct LNode *next;
}LNode,*Linklist;
void CreatList(Linklist &L){
int d;Linklist q,r;
L=new LNode;
r=L;
L->next=NULL;
while(1){
cin>>d;
if(d!=-1){
q=new LNode;
q->data=d;
q->next=NULL;
r->next=q;
r=q;
}
else {break;q->next=NULL;
}
}
}
void MergeList(Linklist &LA,Linklist &LB,Linklist &LC){
Linklist pa,pb,pc;
pa=LA->next;pb=LB->next;
LC=LA;
pc=LC;
while(pa&&pb){
if(pa->data<pb->data&&pa->data!=pc->data){
pc->next=pa;
pc=pa;
pa=pa->next;
}
else if(pa->data>pb->data&&pb->data!=pc->data){
pc->next=pb;
pc=pb;
pb=pb->next;
}
else if(pa->data==pb->data&&pa->data!=pc->data){
pc->next=pa;
pc=pa;
pa=pa->next;
pb=pb->next;}
else if(pa->data==pc->data) pa=pa->next;
else if(pb->data==pc->data)pb=pb->next;
}
while(pa){
if(pc->data!=pa->data){pc->next=pa;pc=pa;
}pa=pa->next;}
while(pb){
if(pc->data!=pb->data){pc->next=pb;pc=pb;
}pb=pb->next;}
pc->next=NULL;
}
void printlist(Linklist&L){
Linklist p;
p=L->next;
if(p==NULL)
cout<<"NULL";
while(p){
cout<<p->data;
if(p->next!=NULL) {cout<<" ";
}p=p->next;
}
}
int main(){
Linklist LA,LB,LC;
LA=new LNode;LA->next=NULL;
LB=new LNode;LB->next=NULL;
LC=new LNode;LC->next=NULL;
CreatList(LA);
CreatList(LB);
MergeList(LA,LB,LC);
printlist(LC);
return 0;
}
堆栈操作合法性
#include<iostream>
#include<malloc.h>
#include<stdlib.h>
#include<string>
defineOVERFLOW -2
defineOK 1
defineERROR 0
typedef int Status;
using namespace std;
typedef struct
{
char *base;
char *top;
int stacksize;
} SqStack;
Status InitStack(SqStack &S,int L)
{
S.base=new char[L];
if(!S.base)
exit(OVERFLOW);
S.top=S.base;
S.stacksize=L;
return OK;
}
Status push(SqStack &S,char c)
{
if(S.top-S.base==S.stacksize)
return ERROR;
*S.top++=c;
return OK;
}
Status pop(SqStack &S,char c)
{
if(S.top==S.base)
return ERROR;
c=*(--S.top);
return OK;
}
bool IsRight(string s,int L)
{
int i=0,flag=1;
SqStack St;
InitStack(St,L);
while(s[i]!='\0')
{
if(s[i]=='S')
{
if(push(St,s[i])==OK)
i++;
else
{
flag=0;
break;
}
}
else
{
if(pop(St,s[i])==OK)
i++;
else
{
flag=0;
break;
}
}
}
if((St.top==St.base) && s[i]=='\0')
flag=1;
else
flag=0;
if(flag==1)
return true;
else
return false;
}
int main()
{
int N,M,k=0;
char c;
string ss;
cin>>N>>M;
for(int i=0; i<N; i++)
{
cin>>ss;
if(IsRight(ss,M)==true)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
根据后序和中序遍历输出先序遍历
#include<bits/stdc++.h>
using namespace std;
defineMAXSIZE 100
typedef int TElemType;
typedef struct BiNode{
TElemType data;
struct BiNode *lchild, *rchild;
}BiNode, *BiTree;
BiTree Build(int *in, int *post, int n){ /// in是中序遍历结果, post是后序遍历结果
if(n <= 0) return NULL;
int *p = in;
while(p){
if(*p == *(post + n - 1))
break;
p++;
}
BiTree T = new BiNode;
T->data = *p;
int len = p - in;
T->lchild = Build(in, post, len);
T->rchild = Build( p + 1, post + len, n - len - 1);
return T;
}
void PreOrder(BiTree T){
if(T){
printf(" %d", T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
return ;
}
int main()
{
int n;
int pre[110], in[110];
BiTree T;
scanf("%d", &n);
for(int i=0; i<n; i++){
scanf("%d", &in[i]); //后序遍历
}
for(int i=0; i<n; i++){
scanf("%d", &pre[i]); //中序遍历
}
T = Build(pre, in, n);
printf("Preorder:");
PreOrder(T);
return 0;
}
哈夫曼编码
include<iostream>
include<queue>
include<algorithm>
using namespace std;
int sum=0;
bool Check(int *a,string *ss,int n)
{
int len=0;
string l,s;
int c;
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
c=min(ss[i].length(),ss[j].length());
if(ss[i].substr(0,c)==ss[j].substr(0,c))//检查是否存在一个编码是另一个编码的前缀
{
return false;
}
}
len+=a[i]*ss[i].length();
}
if(len!=sum)//如果长度不是最短长度
return false;
return true;
}
int main()
{
priority_queue<int,vector<int>,greater<int> > Q;
string ss[1001],s,code[1001];
int n,n2,a[1001],t=0;
cin>>n;
for(int i=0; i<n; i++)
{
cin>>ss[i];
cin>>a[i];
Q.push(a[i]);
}
while(Q.size()>1)//求最短编码的长度
{
t=0;
t+=Q.top();
Q.pop();
t+=Q.top();
Q.pop();
sum+=t;
Q.push(t);
}
cin>>n2;
for(int i=0; i<n2; i++)
{
for(int j=0; j<n; j++)
{
cin>>s;
cin>>code[j];
}
if(Check(a,code,n)==true)
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
}
return 0;
}
学生顺序表的建立
include<bits/stdc++.h>
using namespace std;
defineMAXSIZE 1000
struct sz{
int no;
string name;
double x,y,z;
};
class Seqlist
{
public:
int length;
sz date[MAXSIZE];
Seqlist(sz a[],int n)
{
for(int i=0; i<n; i++)
{
date[i]=a[i];
}
length=n;
}
void print()
{
for(int i=0; i<length; i++)
{
cout<<setiosflags(ios::fixed)<<setprecision(1);
cout<<date[i].no<<" "<<date[i].name<<" "<<date[i].x<<" "<<date[i].y<<" "<<date[i].z<<endl;
}
}
};
int main()
{
int n,i;
cin>>n;
sz a[MAXSIZE];
for(i=0;i<n;i++){
cin>>a[i].no;
cin>>a[i].name;
cin>>a[i].x;
cin>>a[i].y;
cin>>a[i].z;
}
Seqlist l(a,n);
l.print();
}
求两个一元多项式的和
include<iostream>
using namespace std;
struct Node //定义多项式链表的结点
{
int coef, exp; // coef表示系数，exp表示指数
Node *next;
};
class Polynomial
{
public:
Polynomial( ); //构造函数
~Polynomial( ); //析构函数，同单链表析构函数
Polynomial(const Polynomial &B); //拷贝构造函数
Polynomial operator + (Polynomial &B); //重载运算法，多项式相加
void Print( ); //打印一元多项式
private:
Node *first;
};
Polynomial::~Polynomial( )
{
Node *q = nullptr;
while (first != nullptr) //释放单链表的每一个结点的存储空间
{
q = first; //暂存被释放结点
first = first->next; // first指向被释放结点的下一个结点
delete q;
}
}
Polynomial :: Polynomial(const Polynomial &B){
first = B.first;
}
Polynomial :: Polynomial( )
{
Node *r = nullptr, *s = nullptr;
int coef, exp;
first = new Node; //申请头结点
r = first; r->next = nullptr; //尾插法建立单链表
//cout<<"sr xs zs:";
int nnn;
cin>>nnn;
while(nnn--){
cin >> coef >> exp;
s = new Node; s->coef = coef; s->exp = exp;
r->next = s; r = s;
}
//cout << "请输入系数和指数：";
//输入第一项的系数和指数
/*while (coef != 0 && exp != 0) //循环结束的条件是输入系数为0
{
//将结点s插入单链表的尾部
//cout<<"sr xs zs:";
//cout << "请输入系数和指数：";
cin >> coef >> exp;
}*/
r->next = nullptr;
}
Polynomial Polynomial :: operator + (Polynomial &B)
{
Node *pre = first, *p = pre->next; //工作指针pre和p初始化
Node *qre = B.first, *q = qre->next; //工作指针qre和q初始化
Node *qtemp = nullptr;
while (p != nullptr && q != nullptr)
{
if (p->exp > q->exp) { //第1种情况
pre = p; p = p->next;
}
else if (p->exp < q->exp) { //第2种情况
qtemp = q->next;
pre->next = q; //将结点q插入到结点p之前
q->next = p;
q = qtemp;
pre = q;
qre->next = q;
}
else { //第3种情况
p->coef = p->coef + q->coef;
if (p->coef == 0) { //系数相加为0，则删除结点p
pre->next = p->next;
delete p;
p = pre->next;
}
else { //系数不为0
pre = p; p = p->next;
}
qre->next = q->next; //第3种情况都要删除结点q
delete q;
q = qre->next;
}
}
if (p == nullptr) pre->next = q; //将结点q链接在第一个单链表的后面
B.first->next = nullptr;
return *this;
}
void Polynomial :: Print( )
{
Node *p = first->next;
if(p==nullptr){
cout<<0<<" "<<0<<endl;
return;
}
if (p != nullptr) /*输出第一项*/
cout << p->coef << " " << p->exp;
p = p->next;
while (p != nullptr)
{
if (p->coef > 0) /*输出系数的正号或负号*/
cout << " " << p->coef << " " << p->exp;
else
cout << " "<< p->coef << " " << p->exp;
p = p->next;
}
cout << endl;
}
int main( )
{
Polynomial A{ };
//A.Print( );
Polynomial B{ }; //定义多项式A和B
//B.Print( );
Polynomial C = A + B;
//printf("结果是：");
C.Print( ); //输出相加结果
return 0;
}
京公网安备11010502036362号