数据结构与算法实验源代码.doc

实验二#include#include#define Maxlen 100typedef structint dataMaxlen;int last;Sequenlist;Sequenlist *SqLsetnull() /建立一个空的顺序表Sequenlist *L;L=(Sequenlist *)malloc(sizeof(Sequenlist);L-last=-1;return L;void *SqLset(Sequenlist *L) /对顺序表输入数据int n;printf(请输入要输入的元素数量：);scanf(%d,&n);printf(请输入要输入的元素：);for(int i=0;idatai);L-last=i;return L;int SqLdelete(Sequenlist *L,int i) /删除顺序表中的元素 /因为只是调用该函数删除顺序表中多余的元素省略的一些数据判断int j;for(j=i;jlast+1;j+)L-dataj=L-dataj+1;L-last-;return 1;void SqLdel(Sequenlist *L) /寻找顺序表中多余的元素并删除int i,j;if(L-last0)printf(n顺序表为空n);elsefor(i=0;ilast;i+)for(j=i+1;jlast;j+)if(L-dataj=L-datai)SqLdelete(L,j); /调用函数删除下标为j的结点void SqLsc(Sequenlist *L) /输出顺序表中的数据int i;if(L-last0)printf(n顺序表为空n);elseprintf(顺序表中的元素：);for(i=0;ilast;i+)printf(%d ,L-datai);printf(n);int main(void)Sequenlist *L;L=SqLsetnull();int choice;printf(1,输入数据 2，删除重复多余的数据 3,输出数据 0，退出 n);doprintf(请输入选择：);scanf(%d,&choice);switch(choice)case 1:SqLset(L);printf(n);break;case 2:SqLdel(L);printf(n);break;case 3:SqLsc(L);printf(n);break;default:printf(请输入正确的选择!n);break;case 0:break;while(choice!=0);return 0;实验三#include#include#define SIZE 15typedef structint dataSIZE;int last;RecordList;RecordList *shuru() /向顺序表中输入数据int s,i=0;RecordList *L;L=(RecordList *)malloc(sizeof(RecordList);printf(请输入要输入到顺序表中数据的数量：);scanf(%d,&s);if(s15)printf(超过最大的数据长度);elseprintf(请输入要输入的数据：);for(i=0;idatai);printf(成功输入%d个数据 nn,i);L-last=i-1;return L;void paixu(RecordList *L) /冒泡排序法对顺序表中的数据进行排序int x,change=1,i,j;for(i=0;ilast&change!=0;i+)change=0;for(j=0;jlast-i;j+)if(L-datajL-dataj+1)x=L-dataj+1;L-dataj+1=L-dataj;L-dataj=x;change=1;int BinSrch(RecordList *L,int k) /二分查找int low=0,i=-1,high,mid;high=L-last;while(lowdatamid)i=mid;break;else if(kdatamid)high=mid-1;elselow=mid+1;return i;int main(void)RecordList *L=NULL;int i,choice,data1;printf(1,输入数据2，二分法查找0,退出n);doprintf(请输入选择：);scanf(%d,&choice);switch(choice)case 1:L=shuru(); /输入数据paixu(L); /数据排序break;case 2:if(L=NULL|L-last=-1) /查找前检验表中是否有数据printf(n顺序表为空nn);break;elseprintf(请输入要查找的数据：);scanf(%d,&data1);i=BinSrch(L,data1);printf(数据%d的序号(下标)是%d nn,data1,i);break;default:printf(n请输入正确的选择nn);break;case 0:break;while(choice!=0);return 0;实验四#include#include#define SIZE 15typedef structint dataSIZE;int last;RecordList;RecordList *shuru() /向顺序表中输入数据int s,i=0;RecordList *L;L=(RecordList *)malloc(sizeof(RecordList);printf(请输入要输入到顺序表中数据的数量：);scanf(%d,&s);if(s15)printf(超过最大的数据长度);elseprintf(请输入要输入的数据：);for(i=0;idatai);printf(成功输入%d个数据 nn,i);L-last=i-1;return L;void paixu(RecordList *L) /冒泡排序法对顺序表中的数据进行排序int x,change1=1,change2=1,i,j;for(i=0;change1!=0|change2!=0;i+)change1=0;change2=0;if(i%2=0)for(j=1;jlast;j=j+2)if(L-datajL-dataj+1)x=L-dataj+1;L-dataj+1=L-dataj;L-dataj=x;change1=1;elsefor(j=0;jlast;j=j+2)if(L-datajL-dataj+1)x=L-dataj+1;L-dataj+1=L-dataj;L-dataj=x;change2=1;void shuchu(RecordList *L)int i;for(i=0;ilast;i+)printf(%d ,L-datai);int main(void)RecordList *L=NULL;int choice;printf(1,输入数据2，冒泡排序3,输出0,退出n);doprintf(请输入选择：);scanf(%d,&choice);switch(choice)case 1:L=shuru(); /输入数据break;case 2:paixu(L); /数据排序printf(排序成功nn);break;case 3:shuchu(L);printf(n);break;default:printf(n请输入正确的选择nn);break;case 0:break;while(choice!=0);return 0;实验五#include#includetypedef struct node int data;struct node *next;LinkList;LinkList *CreatList()LinkList *head,*r,*s; /建立带头结点的链表，head为链表的头结点int n;head=(LinkList *)malloc(sizeof(LinkList);head-next=NULL;r=head; printf(请输入要输入的数据的个数:);scanf(%d,&n);printf(请输入要输入的数据:);for(int i=0;idata);s-next=NULL;r-next=s;r=s; /r指向链表的尾节点return head;void Add(LinkList *head,int x)LinkList *s,*r,*t;t=(LinkList *)malloc(sizeof(LinkList);r=head;s=head-next;for(;s!=NULL&x=s-data;s=s-next) /要寻找要插入节点的位置r=r-next;t-data=x;if(s=NULL) /插入在链表的表尾r-next=t;t-next=NULL;else /插入在链表的中间t-next=r-next;r-next=t;void Out(LinkList *head) /输出表中的数据LinkList *L;L=head-next;printf(表中的数据:);for(;L;L=L-next)printf(%d ,L-data);printf(n);int main(void)LinkList *head;int x;head=CreatList();Out(head);printf(请输入要插入的数据:);scanf(%d,&x);Add(head,x);Out(head);return 0;实验七#include#includetypedef struct nodeint data;struct node *next;LinkList;typedef structLinkList *rear;LinkQueue;LinkQueue *SetQueue() /建立空的队列LinkQueue *Q;LinkList *head;Q=(LinkQueue *)malloc(sizeof(LinkQueue);head=(LinkList *)malloc(sizeof(LinkQueue);head-data=-1;head-next=head;Q-rear=head;return Q;int QueueEmpty(LinkQueue *Q) /检验对列是否为空LinkList *p;p=Q-rear;if(p-data=-1)return 1;elsereturn 0;LinkQueue *Add(LinkQueue *Q,int x) /数据入队LinkList *p;p=(LinkList *)malloc(sizeof(LinkList);p-data=x;p-next=Q-rear-next;Q-rear-next=p;Q-rear=p;return Q;void Out(LinkQueue *Q) /数据出队LinkList *p1,*p2;p1=Q-rear;p2=Q-rear;p2=p2-next;p1=p2-next;if(p1-data=-1)printf(队列为空);return;printf(出队的数据是%dn,p1-data);p2-next=p1-next;LinkQueue *SetNull(LinkQueue *Q) /队列置空Q-rear=Q-rear-next;Q-rear-next=Q-rear;return Q;int main(void)LinkQueue *Q=NULL;int choice,x,i;printf(1，建立空队列2，数据入队3，数据出队4，置队空5，检验队空0,退出n);doprintf(n请输入选择:);scanf(%d,&choice);switch(choice)case 1:Q=SetQueue();printf(已建立空队列n);break;case 2:printf(请输入要入队的数据:);scanf(%d,&x);Q=Add(Q,x);break;case 3:Out(Q);break;case 4:Q=SetNull(Q);printf(队列已置空);break;case 5:i=QueueEmpty(Q);if(i=1)printf(队列为空n);elseprintf(队列未空n);break;case 0:break;while(choice!=0);return 0;实验八#include#define SIZE 100void zhuanzhi(int sa,int n) /转置函数int m,t;for(int i=0;i3*n-2;i+)if(i%3!=0)m=i+1;t=sai;sai=sam; /交换对称的两个数据sam=t;i+; /跳过矩阵的下三角数据/矩阵对角线上的数据不进行操作void JPrintf(int sa,int n) /输出函数int i,j;for(i=1;i=n;i+)for(j=1;j=n;j+)if(i=j-1|i=j|i=j+1) /i=j-1 对角线下方的元素 i=j对角线上的元素 i=j+1对角线上方的元素printf( %d,sa2*i+j-3);/非零元素在数据中的下标为 2*i+j-3elseprintf( 0);printf(n);int main(void)int n,saSIZE;printf(请输入三对角矩阵的阶数:);scanf(%d,&n);printf(请依次输入三对角矩阵中的非零数据:);for(int i=0;i3*n-2;i+) /三对角矩阵共有3*n-2g个非零元素scanf(%d,&sai);JPrintf(sa,n);zhuanzhi(sa,n);printf(转置后的矩阵：n);JPrintf(sa,n);return 0;实验九#include#include#define maxsize 10typedef struct nodechar data;struct node *lchild,*rchild;Bitree;Bitree *Qmaxsize; /使用队列临时记录节点地址Bitree *Creatree() /建立一个二叉树char ch;int front,rear;Bitree *T,*s;T=NULL;front=1;rear=0;printf(请输入一个二叉树(以#号结束):);ch=getchar();while(ch!=#) /以输入“#”结束输入s=NULL;if(ch!=) /输入“”表示虚节点s=(Bitree *)malloc(sizeof(Bitree); /如果不是虚节点就建立新节点s-data=ch;s-lchild=s-rchild=NULL;rear+;Qrear=s;if(rear=1) /输入的第一个节点为根节点T=s;elseif(s!=NULL&Qfront!=NULL)if(rear%2=0) /若rear为偶数则该节点为父节点的左孩子 ，否则为右孩子Qfront-lchild=s;elseQfront-rchild=s;if(rear%2=1) front+;ch=getchar();return T;void visite(Bitree *T,int *m)if(T-lchild=NULL&T-rchild=NULL) /没有左孩子也没有右孩子就是叶子节点(*m)+;void Preorder(Bitree *T,int *m) /使用递归遍历二叉树if(T)visite(T,m); /访问根节点Preorder(T-lchild,m);Preorder(T-rchild,m);int main(void)int *m,n=0;m=&n; /使用一个指针用于记录叶子节点的个数Bitree *T;T=Creatree();Preorder(T,m);printf(该二叉树的叶子节点数：%dn,n);return 0;实验十#include#include#define maxsize 10typedef struct nodechar data;struct node *lchild,*rchild;Bitree;Bitree *Qmaxsize; /使用队列临时记录节点地址Bitree *Creatree() /建立一个二叉树char ch;int front,rear;Bitree *T,*s;T=NULL;front=1;rear=0;printf(请输入一个二叉树(以#号结束):);ch=getchar();while(ch!=#) /以输入“#”结束输入s=NULL;if(ch!=) /输入“”表示虚节点s=(Bitree *)malloc(sizeof(Bitree); /如果不是虚节点就建立新节点s-data=ch;s-lchild=s-rchild=NULL;rear+;Qrear=s;if(rear=1) /输入的第一个节点为根节点T=s;elseif(s!=NULL&Qfront!=NULL)if(rear%2=0) /若rear为偶数则该节点为父节点的左孩子 ，否则为右孩子Qfront-lchild=s;elseQfront-rchild=s;if(rear%2=1) front+;ch=getchar();return T;void visite(Bitree *T,char m) /把中序遍历的数据保存到数据m中int i=0;while(mi!=*) / * 是数组的结束标志i+;mi=T-data;mi+1=*;void Inorder(Bitree *T,char m) /中序遍历递归算法if(T)Inorder(T-lchild,m);visite(T,m);Inorder(T-rchild,m);int Pan(char m) int i=0,j=0; /j=0是表示是二叉树while(mi+1!=*)if(mimi+1) j=1; /j=1是表示不是二叉树break;i+;return j;int main(void)Bitree *T;int j;T=Creatree();char m50;m0=*;Inorder(T,m);j=Pan(m);if(j=1)printf(该二叉树不是二叉排序树n);elseprintf(该二叉树是二叉排序树n);return 0;实验十一#include#include#include#define MAX_VERTEX_NUM 100/* 临接表的数据类型定义 */typedef struct nodeint adjvex;/邻接点位置struct node *nextarc;/指向下一个结点char info;/边得信息ARCNODE;typedef struct VEXNODEchar vexdata;/顶点信息ARCNODE *firstarc;/指向第一个邻接点VEXNODE,AdjListMAX_VERTEX_NUM;typedef struct/邻接表类型AdjList vextices;int vexnum,arcnum;/顶点数目，边数目ALGraph;ALGraph create_AdjListGraph()/建立邻接表int n,e,i,j,k;ALGraph alg;ARCNODE *p,*q;printf(请输入顶点数:);scanf(%d,&n);for(i=0;i=n;i+)/初始化邻接表alg.vexticesi.vexdata=(char)i;alg.vexticesi.firstarc=NULL;printf(请输入边数:);scanf(%d,&e);printf(请输入图的信息：n);for(i=0;iadjvex=k;p-info= ;p-nextarc=alg.vexticesj.firstarc; /把节点接到链表上alg.vexticesj.firstarc=p;q=(ARCNODE *)malloc(sizeof(ARCNODE);q-adjvex=j;q-info= ;q-nextarc=alg.vexticesk.firstarc;/把节点接到链表上alg.vexticesk.firstarc=q;alg.vexnum=n;alg.arcnum=e;return alg;/* 邻接矩阵的数据类型定义 */typedef structint num;/顶点序号char data;/顶点数据VERTEX;typedef struct/邻接矩阵类型int n;/顶点数目int e;/边的数目VERTEX vexsMAX_VERTEX_NUM; /存储顶点int edgesMAX_VERTEX_NUMMAX_VERTEX_NUM;/邻接矩阵，存储边MGraph;MGraph *ALG_MG(ALGraph alg)/邻接表转化为邻接矩阵MGraph *mg;ARCNODE *arc;mg=(MGraph *)malloc(sizeof(MGraph);mg-n=alg.vexnum;mg-e=alg.arcnum;int i,j;for(i=0;i=alg.vexnum;i+)/初始化邻接矩阵for(j=0;jedgesij=0;for(i=1;ivexsi.num=i;/依次从邻接表中把顶点信息读入到邻接矩阵中mg-vexsi.data=alg.vexticesi.vexdata;arc=alg.vexticesi.firstarc;for(;arc!=NULL;arc=arc-nextarc) /从邻接表中把边得信息读入到邻接矩阵中mg-edgesiarc-adjvex=1;return mg;void Palg(ALGraph G)/输出邻接表int i,j; ARCNODE *p;printf(输出图为:n); for(i=1;iadjvex);p=p-nextarc;j=1;if(j=1)coutendl;void Pmg(MGraph *mg)/输出邻接矩阵for(int i=1;in;i+) /遍历邻接矩阵for(int j=1;jn;j+)printf(%d ,mg-edgesij);printf(n);int main(void)ALGraph alg;MGraph *mg;alg=create_AdjListGraph();Palg(alg);mg=ALG_MG(alg);printf(转化为邻接矩阵为:n); Pmg(mg);return 0;实验十二#include#include#define MAX 50typedef struct /学生信息结构char name20;char id10;int age;char address20;char tel15;PersonInfo;typedef struct/班级信息结构PersonInfo personMAX;char classid10;int count;ClassInfo;int xCinfo(ClassInfo Cinfo)/寻找班级号对应的下标char cid10;printf(请输入班级号:);scanf(%s,cid);strcpy(Cinfo0.classid,cid);for(int i=1;Cinfoi.count0;i+);i-;for(;i0;i-)if(strcmp(Cinfoi.classid,cid)=0)break;if(i=0)printf(不存在该班级n);return -1;elsereturn i;void inSinfo(ClassInfo Cinfo)PersonInfo si;int i;i=xCinfo(Cinfo);if(i=-1)return;printf(请输入学生姓名:);scanf(%s,);printf(请输入学生学号:);scanf(%s,si.id);printf(请输入学生年龄:);scanf(%d,&si.age);printf(请输入学生宿舍号:);scanf(%s,si.address);printf(请输入学生电话:);scanf(%s,si.tel);for(int j=1;Cinfoi.personj.age0;j+);Cinfoi.personj=si;Cinfoi.personj+1.age=-1;Cinfoi.count+;printf(信息已插入n);void CreateClass(ClassInfo Cinfo)/建立班级ClassInfo ci;printf(请输入班号:);scanf(%s,ci.classid);printf(请输入班级成员总数:);scanf(%d,&ci.count);for(int i=1;Cinfoi.count0;i+);Cinfoi=ci;for(int j=1;j0;j-)if(strcmp(Cinfoi.personj.id,sid)=0)break;if(j=0)printf(不存在该学号的学生);return -1;elsereturn j;void OutSinfo(ClassInfo Cinfo)/输入学生的信息int i;i=xCinfo(Cinfo);if(i=-1)return;int j;j=xSinfo(Cinfo,i);if(j=-1)return;elseprintf(该学生的信息:n);printf(学号:%sn,Cinfoi.personj.id);printf(姓名:%sn,C);printf(年龄:%dn,&Cinfoi.personj.age);printf(宿舍:%sn,Cinfoi.personj.address);printf(电话:%sn,Cinfoi.personj.