一.图书信息管理系统

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXSIZE 10000typedef struct {char no[100];//图书ISBNchar name[100];//图书名字double price;//图书价格
} Book;typedef struct {Book data[MAXSIZE];int length;
} SqList,*PSqList;FILE* fp;
int cnt,st,op,i,j,k,flag,idx,num;
char name[100],no[100];
double price;
Book temp;void menu();//菜单
void add(PSqList PL);//图书插入
void delete1(PSqList PL);//图书删除
void modify(PSqList PL);//价格更新
void output(PSqList PL);//图书浏览
void search(PSqList PL);//图书查找
void price_sort(PSqList PL);//价格排序
void reserse_save(PSqList PL);//逆序存储
void bookstatistics(PSqList PL);//图书统计
void read_in_information(PSqList PL);//导入信息
void save_information1(PSqList PL);//保存信息1(存储到book.txt中)
void save_information2(PSqList PL);//保存信息2.1(正序存储到book-newsort.txt中)
void save_information3(PSqList PL);//保存信息2.2(逆序存储到book-newsort.txt中)
int main() {PSqList PL;//创建一个顺序表,PL为一个指针变量PL = (PSqList)malloc(sizeof(SqList)); // 分配内存if(PL) PL->length = 0;else {printf("内存分配失败!!!\n");exit(-1);}read_in_information(PL);//导入信息printf("图书信息如下:\n");output(PL);//图书浏览menu();//菜单scanf("%d", &op);if (op >= 1 && op <= 8) {switch (op) {case 1:add(PL);break;case 2:delete1(PL);break;case 3:modify(PL);break;case 4:price_sort(PL);break;case 5:output(PL);break;case 6:search(PL);break;case 7:bookstatistics(PL);break;case 8:reserse_save(PL);break;}} else printf("输入无效\n");return 0;
}
//菜单
void menu() {printf("                                            图书信息管理系统\n");printf("***********************************************************************************************************************\n");printf("                                 	1.图书插入\n");printf("                                 	2.图书删除\n");printf("                                 	3.价格更新\n");printf("                                	4.价格排序\n");printf("                                 	5.图书浏览\n");printf("                                 	6.图书查找\n");printf("                                 	7.图书统计\n");printf("                                 	8.逆序存储\n");printf("***********************************************************************************************************************\n");printf("请输入代码选择(1-8):\n");
}
//图书浏览
void output(PSqList PL) {printf("北京林业大学图书馆计算机类图书采购列表\n");printf("ISBN         书名                    定价\n");for(i=1; i<=PL->length; i++) {printf("%-10s  %-20s    %-10.2f\n",PL->data[i].no,PL->data[i].name,PL->data[i].price);}printf("\n");
}
//图书统计
void bookstatistics(PSqList PL) {printf("图书总数为%d\n",PL->length);printf("\n");
}
//图书查找
void search(PSqList PL) {flag = 1;while (1) {printf("请输入需要查找的图书位置或书名(如果有多本,则全部输出)\n按键1选择输入图书位置,按键2选择输入书名,按键0选择停止输入:");scanf("%d", &op);if (op == 1 || op == 2 || op == 0) {switch (op) {case 0:flag = 0;break;case 1: {printf("请输入要查找的图书位置:");scanf("%d", &num);if(num<1||num>PL->length) printf("图书不存在,查找失败\n");else {printf("该图书信息如下:\n");printf("ISBN       书名         定价\n");printf("%-8s  %-8s    %-6.2f\n",PL->data[num].no,PL->data[num].name,PL->data[num].price);}}break;case 2: {printf("请输入要查找的书名:");scanf("%s", name);int cnt=0;for(int i=1; i<=PL->length; i++) {if(strcmp(PL->data[i].name,name)==0) cnt++;}if(cnt==0) printf("图书不存在,查找失败\n");else {printf("该图书信息如下:\n");printf("ISBN       书名         定价\n");for(int i=1; i<=PL->length; i++) {if(strcmp(PL->data[i].name,name)==0) printf("%-8s  %-8s    %-6.2f\n",PL->data[i].no,PL->data[i].name,PL->data[i].price);}}break;}}} else {printf("输入无效,请重新输入!!!\n");continue;}if (flag == 0) break;}printf("\n");
}
//价格更新
void modify(PSqList PL) {for(i=1; i<=PL->length; i++) {if(PL->data[i].price<45) PL->data[i].price*=1.2;else PL->data[i].price*=1.1;}save_information2(PL);//正序存储到新文件book-newsort.txt中printf("更新成功!!!\n");
}
//图书插入
void add(PSqList PL) {printf("请输入需要插入的图书信息(ISBN,书名,定价):\n");scanf("%s%s%lf", no, name, &price);printf("请输入需要插入的位置num:\n");scanf("%d",&num);if(num<1||num>PL->length) printf("指定位置非法!!!\n");else {for(i=PL->length; i>=num; i--) {strcpy(PL->data[i+1].no,PL->data[i].no),strcpy(PL->data[i+1].name,PL->data[i].name),PL->data[i+1].price=PL->data[i].price;}strcpy(PL->data[num].no,no),strcpy(PL->data[num].name,name),PL->data[num].price=price;PL->length++;}save_information1(PL);//存储到book.txt中
}
//图书删除
void delete1(PSqList PL) {printf("请输入需要删除的图书位置:\n");scanf("%d", &num);if(num<1||num>PL->length) printf("指定位置非法!!!\n");else {for(int i=num; i<PL->length; i++) {strcmp(PL->data[i].no,PL->data[i+1].no),strcmp(PL->data[i].name,PL->data[i+1].name),PL->data[i].price=PL->data[i+1].price;}PL->length--;}save_information1(PL);//存储到book.txt中
}
//导入信息
void read_in_information(PSqList PL) {if ((fp = fopen("D:\\book.txt", "r")) == NULL) {printf("file open error!\n");exit(0);}while (!feof(fp)) {++cnt;fscanf(fp,"%s%s%lf",PL->data[cnt].no,PL->data[cnt].name,&PL->data[cnt].price);PL->length++;}if (fclose(fp)) {printf("can not close the file!\n");exit(0);}
}
//价格排序
void price_sort(PSqList PL) {for(i=1; i<PL->length; i++) {k=i;for(j=i+1; j<=PL->length; j++) {if(PL->data[j].price<PL->data[k].price) k=j;}if(k!=i) {temp=PL->data[i];PL->data[i]=PL->data[k];PL->data[k]=temp;}}save_information2(PL);//正序存储到新文件book-newsort.txt中printf("排序成功!!!\n");
}
//逆序存储
void reserse_save(PSqList PL) {save_information3(PL);//逆序存储到新文件book-newsort.txt中printf("操作成功!!!\n");
}
//保存信息1
void save_information1(PSqList PL) {if ((fp = fopen("D:\\book.txt", "w")) == NULL) {printf("file open error!\n");exit(0);}for(int i=1; i<=PL->length; i++) {if(i<PL->length) fprintf(fp,"%s %s %.2f\n",PL->data[i].no,PL->data[i].name,PL->data[i].price);else fprintf(fp,"%s %s %.2f",PL->data[i].no,PL->data[i].name,PL->data[i].price);}if (fclose(fp)) {printf("can not close the file!\n");exit(0);}
}
//保存信息2.1(正序存储到book-newsort.txt中)
void save_information2(PSqList PL) {if ((fp = fopen("D:\\book-newsort.txt", "w")) == NULL) {printf("file open error!\n");exit(0);}for(int i=1; i<=PL->length; i++) {if(i<PL->length) fprintf(fp,"%s %s %.2f\n",PL->data[i].no,PL->data[i].name,PL->data[i].price);else fprintf(fp,"%s %s %.2f",PL->data[i].no,PL->data[i].name,PL->data[i].price);}if (fclose(fp)) {printf("can not close the file!\n");exit(0);}
}
//保存信息2.2(逆序存储到book-newsort.txt中)
void save_information3(PSqList PL) {if ((fp = fopen("D:\\book-newsort.txt", "w")) == NULL) {printf("file open error!\n");exit(0);}for(int i=PL->length; i>=1; i--) {if(i>1) fprintf(fp,"%s %s %.2f\n",PL->data[i].no,PL->data[i].name,PL->data[i].price);else fprintf(fp,"%s %s %.2f",PL->data[i].no,PL->data[i].name,PL->data[i].price);}if (fclose(fp)) {printf("can not close the file!\n");exit(0);}
}

二.排序综合

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include<iostream>
using namespace std;
#define MAXSIZE 1000000
typedef struct node {int r[MAXSIZE];int length;
} SeqList, *PSeqList;
int cnt;//移动次数
double t0;
clock_t start_t,end_t;
int gaps[3] = {5, 3, 1};
// 生成随机整数数组
void generateRandomArray(int arr[]) {srand(time(NULL));for (int i = 1; i <= 3000; i++) {arr[i] = rand() % 100000;}
}
//冒泡排序
void BubbleSort(SeqList *S) {int i, j;start_t=clock();cnt=0;for (i = 1; i <= S->length - 1; i++) {for (j = 2; j <= 1 + S->length - i; j++) {if (S->r[j] < S->r[j - 1]) {S->r[0] = S->r[j];S->r[j] = S->r[j - 1];S->r[j - 1] = S->r[0];cnt++;}}}end_t=clock();t0=(double)(end_t-start_t)/CLK_TCK;printf("移动次数:%d\n", cnt);cout<<"所用时间:"<<t0<<"秒"<<endl;
}
//简单选择
void SelectSort(SeqList *S) {int i, j, tmp, t;start_t=clock();cnt=0;for (i = 1; i < S->length; i++) {for (j = i + 1, t = i; j <= S->length; j++) {if (S->r[t] > S->r[j]) t = j;}if (t != i) {tmp = S->r[t];S->r[t] = S->r[i];S->r[i] = tmp;cnt++;}}end_t=clock();t0=(double)(end_t-start_t)/CLK_TCK;printf("移动次数:%d\n", cnt);cout<<"所用时间:"<<t0<<"秒"<<endl;
}
//直接插入排序
void StraightInsert(SeqList *S) {int i, j;start_t=clock();cnt=0;for (i = 2; i <= S->length; i++) {S->r[0] = S->r[i];j = i - 1;while (S->r[0] < S->r[j]) {S->r[j + 1] = S->r[j];cnt++;j--;}S->r[j + 1] = S->r[0];cnt++;}end_t=clock();t0=(double)(end_t-start_t)/CLK_TCK;printf("移动次数:%d\n", cnt);cout<<"所用时间:"<<t0<<"秒"<<endl;
}
//希尔排序
void ShellInsert(SeqList *S, int gap) {int i, j;for (i = gap + 1; i <= S->length; i++) {if (S->r[i] < S->r[i - gap]) {S->r[0] = S->r[i];for (j = i - gap; j > 0 && S->r[0] < S->r[j]; j = j - gap) S->r[j + gap] = S->r[j], cnt++;S->r[j + gap] = S->r[0];cnt++;}}
}
void ShellSort(SeqList *S, int gaps[], int t) {int k;start_t=clock();cnt=0;for (k = 0; k < t; k++) ShellInsert(S, gaps[k]);end_t=clock();t0=(double)(end_t-start_t)/CLK_TCK;printf("移动次数:%d\n", cnt);cout<<"所用时间:"<<t0<<"秒"<<endl;
}
//快速排序
int QuickSort1(SeqList *S, int low, int high) {int pivotkey;S->r[0] = S->r[low];pivotkey = S->r[low];while (low < high) {while (low < high && S->r[high] >= pivotkey) high--;S->r[low] = S->r[high];cnt++;while (low < high&&S->r[low]<=pivotkey) low++;S->r[high] = S->r[low];cnt++;}S->r[low] = S->r[0];cnt++;return low;
}
void QuickSort(SeqList *S, int low, int high) {int pivotloc;if (low < high) {pivotloc = QuickSort1(S, low, high);QuickSort(S, low, pivotloc - 1);QuickSort(S, pivotloc + 1, high);}
}
//归并排序
void Merge(int r[], int rf[], int u, int v, int t) {int i, j, k;for (i = u, j = v + 1, k = u; i <= v && j <= t; k++) {if (r[i] <= r[j]) {rf[k] = r[i];i++;cnt++;} else {rf[k] = r[j];j++;cnt++;}}while (i <= v) rf[k++] = r[i++], cnt++;while (j <= t) rf[k++] = r[j++], cnt++;
}
void MSort(int p[], int p1[], int n, int t) {int m;int p2[3010];if (n == t) {p1[n] = p[n];} else {m = (n + t) / 2;MSort(p, p2, n, m);MSort(p, p2, m + 1, t);Merge(p2, p1, n, m, t);}
}
void MergeSort(SeqList *S) {start_t=clock();cnt=0;MSort(S->r, S->r, 1, S->length);end_t=clock();t0=(double)(end_t-start_t)/CLK_TCK;printf("移动次数:%d\n", cnt);cout<<"所用时间:"<<t0<<"秒"<<endl;
}
//堆排序
void HeapAdjust(SeqList *S, int n, int m) {int i, j;int rc;rc = S->r[n];i = n;for (j = 2 * i; j <= m; j = j * 2) {if (j < m && S->r[j] < S->r[j + 1]) j = j + 1;if (rc > S->r[j]) break;S->r[i] = S->r[j];i = j;cnt++;}S->r[i] = rc;
}
void HeapSort(SeqList *S) {start_t=clock();cnt=0;int i;int temp;for (i = S->length / 2; i > 0; i--) {HeapAdjust(S, i, S->length);}for (i = S->length; i > 1; i--) {temp = S->r[1];S->r[1] = S->r[i];S->r[i] = temp;HeapAdjust(S, 1, i - 1);cnt++;}end_t=clock();t0=(double)(end_t-start_t)/CLK_TCK;printf("移动次数:%d\n", cnt);cout<<"所用时间:"<<t0<<"秒"<<endl;
}
int main() {PSeqList S;S = (PSeqList)malloc(sizeof(SeqList));if (S) S->length = 3000;generateRandomArray(S->r);printf("\n");printf("**********************************************************************\n");printf("                        	排序方式\n");printf("                        	1.冒泡排序\n");printf("                        	2.简单选择排序\n");printf("                        	3.直接插入排序\n");printf("                        	4.希尔排序\n");printf("                        	5.快速排序\n");printf("                        	6.归并排序\n");printf("                        	7.堆排序\n");printf("**********************************************************************\n");printf("请选择排序方式:");int op;scanf("%d", &op);if (op >= 1 && op <= 7) {switch (op) {case 1:BubbleSort(S);break;case 2:SelectSort(S);break;case 3:StraightInsert(S);break;case 4:ShellSort(S, gaps, 3);break;case 5:start_t=clock();cnt=0;QuickSort(S, 1, S->length);end_t=clock();t0=(double)(end_t-start_t)/CLK_TCK;printf("移动次数:%d\n", cnt);cout<<"所用时间:"<<t0<<"秒"<<endl;break;case 6:MergeSort(S);break;case 7:HeapSort(S);break;}} else {printf("输入无效!!!\n");}return 0;
}

三.最小生成树 

#include<stdio.h>
#define INFINITY 30000
#define MaxVertexNum 30
typedef struct{char vertexs[MaxVertexNum];//顶点表int arcs[MaxVertexNum][MaxVertexNum];//邻接矩阵,即边表int vertexNum,edgeNum;//顶点数和边数
}MGraph;//MGraph是以邻接矩阵存储的图类型
typedef struct{int adjvertex;//某顶点与已构造好的部分生成树的顶点之间权值最小的顶点int lowcost;//某顶点与已构造好的部分生成树的顶点之间的最小权值
}ClosEdge[MaxVertexNum];//用prim算法求最小生成树时的辅助数组
void CreatGraph(MGraph *G){//建立一个图的邻接矩阵int i,j,k,w;scanf("%d%d",&(G->vertexNum),&(G->edgeNum));//输入顶点数和边数for(i=0;i<G->vertexNum;i++){scanf(" %c",&(G->vertexs[i]));//输入顶点信息,建立顶点表 A,B,C,D}for(i=0;i<G->vertexNum;i++){for(int j=0;j<G->vertexNum;j++){if(i==j) {G->arcs[i][j]=G->arcs[j][i]=0;}else G->arcs[i][j]=G->arcs[j][i]=INFINITY;//初始化邻接矩阵}}for(k=0;k<G->edgeNum;k++){scanf("%d%d%d",&i,&j,&w);//输入e条边,建立邻接矩阵G->arcs[i][j]=w;G->arcs[j][i]=w;}
}
void Prim(MGraph G,int u,ClosEdge closedge){//从第u个顶点出发构造图G的最小生成树,最小生成树顶点信息存放在数组closedge中int i,j,w,k;for(i=0;i<G.vertexNum;i++){//辅助数组初始化if(i!=u){closedge[i].adjvertex=u;closedge[i].lowcost=G.arcs[u][i];}}closedge[u].lowcost=0;//初始,U={u};for(i=0;i<G.vertexNum-1;i++){//选择其余的G.vertxeNum-1个顶点w=INFINITY;for(j=0;j<G.vertexNum;j++){//在辅助数组closedge中选择权值最小的顶点if(closedge[j].lowcost!=0&&closedge[j].lowcost<w){w=closedge[j].lowcost;k=j;}}closedge[k].lowcost=0;//求得生成树的下一个顶点k,第k顶点并U集for(j=0;j<G.vertexNum;j++){//新顶点并入U后,修改辅助数组if(G.arcs[k][j]<closedge[j].lowcost){closedge[j].adjvertex=k;closedge[j].lowcost=G.arcs[k][j];}}}int sum=0;for(i=0;i<G.vertexNum;i++){if(i!=u) {printf("%c->%c,%d\n",G.vertexs[i],G.vertexs[closedge[i].adjvertex],G.arcs[i][closedge[i].adjvertex]);sum+=G.arcs[i][closedge[i].adjvertex];}}printf("最小生成树总和为%d\n",sum);
}
int main()
{MGraph G;ClosEdge closedge;CreatGraph(&G);int start=1;Prim(G,start,closedge);return 0;
}

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
#define MaxvertexNum 30
#define MaxEdge 100
typedef struct ENode{int vertex1,vertex2;int weight;
}ENode;
typedef struct ELGraph{int vertexNum,edgeNum;//顶点个数,边的个数char vertexs[MaxvertexNum];//顶点信息ENode edges[MaxvertexNum];//边的信息
}ELGraph;
bool compareEdges(ENode edge1, ENode edge2) {return edge1.weight < edge2.weight;
}
void Kruskal(ELGraph G,ENode TE[]){//用Kruskal算法构成图G的最小生成树,最小生成树存放在TE[]中int i,j,k;int s1,s2;int f[MaxvertexNum];for(i=0;i<G.vertexNum;i++) f[i]=i;//初始化f数组sort(G.edges, G.edges + G.edgeNum, compareEdges);//对图G的边表按权值从小到大排序j=0;k=0;while(k<G.vertexNum-1){//选n-1条边s1=f[G.edges[j].vertex1];s2=f[G.edges[j].vertex2];if(s1!=s2){//产生一条最小边TE[k].vertex1=G.edges[j].vertex1;TE[k].vertex2=G.edges[j].vertex2;TE[k].weight=G.edges[j].weight;k++;for(i=0;i<G.vertexNum;i++){if(f[i]==s2) f[i]=s1;//修改连通的编号}}j++;}
}
int main()
{ELGraph G;scanf("%d%d",&(G.vertexNum),&(G.edgeNum));//输入顶点数和边数for(int i=0;i<G.vertexNum;i++){scanf(" %c",&(G.vertexs[i]));//输入顶点信息,建立顶点表 A,B,C,D}for(int i=0;i<G.edgeNum;i++){int a,b,w;scanf("%d%d%d",&a,&b,&w);G.edges[i]={a,b,w};}ENode TE[G.vertexNum - 1];Kruskal(G,TE);int sum=0;for(int i=0;i<G.vertexNum-1;i++){printf("%c->%c,%d\n",G.vertexs[TE[i].vertex1],G.vertexs[TE[i].vertex2],TE[i].weight);sum+=TE[i].weight;}printf("最小生成树总和为%d\n",sum);return 0;
}