实验目的实验一1掌握线性表的实现。2掌握线性表的应用。实验二1掌握栈和队列的实现。2掌握栈和队列的应用。实验三掌握二叉树的实现。掌握二叉树的应用。实验四掌握图结构的实现。掌握图结构的应用实验内容与实验步骤2.1线性表的应用(1)我选定了题目一学生信息的录入。(2)定义存储结构typedef struct Node {double data;char subject[30];struct Node * next;}Node;data储存分数subject储存科目名称。基本操作a.初始化链表操作initList()创建一个带头节点的空表并返回表头b.往链表里添加元素操作addGrade(Node* list,double score,char subject[30])将分数为score的subject插入链表里c.遍历链表printList(Node* list)输出链表里所有科目及对应成绩d.寻找最高分maxScore(Node* list)和寻找最低分minScore(Node* list)找到分别找到最高分和最低分并输出分数及所属科目e.删除科目deleteSubject(Node* list,char* name)找到并删除名为name的科目及对应分数f.求平均分averageScore(Node* list)求出平均分并输出。2.2栈和队列的应用我选择算术表达式求值利用栈实现一个中缀表达式的求值定义存储结构typedef struct OPNumber{//操作数栈存放操作数int data;struct OPNumber* next;}OPNumber;typedef struct OPChar {//操作符栈存放操作符char opChar;struct OPChar* next;}OPChar基本操作初始化操作数栈initNumberStack()初始化操作符栈 initCharStack()判断栈空isNumberStackEmpty()isCharStackEmpty();入栈pushNumberStack(),pushCharStack()采用头插法入栈出栈时只需弹出头节点地下一节点即可出栈popNumberStack(),popCharStack();获取栈顶getTopOfCharStack(),getTopOfNumberStack();输入get_input();计算evaluate_expression()。2.3 二叉树的应用(1)存储结构孩子链表和二叉链表typedef struct Children {//孩子在邻接表的位置(头节点的index为链表里节点数量)int index;//后继结点struct Children* next;}Children;typedef struct CTBox {//节点在的邻接表位置int index;int perant;//数据域char name[30];int sum;//孩子链表Children* childrenList;}CTBox;typedef struct BNode {char name[30] ;int sum;struct BNode* offspring;//左子树struct BNode* sibling;//右子树}BNode;2操作创建树initTree先根遍历preRootTravel();后根遍历lastRootTravel();初始化二叉树initBTree();把树转化为二叉树toBTree();二叉树的先序、中序、后序遍历preOrder(),midOrder(),lastOrder();读取queries.txt的查询并给出回答操作getAnswer();2.4 图结构的应用1存储结构邻接表typedef struct EBox {//边int distance;//距离int cost;//费用int toVex;//终点顶点位置struct EBox* nextEdge;//下一条边}EBox;typedef struct VexBox {//结点char name[15];struct EBox* firstEdge;//第一条出边}VexBox;typedef struct Graph {//图int edgeNum, vexNum;//边数和结点数VexBox AdjList[MAX];//邻接数组}Graph;2基本操作初始化图initGraph();添加结点间的关系addVexAndEdge();深度优先遍历DFS();广度优先遍历BFS();获取最短路径shortestRoute();实验环境操作系统、调试软件名称、版本号上机地点机器台号操作系统windows11 64位操作系统调试软件visual studio2019 4.8.04161实验过程与分析实验一实验过程1初始化链表Node* initList() {Node* head (Node*)malloc(sizeof(Node));head-next NULL;head-data 0;strcpy(head-subject, 表头);return head;}头节点data域存放链表的元素个数便于在平均数求取时得到科目数量。2插入节点void addGrade(Node* list, double score, char subjectName[30]) {Node* node (Node*)malloc(sizeof(Node));node-data score;strcpy(node-subject, subjectName);node-next list-next;list-next node;list-data;}采用头插法插入结点每添加一个元素头节点data加一。3输出链表内容void printList(Node* list) {Node* node list-next;printf(成绩如下\n);printf(\n科目\t成绩\n);while (node) {printf(%s\t%.2f\n, node-subject, node-data);node node-next;}}4计算最高分void maxScore(Node* list) {Node* node list-next;Node* maxNode node;while (node) {if (node-data maxNode-data) {maxNode node;}node node-next;}printf(\n最高分\n);printf(%s\t%.2f\n, maxNode-subject, maxNode-data);}找到最低分的科目并输出其科目名称及分数5计算最低分void minScore(Node* list) {Node* node list-next;Node* minNode node;while (node) {if (node-data minNode-data) {minNode node;}node node-next;}printf(\n最低分\n);printf(%s\t%.2f\n, minNode-subject, minNode-data);}找出最低分的科目并输出科目名称和分数6删除科目void deleteSubject(Node* list, char* name) {Node* p list;Node* node p-next;while (node) {if (strcmp(node-subject, name) 0) {p-next node-next;free(node);printf(\n删除成功\n);return;}p node;node node-next;}printf(\n删除失败\n);}输入科目名称在链表中找到并删除科目名称为输入值的结点7计算平均分void averageScore(Node* list) {double sum 0;Node* node list-next;while (node) {sum node-data;node node-next;}printf(\n平均分);printf(%.2f\n, sum / list-data);}测试用例用例编号用例输入预计输出实际输出测试结果评估1语文 100数学 99英语 98化学 50生物 78语文 100数学 99英语 98化学 50生物 78最高分语文 100最低分化学 50平均分85.00输出结果符合预期2删除语文数学 99英语 98化学 50生物 78最高分数学 99最低分化学 50平均分81.25结果符合预期3语文 99.99数学 98.99英语 59.9历史 100语文 99.99数学 98.99英语 59.9历史 100最高分历史 100最低分英语 59.9平均分89.72结果符合预期4删除历史语文 99.99数学 98.99英语 59.9最高分语文 99.99最低分英语 59.9平均分86.29结果符合预期实验二实验过程初始化栈此为初始化操作数栈OPNumber * initNumberStack() {OPNumber* numberStack (OPNumber*)malloc(sizeof(OPNumber));numberStack-data 0;numberStack-next NULL;return numberStack;}创建一个带头结点地链式栈并返回头节点初始化操作符栈类似。判断栈空此为操作数栈int isNumberStackEmpty(OPNumber* stack) {if (stack-next)return 0;elsereturn 1;}栈为空返回1否则返回0操作符栈判断方法一样。入栈以操作数入栈为例void pushNumberStack(OPNumber* stack, int number) {OPNumber* node (OPNumber*)malloc(sizeof(OPNumber));node-data number;node-next stack-next;stack-next node;}使用头插法入栈操作符入栈与此类似出栈以操作数出栈为例int popNumberStack(OPNumber* stack) {if (!isNumberStackEmpty(stack)) {OPNumber* node stack-next;int number stack-next-data;stack-next stack-next-next;free(node);return number;}elseprintf(操作符栈为空\n);}栈不为空则弹出第一个结点否则出栈失败操作符出栈与此类似获取栈顶char getTopOfCharStack(OPChar* stack) {if (!isCharStackEmpty(stack)) {return stack-next-opChar;}elseprintf(栈为空\n);}得到栈顶元素用于比较运算符优先级和计算获取输入int get_input(int* n){*n 0;char ch getchar();if (!isdigit(ch)){*n ch;getchar();return true;}do{*n (*n) * 10 (ch - 0);ch getchar();} while (ch ! \n);return false;}依次获取从控制台输入的字符计算int evaluate_expression(OPNumber* numberStack,OPChar* charStack) {/* 输入元素 */int* element (int*)malloc(sizeof(int));/* 输入元素类型* type true表示输入为运算符* type false表示输入为运算数*/int type;/* 出栈元素 */int* x (int*)malloc(sizeof(*x));/* 运算出栈元素 */int* theta (int*)malloc(sizeof(int));int* a (int*)malloc(sizeof(int));int* b (int*)malloc(sizeof(int));pushCharStack(charStack, #);type get_input(element);*x #;while (*element ! # || *x ! #){/* 输入不是运算符 */if (!type){//操作数入栈pushNumberStack(numberStack, *element);type get_input(element);}else{*x getTopOfCharStack(charStack);switch (precmp(*x, *element)){case :pushCharStack(charStack, *element);type get_input(element);*x getTopOfCharStack(charStack);break;case :*x popCharStack(charStack);type get_input(element);break;case :*theta popCharStack(charStack);*b popNumberStack(numberStack);*a popNumberStack(numberStack);pushNumberStack(numberStack, compute(*a, *theta, *b));*x getTopOfCharStack(charStack);break;}}}*x getTopOfNumberStack(numberStack);free(element);free(a);free(b);free(theta);return *x;}测试用例用例编号测试输入预计输出实际输出结果评估1141630结果符合预期21416*390结果符合预期31415*9/42893.25由于程序的数据类型为int所以小数位被舍去实验结果较符合预期实验三实验过程初始化树void initTree(CTBox* Tree, char info[][3][30],char buildings[][30],int* many) {for (int i 0; i Max; i) {Tree[i].index i;strcpy(Tree[i].name, buildings[i]);Tree[i].sum *(many i);Tree[i].childrenList initChildrenList();}Tree[0].perant -1;//根节点无父节点for (int i 0; i 17; i) {int parent -1;for (int j 1; j Max; j) {if (strcmp(info[i][2], Tree[j].name) 0) {//儿子for (int k 0; k Max; k) {if (strcmp(info[i][0], Tree[k].name) 0) {//父亲Tree[j].perant k;addChild(Tree[k].childrenList, j);}}}}}}info为一个通过读取definition.txt构建的二维字符串数组存储了医院各个建筑的名称、每个建筑数量及其之间的关系buildings字符串数组存储了医院的所有不重复建筑名称many数组为对应的数量。树的先根遍历void preRootTravel(CTBox* Tree,CTBox* Root) {//先根遍历printf(\t%-30s%d\n, Root-name,Root-sum);Children* node Root-childrenList-next;while (node) {preRootTravel(Tree, Tree[node-index]);node node-next;}}先根遍历树的结点及其数量树的后根遍历void lastRootTravel(CTBox* Tree, CTBox* Root) {//后根遍历Children* node Root-childrenList-next;while (node) {lastRootTravel(Tree, Tree[node-index]);node node-next;}printf(\t%-30s%d\n, Root-name,Root-sum);}后根遍历树的结点及其数量初始化二叉树BNode* initBTree(CTBox* Tree) {BNode* BTree (BNode*)malloc(sizeof(BNode));BTree-offspring NULL;BTree-sibling NULL;toBTree(Tree, BTree, Tree[0]);return BTree;}Tree为一个多叉树调用toBTree方法后将其转为二叉树并返回根节点地址把多叉树转二叉树int toBTree(CTBox* Tree,BNode* BTree,CTBox root) {//多叉树转二叉树int i 0;BNode* ptemp;strcpy(BTree-name, root.name);BTree-sum root.sum;if (root.childrenList-next NULL) {BTree-offspring NULL;return 0;}BNode* pbnode (BNode*)malloc(sizeof(BNode));BTree-offspring pbnode;toBTree(Tree, pbnode, Tree[root.childrenList-next-index]);//处理左子树i 1;ptemp pbnode;Children* node root.childrenList-next-next;while (i root.childrenList-index node ! NULL) {BNode* pbnode (BNode*)malloc(sizeof(BNode));ptemp-sibling pbnode;ptemp pbnode;toBTree(Tree, pbnode, Tree[node-index]);//处理右子树i;node node-next;}ptemp-sibling NULL;return 0;}传入一棵二叉树的根和一个多叉树以及多叉树根通过递归将其转为二叉树多叉树的第一个孩子变成二叉树左子树第二个孩子作为第一个孩子的右子树以此类推兄弟变右孩子直到所有子树都变为二叉树为止。6二叉树遍历以前序遍历为例中后序遍历仅访问结点语句位置不同void preOrder(BNode* BTree) {//先序遍历if (BTree ! NULL) {printf(\t%-30s%d\n, BTree-name,BTree-sum);preOrder(BTree-offspring);preOrder(BTree-sibling);}else {return;}}7读取queries.txt的查询并给出回答void getAnswer(char* questionsFile,CTBox Tree[]) {//读取问题并获得答案char question[13][4][30];FILE* fp;char line[100];if ((fp fopen(questionsFile, r)) NULL) {printf(Error\n);return -1;}for (int i 0; i 13;i) {for (int j 0; j 4; j) {strcpy(question[i][j], );}}int index 0;while (!feof(fp) index 13) {//将文件内容读取到info数组里fgets(line, 100, fp);int t strlen(line);//逐行读取存入line里if (line[t - 1] \n) {//吃掉\nline[t - 1] 0;}char* str2 strtok(line, );//对line以 作为分隔符分割int j 0;while (j 4 str2 ! NULL) {strcpy(question[index][j], str2);str2 strtok(NULL, );j;}index;}fclose(fp);answer(question, Tree);}void answer(char question[][4][30], CTBox* Tree) {//获取答案int sum 0;for (int i 0; i 13; i) {if (strcmp(question[i][0], what) 0) {for (int j 0; j Max; j) {if (strcmp(question[i][2], Tree[j].name) 0) {printf(\n\t(%d)Part %s subparts are:\n,i 1,Tree[j].name);Children* node Tree[j].childrenList-next;while (node) {printf(\t\t%d %s\n, Tree[node-index].sum, Tree[node-index].name);node node-next;}}}}if (strcmp(question[i][0], how) 0) {for (int j 0; j Max; j) {if (strcmp(question[i][2], Tree[j].name) 0) {//孩子for (int k 0; k j; k) {if (strcmp(question[i][3], Tree[k].name) 0) {//父亲sum getSum(Tree[k], Tree[j], Tree);printf(\n\t(%d)%s has %d %s\n,i 1,Tree[k].name, sum, Tree[j].name);break;}}}}}}}运行结果实验四实验过程初始化图生成孤立结点Graph* initGraph(char cities[][15]) {//初始化邻接数组Graph* graph (Graph*)malloc(sizeof(Graph));graph-edgeNum 0;graph-vexNum MAX;for (int i 0; i MAX; i) {strcpy(graph-AdjList[i].name, cities[i]);graph-AdjList[i].firstEdge initEdgeList();}return graph;}cities为存储城市名称的数组将其依次赋值给结点的name域建立结点间的关系添加边void addVexAndEdge(Graph* graph,char info[][4][15],char cities[][15]) {for (int i 0; i 54; i) {int start -1;int end -1;for (int j 0; j MAX; j) {if (strcmp(graph-AdjList[j].name, info[i][0]) 0) {//起点start j;}if (strcmp(graph-AdjList[j].name, info[i][1]) 0) {//终点end j;}}int cost atoi(info[i][2]);int distance atoi(info[i][3]);addEdge(graph-AdjList[start].firstEdge, cost, distance, end);graph-edgeNum;}}info为存储结点名称、结点间关系和边的权值的数组cities为存储城市名称的数组深度优先遍历void DFS(Graph* graph,int* isvisted,int* index) {//深度遍历连通的19个城市if (isvisted[*index] ! 0) {return;}printf(\t\t%s\n, graph-AdjList[*index].name);isvisted[*index] 1;EBox* node graph-AdjList[*index].firstEdge-nextEdge;while (node) {*index node-toVex;DFS(graph, isvisted, index);node node-nextEdge;}}void DFSAll(Graph* graph,int* visited) {//深度遍历所有城市int order 0;DFS(graph, visited, order);EBox* node graph-AdjList[20].firstEdge-nextEdge;while (node) {//遍历孤立的两个城市printf(\n\t\t%s\n, graph-AdjList[20].name);visited[20] 1;printf(\t\t%s\n, graph-AdjList[node-toVex].name);visited[node-toVex] 1;node node-nextEdge;}}采用递归对每个城市深度优先遍历广度优先遍历void BFS(Graph* graph, int* visited,int index,Queue* Q) {//广度优先遍历一个点printf(\t\t%s\n, graph-AdjList[index].name);//访问节点visited[index] 1;inQueue(Q, graph-AdjList[index]);//节点入队EBox* p;while (!isEmpty(Q)) {p graph-AdjList[index].firstEdge-nextEdge;deQueue(Q);//节点出队while (p) {if (visited[p-toVex] 0) {printf(\t\t%s\n, graph-AdjList[p-toVex].name);visited[p-toVex] 1;inQueue(Q, graph-AdjList[p-toVex]);//入队相关结点}p p-nextEdge;}}}建立辅助数组visited记录结点是否被访问过假设对结点i进行广度优先遍历则先访问结点i将结点i入队再将visited[i]标记为true,然后弹出队首访问i能直接到达且还未被访问过的结点入队然后修改visited相应的元素。void BFSAll(Graph* graph,int* visited) {//广度优先遍历所有结点for (int i 0; i 22; i) {visited[i] 0;}Queue* Q initQueue();for (int i 0; i graph-vexNum; i) {if (visited[i] 0) {if (i 20) {printf(\n);}BFS(graph, visited, i, Q);}}}对所有违背访问过的结点进行广度优先遍历。获取最短路径采用迪杰斯特拉算法void DJ(Graph* graph, int dist[],int distance[], int path[], int v) {//迪杰斯特拉算法,v为起点索引int set[MAX];//1为已找到最短路径0为未找到int i, j, u, min;int cost;for ( i 0; i graph-vexNum; i) {set[i] 0;path[i] -1;dist[i] 9999;distance[i] 9999;}EBox* p graph-AdjList[v].firstEdge-nextEdge;while (p) {dist[p-toVex] p-cost;distance[p-toVex] p-distance;path[p-toVex] v;p p-nextEdge;}path[v] -1;set[v] 1;dist[v] 0;distance[v] 0;for (i 0; i graph-vexNum; i) {min 9999;for (j 0; j graph-vexNum; j) {if (set[j] 0 dist[j] min) {min dist[j];u j;}}set[u] 1;for (j 0; j graph-vexNum; j) {int cost getCost(graph, u, j);if (set[j] 0 dist[u] cost dist[j]) {dist[j] dist[u] cost;distance[j] getDistance(graph, u, j) distance[u];path[j] u;}}}}1.初始化。V为G中所有顶点集合path{v}。dist[x]表示从源点到x的已知路径的权值初始dist[v]为0其余为无穷大。2.从源点v开始运行一步广度优先算法即找其相邻点。3.计算可见点到源点v的路径长度更新dist[x]。然后对路径进行排序选择最短的一条作为确定找到的最短路径将其终点加入到path中.4.从path中选择新加入的点运行广度优先算法找其相邻点重复step3。直至所有点已加入S或者再搜索不到新的可见点图中存在不联通的点此时pathV终止算法。void printPath(Graph* graph,int path[], int v1) {//v1为终点索引,从终点往前打印路径if (path[v1] -1) {printf(%s, graph-AdjList[v1].name);}else {printPath(graph,path, path[v1]);//v1变为v1的前驱printf(---%s, graph-AdjList[v1].name);}}打印从起点v到终点v1的路径void shortestRoute(Graph* graph) {char start[30];char end[30];int dist[MAX], path[MAX], distance[MAX];//dist存储每条最短路径的花费总和path[i]存储索引为i的城市的的前驱结点索引distance存储每条最短路径的路程总和printf(\n请输入起点和终点用空格隔开:\n);scanf(%s %s, start,end);int v0 getLocation(graph, start);int v getLocation(graph, end);if (v0 ! -1 v ! -1) {DJ(graph, dist, distance, path, v0);if (dist[v] ! 9999) {printf(\n%s到%s费用最少的路线\n, start, end);printf(花费%d距离为%d公里\n, dist[v], distance[v]);printf(\n路线为\n);printPath(graph, path, v);printf(\n);}else {printf(\n%s到%s不连通所以无最短路径\n, start, end);}}else {printf(\n未找到此城市\n);}}输入起始点并输出其最短路径权值总和和最短路径。遍历运行结果测试用例编号输入预计输出实际输出实验结果评估1London Lisbon花费245距离为3000公里London--Paris--Bern--Madrid--Lisbon结果符合预期2LondonLondon花费0距离为0公里London符合预期3LisbonBucharest花费165距离4550公里Lisbon--Madrid--Bern--Sarajevo--Budapest--Bucharest符合预期4LisbonBelfast不连通无最短路径符合预期实验结果总结对每个实验分别进行测试总结实验一链表不要求在创建时就确定链表长度所以适合在不确定数据地数量时使用但是链表不能根据索引直接找到某个结点而要从头开始找因此链表的插入和删除效率比较低当数据量比较大而且要频繁地查找和删除数据时不推荐使用。实验二用栈来进行表达式求值的难点在于判断操作符的优先级在该实验中设置一个操作符数组用于获取运算符优先级。/* 存储运算符和界限符 */char OP[7] { , -, *, /, (, ), # };/* OP的优先级表 */char pre[][7] {{, , , , , , },{, , , , , , },{, , , , , , },{, , , , , , },{, , , , , , 0},{, , , , 0, , },{, , , , , 0, }};-*/#-*/#如下图所示a为当前读取的操作符b为当前操作符栈顶元素ab a的优先权高于,a不入栈操作数出栈与a后面的操作数作a运算结果入操作数栈ab a的优先权低于a入栈ab a的优先权等于加减乘除优先性都低于“”但是高于“”为了算法简洁在表达式的左边和右边虚设一个“#”这一对“#”表示一个表达式求值完成“”“”表示当一对括号相遇时表示括号内已运算完成。“”和“”、“#”和“(”、“(”和“#”无法相继出现如果出现则表达式出现语法错误。栈在表达式求值中有较为广泛的运用。实验三本实验需要从文件中读取数据来构建树还有从文件中读取问题并提取出关键字来在树中寻找相应的结果本实验让我对树的构建和基本操作以及文件读取字符串操作都得到了更深的理解。实验四本实验实现了图的创建遍历和求最短路径的操作其中最短路径问题为该实验的重难点在本实验中我使用了迪杰斯特拉算法本算法思路比较简单在不使用堆优化的情况下时间复杂度为O(E2),使用二叉堆后能优化到O((VE)logE),效率还是挺可观的。通过本实验我掌握了图的邻接表式创建和遍历以及常规迪杰斯特拉算法求最短路径。