找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
查看: 2003|回复: 0
打印 上一主题 下一主题
收起左侧

数据结构上机实验报告下载

[复制链接]
跳转到指定楼层
楼主
ID:313328 发表于 2018-6-5 20:28 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
可以参考的数据结构实验报告,用C语言编写链表
数据结构上机实验报告
----线性表
专    业:计算机科学与技术学院
班    级:            
姓    名            
学    号:           
指导教师:               
日    期:         
一.实验题目
线性表的实现与操作
二.实验目的
(1).掌握顺序表的存储结构形式及其描述和基本运算的实现。
(2).熟练掌握动态链表结构及有关算法的设计。
(3).掌握用链表表示特定形式的数据的方法,并能编写出有关
运算的算法。
*(4).理解单循环链表及双循环链表的特点。
三.实验要求
1.线性表的顺序存储与操作
(1). 输入一组整型元素序列,建立顺序表.
(2). 实现该顺序表的遍历.
(3). 在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0.
(4). 判断该顺序表中元素是否对称,对称返回1,否则返回0.
(5). 实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数.
(6). 输入整型元素序列利用有序表插入算法建立一个有序表.
(7). 利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表.
(8). 编写一个主函数,调试上述算法.

2.线性表的链式存储与操作
(1). 随机产生或键盘输入一组元素,建立一个带头结点的单向链表(无序).
(2). 遍历单向链表.
(3). 把单向链表中元素逆置(不允许申请新的结点空间).
(4). 在单向链表中删除所有的偶数元素结点.
(5). 编写在非递减有序链表中插入一个元素使链表元素仍有序的函数,并利用该函数建立一个非递减有序单向链表.
(6). 利用算法5建立两个非递减有序单向链表,然后合并成一个非递增链表.
(7). 利用算法5建立两个非递减有序单向链表,然后合并成一个非递减链表.
(8). 利用算法1建立的链表,实现将其分解成两个链表,其中一个全部为奇数,另一个全部为偶数(尽量利用已知的存储空间).

(9). 采用单向链表实现一元多项式的存储并实现两个多项式相
加并输出结果
(10) 在主函数中设计一个简单的菜单,分别调试上述算法.

四.实验内容
为线性表的顺序存储与链式存储建两个工程,分别为SqList和LinkList.函数的实现部分采用头文件的形式,在主函数中引用各个头文件,并调用相关函数实现实验的要求.

1. 线性表的顺序存储与操作
下面的头文件是一个类型定义文件.
//Instruction.h
#ifndef INSTRUCTION_H
#define INSTRUCTION_H
#define MAXSIZE 100  //表中元素的最大个数
typedef int  ElemType;//元素类型
typedef struct list{
    ElemType elem[MAXSIZE];//静态线性表
    int length;   //表的实际长度
}SqList;//顺序表的类型名
#endif
(1). 输入一组整型元素序列,建立顺序表.
说明:这个功能用CreatList.h来实现.这个函数已经实现了元素的有序插入.在输入数据时需以一个字符来作为结束符.另外,在源程序中还增加了任意插入和删除操作的函数.这里只列出了创建有序顺序表的部分.
//CreatList.h
#ifndef CREATLIST_H
#define CREATLIST_H
#include"Instruction.h"
#include<stdio.h>
#include<stdlib.h>
void CreatList(SqList *mysqlist){             //创建一个整数顺序链表
              int count=0;
              int temp;
              mysqlist->length=0;
              printf("输入一组整数(以字符结束):\n");
              while(scanf("%d",&temp))
              {
                            if(mysqlist->length==MAXSIZE)
                            {
                                          printf("顺序表已满!\n");
                                          return ;
                            }
                            else                                      //有序插入
                            {
                                          int i;
                                          for(i=0;i<mysqlist->length;i++)
                                          {
                                                        if(temp<mysqlist->elem[ i])
                                                        {
                                                                      int j;
                                                                      for(j=mysqlist->length;j>i;j--)            //后移
                                                                                    mysqlist->elem[j]=mysqlist->elem[j-1];
                                                                      mysqlist->elem[ i]=temp;                     //插入
                                                                      break;
                                                        }
                                          }
                                          if(i==mysqlist->length)mysqlist->elem[ i]=temp; //插入到表尾
                                count++;
                                mysqlist->length++;
                            }
              }
    fflush(stdin);  //清空缓存
}

(2).实现该顺序表的遍历.
//Traversal.h
#ifndef TRAVERSAL_H
#define TRAVERSAL_H
#include"Instruction.h"
#include<stdio.h>
void Traversal(SqList mysqlist){
              int count=0;
              printf("此顺序表中的元素为:\n");
              for(count;count<mysqlist.length;count++)          // 遍历
                 printf("%d ",mysqlist.elem[count]);
              printf("\n");
}
#endif

(3) 在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0
//Search.h
#ifndef SEARCH_H
#define SEARCH_H
#include"Instruction.h"
int Search(SqList mysqlist,int elem)
{
              int count=0;
              for(count;count<mysqlist.length;count++)        //查找
                            if(mysqlist.elem[count]==elem)
                                          return 1;
                            return 0;
}
#endif

(4). 判断该顺序表中元素是否对称,对称返回1,否则返回0.
//IsSimilar.h
#ifndef ISSIMILAR_H
#define ISSIMILAR_H
#include"Instruction.h"
int IsSimilar(SqList mysqlist){
              int i;
              for(i=0;i<mysqlist.length/2;i++)    //对于顺序表,只需到length/2
              {
                            if(mysqlist.elem[ i]!=mysqlist.elem[mysqlist.length-1-i])//判断是否对称
                                          return 0;    //不对称
              }
              return 1;   //对称
}
#endif

(5). 实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数
//ReOrder.h
#ifndef REORDER_H
#define REORDER_H
#include"Instruction.h"
void ReOrder(SqList *mysqlist){
              int temp,count=0,newLocation=0;
              for(count;count<mysqlist->length;count++)
              {
                            if(mysqlist->elem[count]%2!=0)       //元素为奇数
                            {
                                          temp=mysqlist->elem[count];   
                                mysqlist->elem[count]=mysqlist->elem[newLocation]; //将奇数调到前面(对调)
                                          mysqlist->elem[newLocation]=temp;
                                          newLocation++;
                            }
              }
}
#endif

(6). 输入整型元素序列利用有序表插入算法建立一个有序表.
说明:这个功能与第一个功能合并.已在(1)中.此处略

(7).利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表.
//MergeList.h
#ifndef MERGELIST_H
#define MERGELIST_H
#include"Instruction.h"
#include"CreatList.h"
SqList MergeList(SqList *ListA,SqList *ListB){
              int counta=0,countb=0,countc=0;
              SqList C;
              C.length=0;
              while((counta<ListA->length)&&(countb<ListB->length)) //A,B为非空
              {
                            if(ListA->elem[counta]<ListB->elem[countb])
                            {
                                          C.elem[countc]=ListA->elem[counta];counta++;
                                          countc++;C.length++;
                            }
                            else
                            {
                                          C.elem[countc]=ListB->elem[countb];countb++;
                                          countc++;C.length++;
                            }
              }
              while(counta<ListA->length)           //将A的剩余部分插到C后面
              {
                            for(counta;counta<ListA->length;counta++)
                            {
                                          C.elem[countc]=ListA->elem[counta];
                                          countc++;C.length++;
                            }
              }
              while(countb<ListB->length)         //将B的剩余部分插到C后面
              {
                            for(countb;countb<ListB->length;countb++)
                            {
                                          C.elem[countc]=ListB->elem[countb];
                                          countc++;C.length++;
                            }
              }
              return C;
}
#endif

(8). 编写一个主函数,调试上述算法.
说明:在主函数中包含上述所有头文件,Menu头文件给出一个菜单,用户输入选项并执行函数调用,这里不将其列出以免冗余.
//ListTest.c
#include<stdio.h>
#include<stdlib.h>
#include"Instruction.h"
#include"CreatList.h"
#include"Traversal.h"
#include"IsSimilar.h"
#include"Search.h"
#include"ReOrder.h"
#include"MergeList.h"
#include"Menu.h"

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

2. 线性表的链式存储与操作
说明:链式存储与顺序存储大同小异,只不过链式存储用的是指针,而顺序存储用数组.
首先给出下列的类型定义
//LinkList.h
#ifndef LINKLIST_H
#define LINKLIST_H
typedef struct LinkList{
              int element;                  //数据元素
              struct LinkList *next;        //结点指针
}LkList;
#endif
(1). 随机产生或键盘输入一组元素,建立一个带头结点的单向链表(无序).
说明:下面这个函数实现从键盘输入元素,建立的链表是无序的,有头结点.与顺序表的输入一样,需键入一个字符以作为结束符
//CreatLinkList
#ifndef BUILDLINKLIST_H
#define BUILDLINKLIST_H
#include"LinkList.h"
LkList * CreatLinkList(){
              int buffer;
              LkList *Head=(LkList*)malloc(sizeof(LkList));
              LkList *NewElement,*p;
              Head->next=NULL;
              p=Head;
              printf("输入一行整数(以字符结束):\n");
              while(scanf("%d",&buffer))
              {
                            NewElement=(LkList*)malloc(sizeof(LkList)); //为新结点分配空间
                            NewElement->element=buffer;
                            p->next=NewElement;
                            p=p->next;
                            p->next=NULL;
              }
              fflush(stdin);        //清空缓冲输入
              return Head;
}
#endif

(2). 遍历单向链表.
//Traversal.h
#ifndef TRAVERSAL_H
#define TRAVERSAL_H
#include"LinkList.h"
void Traversal(LkList* List){
              LkList *p;
              if(List->next==NULL)
              {
                            printf("这是一个空表!\n");
                            return ;
              }
              printf("遍历链表:");                        //遍历链表
              for(p=List->next;p!=NULL;p=p->next)
                            printf("%d ",p->element);
              printf("\n");
}
#endif
(3). 把单向链表中元素逆置(不允许申请新的结点空间).
说明:这个函数在习题集上有一道.要注意的主要是如何在不申请新的结点空间的情况下逆置.解决的办法是依次将头结点后面的结点插入到头结点之后,作为它的直接后继.这样,第一个插入的是第一个结点,到插入完毕已变成了最后一个结点.而最后插入的结点变成了第一个结点.
//Reserve.h
#ifndef REVERSE_H
#define REVERSE_H
#include"LinkList.h"
void Reverse(LkList *L){
              LkList *p,*q;
              p=L->next;
              L->next=NULL;
              for(p;p!=NULL;)
              {
                            q=p->next;                      //将结点插入到头结点之后
                            p->next=L->next;
                            L->next=p;
                            p=q;
              }
              printf("成功逆置!\n");
}
#endif

(4). 在单向链表中删除所有的偶数元素结点.
//DeleteEven.h
#ifndef DELETEEVEN_H
#define DELETEEVEN_H
#include"LinkList.h"
void DeleteEven(LkList *L){
              LkList *p,*q;
              p=L;
              for(p;p->next!=NULL;)
              {
                            if((p->next->element)%2==0)               //结点元素为偶数
                            {
                                          q=p->next;
                                          p->next=p->next->next;
                                          free(q);                              //释放已删除的结点
                                          continue;
                            }
                            p=p->next;
              }
                            printf("已成功删除偶数结点!\n");
}
#endif

(5). 编写在非递减有序链表中插入一个元素使链表元素仍有序的函数,并利用该函数建立一个非递减有序单向链表.
    说明:与函数(1)的功能相似,增加了有序非递减的要求
//BuildIncreaseLinkList.h
#ifndef BUILDINCREASELINKLIST_H
#define BUILDINCREASELINKLIST_H
#include"LinkList.h"
LkList *BuildIncreaseLinkList(){
              int buffer;
              LkList *Head=(LkList*)malloc(sizeof(LkList));
              LkList *NewElement,*p,*q;
              Head->next=NULL;
              p=Head;
              printf("输入一行整数(以字符结束):\n");
              while(scanf("%d",&buffer))
              {
                            NewElement=(LkList*)malloc(sizeof(LkList));
                            NewElement->element=buffer;
                            for(p=Head;p!=NULL;p=p->next)               //按递增顺序插入
                            {
                                          if(p==Head)continue;
                                          if(p->element>buffer)
                                          {
                                                        for(q=Head;q->next!=p;q=q->next){}           //将新元素插入到P之前
                                                        q->next=NewElement;  
                                                        NewElement->next=p;
                                                        break;
                                          }
                            }//for
                            if(p==NULL)
                            {
                               for(p=Head;p->next!=NULL;p=p->next){}            
                               p->next=NewElement;                                //若是为空表或者要插入的元素在链表中是最大的,
                               p=p->next;                                         //则将其直接插入到表尾
                               p->next=NULL;
                            }
              }//while
              fflush(stdin);                                         //清空缓冲输入
              return Head;
}
#endif
(6). 利用算法5建立两个非递减有序单向链表,然后合并成一个非递增链表.
说明:这个功能与(7)基本一样,因为在(7)的基础上利用(3)功能即可实现.此处略写,而只列出(7)的实现方法.

(7). 利用算法5建立两个非递减有序单向链表,然后合并成一个非递减链表.
说明:为了节省空间,合并之后的头结点即为Lc=La;
//MergeLinkList.h
#ifndef MERGELINKLIST_H
#define MERGELINKLIST_H
#include"LinkList.h"
LkList * MergeLinkList(LkList *La,LkList *Lb){
              LkList *Lc,*pa,*pb,*pc;pa=La->next;
              pb=Lb->next;Lc=pc=La;
              while(pa&&pb)              //La,Lb为非空
              {
                            if(pa->element<pb->element)
                            {
                                          pc->next=pa;pc=pa;
                                          pa=pa->next;
                            }
                            else
                            {
                                          pc->next=pb;pc=pb;
                                          pb=pb->next;
                            }
              }
              while(pa)                  //插入La剩余部分
              {
                            pc->next=pa;pc=pa;
                            pa=pa->next;
              }
              while(pb)                 //插入Lb剩余部分

              {
                            pc->next=pb;pc=pb;
                            pb=pb->next;
              }
              free(Lb);
              printf("合并成功!\n");
              return Lc;
}
#endif

(8). 利用算法1建立的链表,实现将其分解成两个链表,其中一个全部为奇数,另一个全部为偶数(尽量利用已知的存储空间).
说明:这里不用(1)建立的链表,而是用合并后的Lc来完成.分解后奇数部分以Oddpart为头结点.剩余的偶数部分以Lc作为头结点
//Separate.h
#ifndef SEPARATE_H
#define SEPARATE_H
#include"LinkList.h"
void Separate(LkList *OddPart,LkList *Source){
              LkList *p,*q;
              p=Source;
              q=OddPart;
              if(Source->next==NULL)
              {
                            printf("这是一个空表!\n");
                            return ;
              }
              for(p;p->next!=NULL;)
              {
                            if((p->next->element)%2!=0)
                            {
                                          q->next=p->next;
                                          q=q->next;
                                          p->next=p->next->next;
                                          q->next=NULL;
                            }
                            else p=p->next;
              }
}
#endif
(9). 采用单向链表实现一元多项式的存储并实现两个多项式相
加并输出结果
//暂未实现,不写了。
(10) 在主函数中设计一个简单的菜单,分别调试上述算法.
说明:给出了一个菜单,由用户选择操作
//LinkListTest.h
#include<stdio.h>
#include<stdlib.h>
#include"LinkList.h"
#include"Traversal.h"
#include"BuildLinkList.h"
#include"Reverse.h"
#include"DeleteEven.h"
#include"BuildIncreaseLinkList.h"
#include"MergeLinkList.h"
#include"Separate.h"

int main(){
              LkList *lklist,*OddPart;
              LkList *La,*Lb,*Lc;
              int option;
              lklist=(LkList*)malloc(sizeof(LkList));lklist->next=NULL;//初始化lklist
              La=(LkList*)malloc(sizeof(LkList));La->next=NULL; //初始化La
              Lb=(LkList*)malloc(sizeof(LkList));Lb->next=NULL; //初始化Lb
              Lc=(LkList*)malloc(sizeof(LkList));Lc->next=NULL; //初始化Lc
loop:printf("选项:\n1.创建一个链表lklist\n2.遍历链表lklist\n3.逆置链表lklist\n4.删除lklist中偶数结点");
              printf("\n5.建立两个非递减有序链表La,Lb\n6.合并La,Lb\n7.将合并得到的Lc分解成奇偶两部分\n8.多项式相加\n");
              printf("输入选项:");
              scanf("%d",&option);
              switch(option)
              {
              case 1:lklist=CreatLinkList();   //创建一个链表
                                          break;
              case 2:Traversal(lklist);        //遍历链表
                                break;
              case 3:Reverse(lklist);          //逆置链表
                                break;
              case 4:DeleteEven(lklist);       //删除偶数结点
                                break;
              case 5:
                            {
                                          printf("建立有序非递减链表La:");
                                          La=BuildIncreaseLinkList();
                                          Traversal(La);
                                          printf("建立有序非递减链表Lb:");
                                          Lb=BuildIncreaseLinkList();
            Traversal(Lb);
                                          break;
                            }
              case 6:Lc=MergeLinkList(La,Lb);//遍历合并后的非递减链表,若想得到递增链表,逆置即可.
                               Traversal(Lc);
                                break;
              case 7:
                            {
                                          OddPart=(LkList*)malloc(sizeof(LkList));OddPart->next=NULL;//初始化OddPart
                                          Separate(OddPart,Lc);//将Lc分解为奇偶两部分
                                          printf("奇数部分");
                                          Traversal(OddPart);
                                          printf("偶数部分");
                                          Traversal(Lc);
                                          break;
                            }
              case 8:{}break;
              default:printf("输入错误!\n");
              }//switch
              fflush(stdin);
              getchar();
              system("cls");
              goto loop;
              return 0;
              }

五.实验结果(以上所列程序如与源程序有所不同,则以源程序为主)
1.线性表的顺序存储:

输入一组整数(以字符结束):
1 2 3 45 6 7 89 543 5 a
此顺序表中的元素为:
1 2 3 5 6 7 45 89 543
选项:
1.插入元素.
2.删除元素.
3.查找元素.
4.判断顺序表是否对称.
5.重新按奇偶排列.
6.合并两个顺序表.

输入选项:1
输入要加入顺序表的元素和位置:12,0
不合法的位置!
此顺序表中的元素为:
1 2 3 5 6 7 45 89 543

输入选项:1
输入要加入顺序表的元素和位置:234,6
插入成功!
此顺序表中的元素为:
1 2 3 5 6 234 7 45 89 543

输入选项:2
输入要删除结点的位置:3
删除成功!
此顺序表中的元素为:
1 2 5 6 234 7 45 89 543

输入选项:3
请输入要查找的元素:234
找到了这个元素

输入选项:4
不对称

输入选项:5
已重新排列!
此顺序表中的元素为:
1 5 7 45 89 543 6 234 2

输入选项:6
创建有序表A:输入一组整数(以字符结束):
12 3435 67 89 0 a
创建有序表B:输入一组整数(以字符结束):
7 6543 7 853 a
合并完成!此顺序表中的元素为:
0 7 7 12 67 89 853 3435 6543

输入选项:9
输入错误:
Press any key to continue

2.线性表的链式存储:
说明:输入数据后,再一次按ENTER键时会清屏,并再输出选项.所以此处只列出需要的结果.而不重复列出选项.
选项:
1.创建一个链表lklist
2.遍历链表lklist
3.逆置链表lklist
4.删除lklist中偶数结点
5.建立两个非递减有序链表La,Lb
6.合并La,Lb
7.将合并得到的Lc分解成奇偶两部分
8.多项式相加
输入选项:1
输入一行整数(以字符结束):
12 45 67 89 34 a

输入选项:2
遍历链表:12 45 67 89 34

输入选项:3
成功逆置!

输入选项:2
遍历链表:34 89 67 45 12

输入选项:4
已成功删除偶数结点!

输入选项:5
建立有序非递减链表La:输入一行整数(以字符结束):
12 467 8 90 a
遍历链表:8 12 90 467
建立有序非递减链表Lb:输入一行整数(以字符结束):
45 89 5 3 32 a
遍历链表:3 5 32 45 89

输入选项:6
合并成功!
遍历链表:3 5 8 12 32 45 89 90 467

输入选项:7
奇数部分遍历链表:3 5 45 89 467
偶数部分遍历链表:8 12 32 90

六.实验体会
总体来说,这种实验没什么难度,只不过按照功能要求一一实现.虽然如此,在写代码的过程中,也巩固了以前的知识.也在编程的过程中发现了一些问题.比如一些隐蔽的错误很难找出来,因为不太会用DEBUG工具,往往一找错误就是几十分钟.严重降低了效率.
实验中,也有些功能要求实现得不是很好.就拿创建链表来说,输入数据一定要以非数字符结束.但我又始终无法在不必输结束符的情况下完成链表的创建.原因是对键盘缓冲区了解甚少.
实验中还有一个问题:LinkList的第(9)问没有完成。代码写到最后自己都看不明白在写什么,索性全删掉不做了,就这样交了吧。等有空时再去将它解决。
最后,实验报告太长,但是也没有好的办法。如果不贴上源程序,则又太短。


完整的Word格式文档51黑下载地址:
数据结构上机实验报告.doc (84.5 KB, 下载次数: 6)


评分

参与人数 1黑币 +50 收起 理由
admin + 50 共享资料的黑币奖励!

查看全部评分

分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
收藏收藏 分享淘帖 顶 踩
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

手机版|小黑屋|51黑电子论坛 |51黑电子论坛6群 QQ 管理员QQ:125739409;技术交流QQ群281945664

Powered by 单片机教程网

快速回复 返回顶部 返回列表