数据结构课程实验一至实验五总集

实验一：链表

一、实验目的
1、掌握线性表中元素的前驱、后续的概念。
2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。
3、对线性表相应算法的时间复杂度进行分析。
4、理解顺序表、链表数据结构的特点（优缺点）。

二、实验预习
说明以下概念
1、线性表：
线性表是一种抽象的数据结构，其中元素之间存在顺序关系，即每个元素都有唯一的驱和后继，除了第一个元素没有前驱，最后一个元素没有后继。线性表可以用于表示一组有序的数据元素。
2、顺序表：
顺序表是一种线性表的物理存储结构，它使用一段连续的内存空间来存储元素，元素在内存中的相对位置反映了它们在逻辑上的顺序关系。数组是顺序表的一种实现方式，其中元素在内存中是紧密相邻排列的。
3、链表：
链表是一种线性表的物理存储结构，它使用一组节点来存储元素，其中每个节点包含数据域和指针域。数据域存储元素的值，而指针域则指向下一个节点，从而构建起元素之间的逻辑关系。链表相比于顺序表更灵活，因为它不要求内存空间是连续的，节点可以动态分配。链表可以分为单向链表、双向链表和循环链表等不同类型。

三、实验内容和要求
1、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。
#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1

#define INIT_SIZE 5 /初始分配的顺序表长度/
#define INCREM 5 /溢出时，顺序表长度的增量/
typedef int ElemType; /定义表元素的类型/
typedef struct Sqlist{
ElemType *slist; /存储空间的基地址/
int length; /顺序表的当前长度/
int listsize; /当前分配的存储空间/
}Sqlist;

int InitList_sq(Sqlist L); / 初始化顺序表 */
int CreateList_sq(Sqlist *L,int n); /*创建顺序表，添加数据 */
int ListInsert_sq(Sqlist *L,int i,ElemType e);/*插入元素 */
int PrintList_sq(Sqlist *L); /输出顺序表的元素/
int ListDelete_sq(Sqlist *L,int i); /删除第i个元素/
int ListLocate(Sqlist *L,ElemType e); /查找值为e的元素/

int InitList_sq(Sqlist L){
L->slist=(ElemType)malloc(INIT_SIZE*sizeof(ElemType));
if(!L->slist) return ERROR; //判断创建空间是否完成
L->length=0;
L->listsize=INIT_SIZE;
return OK;
}/InitList/

int CreateList_sq(Sqlist *L,int n){
ElemType e;
int i;
for(i=0;i<n;i++){
printf(“input data %d：”,i+1);
scanf(“%d”,&e);
if(!ListInsert_sq(L,i+1,e))
return ERROR;
}
return OK;
}/CreateList/

/输出顺序表中的元素/
int PrintList_sq(Sqlist *L){
int i;
for(i=1;i<=L->length;i++)
printf(“%5d”,L->slist[i-1]);
return OK;
}/PrintList/

int ListInsert_sq(Sqlist L,int i,ElemType e){
int k;
if(i<1||i>L->length+1)
return ERROR;
if(L->length>=L->listsize){
L->slist=(ElemType)realloc(L->slist,
(INIT_SIZE+INCREM)*sizeof(ElemType));
if(!L->slist)
return ERROR;
L->listsize+=INCREM;
}//扩充
for(k=L->length-1;k>=i-1;k–){
L->slist[k+1]= L->slist[k];
}
L->slist[i-1]=e;
L->length++;
return OK;
}/ListInsert/
int ListDelete_sq(Sqlist *L,int i){/在顺序表中删除第i个元素/
int k;
if(i<1||i>L->listsize)
return ERROR;
for(k=i-1;k<length;k++){
L->slist[k]=L->slist[k+1];
}
L->length–;
return OK;
}
/在顺序表中查找指定值元素，返回其序号/
int ListLocate(Sqlist *L,ElemType e){
int i;
for(i=0;ilength;i++){
if(L->length[i]==e)
return i+1;
}
}
int main(){
Sqlist sl;
int n,m,k;
printf(“please input n:”); /输入顺序表的元素个数/
scanf(“%d”,&n);
if(n>0){
printf(“\n1-Create Sqlist:\n”);
InitList_sq(&sl);
CreateList_sq(&sl,n);
printf(“\n2-Print Sqlist:\n”);
PrintList_sq(&sl);
printf(“\nplease input insert location and data:(location,data)\n”);
scanf(“%d,%d”,&m,&k);
ListInsert_sq(&sl,m,k);
printf(“\n3-Print Sqlist:\n”);
PrintList_sq(&sl);
printf(“\n”);}
else printf(“ERROR”);return 0;}
 运行结果

 算法分析
答：插入一次的时间复杂度为O(n)。

2、为第1题补充删除和查找功能函数，并在主函数中补充代码验证算法的正确性。
删除算法代码：
int ListDelete_sq(Sqlist *L,int i){
int k;
if(i<1||i>L->listsize)
return ERROR;
for(k=i-1;klength;k++)
L->slist[k]=L->slist[k+1];
L->length–;
return OK;
}
 运行结果

 算法分析
答：删除操作一次时间复杂度为O(n)。

查找算法代码：
答：
int ListLocate(Sqlist *L,ElemType e){
ElemType *p;
int i=1;
p=L->slist;
while(i<=L->length)
{
if((*p++)!=e)
;
else
printf(“%d “,i);
++i;
}
printf(”\n”);
return OK;
}

 运行结果

 算法分析
答：查找操作一次时间复杂度为O(n)。

3、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。
#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1
typedef int ElemType; /定义表元素的类型/
typedef struct LNode{ /线性表的单链表存储/
ElemType data;
struct LNode *next;
}LNode,*LinkList;

LinkList CreateList(int n); /建立带头结点的空链表并存入n个元素/
void PrintList(LinkList L); /输出带头结点单链表的所有元素/
int GetElem(LinkList L,int i,ElemType *e); /当带头结点的空链表第i个元素存在时赋值给e并返回OK，否则返回ERROR/

LinkList CreateList(int n){
LNode *p,*q,*head;
int i;
head=(LinkList)malloc(sizeof(LNode)); head->next=NULL;
p=head;
for(i=0;i<n;i++){
q=(LinkList)malloc(sizeof(LNode)); printf(“input data %i:”,i+1);
scanf(“%d”,&q->data); /输入元素值/
q->next=NULL; /结点指针域置空/
p->next=q; /新结点连在表末尾/
p=q;
}
return head;
}/CreateList/

void PrintList(LinkList L){
LNode *p;
p=L->next; /p指向单链表的第1个元素/
while(p!=NULL){
printf(“%5d”,p->data);
p=p->next;
}
}/PrintList/

int GetElem(LinkList L,int i,ElemType *e){
LNode *p;int j=1;
p=L->next;
while(p&&j<i){
p=p->next;j++;
}
if(!p||j>i)
return ERROR;
*e=p->data;
return OK;
}/GetElem/

int main(){
int n,i;ElemType e;
LinkList L=NULL; /定义指向单链表的指针/
printf(“please input n:”); /输入单链表的元素个数/
scanf(“%d”,&n);
if(n>0){
printf(“\n1-Create LinkList:\n”);
L=CreateList(n);
printf(“\n2-Print LinkList:\n”);
PrintList(L);
printf(“\n3-GetElem from LinkList:\n”);
printf(“input i=”);
scanf(“%d”,&i);
if(GetElem(L,i,&e))
printf(“No%i is %d”,i,e);
else
printf(“not exists”);
}else
printf(“ERROR”);
return 0;
}
 运行结果

 算法分析
答：
(1)创建链表（CreateList）： 包括为n个节点分配内存并一次遍历整个列表。 时间复杂度：O(n)
(2)打印链表（PrintList）： 包括一次遍历整个链表。 时间复杂度：O(n)
(3)从链表中获取元素（GetElem）： 包括遍历列表直到达到第i个元素。 时间复杂度：O(i)
(4) 程序的总体时间复杂度是 O(n)。
4、为第3题补充插入功能函数和删除功能函数。并在主函数中补充代码验证算法的正确性。
插入算法代码：
答：
int InsertElem(LinkList L,int i,ElemType e){
int j=0;
LinkList p = L,s;
while(p&&j<i-1){
p=p->next;
j++;
}
if(!p||j>i-1){
printf(“the node isn’t exist\n”);
return ERROR;
}
s = (LinkList)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}

 运行结果

 算法分析
答：插入的时间复杂度为O(n)其中查找的时间复杂度为O(n),插入的时间复杂度为O(1)。

删除算法代码：
答：
int DeleteElem(LinkList L,int i){
int j=0;
LinkList p = L,q;
while(p->next&&j<i-1){
p=p->next;
j++;
}
if(!(p->next)||j>i-1){
printf(“the node is not exist\n”);
return ERROR;
}
q= p->next;
p->next=q->next;
free(q);
return OK;
}

 运行结果

 算法分析
答：操作一次的时间复杂度是O(n)其中查找消耗的时间为O(n)删除的时间复杂度为O(1)；

以下为选做实验：
5、循环链表的应用（约瑟夫回环问题）
n个数据元素构成一个环，从环中任意位置开始计数，计到m将该元素从表中取出，重复上述过程，直至表中只剩下一个元素。
提示：用一个无头结点的循环单链表来实现n个元素的存储。
 算法代码
答：
#include <stdio.h>
#include
#include <stdlib.h>
#include <malloc.h>
#define ERROR 0
#define OK 1
typedef int ElemType; /定义表元素的类型/
typedef struct LNode /线性表的单链表存储/
{
ElemType data;
struct LNode *next;
} LNode,*LinkList;

LinkList CreateList(int n)
{
LNode *p,*q,*head;
int i;
printf(“输入初始的n个数据:\n”);
head=(LinkList)malloc(sizeof(LNode));
p = head;
printf(“输入第1个数据：”);
scanf(“%d”,&head->data);
for(i = 1; i < n; i++){
q = (LinkList)malloc(sizeof(LNode));
printf(“输入第%d个数据：”,i+1);
scanf(“%d”,&q->data);
p->next = q;
p = q;
}
p->next = head;
return head;
}/CreateList/

int DeleteEem(LinkList L)
{
LNode *temp = L,*fnode;
while(temp->next != L){
temp = temp->next;
}
fnode = temp;
fnode->next = L->next;
free(L);
return OK;
}

void go(LinkList L,int n,int m)
{
int i,j;
LNode *p = L;
for(i = 1; i <= n - 1; i++){
for(j = 0; j < m - 1; j++){
p = p->next;
}
printf(“第%d个取出的数据:%d\n”,i,p->data);
LNode *fnode = p;
p = p->next;
DeleteEem(fnode);
}
return ;
}

int main()
{
int n,m;
LinkList L=NULL;
printf(“请输入总数据量n,以及一次循环的数量m:”);
scanf(“%d%d”,&n,&m);
printf(“\n”);
L = CreateList(n);
printf(“\n”);
go(L,n,m);
printf(“\n此时表中便只剩一个元素\n”);
return 0;
}

6、设一带头结点的单链表，设计算法将表中值相同的元素仅保留一个结点。
提示：指针p从链表的第一个元素开始，利用指针q从指针p位置开始向后搜索整个链表，删除与之值相同的元素；指针p继续指向下一个元素，开始下一轮的删除，直至p＝＝null为至，既完成了对整个链表元素的删除相同值。
 算法代码
答：
#include<stdio.h>
#include<malloc.h>
#include
#define ERROR 0
#define OK 1
typedef int ElemType; /定义表元素的类型/
typedef struct LNode /线性表的单链表存储/
{
ElemType data;
struct LNode *next;
} LNode,*LinkList;

LinkList CreateList(int n); /* 创建一个长度为n的单链表 */
void PrintList(LinkList L); /输出带头结点单链表的所有元素/
LinkList CreateList(int n)
{
LNode *p,*q,*head;
int i;
head=(LinkList)malloc(sizeof(LNode));
head->next=NULL;
p=head;
for(i=0; i<n; i++)
{
q=(LinkList)malloc(sizeof(LNode));
printf(“输入第%i个元素:”,i+1);
scanf(“%d”,&q->data); /输入元素值/
q->next=NULL; /结点指针域置空/
p->next=q; /新结点连在表末尾/
p=q;
}
return head;
}/CreateList/

void PrintList(LinkList L)
{
LNode *p;
p=L->next; /p指向单链表的第1个元素/
while(p!=NULL)
{
printf(“%5d”,p->data);
p=p->next;
}
}/PrintList/

int go(LinkList L)
{
int t;
LNode *p = L;
p = p->next;
for(;p != NULL;)
{
t = p->data;
LNode *now = p->next;
LNode *fnode = p;
for(;now != NULL;)
{
LNode *tnode = now;
if(now->data == t)
{
tnode = fnode;
fnode->next = now->next;
free(now);
}
fnode = tnode;
now = tnode->next;
}
p = p->next;
}
return OK;
}

int main()
{
int n;
LinkList L=NULL; /定义指向单链表的指针/
printf(“请输入总数据量n:”); /输入单链表的元素个数/
scanf(“%d”,&n);
printf(“\n”);
L = CreateList(n);
printf(“\n”);
printf(“删除重复元素之后：\n”);
go(L);
PrintList(L);
return 0;
}

四、实验小结
通过实验一，我深入理解了线性表、顺序表、链表的概念和特点，掌握了顺序表和链表的建立、插入、删除、查找等基本算法。对于顺序表，我了解了如何动态分配存储空间以及扩充空间的方法。在链表中，我学到了如何创建带头结点的单链表，以及插入、删除、查找等操作的实现。通过约瑟夫问题和删除重复元素的实例，我进一步加深了对链表操作的理解。这次实验提高了我的编程能力和对数据结构的理解。

五、教师评语

实验二 栈和队列

一、实验目的
1、掌握栈的结构特性及其入栈，出栈操作；
2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。

二、实验预习
说明以下概念
1、顺序栈：
顺序栈是一种基于数组实现的栈结构，具有先进后出（LIFO）的特点。栈顺序地存储在数组中，栈顶即为数组的末尾，栈底为数组的起始位置。入栈操作在栈顶进行，出栈操作同样在栈顶进行。顺序栈的优势在于直观简单，但缺点是容量固定，如果栈满需要扩容。
2、链栈：
链栈是一种基于链表实现的栈结构。每个节点包含数据元素和指向下一个节点的指针，栈顶即为链表的头节点。入栈操作将新元素作为新的头节点，出栈操作删除头节点。链栈相比于顺序栈更加灵活，不受固定容量的限制。
3、循环队列：
循环队列是一种基于数组实现的队列结构，具有先进先出（FIFO）的特点。相比于普通队列，循环队列通过循环利用数组空间，实现了更高的空间利用率。队列头尾相连形成一个环，当队尾到达数组末尾时，可以循环到数组起始位置。循环队列解决了顺序队列空间浪费的问题。
4、链队：
链队是一种基于链表实现的队列结构。与链栈类似，每个节点包含数据元素和指向下一个节点的指针。队列的头节点指向队首，尾节点指向队尾。链队相比于循环队列在动态内存管理方面更加灵活，但在高效随机访问元素方面性能稍逊于循环队列。

三、实验内容和要求
1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列1 2 3 4 5 e，运行结果如下所示。

#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1
#define STACK_INT_SIZE 10 /存储空间初始分配量/
#define STACKINCREMENT 5 /存储空间分配增量/
typedef int ElemType; /定义元素的类型/
typedef struct{
ElemType *base;
ElemType *top;
int stacksize; /当前已分配的存储空间/
}SqStack;

int InitStack(SqStack *S); /构造空栈/
int push(SqStack *S,ElemType e); /入栈/
int Pop(SqStack *S,ElemType *e); /出栈/
int CreateStack(SqStack *S); /创建栈/
void PrintStack(SqStack *S); /出栈并输出栈中元素/

int InitStack(SqStack *S){
S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType));
if(!S->base) return ERROR;
S->top=S->base;
S->stacksize=STACK_INT_SIZE;
return OK;
}/InitStack/

int Push(SqStack *S,ElemType e){
if((S->top)-(S->base)S->stacksize){
S->base=(ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));
if(S->baseNULL)
return ERROR;
S->top=S->base+S->stacksize;
S->stacksize=S->stacksize+STACKINCREMENT;
}
*S->top=e;
S->top++;
return OK;
}/Push/

int Pop(SqStack *S,ElemType *e){
if(S->top==S->base)
return ERROR;
else{
S->top–;
*e=*S->top;
return OK;
}
}/Pop/

int CreateStack(SqStack *S){
int e;
if(InitStack(S))
printf(“Init Success!\n”);
else{
printf(“Init Fail!\n”);
return ERROR;
}
printf(“input data:(Terminated by inputing a character)\n”);
while(scanf(“%d”,&e))
Push(S,e);
return OK;
}/CreateStack/

void PrintStack(SqStack *S){
ElemType e;
while(Pop(S,&e))
printf(“%3d”,e);
}/Pop_and_Print/

int main(){
SqStack ss;
printf(“\n1-createStack\n”);
CreateStack(&ss);
printf(“\n2-Pop&Print\n”);
PrintStack(&ss);
return 0;
}
 算法分析：输入元素序列1 2 3 4 5，为什么输出序列为5 4 3 2 1？体现了栈的什么特性？
答：
由于栈的特性是先进后出，所以在进行 Pop 操作时，实际上是取出了最后一个入栈的元素。在CreateStack函数中，输入的元素序列为1 2 3 4 5，但由于栈的特性，最后输入的元素5首先被压入栈底，而第一个输入的元素1最后才被压入栈顶。因此，在执行PrintStack函数进行出栈并输出时，实际上是按照后进先出的顺序输出元素，即5 4 3 2 1。这反映了栈的先进后出特性。
运行结果如下图

2、在第1题的程序中，编写一个十进制转换为二进制的数制转换算法函数（要求利用栈来实现），并验证其正确性。
 实现代码
答：
#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1
#define STACK_INT_SIZE 10 /存储空间初始分配量/
#define STACKINCREMENT 5 /存储空间分配增量/
typedef int ElemType; /定义元素的类型/
typedef struct{
ElemType *base;
ElemType *top;
int stacksize; /当前已分配的存储空间/
}SqStack;

int InitStack(SqStack *S); /构造空栈/
int push(SqStack *S,ElemType e); /入栈/
int Pop(SqStack *S,ElemType *e); /出栈/
int CreateStack(SqStack *S); /创建栈/
void PrintStack(SqStack *S); /出栈并输出栈中元素/

int InitStack(SqStack *S){
S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType));
if(!S->base) return ERROR;
S->top=S->base;
S->stacksize=STACK_INT_SIZE;
return OK;
}/InitStack/

int Push(SqStack *S,ElemType e){
if((S->top)-(S->base)S->stacksize){
S->base=(ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));
if(S->baseNULL)
return ERROR;
S->top=S->base+S->stacksize;
S->stacksize=S->stacksize+STACKINCREMENT;
}
*S->top=e;
S->top++;
return OK;
}/Push/

int Pop(SqStack *S,ElemType *e){
if(S->top==S->base)
return ERROR;
else{
S->top–;
*e=*S->top;
return OK;
}
}/Pop/

int CreateStack(SqStack *S){
int e;
if(InitStack(S))
printf(“Init Success!\n”);
else{
printf(“Init Fail!\n”);
return ERROR;
}
printf(“input data:(Terminated by inputing a character)\n”);
while(scanf(“%d”,&e))
Push(S,e);
return OK;
}/CreateStack/

void PrintStack(SqStack *S){
ElemType e;
while(Pop(S,&e))
printf(“%3d”,e);
}/Pop_and_Print/

int IsEmpty(SqStack *S){
if(S->top==S->base)
return OK;
else
return ERROR;
}

void Conversion(int N){
SqStack S;
int x;
InitStack(&S);
while(N>0){
x=N%2;
Push(&S,x);
N=N/2;
}
while(!IsEmpty(&S)){
Pop(&S,&x);
printf(“%d”,x);
}
}

int main(){
int n;
scanf(“%d”,&n);
Conversion(n);
return 0;
}

 验证
验证结果正确

3、阅读并运行程序，并分析程序功能。
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define M 20
#define elemtype char
typedef struct
{
elemtype stack[M];
int top;
}
stacknode;
void init(stacknode *st);
void push(stacknode *st,elemtype x);
void pop(stacknode *st);

void init(stacknode *st)
{
st->top=0;
}

void push(stacknode *st,elemtype x)
{
if(st->top==M)
printf(“the stack is overflow!\n”);
else
{
st->top=st->top+1;
st->stack[st->top]=x;
}
}

void pop(stacknode *st)
{
if(st->top>0) st->top–;
else printf(“Stack is Empty!\n”);
}

int main()
{
char s[M];
int i;
stacknode *sp;
printf(“create a empty stack!\n”);
sp= (stacknode *)malloc(sizeof(stacknode));
init(sp);
printf(“input a expression:\n”);
gets(s);
for(i=0;i<strlen(s);i++)
{
if(s[i]‘(’)
push(sp,s[i]);
if(s[i]‘)’)
pop(sp);
}
if(sp->top==0)
printf(“‘(‘match’)’!\n”);
else
printf(“‘(‘not match’)’!\n”);
return 0;
}

 输入：2+((c-d)*6-(f-7)*a)/6
 运行结果：

 输入：a-((c-d)*6-(s/3-x)/2
 运行结果：

 程序的基本功能：
答：基本功能是判断给定表达式中所包含的括号是否正确配对出现

以下为选做实验：
4、设计算法，将一个表达式转换为后缀表达式，并按照后缀表达式进行计算，得出表达式得结果。
 实现代码
答：
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX_EXPR_SIZE 100

typedef struct {
char *data; // 栈的数据
int top; // 栈顶指针
int maxSize; // 栈的最大容量
} Stack;

// 初始化栈
void initStack(Stack *s, int maxSize) {
s->data = (char *)malloc(sizeof(char) * maxSize);
s->top = -1;
s->maxSize = maxSize;
}

// 判断栈是否已满
int isFull(Stack *s) {
return s->top == s->maxSize - 1;
}

// 判断栈是否为空
int isEmpty(Stack *s) {
return s->top == -1;
}

// 入栈操作
void push(Stack *s, char value) {
if (!isFull(s)) {
s->data[++s->top] = value;
}
}

// 出栈操作
char pop(Stack *s) {
if (!isEmpty(s)) {
return s->data[s->top–];
}
return ‘\0’;
}

// 获取操作符的优先级
int getPriority(char op) {
if (op == ‘+’ || op == ‘-’) {
return 1;
} else if (op == ‘*’ || op == ‘/’) {
return 2;
}
return 0;
}

// 将中缀表达式转换为后缀表达式
void infixToPostfix(char *infix, char *postfix) {
Stack operatorStack;
initStack(&operatorStack, MAX_EXPR_SIZE);

int i = 0, j = 0;

while (infix[i] != '\0') {
    if (isdigit(infix[i])) {
        postfix[j++] = infix[i++];
    } else if (infix[i] == '(') {
        push(&operatorStack, infix[i++]);
    } else if (infix[i] == ')') {
        while (!isEmpty(&operatorStack) && operatorStack.data[operatorStack.top] != '(') {
            postfix[j++] = pop(&operatorStack);
        }
        pop(&operatorStack);  // 弹出 '('
        i++;
    } else {
        while (!isEmpty(&operatorStack) && getPriority(operatorStack.data[operatorStack.top]) >= getPriority(infix[i])) {
            postfix[j++] = pop(&operatorStack);
        }
        push(&operatorStack, infix[i++]);
    }
}

while (!isEmpty(&operatorStack)) {
    postfix[j++] = pop(&operatorStack);
}

postfix[j] = '\0';
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

}

// 计算后缀表达式的值
int evaluatePostfix(char *postfix) {
Stack operandStack;
initStack(&operandStack, MAX_EXPR_SIZE);

int i = 0;

while (postfix[i] != '\0') {
    if (isdigit(postfix[i])) {
        push(&operandStack, postfix[i] - '0');
    } else {
        int operand2 = pop(&operandStack);
        int operand1 = pop(&operandStack);

        switch (postfix[i]) {
            case '+':
                push(&operandStack, operand1 + operand2);
                break;
            case '-':
                push(&operandStack, operand1 - operand2);
                break;
            case '*':
                push(&operandStack, operand1 * operand2);
                break;
            case '/':
                push(&operandStack, operand1 / operand2);
                break;
        }
    }

    i++;
}

return pop(&operandStack);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

}

int main() {
char infix[MAX_EXPR_SIZE], postfix[MAX_EXPR_SIZE];

printf("请输入中缀表达式: ");
scanf("%s", infix);

infixToPostfix(infix, postfix);
printf("后缀表达式: %s\n", postfix);

int result = evaluatePostfix(postfix);
printf("结果: %d\n", result);

return 0;
1
2
3
4
5
6
7
8
9
10

}

5、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点（不设队头指针），试编写相应的置空队列、入队列、出队列的算法。
实现代码：
答：
#include<bits/stdc++.h>
#include<conio.h>
#define TRUE 1
#define FALSE 0
#define QelemType int
typedef struct Node
{
QelemType data;
struct Node *next;
} Node,*LinkQNode;
typedef struct
{
LinkQNode rear;
} LinkQueue;

void InitLinkQueue(LinkQueue &Q)
{
Q.rear=(LinkQNode)malloc(sizeof(Node));
Q.rear->next=Q.rear;
}

int IsLQEmpty(LinkQueue &Q)
{
if(Q.rear->next==Q.rear)
return TRUE;
else
return FALSE;
}

int EnLinkQueue(LinkQueue &Q,QelemType x)
{
LinkQNode NewNode;
NewNode=(LinkQNode)malloc(sizeof(LinkQNode));
if(NewNode!=NULL)
{
NewNode->data=x;
NewNode->next=Q.rear->next;
Q.rear->next=NewNode;
Q.rear=NewNode;
return TRUE;
}
else
return FALSE;
}

int DeLinkQueue(LinkQueue &Q,QelemType *x)
{
LinkQNode p;
if(Q.rear->nextQ.rear)
return FALSE;
p=Q.rear->next->next;
Q.rear->next->next=p->next;
if(Q.rearp)
Q.rear=Q.rear->next;
*x=p->data;
free§;
return TRUE;
}

int main()
{
int t;
char a;
QelemType tt;
LinkQueue Q;
InitLinkQueue(Q);
if(IsLQEmpty(Q))
printf(“该队列目前为空!\n”);
else
printf(“该队列不为空!\n”);
printf(“输入入队列的元素个数：”);
scanf(“%d”,&t);
for(int i=1; i<=t; i++)
{
QelemType ys;
printf(“\n输入第%d个入列元素：”,i);
scanf(“%d”,&ys);
if(EnLinkQueue(Q,ys))
printf(“元素%d成功入列!\n”,ys);
}
printf(“\n输入字母‘e’开始出列\n”);
getchar();
while(~scanf(“%c”,&a))
{
getchar();
if(a!=‘e’)
{
printf(“\n输入字母’e’继续出列\n”);
continue;
}
if(DeLinkQueue(Q,&tt))
printf(“元素%d成功出列\n”,tt);
if(IsLQEmpty(Q))
{printf(“该队列目前为空!\n”);break;}
else
printf(“该队列不为空!\n”);
printf(“\n输入字母’e’继续出列\n”);
}
return 0;
}

四、实验小结
通过本次实验，我深入理解了栈和队列的基本概念和实现方式，包括顺序栈、链栈、循环队列和链队。在具体操作中，完成了顺序栈的初始化、入栈、出栈等功能，并体现了栈的先进后出特性。通过实现十进制转二进制算法，运用栈的特性成功得到正确的二进制表示。学习了使用栈检验表达式中的括号匹配情况，以及将中缀表达式转换为后缀表达式，并通过后缀表达式求值。这次实验对我在数据结构和算法领域的学习提供了坚实的基础。

五、教师评语

实验三 串的模式匹配

一、实验目的
1、了解串的基本概念
2、掌握串的模式匹配算法的实现

二、实验预习
说明以下概念
1、模式匹配：
模式匹配是在一个文本中查找一个特定的模式或字符串的过程。在计算机科学中，这通常涉及搜索一个文本串中是否包含一个特定的子串。模式匹配在字符串搜索、数据检索、文本编辑等领域得到广泛应用。
2、BF算法：
BF算法，即暴力匹配算法，是一种简单直观的模式匹配算法。它通过在文本串中逐一比较每个可能的位置，检查是否与模式串相匹配。该算法的时间复杂度较高，为O((n-m+1)*m)，其中n为文本串长度，m为模式串长度，但它的实现简单，易于理解。
3、KMP算法：
KMP算法是一种高效的字符串匹配算法，其全称为Knuth-Morris-Pratt算法。相比于BF算法，KMP算法通过预处理模式串，构建一个部分匹配表，以避免在匹配过程中重复比较已匹配的字符。这使得KMP算法的时间复杂度降低到O(n+m)，其中n为文本串长度，m为模式串长度。 KMP算法在大规模文本匹配问题中表现出色，特别是对于长文本和重复模式的情况。

三、实验内容和要求
1、阅读并运行下面程序，根据输入写出运行结果。
#include<stdio.h>
#include<string.h>
#define MAXSIZE 100
typedef struct{
char data[MAXSIZE];
int length;
}SqString;

int strCompare(SqString *s1,SqString *s2); /串的比较/
void show_strCompare();
void strSub(SqString *s,int start,int sublen,SqString *sub);
/求子串/
void show_subString();

int strCompare(SqString s1,SqString s2){
int i;
for(i=0;ilength&&ilength;i++)
if(s1->data[i]!=s2->data[i])
return s1->data[i]-s2->data[i];
return s1->length-s2->length;
}
void show_strCompare(){
SqString s1,s2;
int k;
printf("\nshow Compare**\n");
printf(“input string s1:”);
gets(s1.data);
s1.length=strlen(s1.data);
printf(“input string s2:”);
gets(s2.data);
s2.length=strlen(s2.data);
if((k=strCompare(&s1,&s2))==0)
printf(“s1=s2\n”);
else if(k<0)
printf(“s1<s2\n”);
else
printf(“s1>s2\n”);
printf(“\nshow over\n”);
}

void strSub(SqString s,int start,int sublen,SqString sub){
int i;
if(start<1||start>s->length||sublen>s->length-start+1){
sub->length=0;
}
for(i=0;i<sublen;i++)
sub->data[i]=s->data[start+i-1];
sub->length=sublen;
}
void show_subString(){
SqString s,sub;
int start,sublen,i;
printf("\nshow subString**\n");
printf(“input string s:”);
gets(s.data);
s.length=strlen(s.data);
printf(“input start:”);
scanf(“%d”,&start);
printf(“input sublen:”);
scanf(“%d”,&sublen);
strSub(&s,start,sublen,&sub);
if(sub.length==0)
printf(“ERROR!\n”);
else{
printf(“subString is :”);
for(i=0;i<sublen;i++)
printf(“%c”,sub.data[i]);
}
printf(“\nshow over\n”);
}

int main(){
int n;
do {
printf(“\n—String—\n”);
printf(“1. strCompare\n”);
printf(“2. subString\n”);
printf(“0. EXIT\n”);
printf(“\ninput choice:”);
scanf(“%d”,&n);
getchar();
switch(n){
case 1:show_strCompare();break;
case 2:show_subString();break;
default:n=0;break;
}
}while(n);
return 0;
}
 运行程序
输入：
1
student
students
2
Computer Data Stuctures
10
4
运行结果：

2、实现串的模式匹配算法。补充下面程序，实现串的BF和KMP算法。
#include<stdio.h>
#include<string.h>
#define MAXSIZE 100
typedef struct{
char data[MAXSIZE];
int length;
}SqString;

int index_bf(SqString *s,SqString *t,int start);
void getNext(SqString *t,int next[]);
int index_kmp(SqString *s,SqString *t,int start,int next[]);
void show_index();

int index_bf(SqString *s,SqString *t,int start){
/返回模式串t在主串s中第start个字符开始第一次出现的位置;若不存在,返回0/
//模式串t长度为0 或 起始查找位置超出主串范围:直接返回0
if(0 == t->length || start < 1 || start > s->length)
return (0);
int pos=start-1; //pos记录主串s开始匹配的字符下标
int i=pos; //i指向主串s当前正待比较的字符下标
int j=0; //j指向模式串t当前正待比较的字符下标
while( i < s->length && j < t->length )
{
if(s->data[i] == t->data[j]) //匹配成功:i,j都++,继续比较后续字符
{
i++;
j++;
}
else //匹配失败
{
pos++; //主串开始匹配的位置+1
i=pos; //i回溯到主串初始位置下一字符
j=0; //j回溯到模式串第一个字符
}
}
if(j >= t->length)
return (pos-start+2); //返回模式串t在主串s中第start个字符开始第一次出现的位置
else
return (-1); //查找失败,返回-1
}/index_bf/

void getNext(SqString *t,int next[]){
int i=0,j=-1;
next[0]=-1;
while(ilength){
if((j==-1)||(t->data[i]==t->data[j])){
i++;j++;next[i]=j;
}else
j=next[j];
}
}

int index_kmp(SqString *s,SqString *t,int start,int next[]){
/返回模式串t在主串s中第start个字符开始第一次出现的位置;若不存在,返回0/
//模式串t长度为0 或 起始位置超出主串范围:直接返回0
if(0 == t->length || start < 1 || start > s->length)
return (0);
int i=start-1; //i指向主串s当前正待比较的字符下标
int j=0; //j指向模式串t当前正待比较的字符下标
while(ilength && jlength)
{
if(-1 == j || (s->data[i] == t->data[j]))
{
i++;
j++;
}
else //匹配失败
{
j=next[j]; //i不回溯,j回溯到next[j]
}
}
if(j>=t->length)
return (i-j-start+2); //返回模式串t在主串s中第start个字符开始第一次出现的位置
else
return (-1); //查找失败,返回-1
}/index_kmp/

void show_index(){
SqString s,t;
int k,next[MAXSIZE]={0},i;
printf(“\nshow index\n”);
printf(“input string s:”);
gets(s.data);
s.length=strlen(s.data);
printf(“input string t:”);
gets(t.data);
t.length=strlen(t.data);
printf(“input start position:”);
scanf(“%d”,&k);
printf(“BF:\nthe result of BF is %d\n”,index_bf(&s,&t,k));
getNext(&t,next);
printf(“KMP:\n”);
printf(“next[]:”);
for(i=0;i<t.length;i++)
printf(“%3d”,next[i]);
printf(“\n”);
printf(“the result of KMP is %d\n”,index_kmp(&s,&t,k,next));
printf(“\nshow over\n”);
}

int main(){
show_index();
return 0;
}

输入：
abcaabbabcabaacbacba
abcabaa
1

运行结果：

四、实验小结
这次实验对我的帮助很大。通过预习，我对串的基本概念和模式匹配算法有了清晰的认识。在实验中，我不仅学会了串的基本操作，还实现了BF和KMP算法。通过这两种算法，我能够高效地在文本串中查找特定模式，这对我理解字符串匹配过程和提高算法实现能力都有很大帮助。在实际运行程序时，我成功使用这些算法解决了模式匹配问题，进一步巩固了所学知识。总的来说，这次实验让我更深入地理解了字符串处理和模式匹配算法。

五、教师评语

实验四 二叉树

一、实验目的
1、掌握二叉树的基本特性
2、掌握二叉树的先序、中序、后序的递归遍历算法
3、理解二叉树的先序、中序、后序的非递归遍历算法
4、通过求二叉树的深度、叶子结点数和层序遍历等算法，理解二叉树的基本特性

二、实验预习
说明以下概念
1、二叉树：
二叉树是一种数据结构，其中每个节点最多有两个子节点，通常称为左子树和右子树。二叉树的节点包含一个数据元素和指向其左右子树的指针。节点的左子树和右子树本身也是二叉树。二叉树在计算机科学中广泛用于实现搜索算法和数据组织。
2、递归遍历：
递归遍历是指在处理数据结构（如树或列表）时，通过递归地调用自己来访问或处理结构中的每个元素。在二叉树中，递归遍历包括前序、中序和后序遍历，其中前序是先访问根节点，然后递归地访问左右子树；中序是先递归地访问左子树，然后访问根节点，最后递归地访问右子树；后序是先递归地访问左右子树，最后访问根节点。
3、非递归遍历：
非递归遍历是指在处理数据结构时，不使用递归而是利用循环或其他辅助数据结构来遍历元素。在二叉树中，使用栈或队列通常是实现非递归遍历的常见方式。这种方法可以减少递归调用的空间复杂度。
4、层序遍历：
层序遍历是一种按层级顺序逐层访问树或图节点的方式。在二叉树中，从根节点开始，按照从左到右的顺序逐层访问每个节点，先访问当前层的所有节点，然后再依次访问下一层的节点。通常使用队列来实现层序遍历，保证节点的访问顺序符合每一层从左到右的次序。这种遍历方式对于分析树的结构和层级关系非常有用。

三、实验内容和要求
1、阅读并运行下面程序，根据输入写出运行结果，并画出二叉树的形态。
#include<stdio.h>
#include<malloc.h>
#define MAX 20
typedef struct BTNode{ /节点结构声明/
char data ; /节点数据/
struct BTNode *lchild;
struct BTNode *rchild ; /指针/
}*BiTree;

void createBiTree(BiTree t){ / 先序遍历创建二叉树*/
char s;
BiTree q;
printf(“\nplease input data:(exit for #)”);
s=getchar();
if(s==‘#’){*t=NULL; return;}
q=(BiTree)malloc(sizeof(struct BTNode));
if(q==NULL){printf(“Memory alloc failure!”); return;}
q->data=s;
*t=q;
createBiTree(&q->lchild); /递归建立左子树/
createBiTree(&q->rchild); /递归建立右子树/
}

void PreOrder(BiTree p){ /* 先序遍历二叉树*/
if ( p!= NULL ) {
printf(“%c”, p->data);
PreOrder( p->lchild ) ;
PreOrder( p->rchild) ;
}
}
void InOrder(BiTree p){ /* 中序遍历二叉树*/
if( p!= NULL ) {
InOrder( p->lchild ) ;
printf(“%c”, p->data);
InOrder( p->rchild) ;
}
}
void PostOrder(BiTree p){ /* 后序遍历二叉树*/
if ( p!= NULL ) {
PostOrder( p->lchild ) ;
PostOrder( p->rchild) ;
printf(“%c”, p->data);
}
}

void Preorder_n(BiTree p){ /先序遍历的非递归算法/
BiTree stack[MAX],q;
int top=0,i;
for(i=0;i<MAX;i++) stack[i]=NULL;/初始化栈/
q=p;
while(q!=NULL){
printf(“%c”,q->data);
if(q->rchild!=NULL) stack[top++]=q->rchild;
if(q->lchild!=NULL) q=q->lchild;
else
if(top>0) q=stack[–top];
else q=NULL;
}
}

void release(BiTree t){ /释放二叉树空间/
if(t!=NULL){
release(t->lchild);
release(t->rchild);
free(t);
}
}

int main(){
BiTree t=NULL;
createBiTree(&t);
printf(“\n\nPreOrder the tree is:”);
PreOrder(t);
printf(“\n\nInOrder the tree is:”);
InOrder(t);
printf(“\n\nPostOrder the tree is:”);
PostOrder(t);
printf(“\n\n先序遍历序列（非递归）:”);
Preorder_n(t);
release(t);
return 0;
}
 运行程序
输入：
ABC##DE#G##F###
运行结果：

二叉树状态图：

2、在上题中补充求二叉树中求结点总数算法（提示：可在某种遍历过程中统计遍历的结点数），并在主函数中补充相应的调用验证正确性。
算法代码：
答：
int Num_of_Nodes(BiTree t){ /求二叉树t的结点总数,函数返回值即结点总数/
BiTree q;
q = t;

//二叉树为空，直接返回0
if( !q )
    return 0;

//二叉树非空，总结点数 = 1 + 左子树的总结点数 + 左子树的总结点数
int num_l = Num_of_Nodes(q->lchild);
int num_r = Num_of_Nodes(q->rchild);
return (1 + num_l + num_r);
1
2
3
4
5
6
7
8

}

int main(){
BiTree t = NULL;
createBiTree(&t);
printf(“\n\nPreOrder the tree is:”);
PreOrder(t);
printf(“\n\nInOrder the tree is:”);
InOrder(t);
printf(“\n\nPostOrder the tree is:”);
PostOrder(t);
printf(“\n\n先序遍历序列（非递归）:”);
Preorder_n(t);

//主函数添加代码
printf("\n\n此二叉树结点总数为:%d",Num_of_Nodes(t));
release(t);
return 0;
1
2
3
4

}

验证

3、在上题中补充求二叉树中求叶子结点总数算法（提示：可在某种遍历过程中统计遍历的叶子结点数），并在主函数中补充相应的调用验证正确性。
算法代码：
答：
int Num_of_LeafNodes(BiTree t){ /求二叉树t的叶子结点总数,函数返回值即叶子结点总数/
BiTree q;
q = t;

//二叉树为空，直接返回0
if( !q )
    return 0;
//结点的左右子树均为空，则该结点为叶子结点
if( !(q->lchild) && !(q->rchild) )
    return 1;

//二叉树非空，叶子结点总数 = 左子树的叶子结点总数 + 右子树的叶子结点总数
int num_l = Num_of_LeafNodes(q->lchild);
int num_r = Num_of_LeafNodes(q->rchild);

return (num_l + num_r);
1
2
3
4
5
6
7
8
9
10
11
12

}
int main(){
BiTree t = NULL;
createBiTree(&t);
printf(“\n\nPreOrder the tree is:”);
PreOrder(t);
printf(“\n\nInOrder the tree is:”);
InOrder(t);
printf(“\n\nPostOrder the tree is:”);
PostOrder(t);
printf(“\n\n先序遍历序列（非递归）:”);
Preorder_n(t);

//主函数添加代码
printf("\n\n此二叉树结点总数为:%d",Num_of_Nodes(t));
printf("\n\n此二叉树叶子结点总数为:%d",Num_of_LeafNodes(t));

release(t);
return 0;
1
2
3
4
5
6

}

验证

4、在上题中补充求二叉树深度算法，并在主函数中补充相应的调用验证正确性。
算法代码：
答：
int Depth_of_BiTree(BiTree t){ /求二叉树t的深度,函数返回值即二叉树深度/
BiTree q;
q = t;

//二叉树为空，直接返回0
if( !q )
    return 0;
//二叉树非空，深度 = 1 + Max（左子树深度，右子树深度）
int dep_l = Depth_of_BiTree(q->lchild);
int dep_r = Depth_of_BiTree(q->rchild);
int dep = 1 + ( (dep_l > dep_r)?dep_l:dep_r );
return dep;
1
2
3
4
5
6
7
8

}

int main(){
BiTree t = NULL;
createBiTree(&t);
printf(“\n\nPreOrder the tree is:”);
PreOrder(t);
printf(“\n\nInOrder the tree is:”);
InOrder(t);
printf(“\n\nPostOrder the tree is:”);
PostOrder(t);
printf(“\n\n先序遍历序列（非递归）:”);
Preorder_n(t);

//主函数添加代码
printf("\n\n此二叉树结点总数为:%d",Num_of_Nodes(t));
printf("\n\n此二叉树叶子结点总数为:%d",Num_of_LeafNodes(t));
printf("\n\n此二叉树深度为:%d",Depth_of_BiTree(t));

release(t);
return 0;
1
2
3
4
5
6
7

}

验证

选做实验：（代码可另附纸）
1、补充二叉树层次遍历算法。（提示：利用队列实现）
答：
#include <stdio.h>
#include <stdlib.h>
typedef struct btnode
{
char data;
struct btnode *lchild,*rchild;
} bitree,*Bitree;
//链队列类型定义
typedef struct LinkQueueNode
{
bitree *data;
struct LinkQueueNode *next;
} LKQueNode;
typedef struct LKQueue
{
LKQueNode *front,*rear;
} LKQue;

//初始化队列
void InitQueue(LKQue *LQ)
{
LKQueNode p;
p = (LKQueNode)malloc(sizeof(LKQueNode));
LQ->front = p;
LQ->rear = p;
LQ->front->next = NULL;
}

//判断队列是否为空
int EmptyQueue(LKQue *LQ)
{
if(LQ->front == LQ->rear)
return 1;
else
return 0;
}

//入队列
void EnQueue(LKQue *LQ,Bitree x)
{
LKQueNode p;
p = (LKQueNode)malloc(sizeof(LKQueNode));
p->data = x;
p->next = NULL;
LQ->rear->next = p;
LQ->rear = p;
}

//出队列
int OutQueue(LKQue *LQ)
{
LKQueNode *s;
if ( EmptyQueue(LQ))
{
exit(0);
return 0;
}
else
{
s = LQ->front->next;
LQ->front->next = s->next;
if(s->next == NULL)
LQ->rear = LQ->front;
free(s);
return 1;
}
}

//取队列首元素
Bitree GetHead(LKQue *LQ)
{
LKQueNode *p;
bitree *q;
if(EmptyQueue(LQ))
return q;
else
{
p = LQ->front->next;
return p->data;
}
}

//建二叉树
Bitree Initiate()
{
char ch;
Bitree t;
ch = getchar();
if(ch == ‘#’)
t = NULL;
else
{
t = (Bitree)malloc(sizeof(bitree));
t->data = ch;
t->lchild = Initiate();
t->rchild = Initiate();
}
return t;
}

//层次遍历
void LevelOrder(Bitree bt)
{
LKQue Q;
Bitree p;
InitQueue(&Q);
if(bt != NULL)
{
EnQueue(&Q,bt);
while(!EmptyQueue(&Q))
{
p = GetHead(&Q);
OutQueue(&Q);
printf(“%c”,p->data); //输出是char
if(p->lchild != NULL)
EnQueue(&Q,p->lchild);
if(p->rchild != NULL)
EnQueue(&Q,p->rchild);
}
}
}
int main()
{
Bitree T;
printf(“按先序序列输入结点序列，'#'代表空:\n”);
T=Initiate();
printf(“\n层次遍历序列为:”);
LevelOrder(T);
printf(“\n”);
return 0;
}

2、补充二叉树中序、后序非递归算法。
答：
#include<stdio.h>
#include<malloc.h>

#define MAX 20
typedef struct BTNode /节点结构声明/
{
char data ; /节点数据/
struct BTNode *lchild;
struct BTNode *rchild ; /指针/
}*BiTree;

BiTree createBiTree(BiTree t) /* 先序遍历创建二叉树*/
{
char s;
printf(“\nplease input data:(exit for #)”);
s=getchar();
if(s==‘#’)
{
t=NULL;
return t;
}
t=(BiTree)malloc(sizeof(struct BTNode));
if(t==NULL)
{
printf(“Memory alloc failure!”);
exit(0);
}
t->data=s;
t->lchild=createBiTree(t->lchild); /递归建立左子树/
t->rchild=createBiTree(t->rchild); /递归建立右子树/
return t;
}

void PreOrder(BiTree p) /* 先序遍历二叉树*/
{
if ( p!= NULL )
{
printf(“%c”, p->data);
PreOrder( p->lchild ) ;
PreOrder( p->rchild) ;
}
}
void InOrder(BiTree p) /* 中序遍历二叉树*/
{
if( p!= NULL )
{
InOrder( p->lchild ) ;
printf(“%c”, p->data);
InOrder( p->rchild) ;
}
}
void PostOrder(BiTree p) /* 后序遍历二叉树*/
{
if ( p!= NULL )
{
PostOrder( p->lchild ) ;
PostOrder( p->rchild) ;
printf(“%c”, p->data);
}
}

void Preorder_n(BiTree p) /先序遍历的非递归算法/
{
BiTree stack[MAX],q;
int top=0,i;
for(i=0; i<MAX; i++) stack[i]=NULL; /初始化栈/
q=p;
while(q!=NULL)
{
printf(“%c”,q->data);
if(q->rchild!=NULL) stack[top++]=q->rchild;
if(q->lchild!=NULL) q=q->lchild;
else if(top>0) q=stack[–top];
else q=NULL;
}
}

void release(BiTree t) /释放二叉树空间/
{
if(t!=NULL)
{
release(t->lchild);
release(t->rchild);
free(t);
}
}
void InordeTraverse(BiTree bt)
{
BiTree stack[100], p;
int top=0;
p=bt;
do
{
while(p!=NULL)
{
stack[top++]=p;
p=p->lchild;
}
if(top>0)
{
p=stack[top-1];
printf(“%c”,stack[top-1]->data);
top–;
p=p->rchild;
}
}
while(top!=0||p!=NULL);
}/中序遍历非递归算法/
void PostorderTraverse(BiTree bt)
{
BiTree stack[MAX];
int top1 = 0;
BiTree cur,top,last = NULL;
cur = bt;
for(int i = 0; i < MAX; i++)
stack[i] = NULL;
while(cur || top1)
{
while(cur)
{
stack[++top1] = cur;
cur = cur->lchild;
}

    top = stack[top1];

    if(top->rchild == NULL || top->rchild == last)
    {
        top1--;
        printf("%c",top->data) ;
        last = top;
    }
    else
    {
        cur = top->rchild;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

}
int main()
{
BiTree t=NULL;
t=createBiTree(t);
printf(“\n\nPreOrder the tree is:”);
PreOrder(t);
printf(“\n\nInOrder the tree is:”);
InOrder(t);
printf(“\n\nPostOrder the tree is:”);
PostOrder(t);
printf(“\n\n先序遍历序列（非递归）:”);
Preorder_n(t);
printf(“\n\n中序遍历序列（非递归）:”);
InordeTraverse(t);
printf(“\n\n后序遍历序列（非递归）:”);
PostorderTraverse(t);
release(t);
return 0;
}

四、实验小结
在这次实验中，我通过编写和运行C语言程序深入理解了二叉树的结构和特性。我学会了如何实现二叉树的递归和非递归遍历算法，包括先序、中序和后序遍历。通过练习，我还掌握了如何求二叉树的深度、叶子节点数和层序遍历，这些操作加深了我对二叉树遍历过程和树形结构的认识。编码过程中，我遇到了一些编程错误和逻辑挑战，但通过不断调试和验证，我能够解决这些问题，这对提升我的编程能力和问题解决能力非常有帮助。总的来说，这次实验不仅加强了我对理论知识的理解，也提高了我的实践技能。

五、教师评语

实验五 图的表示与遍历

一、实验目的
1、掌握图的邻接矩阵和邻接表表示
2、掌握图的深度优先和广度优先搜索方法
3、理解图的应用方法

二、实验预习
说明以下概念
1、深度优先搜索遍历：
深度优先搜索是一种用于遍历或搜索树或图的结构的算法。在这种算法中，从根节点（或任意指定的节点）开始沿着树的边进行探索，尽可能深地搜索每个分支，直到该分支的末端，然后回溯。在图的遍历中，为了避免重复访问节点，通常会标记已访问过的节点。DFS非常适合目标路径较深或问题域较大时的情况。
2、广度优先搜索遍历：
广度优先搜索是另一种图和树的遍历算法。它从根节点开始，一层层地进行，先访问离根节点最近的节点，然后是其次近的节点等等。在实现时通常使用队列来进行。BFS特别适用于找到最短路径或者是离根节点最近的解决方案。
3、拓扑排序：
拓扑排序是对有向无环图（DAG）的顶点的线性排序，使得对于任何来自顶点 U 到顶点 V 的边，U 在排序中都出现在 V 之前。拓扑排序不是唯一的，一个有向无环图可以有一个或多个拓扑排序。这种排序方法通常用于任务调度或确定项目构建的依赖关系。
4、最小生成树：
在带权的无向连通图中，最小生成树是一种把所有顶点以最小的权值总和连接起来的树。它是原图的一个子图，并包含原图中连接所有顶点的最小边权值的边。最小生成树的典型算法有Prim算法和Kruskal算法。
5、最短路径：
在图论中，最短路径问题是找到图中两个顶点之间的路径，使得其边的权重之和被最小化。最短路径可以在无向图或有向图中定义，并且边的权重可以代表距离、时间、成本等。解决这个问题的算法有很多，包括Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法等。
三、实验内容和要求
1、阅读并运行下面程序，根据输入写出运行结果。
#include<stdio.h>
#define N 20
#define TRUE 1
#define FALSE 0
int visited[N];
typedef struct /队列的定义/
{
int data[N];
int front,rear;
}queue;
typedef struct /图的邻接矩阵/
{
int vexnum,arcnum;
char vexs[N];
int arcs[N][N];
}
graph;

void createGraph(graph *g); /建立一个无向图的邻接矩阵/
void dfs(int i,graph *g); /从第i个顶点出发深度优先搜索/
void tdfs(graph *g); /深度优先搜索整个图/
void bfs(int k,graph *g); /从第k个顶点广度优先搜索/
void tbfs(graph *g); /广度优先搜索整个图/
void init_visit(); /初始化访问标识数组/

void createGraph(graph *g) /建立一个无向图的邻接矩阵/
{ int i,j;
char v;
g->vexnum=0;
g->arcnum=0;
i=0;
printf(“输入顶点序列(以#结束)：\n”);
while((v=getchar())!=‘#’)
{
g->vexs[i]=v; /读入顶点信息/
i++;
}
g->vexnum=i; /顶点数目/
for(i=0;ivexnum;i++) /邻接矩阵初始化/
for(j=0;jvexnum;j++)
g->arcs[i][j]=0;
printf(“输入边的信息：\n”);
scanf(“%d,%d”,&i,&j); /读入边i,j/
while(i!=-1) /读入i,j为－1时结束/
{
g->arcs[i][j]=1;
g->arcs[j][i]=1;
scanf(“%d,%d”,&i,&j);
}
}

void dfs(int i,graph *g) /从第i个顶点出发深度优先搜索/
{
int j;
printf(“%c”,g->vexs[i]);
visited[i]=TRUE;
for(j=0;jvexnum;j++)
if((g->arcs[i][j]==1)&&(!visited[j]))
dfs(j,g);
}

void tdfs(graph *g) /深度优先搜索整个图/
{
int i;
printf(“\n从顶点%C开始深度优先搜索序列：”,g->vexs[0]);
for(i=0;ivexnum;i++)
if(visited[i]!=TRUE)
dfs(i,g);
}

void bfs(int k,graph *g) /从第k个顶点广度优先搜索/
{
int i,j;
queue qlist,*q;
q=&qlist;
q->rear=0;
q->front=0;
printf(“%c”,g->vexs[k]);
visited[k]=TRUE;
q->data[q->rear]=k;
q->rear=(q->rear+1)%N;
while(q->rear!=q->front)
{
i=q->data[q->front];
q->front=(q->front+1)%N;
for(j=0;jvexnum;j++)
if((g->arcs[i][j]==1)&&(!visited[j]))
{
printf(“%c”,g->vexs[j]);
visited[j]=TRUE;
q->data[q->rear]=j;
q->rear=(q->rear+1)%N;
}
}
}

void tbfs(graph *g) /广度优先搜索整个图/
{
int i;
printf(“\n从顶点%C开始广度优先搜索序列：”,g->vexs[0]);
for(i=0;ivexnum;i++)
if(visited[i]!=TRUE)
bfs(i,g);
}

void init_visit() /初始化访问标识数组/
{
int i;
for(i=0;i<N;i++)
visited[i]=FALSE;
}

int main()
{
graph ga;
int i,j;
createGraph(&ga);
printf(“无向图的邻接矩阵：\n”);
for(i=0;i<ga.vexnum;i++)
{
for(j=0;j<ga.vexnum;j++)
printf(“%3d”,ga.arcs[i][j]);
printf(“\n”);
}
init_visit();
tdfs(&ga);
init_visit();
tbfs(&ga);
return 0;
}
 根据右图的结构验证实验，输入：
ABCDEFGH#
0,1
0,2
0,5
1,3
1,4
2,5
2,6
3,7
4,7
-1,-1

 运行结果：

2、阅读并运行下面程序，补充拓扑排序算法。
#include<stdio.h>
#include<malloc.h>
#define N 20
typedef struct edgenode{ /图的邻接表：邻接链表结点/
int adjvex; /顶点序号/
struct edgenode *next; /下一个结点的指针/
}edgenode;

typedef struct vnode{ /图的邻接表：邻接表/
char data; /顶点信息/
int ind; /顶点入度/
struct edgenode *link; /指向邻接链表指针/
}vnode;

void createGraph_list(vnode adjlist[],int *p)； /建立有向图的邻接表/
void topSort(vnode g[],int n)； /拓扑排序/

void createGraph_list(vnode adjlist[],int *p){ /建立有向图的邻接表/
int i,j,n,e;
char v;
edgenode *s;
i=0;n=0;e=0;
printf(“输入顶点序列(以#结束)：\n”);
while((v=getchar())!=‘#’)
{
adjlist[i].data=v; /读入顶点信息/
adjlist[i].link=NULL;
adjlist[i].ind=0;
i++;
}
n=i;
p=n;
/建立邻接链表/
printf(“\n请输入弧的信息(i=-1结束)：i,j:\n”);
scanf(“%d,%d”,&i,&j);
while(i!=-1){
s=(struct edgenode)malloc(sizeof(edgenode));
s->adjvex=j;
s->next=adjlist[i].link;
adjlist[i].link=s;
adjlist[j].ind++; /顶点j的入度加1/
e++;
scanf(“%d,%d”,&i,&j);
}
printf(“邻接表:”);
for(i=0;i<n;i++){ /输出邻接表/
printf(“\n%c,%d:”,adjlist[i].data,adjlist[i].ind);
s=adjlist[i].link;
while(s!=NULL){
printf(“->%d”,s->adjvex);
s=s->next;
}
}
}

//g[]为图的邻接表,n为图中顶点数
void topSort(vnode g[],int n) { /拓扑排序/
printf(“拓扑排序顶点序列：\n”);
int i,j,k,m = 0;
int top = -1; //初始化栈为空,栈顶指针top置为-1
struct edgenode *p;

//遍历图中所有顶点,将度为0的顶点都入栈
for(i=0;i<n;i++)
{
    if(0 == g[i].ind)
    {
        g[i].ind = top;   
        top = i;
    }
}

//栈非空
while(-1 != top)
{
    j = top;                
    printf("%c",g[j].data);  //输出栈顶顶点
    m++;                     //m为拓扑排序序列中的顶点数(可判断图中是否有环)
    top = g[j].ind;        //出栈

    //顶点j输出后还需修改邻接自j的顶点的入度(即删除顶点j和所有以它为弧尾的弧)
    p = g[j].link;           //p指向顶点j的第一个邻接结点
    while( p )
    {
        k = p->adjvex;       //k为邻接顶点序号
        g[k].ind--;          //邻接顶点入度-1

        //将入度为0的顶点入栈
        if(0 == g[k].ind)
        {
            g[k].ind = top;
            top = k;
        }
        p = p->next;         //p继续指向下一个邻接结点
    }
}

//如果拓扑序列中不包含图中所有顶点,则图中一定存在环
if(m < n)
    printf("图中存在环");
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

}

int main(){
vnode adjlist[N];
int n,*p;
p=&n;
createGraph_list(adjlist,p);
return 0;
}
 根据输入，输出有向图的拓扑排序序列。并画出有向图。输入:
ABCDEF#
0,1
1,2
2,3
4,1
4,5
-1,-1
 运行结果：

3、阅读并运行下面程序。
#include<stdio.h>
#define N 20
#define TRUE 1
#define INF 32766 /邻接矩阵中的无穷大元素/
#define INFIN 32767 /比无穷大元素大的数/

typedef struct
{ /图的邻接矩阵/
int vexnum,arcnum;
char vexs[N];
int arcs[N][N];
}
graph;

void createGraph_w(graph *g,int flag);
void prim(graph *g,int u);
void dijkstra(graph g,int v);
void showprim();
void showdij();

/建带权图的邻接矩阵,若flag为1则为无向图，flag为0为有向图/
void createGraph_w(graph *g,int flag)
{
int i,j,w;
char v;
g->vexnum=0;
g->arcnum=0;
i=0;
printf(“输入顶点序列(以#结束)：\n”);
while((v=getchar())!=‘#’)
{
g->vexs[i]=v; /读入顶点信息/
i++;
}
g->vexnum=i;
for(i=0;i<6;i++) /邻接矩阵初始化/
for(j=0;j<6;j++)
g->arcs[i][j]=INF;
printf(“输入边的信息：\n”);
scanf(“%d,%d,%d”,&i,&j,&w); /读入边(i,j,w)/
while(i!=-1) /读入i为－1时结束/
{
g->arcs[i][j]=w;
if(flag==1)
g->arcs[j][i]=w;
scanf(“%d,%d,%d”,&i,&j,&w);
}
}

void prim(graph *g,int u)/出发顶点u/
{
int lowcost[N],closest[N],i,j,k,min;
for(i=0;ivexnum;i++) /求其他顶点到出发顶点u的权/
{
lowcost[i]=g->arcs[u][i];
closest[i]=u;
}
lowcost[u]=0;
for(i=1;ivexnum;i++) /循环求最小生成树中的各条边/
{ min=INFIN;
for(j=0;jvexnum;j++) /选择得到一条代价最小的边/
if(lowcost[j]!=0&&lowcost[j]<min)
{
min=lowcost[j];
k=j;
}
printf(“(%c,%c)–%d\n”,g->vexs[closest[k]],g->vexs[k],lowcost[k]); /输出该边/
lowcost[k]=0; /*顶点k纳入最小生成树 */
for(j=0;jvexnum;j++) /求其他顶点到顶点k 的权/
if(g->arcs[k][j]!=0&&g->arcs[k][j]<lowcost[j])
{
lowcost[j]=g->arcs[k][j];
closest[j]=k;
}
}
}

void printPath(graph g,int startVex,int EndVex)
{
int stack[N],top=0; /堆栈/
int i,k,j;
int flag[N]; /输出路径顶点标志/
k=EndVex;
for (i=0;i<g.vexnum;i++) flag[i]=0;
j=startVex;
printf(“%c”,g.vexs[j]);
flag[j]=1;
stack[top++]=k;
while (top>0) /找j到k的路径/
{
for (i=0;i<g.vexnum;i++)
{
if (path[k][i]==1 && flag[i]==0) /j到k的路径含有i顶点/
{
if (g.arcs[j][i]!=INF ) /j到i的路径含有中间顶点/
{
printf("-> %c(%d) ",g.vexs[i],g.arcs[j][i]);
/输出j到k的路径的顶点i/
flag[i]=1;
j=i;
k=stack[–top];
break;
}
else
{
if (i!=k) stack[top++]=i; /break;/
}
}
}
}

void dijkstra(graph g,int v){ /dijkstra算法求单源最短路径/
int path[N][N],dist[N],s[N];
int mindis,i,j,u,k;
for(i=0;i<g.vexnum;i++){
dist[i]=g.arcs[v][i];
s[i]=0;
for(j=0;j<g.vexnum;j++)
path[i][j]=0;
if(dist[i]<INF){
path[i][v]=1;
path[i][i]=1;
}
}
dist[v]=0;
s[v]=1;
for(i=0,u=1;i<g.vexnum;i++){
mindis=INFIN;
for(j=0;j<g.vexnum;j++)
if(s[j]==0)
if(dist[j]<mindis){
u=j;
mindis=dist[j];
}
s[u]=1;
for(j=0;j<g.vexnum;j++)
if((s[j]==0)&&dist[u]+g.arcs[u][j]<dist[j]){
dist[j]=dist[u]+g.arcs[u][j];
for(k=0;k<g.vexnum;k++)
path[j][k]=path[u][k];
path[j][j]=1;
}
}
printf(“\n顶点%c->到各顶点的最短路径\n”,g.vexs[v]);
for(i=0;i<g.vexnum;i++){
printf(“\n顶点%c->顶点%c：”,g.vexs[v],g.vexs[i]);
if(dist[i]==INF||dist[i]==0)
printf(“无路径”);
else{
printf("%d ",dist[i]);
printf(“经过顶点：”);
printPath(g,v,i); /输出v到i的路径/
}
}
}

void showprim()/最小生成树prim算法演示/
{
graph ga;
createGraph_w(&ga,1);
prim(&ga,0);
}

void showdij(){ /dijstra算法演示/
graph ga;
createGraph_w(&ga,0);
dijkstra(ga,0);
}

int main(){
showprim(); /prim算法演示/
getchar();
showdij(); /dijstra算法演示/
return 0;
}
 下面的输入分别验证prim算法和dijstra算法。输入实例的第一部分为无向图，求其最小生成树；输入的第二部分为有向图，求其最短路径。
最小生成树 最短路径

ABCDEF#
0,1,6
0,2,1
0,3,5
1,2,5
1,4,3
2,3,5
2,4,6
2,5,4
3,5,2
4,5,6
-1,-1,-1
ABCDEF#
0,2,10
0,5,100
0,4,30
1,2,5
2,3,50
3,4,20
3,5,10
4,3,20
4,5,60
-1,-1,-1

 运行结果：（并画出两个图）
答：这里我对代码进行了一些修改，老师你给出的代码中有一些问题，最短路径经过的顶点有问题。
最小生成树和最短路径运行结果

最小生成树图和最短路径图：

四、实验小结
通过实践深入理解了图的两种基本表示方法：邻接矩阵和邻接表。我学会了实现图的深度优先搜索（DFS）和广度优先搜索（BFS），这两种搜索技术帮助我掌握了图的基本遍历过程。通过拓扑排序，我了解了如何处理有向无环图，并认识到了它在解决实际问题中的应用，如任务调度。此外，我还探索了图的最小生成树和最短路径问题，通过Prim算法和Dijkstra算法的编码与执行，提高了我的编程能力和算法应用技巧。整个实验过程不仅巩固了我对图论知识的理解，还激发了我进一步探索图的复杂性及其在多个领域中应用的兴趣。

五、教师评语