Practice Report for Data Structures and Algorithm Analysis

Data Structures Course Report

 Candidate:     

 Student Number: 20101000639

 Major :         Communication Engineering

 Supervisor :     Wu rangzhong

          China University of Geosciences(Wuhan)

Wuhan, Hubei 430074, P. R. China

july 12, 2013

链表实现线性表

一、    实验目的与要求

1、实现单链表的建立；

2、掌握单链表的插入、删除和查找运算；

3、熟练进行C语言源程序的编辑调试。

二、    实验内容

（1）建立带表头结点的单链表；

首先输入结束标志，然后建立循环逐个输入数据，直到输入结束标志。

数据输入的函数为：

LNode *createtail()

{

    LNode *s,*r;

    int x,tag;

    printf("input the sign of ending:");  /*输入结束标志*/

    scanf("%d",&tag);

    h=(LNode * )malloc(sizeof(LNode));  /*建立表头结点*/

    h->data=tag;

    r=h;

    printf("input the data:");

    scanf("%d",&x);

    while(x!=tag)       /*建立循环逐个输入数据*/

    {

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

        s->data=x;

        r->link=s;

        r=s;

        scanf("%d",&x);

    }

    r->link=NULL;

    return h;

}

（2）输出单链表中所有结点的数据域值；

    

     首先获得表头结点地址，然后建立循环逐个输出数据，直到地址为空。

     数据输出的函数为：

     void output(LNode *h)

{

        LNode *r;

        int i;

        r=h;

        for(i=1;r->link!=NULL;i++)

              {

               printf("%d.%d\n",i,r->link->data);

               r=r->link;

        }           

}

（3）输入x,y在第一个数据域值为x的结点之后插入结点y，若无结点x，则在表尾插入结点y;

       建立两个结构体指针，一个指向当前结点，另一个指向当前结点的上一结点，建立循环扫描链表。当当前结点指针域不为空且数据域等于x的时候，申请结点并给此结点数据域赋值为y，然后插入当前结点后面，退出函数；当当前结点指针域为空的时候，申请结点并给此结点数据域赋值为y，插入当前结点后面，退出函数。

    数据插入函数为：

    void insert(LNode *h)

{

       LNode *r,*s;

       int x,y;

       printf("Input the data that you want to insert:\n");

       printf("x=");

       scanf("%d",&x);    /*输入x值*/

       printf("y=");

       scanf("%d",&y);    /*输入y值*/

       r=h;

       r=r->link;

       for(;;r=r->link)

       {

              if(r->data==x)    /*当当前结点指针域不为空且数据域等于x的时候…*/

              {

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

                     s->data=y;

                     s->link=r->link;

                     r->link=s;

                     break;

              }

              if(r->link==NULL)    /*当当前结点指针域为空的时候*/

              {

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

                     s->data=y;

                     s->link=NULL;

                     r->link=s;

                     break;

              }

       }

}

（4）输入k，删除单链表中所有的结点k，并输出被删除结点的个数。

               

        建立三个结构体指针，一个指向当前结点，另一个指向当前结点的上一结点，最后一个备用；建立整形变量l=0；建立循环扫描链表。当当前结点指针域为空的时候，如果当前结点数据域等于k，删除此结点，l++，跳出循环，结束操作；如果当前结点数据域不等于k，跳出循环，结束操作。当当前结点指针域不为空的时候，如果当前结点数据域等于k，删除此结点，l++，继续循环操作；如果当前结点数据域不等于k，指针向后继续扫描。循环结束后函数返回变量l的值，l便是删除的结点的个数。

        数据删除函数为：

        int del(LNode *h)

{

              LNode *r,*s,*t;

              int k,l=0;

              printf("Input the data that you want to delete:");

              scanf("%d",&k);

              r=h;

              s=r;

              r=r->link;

              for(;;)

              {

              if(r->link==NULL)     /*当当前结点指针域为空的时候*/

              {

                     if(r->data==k)     /*如果当前结点数据域不等于k…*/

                     {

                            l++;

                            s->link=NULL;

                            free(r);

                            break;

                     }

                     else break;        /*如果当前结点数据域等于k…*/

              }

              else                  /*当当前结点指针域不为空的时候*/

              {

                     if(r->data==k)      /*如果当前结点数据域不等于k…*/

                     {

                            l++;

                            t=r;

                            s->link=t->link;

                            r=t->link;

                            free(t);

                     }

                     else {r=r->link;s=s->link;}  /*如果当前结点数据域不等于k…*/

              }

              }

              return l;

}

 

堆栈与队列

一．实验目的

1． 会定义顺序栈和链栈的结点类型。

2． 掌握栈的插入和删除结点在操作上的特点。

3． 熟悉对栈的一些基本操作和具体的函数定义。

4． 会定义顺序队列和链队列的结点类型。

二．实验内容

程序1

该程序的功能是实现顺序栈的定义和操作。该程序包括定义的栈结构类型以及对每一种栈操作的具体的函数定义和主函数。

/* 定义DataType为int类型 */

typedef int DataType;

/* 栈的结点类型 */

#define MAXSIZE  1024  

typedef  struct

{DataType  data[MAXSIZE];

int  top;

}SeqStack;

程序2：试利用堆栈将队列中的元素逆置。

程序3：编写括号匹配算法。

1    队列的抽象数据类型定义：

ADT Queue{数据对象：D={|∈ElemSet, i=1,2,...,n, n>=0}

数据关系：R1={<,>|,∈D, i=2,...,n}

基本操作：

InitQueue(&Q)       构造一个空队列Q

QueueEmpty(Q)       判断队列是否为空

QueueLenght(Q)     返回队列Q的元素个数，即队列的长度

GetHead(Q,&e)       取队列Q的队头元素，并用e返回

EnQueue(&Q,e)       将元素e入队列

DeQueue(&Q,&e)     删除非空队列Q的队头元素，并用e返回其值

}ADT Queue

1.  队列的表示：

队列有两种表示方法：链队列、循环队列（顺序队列）。

（1）   链队列的表示：

typedef struct QNode{

QElemType data;

struct QNode *next;

}QNode,*QueuePtr;

typedef struct{

QueuePtr front;

QueuePtr rear;

}LinkQueue;

(2) 循环队列的表示

1.  操作系统作业调度模拟。

编写一个程序，其功能是实现顺序栈的定义和操作。该程序包括定义的栈结构类型以及对每一种栈操作的具体的函数定义和主函数。

利用堆栈将队列中的元素逆置。编写括号匹配算法

假设有几个作业运行。如果都需要请求CPU，则可以让作业按先后顺序排队，每当CPU处是完一个作业后，就可以接受新的作业，这时队列中队头的作业先退出进行处理。后来的作业排在队尾。此题算法跟模拟服务台前的排队现象问题相似，假定只有一个CPU，但为了防止一个作业占用CPU太久，可规定每个作业一次最长占用CPU的时间（称时间片），如果时间片到，作业未完成，则此作业重新进入等待队列，等到下次占有CPU时继续处理。

三．问题描述和分析

1．   实现顺序栈的定义和操作共有如下几个环节：

a)   初始化顺序栈

b)   检查顺序栈是否为空

c)   置为空栈

d)   把元素压入栈，使其成为新的栈顶元素

e)   把栈顶元素弹出

f)   取栈顶元素

g)   输出顺序栈中的元素

2． 利用堆栈队列的元素逆置的流程图如下：

            

            ………………………………………………………………

            ………………………………………………………………

3．  括号匹配问题的转化：在算法中设置一个栈，每读入一个括号，若是右括号，则或者使置于栈顶的最急迫的期待得以消解，或者是不合法的情况，若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性都降了一级。

稀疏矩阵表示、转置和乘法

一．实验目的:

通过查找相关书籍和所学过的知识，将自己的编程能力提高，以及掌握稀疏矩阵的压缩存储及基本操作，了解多维数组的逻辑结构和存储结构。本程序是用三元组表示矩阵，并进行相关的操作，主要用到线性和链式存储法将矩阵表示出来，以及快速转置法和加法的应用。

二．实验要求:

（1）  用顺序和链式存储方式存放用于存储稀疏矩阵的三元组表

（2）  快速转置

（3）  矩阵的乘法

课程设计的实验报告内容:

整个程序通过结构体实现题目要求的的功能（乘法除外），通过用三元组（线性和链式）来表示稀疏矩阵，并能够在屏幕上输出，且还要见其转置（分两种方法）和相加。

LMatrix Add(LMatrix& M1,LMatrix& M2)实现了矩阵的加法，其中包括检验要想家的矩阵是否合格，不合格会报错。SMatrix FastTranspose(SMatrix& M)实现了稀疏矩阵的快速转置，用了两个动态数组查找矩阵中的非零元素，只将这些非零元素转置，是速度大大提高。

三．课程设计的原程序代码:

#include <iostream>

#define MaxTerms 10

#define MaxRows 10

using namespace std;

typedef int ElemType;

struct Triple//三元组

{

       int row,col;//行号和列号

       ElemType val;//元素值

};

struct SMatrix

{

       int m,n,t;//行，列及非零元素个数

       Triple sm[MaxTerms+1];

};

struct TripleNode//三元组结点

{

       int row,col;

       ElemType val;

       TripleNode* next;

};

struct LMatrix

{

       int m,n,t;

       TripleNode* vector[MaxRows+1];

};

void InitMatrix1(SMatrix& M)

{

       M.m=0; M.n=0; M.t=0;

}

void InitMatrix2(LMatrix& M)

{

       int i;

       M.m=0;M.n=0;M.t=0;

       for(i=1;i<=MaxRows;i++)

              M.vector[i]=NULL;

}

void InputMatrix1(SMatrix& M,int m,int n)//row和col用来分别存储元素的行号和列号，val用来存储元素值，t为非零元素个数

{

       M.m=m;M.n=n;

       int row,col,val;

       int k=0;

       cout<<"输入顺序三元组的行号列号以及该位置的元素值，以0 0 0为结束标志"<<endl;

       cin>>row>>col>>val;

       while(row!=0)

       {

              k++;

              M.sm[k].row=row;

              M.sm[k].col=col;

              M.sm[k].val=val;

              cin>>row>>col>>val;

       }

       M.t=k;

}

void InputMatrix2(LMatrix& M,int m,int n)

{

       M.m=m;M.n=n;

       int row,col,val;

       int k=0;

       cout<<"输入链式三元组中的行、列和对应值，以0 0 0为结束标志"<<endl;

       cin>>row>>col>>val;

       while(row!=0)

       {

              k++;

              TripleNode *p;

              TripleNode *newptr;

              newptr=new TripleNode;//建立新结点

              newptr->row=row;

              newptr->col=col;

              newptr->val=val;

              newptr->next=NULL;            

              p=M.vector[row];

              if(p==NULL)

              {                  

                     M.vector[row]=newptr;

              }

           else

              {

                     while(p->next!=NULL)

                            p=p->next;

                     p->next=newptr;

              }/*  */

              cin>>row>>col>>val;

       }

       M.t=k;

}

void OutputMatrix1(SMatrix& M)//输出函数

{

       int i=1;

       cout<<"(";

       for(i=1;i<M.t;i++)

       {

              cout<<"("<<M.sm[i].row<<",";

              cout<<M.sm[i].col<<",";

              cout<<M.sm[i].val<<")"<<",";

       }

       if(M.t!=0)

       {

              cout<<"("<<M.sm[M.t].row<<",";

              cout<<M.sm[M.t].col<<",";

              cout<<M.sm[M.t].val<<")";

       }

       cout<<")"<<endl;

}

void OutputMatrix2(LMatrix& M)

{

       int i;

       TripleNode *p;

      

       for(i=1;i<=M.m;i++)

       {

              for(p=M.vector[i];p!=NULL;p=p->next)

              {

                     cout<<"(";

                     cout<<p->row<<","<<p->col<<","<<p->val;

                     cout<<")"<<",";

              }

       }

       cout<<endl;

}

SMatrix Transpose(SMatrix& M)//普通转置

{

       SMatrix S;

       InitMatrix1(S);

       int m,n,t;

       m=M.m; n=M.n; t=M.t;//用m,n,t分别暂存M的行数、列数和非零元素的个数

       S.m=n; S.n=m; S.t=t;//分别置S的行数域、列数域和非零元素的个数域为n,m和t

       if(t==0)//若是零矩阵则转换完毕返回

              return S;

       int k=1;//用k指示S.sm数组中待存元素的下标

       for(int col=1;col<=n; col++)

              for(int i=1;i<=t;i++)

                     if(M.sm[i].col==col)

                     {

                            S.sm[k].row=col;

                            S.sm[k].col=M.sm[i].row;

                            S.sm[k].val=M.sm[i].val;

                            k++;

                     }

       return S;//返回转置矩阵S

}

SMatrix FastTranspose(SMatrix& M)//快速转置，不必考虑大量的0元素

{

       SMatrix S;

       InitMatrix1(S);

       int m,n,t;

       m=M.m; n=M.n; t=M.t;//用m,n,t分别暂存M的行数、列数和非零元素的个数

       S.m=n; S.n=m; S.t=t;//分别置S的行数域、列数域和非零元素的个数域为n,m和t

       if(t==0)//若是零矩阵则转换完毕返回

              return S;

       int* num=new int[n+1];//为num向量动态分配存储空间

       int* pot=new int[n+1];//为pot向量动态分配存储空间

       int col,i;

       for(col=1;col<=n;col++)//对num向量进行初始化，置每个分量为0

              num[col]=0;

       for(i=1;i<=t;i++)//第1遍扫描数组M.sm,统计出每一列非零元素的个数

       {

              int j=M.sm[i].col;

              num[j]++;

       }

       pot[1]=1;

       for(col=2;col<=n;col++)//计算每一列的第1个非零元素在S.sm中存储位置

              pot[col]=pot[col-1]+num[col-1];

       for(i=1;i<=t;i++)//对M.sm进行第2遍扫描，把每个元素行、列值互换写入到S.sm的确定位置

       {

              int j=M.sm[i].col;

              int k=pot[j];

              S.sm[k].row=j;

              S.sm[k].col=M.sm[i].row;

              S.sm[k].val=M.sm[i].val;

              pot[j]++;

       }

       delete[] num;//删除动态分配的数组

       delete[] pot;

       return S;

}

LMatrix Add(LMatrix& M1,LMatrix& M2)//矩阵加法

{

       LMatrix M;//暂存运算结果，以便返回

       InitMatrix2(M);

       if((M1.n!=M2.n)||(M1.n!=M2.n))

       {

              cout<<"两个矩阵规格不同"<<endl;

              exit(1);

       }

       M.m=M1.m; M.n=M1.n;//把其中一个加数矩阵的尺寸赋给结果矩阵

       if((M1.t==0) && (M2.t==0))

              return M;

       //进行两矩阵相加产生和矩阵

       int k=0;//用k统计结果矩阵中结点的个数

       for(int i=1;i<=M.m;i++)//循环的次数相当于矩阵的行数

       {

              TripleNode *p1,*p2,*p;

              p1=M1.vector[i];//p1指向M1矩阵中第i行单链表的待相加的结点

              p2=M2.vector[i];//p2指向M2矩阵中第i行单链表的待相加的结点

              p=M.vector[i];//p指向M矩阵中第i行单链表的待相加的结点

              while((p1!=NULL) && (p2!=NULL))

              {

                     TripleNode* newptr=new TripleNode;

                     if(p1->col<p2->col)//赋值新结点，p1指针后移

                     {

                            *newptr=*p1;

                            p1=p1->next;

                     }

                     else if(p1->col>p2->col)//赋值新结点，p2指针后移

                     {

                            *newptr=*p2;

                            p2=p2->next;

                     }

                     else//对具有相同列号的结点进行处理

                            if(p1->val+p2->val==0)//不建立新结点和链接

                            {

                                   p1=p1->next;

                                   p2=p2->next;//p1和p2指针后移

                                   continue;

                            }

                            else //新结点值为两结点值之和，p1和p2指针后移

                            {

                                   *newptr=*p1;

                                   newptr->val+=p2->val;

                                   p1=p1->next;

                                   p2=p2->next;

                            }

                     newptr->next=NULL;//将新结点的指针域置空

                     //把新结点链接到结果矩阵的第i行单链表的表尾

                     if(p==NULL)

                            M.vector[i]=newptr;

                     else

                            p->next=newptr;

                     p=newptr;

                     k++;

              }

              while(p1!=NULL)

              {

                     TripleNode* newptr=new TripleNode;

                     *newptr=*p1;

                     newptr->next=NULL;

                     if(p==NULL)

                            M.vector[i]=newptr;

                     else

                            p->next=newptr;

                     p=newptr;

                     p1=p1->next;

                     k++;

              }

              //若p2不为空，则把剩余结点复制链接到结果矩阵中

              while(p2!=NULL)

              {

                     TripleNode* newptr=new TripleNode;

                     *newptr=*p2;

                     newptr->next=NULL;

                     if(p==NULL)

                            M.vector[i]=newptr;

                     else

                            p->next=newptr;

                     p=newptr;

                     p2=p2->next;

                     k++;

              }

       }

       M.t=k;//置和矩阵中结点数

       cout<<"相加后得矩阵"<<endl;

       return M;//返回和矩阵

}

void menu()

{

//     system("cls");

       system("color 61");

       cout<<"                        请进入稀疏矩阵运算之门"<<endl;

       cout<<"                    ***********************************"<<endl;

       cout<<"                    ** 1.用三元组(顺序存储)建立矩阵  **"<<endl;

       cout<<"                    ** 2.矩阵普通转置                **"<<endl;

       cout<<"                    ** 3.矩阵快速转置                **"<<endl;

//     cout<<"                    ** 4.矩阵乘法                    **"<<endl;

       cout<<"                    ** 4.用三元组(链接存储)建立矩阵  **"<<endl;

       cout<<"                    ** 5.矩阵加法                    **"<<endl;

       cout<<"                    ** 6.退出                        **"<<endl;

       cout<<"                    ***********************************"<<endl;

}

int main()

{

       SMatrix S1;//,S2;,*S;

       LMatrix L1,L2;

       LMatrix L;

       int c,m=1;

       while(m==1)

       {

              menu();

              cout<<"请输入你需要的操作"<<endl;

              cin>>c;

                     switch(c)

                     {

                            case 1:

                                          InitMatrix1(S1);

                                          InputMatrix1(S1,10,10);

                                          OutputMatrix1(S1);

                                          break;

                            case 2:

                                   OutputMatrix1(Transpose(S1));

                                   break;

                            case 3: OutputMatrix1(FastTranspose(S1));

                                          break;                                      

                           

                            case 4:

                                   InitMatrix2(L1);

                                   InputMatrix2(L1,10,10);

                                   OutputMatrix2(L1);

                                   break;

                            case 5:

                                   InitMatrix2(L2);

                                   cout<<"输入要相加的矩阵"<<endl;

                                   InputMatrix2(L2,10,10);

                                   OutputMatrix2(L2);

                                   L=Add(L1,L2);

                                   OutputMatrix2(L);

                                   break;

                            case 6:

                                   cout<<"再见"<<endl;

                                   exit(1);

                     }

       }

       return 0;

}

 

题目四：实现平衡二叉排序树的各种算法

（一）分析题目要求

（1）输入形式及输入值范围

输入形式：当树没创建时，先在第一行输入树的节点数目n，第二行再输入n个大于0的不重复整数，以空格隔开。删除结点时，直接输入要删除结点的值。

输入范围：所有int类型的大于零的值，注意不能重复输入。

（2）输出形式

输出形式：各种遍历形式输出均用空格隔开，删除结点时，若成功，打印成功信息，若失败，则打印失败的信息。

（3）程序所能达到的功能

程序里面的函数可以实现平衡二叉树的以下功能：

（1） 插入新结点

（2） 前序、中序、后序遍历二叉树 （递归）

（3） 前序、中序、后序遍历的非递归算法

（4） 层次遍历二叉树

（5） 在二叉树中查找给定关键字

（6） 交换各结点的左右子树

（7） 求二叉树的深度

（8） 叶子结点数

（9） 删除某结点

（二）调试分析

（1）使用的测试数据：

第一组：输入顺序是54321，树的三种遍历是42135，12345，13254.正确。删除结点5后是2143，1234，1342.正确。

第二组：输入顺序是76543218，树的三种遍历是42136578，12345678，13258764.删除结点7后是4213568，1234658，1326854。

第三组：输入顺序是45 12 33 60 10.树的三种遍历是33 12 10 45 60，10 12 33 45 60， 10 12 60 45 33.删除60后是33 12 10 45，10 12 33 45，10 12 45 33.

（2）算法的效率分析和改进设想：删除和插入的算法均是用了二叉排序树的性质来进行，故算法的效率大概为O(lgn)。而遍历的非递归算法均是以栈结构实现。故应该以O(n)的效率进行。由于算法设计的不完善，删除和插入函数的旋转操作都可以进一步提升效率，判断情况也可以尽量减少冗余。这样可以让时间复杂度前面的系数变小，从而提高算法整体效率。

附录—实验截图（代码见CPP文件）

路由算法

路由算法

距离矢量路由算法的具体实现

距离矢量路由算法的原理：距离向量路由算法(Bellman-Ford Routing Algorithm)，作为距离向量协议的一个算法，如RIP, （RIP 跳 最大跳数16）BGP。使用这个算法的路由器必须掌握这个距离表，它告诉在网络中每个节点的最远和最近距离。在距离表中的这个信息是根据临近接点信息的改变而时时更新的。这个在算法中的度量公式是跳跃的次数，等待时间，流出数据包的数量等等。

概括地说，距离向量算法要求每一个路由器把它的整个路由表发送给与它直接连接的其它路由器。路由表中的每一条记录都包括目标逻辑地址、相应的网络接口和该条路由的向量距离。当一个路由器从它的相邻处收到更新信息时，它会将更新信息与本身的路由表相比较。如果该路由器比较出一条新路由或是找到一条比当前路由更好的路由时，它会对路由表进行更新：将从该路由器到邻居之间的向量距离与更新信息中的向量距离相加作为新路由的向量距离。在距离向量路由算法中，相邻路由器之间周期性地相互交换各自的路由表备份。当网络拓扑结构发生变化时，路由器之间也将及时地相互通知有关变更信息。

距离矢量路由算法在理论中可以工作，但在实践中有一个严重的缺陷：虽然它总是能够达到正确的答案，但是它收敛到正确答案的速度非常慢，尤其是，它对于好消息的反应非常快，但是对于坏消息的反应非常迟缓。

程序源代码（c语言）

#include "stdio.h"

#include "stdlib.h"     //atoi的头文件

//#include "alloc.h"

#define ROUTNUM 7       //定义路由的个数为7个

typedef struct

{

       int dis;                   //存延迟大小

       int from;                  //存下一跳的路由

}RoutNode;

RoutNode data[ROUTNUM][ROUTNUM];         /*路由表，能存7行7列数据,数据为权值*/

void InitData(FILE* pfile);                        /*从数据文件读取数据，初始化路由表*/

void OutputRoutData();                             /*输出所有的路由表*/

void Communication(int recv, int send);/*send点向recv点发送自己的路由表*/

void Exchange();                                       /*所有节点进行一次数据交换, 更新路由表*/

void main()

{

       int start, end, i, j;

       FILE *pfile;

       pfile = fopen("1.txt", "r");

       if (pfile == NULL)

       {

              printf("文件打开错误，按任意键退出.\n");

              getch();

              return;

       }

       else

       printf("\n路由表初始:\n");

       InitData(pfile);

       fclose(pfile);

       for (i = 0; i<ROUTNUM; i++)

       {

              printf("%c||", i + 65);

              for (j = 0; j < ROUTNUM; j++)

                     if (data[i][j].dis > 0)

                            printf("<%c %d> ", j + 65, data[i][j].dis);

              printf("\n");

       }                                      //显示各路由的路由表

    for (i = 0; i < ROUTNUM; i++)      //循环7次（好像多余，改成一次得到同样结果）

       {

              Exchange();

       }                                   

       printf("\n路由表交换:\n");

       OutputRoutData();

       printf("输入起始路由节点数字(%d-%d)[0代表A，1代表B...] : ", 0, ROUTNUM - 1);

       scanf("%d",  &start);

       printf("输入终点路由节点数字(%d-%d)[0代表A，1代表B...] : ", 0, ROUTNUM - 1);

       scanf("%d", &end);

       if (start == end || start < 0 || start > 6 || end < 0 || end > 6)

       {

              printf("\n输入错误，请按任意键退出\n");

              getch();

              return;

       }

       else

       {

              int cur = start;

              int total = 0;

              if (data[start][end].dis < 0)

              {

                     printf("没有路由路径发现!\n");

                     getch();

                     return;

              }

              printf("%c->", cur + 65);

              while (data[cur][end].from >= 0)    //起始点与终点不相连。0是A

              {

                     total += data[cur][data[cur][end].from].dis;    //total变成cur与下一跳的延迟

                     printf("%c->", data[cur][end].from + 65);

                     cur = data[cur][end].from;                    //起始路由变成下一跳

              }

              total += data[cur][end].dis;

              printf("%c\n总的路由距离 = %d", end + 65, total);

              getch();

              return;

       }

}

void InitData(FILE *pfile)

{

       char num[10];

       int i = 0;

       char c;

       int m, n;

       fseek(pfile, 0, 0);         //文件指针从距0位置0距离开始读取

       for (m = 0; !feof(pfile) && m < 7; m++)         //feof(pfile),文件尾返回1，不是返回0.即不是文件尾部且m<7循环.

       {

              for (n = 0; !feof(pfile) && n < 7; n++)

              {

                     while (!feof(pfile))

                     {

                            c = fgetc(pfile);              //读取单个字节

                            if (c == ',')                           /*读完一个数字*/

                            {

                                   num[i] = '\0';    //赋值为空

                                   data[m][n].dis = atoi(num);//atoi将字符变成数字，将路由权值给data[][].dis

                                   data[m][n].from = -1;       //直接相连下一跳全都赋值为-1

                                   i = 0;

                                   break;

                            } /*end of if*/

                            else if ((c >= '0' && c <= '9') || c == '-') /*如果读到数字或符号.本题路由权值只能0到9*/

                            {

                                   num[i++] = c;

                            } /*end of else if*/

                     } /*end of while*/

              } /*end of for (n = 0*/

       } /*end of for (m = 0*/

}

void OutputRoutData()

{

       int i, j;

       printf("   ");

       for (i = 0; i < ROUTNUM; i++)

       {

              printf("    %c   ", i + 65);

       }

       printf("\n");

       for (i = 0; i < ROUTNUM; i++)

       {

              printf("%c  ", i + 65);

              for (j = 0; j < ROUTNUM; j++)

              {

                     if (data[i][j].dis < 0)             //如果无路径

                            printf("  -");

                     else

                            if(data[i][j].dis>=10)

                                   printf(" %d", data[i][j].dis);

                            else

                                   printf("  %d", data[i][j].dis);

                     if (data[i][j].from < 0)   //如果未经过其它节点  所以直接相连的路由下一跳为-1

                            printf("  -  ");

                     else

                            printf("  %c  ", data[i][j].from + 65);   //输出下一跳路由

              }

              printf("\n");

       }

}

void Communication(int recv, int send)                  //相连的两路由recv和send交换数据计算一次得到暂时最短距离

{

       int i;

       for (i = 0; i < ROUTNUM; i++)

       {

              if (data[send][i].dis > 0)        //如果send节点到i号节点有路线

              {

                     if (data[recv][i].dis < 0) //如果recv到i号节点无路径   

                     {

                            data[recv][i].dis = data[send][i].dis + data[recv][send].dis; //第一种recv不予i相连，recv到不与他相连的i的延迟

                            data[recv][i].from = send;                                     //下一跳为send

                     }

                     else if (data[recv][i].dis > data[send][i].dis + data[recv][send].dis)//第二种recv与i相连，且直接相连值大于间接到i的延迟

                     //如果现有路径比新路径远

                     {

                            data[recv][i].dis = data[send][i].dis + data[recv][send].dis;     //将recv到i的延迟改为间接延迟的值

                            data[recv][i].from = send;                                          //下一跳改为send

                     }

              }

       }

}

void Exchange()                           //实现所有相连的两路由进行数据交换并计算最短数值

{

       int i, j;

       for (i = 0; i < ROUTNUM; i++)

       {

              for (j = 0; j < ROUTNUM; j++)

              {

                     if (data[i][j].dis > 0)             //如果两个节点之间有路径

                     {

                            Communication(j, i);     //将i号节点的路由表发送给j号节点

                     }

              }

       }

}

/*1.text中存者路由信息

0, 2,-1,-1, 8,-1, 5,

2, 0,4, 5,-1,-1,-1,

-1,4, 0,-1,-1, 9,-1,

-1, 5,-1, 0,1,-1,-1,

8,-1,-1,1, 0,-1, 7,

-1,-1, 9,-1,-1, 0, 3,

5,-1,-1,-1, 7, 3, 0,

数值代表权值（如延迟大小）

0代表目的网络到其本身

-1代表无法直接相连

 */

网络拓扑结构

实验结果

分析与综述

实验结果正确。起始点C下一跳为D到达E。其最短的距离为10.多次验证均正确。本实验的路由表由一个而为数组结构体实现，数组名代表两个相关路由，结构体中存放延时和下一跳。路由表初始信息从文件读取，根据距离向量路由算法系统自动完成路由表的更新操作，最后任意输入两个路由表接点，则可得出两接点之间的最短路径。

所有距离矢量路由协议均使用Bellman-Ford(Ford-Fulkerson)算法，容易产生路由环路和计数到无穷大的问题。因此它们必须结合一些防环机制。

距离矢量路由算法中每一个路由器都存放着整个网络的节点信息，但当一个节点发生变化时，路由不一定能很快的收敛。导致网络效率下降。适用于小型网络。

稀疏矩阵表示、转置和乘法

一．实验目的:

通过查找相关书籍和所学过的知识，将自己的编程能力提高，以及掌握稀疏矩阵的压缩存储及基本操作，了解多维数组的逻辑结构和存储结构。本程序是用三元组表示矩阵，并进行相关的操作，主要用到线性和链式存储法将矩阵表示出来，以及快速转置法和加法的应用。

二．实验要求:

（4）  用顺序和链式存储方式存放用于存储稀疏矩阵的三元组表

（5）  快速转置

（6）  矩阵的乘法

课程设计的实验报告内容:

整个程序通过结构体实现题目要求的的功能（乘法除外），通过用三元组（线性和链式）来表示稀疏矩阵，并能够在屏幕上输出，且还要见其转置（分两种方法）和相加。

LMatrix Add(LMatrix& M1,LMatrix& M2)实现了矩阵的加法，其中包括检验要想家的矩阵是否合格，不合格会报错。SMatrix FastTranspose(SMatrix& M)实现了稀疏矩阵的快速转置，用了两个动态数组查找矩阵中的非零元素，只将这些非零元素转置，是速度大大提高。

三．课程设计的原程序代码:

#include <iostream>

#define MaxTerms 10

#define MaxRows 10

using namespace std;

typedef int ElemType;

struct Triple//三元组

{

       int row,col;//行号和列号

       ElemType val;//元素值

};

struct SMatrix

{

       int m,n,t;//行，列及非零元素个数

       Triple sm[MaxTerms+1];

};

struct TripleNode//三元组结点

{

       int row,col;

       ElemType val;

       TripleNode* next;

};

struct LMatrix

{

       int m,n,t;

       TripleNode* vector[MaxRows+1];

};

void InitMatrix1(SMatrix& M)

{

       M.m=0; M.n=0; M.t=0;

}

void InitMatrix2(LMatrix& M)

{

       int i;

       M.m=0;M.n=0;M.t=0;

       for(i=1;i<=MaxRows;i++)

              M.vector[i]=NULL;

}

void InputMatrix1(SMatrix& M,int m,int n)//row和col用来分别存储元素的行号和列号，val用来存储元素值，t为非零元素个数

{

       M.m=m;M.n=n;

       int row,col,val;

       int k=0;

       cout<<"输入顺序三元组的行号列号以及该位置的元素值，以0 0 0为结束标志"<<endl;

       cin>>row>>col>>val;

       while(row!=0)

       {

              k++;

              M.sm[k].row=row;

              M.sm[k].col=col;

              M.sm[k].val=val;

              cin>>row>>col>>val;

       }

       M.t=k;

}

void InputMatrix2(LMatrix& M,int m,int n)

{

       M.m=m;M.n=n;

       int row,col,val;

       int k=0;

       cout<<"输入链式三元组中的行、列和对应值，以0 0 0为结束标志"<<endl;

       cin>>row>>col>>val;

       while(row!=0)

       {

              k++;

              TripleNode *p;

              TripleNode *newptr;

              newptr=new TripleNode;//建立新结点

              newptr->row=row;

              newptr->col=col;

              newptr->val=val;

              newptr->next=NULL;            

              p=M.vector[row];

              if(p==NULL)

              {                  

                     M.vector[row]=newptr;

              }

           else

              {

                     while(p->next!=NULL)

                            p=p->next;

                     p->next=newptr;

              }/*  */

              cin>>row>>col>>val;

       }

       M.t=k;

}

void OutputMatrix1(SMatrix& M)//输出函数

{

       int i=1;

       cout<<"(";

       for(i=1;i<M.t;i++)

       {

              cout<<"("<<M.sm[i].row<<",";

              cout<<M.sm[i].col<<",";

              cout<<M.sm[i].val<<")"<<",";

       }

       if(M.t!=0)

       {

              cout<<"("<<M.sm[M.t].row<<",";

              cout<<M.sm[M.t].col<<",";

              cout<<M.sm[M.t].val<<")";

       }

       cout<<")"<<endl;

}

void OutputMatrix2(LMatrix& M)

{

       int i;

       TripleNode *p;

      

       for(i=1;i<=M.m;i++)

       {

              for(p=M.vector[i];p!=NULL;p=p->next)

              {

                     cout<<"(";

                     cout<<p->row<<","<<p->col<<","<<p->val;

                     cout<<")"<<",";

              }

       }

       cout<<endl;

}

SMatrix Transpose(SMatrix& M)//普通转置

{

       SMatrix S;

       InitMatrix1(S);

       int m,n,t;

       m=M.m; n=M.n; t=M.t;//用m,n,t分别暂存M的行数、列数和非零元素的个数

       S.m=n; S.n=m; S.t=t;//分别置S的行数域、列数域和非零元素的个数域为n,m和t

       if(t==0)//若是零矩阵则转换完毕返回

              return S;

       int k=1;//用k指示S.sm数组中待存元素的下标

       for(int col=1;col<=n; col++)

              for(int i=1;i<=t;i++)

                     if(M.sm[i].col==col)

                     {

                            S.sm[k].row=col;

                            S.sm[k].col=M.sm[i].row;

                            S.sm[k].val=M.sm[i].val;

                            k++;

                     }

       return S;//返回转置矩阵S

}

SMatrix FastTranspose(SMatrix& M)//快速转置，不必考虑大量的0元素

{

       SMatrix S;

       InitMatrix1(S);

       int m,n,t;

       m=M.m; n=M.n; t=M.t;//用m,n,t分别暂存M的行数、列数和非零元素的个数

       S.m=n; S.n=m; S.t=t;//分别置S的行数域、列数域和非零元素的个数域为n,m和t

       if(t==0)//若是零矩阵则转换完毕返回

              return S;

       int* num=new int[n+1];//为num向量动态分配存储空间

       int* pot=new int[n+1];//为pot向量动态分配存储空间

       int col,i;

       for(col=1;col<=n;col++)//对num向量进行初始化，置每个分量为0

              num[col]=0;

       for(i=1;i<=t;i++)//第1遍扫描数组M.sm,统计出每一列非零元素的个数

       {

              int j=M.sm[i].col;

              num[j]++;

       }

       pot[1]=1;

       for(col=2;col<=n;col++)//计算每一列的第1个非零元素在S.sm中存储位置

              pot[col]=pot[col-1]+num[col-1];

       for(i=1;i<=t;i++)//对M.sm进行第2遍扫描，把每个元素行、列值互换写入到S.sm的确定位置

       {

              int j=M.sm[i].col;

              int k=pot[j];

              S.sm[k].row=j;

              S.sm[k].col=M.sm[i].row;

              S.sm[k].val=M.sm[i].val;

              pot[j]++;

       }

       delete[] num;//删除动态分配的数组

       delete[] pot;

       return S;

}

LMatrix Add(LMatrix& M1,LMatrix& M2)//矩阵加法

{

       LMatrix M;//暂存运算结果，以便返回

       InitMatrix2(M);

       if((M1.n!=M2.n)||(M1.n!=M2.n))

       {

              cout<<"两个矩阵规格不同"<<endl;

              exit(1);

       }

       M.m=M1.m; M.n=M1.n;//把其中一个加数矩阵的尺寸赋给结果矩阵

       if((M1.t==0) && (M2.t==0))

              return M;

       //进行两矩阵相加产生和矩阵

       int k=0;//用k统计结果矩阵中结点的个数

       for(int i=1;i<=M.m;i++)//循环的次数相当于矩阵的行数

       {

              TripleNode *p1,*p2,*p;

              p1=M1.vector[i];//p1指向M1矩阵中第i行单链表的待相加的结点

              p2=M2.vector[i];//p2指向M2矩阵中第i行单链表的待相加的结点

              p=M.vector[i];//p指向M矩阵中第i行单链表的待相加的结点

              while((p1!=NULL) && (p2!=NULL))

              {

                     TripleNode* newptr=new TripleNode;

                     if(p1->col<p2->col)//赋值新结点，p1指针后移

                     {

                            *newptr=*p1;

                            p1=p1->next;

                     }

                     else if(p1->col>p2->col)//赋值新结点，p2指针后移

                     {

                            *newptr=*p2;

                            p2=p2->next;

                     }

                     else//对具有相同列号的结点进行处理

                            if(p1->val+p2->val==0)//不建立新结点和链接

                            {

                                   p1=p1->next;

                                   p2=p2->next;//p1和p2指针后移

                                   continue;

                            }

                            else //新结点值为两结点值之和，p1和p2指针后移

                            {

                                   *newptr=*p1;

                                   newptr->val+=p2->val;

                                   p1=p1->next;

                                   p2=p2->next;

                            }

                     newptr->next=NULL;//将新结点的指针域置空

                     //把新结点链接到结果矩阵的第i行单链表的表尾

                     if(p==NULL)

                            M.vector[i]=newptr;

                     else

                            p->next=newptr;

                     p=newptr;

                     k++;

              }

              while(p1!=NULL)

              {

                     TripleNode* newptr=new TripleNode;

                     *newptr=*p1;

                     newptr->next=NULL;

                     if(p==NULL)

                            M.vector[i]=newptr;

                     else

                            p->next=newptr;

                     p=newptr;

                     p1=p1->next;

                     k++;

              }

              //若p2不为空，则把剩余结点复制链接到结果矩阵中

              while(p2!=NULL)

              {

                     TripleNode* newptr=new TripleNode;

                     *newptr=*p2;

                     newptr->next=NULL;

                     if(p==NULL)

                            M.vector[i]=newptr;

                     else

                            p->next=newptr;

                     p=newptr;

                     p2=p2->next;

                     k++;

              }

       }

       M.t=k;//置和矩阵中结点数

       cout<<"相加后得矩阵"<<endl;

       return M;//返回和矩阵

}

void menu()

{

//     system("cls");

       system("color 61");

       cout<<"                        请进入稀疏矩阵运算之门"<<endl;

       cout<<"                    ***********************************"<<endl;

       cout<<"                    ** 1.用三元组(顺序存储)建立矩阵  **"<<endl;

       cout<<"                    ** 2.矩阵普通转置                **"<<endl;

       cout<<"                    ** 3.矩阵快速转置                **"<<endl;

//     cout<<"                    ** 4.矩阵乘法                    **"<<endl;

       cout<<"                    ** 4.用三元组(链接存储)建立矩阵  **"<<endl;

       cout<<"                    ** 5.矩阵加法                    **"<<endl;

       cout<<"                    ** 6.退出                        **"<<endl;

       cout<<"                    ***********************************"<<endl;

}

int main()

{

       SMatrix S1;//,S2;,*S;

       LMatrix L1,L2;

       LMatrix L;

       int c,m=1;

       while(m==1)

       {

              menu();

              cout<<"请输入你需要的操作"<<endl;

              cin>>c;

                     switch(c)

                     {

                            case 1:

                                          InitMatrix1(S1);

                                          InputMatrix1(S1,10,10);

                                          OutputMatrix1(S1);

                                          break;

                            case 2:

                                   OutputMatrix1(Transpose(S1));

                                   break;

                            case 3: OutputMatrix1(FastTranspose(S1));

                                          break;                                      

                           

                            case 4:

                                   InitMatrix2(L1);

                                   InputMatrix2(L1,10,10);

                                   OutputMatrix2(L1);

                                   break;

                            case 5:

                                   InitMatrix2(L2);

                                   cout<<"输入要相加的矩阵"<<endl;

                                   InputMatrix2(L2,10,10);

                                   OutputMatrix2(L2);

                                   L=Add(L1,L2);

                                   OutputMatrix2(L);

                                   break;

                            case 6:

                                   cout<<"再见"<<endl;

                                   exit(1);

                     }

       }

       return 0;

}

心得体会

通过短暂的两次实习，对本来基础不是很好的我有了很大的提高。不仅让我对c语言进行了一轮复习，更重要的是对数据结构的几章重要内容有了深刻的认识并学会了如何在实践中运用上课学到的理论知识，我们对所学的知识进行了实际上的运用，所谓温故而知新，在复习的同时，加深了对这些知识的理解，学会了对其的运用。同时在实习的过程中锻炼了自己的总体分析解决问题的能力，对c语言的编程能力也得到了一定的提高。总之，我们需要通过实习锻炼出理论与实际相结合来解决问题的能力，在解决问题的过程中一定要细心，例如我在做字符串匹配的题目时，程序写好了，但是一运行每次都不能匹配，我就以为是程序除了问题，自习的找错误，花了很长时间，最后才发现是我输入的有问题。正确出入字符串后成功地匹配了。所以说，做实验时,一定要亲力亲为,务必要将每个步骤,每个细节弄准确。虽然是一个小错误，但往往就是因为个别的细节问题导致我们在某个问题上浪费很多不必要的时间，所以说细心很重要！感谢实习过程中同学和老师的指导，谢谢！数据结构的课程实习结束了，我需要学习的知识还有很多，我会继续努力了解新知识，提高自己解决这方面问题的能力！