《数据结构》(C语言)实验报告

实验报告

****   ****

学号：*********

成绩：＿＿＿＿＿

实验一，线性表的应用……………………………………3

实验二，栈和队列的应用…………………………………8

实验三，数组的应用………………………………………13

实验四，树和二叉树的应用………………………………19

实验五，图的应用…………………………………………24

实验六，查找表的应用……………………………………32

实验七，排序算法的应用…………………………………44

                                  实验一  线性表的应用

【实验目的】

1.熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；

2.以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；

3.掌握线性表的动态分配顺序存储结构的定义和基本实现；

4.通过对本章实验帮助学生加深对C语言的使用（特别是函数参数调用、指针类型的应用和链表的建立等各种基本操作）。

【实验内容】

约瑟夫问题的实现：n只猴子要选猴王，所有猴子按1,2，…，n编号围坐一圈，从第1只开始按1，2，…，m报数，凡报到m号的猴子退出圈外，如此循环报数，直到圈内省剩下一只猴子时，这个猴子就是猴王。编写一个程序实现上述过程，n和m由键盘输入。

【实验要求】

1.要求用顺序表和链表分别实现约瑟夫问题；

2.完成，严禁抄袭；

3.上交的实验报告由如下部分组成：①实验名称②实验目的③实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。

实验结果：

一，源程序：#include

#include

#define Maxsize 80

struct SeqList

{

 int data[Maxsize];

 int len;

};

typedef struct SeqList SeqList;

void InitList(SeqList *L)

{

 L=(SeqList *)malloc(sizeof(SeqList));

L->len=0;

}

void MadeList(SeqList *L)

{

 int i;

 int people;

 printf("请输入参选的总数:\\n");

 scanf("%d",&people);

for (i=0;i {

L->data[i]=i+1;

printf(" %d ",L->data[i]);

 }  

 printf("\\n");

L->len=people;

}

void WentList(SeqList *L)

{

   int m,i,j;

   int k=0;

   printf("请输入出列数：\\n");

   scanf("%d",&m);

for (i=L->len;i>0;i--)

   {

       k=(k+m-1)%i;

printf(" %d ",L->data[k]);

for (j=k;j    {

L->data[j]=L->data[j+1];

    }

L->len=L->len-1;

   }

   printf("\\n");

}

void main()

{

 SeqList *L;

 InitList(L);

 MadeList(L);

 WentList(L);

}

二，运行结果及截屏视图：

 实验二  栈和列队的应用

【实验目的】

1.熟练掌握栈和列队的结构，以及这两种数据结构的特点；

2.能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空时的判断条件和描述方法；

3.熟练掌握链队列和循环列表的基本运算，特别注意队列满和队列空时的判断条件和描述方法。

【实验内容】

表达式求值的实现：输入一个包含“+“、”-“、”*“、”/“、正整数和圆括号的合法表达式，用算法优先法计算该表达式的结果。

【实验要求】

1.要求用栈实现表达式求值问题；

2.完成，严禁抄袭；

3.上交的实验报告由如下部分组成：①实验名称②实验目的③实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。

实验结果：

一，源程序: #define DATATYPE1 int

#define MAXSIZE 100

typedef struct

{DATATYPE1 data[MAXSIZE];

int top;

}SEQSTACK;

#include

void initstack(SEQSTACK *s)

{s->top=0;}

int push(SEQSTACK *s,DATATYPE1 x)

{

if(s->top==MAXSIZE-1)

    {printf("栈满\\n"); return 0;}

    else

{s->top++;(s->data)[s->top]=x; return 1;}

}

DATATYPE1 pop(SEQSTACK *s)

{

    DATATYPE1 x;

if(s->top==0)

    {printf("栈空\\n"); x=0;}

    else

{x=(s->data)[s->top]; s->top--;}

    return x;

}

DATATYPE1 gettop(SEQSTACK *s)

{

    DATATYPE1 x;

if(s->top==0)

    {

        printf("栈空\\n"); x=0;

    }

    else

        x=(s->data)[s->top];

    return x;}

check(SEQSTACK *s)

    {

        int bool;

        char ch;

        push(s,'#');

        printf("请输入一串括号，回车键结束: ");

        ch=getchar();

        bool=1;

        while(ch!='\\n'&&bool)

        {if(ch=='(')

        push(s,ch);

        if(ch==')')

            if(gettop(s)=='#') bool=0;

            else pop(s);

            ch=getchar();}

        if(gettop(s)!='#')

            bool=0;

        if(bool)

            printf("\\n括号配对正确\\n");

        else

            printf("\\n括号配对错误\\n");

    }

    main()

    {

        SEQSTACK st,*s;

        s=&st;

        initstack(s);

        check(s);

    }

二，实验结果及截屏视图：

实验三  数组的应用

【实验目的】

1.掌握数组的两种存储表示方法；

2.掌握对特殊矩阵进行压缩存储时的下标变换公式；

3.掌握稀疏矩阵的两种压缩存储方法的特点和适用范围。

【实验内容】

稀疏矩阵转置的实现:用三元组顺序表做存储结构，实现稀疏矩阵的转置。

【实验要求】

1.已知某一稀疏矩阵的三元顺序表，由其直接得到其转置矩阵的三元顺序表；

2.完成，严禁抄袭；

3.上交的实验报告由如下部分组成：①实验名称②实验目的③实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。

实验结果：

一，源程序；

#include

#define MAX 80

struct tuple3tp

{

    int i,j,v;

};

struct sparmattp

{

    int m,n,u;

    struct tuple3tp data[MAX];

};

struct sparmattp a,b;

void crt_sparmat()

{

    int i;

    printf("输入稀疏矩阵行值，列值，最大非零元的个数：");

    scanf("%d%d%d",&a.data[i].i,&a.data[i].j,&a.data[i].v);

for(i=1;i<=a.u;i)

    printf("输入行坐标，列坐标，非零元");

    scanf("%d%d%d",&a.data[i].i,&a.data[i].j,&a.data[i].v);

}

void trans_sparmat()

{

    int col,p,q;

    b.m=a.n;

    b.n=a.m;

    b.u=a.u;

    if(b.u!=0)

    {

        q=1;

        for(col=1;col<=a.n;col++)

            for(p=1;p<=a.u;p++)if(a.data[p].j==col)

            {

                b.data[q].i=a.data[p].j;

                b.data[q].j=a.data[p].i;

                b.data[q].v=a.data[p].v;

                q++;

            }

    }

}

out(struct sparmattp x)

{

    int i,j,k,flag;

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

        for(j=1;j<=x.n;j++)

            flag=0;

        for(k=1;k<=x.u;k++)

        {

            if(((x.data[k].i==i)&&((x.data[k].j)==j)))

            {

                flag=1;

                printf("%5d",x.data[k].v);

            }

        }

        if(flag=0)printf("     0");

}

main()

{

    printf("稀疏矩阵的 建立与专置\\n");

    crt_sparmat();

    trans_sparmat();

    printf("\\n");

    out(a);

    printf("\\n");

    out(b);

}

二，实验结果及截屏视图：

实验四 树和二叉树的应用

【实验目的】

1.熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现；

2.重点掌握二叉树的生成、遍历及求深度等算法；

3.掌握哈夫曼树的含义及其应用；

4.掌握运用递归方式描述算法及编写递归C程序的方法，提高算法分析和程序设计能力。

【实验内容】

二叉树采用二叉链表作存储结构，试编写程序实现二叉树的如下基本操作：

1.按先序序列构造一棵二叉树T；

2.对这棵二叉树进行遍历：先序、中序、后序以及层次遍历序列，分别输出结点的遍历序列；

3.求二叉树的深度/结点数目/叶结点数目。

【实验要求】

1.上交实验报告。

2.完成，严禁抄袭。

3.实验报告由如下部分组成：①实验名称②实验目的③实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。

实验结果：

一，源程序

#include

#include

#define bitreptr struct typel

#define NULL 0

#define len sizeof(bitreptr)

bitreptr *bt;

int f,g;

bitreptr

{

    char data;

    bitreptr *lchild,*rchild;

};

preorder(bitreptr *bt)

{

    if(g==1)printf("先序遍历为: \\n");

        g=g+1;

    if(bt)

    {

        printf("%6c",bt->data);

        preorder(bt->lchild);

        preorder(bt->rchild);

    }

    else if(g==2)printf("树空\\n");

}

bitreptr *crt_bt()

{

    bitreptr *bt;

    char ch;

    if(f==1)printf("请输入根节点，以#结束\\n");

    else printf("输入节点，以#结束\\n");

    scanf("\\n%c",&ch);

    f=f+1;

    if(ch=='#')bt=NULL;

    else

    {

        bt=(bitreptr *)malloc(len);

        bt->data=ch;

        printf("%c ",bt->data);

        bt->rchild=crt_bt();

        printf("%c ",bt->data);

        bt->rchild=crt_bt();

    }

    return(bt);

}

main()

{

    f=1;

    g=1;

    bt=crt_bt();

    preorder(bt);

}

二，实验结果及截屏图示：

实验五  图的应用

【实验目的】

1.熟练掌握图的邻接矩阵和邻接表的存储方式；

2.实现图的一些基本运算，特别是深度遍历和广度遍历；

3.掌握以图为基础的一些常用算法，如最小生成树、拓扑排序、最短路径等。

【实验内容】

1.由给定的顶点和边的信息构造图的邻接矩阵存储；

2.对该图进行深度优先搜索，输出搜索得到的结点序列；

3.以邻接表作存储结构，用克鲁斯卡尔算法构造最小生成树。

【实验要求】

1.上交实验报告。

2.完成，严禁抄袭。

3.实验报告由如下部分组成：①实验名称②实验目的③实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。

实验结果：

一，源程序：

图一：

#include

#define INF 9999

#define MAXVEX 100

typedef char vertexType;

typedef float adjtype;

typedef struct{

    vertexType vexs[MAXVEX];

    adjtype arcs[MAXVEX][MAXVEX];

    int n,e;}mGraph;

    void createAdjMatrix(mGraph *G)

    {

        int i,j,k;

        float w;

        scanf("%d%d",&G->n,&G->e);

        for(k=0;kn;k++)

            scanf("%c",&G->vexs[k]);

        for(i=0;in;i++)

            for(j=0;jn;j++)

                G->arcs[i][j]=INF;

            for(k=0;ke;k++)

            {

                scanf("%d%d%f",&i,&j,&w);

            G->arcs[i][j]=w;

            G->arcs[j][i]=w;

            }

    }

    void main()

    { 

        mGraph;

    }

二，实验结果及截屏图示：

图二：

#include

#include

#include

#define MAX_NUM 99

typedef struct{

    int u,v;

    int cost;

}edgeset[MAX_NUM];

void Kruskal(edgeset E,int m,int n)

{

    int x,y,a,b,count,i,p;

    int vset[MAX_NUM];

for(i=0;i<=m;i++) vset[i]=i;

    p=0;

    count=0;

while(count    {

        x=E[p].u;y=E[p].v;

        a=vset[x];b=vset[y];

        if(a!=b)

        {

            printf("边：(%d, %d),  权值： %d\\n",x,y,E[p].cost);

            count++;

            for(i=0;i                if(vset[i]==b)

                    vset[i]=a;

        }p++;

    }

}

void main()

{

    int m=6,n=10;

    edgeset E={{0,1,1},{1,3,2},{3,5,2},{2,4,3},{1,5,4},{1,2,5},{2,5,6},{4,5,7},{0,2,8},{3,4,8}};

    Kruskal(E,m,n);

}

截屏视图：

实验六  查找表的应用

【实验目的】

1.熟悉掌握静态查找表的构造方法和查找算法；

2.熟练掌握二叉排序树的构造和查找方法；

3.熟练掌握哈希表的构造和处理冲突的方法；

4.掌握各种查找表查找效率的分析方法。

【实验内容】

1.要求将二叉排序树的建立、插入、删除、显示等算法合并在一个综合程序中、用户可以通过菜单选择方式运行各种操作算法；

2.一直哈希表的表为m，哈希函数为H(key)=key MOD p,用开放定址法（增量序列采用线性探测再散列）解决冲突，试编写构造哈希表的程序。

【实验要求】

1.上交实验报告。

2.完成，严禁抄袭。

3.实验报告由如下部分组成：①实验名称②实验目的③实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。

实验结果：

一，源程序：#include 

using namespace std;

typedef struct TreeNode 

{ 

    int key;                    

    struct TreeNode *left;      

    struct TreeNode *right;      

}treeNode; 

class BiSortTree 

{ 

    public: 

        BiSortTree(void);            

        void desplayTree(void);      

        void insertTree(int key);  

        void deleteTree(int key);    

        treeNode* searchTree(int key); 

        ~BiSortTree();               

    private: 

        treeNode* buildTree(treeNode* head,int number);                 

        treeNode* search(treeNode* head ,int key);                       

        treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p);  

        treeNode* BiSortTree::searchMinRight(treeNode* head);           

        void showTree(treeNode* head);                                  

        void destroyTree(treeNode* head);                                

        treeNode *Head; 

}; 

BiSortTree::BiSortTree() 

{ 

cout<<"建立一棵二叉排序树,请输入所有节点(以-1 作为结束标志!): "<    Head=NULL; 

    int number; 

cin>>number;

    while(number!=-1) 

    { 

        Head=buildTree(Head,number); 

cin>>number;

    } 

} 

treeNode* BiSortTree::buildTree(treeNode* head,int number) 

{ 

    treeNode *p; 

    p=new treeNode; 

p->key=number;

p->left =p->right=NULL;

    if(head==NULL) 

    { 

      return p; 

    } 

    else 

    { 

if(p->key key)

head->left=buildTree(head->left,number);

        else 

head->right=buildTree(head->right,number);

        return head; 

    } 

} 

void BiSortTree::insertTree(int key) 

{ 

     Head=buildTree(Head,key); 

} 

treeNode* BiSortTree::searchTree(int key) 

{ 

     return search(Head,key); 

} 

treeNode* BiSortTree::search(treeNode* head ,int key) 

{ 

    if(head==NULL) 

        return NULL; 

if(head->key==key)

        return head; 

    else 

    { 

if(keykey )

return search( head->left,key);

        else 

return search(head->right,key);

    } 

}  

void BiSortTree::deleteTree(int key) 

{ 

    treeNode *p; 

    p=NULL; 

    p=search(Head,key); 

    if(p==NULL) 

    { 

cout<<"Don't find the key";

    } 

    if(p==Head) 

    { 

      Head=NULL; 

    } 

    else 

    { 

        treeNode* parent; 

        parent=searchParent(Head,p); 

if(p->left==NULL&&p->right==NULL)

        { 

if(parent->left==p)

            { 

parent->left=NULL;

            } 

            else 

            { 

parent->right=NULL;

            } 

        } 

        else 

        { 

if(p->right==NULL)

            { 

if(parent->left==p)

                { 

parent->left=p->left ;

                } 

                else 

                { 

parent->right=p->left;

                } 

            } 

            else 

            { 

                treeNode * rightMinSon,* secondParent;

rightMinSon=searchMinRight(p->right);

secondParent=searchParent(p->right ,rightMinSon);

secondParent->left=rightMinSon->right;

                if(p->right==rightMinSon)

                { 

p->right=rightMinSon->right ;

                } 

p->key=rightMinSon->key ;

            } 

        } 

    } 

} 

treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p) 

{ 

if(head->left==p||head->right==p||head==p||head==NULL)

        return head; 

    else 

    { 

if(p->keykey)

return searchParent(head->left ,p);

        else 

return searchParent(head->right ,p);

    } 

} 

treeNode* BiSortTree::searchMinRight(treeNode* head)

{ 

if(head->left ==NULL||head==NULL)

    { 

      return head; 

    } 

    else 

    { 

return searchMinRight(head->left);

    } 

} 

void BiSortTree::desplayTree(void) 

{ 

    showTree(Head); 

cout<} 

void BiSortTree::showTree(treeNode* Head) 

{ 

    if(Head!=NULL) 

    { 

showTree(Head->left ) ;

cout<key<<' ' ;

showTree(Head->right) ;

    } 

} 

BiSortTree::~BiSortTree() 

{ 

cout<<"已经消除了一棵树"<    destroyTree(Head); 

} 

void BiSortTree::destroyTree(treeNode* head ) 

{ 

    if(head!=NULL) 

    { 

destroyTree(head->left );

destroyTree(head->right );

        delete head; 

    } 

void print() 

{ 

cout< <<"1.显示树"< <<"2.插入一个节点"< <<"3.寻找一个节点"< <<"4.删除一个节点"<} 

int  main() 

{ 

    BiSortTree tree; 

    int number; 

    int choiceNumber; 

    char flag; 

    while(1) 

    { 

        print() ; 

cout<<"请选择你要进行的操作(1~4)"< cin>>choiceNumber;

        switch(choiceNumber) 

        { 

            case 1: 

                 tree.desplayTree();break; 

            case 2: 

cout<<"请插入一个节点: "< cin>>number;

                tree.insertTree(number); 

                tree.desplayTree(); 

                break; 

            case 3: 

cout<<"请插入你要找的节点: "< cin>>number;

                if(tree.searchTree(number)==NULL) 

                { 

cout<<"没有发现你要找的节点"<                } 

                else 

                { 

cout<<"发现你要找的节点"<                } 

                break; 

            case 4: 

cout<<"请输入你要删除的节点: "< cin>>number;

                tree.deleteTree(number); 

                tree.desplayTree(); 

                break; 

                default: break; 

        } 

cout<<"你是否要继续(Y/N)?"< cin>>flag;

        if(flag=='N'||flag=='n') 

             break;  

    } 

    return 0;

}

二，实验结果截屏视图：

实验七 排序算法的应用

【实验目的】

有如下数据：

1.用冒泡排序对上面数据按成绩非递减排列，并分析时空复杂度；

2.用简单选择排序对上面数据按成绩非递减排列，并分析时空复杂度；

3.用快速排序对上面数据按成绩非递减排列，并分析时空复杂度。

【实验要求】

1.上交实验报告。

2.完成，严禁抄袭。

3.实验报告由如下部分组成：①实验名称②实验目的③实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。

实验结果：

一，源程序：/*#include 

#include

using namespace std;

int main(int argc, char *argv[])

{

    system("PAUSE");

    return EXIT_SUCCESS;

}

#include

#include

#include

typedef struct student

{

   int score;

   char name[10];

   int flag;

}student;

int main()

{

    student stu[10];

    stu[0].score = 75;

    strcpy(stu[0].name, "王华");

    stu[0].flag = 0; 

    stu[1].score = 87;

    strcpy(stu[1].name, "李燕");

    stu[1].flag = 1;

    stu[2].score = 68;

    strcpy(stu[2].name, "张萍");

    stu[2].flag = 2; 

    stu[3].score = 92;

    strcpy(stu[3].name, "陈涛");

    stu[3].flag = 3;

    stu[4].score = 88;

    strcpy(stu[4].name, "刘丽");

    stu[4].flag = 4; 

    stu[5].score = 61;

    strcpy(stu[5].name, "章强");

    stu[5].flag = 5;

    stu[6].score = 77;

    strcpy(stu[6].name, "孙军");

    stu[6].flag = 6; 

    stu[7].score = 96;

    strcpy(stu[7].name, "朱彬");

    stu[7].flag = 7;

    stu[8].score = 80;

    strcpy(stu[8].name, "徐伟");

    stu[8].flag = 8;

    stu[9].score = 72;

    strcpy(stu[9].name, "曾亚");

    stu[9].flag = 9; 

 //冒泡排序   时间复杂度O(n2 )

/*    int tmp = 0; 

    int tmp1=0;  

    int i,j; 

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

    { 

for(j=0; j<9-i; j++)

            {

if (stu[j].score > stu[j+1].score)

                    {

                        tmp1 = stu[j].score;

                        stu[j].score = stu[j+1].score;

                        stu[j+1].score = tmp1;            

                        tmp = stu[j].flag;

                        stu[j].flag = stu[j+1].flag;

                        stu[j+1].flag = tmp;

                    }

             }

     } 

//简单选择排序， 时间复杂度O(n2 )

    int tmp = 0; 

    int tmp1=0;  

    int i,j; 

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

    {       

for(j=i+1; j<=9; j++)

            {

if (stu[j].score < stu[i].score)

                    {

                        tmp1 = stu[j].score;

                        stu[j].score = stu[i].score;

                        stu[i].score = tmp1;            

                        tmp = stu[j].flag;

                        stu[j].flag = stu[i].flag;

                        stu[i].flag = tmp;

                    }

             }

     }  

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

    {

             printf("score=%d, name=%s, flag=%d\\n", stu[i].score, stu[stu[i].flag].name, stu[i].flag);

    }  

    system("PAUSE");

    return 0;

}

二，实验结果截屏视图