实验三 实验报告表

实验名称：字符编码与信息交换 学号： 姓名： 班级： 实验时间：

实验报告表3-1 西文字符显示过程编码记录表

实验报告表3-2 汉字显示过程编码记录表

实验报告表3-3 不同字体的字型码

 

第二篇：北京理工大学数据结构实验报告选作1

《数据结构与算法统计》

实验报告

学院：

班级：

学号：

姓名：

一、实验目的

1.熟悉VC++6.0环境，学习使用C++实现链表的存储结构；

2.通过编程，上机调试，进一步理解线性表、链表的基本概念。

二、实验内容

    归并顺序表（选作）。

请按以下要求编程实现：

①   从键盘输入两个升序排列的整数序列linka和linkb，每个序列以输入0为结束标记。

②   将链表linka和linkb归并为linkc，linkc仍然为升序排列。归并完成后，linka和linkb为空表。输出linkc。

③   对linkc进行处理，保持升序不变，删除其中重复的整数，对重复的整数只保留一个，输出删除重复整数后的链表。

例如：linka输入为：10  20  30  40  50  0

      linkb输入为：15  20  25  30  35  40  45  50  0

      归并后的linkc为：10  15  20  20  25  30  30  35  40  40  45  50  50

      删除重复后的linkc为：10  15  20  25  30  35  40  45  50

三、程序设计

   1、概要设计

说明程序的主要功能，主程序的流程以及各个程序模块之间的调用关系，给出主要流程图。

应用单链线性表寄存数字序列。

⑴单链线性表的抽象数据类型线性表的定义如下：

ADT LinkList {

         数据对象：

                   D = { ai | ai ÎElemSet, i=1,…,n，n≥0 }

         数据关系：

                   R1 = { <ai-1, ai> | ai-1,ai ÎD, i=2, …,n }

         基本操作：

      Creat(LinkList &L)

                      操作结果：构造单链线性表L。

                   MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)

                       初始条件：单链线性表La，Lb，Lc已经存在。

                操作结果：归并La，Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。

Delete(LinkList &L)

初始条件：链表L已经存在。

   操作结果：删除L中的重复元素。

                   Output(LinkList &L)

初始条件：单链线性表L已经存在。

                       操作结果：输出单链线性表L中的各项值。

} ADT LinkList

⑵主程序流程

主程序首先调用Creat(LinkList &L)函数，构造单链线性表La，Lb;再调用MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)函数归并La，Lb，得到新的单链线性表Lc，Lc的元素也按值非递减排列;再释放La，Lb的头结点；再调用Delete(LinkList &L) 删除Lc中的重复元素；最后调用Output(LinkList &L)函数，在屏幕上显示计算结果。

⑶模块调用关系

     由主函数模块调用创建模块、归并模块、删除模块和输出模块。

⑷流程图

   2、详细设计

⑴数据类型设计

typedef struct LNode

{

       int data;

    LNode *next;

}LNode,*LinkList;  //结点类型，指针类型

⑵操作算法设计

void Creat(LinkList &L)// 构造单链线性表L

{

       LinkList p,q;

       int num;

       L=(LinkList)malloc(sizeof(LNode));

       L->next=NULL;

       p=L;//建立头结点

       scanf("%d",&num);

while(num!=0)// 每个序列以输入0为结束标记。

{

                q=(LinkList)malloc(sizeof(LNode));

                q->data=num;

                q->next=p->next;

                p->next=q; //插入到表尾

                p=q;

                scanf("%d",&num);     

       }

}                       

void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)

//归并La，Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。

{

       LinkList pa,pb,pc,p,q;

       pa=La->next;

       pb=Lb->next;

       Lc=(LinkList)malloc(sizeof(LNode));

       Lc->next=NULL;

       pc=Lc; //建立头结点

       while(pa&&pb)

       {

                q=(LinkList)malloc(sizeof(LNode));

                if(pa->data<=pb->data)

//La，Lb中的数据进行比较，插入小的数据

//小数据所在单线性链表指针向后移，另一链表指针位置不变

                {

                         q->data=pa->data;

                         pa=pa->next;

                }

                else

                {

                         q->data=pb->data;

                         pb=pb->next;

                }

                q->next=pc->next;

                pc->next=q;

                pc=q;//插入到表尾

       }

       while(pa)//若La剩余,插入剩余部分

       {

                p=(LinkList)malloc(sizeof(LNode));

                p->data=pa->data;

                p->next=pc->next;

                pc->next=p;

                pa=pa->next;

       }

       while(pb) //若Lb剩余,插入剩余部分

       {

                p=(LinkList)malloc(sizeof(LNode));

                p->data=pb->data;

                p->next=pc->next;

                pc->next=p;

                pb=pb->next;

       }

}

void Delete(LinkList &L)// 删除Lc中的重复元素

{

       LinkList p,q,r;

       p=L->next;

       q=L->next->next;

       r=q;

       while(q!=NULL)

       {

                if(q->data==p->data)//比较数据

                {

                         q=q->next;

                         p->next=r->next;

                         free(r);

                         r=q;

                }

                else

                {

                         p=p->next;

                         q=q->next;

                         r=q;

                }

       }

}

void Output(LinkList &L)// 输出单链线性表L中的各项值

{

       LinkList p;

       p=L->next;

       while(p->next!=NULL)

       {

                printf("%d,",p->data);

                p=p->next;

       }

       printf("%d\n",p->data);

}

⑶主函数设计

void main()

{

       LinkList La,Lb,Lc;

       Creat(La);// 构造单链线性表La

       Creat(Lb);// 构造单链线性表Lb

       MergeList(La,Lb,Lc);// 归并La，Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列

       free(La);//释放La的头结点

       free(Lb);// 释放Lb的头结点

       Delete(Lc);// 删除Lc中的重复元素

       Output(Lc);// 输出单链线性表Lc中的各项值

}

四、程序调试分析

在构造单线性链表La时，直接按照书上的算法进行编写（p->next=L->next; L->next=p）,结果将新构造的结点插入到了表头，不符合题目要求，以后应注意审题，并加强对于基本编码的掌握和理解。

五、程序运行结果

从键盘输入两个升序排列的整数序列linka和linkb，每个序列以输入0为结束标记。输出删除重复整数后的链表Lc，保持升序不变。

测试1：

10 20 30 40 50 0

10 15 20 25 30 35 40 45 50 0

10,15,20,25,30,35,40,45,50

测试2：

1 3 5 7 9 0

2 4 6 8 10 0

1,2,3,4,5,6,7,8,9,10

六、程序清单

#include <iostream>

#include <stdio.h>

typedef struct LNode

{

     int data;

     struct LNode *next;

}LNode,*LinkList;

void Creat(LinkList &L);

void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc);

void Delete(LinkList &L);

void Output(LinkList &L);

void main()

{

       LinkList La,Lb,Lc;

       Creat(La);// 构造单链线性表La

       Creat(Lb);// 构造单链线性表Lb

       MergeList(La,Lb,Lc);// 归并La，Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列

       free(La);//释放La的头结点

       free(Lb);// 释放Lb的头结点

       Delete(Lc);// 删除Lc中的重复元素

       Output(Lc);// 输出单链线性表Lc中的各项值

}

void Creat(LinkList &L)// 构造单链线性表L

{

       LinkList p,q;

       int num;

       L=(LinkList)malloc(sizeof(LNode));

       L->next=NULL;

       p=L;//建立头结点

       scanf("%d",&num);

while(num!=0)// 每个序列以输入0为结束标记。

{

                q=(LinkList)malloc(sizeof(LNode));

                q->data=num;

                q->next=p->next;

                p->next=q; //插入到表尾

                p=q;

                scanf("%d",&num);     

       }

}                       

void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)

//归并La，Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。

{

       LinkList pa,pb,pc,p,q;

       pa=La->next;

       pb=Lb->next;

       Lc=(LinkList)malloc(sizeof(LNode));

       Lc->next=NULL;

       pc=Lc; //建立头结点

       while(pa&&pb)

       {

                q=(LinkList)malloc(sizeof(LNode));

                if(pa->data<=pb->data)

//La，Lb中的数据进行比较，插入小的数据

//小数据所在单线性链表指针向后移，另一链表指针位置不变

                {

                         q->data=pa->data;

                         pa=pa->next;

                }

                else

                {

                         q->data=pb->data;

                         pb=pb->next;

                }

                q->next=pc->next;

                pc->next=q;

                pc=q;//插入到表尾

       }

       while(pa)//若La剩余,插入剩余部分

       {

                p=(LinkList)malloc(sizeof(LNode));

                p->data=pa->data;

                p->next=pc->next;

                pc->next=p;

                pa=pa->next;

       }

       while(pb) //若Lb剩余,插入剩余部分

       {

                p=(LinkList)malloc(sizeof(LNode));

                p->data=pb->data;

                p->next=pc->next;

                pc->next=p;

                pb=pb->next;

       }

}

void Delete(LinkList &L)// 删除Lc中的重复元素

{

       LinkList p,q,r;

       p=L->next;

       q=L->next->next;

       r=q;

       while(q!=NULL)

       {

                if(q->data==p->data)//比较数据

                {

                         q=q->next;

                         p->next=r->next;

                         free(r);

                         r=q;

                }

                else

                {

                         p=p->next;

                         q=q->next;

                         r=q;

                }

       }

}

void Output(LinkList &L)// 输出单链线性表L中的各项值

{

       LinkList p;

       p=L->next;

       while(p->next!=NULL)

       {

                printf("%d,",p->data);

                p=p->next;

       }

       printf("%d\n",p->data);

}