软件基础设计报告学院：电气信息工程学院班级：电科1102班姓名：许波益学号：3110504052实验一在交互方式下完成下列任务：1、建立单向链表，表长任意；2、可交互输出单链表中的内容；3、编写算法计算出自己所建单链表的长度并输出；4、删除自己所建单链表中的第K个结点，并将剩余结点输出；5、将单链表倒排，输出结果。

源代码：#include<stdio.h>#include<stdlib.h>struct LinkList{int data;struct LinkList *next;};struct LinkList *CreatLList(){struct LinkList * H=NULL,*p,*q;int x;q=NULL;printf("输入一个数（-1结束）：");scanf("%d",&x);while(x!=-1) {p=(struct LinkList *)malloc(sizeof(struct LinkList));p->data=x;if(H==NULL) H=p;else q->next=p;q=p;printf("继续输入：");scanf("%d",&x);}if(q!=NULL) q->next=NULL;return(H);}void Outputlist(struct LinkList *Head){ struct LinkList *H;H=Head;printf("链表是：\n");while (H!=NULL){ printf("%d ",H->data);H=H->next;}printf("\n");}LengthLList(struct LinkList *L){int Length=0;struct LinkList *p=L;while(p!=NULL){p=p->next;Length++;}return Length;}void DeleteLList(struct LinkList *L){int a;struct LinkList *p,*s;printf("输入要删除的数：");scanf("%d",&a);if(L->next==NULL) return ;p=L;s=p;while((p->next!=NULL)&&(p->data!=a)){s=p;p=p->next;}if(p==NULL) { printf("链表中无此数\n");return ; } s->next=p->next;free(p);printf("已删除\n");return ;}struct LinkList *NIXU(struct LinkList *h){struct LinkList *p,*r,*s;r=h;p=r->next;s=p->next;if(h==NULL) printf("空链表\n");while(s!=NULL&&h!=NULL){p->next=r;r=p;p=s;s=s->next;}h->next=NULL;p->next=r;return p;}void main(){int a;struct LinkList *head;while(1){ printf("功能：\n");printf("1:建立链表\n");printf("2:输出链表\n");printf("3:计算链表长度\n");printf("4:删除链表结点\n");printf("5:链表逆序\n");printf("6:退出\n");printf("输入功能:");scanf("%d",&a);if(a<=6&&a>=1){switch(a){ case 1: head=CreatLList();break;case 2:Outputlist(head);break;case 3: printf("链表长度是: %d\n",LengthLList(head));break;case 4:DeleteLList(head);break;case 5:head=NIXU(head);break;case 6:exit(0); break;default:break;}}else {printf("错误的功能号码\n");}}}实验二在交互方式下完成下列任务：1、动态交互建立二叉树，结点个数任意；2、分别用DLR、LDR、LRD三种方式对二叉树进行便利并输出结果；3、计算二叉树中的结点个数并输出；4、计算二叉树的深度并输出；源代码：# include "stdio.h"# include "malloc.h"struct BTNode{int data;struct BTNode *Lchild,*Rchild;};struct BTNode *build(struct BTNode *p);struct BTNode *creatrent(struct BTNode *p);void DLR(struct BTNode *T);struct BTNode *creatrent(struct BTNode *p){int x;printf("输入根：rent=");scanf("%d",&x);if(x==1000) {p=NULL;}else{p->data=x;p->Lchild=(struct BTNode *)malloc(sizeof(struct BTNode));p->Rchild=(struct BTNode *)malloc(sizeof(struct BTNode));if(p==NULL) return p;p->Lchild=build(p->Lchild);p->Rchild=build(p->Rchild);return p;}}struct BTNode *build(struct BTNode *p){int x;printf("输入数据(输入值为时999，表示该结点为空)：value=");scanf("%d",&x);if(x==999) {p=NULL;}else{p->data=x;p->Lchild=(struct BTNode *)malloc(sizeof(struct BTNode));p->Rchild=(struct BTNode *)malloc(sizeof(struct BTNode)); }if(p==NULL) return p;p->Lchild=build(p->Lchild);p->Rchild=build(p->Rchild);return p;}void DLR(struct BTNode *T){if(T==NULL) return;printf("%d ",T->data);DLR(T->Lchild);DLR(T->Rchild);}void LDR(struct BTNode *T){if(T==NULL) return;LDR(T->Lchild);printf("%d ",T->data);LDR(T->Rchild);}void LRD(struct BTNode *T){if(T==NULL) return;LRD(T->Lchild);LRD(T->Rchild);printf("%d ",T->data);}void main(){struct BTNode *rent=NULL;int flag;while(1){printf("选择输入的操作：\n1：创建；\n2：先序；\n 3：中序;\n4：后序\n");scanf("%d",&flag);switch(flag){case 1:rent=(struct BTNode *)malloc(sizeof(struct BTNode));rent=creatrent(rent);break;case 2:DLR(rent);printf("\n");break;case 3:LDR(rent);printf("\n");break;case 4:LRD(rent);printf("\n");break;}}}实验三在交互方式下完成下列任务：1、根据教材上算法，完成图的深度和广度优先遍历，要求任意给定起始点，输出结果；2、根据教材上算法，完成图的单源最短路径的算法，要求任意给定源点，输出结果；源代码：#include <stdio.h>#include <malloc.h>#define K 1000#define VNum 6struct GLink{ int No;int Right;struct GLink *Relat;};int G[VNum][VNum] = // 初始化 //{0, 50, 10, K, 45, K,K, 0, 15, 50, 10, K,20, K, 0, 15, K, K,K, 20, K, 0, 35, K,K, K, K, 30, 0, K,K, K, K, 3, K, 0};struct GLink *GL[VNum];int Visited[VNum];void CreateGLink(int G[VNum][VNum]) // 建立邻接表 //{ int i,j;struct GLink *p,*q;for (i=0; i<VNum; i++){ GL[i] = q = NULL;for (j=0; j<VNum; j++){ if (i != j)if ((G[i][j] > 0) &&(G[i][j] < K))// 该两点存在有向路径 //{ p = (structGLink *)malloc(sizeof(struct GLink));p->No = j;// 将该点加入邻接表 //p->Right =G[i][j];if (GL[i] ==NULL)GL[i]= p;elseq->Relat = p;q = p;}}}}void DFS(int A[VNum][VNum], int V) // 用于进行深度优先遍历的子函数，V是起点//{ int i;printf(" [%d] ", V);Visited[V] = 1; // 将其标记为已访问//for (i = 0; i < VNum; i++)if ((A[V][i] > 0) && (A[V][i] < K) && (Visited[i] != 1))// 该结点未被访问过 //DFS(A,i);// 访问该点 //for (i = 0; i < VNum; i++)if (Visited[i] != 1) DFS(A,i); // 仍有未必访问过的点，访问该点 //}void BFS(int A[VNum][VNum], int V) // 广度优先遍历的子函数 // { int CQ[VNum];int a=0,b,c;int i,k=1;for (i=0;i<VNum;i++)CQ[i]=K;Visited[V] = 1; // 标志为访问过 //CQ[0]=V;printf("[%d] ",V); // 将该结点放入队列 //while(k<6&&a<k) // 仍有结点未被访问并且队列中仍有结点的后继结点未被访问//{ b=CQ[a];for(c=0;c<VNum;c++) // 依次将队列中以结点为首的邻接表中的结点插入队列//if(Visited[c]==0&&A[b][c]<K&&A[b][c]!=0){ printf("[%d] ", c);CQ[++k]=c; // 未被访问过，将其插入到队列中//Visited[c]=1; // 标志为访问过 //}a++;}for(i=0;i<VNum;i++)if(Visited[i]==0)BFS(A,i);}void Short(int A[VNum][VNum],int V) // 用于计算最短路径的子函数，V是起点//{ int Dist[VNum], Path[VNum];int S = 0;int i, k;int wm, u;for (i=0; i<VNum; i++){ Dist[i] = A[V][i];// 默认这两点之间即为最短路径 //if (Dist[i] < K) Path[i] = V;// 存储该路径 //}S = S | (1 << V);for (k=0; k<VNum; k++){ wm = K;u = V;for (i=0; i<VNum; i++)if (((S & (1 << i))==0) && (Dist[i] < wm))// 该两点间存在路径 //{ u = i;wm = Dist[i];}S = S | (1 << u);for (i=0; i<VNum; i++)if (((S & (1 << i))==0) && ((Dist[u] + A[u][i]) <Dist[i])){ Dist[i] = Dist[u] + A[u][i];// 找到新的最短路径 //Path[i] = u;// 更新路径长度 //}}for (i=0; i<VNum; i++) // 输出该源结点到其他各点的最短路径//if ((S & (1 << i)) != 0){ k = i;while ( k != V){ printf(" %d <- ", k);k = Path[k];}printf(" %d ", V);printf(" = %d \n", Dist[i]);}else printf(" No Path : %d",i);}main(){ int i,j,a,b;//a为功能号，i用作循环，j，b为函数参数CreateGLink(G);printf("1.深度查找\n"); //功能选择 //printf("2.广度查找\n");printf("3.最短路径\n");printf("4.退出exit\n");while(1) { printf("\n please input a num from 1 to 4 : ");scanf("%d",&a);if(a==1) //深度查找{ for (i=0; i<VNum; i++)Visited[i] = 0;printf("please input the first node: ");scanf("%d",&j);printf("\n The result of DFS is:");DFS(G,j);printf("\n");}if(a==2) //广度查找{ for (i=0; i<VNum; i++)Visited[i] = 0;printf("please input the first node: ");scanf("%d",&j);printf("\n The result of BFS is:");BFS(G,j);printf("\n");}if(a==3) //最短路径{ printf("please input the source node : ");scanf("%d",&b);printf("\n The result of shortest path is:\n"); Short(G,b);}if(a==4) break;}}实验四在交互方式下完成下类任务：1、任意给定无序系列，用快速排序法对其进行排序，并统计交换次数。