本文最后更新于：2 个月前

《数据结构》上机实验内容和要求

通过上机实验加深对课程内容的理解，提高程序设计、开发及调试能力。本实验指导书适用于16学时《数据结构法》实验课，实验项目具体内容如下：

layout: pages
title: 数据结构与算法实验指导书
author: 谭自财
date: 2021-03-21 07:21:35
categories: 数据结构与算法
tags:

数据结构
算法
C语言
实验

实验报告要求

请按照评分标准和报告模板要求，提交实验报告电子版文件。

👦实验一、顺序表的实现及应用

一、实验目的

了解和掌握线性表的顺序存储结构；掌握用C语言上机调试线性表的基本方法；掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算，以及对相应算法的性能分析。

二、实验要求

给定一段程序代码，程序代码所完成的功能为：

（1）建立一个线性表；

（2）依次输入数据元素1,2,3,4,5,6,7,8,9,10；

（3）删除数据元素5；

（4）依次显示当前线性表中的数据元素。假设该线性表的数据元素个数在最坏情况下不会超过100个，要求使用顺序表。

程序中有3处错误的地方，有标识，属于逻辑错误，对照书中的代码仔细分析后，要求同学们修改错误的代码，修改后上机调试得到正确的运行结果。

三、程序代码

6 #include <stdio.h>
#include "stdlib.h"
#define MaxSize  100
typedef int DataType;

typedef struct
{
    DataType list[MaxSize];
    int size;
} SeqList;

void ListInitiate(SeqList *L)/*初始化顺序表L*/
{
    L->size = 0;/*定义初始数据元素个数*/
}

int ListLength(SeqList L)/*返回顺序表L的当前数据元素个数*/
{
    return L.size;
}

int ListInsert(SeqList *L, int i, DataType x)
/*在顺序表L的位置i（0 ≤ i ≤ size）前插入数据元素值x*/
/*插入成功返回1，插入失败返回0*/
{
    int j;
    if(L->size >= MaxSize)
    {
        printf("顺序表已满无法插入! \\n");
        return 0;
    }
    else if(i < 0 || i > L->size )
    {
        printf("参数i不合法! \\n");
        return 0;
    }
    else
    { //此段程序有一处错误
        for(j = L->size; j >= i; j--) L->list[j+1] = L->list[j];/*为插入做准备*/
        L->list[i] = x;/*插入*/
        L->size ++;/*元素个数加1*/
        return 1;
    }
}

int ListDelete(SeqList *L, int i, DataType *x)
/*删除顺序表L中位置i（0 ≤ i ≤ size - 1）的数据元素值并存放到参数x中*/
/*删除成功返回1，删除失败返回0*/
{
    int j;
    if(L->size <= 0)
    {
        printf("顺序表已空无数据元素可删! \\n");
        return 0;
    }
    else if(i < 0 || i > L->size-1)
    {
        printf("参数i不合法");
        return 0;
    }
    else
    {//此段程序有一处错误

        *x = L->list[i];/*保存删除的元素到参数x中*/
        for(j = i +1; j <= L->size-1; j++) L->list[j-1] = L->list[j];/*依次前移*/
        L->size--;/*数据元素个数减1*/
        return 1;
    }
}

int ListGet(SeqList L, int i, DataType *x)
/*取顺序表L中第i个数据元素的值存于x中，成功则返回1，失败返回0*/
{
    if(i < 0 || i > L.size-1)
    {
        printf("参数i不合法! \\n");
        return 0;
    }
    else
    {
        *x = L.list[i];
        return 1;
    }
}

void ListMerge(SeqList L1,SeqList L2,SeqList *L3)
{
    int ai=0,bi=0;
    int i=0,j=0,k=0;
    ListInitiate(L3);
    while (i <= ListLength(L1)-1 && j <= ListLength(L2)-1)
    {
        ListGet(L1,i,&ai);
        ListGet(L2,j,&bi);
        if (ai<=bi)
        {
            ListInsert(L3,k++,ai);
            ++i;

        }
        else {
            ListInsert(L3, k++, bi);
            ++j;
        }
    }
    while(i<=ListLength(L1)-1)
    {
        ListGet(L1,i++,&ai);
        ListInsert(L3,++k,ai);
    }
    while (j<=ListLength(L2)-1)
    {
        ListGet(L2,j++,&bi);
        ListInsert(L3,k++,bi);
    }
}

int main(void)
{   SeqList myList;
    SeqList list;
    SeqList listAll;
    int i , x;
    ListInitiate(&myList);
    ListInitiate(&list);
    ListInitiate(&listAll);
    for(i = 0; i < 10; i++)
        ListInsert(&myList, i, i+1);
    ListDelete(&myList, 4, &x);
    for (int j = 0; j < 10; ++j) {
        ListInsert(&list,j,j+21);
    }
    ListMerge(myList,list,&listAll);
    for(i = 0; i < ListLength(myList); i++)
    {
        ListGet(myList,i,&x); //此段程序有一处错误
        printf("%d\\n", x);
    }
    printf("\\n");
    for(i = 0; i < ListLength(list); i++)
    {
        ListGet(list,i,&x); //此段程序有一处错误
        printf("%d\\n", x);
    }
    for (i = 0; i < ListLength(listAll); i++) {
        ListGet(listAll,i,&x);
        printf("%d\\n",x);
    }
}

合并函数_WriteByLiyihan

void ListMerge(SeqList L1,SeqList L2,SeqList *L3)
{
    int ai=0,bi=0;
    int i=0,j=0,k=0;
    ListInitiate(L3);
    while (i <= ListLength(L1)-1 && j <= ListLength(L2)-1)
    {
        ListGet(L1,i,&ai);
        ListGet(L2,j,&bi);
        if (ai<=bi)
        {
            ListInsert(L3,k++,ai);
            ++i;

        }
        else {
            ListInsert(L3, k++, bi);
            ++j;
        }
    }
    while(i<=ListLength(L1)-1)
    {
        ListGet(L1,i++,&ai);
        ListInsert(L3,++k,ai);
    }
    while (j<=ListLength(L2)-1)
    {
        ListGet(L2,j++,&bi);
        ListInsert(L3,k++,bi);
    }
}

四、实验任务

1.改正上述程序中的错误。

2.编写合并函数，将两个有序线性表合并为一个有序表并在主函数中加以测试。

3.完成实验报告的撰写。

实验二链表的实现及应用

一、实验目的

了解和掌握线性表的链式存储结构；掌握用C语言上机调试线性表的基本方法；掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算，以及对相应算法的性能分析。

二、实验要求

给定一段程序代码，程序代码所完成的功能为：

（1）建立一个线性表；

（2）依次输入数据元素1,2,3,4,5,6,7,8,9,10；

（3）删除数据元素5；

（4）依次显示当前线性表中的数据元素。假设该线性表的数据元素个数在最坏情况下不会超过100个，要求使用单链表。

程序中有3处错误的地方，有标识，属于逻辑错误，对照书中的代码仔细分析后，要求同学们修改错误的代码，上机调试并得到正确的运行结果。

三、程序代码：

#include <stdio.h>/*该文件包含printf()等函数*/
#include <stdlib.h>/*该文件包含exit()等函数*/
#include <malloc.h>/*该文件包含malloc()等函数*/
typedef int DataType;/*定义DataType为int*/
typedef struct Node
{
	DataType data;
	struct Node *next;
} SLNode;

void ListInitiate(SLNode **head)/*初始化*/
{
/*如果有内存空间，申请头结点空间并使头指针head指向头结点*/
	if((*head = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1);
	(*head)->next = NULL;/*置链尾标记NULL */
}

int ListLength(SLNode *head)        /* 单链表的长度*/
{
	SLNode *p = head;/*p指向首元结点*/
	int size = 0;/*size初始为0*/
	while(p->next != NULL)/*循环计数*/
	{
		p = p->next;
		size ++;
	}
	return size;
}
int ListInsert(SLNode *head, int i, DataType x)
/*在带头结点的单链表head的数据元素ai（0 ≤ i ≤ size）结点前*/
/*插入一个存放数据元素x的结点*/
{
	SLNode *p, *q;
	int j;
	p = head; /*p指向首元结点*/
	j = -1;/*j初始为-1*/
	while(p->next != NULL && j < i - 1) 
/*最终让指针p指向数据元素ai-1结点*/
	{
		p = p->next;
		j++;
	}
	if(j != i - 1)
	{
		printf("插入位置参数错！");
		return 0;
	}
/*生成新结点由指针q指示*/
	if((q = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1);
		q->data = x; 
//此段程序有一处错误
	q->next = p->next;/*给指针q->next赋值*/
	p->next = q;/*给指针p->next重新赋值*/
	return 1;
}
int ListDelete(SLNode *head, int i, DataType *x)
/*删除带头结点的单链表head的数据元素ai（0 ≤ i ≤ size - 1）结点*/
/*删除结点的数据元素域值由x带回。删除成功时返回1；失败返回0*/
{
	SLNode *p, *s;
	int j;
	p = head; /*p指向首元结点*/
	j = -1;/*j初始为-1*/
while(p->next != NULL && p->next->next!= NULL && j < i - 1) 
/*最终让指针p指向数据元素ai-1结点*/
	{
		p = p->next;
		j++;
	}
	if(j != i - 1)
	{
		printf("删除位置参数错！");
		return 0;
}
	q= p->next; /*指针s指向数据元素ai结点*/
	*x = s->data;/*把指针s所指结点的数据元素域值赋予x*/
	p->next = s->next;/*把数据元素ai结点从单链表中删除*/
	free(s);/*释放指针s所指结点的内存空间*/
	return 1;
}

int ListGet(SLNode *head, int i, DataType *x)
/*取数据元素ai和删除函数类同，只是不删除数据元素ai结点*/
{
	SLNode *p;
	int j;
	p = head;
	j = -1;
	while(p->next != NULL && j < i)
	{
		p = p->next;j++;
	}
	if(j != i)
	{
		printf("取元素位置参数错！");
	return 0;
	}
	*x = p->data;
	return 1;
}
void Destroy(SLNode **head)
{
	SLNode *p, *p1;
	p = *head;
	while(p != NULL)
	{
		p1 = p;
		p = p->next;
		free(p1);
	}
	*head = NULL;
}

	void main(void)
{
	SLNode *head;
	int i , x;
	ListInitiate(&head);/*初始化*/
	for(i = 0; i < 10; i++)
	{
		if(ListInsert(head, i, i+1) == 0) /*插入10个数据元素*/
		{
			printf("错误! \\n");
			rturn;
		}
	}
	if(ListDelete(head, 4, &x) == 0) /*删除数据元素5*/
	{
		printf("错误! \\n");
		return;
	}
	for(i = 0; i < ListLength(head); i++)
	{
	if(ListGet(head, i, &x) == 0) /*取元素*/
	{
		printf("错误! \\n");
		return;
	}
	else printf("%d   ", x);/*显示数据元素*/
	}
	Destroy(&head);
	}

三、实验任务

1.改正上述程序中的错误。

2.编写合并函数，将两个有序的单链表合并成一个有序单链表。

3.完成实验报告的撰写。

实验三、栈的实现及应用

一、实验目的

1.掌握栈的存储表示和实现

2.掌握栈的基本操作实现。

3.掌握栈在解决实际问题中的应用。

二、实验要求

问题描述：设计一个程序，演示用算符优先法对算术表达式求值的过程。利用算符优先关系，实现对算术四则混合运算表达式的求值。

（1）输入的形式：表达式，例如2*(3+4)#

包含的运算符只能有’+’ 、’-‘ 、’*’ 、’/‘ 、’(‘、 ‘)’，“#”代表输入结束符；

（2）输出的形式：运算结果，例如2*(3+4)=14；（3）程序所能达到的功能：对表达式求值并输出。

三、解题参考思路

为了实现用栈计算算数表达式的值，需设置两个工作栈：用于存储运算符的栈opter，以及用于存储操作数及中间结果的栈opnd。

算法基本思想如下：

（1）首先将操作数栈opnd设为空栈，而将’#’作为运算符栈opter的栈底元素，这样的目的是判断表达式是否求值完毕。

（2）依次读入表达式的每个字，表达式须以’#’结，读入字符若是操作数则入栈opnd，读入字符若是运算符，则将此运算符c与opter的栈顶元素top比较优先级后执行相应的操作，具体操作如下：

若top的优先级小于c，即top<c，则将c直接入栈opter，并读入下一字符赋值给c；
若top的优先级等于c，即top=c，则弹出opter的栈顶元素，并读入下一字符赋值给c，这一步目的是进行括号操作;
若top优先级高于c，即top>c，则表明可以计算，此时弹出opnd的栈顶两个元素，并且弹出opter栈顶的的运算符，计算后将结果放入栈opnd中。直至opter的栈顶元素和当前读入的字符均为’#’，此时求值结束。

算符间的优先关系如下表所示（表来源：严蔚敏《数据结构》）：

表来源：严蔚敏《数据结构》

表中需要注意的是θ1为opter的栈顶元素，θ2为从表达式中读取的操作符，此优先级表可以用二维数组实现。

图例：

表达式求值

比较算符优先关系代码示例：

1.	int getIndex(char theta)   //获取theta所对应的索引  
2.	{  
3.	    int index = 0;  
4.	    switch (theta)  
5.	    {  
6.	    case '+':
7.	        index = 0;  
8.	        break;  
9.	    case '-':  
10.	        index = 1;  
11.	        break;  
12.	    case '*':  
13.	        index = 2;  
14.	        break;  
15.	    case '/':  
16.	        index = 3;  
17.	        break;  
18.	    case '(':  
19.	        index = 4;  
20.	        break;  
21.	    case ')':  
22.	        index = 5;  
23.	        break;  
24.	    case '#':  
25.	        index = 6;  
26.	    default:break;  
27.	    }  
28.	    return index;  
29.	}  
30.	  
31.	char getPriority(char theta1, char theta2)   //获取theta1与theta2之间的优先级  
32.	{  
33.	    const char priority[][7] =     //算符间的优先级关系  
34.	    {  
35.	        { '>','>','<','<','<','>','>' },  
36.	        { '>','>','<','<','<','>','>' },  
37.	        { '>','>','>','>','<','>','>' },  
38.	        { '>','>','>','>','<','>','>' },  
39.	        { '<','<','<','<','<','=','0' },  
40.	        { '>','>','>','>','0','>','>' },  
41.	        { '<','<','<','<','<','0','=' },  
42.	    };  
43.	  
44.	    int index1 = getIndex(theta1);  
45.	    int index2 = getIndex(theta2);  
46.	    return priority[index1][index2];  
47.	}

四、实验任务

认真阅读与理解实验内容的具体要求，参考教材相关章节，结合实验内容的要求，编写实验程序并上机调试与测试，完成实验报告的撰写。

五、实验思路

栈的定义

创建两个结构体，一个做栈，一个是栈的节点

typedef struct node
{
    int data;
    struct node *next;
}Node;

typedef struct stack
{
    Node *top;
    int count;
}Stack;

栈的操作

包括栈的基本操作

栈的初始化
栈空的判断
压栈
出栈
取栈顶元素
清空栈

//初始化栈
int InitStack(Stack *s)
{
    s->top = NULL;
    s->count= 0;
    return OK;
}

//判空栈
int EmptyStack(Stack *s)
{
    return (s->count == 0) ? OK : ERROR;
}

//压栈
int Push(Stack *s, int e)
{
    Node *p = (Node *)malloc(sizeof(Node));
    if(p == NULL)
    {
        return ERROR;
    }
    p->data = e;
    p->next = s->top;
    s->top = p;
    s->count++;

    return OK;
}

//取栈顶元素
int GetTop(Stack *s)
{
    if(NULL == s->top)
    {
        return ERROR;
    }

    return (s->top->data);
}

//出栈
int Pop(Stack *s)
{
    int e;
    if(NULL == s->top)
    {
        return ERROR;
    }

    Node *p = s->top;
    e = p->data;
    s->top = p->next;
    free(p);
    s->count--;

    return e;
}

//清空栈
int ClearStack(Stack *s)
{
    if(s->count <= 0){
        printf("栈已空");
        return ERROR;
    }
    Node *p = s->top;
    while(s->count > 0)
    {
        p=s->top;
        s->top=s->top->next;
        free(p);
        s->count--;
    }

    s->top==NULL;
    return OK;
}

符号优先级判断函数

int Priority(char s)
{
    switch(s)
    {
        case '(':
            return 3;
        case '*':
        case '/':
            return 2;
        case '+':
        case '-':
            return 1;
        default:
            return 0;
    }
}

主函数思路1

判断符号还是数字，数字直接入栈
判断符号
1. 如果是（符号栈为空||符号栈栈顶为’(‘&&当前符号不是’)’||栈顶优先级低于当前符号),则入栈不计算
2. 如果’()’内无其他运算符，即最栈顶是（当前操作符号是），直接（出栈
3. 如果（字符串扫描完成且符号栈不为空）||(当前运算符优先级低于栈顶元素)

int main() {
    Stack num, opt;
    char l = '*';
    char str[100] = {0};
    int i = 0, tmp = 0, j;

    if (InitStack(&num) != OK || InitStack(&opt) != OK) {
        printf("Init Failure!\\n");
        exit(1);
    }

    while(l != '#'){
        printf("Please Input Operator :\\n");
        scanf("%s", str);
        if(str[0]=='#')return 0;
        while (str[i] != '\\0' || EmptyStack(&opt) != OK) {
            if (str[i] >= '0' && str[i] <= '9') {
                tmp = tmp * 10 + str[i] - '0';
                i++;
                if (str[i] < '0' || str[i] > '9') {
                    Push(&num, tmp);
                    tmp = 0;
                }
            } else {
                //符号栈为空
                //符号栈栈顶为'('&&当前符号不是')'
                //栈顶优先级低于当前符号
                if ((EmptyStack(&opt) == OK) || (GetTop(&opt) == '(' && str[i] != ')') || Priority(str[i]) > Priority(GetTop(&opt)))//进栈不参与运算
                {
                    Push(&opt, str[i]);
                    i++;
                    continue;
                }
                //'()'内无其他运算符
                if (GetTop(&opt) == '(' && str[i] == ')')//出栈不参与运算
                {
                    Pop(&opt);
                    i++;
                    continue;
                }
                //
                if ((str[i] == '\\0' && EmptyStack(&opt) != OK) || (str[i] == ')' && GetTop(&opt) != '(') || Priority(str[i]) <= Priority(GetTop(&opt)))//出栈并参与运算
                {
                    switch (Pop(&opt)) {
                        case '+':
                            Push(&num, Pop(&num) + Pop(&num));
                            break;
                        case '-':
                            j = Pop(&num);
                            Push(&num, Pop(&num) - j);
                            break;
                        case '*':
                            Push(&num, Pop(&num) * Pop(&num));
                            break;
                        case '/':
                            j = Pop(&num);
                            Push(&num, Pop(&num) / j);
                    }
                    continue;
                }
            }
        }

        printf("%d", Pop(&num));
        printf("\\n");
        i=0;

    }
    return 0;
}

主函数思路2：数据结构指导书要求

首先创建两个栈opnd、opter，设为opnd为空栈，而将’#’作为运算符栈opter的栈底元素，以判断表达式是否求值完毕。
依次读入表达式的每个字，表达式须以’#’结，读入字符若是操作数则入栈opnd，读入字符若是运算符，则将此运算符c与opter的栈顶元素top比较优先级后执行相应的操作，具体操作如下：
1. 若top的优先级小于c，即top<c，则将c直接入栈opter，并读入下一字符赋值给c；
2. 若top的优先级等于c，即top=c，则弹出opter的栈顶元素，并读入下一字符赋值给c，这一步目的是进行括号操作;
3. 若top优先级高于c，即top>c，则表明可以计算，此时弹出opnd的栈顶两个元素，并且弹出opter栈顶的的运算符，计算后将结果放入栈opnd中。直至opter的栈顶元素和当前读入的字符均为’#’，此时求值结束。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>

#define OK     1
#define ERROR  0
#define MAX_LINE 100

typedef struct nodeNum
{
    int data;
    struct node *next;
}Node;

typedef struct stack
{
    Node *top;
    int count;
}Stack;

//初始化栈
int InitStack(Stack *l)
{
    l->top = NULL;
    l->count= 0;
    return OK;
}

//判空栈
int EmptyStack(Stack *s)
{
    return (s->count == 0) ? OK : ERROR;
}

//压栈
int Push(Stack *s, int e)
{
    Node *p = (Node *)malloc(sizeof(Node));
    if(p == NULL)
    {
        return ERROR;
    }
    p->data = e;
    p->next = s->top;
    s->top = p;
    s->count++;

    return OK;
}

//取栈顶元素
int GetTop(Stack *s)
{
    if(NULL == s->top)
    {
        return ERROR;
    }

    return (s->top->data);
}

//符号优先级判断
int Priority(char s)
{
    switch(s)
    {
        case '(':
            return 3;
        case '*':
        case '/':
            return 2;
        case '+':
        case '-':
            return 1;
        case '#':
            return 0;
        default:
            return -1;
    }
}

//出栈
int Pop(Stack *s)
{
    int e;
    if(NULL == s->top)
    {
        return ERROR;
    }

    Node *p = s->top;
    e = p->data;
    s->top = p->next;
    free(p);
    s->count--;

    return e;
}

//清空栈
int ClearStack(Stack *s)
{
    if(s->count <= 0){
        printf("栈已空");
        return ERROR;
    }
    Node *p = s->top;
    while(s->count > 0)
    {
        p=s->top;
        s->top=s->top->next;
        free(p);
        s->count--;
    }

    s->top==NULL;
    return OK;
}

int main(){
    char str[MAX_LINE] = {"123"};
    int i=0,temp=0,j=0;
    Stack opnd,opter;

    if(InitStack(&opnd) != OK || InitStack(&opter) != OK){
        printf("初始化错误，请关闭后重试");
        exit(1);
    }
    Push(&opter,'#');

    do{
        printf("请输入计算表达式,并以#结尾\\n");
        scanf("%s",str);
    }while(str[0]== '#'|| str[strlen(str)-1] != '#');

    while(str[i] != '#' || GetTop(&opter) != '#')
    {
        if(str[i] >= '0' && str[i] <= '9')
        {
            temp = temp * 10 + str[i] - '0';
            i++;
            if(str[i] < '0' || str[i] > '9')
            {
                Push(&opnd,temp);
                temp = 0;
            }
        }else{
            //符号栈栈底是#
            //符号栈栈顶为'('&&当前符号不是')'
            //栈顶优先级低于当前符号
            //进栈不参与运算
            if ((GetTop(&opter) == '#') || (GetTop(&opter) == '(' && str[i] != ')') || Priority(str[i]) > Priority(GetTop(&opter)))
            {
                Push(&opter, str[i]);
                i++;
                continue;
            }
            //'()'内无其他运算符
            //出栈不参与运算
            if (GetTop(&opter) == '(' && str[i] == ')')
            {
                Pop(&opter);
                i++;
                continue;
            }
            //
            //出栈运算
            if ((str[i] == '#' && GetTop(&opter) != '#') || (str[i] == ')' && GetTop(&opter) != '(') || Priority(str[i]) <= Priority(GetTop(&opter)))
            {
                switch (Pop(&opter)) {
                    case '+':
                        Push(&opnd, Pop(&opnd) + Pop(&opnd));
                        break;
                    case '-':
                        j = Pop(&opnd);
                        Push(&opnd, Pop(&opnd) - j);
                        break;
                    case '*':
                        Push(&opnd, Pop(&opnd) * Pop(&opnd));
                        break;
                    case '/':
                        j = Pop(&opnd);
                        Push(&opnd, Pop(&opnd) / j);
                }
                continue;
            }
        }
    }

    printf("%d", Pop(&opnd));
    printf("\\n");
    return 0;

}

实验四、队列的实现及应用

一、实验目的

1.掌握队列的存储表示和实现。

2.掌握队列的基本操作实现。

3.掌握队列在解决实际问题中的应用。

二、实验要求

利用队列模拟服务台前的排队现象问题。

某银行有一个客户办理业务站，在单位时间内随机地有客户到达，设每位客户的业务办理时间是某个范围的随机值。设只有一个窗口，一位业务人员，要求程序模拟统计在设定时间内，业务人员的总空闲时间和客户的平均等待时间。假定模拟数据已按客户到达的先后顺序依次存于某个正文数据文件中，对应每位客户有两个数据：到达时间和需要办理业务的时间，文本文件内容如：10 20 10 10 45 5 55 10 58 15 65 10

三、解题参考思路

与栈相对应，队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端进行删除元素。允许插入的一端称队尾，允许删除的一端称队头。插入与删除分别称为入队与出队。队列示意图如下图所示：

一、数据描述（结构体定义）

数据描述（结构体定义）

typedef struct{
  int arrive;
  int treat;//客户的信息结构
}QNODE；
    
typedef struct node{
	QNODE data;
	Struct node *next;//队列中的元素信息
}LNODE,*QueuePtr;

typedef  struct{ //链队列类型
  QueuePtr   front ;  //队头指针    
  QueuePtr   rear ;  //队尾指针
} LinkQueue;

二、存取操作（队列操作函数）

/*
 * 函数功能：队列初始化
 * 传入参数：队列指针
 * 返回值：int 1 OK 操作成功
 *       int 1 ERROE 操作失败
 */
int InitQueue(LinkQueue *Q){
    QueuePtr p =(QueuePtr)malloc(sizeof(LNODE));
    if (p == NULL){
        printf("初始化失败\\n");
        return ERROR;
    }
    Q->rear = Q->front = p;
    Q->front->next = NULL;
    return OK;
}
/*
 * 函数功能：入队
 * 传入参数：队列指针 入队数据
 * 返回值：int 1 OK 操作成功
 *       int 1 ERROE 操作失败
 * */
int EnQueue(LinkQueue* Q,QNODE data){
    QueuePtr p =(QueuePtr)malloc(sizeof(LNODE));
    p->data = data;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
    return OK;
}
/* 函数功能：出队
 * 传入参数：队列指针 取值变量指针
 * 传入参数：无
 * 返回值：int 1 OK 操作成功
 *       int 1 ERROE 操作失败
 * */
int DeQueue(LinkQueue *Q,QNODE *e){
    if (Q->front == Q->rear) {
        printf("队列为空，删除失败\\n");
        return ERROR;
    }
    LNODE* p;
    p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if (Q->rear == p)Q->rear = Q->front;
    free(p);
    return OK;
}

三、主函数流程

主函数流程

{ 
	设置统计初值：业务员等待时间，客户总的待时间，客户总人数等

	设置当前时钟clock时间为0；
	//用变量clock来模拟当前时间.

	打开数据文件，准备读；
	printf("\\nenterfilename:");
  scanf("%s",Fname);/*输入装客户模拟数据的文件的文件名*/

	读入第一位客户信息于暂存变量中；
	//文件读操作have= fscanf(fp,"%d %d",&temp.arrive,&temp.treat);

	//约定每轮循环，处理完一位客户
	do{
			if(等待队列为空，并且还有客户){ 

				累计业务员总等待时间；

				时钟推进到暂存变量中的客户的到达时间；//clock=temp.arrive

				暂存变量中的客户信息进队；

				读取下一位客户信息于暂存变量；

}

从等待队列出队一位客户；

累计客户人数；

将该客户的等待时间累计到客户的总等待时间；//=当前时间-客户到达时间

设定当前客户的业务办理结束时间；//=当前时间+客户办理业务所需时间

while(下一位客户的到达时间在当前客户处理结束之前，并且还有客户)

{

		暂存变量中的客户信息进队；

读取下一位客户信息于暂存变量；

}

		时钟推进到当前客户办理结束时间；

}while(还有未处理的客户)；//等待队列不为空或者还有客户（have==2）

计算统计结果，并输出；
void main(){
    QNODE curret,temp;
    int dwait=0,clock=0,wait=0,count=0,have=0,finish;
    LinkQueue BankQueue;
    InitQueue(&BankQueue);
    printf("\\n请输入读取文件的文件名\\n");
    scanf("%s",file_name);
    fopen_s(&fp,file_name,"r");
    while (fp == NULL){
        printf("当前目录没有此文件，请重新输入文件名");
        scanf("%s",file_name);
    }
    have = fscanf_s(fp,"%d %d",&temp.arrive,&temp.treat);
    do{        //约定每轮循环，处理一个客户
        if(BankQueue.front->next == NULL&&have==2)     //等待队列为空，但还有客户
        {
            dwait+=temp.arrive-clock;  //累计业务员总等待时间
            clock=temp.arrive;
            EnQueue(&BankQueue,temp); //暂存变量中客户的信息进队
            have=fscanf(fp,"%d %d",&temp.arrive,&temp.treat);
        }
        count++;
        DeQueue(&BankQueue,&curret); //出队一位客户信息
        wait+=clock-curret.arrive;  //累计到客户的等待时间
        finish=clock+curret.treat;  //设定业务办理结束时间
        while(have==2&&temp.arrive<=finish)   //下一位客户到达时间在当前客户处理结束之前
        {
            EnQueue(&BankQueue,temp);  //暂存变量中的客户信息进队
            have=fscanf(fp,"%d%d",&temp.arrive,&temp.treat);
        }
        clock=finish;  //时钟推进到当前客户办理结束时间
    }while(have==2||BankQueue.front->next!=NULL);
    printf("结果：业务员等待时间%d\\n客户平均等待时间%f\\n",dwait,(double)wait/count);
    printf("模拟总时间：%d,\\n客户人数：%d,\\n总等待时间：%d\\n",clock,count,wait);
    getchar();
}
#include<stdio.h>
#include<stdlib.h>
#include <malloc.h>
#define MAX_FILE_NAME_LENGHT 120
#define OK 1
#define ERROR 0

//客户的信息结构
typedef struct{
    int arrive;
    int treat;
}QNODE;

//队列节点定义结构
typedef struct node{
    QNODE data;
    struct node *next;//队列中的元素信息
}LNODE,*QueuePtr;

//队列-链队列类型
typedef struct{
    QueuePtr  front ; //队头指针
    QueuePtr  rear ; //队尾指针
}LinkQueue;

char file_name[MAX_FILE_NAME_LENGHT];
FILE *fp;

/*
 * 函数功能：队列初始化
 * 传入参数：队列指针
 * 返回值：int 1 OK 操作成功
 *       int 1 ERROE 操作失败
 */
int InitQueue(LinkQueue *Q){
    QueuePtr p =(QueuePtr)malloc(sizeof(LNODE));
    if (p == NULL){
        printf("初始化失败\\n");
        return ERROR;
    }
    Q->rear = Q->front = p;
    Q->front->next = NULL;
    return OK;
}
/*
 * 函数功能：入队
 * 传入参数：队列指针 入队数据
 * 返回值：int 1 OK 操作成功
 *       int 1 ERROE 操作失败
 * */
int EnQueue(LinkQueue* Q,QNODE data){
    QueuePtr p =(QueuePtr)malloc(sizeof(LNODE));
    p->data = data;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
    return OK;
}
/* 函数功能：出队
 * 传入参数：队列指针 取值变量指针
 * 传入参数：无
 * 返回值：int 1 OK 操作成功
 *       int 1 ERROE 操作失败
 * */
int DeQueue(LinkQueue *Q,QNODE *e){
    if (Q->front == Q->rear) {
        printf("队列为空，删除失败\\n");
        return ERROR;
    }
    LNODE* p;
    p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if (Q->rear == p)Q->rear = Q->front;
    free(p);
    return OK;
}
/*
 *函数功能：模仿模拟服务台前的排队现象问题
 * */
void main(){
    QNODE curret,temp;
    int dwait=0,clock=0,wait=0,count=0,have=0,finish;
    LinkQueue BankQueue;
    InitQueue(&BankQueue);
    printf("\\n请输入读取文件的文件名\\n");
    scanf("%s",file_name);
    fopen_s(&fp,file_name,"r");
    while (fp == NULL){
        printf("当前目录没有此文件，请重新输入文件名");
        scanf("%s",file_name);
    }
    have = fscanf_s(fp,"%d %d",&temp.arrive,&temp.treat);
    do{        //约定每轮循环，处理一个客户
        if(BankQueue.front->next == NULL&&have==2)     //等待队列为空，但还有客户
        {
            dwait+=temp.arrive-clock;  //累计业务员总等待时间
            clock=temp.arrive;
            EnQueue(&BankQueue,temp); //暂存变量中客户的信息进队
            have=fscanf(fp,"%d %d",&temp.arrive,&temp.treat);
        }
        count++;
        DeQueue(&BankQueue,&curret); //出队一位客户信息
        wait+=clock-curret.arrive;  //累计到客户的等待时间
        finish=clock+curret.treat;  //设定业务办理结束时间
        while(have==2&&temp.arrive<=finish)   //下一位客户到达时间在当前客户处理结束之前
        {
            EnQueue(&BankQueue,temp);  //暂存变量中的客户信息进队
            have=fscanf(fp,"%d%d",&temp.arrive,&temp.treat);
        }
        clock=finish;  //时钟推进到当前客户办理结束时间
    }while(have==2||BankQueue.front->next!=NULL);
    printf("结果：业务员等待时间%d\\n客户平均等待时间%f\\n",dwait,(double)wait/count);
    printf("模拟总时间：%d,\\n客户人数：%d,\\n总等待时间：%d\\n",clock,count,wait);
    getchar();
}

四、实验任务

认真阅读与理解实验内容的具体要求，参考教材相关章节，结合实验内容的要求，编写实验程序并上机调试与测试，完成实验报告的撰写。

五、注意点

*fopen()函数原型为FILE * =fopen(char* ,char ** );
**fopen_s函数更改为int fopen_s(FILE ,char ,char *);
fscanf_s函数原型为 int fscanf_s(FILE *,char * ,dataType *……)
fscanf_s函数原型为 int fscanf_s(FILE *,char * ,dataType *……)
被打开的文件必须与exe文件夹放在一起，或者指定绝对路径
在使用fscanf前确保传入的FILE*不是NULL,否则会出现错误

/*文件操作实例*/
#include <stdio.h>

int main() {
    char file_name[150] ="text.txt";
    int data;
    int data2;
    FILE *fp;
    int l =1;
    fopen_s(&fp,file_name,"r");
    if (fp != NULL){
        printf("OK");
        fscanf_s(fp,"%d %d",&data2,&data);
        printf("%d %d",data,data2);
    } else{
        printf("Fause");
    }

}

实验五、二叉树操作及应用

一、实验目的

掌握二叉树的定义、结构特征，以及各种存储结构的特点及使用范围，各种遍历算法。掌握用指针类型描述、访问和处理二叉树的运算。掌握前序或中序的非递归遍历算法。

二、相关知识

遍历

二叉树的遍历主要有三种：

（1）先(根)序遍历（根左右）

（2）中(根)序遍历（左根右）

（3）后(根)序遍历（左右根）

举个例子：

https://img-blog.csdn.net/20180704200305280?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODQwMTI5/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70

先(根)序遍历（根左右）：A B D H E I C F J K G

中(根)序遍历（左根右） : D H B E I A J F K C G

后(根)序遍历（左右根） : H D I E B J K F G C A

class Node:
    def __init__(self, dat, left=None, right=None):
        self.data = dat
        self.left = left
        self.right = right
 
 
def rebuild(rear, center):
    if not rear:
        return
    cur = Node(rear[-1])
    index = center.index(rear[-1])
    cur.left = rebuild(rear[:index], center[:index])
    cur.right = rebuild(rear[index:-1], center[index + 1:]) #rear[index:-1]是到倒数第二个数
    return cur
 
 
def pre_order(t):
    if t == None:
        return
    print(t.data)
    pre_order(t.left)
    pre_order(t.right)
 
 
if __name__ == "__main__":
    rear = ['d','a','b','e','c']
    center = ['d','e','b','a','c']
    t = rebuild(rear, center)
    pre_order(t)

二、实验要求

有如下二叉树：

二叉树

程序代码给出了该二叉树的链式存储结构的建立、前序、中序、后序遍历的算法，同时也给出了查询“E”是否在二叉树里的代码。代码有三处错误，有标识，属于逻辑错误，对照书中的代码仔细分析后，请修改了在电脑里运行。

#include <stdlib.h>
#include <stdio.h>

typedef char DataType;

typedef struct Node

{

DataType data;/*数据域*/

struct Node *leftChild;/*左子树指针*/

struct Node *rightChild;/*右子树指针*/

}BiTreeNode;/*结点的结构体定义*/

/*初始化创建二叉树的头结点*/

void Initiate(BiTreeNode **root)

{

- root = (BiTreeNode *)malloc(sizeof(BiTreeNode));

(*root)->leftChild = NULL;

(*root)->rightChild = NULL;

}

void Destroy(BiTreeNode **root)

{

if((*root) != NULL && (*root)->leftChild != NULL)

Destroy(&(*root)->leftChild);

if((*root) != NULL && (*root)->rightChild != NULL)

Destroy(&(*root)->rightChild);

free(*root);

}

/*若当前结点curr非空，在curr的左子树插入元素值为x的新结点*/

/*原curr所指结点的左子树成为新插入结点的左子树*/

/*若插入成功返回新插入结点的指针，否则返回空指针*/

BiTreeNode *InsertLeftNode(BiTreeNode *curr, DataType x)

{

BiTreeNode *s, *t;

if(curr == NULL) return NULL;

t = curr->leftChild;/*保存原curr所指结点的左子树指针*/

s = (BiTreeNode *)malloc(sizeof(BiTreeNode));

s->data = x;

s->leftChild = t;/*新插入结点的左子树为原curr的左子树*/

s->rightChild = NULL;

curr->leftChild = s;/*新结点成为curr的左子树*/

return curr->leftChild;/*返回新插入结点的指针*/

}

/*若当前结点curr非空，在curr的右子树插入元素值为x的新结点*/

/*原curr所指结点的右子树成为新插入结点的右子树*/

/*若插入成功返回新插入结点的指针，否则返回空指针*/

BiTreeNode *InsertRightNode(BiTreeNode *curr, DataType x)

{

BiTreeNode *s, *t;

if(curr == NULL) return NULL;

t = curr->rightChild;/*保存原curr所指结点的右子树指针*/

s = (BiTreeNode *)malloc(sizeof(BiTreeNode));

s->data = x;

s->rightChild = t;/*新插入结点的右子树为原curr的右子树*/

s->leftChild = NULL;

curr->rightChild = s;/*新结点成为curr的右子树*/

return curr->rightChild;/*返回新插入结点的指针*/

}

void PreOrder(BiTreeNode *t, void visit(DataType item))

//使用visit(item)函数前序遍历二叉树t

{

if(t != NULL)

{//此小段有一处错误

visit(t->data);

PreOrder(t-> rightChild, visit);

PreOrder(t-> leftChild, visit);

}

}

void InOrder(BiTreeNode *t, void visit(DataType item))

//使用visit(item)函数中序遍历二叉树t

{

if(t != NULL)

{//此小段有一处错误

InOrder(t->leftChild, visit);

InOrder(t->rightChild, visit);

visit(t->data);

}

}

void PostOrder(BiTreeNode *t, void visit(DataType item))

//使用visit(item)函数后序遍历二叉树t

{

if(t != NULL)

{//此小段有一处错误

visit(t->data);

PostOrder(t->leftChild, visit);

PostOrder(t->rightChild, visit);

}

}

void Visit(DataType item)

{

printf("%c ", item);

}

BiTreeNode *Search(BiTreeNode *root, DataType x)//需找元素x是否在二叉树中

{

BiTreeNode *find=NULL;

if(root!=NULL)

{

if(root->data==x)

find=root;

else

{

find=Search(root->leftChild,x);

if(find==NULL)

find=Search(root->rightChild,x);

}

}

return find;

}

void main(void)

{

BiTreeNode *root, *p, *pp,*find;

char x='E';

Initiate(&root);

p = InsertLeftNode(root, 'A');

p = InsertLeftNode(p, 'B');

p = InsertLeftNode(p, 'D');

p = InsertRightNode(p, 'G');

p = InsertRightNode(root->leftChild, 'C');

pp = p;

InsertLeftNode(p, 'E');

InsertRightNode(pp, 'F');

printf("前序遍历：");

PreOrder(root->leftChild, Visit);

printf("\\n中序遍历：");

InOrder(root->leftChild, Visit);

printf("\\n后序遍历：");

PostOrder(root->leftChild, Visit);

find=Search(root,x);

if(find!=NULL)

printf("\\n数据元素%c在二叉树中 \\n",x);

else

printf("\\n数据元素%c不在二叉树中 \\n",x);

Destroy(&root);

}

三、实验任务：

1.改正程序错误。

2.编写二叉树的前序（或中序）的非递归遍历算法并进行测试。

#include

using namespace std;

stack<BiTreeNode*> s;

BiTreeNode *p;

s.push(p);

s.top();

s.pop();

s.empty()_

3.完成实验报告的撰写。

实验六、图的遍历操作及应用

一*、*实验目的*

掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。

二、实验要求*

采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。本实验给出了示例程序，其中共有4处错误，错误段均有标识，属于逻辑错误。请认真理解程序，修改程序代码，并在电脑上调试运行。

三、 DFS和BFS 的基本思想*

深度优先搜索法DFS的基本思想：*从图G中某个顶点Vo出发，首先访问Vo，然后选择一个与Vo相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问，……依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。
广度优先算法BFS的基本思想：*从图G中某个顶点Vo出发，首先访问Vo，然后访问与Vo相邻的所有未被访问过的顶点V1，V2，……，Vt；再依次访问与V1，V2，……，Vt相邻的起且未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。

file:////private/var/folders/rq/rhtpqfks4_3brk7ddz_g1qh80000gn/T/com.kingsoft.wpsoffice.mac/wps-tanzicai/ksohtml/wpsF7cE0U.png?lastModify=1605522401

四、

示例程序
1.邻接矩阵作为存储结构的程序示例

#include"stdio.h"

\#include"stdlib.h"

\#define MaxVertexNum 100 //定义最大顶点数

typedef struct{

char vexs[MaxVertexNum]; //顶点表

int edges**[MaxVertexNum](notion://www.notion.so/afc75248d48d4c3baadfce4b9c10a03d#)**; //邻接矩阵，可看作边表

int n,e; //图中的顶点数n和边数e

}MGraph; //用邻接矩阵表示的图的类型

//=========建立邻接矩阵=======

void CreatMGraph(MGraph *G)

{

int i,j,k;

char a;

printf("Input VertexNum(n) and EdgesNum(e): ");

scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数

scanf("%c",&a);

printf("Input Vertex string:");

for(i=0;i<G->n;i++)

{

scanf("%c",&a);

G->vexs[i]=a; //读入顶点信息，建立顶点表

}

for(i=0;i<G->n;i++)

for(j=0;j<G->n;j++)

G->edges**[i](notion://www.notion.so/afc75248d48d4c3baadfce4b9c10a03d#)**=0; //初始化邻接矩阵

printf("Input edges,Creat Adjacency Matrix\n");

for(k=0;k<G->e;k++) { //读入e条边，建立邻接矩阵

scanf("%d%d",&i,&j); //输入边（Vi，Vj）的顶点序号

G->edges**[i](notion://www.notion.so/afc75248d48d4c3baadfce4b9c10a03d#)**=1;

G->edges**[j](notion://www.notion.so/afc75248d48d4c3baadfce4b9c10a03d#)**=1; //若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句

}

}

//=========定义标志向量，为全局变量=======

typedef enum{FALSE,TRUE} Boolean;

Boolean visited[MaxVertexNum];

//========DFS：深度优先遍历的递归算法======

void DFSM(MGraph *G,int i)

{ //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵

int j;

printf("%c",G->vexs[i]); //访问顶点Vi

visited[i]=TRUE; //置已访问标志

for(j=0;j<G->n;j++) //依次搜索Vi的邻接点

if(G->edges**[i](notion://www.notion.so/afc75248d48d4c3baadfce4b9c10a03d#)**==1 && ! visited[j])

DFSM(G,j); //（Vi，Vj）∈E，且Vj未访问过，故Vj为新出发点

}

void DFS(MGraph *G)

{ //此段代码有一处错误

int i;

for(i=0;i<G->n;i++)

visited[i]=FALSE; //标志向量初始化

for(i=0;i<G->n;i++)

if(!visited[i]) //Vi未访问过

DFS(G,i); //以Vi为源点开始DFS搜索

}

//===========BFS：广度优先遍历=======

void BFS(MGraph *G,int k)

{ //以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索

int i,j,f=0,r=0;

int cq[MaxVertexNum]; //定义队列

for(i=0;i<G->n;i++)

visited[i]=FALSE; //标志向量初始化

for(i=0;i<=G->n;i++)

cq[i]=-1; //队列初始化

printf("%c",G->vexs[k]); //访问源点Vk

visited[k]=TRUE;

cq[r]=k; //Vk已访问，将其入队。注意，实际上是将其序号入队

while(cq[f]!=-1) { //队非空则执行

i=cq[f]; f=f+1; //Vf出队

for(j=0;j<G->n;j++) //依次Vi的邻接点Vj

if(G->edges**[i](notion://www.notion.so/afc75248d48d4c3baadfce4b9c10a03d#)**==1 && !visited[j]) { //Vj未访问 以下三行代码有一处错误

printf("%c",G->vexs[j]); //访问Vj

visited[j]=FALSE; r=r+1; cq[r]=j; //访问过Vj入队

}

}

}

//==========main=====

void main()

{

MGraph *G;

G=(MGraph *)malloc(sizeof(MGraph)); //为图G申请内存空间

CreatMGraph(G); //建立邻接矩阵

printf("Print Graph DFS: ");

DFS(G); //深度优先遍历

printf("\n");

printf("Print Graph BFS: ");

BFS(G,3); //以序号为3的顶点开始广度优先遍历

printf("\n");}

执行顺序：*

VertexNum(n) and EdgesNum(e): 8，9
Input Vertex string: 01234567

Input edges,Creat Adjacency Matrix

0 1

0 2

1 3

1 4

2 5

2 6

3 7

4 7

5 6

Print Graph DFS: 01374256

Print Graph BFS: 31704256

2.*邻接链表作为存储结构程序示例*

\#include"stdio.h"

\#include"stdlib.h"

\#define MaxVertexNum 50 //定义最大顶点数

typedef struct node{ //边表结点

int adjvex; //邻接点域

struct node *next; //链域

}EdgeNode;

typedef struct vnode{ //顶点表结点

char vertex; //顶点域

EdgeNode *firstedge; //边表头指针

}VertexNode;

typedef VertexNode AdjList[MaxVertexNum]; //AdjList是邻接表类型

typedef struct {

AdjList adjlist; //邻接表

int n,e; //图中当前顶点数和边数

} ALGraph; //图类型

//=========建立图的邻接表=======

void CreatALGraph(ALGraph *G)

{

int i,j,k;

char a;

EdgeNode *s; //定义边表结点

printf("Input VertexNum(n) and EdgesNum(e): ");

scanf("%d,%d",&G->n,&G->e); //读入顶点数和边数

scanf("%c",&a);

printf("Input Vertex string:");

for(i=0;i<G->n;i++) //建立顶点表

{

scanf("%c",&a);

G->adjlist[i].vertex=a; //读入顶点信息

G->adjlist[i].firstedge=NULL; //边表置为空表

}

printf("Input edges,Creat Adjacency List\n");

for(k=0;k<G->e;k++) { //建立边表

scanf("%d%d",&i,&j); //读入边（Vi，Vj）的顶点对序号

s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成边表结点

s->adjvex=j; //邻接点序号为j

s->next=G->adjlist[i].firstedge;

G->adjlist[i].firstedge=s; //将新结点*S插入顶点Vi的边表头部

s=(EdgeNode *)malloc(sizeof(EdgeNode));

s->adjvex=i; //邻接点序号为i

s->next=G->adjlist[j].firstedge;

G->adjlist[j].firstedge=s; //将新结点*S插入顶点Vj的边表头部

}

}

//=========定义标志向量，为全局变量=======

typedef enum{FALSE,TRUE} Boolean;

Boolean visited[MaxVertexNum];

//========DFS：深度优先遍历的递归算法======

void DFSM(ALGraph *G,int i)

{ //以Vi为出发点对邻接链表表示的图G进行DFS搜索

EdgeNode *p;

printf("%c",G->adjlist[i].vertex); //访问顶点Vi

visited[i]=TRUE; //标记Vi已访问

p=G->adjlist[i].firstedge; //取Vi边表的头指针

while(p) { //依次搜索Vi的邻接点Vj，这里j=p->adjvex

//以下3行代码有一处错误

if(! visited[p->adjvex]) //若Vj尚未被访问

DFS(G,p->adjvex); //则以Vj为出发点向纵深搜索

p=p->next; //找Vi的下一个邻接点

}

}

void DFS(ALGraph *G)

{

int i;

for(i=0;i<G->n;i++)

visited[i]=FALSE; //标志向量初始化

for(i=0;i<G->n;i++)

if(!visited[i]) //Vi未访问过

DFSM(G,i); //以Vi为源点开始DFS搜索

}

//==========BFS：广度优先遍历=========

void BFS(ALGraph *G,int k)

{ //以Vk为源点对用邻接链表表示的图G进行广度优先搜索

int i,f=0,r=0;

EdgeNode *p;

int cq[MaxVertexNum]; //定义FIFO队列

for(i=0;i<G->n;i++)

visited[i]=FALSE; //标志向量初始化

for(i=0;i<=G->n;i++)

cq[i]=-1; //初始化标志向量

printf("%c",G->adjlist[k].vertex); //访问源点Vk

visited[k]=TRUE;

cq[r]=k; //Vk已访问，将其入队。注意，实际上是将其序号入队

while(cq[f]!=-1)

{ //队列非空则执行

i=cq[f]; f=f+1; //Vi出队

p=G->adjlist[i].firstedge; //取Vi的边表头指针

while(p)

{ //依次搜索Vi的邻接点Vj（令p->adjvex=j）

if(!visited[p->adjvex]) { //若Vj未访问过

printf("%c",G->adjlist[p->adjvex].vertex); //访问Vj

visited[p->adjvex]=TRUE;

//以下3行代码有一处错误

r=r+1; cq[r]=p->adjvex; //访问过的Vj入队

}

p=p->next->next; //找Vi的下一个邻接点

}

}//endwhile

}

//==========主函数===========

void main()

{

int i;

ALGraph *G;

G=(ALGraph *)malloc(sizeof(ALGraph));

CreatALGraph(G);

printf("Print Graph DFS: ");

DFS(G);

printf("\n");

printf("Print Graph BFS: ");

BFS(G,3);

printf("\n");

}

执行顺序：*

Input VertexNum(n) and EdgesNum(e): 8，9

Input Vertex string: 01234567

Input edges,Creat Adjacency List

0 1

0 2

1 3

1 4

2 5

2 6

3 7

4 7

5 6

Print Graph DFS: 02651473

Print Graph BFS: 37140265

二、实验任务*

\1. 改正程序中的错误并调试通过，测试并完成实验报告的撰写。

\2. 选做题，编写程序输出该无向网络的最小生成树以及该最小生成树的所有边。

实验七、查找算法的实现

一、实验目的

掌握顺序和二分查找算法的基本思想及其实现方法。

二、实验要求

问题描述：对给定的任意数组（设其长度为n），分别用顺序和二分查找方法在此数组中查找与给定值k相等的元素。

顺序查找基本思想：从查找表的一端开始，逐个将记录的关键字值和给定值进行比较，如果某个记录的关键字值和给定值相等，则称查找成功；否则，说明查找表中不存在关键字值为给定值的记录，则称查找失败。

二分查找基本思想：先取查找表的中间位置的关键字值与给定关键字值作比较，若它们的值相等，则查找成功；如果给定值比该记录的关键字值大，说明要查找的记录一定在查找表的后半部分，则在查找表的后半部分继续使用折半查找；若给定值比该记录的关键字值小，说明要查找的记录一定在查找表的前半部分，则在查找表的前半部分继续使用折半查找。…直到查找成功，或者直到确定查找表中没有待查找的记录为止，即查找失败。

两者比较：

（1）顺序查找的查找效率很低；但是对于待查记录的存储结构没有任何要求，既适用于顺序存储，又适用于链式存储；当待查表中的记录个数较少时，采用顺序查找法较好。

（2）二分查找的平均查找长度较小，查找速度快；但它只能用于顺序存储，不能用于链式存储；且要求表中的记录是有序的。对于不常变动的有序表，采用折半查找法是较为理想的。

三、算法思想与算法描述

1、顺序查找，在顺序表R[0..n-1]中查找关键字为k的记录，成功时返回找到的记录位置，失败时返回-1，具体的算法如下所示：

int SeqSearch(SeqList R[],int n,KeyType k)
{
int i=0;
while(i<n&&R[i].key!=k)
{
printf("%d",R[i].key);
i++;

}
if(i>=n)
return -1;
else
{
printf("%d",R[i].key);
return i;
}
}

程序代码

#include <stdio.h>
#define KeyType int
#define MAX_SIZE 10
//顺序表结构体
typedef struct{
    int oder;
    KeyType key;
}SeqList;
//顺序查找函数
int SeqSearch(SeqList R[],int n,KeyType k)
{
    int i=0;
    while(i<=n&&R[i].key!=k)
    {
        //printf("%d:%d\\n",i,R[i].key);
        i++;
    }
    if(i > n)
        return -1;
    else
    {
        printf("%d！",R[i].key);
        return i;
    }
}

int main() {
		//初始化待查找数据
    SeqList source[]={{0,9},{1,13},{2,15},{3,7},{4,45},{5,32},{6,56},{7,89},{8,60},{9,36}};
    //查找的数据
		int finder;
		//返回的下标
    int result=-1;
		//查找开始
    printf("程序开始***************************\\n请输入查找内容：");
    scanf("%d",&finder);
		//返回查找内容 -1：未找到 否则返回下标志
    result= SeqSearch(source,9,finder);
    if (result == -1)printf("未查找到相关信息");
    else printf("所查找元素下标值为%d",result);
    return 0;
}

2、二分查找，在有序表R[0..n-1]中进行二分查找，成功时返回记录的位置，失败时返回-1，具体的算法如下：

int BinSearch(SeqList R[],int n,KeyType k)
{
int low=0,high=n-1,mid,count=0;
while(low<=high)
{
mid=(low+high)/2;
printf("第%d次查找：在[ %d ,%d]中找到元素R[%d]:%d\\n ",++count,low,high,mid,R[mid].key);
if(R[mid].key==k)
return mid;
if(R[mid].key>k)
high=mid-1;
else
low=mid+1;
}
return -1;
}
#include <stdio.h>
#define KeyType int
#define MAX_SIZE 10
//顺序表结构体
typedef struct{
    int oder;
    KeyType key;
}SeqList;
int BinSearch(SeqList R[],int n,KeyType k)
{
    int low=0,high=n-1,mid,count=0;
    while(low<=high)
    {
        mid=(low+high)/2;
        printf("第%d次查找：在[ %d ,%d]中找到元素R[%d]:%d\\n ",++count,low,high,mid,R[mid].key);
        if(R[mid].key==k)
            return mid;
        if(R[mid].key>k)
            high=mid-1;
        else
            low=mid+1;
    }
    return -1;
}
int main() {
    //初始化待查找数据
    SeqList source[]={{0,5},{1,7},{2,9},{3,12},{4,15},{5,18},{6,20},{7,22},{8,25},{9,30},{10,100}};
    //查找的数据
    int finder;
    //返回的下标
    printf("*********************程序开始***************************\\n");
    int result=-1;
    //查找开始
    printf("请输入查找内容：");
    scanf("%d",&finder);
    while (finder != '-1'){
        //返回查找内容 -1：未找到 否则返回下标志
        result= BinSearch(source,10,finder);
        if (result == -1)printf("未查找到相关信息\\n");
        else printf("所查找元素下标值为%d\\n",result);
        printf("请输入查找内容：");
        scanf("%d",&finder);
    }
    return 0;
}

C方式实现

#include <stdio.h>
#define KeyType int
#define MAX_SIZE 10
//顺序表结构体
typedef struct{
    int oder;
    KeyType key;
}SeqList;

/*
 * 顺序查找
 * R[] 数组 待查找数据组
 * n int 待查找数据长度
 * k KeyType查找数据
 * */
int SeqSearch(SeqList R[],int n,KeyType k)
{
    int i=0;
    while(i<=n&&R[i].key!=k)
    {
        //printf("%d:%d\\n",i,R[i].key);
        i++;
    }
    if(i > n)
        return -1;
    else
    {
        printf("%d！",R[i].key);
        return i;
    }
}

/*
 * 折半方查找
 * R[] 数组 待查找数据组
 * n int 待查找数据长度
 * k KeyType查找数据
 * */
int BinSearch(SeqList R[],int n,KeyType k)
{
    int low=0,high=n-1,mid,count=0;
    while(low<=high)
    {
        mid=(low+high)/2;
        printf("第%d次查找：在[ %d ,%d]中找到元素R[%d]:%d\\n ",++count,low,high,mid,R[mid].key);
        if(R[mid].key==k)
            return mid;
        if(R[mid].key>k)
            high=mid-1;
        else
            low=mid+1;
    }
    return -1;
}

/*
 * 插值查找
 * R[] 数组 待查找数据组
 * n int 待查找数据长度
 * k KeyType查找数据
 * */
int interpolationSearch(SeqList R[],int n,KeyType k)
{
    int low=0,high=n-1,mid,count=0;
    while (low < high) {
        mid = low + (high - low) * (k - R[low].key) / (R[high].key - R[low].key);
        printf("第%d次查找：在[ %d ,%d]中找到元素R[%d]:%d\\n ",++count,low,high,mid,R[mid].key);
        // mid = (high + low) / 2;// 折半下标
        if (k > R[mid].key) {
            low = mid + 1; // 关键字比 折半值 大，则最小下标 调成 折半下标的下一位
        } else if (k < R[mid].key) {
            high = mid - 1;// 关键字比 折半值 小，则最大下标 调成 折半下标的前一位
        } else {
            return mid; // 当 key == a[mid] 返回 折半下标
        }
    }
    return -1;
    return -1;
}

int main() {
    //初始化待查找数据
    SeqList source1[]={{0,9},{1,13},{2,15},{3,7},{4,45},{5,32},{6,56},{7,89},{8,60},{9,36}};
    SeqList source2[]={{0,5},{1,7},{2,9},{3,12},{4,15},{5,18},{6,20},{7,22},{8,25},{9,30},{10,100}};
    SeqList* source;
    //查找的数据
    int finder;
    //数据大小
    int size;
    //查找方式
    int way;
    //查找数据选择
    int data;
    //返回的下标
    printf("程序开始***************************\\n");
    int result=-1;
    //查找开始
    printf("请输入查找内容：");
    scanf("%d",&finder);
    printf("请选择查找方式：\\n1:顺序查找\\n2:折半查找\\n3:插值查找");
    scanf("%d",&way);
    printf("请选择待查找数组");
    scanf("%d",&data);
    if (data == 1){
        source = source1;
        size=9;
    }else if (data ==2){
        source = source2;
        size = 10;
    }
    while (finder != '-1'){
        //返回查找内容 -1：未找到 否则返回下标志
        switch (way) {
            case 1:result= SeqSearch(source,size,finder);break;
            case 2:result= BinSearch(source,size,finder);break;
            case 3:result= interpolationSearch(source,size,finder);break;
            default:printf("输入错误,程序结束");
        }
        if (result == -1)printf("未查找到相关信息\\n");
        else printf("所查找元素下标值为%d\\n",result);
        printf("请输入查找内容：");
        scanf("%d",&finder);
        printf("请选择查找方式：\\n1:顺序查找\\n2:折半查找\\n3:插值查找");
        scanf("%d",&way);
    }
    return 0;
}

Java方法实现

package com.finder.oder;

import java.util.Scanner;

public class Main{
    public static void main(String args[]){
        int[] data = {9,13,15,7,45,32,56,89,60,36};
        int finder;
        int way;
        int result=-1;
        System.out.println("请输入要查找的数据（int）");
        Scanner input = new Scanner(System.in);
        finder = input.nextInt();
        way = input.nextInt();
        System.out.println("请选择查找方法\\n1:顺序查找\\n2:优化顺序查找\\n3：折半查找\\n4.插值查找");
        switch (way){
            case 1:result = sequentialSearch(data,finder);break;
            case 2:result = sequentialSearch2(data,finder);break;
            case 3:result = binarySearch(data,finder);break;
            case 4:result = interpolationSearch(data,finder);break;
            default:System.out.println("输入错误，程序结束");
        }
        if (result != -1)System.out.println("下标为"+result);
				else System.out.println("未查找到此数据");
    }

    /**
     * 顺序查找
     * @param a 数组
     * @param key 待查找关键字
     * @return 关键字下标
     */
    public static int sequentialSearch(int[] a, int key) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] == key)
                return i;
        }
        return -1;
    }
    /**
     * 有哨兵顺序查找
     * @param a 数组(下标为0存放哨兵元素)
     * @param key 待查询关键字
     * @return 关键字下标 返回0 则未找到
     */
    public static int sequentialSearch2(int[] a, int key) {
        int index = a.length - 1;
        a[0] = key;// 将下标为0的数组元素设置为哨兵
        while (a[index] != key) {
            index--;
        }
        return index;
    }
    /**
     * 折半查找
     * @param a 数组
     * @param key 待查找关键字
     * @return 返回折半下标， -1表示不存在该关键字
     */

    public static int binarySearch(int[] a, int key) {
        int low, mid, high;
        low = 0;// 最小下标
        high = a.length - 1;// 最大小标
        while (low <= high) {
            mid = (high + low) / 2;// 折半下标
            if (key > a[mid]) {
                low = mid + 1; // 关键字比 折半值 大，则最小下标 调成 折半下标的下一位
            } else if (key < a[mid]) {
                high = mid - 1;// 关键字比 折半值 小，则最大下标 调成 折半下标的前一位
            } else {
                return mid; // 当 key == a[mid] 返回 折半下标
            }
        }
        return -1;
    }
    /**
     * 插值查找
     * @param a 数组
     * @param key 待查找关键字
     * @return 返回折半下标， -1表示不存在该关键字
     */
    public static int interpolationSearch(int[] a, int key) {
        int low, mid, high;
        low = 0;// 最小下标
        high = a.length - 1;// 最大小标
        while (low < high) {
            mid = low + (high - low) * (key - a[low]) / (a[high] - a[low]);
            // mid = (high + low) / 2;// 折半下标
            if (key > a[mid]) {
                low = mid + 1; // 关键字比 折半值 大，则最小下标 调成 折半下标的下一位
            } else if (key < a[mid]) {
                high = mid - 1;// 关键字比 折半值 小，则最大下标 调成 折半下标的前一位
            } else {
                return mid; // 当 key == a[mid] 返回 折半下标
            }
        }
        return -1;
    }
}

四、实验任务

认真阅读与理解实验内容的具体要求，参考教材相关章节，编写实验程序并上机调试与测试，完成实验报告的撰写。

1.已知含有10个整数的查找表如下：（9，13，15，7，45，32，56，89，60，36），从键盘上输入一个整数，用顺序查找的方法在查找表中查找该整数。若存在，输出该元素的下标值，否则，给出相应的信息。

2.对有序数据表(5，7，9，12，15，18，20，22，25，30，100)，编写程序按折半查找方法查找12和28。

实验八、排序算法的实

一、实验目的

掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；
深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；
了解各种方法的排序过程及其时间复杂度的分析方法。

二、实验要求

统计成绩：给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法：

（1）按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；

（2）按名次列出每个学生的姓名与分数。

三、实验步骤

1.定义结构体。

typedef  struct  student{ 
	char  name[8];
	int  score; 
}studentImform,*studentPtr；
typedef struct student{
    char name[8];
    int score;
}studentImform,*studentPtr;

2.定义结构体数组。

//直接数组
struct student students[MAX_SIZE];
studentImform students[MAX_SIZE];
//malloc 分配
studentPtr students = (studentPtr)malloc(sizeof(studentImform));
studentPtr students = (studentPtr)malloc(MAX_SIZE*sizeof(studentImform));
//直接数组
struct student Students[MAX_SIZE];
studentImform Students[MAX_SIZE];
studentImform Students[N];//N确定后c89\\99标准中不支持

//动态分配
studentPtr Students = (studentPtr)malloc(sizeof(studentImform));
studentPtr Students = (studentPtr)malloc(sizeof(studentImform)*MAX_SIZE);
studentPtr Students = (studentPtr)malloc(sizeof(studentImform)*N);//N确定后

3.编写主程序，对数据进行排序。

4.要求至少采用两种排序算法实现，如直接插入排序、快速排序等算法。

4.1直接插入排序基本思想

排序过程：默认初始数组下标为0的数字为有序序列，每次从后续数组中顺序拿一个数字，将这个数字放到前面的有序序列中，放的位置要确保放完之后依旧是有序的。

将n个元素的数列分为已有序和无序两个部分，

插入排序过程示例如下所示：

a1，a2，a3，a4，…，an

a1，a2，a3，a4，…，an

a1⑴，a2⑴，a3⑴，a4⑴…，an⑴

a1⑴，a2⑴，a3⑴，a4⑴…，an⑴

…

…

a1(n−1），a2(n−1)，…,an(n−1)

a1(n−1），a2(n−1)，…,an(n−1)

每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。

void insertionSort(int *number,int n)
{
    int i=0,ii=0,temp=0;
    for(i=1;i<n;i++)  //循环遍历
    {
        temp=number[i];  //将temp每一次赋值为number[i]
        ii=i-1;
        while(ii>=0 && temp>number[ii])   //这里改顺序 (temp后的)"<"为小到大，">"为大到小
        {
            number[ii+1]=number[ii];    //将大的元素往前放
            ii--;
        }
        number[ii+1]=temp;
    }
}

4.2 快速排序基本思想

基本思想：是对冒泡排序的一种改进。1快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

排序过程：对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设rp=r[s]，x=rp.key。初始时令i=s,j=t。首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换。再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换。重复上述两步，直至i=j为止。再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止。

排序演示示例

假设用户输入了如下数组：

Untitled

创建变量 i=0 （指向第一个数据）,j=5(指向最后一个数据), k=6(赋值为第一个数据的值)。

我们要把所有比k小的数移动到k的左面，所以我们可以开始寻找比6小的数，从j开始，从右往左找，不断递减变量j的值，我们找到第一个下标3的数据比6小，于是把数据3移到下标0的位置，把下标0的数据6移到下标3，完成第一次比较：

Untitled

i=0 , j=3 , k=6

接着，开始第二次比较，这次要变成找比k大的了，而且要从前往后找了。递加变量i，发现下标2的数据是第一个比k大的，于是用下标2的数据7和j指向的下标3的数据的6做交换，数据状态变成下表：

Untitled

i=2 , j=3 ,k=6

称上面两次比较为一个循环。

接着，再递减变量jj，不断重复进行上面的循环比较。

在本例中，我们进行一次循环，就发现ii和jj “碰头”了：他们都指向了下标22。于是，第一遍比较结束。得到结果如下，凡是k(=6)k(=6)左边的数都比它小，凡是kk右边的数都比它大：

Untitled

如果ii和jj没有碰头的话，就递加i找大的，还没有，就再递减j找小的，如此反复，不断循环。注意判断和寻找是同时进行的。

然后，对k两边的数据，再分组分别进行上述的过程，直到不能再分组为止。

注意：第一遍快速排序不会直接得到最终结果，只会把比kk大和比kk小的数分到kk的两边。为了得到最后结果，需要再次对下标两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。

void quickSortIn(int left,int right,int a[]);
{
    if(left>=right)  //如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了
        return ;
    int i=left;     //将区间记录下来 
    int j=right;
    int key=a[i];    //记录参考值 
    while(i<j)   //控制在当组内寻找一遍
    {
        while(i<j&&key<=a[j])   //而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升序还是降序）2，没有符合条件1的，并且i与j的大小没有反转 
            j--;    //向前寻找
        a[i]=a[j];     //找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是a[left]，那么就是给key）
        while(i<j&&key>=a[i])   //这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反
            i++;
        a[j]=a[i];
    }
    a[i]=key;                  //当在当组内找完一遍以后就把中间数key回归
    quickSortIn(left,i-1,a);     //最后用同样的方式对分出来的左边的小组进行同上的做法
    quickSortIn(i+1,right,a);    //用同样的方式对分出来的右边的小组进行同上的做法
                               //当然最后可能会出现很多分左右，直到每一组的i = j 为止
}

void quickSort(int a[],int n){
	quickSortIn(0,n,int a[]);
}

4.3 选择排序

是一种简单直观的排序算法。1它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。

void selectSort(int R[],int n)    //定义选择排序函数"select_sort"
{
    int i, j, k, index;
    for (i = 0; i < n - 1; i++) {
        k = i;
        for (j = i + 1; j < n; j++)    //j初始不为0，冒泡初始为0，所以选排比冒泡快，但不稳定
        {
            if (R[j] > R[k])   //顺序从这里改顺序 小到大"<",大到小">"
                k = j;      //这里是区分冒泡排序与选择排序的地方，冒泡没这句
        }
        index = R[i];   //交换R[i]与R[k]中的数
        R[i] = R[k];    //简单的交换c=a,a=b,b=c
        R[k] = index;
    }
}

4.4冒泡排序

它重复地走访过要排序的元素列，一次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

冒泡排序算法的原理如下：

1.比较相邻的元素。如果第一个比第二个大，就交换他们两个，这样是从小到大排。

(如果第一个比第二个小，交换 , 那就是从大到小排)

2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3.针对所有的元素重复以上的步骤，除了最后一个。

4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

void bubbleSort(int a[], int n)    //下面是函数bubble_sort的程序 
{
    int i,j,temp;    //定义三个整型变量 
    for (j=0;j<n-1;j++)    //用一个嵌套循环来遍历一遍每一对相邻元素 （所以冒泡函数慢嘛，时间复杂度高）  
    {                           
        for (i=0;i<n-1-j;i++)
        {
            if(a[i]>a[i+1])  //从大到小排就把左边的">"改为"<" ！！！
            {
                temp=a[i];      //a[i]与a[i+1](即a[i]后面那个) 交换
                a[i]=a[i+1];    //基本的交换原理"c=a;a=b;b=c" 
                a[i+1]=temp;
            }
        }
    }    
}

完整源代码

#include <stdio.h>
#include <stdlib.h>

//学生最大输入量
#define MAX_SIZE 100

//学生信息结构体
typedef struct student{
    char name[8];
    int score;
}studentImform,*studentPtr;

//插入排序
void insertionSort(studentPtr number,int n)
{
    int i=0,ii=0;
    studentImform temp;
    for(i=1;i<n;i++)
    {
        temp = number[i];
        ii=i-1;
        while(ii>=0 && temp.score >number[ii].score)
        {
            number[ii+1]=number[ii];
            ii--;
        }
        number[ii+1]=temp;
    }
}
void bubbleSort(studentPtr a, int n)
{
    int i,j;
    studentImform temp;
    for (j=0;j<n-1;j++)
    {
        for (i=0;i<n-1-j;i++)
        {
            if(a[i].score < a[i+1].score)
            {
                temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
            }
        }
    }
}

//选择排序法
void selectSort(studentPtr R,int n)
{
    int i, j, k;
    studentImform index;
    for (i = 0; i < n - 1; i++) {
        k = i;
        for (j = i + 1; j < n; j++)
        {
            if (R[j].score > R[k].score)
                k = j;
        }
        index = R[i];
        R[i] = R[k];
        R[k] = index;
    }
}

//快速排序法
void quicksortIn(int left,int right,studentPtr a)
{
    if(left >= right) return ;
    int i=left;
    int j=right;

    studentImform key=a[i];

    while(i<j)
    {
    while(i<j && key.score >= a[j].score)
        j--;
        a[i]=a[j];
    while(i<j && key.score <= a[i].score)
        i++;
        a[j]=a[i];
    }
    a[i] = key;
    quicksortIn(left,i-1,a);
    quicksortIn(i+1,right,a);
    }
void quickSort(studentPtr a,int n){
    quicksortIn(0,n+1,a);
}
int main(){
    //定义变量
    int N,i=0,way;
    studentImform Students[MAX_SIZE] = {0};
    //输入信息
    printf("请输入学生数量\\n");
    scanf("%d",&N);

    while (N<=0){
        printf("输入不合法，请重新输入\\n");
        scanf("%d",&N);
    }
    printf("请依次输入%d学生的姓名及成绩\\n",N);
    for (int j= 0; j < N; ++j) {
        scanf("%s",Students[j].name);
        scanf("%d",&Students[j].score);
        while (Students[i].name == NULL || Students[j].score<0){
            printf("输入不合法，请重新输入%d位同学的信息\\n",j+1);
            scanf("%s",Students[j].name);
            scanf("%d",&Students[j].score);
        }
    }
    printf("请选择排序方式:\\n1.直接插入排序\\n2.快速排序\\n3.选择排序\\n4.\\n");
    scanf("%d",&way);
    switch (way) {
        case 1:
            insertionSort(Students,N);
            break;
        case 2:
            quickSort(Students,N);
            break;
        case 3:
            selectSort(Students,N);
            break;
        case 4:
            bubbleSort(Students,N);
        default:
            printf("输入有误\\n");
    }
    printf("\\t序号  \\t姓名\\t:  \\t分数\\n");
    for (int j = 0; j < N; ++j) {
        printf("\\t%-d\\t%-s\\t:\\t%-d\\n",j,Students[j].name,Students[j].score);
    }

}

老师标准子函数

四、实验任务

认真阅读与理解实验内容的具体要求，参考教材相关章节，编写实验程序并上机调试与测试，完成实验报告的撰写。

数据结构与算法

#工具 #论文 #公式 #latex

数据结构与算法实验指导书

https://tanzicai.github.io/2021/03/21/数据结构与算法实验指导书/

作者

谭自财

发布于

2021年3月21日

更新于

2022年12月20日

许可协议

数据结构(C语言)笔记上一篇

Tex行内公式说明下一篇

数据结构与算法实验指导书

《数据结构》上机实验内容和要求

实验报告要求

👦实验一、顺序表的实现及应用

一、实验目的

二、实验要求

三、程序代码

合并函数_WriteByLiyihan

四、实验任务

实验二 链表的实现及应用

一、实验目的

二、实验要求

三、程序代码：

三、实验任务

实验三、栈的实现及应用

一、实验目的

二、实验要求

三、解题参考思路

四、实验任务

五、实验思路

栈的定义

栈的操作

符号优先级判断函数

主函数思路1

主函数思路2：数据结构指导书要求

实验四、队列的实现及应用

三、解题参考思路

一、数据描述（结构体定义）

二、存取操作（队列操作函数）

三、主函数流程

四、实验任务

五、注意点

实验五、二叉树操作及应用

一、 实验目的

二、相关知识

遍历

二、 实验要求

三、 实验任务：

实验六、图的遍历操作及应用

实验七、查找算法的实现

C方式实现

Java方法实现

实验八、排序算法的实

一、实验目的

二、实验要求

三、实验步骤

1.定义结构体。

2.定义结构体数组。

3.编写主程序，对数据进行排序。

4.要求至少采用两种排序算法实现，如直接插入排序、快速排序等算法。

4.3 选择排序

4.4冒泡排序

完整源代码

老师标准子函数

实验二链表的实现及应用

一、实验目的

二、实验要求

三、实验任务：