2012《数据结构》上机实验报告链表.doc

西华数学与计算机学院上机实践报告课程名称：数据结构年级： 2011上机实践成绩：指导教师：唐剑梅姓名：蒋俊上机实践名称： 学号：312011080611118上机实践日期：2012-11-6上机实践编号：1上机实践时间：8:00-9:30一、实验目的 1. 了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。2. 重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习程序设计方法。3. 掌握栈这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。4. 掌握队列这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。 5. 了解和掌握递归程序设计的基本原理和方法。6. 掌握使用 C+面向对象的程序设计技术设计数据结构源程序的方法。二、实验内容 1. 熟悉前面的【程序示例2】，按照约瑟夫问题的方法2，试着不设头结点改写原来的程序，上机调试运行。 2. 用链表建立通讯录。通讯录内容有：姓名、通讯地址、电话号码。 要求：（1）通讯录按姓名项的字母顺序排列； （2）能查找通讯录中某人的信息； 提示 用链表来存放这个通讯录，一个人的信息作为一个结点。成链的过程可以这样考虑：先把头结点后面的第一个数据元素结点作为链中的首结点，也是末结点。从第二个数据开始逐一作为“工作结点”，需从链表的首结点开始比较，如果“工作结点”的数据元素的姓名字符串比链中的“当前结点”的数据元素的姓名字符串小，就插在其前面。否则，再看后面是否还有结点，若没有结点了就插在其后面成为末结点；若后面还有结点，再与后面的结点逐一比较处理。3. 写一个程序，将输入的十进制数据M 转换为八进制数据M8，将其调试通过。在此基础上修改程序，实现十进制数据M 向N 进制（N为2或8或16）的转换。（注：辅助栈的实现可使用【程序示例3】）三、实验环境 硬件: 微型计算机P4软件: Windows XP+Microsoft Visual C+6.0四、程序源码及调试过程第一题1） 代码#include struct NodeType / 结点的结构定义 int num; / 编号子域 int psw; /密码域 char name20; / 姓名子域 NodeType *next; / 指针域 ;class Jose /类声明 private: NodeType *Head; public:Jose( ); Jose() ; void creat(); void outs(); ;void Jose:creat() int i=0, n; NodeType *newp, *pre; coutn; pre=new NodeType; Head=new NodeType; pre-num=1; coutn 编号1pre-name; coutn 密码1pre-psw; Head=pre; Head-next=Head; for(i=1;inum=i+1; coutn 编号i+1newp-name; coutn 密码i+1newp-psw; newp-next=Head; pre-next=newp; pre=newp; void Jose:outs( ) int m,i; NodeType *q=Head, *p; cout=2); cinm; coutn 根据m值，开始报数输出：next!=q) for(i=1;inext; cout编号为：num 的人的姓名：nameendl; coutn 编号为:num的人的密码：pswpsw; p-next=q-next; delete q; q=p-next; cout编号为：num的人的姓名：nameendl; coutn 编号为:num的人的密码：pswendl; delete q; int main() Jose h; h.creat(); h.outs(); return 0;第二题2）#include #include struct ElemType / 数据元素的类型 char Add20; char name20; char tel20; ;struct NodeType ElemType data; NodeType *next;class Sqlist private: NodeType *Head; public: Sqlist(); Sqlist(); void creat(); void Insert(ElemType x); void Delet(ElemType x); void PrintOut(); ;Sqlist:Sqlist() Head=new NodeType;Head-next=NULL;strcpy(H,姓名);strcpy(Head-data.Add,地址);strcpy(Head-data.tel,电话号码); Sqlist:Sqlist() NodeType *p=Head-next; while(p!=NULL) Head-next=p-next; delete p; p=Head-next;void Sqlist:creat( ) /初步建立一个通讯录 NodeType*p,*s,*q;ElemType x;int a;q=Head;;coutx.Add;coutx.tel;p=new NodeType;p-data=x;Head-next=p;p-next=NULL;cout输入一个数。若为-1，结束输入:a;while(a!=-1);coutx.Add;coutx.tel;s=new NodeType;s-data=x;if(strcmp(,)0)p-next=s;s-next=NULL;p=s;elses-next=p;q-next=s;q=q-next;cout输入一个数。若为-1，结束输入:a;void Sqlist:Insert(ElemType x)/插入 NodeType *p,*q,*s;s=new NodeType;s-data=x;q=Head;p=q-next;while(p!=NULL&strcmp(,)next;s-next=p;q-next=s;void Sqlist:Delet(ElemType x)/删除NodeType *p,*q;q=Head;p=Head-next;while(p!=NULL&strcmp(,)!=0)q=p;p=p-next;if(p!=NULL)q-next=p-next;delete p;cout删除结点成功endl;elsecout未找到要删除的信息next;while(p!=NULL) ;coutdata.tel ;coutdata.Addnext;coutendl; int main( ) int k; ElemType e; Sqlist as; coutn 通讯录演示; do coutnn; coutnn 1. 初步建立一个通讯录（单链表） ; coutnn 2. 插入新的电话记录 ; coutnn 3. 删除一个电话记录; coutnn 4. 结束程序; coutn* ; coutk;switch(k) case 1: as.creat(); as.PrintOut(); break; case 2: ; coute.tel; coute.Add; as.Insert(e); as.PrintOut(); break; case 3: ; as.Delet(e); as.PrintOut(); break; default:break; while(k=1&k4); coutn 再见!; return 0;第三题2） 代码#include#include typedef int ElemType; / 数据元素的类型const int MAXSIZE=100; / 数组的容量class SqStack private: ElemType elemMAXSIZE; int top; public: SqStack(); SqStack(); void SqStack:push( ElemType e); ElemType SqStack:pop(); void SqStack:PrintOut(); int SqStack:IsEmpty(); void f(ElemType N,ElemType M);void SqStack:f(ElemType N,ElemType M) SqStack s; ElemType e;while(N)s.push(N%M);N=N/M;while(!s.IsEmpty()e=s.pop();if(e=10)e=e%10;switch(e) case 1:coutbendl;break; case 2:coutcendl;break; case 3:coutdendl;break; case 4:couteendl;break; case 5:coutfendl;break; default:coutaendl;break;else coute;coutendl;SqStack:SqStack()top=0; void SqStack:push( ElemType e) if(top=MAXSIZE-1) cout栈满溢出endl; return; elsetop+; elemtop=e; ElemType SqStack:pop() ElemType x; if(top=0) cout 栈为空，不能出栈操作endl; return -1; else x=elemtop; top-; return x;void SqStack:PrintOut() int k; cout=1;k-) coutsetw(6)elemk; coutendl; int SqStack:IsEmpty() if(top=0)