西电数据结构大作业.doc

题 目： 数据结构上机报告 学 院： 电子工程学院 专 业： 信息对抗技术 学生姓名： 甘 佳 霖 学 号： 14020310092 西安电子科技大学 数据结构 课程实验报告 实验名称 线性表 成 绩 电子工程 学院 1402031 班 成 绩 姓名 甘佳霖 学号 14020310092 同作者 实验日期 2017 年 3 月 18 日 指导教师评语： 指导教师： 年 月 日 实验报告内容基本要求及参考格式 一、实验目的 二、实验所用仪器（或实验环境） 三、实验基本原理及步骤（或方案设计及理论计算） 四、实验数据记录（或仿真及软件设计） 五、实验结果分析及回答问题（或测试环境及测试结果） 实验一 线性表 一、实验目的 熟悉线性表的顺序和链式存储结构 掌握线性表的基本运算 能够利用线性表的基本运算完成线性表应用的运算 二、实验要求 1.设有一个线性表E={e1, e2, … , en-1, en}，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E’={ en, en-1 , … , e2 , e1 }，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。 2.已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空间。 设计思路 1.顺序表做逆置操作时将对应的首尾元素位置交换，单链表的指针end指向链表的末尾，指针start指向链表头结点，指针s用来找到指向end节点的节点，将指向链表末尾和头结点的存储内容交换，然后头结点指针指向下一节点，s指针从start节点开始遍历寻找指向end指针的节点，并将end指针赋值为s指针，就完成了单链表的逆置，可以看出单链表和顺序表都可以完成线性表的逆置。 2.分解单链表的实现思路是首先新建3个循环链表，然后顺序遍历单链表，ASCII码判断链表中的元素属于哪一类元素，然后将这个元素添加到对应的循环链表中，从而实现分解单链表的功能。 运行结果 1.单链表逆置： 顺序表逆置： 分解单链表 实验总结 线性表和单链表是最简单的、最常用的数据结构类型，是实现其他数据结构的基础，熟悉对它们的操作有助于后面对数据结构课程的学习和理解。 附录： 单链表逆置代码如下： //单链表逆置主文件.cpp #include<iostream.h> #include<stdio.h> #include"单链表结构类型定义.h" #include"建立单链表.h" #include"输出单链表.h" #include"单链表逆置.h" void main() { linklist*head; creat(head); print(head); invert(head);//调用单链表逆置的函数 print(head); } //单链表结构类型定义.h typedef char datatype; typedef struct node { datatype data; struct node *next; }linklist; //建立单链表.h void creat(linklist*&head) //采用尾插法建立具有结点的单链表 { char ch; linklist *s,*r; head=new linklist; r=head; while((ch=getchar())!='*') { s=new linklist; s->data=ch; r->next=s; r=s; } r->next=NULL; } //输出单链表.h void print(linklist *head) { linklist*p=head->next; while(p!=NULL) { cout<<p->data<<" "; p=p->next; } cout<<endl; } //单链表逆置.h void invert(linklist*head) { linklist*p,*q,*r; p=head->next; q=p->next;