《数据结构实验一2012年.》由会员分享,可在线阅读,更多相关《数据结构实验一2012年.(16页珍藏版)》请在金锄头文库上搜索。
1、撰写人姓名:周红福 撰写时间:2012年12 月11 日 审查人姓名: 实验过程记录实验名称线 性 表时 间3学时地 点应用数学系机房姓 名周红福班级信科10-2班学号 1007050223组 一、实验目的:1.掌握用VC+或Dev C+上机调试线性表的基本方法。2.掌握线性表的基本操作,插入删除查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。3.熟练掌握栈的链表的实现和数组的实现方法;4.熟练掌握栈和队列的基本操作的算法实现;5.栈和队列的应用。6.可以先用C语言实现,然后再将所有的C语言程序改写为C+类的形式。二、 实验内容: 线性表的顺序存储结构背景知识:顺序表的插入、删除
2、及应用。目的要求: 1掌握顺序存储结构的特点。 2掌握顺序存储结构的常见算法。实验内容 1输入一组整型元素序列,建立顺序表。 2实现该顺序表的遍历。 3在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。 4判断该顺序表中元素是否对称,对称返回1,否则返回0。5实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。6输入整型元素序列利用有序表插入算法建立一个有序表。 7利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。8编写一个主函数,调试上述算法。 * 9综合训练:利用顺序表实现一个班级学生信息管理(数据录入、插入、删除、排序、查找等)实验说明 1.算法1至算
3、法7可以以头文件的方式存储,主函数实现该头文件的包含即可调用 2.存储定义 #define MAXSIZE 100 /表中元素的最大个数 typedef int ElemType;/元素类型 typedef struct list ElemType elemMAXSIZE;/静态线性表 int length; /表的实际长度 SqList;/顺序表的类型名 3.建立顺序表时可利用随机函数自动产生数据。注意问题插入、删除时元素的移动原因、方向及先后顺序。解不同的函数形参与实参的传递关系。#include using namespace std;#define MAXSIZE 100 typede
4、f int DataType; class List public: List(); int SLIsEmpty(); void SLCreat(int n); void SLPrint(); int find(DataType k); int duichen(int n); void swap(int n); void sort(int n); void connet(List &L); private: DataType listMAXSIZE; int length; ; List:List() length=0; int List:SLIsEmpty() if (length=0) r
5、eturn 0; else return 1; void List:SLCreat(int n) DataType x; cout 请?输?入?数y据Y元a素?:o; for (int i=0;ix; listi=x; length+; void List:SLPrint() if (!SLIsEmpty() cout空?表!endl; else for (int i=0;ilength;i+) coutlisti ; cout endl; int List:find(DataType k)int i=0; while (i=length) return 0; else return 1; i
6、nt List:duichen(int n)int i=0;int j=n-1;while(i=j)if(listi=listj)i+;j-; else return 0; return 1; void List:swap(int n)int i=0;int j=n-1;int t;for(i;ii;j-)while(listj%2=1)t=listi;listi=listj;listj=t; void List:sort(int n)int i=0,j;int t;for(i;i=n-1;i+)for(j=i+1;jlistj)t=listi;listi=listj;listj=t; voi
7、d List:connet(List &L) int i=0; int j=0; int n,k; List L1,L2; coutn; L1.SLCreat(n); L1.sort(n);L2.length=L.length+L1.length;if(L2.lengthMAXSIZE)cout合?并顺3序表越?界?!?endl;elsefor(k=0;kL2.length;k+)if(L.listiL1.listj&i=L1.length)L2.listk=L.listi;i+;else if(L.listi=L1.listj&j=L.length)L2.listk=L1.listj;j+;
8、 L2.SLPrint(); int main() List myList,L2; int n; coutn; myList.SLCreat(n); cout你?所输?入?的?顺3序表是?: ; myList.SLPrint(); DataType k; coutk; int m; m=myList.find(k); coutmendl; cout是?否?对?称?:endl; coutmyList.duichen(n)endl; cout将?顺3序表按奇?、偶?先后排?序:oendl; myList.sort(n); myList.swap(n); myList.SLPrint(); cout
9、将?顺3序表非?降排?序:oendl; myList.sort(n); myList.SLPrint(); L2.connet(myList);return 0; 链式存储结构(一)-单向链表的有关操作背景知识:单向链表的插入、删除及应用。目的要求 1掌握单向链表的存储特点及其实现。 2掌握单向链表的插入、删除算法及其应用算法的程序实现。实验内容 1随机产生或键盘输入一组元素,建立一个带头结点的单向链表(无序)。 2遍历单向链表。 3把单向链表中元素逆置(不允许申请新的结点空间)。 4在单向链表中删除所有的偶数元素结点。 5编写在非递减有序链表中插入一个元素使链表元素仍有序的函数,并利用该函数
10、建立一个非递减有序单向链表。 6利用算法5建立两个非递减有序单向链表,然后合并成一个非递增链表。 7利用算法5建立两个非递减有序单向链表,然后合并成一个非递减链表。 8利用算法1建立的链表,实现将其分解成两个链表,其中一个全部为奇数,另一个全部为偶数(尽量利用已知的存储空间)。 * 9采用单向链表实现一元多项式的存储并实现两个多项式相加并输出结果。10在主函数中设计一个简单的菜单,分别调试上述算法。 *11综合训练:利用链表实现一个班级学生信息管理(数据录入、插入、删除、排序、查找等,并能够实现将数据存储到文件中)实验说明 1类型定义 #include typedef int ElemType;/元素类型 typedef struct LNode