南阳理工学院
数据结构(C语言版)上机实验指导书
软件学院·软件工程
目
录
实验1 线性表应用
实验2 栈和队列的应用 .......................................................................14 实验3 线性表应用 ...............................................................................27 实验4 图论及其应用 ...........................................................................46
实验5 查找
实验6 排序 ...........................................................................................64
实验1 线性表应用
一、实验目的
3，了解和掌握线性表顺序存储和链式存储在计算机中的表示，基本操做在计算机中的实 2，能够利用线性表结构对实际问题进行分析建模，利用计算机求解。
1，能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。
二、实验内容及步骤
1、利用程序设计语言分别实现顺序表和链表的抽象数据类型。
2、掌握程序分文件（头文件和实现文件）书写的方式。
3、分别用顺序表和链表实现课本算法2.2：合并两个非递减有序序列，并对其时间性能做出分析。
三、实验步骤与调试过程
以线性表来描述一元多项式，储存结构采用单链表，每个结点储存的多项式中某一项的系数和指数，建立单链表时指数高的结点列于指数低的结点之后，即线性表的元素按指数递增有序排列。
四、实验结果
五、疑难小结
当线性表的长度变化较大，难以估计其存储规模，另外对线性表频繁进行插入和删除操作时，则采用链表作为存储结构可能会更好一些。在实际应用中应该考虑以下因素：(1)应有利于运算的实现；(2)应有利于数据的特性；(3)应有利于软件环境。
六、主要算法和程序清单 顺序表的非递减数列合并 #include
/*包含输入输出头文件*/ #define ListSize 100 typedef int DataType; typedef struct { DataType list[ListSize]; int length; }SeqList;
void InitList(SeqList *L)
/*将线性表初始化为空的线性表只需要把线性表的长度length置为0*/ { L->length=0; /*把线性表的长度置为0*/ } int ListEmpty(SeqList L)
/*判断线性表是否为空，线性表为空返回1，否则返回0*/ {
if(L.length==0)
/*判断线性表的长度是否为9*/
return 1;
/*当线性表为空时，返回1；否则返回0*/
else
return 0; } int GetElem(SeqList L,int i,DataType *e)
/*查找线性表中第i个元素。查找成功将该值返回给e，并返回1表示成功；否则返回-1表示失败。*/ { if(iL.length)
/*在查找第i个元素之前，判断该序号是否合法*/
return -1; *e=L.list[i-1]; /*将第i个元素的值赋值给e*/
return 1; } int LocateElem(SeqList L,DataType e)
/*查找线性表中元素值为e的元素，查找成功将对应元素的序号返回，否则返回0表示失败。*/ {
int i; for(i=0;i
if(L.list[i]==e)
return i+1;
return 0; } int InsertList(SeqList *L,int i,DataType e)
/*在顺序表的第i个位置插入元素e，插入成功返回1，如果插入位置不合法返回-1，顺序表满返回0*/ {
int j; if(iL->length+1)
/*在插入元素前，判断插入位置是否合法*/ {
printf(\"插入位置i不合法！\\n\");
return -1; } else if(L->length>=ListSize) /*在插入元素前，判断顺序表是否已经满，不能插入元素*/ {
printf(\"顺序表已满，不能插入元素。\\n\");
return 0; } else {
for(j=L->length;j>=i;j--) /*将第i个位置以后的元素依次后移*/
L->list[j]=L->list[j-1];
L->list[i-1]=e; /*插入元素到第i个位置*/
L->length=L->length+1; /*将顺序表长增1*/
return 1; } } int DeleteList(SeqList *L,int i,DataType *e) {
int j;
if(L->length
{
printf(\"顺序表已空不能进行删除!\\n\");
return 0;
}
else if(iL->length)
{
printf(\"删除位置不合适!\\n\");
return -1;
}
else
{
*e=L->list[i-1];
for(j=i;jlength-1;j++)
L->list[j-1]=L->list[j];
L->length=L->length-1;
return 1;
} } int ListLength(SeqList L) {
return L.length; } void ClearList(SeqList *L) { L->length=0; }
void MergeList(SeqList A,SeqList B,SeqList *C); */ void main() { int i,flag; DataType a[]={6,11,11,23}; DataType b[]={2,10,12,12,21}; DataType e;
/*合并顺序表A和B中元素的函数声明
SeqList A,B,C;
/*声明顺序表A，B和C*/ InitList(&A);
/*初始化顺序表A*/ InitList(&B);
/*初始化顺序表B*/ InitList(&C);
/*初始化顺序表C*/ for(i=1;i
/*将数组a中的元素插入到顺序表A中*/ {
if(InsertList(&A,i,a[i-1])==0)
{
printf(\"位置不合法\");
return;
} } for(i=1;i
/*将数组b中元素插入到顺序表B中*/ {
if(InsertList(&B,i,b[i-1])==0)
{
printf(\"位置不合法\");
return;
} } printf(\"顺序表A中的元素：\\n\"); for(i=1;i
flag=GetElem(A,i,&e); /*返回顺序表A中的每个元素到e中*/
if(flag==1)
printf(\"%4d\",e); } printf(\"\\n\"); printf(\"顺序表B中的元素：\\n\"); for(i=1;i
flag=GetElem(B,i,&e); /*返回顺序表B中的每个元素到e中*/
if(flag==1)
printf(\"%4d\",e);
} printf(\"\\n\"); printf(\"将在A中出现B的元素合并后C中的元素：\\n\"); MergeList(A,B,&C);
/*将在顺序表A和B中的元素合并*/ for(i=1;i
/*显示输出合并后C中所有元素*/ {
flag=GetElem(C,i,&e);
if(flag==1)
printf(\"%4d\",e);
} printf(\"\\n\"); getch();
} void MergeList(SeqList A,SeqList B,SeqList *C) /*合并顺序表A和B的元素到C中，并保持元素非递减排序*/ { int i,j,k; DataType e1,e2; i=1;j=1;k=1; while(i
GetElem(A,i,&e1);
GetElem(B,j,&e2);
if(e1
{
InsertList(C,k,e1);
i++;
k++;
}
else
{
InsertList(C,k,e2);
j++;
k++;
}
} while(i
素*/ {
GetElem(A,i,&e1);
InsertList(C,k,e1);
i++;
k++; } while(j
素*/ {
GetElem(B,j,&e2);
InsertList(C,k,e2);
j++;
/*取出顺序表A中的元素*/ /*取出顺序表B中的元素*/ /*比较顺序表A和顺序表B中的元素*/ /*将较小的一个插入到C中*/ /*往后移动一个位置，准备比较下一个元素*/ /*将较小的一个插入到C中*/ /*往后移动一个位置，准备比较下一个元素*/ /*如果A中元素还有剩余，这时B中已经没有元/*将A中剩余元素插入到C中*/ /*如果B中元素还有剩余，这时A中已经没有元/*将B中剩余元素插入到C中*/
k++; } C->length=A.length+B.length; /*C的表长等于A和B的表长的和*/ } 链式表的非递减数列合并 /*包含头文件*/ #include
#include #include /*宏定义和单链表类型定义*/ #define ListSize 100 typedef int DataType; typedef struct Node {
DataType data;
struct Node *next; }ListNode,*LinkList; void MergeList(LinkList A,LinkList B,LinkList *C); /*将单链表A和B的元素合并到C中的函数声明*/ void InitList(LinkList *head) /*将单链表初始化为空。动态生成一个头结点，并将头结点的指
针域置为空。*/ { if((*head=(LinkList)malloc(sizeof(ListNode)))
==NULL) /*为头结点分配一个存储空间*/
exit(-1); (*head)->next=NULL;
/*将单链表的头结点指针域置为空*/ } int ListEmpty(LinkList head)
/*判断单链表是否为空，就是通过判断头结点的指针域是否为空
*/ {
if(head->next==NULL)
/*判断
单链表头结点的指针域是否为空*/
return 1;
/*当单链表为空时，返回1；否则返回0*/
else
return 0; } ListNode *Get(LinkList head,int i)
/*查找单链表中第i个结点。查找成功返回该结点的指针表示成
功；否则返回NULL表示失败。*/ { ListNode *p; int j; if(ListEmpty(head)) /*在查找第i个元素之前，
判断链表是否为空*/
return NULL; if(i
/*在查找第i个元
素之前，判断该序号是否合法*/
return NULL; j=0; p=head; while(p->next!=NULL&&j
p=p->next;
j++; } if(j==i)
return p; /*找到第i个结点
，返回指针p*/ else
return NULL ;/*如果没有找到第i个元
素，返回NULL*/ } ListNode *LocateElem(LinkList head,DataType e)
/*查找线性表中元素值为e的元素，查找成功将对应元素的结点
指针返回，否则返回NULL表示失败。*/ { ListNode *p; p=head->next; /*指针p指向第一个结点*/ while(p) {
if(p->data!=e) /*找到与e相等的元素，返
回该序号*/
p=p->next;
else
break; } return p; } int LocatePos(LinkList head,DataType e)
/*查找线性表中元素值为e的元素，查找成功将对应元素的序号
返回，否则返回0表示失败。*/ { ListNode *p; int i;
if(ListEmpty(head)) /*在查找第i个元
素之前，判断链表是否为空*/
return 0;
p=head->next; /*指针p指向第一
个结点*/
i=1;
while(p)
{
if(p->data==e) /*找到与e相等的
元素，返回该序号*/
return i;
else
{
p=p->next;
i++;
}
}
if(!p)
/*如果
没有找到与e相等的元素，返回0，表示失败*/
return 0; }
int InsertList(LinkList head,int i,DataType e) /*在单链表中第i个位置插入一个结点，结点的元素值为e。插入
成功返回1，失败返回0*/
{ ListNode *p,*pre; /*定义指向第i个元素的前
驱结点指针pre，指针p指向新生成的结点*/ int j; pre=head;
/*指针p指向头结
点*/ j=0; while(pre->next!=NULL&&j
，即第i个结点的前驱结点*/ {
pre=pre->next;
j++; } if(!pre)
/*如果没找到，说明插入位置错误*/ {
printf(\"插入位置错\");
return 0; } /*新生成一个结点，并将e赋值给该结点的数据域*/ if((p=(ListNode*)malloc(sizeof(ListNode)))==NULL)
exit(-1); p->data=e; /*插入结点操作*/ p->next=pre->next; pre->next=p; return 1; } int DeleteList(LinkList head,int i,DataType *e) /*删除单链表中的第i个位置的结点。删除成功返回1，失败返回
0*/ { ListNode *pre,*p; int j;
pre=head;
j=0;
while(pre->next!=NULL&&pre->next->next!
=NULL&&j
{
pre=pre->next;
j++;
}
if(j!=i-1)
/*如果没找到要
删除的结点位置，说明删除位置错误*/
{
printf(\"删除位置错误\");
return 0; } /*指针p指向单链表中的第i个结点，并将该结点的数据
域值赋值给e*/
p=pre->next; *e=p->data; /*将前驱结点的指针域指向要删除结点的下一个结点，
也就是将p指向的结点与单链表断开*/
pre->next=p->next;
free(p);
/*释放p指向的结
点*/
return 1; } int ListLength(LinkList head) {
ListNode *p;
int count=0;
p=head;
while(p->next!=NULL)
{
p=p->next;
count++;
}
return count; } void DestroyList(LinkList head) {
ListNode *p,*q;
p=head;
while(p!=NULL) {
q=p;
p=p->next;
free(q);
} } void main() { int i; DataType a[]={6,7,9,14,37,45,65,67}; DataType b[]={3,7,11,34,45,89};
LinkList A,B,C;
/*声明单链表A和B*/ ListNode *p; InitList(&A);
/*初始化单链表A*/ InitList(&B);
/*初始化单链表B*/ for(i=1;i
if(InsertList(A,i,a[i-1])==0)
{
printf(\"位置不合法\");
return;
} } for(i=1;i
if(InsertList(B,i,b[i-1])==0)
{
printf(\"位置不合法\");
return;
} } printf(\"单链表A中的元素有%d个：\\n\",ListLength(A)); for(i=1;i
p=Get(A,i);
/*返回单链表A中的每个结点的指针*/
if(p)
printf(\"%4d\",p->data); /*输出单链表A中的每个元素*/ } printf(\"\\n\"); printf(\"单链表B中的元素有%d个：\\n\",ListLength(B)); for(i=1;i
{
p=Get(B,i);
/*返回单链表B中的每个每个结点的指针*/
if(p)
printf(\"%4d\",p->data); /*输出单链表B中的每个元素*/
} printf(\"\\n\"); MergeList(A,B,&C);
/*将单链表A和B中的元素合并到C中*/ printf(\"将单链表A和B的元素合并到C中后，C中的元素有%d个：\\n\",ListLength(C)); for(i=1;i
{
p=Get(C,i);
/*返回单链表C中每个结点的指针*/
if(p)
printf(\"%4d\",p->data); /*显示输出C中所有元素*/ } printf(\"\\n\"); getch(); } void MergeList(LinkList A,LinkList B,LinkList *C) /*单链表A和B中的元素非递减排列，将单链表A和B中的元素合并到C中，C中的元素仍按照非递减排列*/ { ListNode *pa,*pb,*pc;/*定义指向单链表A，B,C的指针*/ pa=A->next; pb=B->next; *C=A;
/*将单链表A的头结点作为C的头结点*/ (*C)->next=NULL; pc=*C; /*依次将链表A和B中较小的元素存入链表C中*/ while(pa&&pb)
{
if(pa->datadata)
{
pc->next=pa; /*如果A中的元素小于或等于B中的元素，将A中的元素的结点作为C的结点*/
pc=pa;
pa=pa->next;
}
else
{
pc->next=pb; /*如果A中的元素大于B中的元素，将B中的元素的结点作为C的结点*/
pc=pb;
pb=pb->next;
} } pc->next=pa?pa:pb; /*将剩余的结点插入C中*/ free(B);
/*释放B的头结点*/ }
实验2 栈和队列的应用
一、实验目的
1、掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。
2、熟练掌握栈类型的两种实现方法。
3、熟练掌握循环队列和链队列的基本操作实现算法。
二、实验内容及步骤
1、用程序设计语言实现栈和队列的抽象数据类型。
2、在第一题的基础上完成以下选择：
选择一：
1) 设计并实现括号匹配算法。
2) 用队列实现在屏幕上打印杨辉三角。 选择二：
分别用栈和队列实现迷宫问题求解。 选择三：
分别用栈和队列实现一个列车调度系统。
三、实验步骤与调试过程 首先只只置操作数栈为空，表达式起始符“#”为运算符栈的栈底元素，依次读入表达式中每个字符，直至整个表达式求值完毕。
四、实验结果
五、疑难小结
对栈的顺序存储结构用了更深刻的了解，同时也对程序设计能力有了提高，加深了对栈先进后出性质的理解，对数组的应用也十分熟练。
六、主要算法： 括号匹配算法。 #include #include #include #include \"string.h\" /*宏定义和链栈类型定义*/ typedef char DataType; int Match(DataType e,DataType ch); typedef struct node {
DataType data;
struct node *next; }LStackNode,*LinkStack; void InitStack(LinkStack *top) /*将链栈初始化为空。动态生成头结点，并将头结点的指针域置为空。*/ { if((*top=(LinkStack)malloc(sizeof(LStackNode)))==NULL) /*为头结点分配一个存储
空间*/ exit(-1); (*top)->next=NULL;
/*将链栈的头结点指针域置为空*/ } int StackEmpty(LinkStack top)
/*判断链栈是否为空，就是通过判断头结点的指针域是否为空*/ {
if(top->next==NULL)
/*判断链栈头结点的指针域是否为空*/
return 1;
/*当链栈为空时，返回1；否则返回0*/
else
return 0; } int PushStack(LinkStack top, DataType e) /*进栈操作就是要在链表的第一个结点前插入一个新结点，进栈成功返回1*/ { LStackNode *p; /*定义指向第i个元素的前驱结点指针pre，指针p指向新生成的结点*/ if((p=(LStackNode*)malloc(sizeof(LStackNode)))==NULL) {
printf(\"内存分配失败!\");
exit(-1); } p->data=e;
/*指针p指向头结点*/ p->next=top->next; top->next=p; return 1; } int PopStack(LinkStack top,DataType *e) /*删除单链表中的第i个位置的结点。删除成功返回1，失败返回0*/ { LStackNode *p;
p=top->next;
if(!p)
/*判断链栈是否为空*/
{
printf(\"栈已空\");
return 0;
}
top->next=p->next;
/*将栈顶结点与链表断开，即出栈*/ *e=p->data;
/*将出栈元素赋值给e*/
free(p);
/*释放p指向的结点*/
return 1; } int StackLength(LinkStack top) {
LStackNode *p;
int count=0;
p=top;
while(p->next!=NULL)
{
p=p->next;
count++;
}
return count; } void DestroyStack(LinkStack top) {
LStackNode *p,*q;
p=top;
while(!p) {
q=p;
p=p->next;
free(q);
} } int GetTop(LinkStack top,DataType *e) { LStackNode *p;
p=top->next;
if(!p)
/*判断链栈是否为空*/
{
printf(\"栈已空\");
return 0;
}
*e=p->data;
/*将出栈元素赋值给e*/
return 1; } void main() {
LinkStack S; char *p; DataType e; DataType ch[60]; InitStack(&S);
/*初始化链栈*/ printf(\"请输入带括号的表达式(\'{}\',\'[]\',\'()\').\\n\"); gets(ch); p=ch; while(*p)
{
switch(*p)
{
case \'(\':
case \'[\':
case \'{\':
PushStack(S,*p++);
break;
case \')\':
case \']\':
case \'}\':
if(StackEmpty(S))
{
printf(\"缺少左括号.\\n\");
return;
}
else
{
GetTop(S,&e);
if(Match(e,*p))
PopStack(S,&e);
else
{
printf(\"左右括号不配对.\\n\");
return;
}
}
default:
p++;
} } if(StackEmpty(S))
printf(\"括号匹配.\\n\"); else
printf(\"缺少右括号.\\n\"); }
int Match(DataType e,DataType ch) { if(e==\'(\'&&ch==\')\')
return 1; else if(e==\'[\'&&ch==\']\')
return 1; else if(e==\'{\'&&ch==\'}\')
return 1; else
return 0; } 用队列实现在屏幕上打印杨辉三角 /*包含头文件*/ #include #include typedef int DataType;
/*定义链式队列元素的类型为整数类型*/ #define MaxSize 100 void PrintArray(int a[],int n); void YangHuiTriangle(int N);
typedef struct QNode { DataType data; struct QNode* next; }LQNode,*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue;
void InitQueue(LinkQueue *LQ)
/*将带头结点的链式队列初始化为空队列需要把头结点的指针域置为0*/ { LQ->front=(LQNode*)malloc(sizeof(LQNode)); if(LQ->front==NULL) exit(-1);
LQ ->front->next=NULL; /*把头结点的指针域置为为0*/ LQ->rear=LQ->front; } int QueueEmpty(LinkQueue LQ)
/*判断链式队列是否为空，队列为空返回1，否则返回0*/ { if(LQ.front->next==NULL) /*当链式队列为空时，返回1，否则返回0*/
return 1;
else
return 0; } int EnterQueue(LinkQueue *LQ,DataType e) /*将元素e插入到链式队列LQ中，插入成功返回1*/ {
LQNode *s; s=(LQNode*)malloc(sizeof(LQNode)); /*为将要入队的元素申请一个结点的空间*/ if(!s) exit(-1);
/*如果申请空间失败，则退出并返回参数-1*/ s->data=e;
/*将元素值赋值给结点的数据域*/ s->next=NULL;
/*将结点的指针域置为空*/ LQ->rear->next=s;
/*将原来队列的队尾指针指向p*/ LQ->rear=s;
/*将队尾指针指向p*/
return 1; } //int DeleteQueue(LinkQueue *LQ,DataType *e) ///*删除链式队列中的队头元素，并将该元素赋值给e，删除成功返回1，否则返回0*/ //{ //
LQNode *s; //if(LQ->front==LQ->rear) /*在删除元素之前，判断链式队列是否为空*/ //
return 0; //
else //{ //
s=LQ->front->next;
/*使指针p指向队头元素的指针*/ //
*e=s->data;
/*将要删除的队头元素赋值给e*/ //
LQ->front->next=s->next;
/*使头结点的指针指向指针p的下一个结点*/ //
if(LQ->rear==s) LQ->rear=LQ->front; /*如果要删除的结点是队尾，则使队尾指针指向队头指针*/ //
free(s);
/*释放指针p指向的结点*/ //
return 1; //
} //} int GetHead (LinkQueue LQ,DataType *e) /*取链式队列中的队头元素，并将该元素赋值给e，取元素成功返回1，否则返回0*/ {
LQNode *s; if(LQ.front==LQ.rear) /*在取队头元素之前，判断链式队列是否为空*/
return 0; else {
s=LQ.front->next; /*将指针p指向队列的第一个元素即队头元素*/
*e=s->data;
/*将队头元素赋值给e，取出队头元素*/
return 1; } } /*出队操作。*/ int DeleteQueue(LinkQueue *Q,DataType *x) {
/* 将队列Q的队头元素出队，并存放到x所指的存储空间中 */ LQNode * p;
if(Q->front==Q->rear)
return(0); p=Q->front->next; Q->front->next=p->next; /* 队头元素p出队 */ if(Q->front==NULL) /* 如果队中只有一个元素p，则p出队后成为空队 */
Q->rear=Q->front;
*x=p->data; free(p);
/* 释放存储空间 */ return(1); } void YangHuiTriangle(int N) /*链式队列实现打印杨辉三角*/ {
int i,j,k,n; DataType e,t; int temp[MaxSize];
LinkQueue Q; k=0; InitQueue(&Q);
EnterQueue(&Q,1);
/*产生第中间n-2行的元素*/ for(n=2;n
在临时数组中*/ {
k=0;
EnterQueue(&Q,1);
for(i=1;i
并入队列*/
{
DeleteQueue(&Q,&t);
temp[k++]=t;
GetHead(Q,&e);
t=t+e;
EnterQueue(&Q,t);
}
DeleteQueue (&Q,&t);
temp[k++]=t;
PrintArray(temp,k,N);
EnterQueue(&Q,1);
} k=0;
while(!QueueEmpty(Q))
{
/*定义一个临时数组，用于存放每一行的元素*/ /*初始化链队列*/ /*第一行元素入队*/ /*产生第i行元素并入队，同时将第i-1行的元素保存/*第i行的第一个元素入队*/ /*利用队列中第i-1行元素产生第i行的中间i-2个元素/*将第i-1行的元素存入临时数组*/
/*取队头元素*/ /*利用队中第i-1行元素产生第i行元素*/ /*将第i-1行的最后一个元素存入临时数组*/ /*第i行的最后一个元素入队*/ /*将最后一行元素存入数组之前，要将下标k置为0*/ /*将最后一行元素存入临时数组*/
DeleteQueue(&Q,&t);
temp[k++]=t;
if(QueueEmpty(Q))
PrintArray(temp,k,N); } }
void main() { int n; printf(\"请输入要打印的行数：n=:\"); scanf(\"%d\",&n);
YangHuiTriangle(n); } void PrintArray(int a[],int n,int N) /*打印数组中的元素，使能够呈正确的形式输出*/ { int i; static count=0;
/*记录输出的行*/ for(i=0;i
/*打印空格*/
printf(\"
\"); count++; for(i=0;i
/*打印数组中的元素*/
printf(\"%6d\",a[i]); printf(\"\\n\"); } 用栈实现迷宫问题求解 #include #include
#define OVERFLOW -1 #define MAX 100 typedef struct {
int x;
int y;
int d; }Data;
typedef struct {
int pos;
Data data[MAX]; }SNode,*Stack;
Stack InitStack()
{
Stack pStack;
pStack=(Stack)malloc(sizeof(SNode));
if(!pStack)
exit(OVERFLOW);
pStack->pos=-1;
return pStack; }
int IsEmpty(Stack pstack) {
return pstack->pos==-1; }
void Push(Stack pStack,Data x) {
if(pStack->pos>=MAX-1)
exit(OVERFLOW);
else
{
pStack->pos++;
pStack->data[pStack->pos]=x;
} }
void Pop(Stack pStack) {
if(pStack->pos==-1)
exit(OVERFLOW);
else
pStack->pos--; }
Data GetTop(Stack pStack) {
return pStack->data[pStack->pos]; }
Data SetStackElem(int x,int y,int d) {
Data element;
element.x=x;
element.y=y;
element.d=0;
return element; }
void DisplayPath(Stack pStack) {
Data element;
printf(\"The path is:\\n\");
while(!IsEmpty(pStack))
{
element=GetTop(pStack);
Pop(pStack);
printf(\"The node is:(%d,%d)\\n\",element.x,element.y);
} }
void MazePath(int maze[8][11],int direction[4][2],int x1,int y1,int x2,int y2) {
int i,j,k,g,h;
Stack pStack;
Data element;
pStack=InitStack();
maze[x1][y1]=2;
Push(pStack,SetStackElem(x1,y1,0));
while(!IsEmpty(pStack)) {
element=GetTop(pStack);
Pop(pStack);
i=element.x;
j=element.y;
k = element.d;
while (k
{
g=i+direction[k][0];
h=j+direction[k][1];
if(g==x2 && h==y2 && maze[g][h]==0)
{
Push(pStack,SetStackElem(i,j,k));
Push(pStack,SetStackElem(x2,y2,k));
DisplayPath(pStack);
return;
}
if(maze[g][h]==0)
{
maze[g][h]=2;
Push(pStack,SetStackElem(i,j,k+1));
i=g;
j=h;
k=0;
}
else
k++;
} }
printf(\"The path has not been found\\n\"); }
void main() {
int direction[4][2]={0,1,1,0,0,-1,-1,0};
int maze[8][11]= {
1,1,1,1,1,1,1,1,1,1,1,
1,0,1,0,0,1,1,1,0,0,1,
1,0,0,0,0,0,1,0,0,1,1,
1,0,1,1,1,0,0,0,1,1,1,
1,0,0,0,1,0,1,1,0,1,1,
1,1,0,0,1,0,1,1,0,0,1,
1,1,1,0,1,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,1 };
int i,j;
printf(\"The maze is:\\n\");
for(i=0;i
for(j=0;j
printf(\"%2d\",maze[i][j]);
printf(\"\\n\"); }; MazePath(maze,direction,1,1,6,9); } 用队列实现迷宫问题求解 #include #define r 64 #define m2 8 #define n2 10 int m=m2-2,n=n2-2; typedef struct { int x,y;
//行列坐标
int pre; }sqtype;
sqtype sq[r]; struct moved { int x, y; //坐标增量，取值-1，0，1 }move[8];
int maze[m2][n2];
int PATH(int maze[][n2]) //找迷宫maze的路径 { int i,j,k,v,front,rear,x,y; int mark[m2][n2]; for(i=0;i
for(j=0;j
mark[i ][j]=0; printf(\"Please Input move array\\n\"); for(i=0;i
//标记入口以到达过
while(front
x=sq[front].x;
y=sq[front].y;
//(x,y)为出发点
for(v=0;v
{
i=x+move[v].x;
j=y+move[v].y;
if((maze[i ][j]==0)&&(mark[i ][j]==0))//(i,j)为可以到达点，将起入队
{
rear++;
sq[rear].pre=front;
mark[i ][j]=1; //标记(i,j)已经到达过
}
if((i==m)&&(j==n))
//到达出口
{
printf(\"THE PATH: \\n\");
k=rear;
do
{
printf(\"(%d %d)
k=sq[k].pre;//找前一点
}while(k!=0);//k=0是已经到达
for(i=1;i
printf(\"%3d\",i);
printf(\"\\n\");
for(i=1;i
printf(\"%3d\",sq[i ].x);
printf(\"\\n\");
for(i=1;i
printf(\"%3d\",sq[i ].y);
printf(\"\\n\");
for(i=1;i
printf(\"%3d\",sq[i ].pre);
printf(\"\\n\");
return(1);
//成功返回
}
}
front++;
//出队，front 指向新的出发点
}
}
//队空，循环结束
printf(\"There is no path! \\n\"); return(0);
//迷宫没有路径返回 }
main() { int i,j; for(i=0;i
maze[0][i ]=1;
maze[7][i ]=1; } for(i=0;i
maze[i ][0]=1;
maze[i ][9]=1; } /*for(i=1;i
for(j=1;j
{
printf(\"%d %d\",i,j);
scanf(\"%d\",&maze[i ][j]);
}*/
maze[1][1]=0;maze[1][2]=1;maze[1][3]=0;maze[1][4]=1;maze[1][5]=1;maze[1][6]=0;maze[1][7]=1;maze[1][8]=1;
maze[2][1]=1;maze[2][2]=0;maze[2][3]=0;maze[2][4]=1;maze[2][5]=1;maze[2][6]=0;maze[2][7]=1;maze[2][8]=0; maze[3][1]=0;maze[3][2]=1;maze[3][3]=1;maze[3][4]=0;maze[3][5]=0;maze[3][6]=1;maze[3][7]=1;maze[3][8]=1; maze[4][1]=1;maze[4][2]=0;maze[4][3]=0;maze[4][4]=1;maze[4][5]=1;maze[4][6]=0;maze[3][7]=0;maze[4][8]=1; maze[5][1]=1;maze[5][2]=1;maze[5][3]=0;maze[5][4]=0;maze[5][5]=1;maze[5][6]=1;maze[5][7]=0;maze[5][8]=1; maze[6][1]=0;maze[6][2]=1;maze[6][3]=1;maze[6][4]=1;maze[6][5]=0;maze[6][6]=0;maze[6][7]=0;maze[6][8]=0;
printf(\"\\n\"); for(i=0;i
for(j=0;j
printf(\"%d\",maze[i ][j]);
printf(\"\\n\"); } PATH(maze); }
分别用队列实现一个列车调度系统。
实验3 树的应用
一、实验目的
1、领会并理解二叉树的类型定义。
2、熟练掌握二叉树的主要特性，。
3、熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。
4、熟练掌握二叉树和树的各种存储结构及其建立的算法。
5、了递归算法的实现过程。
二、实验内容及步骤
1、实现二叉树的抽象数据类型。
2、构造一棵二叉树并用递归实现其先序、中序、后序遍历算法并验证。
3、用非递归算法实现二叉树的中序遍历。
4、给出一段报文和每个字符出现的概率，对其进行哈夫曼编码和解码。
三、实验步骤与调试过程
利用栈来实现；根结点进栈，之后栈非空，弹出，接着根节点的右结点进栈，之后，
左节点进栈；接着，弹出栈顶元素,此结点的右结点进栈，之后左节点进栈，弹出栈顶元素，直到栈为空。
从根节点开始，循环，只要有左子节点则进栈，直到左子节点为空。接着弹出栈顶输出，判断该结点是否有右子节点，若有则进栈，若没有继续弹栈。有右子节点的情况，判断该节点是否有左子节点，有则进栈，直到左子节点为空；若该右子节点没有左子节点，则弹栈；判断弹出的节点，是否有右子节点，若有则进栈，没有继续弹栈；接着又要判断刚进栈的这个节点，是否有左子节点，有则进栈，没有则继续弹栈。
从根结点开始，只要左子节点非空，则进栈，直到左子节点为空为止。取出栈顶元素，判断取出的栈顶元素是否有右子节点，或者右子节点是否被访问过，若满足条件，则输出该结点，同时弹栈，并且记录下该访问的节点。取出的栈顶元素，若有右子节点，且未被访问过，则指针继续移动到右子节点。
四、实验结果
五、疑难小结
用图形显示遍历能够是人更好的明白二叉树的遍历，更好的理解二叉树的链式结构的存储，理解二叉树遍历的过程，能够针对递归结构的二叉树进行查询、修改、删除的操作。
六、主要算法和程序清单
二叉树递归实现其先序、中序、后序遍历算法并验证。 /*包含头文件及宏定义*/ #include #include #include typedef char DataType; #define MaxSize 100
/*定义栈的最大容量*/ /*函数的声明*/ void CreateBitTree2(BiTree *T,char str[]); /*利用括号嵌套的字符串建立二叉树的函数声明*/ void LevelPrint(BiTree T);
/*按层次输出二叉树的结点*/ void TreePrint(BiTree T,int nLayer); /*按树状打印二叉树*/
typedef struct Node
/*二叉链表存储结构类型定义*/ { DataType data;
/*数据域*/ struct Node *lchild;
/*指向左孩子结点*/ struct Node *rchild;
/*指向右孩子结点*/ }*BiTree,BitNode;
void InitBitTree(BiTree *T) /*二叉树的初始化操作*/ { *T=NULL; }
void DestroyBitTree(BiTree *T) /*销毁二叉树操作*/ { if(*T)
/*如果是非空二叉树*/ {
if((*T)->lchild)
DestroyBitTree(&((*T)->lchild));
if((*T)->rchild)
DestroyBitTree(&((*T)->rchild));
free(*T);
*T=NULL; } } void CreateBitTree(BiTree *T) /*递归创建二叉树*/ {
DataType ch;
scanf(\"%c\",&ch);
if(ch==\'#\')
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BitNode)); /*生成根结点*/
if(!(*T))
exit(-1);
(*T)->data=ch;
CreateBitTree(&((*T)->lchild));
/*构造左子树*/
CreateBitTree(&((*T)->rchild));
/*构造右子树*/
} } int InsertLeftChild(BiTree p,BiTree c) /*二叉树的左插入操作*/ {
if(p)
/*如果指针p不空*/
{
c->rchild=p->lchild;
/*p的原来的左子树成为c的右子树*/
p->lchild=c;
/*子树c作为p的左子树*/
return 1;
}
return 0; } int InsertRightChild(BiTree p,BiTree c) /*二叉树的右插入操作*/
{ if(p)
/*如果指针p不空*/
{
c->rchild=p->rchild;
/*p的原来的右子树作为c的右子树*/
p->rchild=c;
/*子树c作为p的右子树*/
return 1;
}
return 0; } BiTree Point(BiTree T,DataType e) /*查找元素值为e的结点的指针*/ { BiTree Q[MaxSize];
/*定义一个队列，用于存放二叉树中结点的指针*/ int front=0,rear=0;
/*初始化队列*/
BitNode *p;
if(T)
/*如果二叉树非空*/
{
Q[rear]=T;
rear++;
while(front!=rear) /*如果队列非空*/
{
p=Q[front];
/*取出队头指针*/
front++;
/*将队头指针出队*/
if(p->data==e)
return p;
if(p->lchild)
/*如果左孩子结点存在，将左孩子指针入队*/
{
Q[rear]=p->lchild; /*左孩子结点的指针入队*/
rear++;
}
if(p->rchild)
/*如果右孩子结点存在，将右孩子指针入队*/
{
Q[rear]=p->rchild; /*右孩子结点的指针入队*/
rear++;
}
}
}
return NULL; } DataType LeftChild(BiTree T,DataType e) /*返回二叉树的左孩子结点元素值操作*/ {
BiTree p;
if(T)
{
p=Point(T,e);
if(p&&p->lchild)
在*/
return p->lchild->data;
}
return; } DataType RightChild(BiTree T,DataType e) /*返回二叉树的右孩子结点元素值操作*/ {
BiTree p;
if(T)
{
p=Point(T,e);
if(p&&p->rchild)
在*/
return p->rchild->data;
}
return; } int DeleteLeftChild(BiTree p) /*二叉树的左删除操作*/ {
if(p)
{
DestroyBitTree(&(p->lchild));
return 1;
}
return 0; } int DeleteRightChild(BiTree p) /*二叉树的左删除操作*/ {
if(p)
{
DestroyBitTree(&(p->rchild));
return 1;
}
return 0; }
void main()
/*如果二叉树不空*/
/*p是元素值e的结点的指针*/ /*如果p不为空且p的左孩子结点存
/*返回p的左孩子结点的元素值*/
/*如果二叉树不空*/
/*p是元素值e的结点的指针*/ /*如果p不为空且p的右孩子结点存/*返回p的右孩子结点的元素值*/
/*如果p不空*/
/*删除左子树*/
/*如果p不空*/
/*删除右子树*/
{ BiTree T,root; printf(\"根据括号嵌套(a(b(c,d),e(f(,g),h(i)))建立二叉树:\\n\"); CreateBitTree2(&T,\"(a(b(c,d),e(f(,g),h(i)))\"); printf(\"按层次输出二叉树的序列：\\n\"); LevelPrint(T); printf(\"\\n\"); printf(\"按树状打印二叉树：\\n\"); TreePrint(T,1); printf(\"根据括号嵌套(A(B(D(,H),E(,I)),C(F,G)))建立二叉树:\\n\"); CreateBitTree2(&root,\"(A(B(D(,H),E(,I)),C(F,G)))\"); printf(\"按层次输出二叉树的序列：\\n\"); LevelPrint(root); printf(\"\\n\"); printf(\"按树状打印二叉树：\\n\"); TreePrint(root,1); DestroyBitTree(&T); DestroyBitTree(&root); }
void LevelPrint(BiTree T) /*按层次打印二叉树中的结点*/ {
BiTree queue[MaxSize];
/*定义一个队列，用于存放结点的指针*/ BitNode *p;
int front,rear;
/*定义队列的队头指针和队尾指针*/
front=rear=-1;
/*队列初始化为空*/
rear++;
/*队尾指针加1*/
queue[rear]=T;
/*将根结点指针入队*/
while(front!=rear)
/*如果队列不为空*/
{
front=(front+1)%MaxSize;
p=queue[front];
/*取出队头元素*/
printf(\"%c \",p->data);
/*输出根结点*/
if(p->lchild!=NULL)
/*如果左孩子不为空，将左孩子结点指针入队*/
{
rear=(rear+1)%MaxSize;
queue[rear]=p->lchild;
}
if(p->rchild!=NULL)
/*如果右孩子不为空，将右孩子结点指针入队*/
{
rear=(rear+1)%MaxSize;
queue[rear]=p->rchild;
}
}
} void TreePrint(BiTree T,int level) /*按树状打印的二叉树*/ {
int i; if(T==NULL)
/*如果指针为空，返回上一层*/
return; TreePrint(T->rchild,level+1);
/*打印右子树，并将层次加1*/
for(i=0;i
/*按照递归的层次打印空格*/
printf(\"
\"); printf(\"%c\\n\",T->data);
/*输出根结点*/
TreePrint(T->lchild,level+1);
/*打印左子树，并将层次加1*/ }
void CreateBitTree2(BiTree *T,char str[]) /*利用括号嵌套的字符串建立二叉链表*/ { char ch; BiTree stack[MaxSize];
/*定义栈，用于存放指向二叉树中结点的指针*/ int top=-1;
/*初始化栈顶指针*/ int flag,k; BitNode *p; *T=NULL,k=0; ch=str[k]; while(ch!=\'\\0\')
/*如果字符串没有结束*/ {
switch(ch)
{
case \'(\':
stack[++top]=p;
flag=1;
break;
case \')\':
top--;
break;
case \',\':
flag=2;
break;
default:
p=(BiTree)malloc(sizeof(BitNode));
p->data=ch;
p->lchild=NULL;
p->rchild=NULL;
if(*T==NULL) /*如果是第一个结点，表示是根结点*/
*T=p;
else
{
switch(flag)
{
case 1:
stack[top]->lchild=p;
break;
case 2:
stack[top]->rchild=p;
break;
}
}
}
ch=str[++k]; }
}
void PreOrderTraverse(BiTree T) /*先序遍历二叉树的递归实现*/ {
if(T)
/*如果二叉树不为空*/
{
printf(\"%2c\",T->data);
/*访问根结点*/
PreOrderTraverse(T->lchild); /*先序遍历左子树*/
PreOrderTraverse(T->rchild);
/*先序遍历右子树*/
} } void InOrderTraverse(BiTree T) /*中序遍历二叉树的递归实现*/ {
if(T)
/*如果二叉树不为空*/ {
InOrderTraverse(T->lchild);
/*中序遍历左子树*/
printf(\"%2c\",T->data);
/*访问根结点*/
InOrderTraverse(T->rchild); /*中序遍历右子树*/
} } void PostOrderTraverse(BiTree T) /*后序遍历二叉树的递归实现*/
{
if(T)
/*如果二叉树不为空*/ {
PostOrderTraverse(T->lchild); /*后序遍历左子树*/
PostOrderTraverse(T->rchild);
/*后序遍历右子树*/
printf(\"%2c\",T->data);
/*访问根结点*/
} } 用非递归算法实现二叉树的中序遍历 /*包含头文件及宏定义*/ #include #include #include typedef char DataType; #define MaxSize 100
/*定义栈的最大容量*/ /*函数的声明*/ void InOrderTraverse2(BiTree T); /*二叉树的中序遍历的非递归函数声明*/ void CreateBitTree2(BiTree *T,char str[]); /*利用括号嵌套的字符串建立二叉树的函数声明*/
typedef struct Node
/*二叉链表存储结构类型定义*/ { DataType data;
/*数据域*/ struct Node *lchild;
/*指向左孩子结点*/ struct Node *rchild;
/*指向右孩子结点*/ }*BiTree,BitNode;
void InitBitTree(BiTree *T) /*二叉树的初始化操作*/ { *T=NULL; }
//BiTree CreateBitTree() //{ //
char ch; //
BiTree b; //
ch = getchar(); // //
if(ch == \'@\')
//表示该结点为空结点 //
{ //
b = NULL; //
}
//
else //
{ //
b = (BiTree )malloc(sizeof(BitNode)); //
b->data = ch; //
b->lchild = CreateBitTree(); //
b->rchild = CreateBitTree(); //
} // //
return b; //}
void DestroyBitTree(BiTree *T) /*销毁二叉树操作*/ { if(*T)
/*如果是非空二叉树*/ {
if((*T)->lchild)
DestroyBitTree(&((*T)->lchild));
if((*T)->rchild)
DestroyBitTree(&((*T)->rchild));
free(*T);
*T=NULL; } } void CreateBitTree(BiTree *T) /*递归创建二叉树*/ {
DataType ch;
scanf(\"%c\",&ch);
if(ch==\'#\')
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BitNode)); /*生成根结点*/
if(!(*T))
exit(-1);
(*T)->data=ch;
CreateBitTree(&((*T)->lchild));
/*构造左子树*/
CreateBitTree(&((*T)->rchild));
/*构造右子树*/
} } int InsertLeftChild(BiTree p,BiTree c) /*二叉树的左插入操作*/ {
if(p)
/*如果指针p不空*/
{
c->rchild=p->lchild;
/*p的原来的左子树成为c的右子树*/
p->lchild=c;
/*子树c作为p的左子树*/
return 1;
}
return 0; } int InsertRightChild(BiTree p,BiTree c) /*二叉树的右插入操作*/ { if(p)
/*如果指针p不空*/
{
c->rchild=p->rchild;
/*p的原来的右子树作为c的右子树*/
p->rchild=c;
/*子树c作为p的右子树*/
return 1;
}
return 0; } BiTree Point(BiTree T,DataType e) /*查找元素值为e的结点的指针*/ { BiTree Q[MaxSize];
/*定义一个队列，用于存放二叉树中结点的指针*/ int front=0,rear=0;
/*初始化队列*/
BitNode *p;
if(T)
/*如果二叉树非空*/
{
Q[rear]=T;
rear++;
while(front!=rear) /*如果队列非空*/
{
p=Q[front];
/*取出队头指针*/
front++;
/*将队头指针出队*/
if(p->data==e)
return p;
if(p->lchild)
/*如果左孩子结点存在，将左孩子指针入队*/
{
Q[rear]=p->lchild; /*左孩子结点的指针入队*/
rear++;
}
if(p->rchild)
/*如果右孩子结点存在，将右孩子指针入队*/
{
Q[rear]=p->rchild; /*右孩子结点的指针入队*/
rear++;
}
}
}
return NULL; } DataType LeftChild(BiTree T,DataType e) /*返回二叉树的左孩子结点元素值操作*/ {
BiTree p;
if(T)
{
p=Point(T,e);
if(p&&p->lchild)
在*/
return p->lchild->data;
}
return; } DataType RightChild(BiTree T,DataType e) /*返回二叉树的右孩子结点元素值操作*/ {
BiTree p;
if(T)
{
p=Point(T,e);
if(p&&p->rchild)
在*/
return p->rchild->data;
}
return; } int DeleteLeftChild(BiTree p) /*二叉树的左删除操作*/ {
if(p)
{
DestroyBitTree(&(p->lchild));
return 1;
}
return 0; } int DeleteRightChild(BiTree p) /*二叉树的左删除操作*/
/*如果二叉树不空*/
/*p是元素值e的结点的指针*/ /*如果p不为空且p的左孩子结点存
/*返回p的左孩子结点的元素值*/
/*如果二叉树不空*/
/*p是元素值e的结点的指针*/ /*如果p不为空且p的右孩子结点存/*返回p的右孩子结点的元素值*/
/*如果p不空*/
/*删除左子树*/
{
if(p)
/*如果p不空*/
{
DestroyBitTree(&(p->rchild));
/*删除右子树*/
return 1;
}
return 0; }
void main() { BiTree T,root; InitBitTree(&T); printf(\"根据输入二叉树的先序序列创建二叉树(\'#\'表示结束)：\\n\"); CreateBitTree(&T); printf(\"二叉树的中序序列：\\n\"); printf(\"递归：\\t\"); InOrderTraverse(T); printf(\"\\n\"); printf(\"非递归：\"); InOrderTraverse2(T); printf(\"\\n\"); printf(\"根据括号嵌套的字符串建立二叉树:\\n\"); CreateBitTree2(&root,\"(a(b(c,d),e(f(,g),h(i)))\"); printf(\"二叉树的中序序列：\\n\"); InOrderTraverse(root); printf(\"\\n\"); DestroyBitTree(&T); DestroyBitTree(&root); }
void CreateBitTree2(BiTree *T,char str[]) /*利用括号嵌套的字符串建立二叉链表*/ { char ch; BiTree stack[MaxSize];
/*定义栈，用于存放指向二叉树中结点的指针*/ int top=-1;
/*初始化栈顶指针*/ int flag,k; BitNode *p; *T=NULL,k=0; ch=str[k]; while(ch!=\'\\0\')
/*如果字符串没有结束*/ {
switch(ch)
{
case \'(\':
stack[++top]=p;
flag=1;
break;
case \')\':
top--;
break;
case \',\':
flag=2;
break;
default:
p=(BiTree)malloc(sizeof(BitNode));
p->data=ch;
p->lchild=NULL;
p->rchild=NULL;
if(*T==NULL) /*如果是第一个结点，表示是根结点*/
*T=p;
else
{
switch(flag)
{
case 1:
stack[top]->lchild=p;
break;
case 2:
stack[top]->rchild=p;
break;
}
}
}
ch=str[++k]; }
}
void InOrderTraverse2(BiTree T) /*中序遍历二叉树的非递归实现*/ { BiTree stack[MaxSize];
/*定义一个栈，用于存放结点的指针*/ int top;
/*定义栈顶指针*/ BitNode *p;
/*定义一个结点的指针*/ top=0;
/*初始化栈*/ p=T;
while(p!=NULL||top>0) {
while(p!=NULL)
/*如果p不空，访问根结点，遍历左子树*/
{
stack[top++]=p;
/*将p入栈*/
p=p->lchild;
/*遍历左子树*/
}
if(top>0)
/*如果栈不空*/
{
p=stack[--top];
/*栈顶元素出栈*/
printf(\"%2c\",p->data);
/*访问根结点*/
p=p->rchild;
/*遍历右子树*/
} } } 给出一段报文和每个字符出现的概率，对其进行哈夫曼编码和解码。 #include #include #include #include #define infinity 10000
/*定义一个无限大的值*/ /*哈夫曼树类型定义*/ typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree;
typedef char **HuffmanCode; /*存放哈夫曼编码*/ int Min(HuffmanTree t,int n); void Select(HuffmanTree *t,int n,int *s1,int *s2); void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n); void HuffmanCoding2(HuffmanTree *HT,HuffmanCode *HC,int *w,int n); int Min(HuffmanTree t,int n) /*返回树中n个结点中权值最小的结点序号*/ {
int i,flag; int f=infinity;
/*f为一个无限大的值*/ for(i=1;i
if(t[i].weight
f=t[i].weight,flag=i;
t[flag].parent=1;
/*给选中的结点的双亲结点赋值1，避免再次查找该结点*/
return flag; }
void Select(HuffmanTree *t,int n,int *s1,int *s2) /*在n个结点中选择两个权值最小的结点序号，其中s1最小，s2次小*/ {
int x; *s1=Min(*t,n); *s2=Min(*t,n); if((*t)[*s1].weight>(*t)[*s2].weight) /*如果序号s1的权值大于序号s2的权值，将两者交换，使s1最小，s2次小*/ {
x=*s1;
*s1=*s2;
*s2=x; } } void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) /*构造哈夫曼树HT，哈夫曼树的编码存放在HC中，w为n个字符的权值*/ {
int m,i,s1,s2,start; unsigned int c,f; HuffmanTree p; char *cd; if(n
return; m=2*n-1; *HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*第零个单元未用*/ for(p=*HT+1,i=1;i
/*初始化n个叶子结点*/ {
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0; } for(;i
/*将n-1个非叶子结点的双亲结点初始化化为0*/
(*p).parent=0; for(i=n+1;i
/*构造哈夫曼树*/ {
Select(HT,i-1,&s1,&s2); /*查找树中权值最小的两个结点*/
(*HT)[s1].parent=(*HT)[s2].parent=i;
(*HT)[i].lchild=s1;
(*HT)[i].rchild=s2;
(*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight; }
/*从叶子结点到根结点求每个字符的哈夫曼编码*/ *HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); cd=(char*)malloc(n*sizeof(char)); /*为哈夫曼编码动态分配空间*/ cd[n-1]=\'\\0\';
/*求n个叶子结点的哈夫曼编码*/ for(i=1;i
start=n-1;
/*编码结束符位置*/
for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent) /*从叶子结点到根结点求编码*/
if((*HT)[f].lchild==c)
cd[--start]=\'0\';
else
cd[--start]=\'1\';
(*HC)[i]=(char*)malloc((n-start)*sizeof(char)); /*为第i个字符编码分配空间*/
strcpy((*HC)[i],&cd[start]);
/*将当前求出结点的哈夫曼编码复制到HC*/ } free(cd); }
void main() { HuffmanTree HT; HuffmanCode HC; int *w,n,i; printf(\"请输入叶子结点的个数: \"); scanf(\"%d\",&n); w=(int*)malloc(n*sizeof(int)); /*为n个结点的权值分配内存空间*/ for(i=0;i
printf(\"请输入第%d个结点的权值:\",i+1);
scanf(\"%d\",w+i); } HuffmanCoding(&HT,&HC,w,n); for(i=1;i
printf(\"哈夫曼编码:\");
puts(HC[i]); }
HuffmanCoding2(&HT,&HC,w,n); for(i=1;i
printf(\"哈夫曼编码:\");
puts(HC[i]); }
/*释放内存空间*/ for(i=1;i
free(HC[i]); free(HC); free(HT); } void HuffmanCoding2(HuffmanTree *HT,HuffmanCode *HC,int *w,int n)
/*构造哈夫曼树HT，并从根结点到叶子结点求赫夫曼编码并保存在HC中*/ {
int s1,s2,i,m;
unsigned int r,cdlen;
char *cd; HuffmanTree p;
if(n
return; m=2*n-1; *HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=*HT+1,i=1;i
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0; } for(;i
(*p).parent=0; /*构造哈夫曼树HT*/ for(i=n+1;i
{
Select(HT,i-1,&s1,&s2);
(*HT)[s1].parent=(*HT)[s2].parent=i;
(*HT)[i].lchild=s1;
(*HT)[i].rchild=s2;
(*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight; } /*从根结点到叶子结点求赫夫曼编码并保存在HC中*/ *HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); cd=(char*)malloc(n*sizeof(char));
r=m;
/*从根结点开始*/
cdlen=0;
/*编码长度初始化为0*/ for(i=1;i
(*HT)[i].weight=0; /*将weight域作为状态标志*/ while(r) {
if((*HT)[r].weight==0)/*如果weight域等于零，说明左孩子结点没有遍历*/
{
(*HT)[r].weight=1; /*修改标志*/
if((*HT)[r].lchild!=0)/*如果存在左孩子结点，则将编码置为0*/
{
r=(*HT)[r].lchild;
cd[cdlen++]=\'0\';
}
else if((*HT)[r].rchild==0)/*如果是叶子结点，则将当前求出的编码保存到HC中*/
{
(*HC)[r]=(char *)malloc((cdlen+1)*sizeof(char));
cd[cdlen]=\'\\0\';
strcpy((*HC)[r],cd);
}
}
else if((*HT)[r].weight==1)/*如果已经访问过左孩子结点，则访问右孩子结点*/
{
(*HT)[r].weight=2; /*修改标志*/
if((*HT)[r].rchild!=0)
{
r=(*HT)[r].rchild;
cd[cdlen++]=\'1\';
}
}
else
/*如果左孩子结点和右孩子结点都已经访问过，则退回到双亲结点*/
{
(*HT)[r].weight=0;
r=(*HT)[r].parent;
--cdlen;
/*编码长度减1*/
} } free(cd); }
实验4 图论及其应用
一、实验目的
1、了解图的基本概念及术语,并能够熟练掌握图的两种存储结构(邻接矩阵和邻接表)。
2、理解最小生成树的概念，能按Prim算法构造最小生成树。
3、掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)、拓扑排序、关键路径、最短路径的算法思想。
二、实验内容及步骤
1、实现网（有权图）的存储结构。
2、利用prim算法构造它的最小生成树。
3、选择一个源点，寻找从原点出发到达其它顶点的最短路径。
三、实验步骤与调试过程
在程序编辑的过程中，有许多地方出现不能顺序运行的，还有代码出现遗漏出错，图的遍历是重点但因为知识的残缺不能完整的编译出来，又或者编译的程序不能得到正确的结果，再通过多人的合作共同讨论后得到了满意的解决。
四、实验结果
五、疑难小结
经过这次这么复杂而程序实验，我终于发现了调用函数的巨大优越性，以前遇到倒是很短的程序，感觉调用有点多余，但复杂的程序如果不采用调用的话，会使程序非常乱，改程序是不知道从哪改，调用函数能够更好使程序简洁化，层次化，更加让人看懂，这次试验的逻辑性给我们很大启发，本次试验让我对图有了更深的认识，再通过多次的更改后终于将实验做出来，在实验中也出现了许多问题，又不出结果，又不能运行的，但最终只要努力都会搞定的。
六、主要算法和程序清单
实现网（有权图）的存储结构。 邻接矩阵存储结构 #include #include #include #include typedef char VertexType[4]; typedef char InfoPtr; typedef int VRType; #define INFINITY 10000
/*定义一个无限大的值*/ #define MaxSize 50
/*最大顶点个数*/ typedef enum{DG,DN,UG,UN}GraphKind; /*图的类型：有向图、有向网、无向图和无向网*/ typedef struct { VRType adj;
/*对于无权图，用1表示相邻，0表示不相邻；对于带权图，存储权值*/ InfoPtr *info;
/*与弧或边的相关信息*/ }ArcNode,AdjMatrix[MaxSize][MaxSize];
typedef struct
/*图的类型定义*/ { VertexType vex[MaxSize]; /*用于存储顶点*/ AdjMatrix arc;
/*邻接矩阵，存储边或弧的信息*/ int vexnum,arcnum;
/*顶点数和边（弧）的数目*/ GraphKind kind;
/*图的类型*/ }MGraph; void CreateGraph(MGraph *N); int LocateVertex(MGraph N,VertexType v); void DestroyGraph(MGraph *N); void DisplayGraph(MGraph N);
void CreateGraph(MGraph *N) /*采用邻接矩阵表示法创建有向网N*/ {
int i,j,k,w,InfoFlag,len; char s[MaxSize]; VertexType v1,v2; printf(\"请输入有向网N的顶点数,弧数,弧的信息(是:1,否:0): \"); scanf(\"%d,%d,%d\",&(*N).vexnum,&(*N).arcnum,&InfoFlag); printf(\"请输入%d个顶点的值(<%d个字符):\\n\",N->vexnum,MaxSize); for(i=0;ivexnum;++i) /*创建一个数组，用于保存网的各个顶点*/
scanf(\"%s\",N->vex[i]); for(i=0;ivexnum;i++) /*初始化邻接矩阵*/
for(j=0;jvexnum;j++)
{
N->arc[i][j].adj=INFINITY;
N->arc[i][j].info=NULL; /*弧的信息初始化为空*/
}
printf(\"请输入%d条弧的弧尾 弧头 权值(以空格作为间隔): \\n\",N->arcnum);
for(k=0;karcnum;k++)
{
scanf(\"%s%s%d\",v1,v2,&w); /*输入两个顶点和弧的权值*/
i=LocateVertex(*N,v1);
j=LocateVertex(*N,v2);
N->arc[i][j].adj=w;
if(InfoFlag)
/*如果弧包含其它信息*/
{
printf(\"请输入弧的相关信息: \");
gets(s);
len=strlen(s);
if(len)
{
N->arc[i][j].info=(char*)malloc((len+1)*sizeof(char)); /* 有向 */
strcpy(N->arc[i][j].info,s);
}
}
}
N->kind=DN;
/*图的类型为有向网*/ } int LocateVertex(MGraph N,VertexType v) /*在顶点向量中查找顶点v，找到返回在向量的序号，否则返回-1*/ {
int i; for(i=0;i
if(strcmp(N.vex[i],v)==0)
return i;
return -1; }
void DestroyGraph(MGraph *N) /*销毁网N*/ {
int i,j; for(i=0;ivexnum;i++)
/*释放弧的相关信息*/
for(j=0;jvexnum;j++)
if(N->arc[i][j].adj!=INFINITY) /*如果存在弧*/
if(N->arc[i][j].info!=NULL) /*如果弧有相关信息，释放该信息所占用空间*/
{
free(N->arc[i][j].info);
N->arc[i][j].info=NULL;
} N->vexnum=0; /*将网的顶点数置为0*/ N->arcnum=0; /*将网的弧的数目置为0*/ }
void DisplayGraph(MGraph N) /*输出邻接矩阵存储表示的图G*/ {
int i,j; printf(\"有向网具有%d个顶点%d条弧，顶点依次是: \",N.vexnum,N.arcnum); for(i=0;i
/*输出网的顶点*/
printf(\"%s \",N.vex[i]); printf(\"\\n有向网N的:\\n\");
/*输出网N的弧*/ printf(\"序号i=\"); for(i=0;i
printf(\"%8d\",i);
printf(\"\\n\"); for(i=0;i
printf(\"%8d\",i);
for(j=0;j
printf(\"%8d\",N.arc[i][j].adj);
printf(\"\\n\");
} } void main() {
MGraph N; printf(\"创建一个网：\\n\"); CreateGraph(&N); printf(\"输出网的顶点和弧：\\n\"); DisplayGraph(N); printf(\"销毁网：\\n\"); DestroyGraph(&N); } 利用prim算法构造它的最小生成树。 #include #include #include #include typedef char VertexType[4]; typedef char InfoPtr; typedef int VRType; #define INFINITY 10000
/*定义一个无限大的值*/ #define MaxSize 50
/*最大顶点个数*/ typedef enum{DG,DN,UG,UN}GraphKind; /*图的类型：有向图、有向网、无向图和无向网*/ typedef struct { VRType adj;
/*对于无权图，用1表示相邻，0表示不相邻；对于带权图，存储权值*/ InfoPtr *info;
/*与弧或边的相关信息*/ }ArcNode,AdjMatrix[MaxSize][MaxSize]; typedef struct
/*图的类型定义*/ { VertexType vex[MaxSize]; /*用于存储顶点*/ AdjMatrix arc;
/*邻接矩阵，存储边或弧的信息*/ int vexnum,arcnum;
/*顶点数和边（弧）的数目*/ GraphKind kind;
/*图的类型*/ }MGraph;
/*记录从顶点集合U到V-U的代价最小的边的数组定义*/ typedef struct {
VertexType adjvex; VRType lowcost; }closeedge[MaxSize]; void CreateGraph(MGraph *N); int LocateVertex(MGraph N,VertexType v); void DestroyGraph(MGraph *N); void DisplayGraph(MGraph N);
void Prim(MGraph G,VertexType u); int MiniNum(closeedge SZ,MGraph G);
void main() {
MGraph N; printf(\"创建一个无向网：\\n\"); CreateGraph(&N); DisplayGraph(N); Prim(N,\"A\");
DestroyGraph(&N); } void Prim(MGraph G,VertexType u) /*利用普里姆算法求从第u个顶点出发构造网G的最小生成树T*/ {
int i,j,k; closeedge closedge; k=LocateVertex(G,u); /*k为顶点u对应的序号*/ for(j=0;j
strcpy(closedge[j].adjvex,u);
closedge[j].lowcost=G.arc[k][j].adj; } closedge[k].lowcost=0; /*初始时集合U只包括顶点u*/ printf(\"无向网的最小生成树的各条边分别是:\\n\"); for(i=1;i
k=MiniNum(closedge,G); /*k为与U中顶点相邻接的下一个顶点的序号*/
printf(\"(%s-%s)\\n\",closedge[k].adjvex,G.vex[k]); /*输出生成树的边*/
closedge[k].lowcost=0; /*第k顶点并入U集*/
for(j=0;j
if(G.arc[k][j].adj
《数据结构(C语言版)清华大学出版社》复习总结(视频+课本+截图)
《数据结构(C语言版)清华大学出版社》复习总结(视频+课本+截图)
