数据结构实验报告.doc

班级：计算机111 姓名：王瑞飞 学号 11136133 完成日期：2012/4/5实验报告实验1 大整数加法（链表）1.目的与要求：1、 线性表的链式存储结构及其基本运算、实现方法和技术的训练。2、 单链表的简单应用训练3、 熟悉标准模版库STL中的链表相关的知识。2.内容与步骤:1、 编程实现单链表的基本操作2、 利用单链表存储大整数（大整数的位数不限）3、 利用单链表实现两个大整数的相加4、 进行测试。3.抽象数据类型定义：ADT List 数据对象：D= ai | ai ElemSet, i =1, 2, , n, n0 数据关系：R1 = | ai-1 , ai D, i =2, , n 基本操作：InitList (&L ) 操作结果：构造一个空的线性表L 。DestoryList (&L)初始条件：线性表L已存在。操作结果：销毁线性表L。ClearList (&L)初始条件：线性表L已存在。操作结果：将L重置为空表。ListEmpty (L)初始条件：线性表L已存在。操作结果：若L 为空表，则返回TRUE，否则返回 FALSE。ListLength (L)初始条件：线性表L已存在。操作结果：返回L中数据元素个数。GetElem ( L, i, &e )初始条件：线性表L已存在，1iListLength(L)+1。操作结果：用e返回L中第i个数据元素的值。LocateElem ( L,e, compare() )初始条件：线性表L已存在，compare()是判定函数。操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值0。PriorElem ( L, cur_e, &pre_e )初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素且不是第1个，则用pre_e返回它的前驱，否则操作失败。NextElem ( L, cur_e, &next_e )初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素且不是最后一个，则用next_e返回它的后继，否则操作失败。ListInsert ( &L, i, e )初始条件：线性表L已存在，1iListLength(L)+1。操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。ListDelete( &L, i, &e )初始条件：线性表L已存在且非空，1iListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。ListTraverse ( L)初始条件：线性表L已存在。操作结果：遍历链表。 ADT List4.单链表的基本操作：Struct Lnodeint data;Lnode* next;struct LinklistLnode* head; /头指针提前封装。void ListTraverse ();bool InitList ();bool ListEmpty ();int ListLength ();int NextElem (int cur_e, int next_e );int PriorElem (int cur_e, int pre_e );void ListInsert (int i,int e );void ListDelete(int e );int GetElem (int i, int e );bool Linklist: InitList t()head=new Lnode;head-next=NULL；void Linklist:insertafter(int k,int h)/ 这里的插入不局限于ADT中的初始条件：线性表L已存在，1iListLength(L)+1。Lnode*p=head;Lnode*q=head-next;if(k=0)Lnode*t=new Lnode;t-data=h;p-next=t;t-next=q;elsewhile(k-)p=q;q=q-next;if(k=0)Lnode*t=new Lnode;t-data=h;p-next=t;t-next=q;int Linklist:Getelem(int i, int e) /获得第节点个位置的数据（除头结点外）Lnode*p=head;while(p!=NULL&i-)p=p-next;e=p-data;return e;void Linklist: ListDelete(int e ) /删除eLnode*p=head;Lnode*q=head-next;while(q!=NULL&q-data!=e)p=q;q=q-next;if(q=NULL) coutNO FINDnext=q-next;free(q);int Linklist:NextElem(int cur_e, int next_e ) /寻找后继Lnode*q=head-next;while(q!=NULL&q-data!=cur_e)q=q-next;if(q=NULL)return 0;elsee=q-next-data;return e;int Linklist:PriorElem(int e,int Prior_e)/寻找前驱Lnode *p=head;Lnode*q=head-next;while(q!=NULL&q-data!= Prior_e)p=q;q=q-next;if(q=NULL)return 0;elsee=p-data;return e;int Linklist:ListLength()/链表长度(节点数目，除头结点)Lnode *p=head;int count=0;while(p-next!=NULL)count+;return count;int Linklist:Getelem(int i,int e) /取得第i个节点的数据Lnode*p=head;while(p!=NULL&i-)p=p-next;int e=p-data;return e;bool Linklist:ListEmpty()/判空if(head-next=NULL)return true;else return false;void Linklist: ListTraverse ()/遍历链表Lnode*p=head-next;while(p!=NULL)coutdatanext;5、 利用单链表存储大整数（大整数的位数不限）void SaveBigInt()string s;cins;for(int i=0;is.size(),i+)int e=si-0;ListInsert(i,e);6、 利用单链表实现两个大整数的相加非STL方法：#include#includeusing namespace std;struct Lnodeint data;Lnode* next;struct LinklistLnode*head;bool InitList();void ListTraverse ();void ListDelete(int e );void Getelem(int i);int ListLength();void ListInsert (int i,int e );int Linklist:ListLength()/链?表?长?度(节?点?数?y目?，?除y头?结?点?)Lnode *p=head;int count=0;while(p-next!=NULL)count+;p=p-next;return count;void Linklist:Getelem(int i)Lnode*p=head;while(p!=NULL&i-)p=p-next;int e=p-data;coutnext;if(k=0)Lnode*t=new Lnode;t-data=h;p-next=t;t-next=q;elsewhile(k-)p=q;q=q-next;if(k=0)Lnode*t=new Lnode;t-data=h;p-next=t;t-next=q;void Linklist:ListTraverse()Lnode*p=head-next;while(p!=NULL)coutdatanext;bool Linklist:InitList()head=new Lnode;head-next=NULL;return true;void BigIntAdd(Linklist MaxL, Linklist MinL)string c;Lnode *p=MaxL.head-next;Lnode *q=MinL.head-next;while(q!=NULL)p-data+=q-data;if(p-data=10)p-data-=10;if(p-next=NULL)Lnode *f=new Lnode;f-next=p-next;p-next=f;f-data=0;p-next-data+=1;p=p-next;q=q-next;for(int i=MaxL.ListLength();i=1;i-)MaxL.Getelem(i);int main()Linklist L1,L2;L1. InitList();L2. InitList();string s1,s2;cins1s2;int i,j=0,len1=s1.size(),len2=s2.size();for(i=len1-1;i=0;i-) int e=s1i-0;L1.ListInsert(j,e);j+;j=0;for(i=len2-1;i=0;i-) int e=s2i-0;L2.ListInsert(j,e);j+;if(L1.ListLength()=L2.ListLength()BigIntAdd(L1,L2);elseBigIntAdd(L2,L1);coutendl;return 0; STL方法：#include#include#include#includeusing namespace std;listsqlist1;listsqlist2;listsqlist3;list:iterator sqlist1Iterator=sqlist1.begin();list:iterator sqlist2Iterator=sqlist2.begin();list:iterator sqlist3Iterator=sqlist3.begin();void BigIntAdd(string a,string b)int i,e;for(i=0;ia.size();i+)e=ai-0;sqlist1.push_front(e);for(i=0;iab;BigIntAdd(a,b);sqlist3Iterator=sqlist3.begin();for(;sqlist3Iterator!=sqlist3.end();sqlist3Iterator+)cout*sqlist3Iterator; coutendl;return 0;测试结果：通过测试O(_)O实验2 栈序列匹配目的与要求1、 栈的顺序存储结构及其基本运算、实现方法和技术的训练。2、 栈的简单应用训练3、 熟悉标准模版库STL中的栈相关的知识内容与步骤:1、 编程实现顺序栈及其基本操作。2、 对于给出的入栈序列和出栈序列，判断2个序列是否相容。即：能否利用栈将入栈序列转换为出栈序列。3、 进行测试。一、 概要设计1、栈的抽象数据类型定义ADT Stack 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 Init(&S); 初始条件：无操作结果：构造一个空栈 SClear(&S); 初始条件：栈 S 已存在。 操作结果：将 S 清为空栈GetTop(S,&e); 初始条件：栈 S 已存在且非空操作结果：用 e 返回 S 的栈顶元素Push(&S, e); 初始条件：栈 S 已存在。 操作结果：压入元素ePop(&S, &e); 初始条件：栈 S 已存在且非空操作结果：删除S的栈顶元素，并用e返回其值Empty(&S); 初始条件：栈 S 已存在操作结果：若栈 S 为空，返回 TRUE，否则 FALSE ADT Stack2、主程序的处理流程 int main() 栈初始化；读入序列长度n和两个序列命令；if(n=0) break;相容判断；输出结果；return 0;二、详细设计1、顺序栈的实现const int MaxStackSize=100; struct SqStackint *base; int top; / 指向栈顶元素的位置(从0开始)bool Init( );/ 初始化int GetTop();/ 取栈顶元素bool Push(int e);/ 压入元素bool Pop(int &e);/ 弹出元素bool Empty();/ 判栈空;bool SqStack:Init() / 初始化base=new intMaxStackSize;top = -1;int SqStack:GetTop()/ 取栈顶元素basetop;bool SqStack:Push ( int e) / 压入元素 if (top= MaxStackSize-1) return false; /栈?满top +;basetop=e;return true;bool SqStack:Pop (int e) /删除栈顶元素，用e返回其值 top-;return true;bool SqStack:Empty()/ 判空if(top=-1)return true;else return false;2、利用栈进行相容序列的判断bool isMatch(int A, int B, int len) /分别代表入栈和出栈序列，以及序列长度SqStack1.Init();SqStack2.Init();int j=0;int i; for(i=0;ilen;i+)SqStack1.Push(Ai);while(SqStack1.Empty()=false)if(SqStack1.GetTop()=Bj)SqStack1.Pop();j+;elsebreak;if(i=len & SqStack1.Empty()=true)return true;elsereturn false;3、主程序#includeusing namespace std;const int MaxStackSize=100; struct SqStackint *base; int top; / 指向栈顶元素的位置(从0开始)bool Init( );/ 初始化int GetTop();/ 取栈顶元素bool Push(int e);/ 压入元素bool Pop();/ 弹出元素bool Empty();/ 判栈空SqStack1,SqStack2;bool SqStack:Init() / 初始化base=new intMaxStackSize;top = -1;return true;int SqStack:GetTop()/ 取栈顶元素return basetop;bool SqStack:Push ( int e) / 压入元素 if (top= MaxStackSize-1) retur