第一篇：南航计算机软件数据结构上机实践报告
数据结构实践报告整理 031040102 刘玉 简述每一部分的对象、目的和要求；
画出程序流程图；另附A4纸手绘； 附源程序清单； 实验的收获：遇到的问题以及解决的办法、方法的优缺点。
实验一 单链表的基本操作与运算
题目一：单链表的定义、创建、插入和删除操作，将数据元素显示出来。
本题目针对单链表。联表示通过一组任意的存储单元来存储线性表格中的数据元素。为了建立起数据元素之间的存储关系，设置每一个结点，结点既存放数据data，又存放其后继地址的部分next。而每个结点中只有一个指向后继的指针，所以称其为单链表。本题目的要求是创建一个新的链表，并且完成链表的创建定义。链表是一种动态管理的存储结构，链表中的每一个结点所占用的空间是根据运行是的实际需要的空间生成的。因此建立单链表是从空链表开始的，每次读入一个数据元素就申请一个结点链表的一段。在单链表中插入一个结点不需要移动元素指针的指向。而删除则需要找到木比啊偶元素的前驱结点，并且修改指针的指向。题目一需要的操作就是，对于一个新建的空链表，以其为对象进行具体的数据的插入填写。待链表中存有数据后，再进行数据的整理查找，然后删除目标数据。
//031040102单链表 #include
//定义一个链表 { int data;SLNODE *next;};void CREATE_SL(SLNODE *h)//创建一个单链表 { SLNODE *p,*s;int x;h->next=NULL;
cout<<“输入以-1结尾的一组数”< cin>>x; //开始输入数据 while(x!=-1) { s=new SLNODE[sizeof(SLNODE)]; //申请一个动态新空间 s->data=x; if(h->next==NULL) h->next=s; else p->next=s; p=s; cin>>x; } p->next=NULL; //链表最后指向空 };int Insert_LinkList(SLNODE *h,int i,int x) //在单链表第i个位置插入x { SLNODE *p,*s;int j=0; p=h;while(p->next!=NULL&&j { p=p->next; j++; } if(j!=i-1){ cout<<“i is invalid!”< return 0;} else { s=new SLNODE[sizeof(SLNODE)]; s->data=x; s->next=p->next; p->next=s; return 1; } };int Del_LinkList(SLNODE *h,int i) //删除单链表上第i个结点 { SLNODE *p,*s;int j=0;p=h;while(p->next!=NULL&&j p=p->next;j++; } if(j!=i-1){ cout<<“i is invalid!”< return 0;4 6 8 9 7 2 6 9 7 5-1 } 链表数据如下 else 4 6 8 9 7 2 6 9 7 5 { 输入需插入的数据8 if(p->next==NULL)输入需插入的结点3 { 插入成功 cout<<“第i个结点不存在链表数据如下 ”< return 0;输入需删除的结点 4 } 删除成功 else 链表数据如下 {s=p->next;p->next=s->next; 7 2 6 9 7 */ //删除结点 Deletes; //释放结点空间 return 1; } } };void Print_LinkList(SLNODE *h)//输出链表中所有元素 { SLNODE *p;p=h->next;cout<<“链表数据如下”< cout< data<<'t';} cout< data< cout<<“插入成功”< cout<<“插入失败”< cout<<“删除成功”< cout<<“删除失败”< 实验一的收获 实验一让我对于链表的创建于定义有了更多的接触与认识。之前的学习经验里主要是 扎实，VC++，涉及链表的内容，我学的不够所以这次在软件基础时间里重新再次 学习。题目一比较简单，设仅是创建和插入以及删除的基本操作。实验一的困难较小，我也是比较顺利参照课本，完成体题目一，也让我对于进一步学习链表有了兴趣和动力。由浅入深，我会一点点开展学习。在图书馆借阅一本《数据结构教程上机实验指 导》，里面对于实验的指导比较全面而且有很多实例可以参考。 上机实践二 题目二：栈、队列的顺序存储结构、链式存储结构的定义、创建、插入和删除操作，将数据元素显示出来。本题目要求掌握栈和列队。栈和列队是 两种常见的数据结构。它们的逻辑结构和线性表相同。其特点是，插入和删除等运算的位置有所限制：栈是按照先进后出的规则进行操作，而是按照先进先出的规则进行操作。堆栈技术现在的应用非常广泛，不管是编译软件还是程序设计，在操作系统和事务管理中则是广泛应用了队列技术。栈是限制在一段进行插入和删除的线性表，允许插入删除的这一端称为栈顶，固定端称为栈底。栈是运算受到限制的一种线 性表，采用顺序存储的是顺序栈，采用链式存储的是链栈。题目要求对于两种存储结构 的栈进行定义创建。对于顺序栈，首先需要申请共享的一位数组空间。即为先置空栈，然后入栈插入元素（特别要注意栈满不能插入），删除出栈（特别要注意栈空不能出栈）。对于链栈，采用带头指针的单链表来实现.队列操作的顺序队列，插入在表的队尾一端，删除在表的另外的队头一端。队的队头和队尾都是活动的，特别地需要设置队头和队尾两个指针。需要实现置空队、入队、出对、以及判别队列是否为空的运算。对于链式队列，通常是用带头结点的单链表实现的，并且设置一个队头指针（始终指向头结点）和一个队尾指针（指向当前的最后一个元素），特别地，当队列为空时队头和队尾指针均指向头结点。显示创建一个带头结点的空队，申请头尾结点，然后进行如对操作不断申请新的结点，还需要进行队列是否为空的判断操作，队空则出队失败。 //031040102 顺序栈 #include return 1;else return 0;};int Push_SeqStack(SqStack *s,ElemType x)//入栈 { if(s->top==MaxSize-1) return 0;else { s->top++; s->data[s->top]=x; return 1; } };int Pop_SeqStack(SqStack *s,ElemType x) //出栈 { if(IsEmpty_SeqStack(s)) return 0;else { x=s->data[s->top]; s->top--; return 1; } }; ElemType Top_SeqStack(SqStack *s) //取出栈顶元素 { if(IsEmpty_SeqStack(s)) return 0; else return(s->data[s->top]); };void Print(SqStack *s) //输出栈内所有元素 { if(IsEmpty_SeqStack(s)) cout<<“ 此栈为空 ”< cout<<“栈内元素为”< for(int i=s->top;i>-1;i--) cout< } };void main(){ SqStack *s;int x; s=Init_SeqStack();cout<<“ 输入一组以-1结尾的数”< s->top++; s->data[s->top]=x; cin>>x;} Print(s);cout<<“输入需插入的数”< cout<<“插入成功”< cout<<“插入失败”< Print(s); delete p;if(Pop_SeqStack(s,x)) return top; cout<<“删除成功”< cout<<“删除失败”< Print(s);} 输入一组以-1结尾的数 5 8 9 7 3 6 2 1 8-1 栈内元素为 8 1 2 6 3 7 9 8 5 输入需插入的数4 插入成功 栈内元素为 4 8 1 2 6 3 7 9 8 5 删除成功 栈内元素为 8 1 2 6 3 7 9 8 5 //031040102 链栈 #include //定义一个链栈 { elemtype data;LinkStack *next;};LinkStack *Init_LinkStack()//链栈的初始化 { LinkStack *top;top=new LinkStack[sizeof(LinkStack)];top=NULL;return top;};LinkStack *Push_LinkStack(LinkStack *top,elemtype x) //数据入栈 { LinkStack *s;s=new LinkStack[sizeof(LinkStack)];s->data=x;s->next=top;top=s;return top;};LinkStack *Pop_LinkStack(LinkStack *top,elemtype x) //数据出栈 { LinkStack *p;if(top==NULL) return NULL;else { x=top->data; p=top; top=top->next;//输出栈内所有元素 { LinkStack *p;p=top;if(p==NULL) cout<<“此栈为空”< cout<<“栈内元素为”< for(;p->next!=NULL;p=p->next) cout< data<<'t'; cout< data< s=new LinkStack[sizeof(LinkStack)]; s->data=x; s->next=top; top=s; cin>>x;} Print(top);cout<<“输入需插入的数”< 输入需插入的数15 栈内元素为 15 65 23 1 6 3 4 8 9 7 栈内元素为 65 23 1 6 3 4 8 9 7 //031040102 顺序队列 #include typedef struct queue //定义一个顺序队列 { ElemType data[MaxSize];int rear,front;}SeQueue;SeQueue*Init_Queue()//队列的初始化 { SeQueue *sq;sq=new SeQueue[sizeof(SeQueue)];sq->front=sq->rear=-1;return sq;};int IsEmpty_Queue(SeQueue *sq)//判空队列 { if(sq->rear==-1) return 1;else return 0;};int In_Queue(SeQueue *sq,ElemType x) //入队 { if(sq->rear==MaxSize-1) return 0;else { sq->rear++; sq->data[sq->rear]=x; return 1;} };int Out_Queue(SeQueue*sq) //出队 { if(IsEmpty_Queue(sq)) return 0;else { sq->front++; return(sq->data[sq->front]);} };int Front_Queue(SeQueue *sq)//读队头元素 { if(IsEmpty_Queue(sq)) return 0;else { return(sq->data[sq->front+1]);} };void Print(SeQueue *sq)//输出队列所有元素 { if(IsEmpty_Queue(sq)) cout<<“此队列为空”< cout<<“队列内元素为”< for(int i=sq->front+1;i<=sq->rear;i++) cout< cout< cin>>x;while(x!=-1){ sq->rear++; sq->data[sq->rear]=x; cin>>x;} Print(sq);cout<<“输入需插入的数”< cout<<“插入成功”< cout<<“插入失败”< cout<<“删除成功”< cout<<“删除失败”< //定义链队的结点类型 { ElemType data;QNODE *next;}; typedef struct linkqueue p=q->front->next; //封装头尾指针 if(IsEmpty_LQueue(q)){ cout<<“此栈为空”< cout<<“ 队列内元素为 ”< { for(;p->next!=q->rear->next;p=p->next)LinkQueue *q; cout< data<<'t';QNODE *p; cout< data< } //申请头尾节点 p=new QNODE[sizeof(QNODE)];//申请链队头结点 p->next=NULL;q->front=q->rear=p;return q;};void In_LQueue(LinkQueue *q,ElemType x)//入队操作 { QNODE *p;p=new QNODE[sizeof(QNODE)];//申请新结点 p->data=x;p->next=NULL;q->rear->next=p;q->rear=p;};int IsEmpty_LQueue(LinkQueue *q)//判队空 { if(q->front==q->rear) return 1;else return 0;};int Out_LQueue(LinkQueue *q,ElemType x)//出队操作 { QNODE *p;if(IsEmpty_LQueue(q)) return 0;else { p=q->front->next; q->front->next=p->next; x=p->data; delete p; if(q->front->next==NULL) //一个元素时，出队后队空还要改队尾指针 q->rear=q->front; return 1;} };void Print(LinkQueue *q){ QNODE *p;}; void main(){ LinkQueue *q;QNODE *s;int x; q=Init_LQueue();cout<<“输入一组以-1结尾的数”< { s=new QNODE[sizeof(QNODE)]; s->data=x; s->next=NULL; q->rear->next=s; q->rear=s; cin>>x; } Print(q);cout<<“输入需插入的数”< cout<<“删除成功”< else cout<<“删除失败”< 队列内元素为 8 9 4 5 3 2 1 实验二的收获 实验二是全新的知识需要理解。在之前的学习经历中没有接触到栈和队列。所以这 次是从概念开始学习的。在具体程序的学习应用时候，我对于书上提到的，首先需要的是为栈申请共享空间，有了理解和认识。特别地，在栈空的时候有s->top[0]==-1;s->top[1]==Maxsize。再有就是栈满的时候不可以入栈操作，未满的入栈操作则是先移动再赋入值。例如语句(两句的顺序不可以颠倒)s->top++;s->data[s->top]=x;由于栈的主要运算是在栈顶插入、删除。因此我在链表的头部作为栈顶，这样方便了程序，而且不需要像单链表一样为了运算方便附加一个头结点。在联系队列的相关程序时候，我理解了，列队单向空间无法利用，即为前面的已经被指针制动过的空间不能释放也无法利用。除此，队列的操作里面。有可能出现“队满”“队空”的条件相同，front==rear;需要具体区分。 上机实践三 题目三：二叉树的链式存储结构的数据结构定义、创建、先序和后序遍历，并将结果序列输出。 二叉树是有限个元素的集合，该集合或者为空、或者由一个称为根的元素以及两个不相交的、被称为左子树右子树的二叉树组成。二叉树的脸是存储结构是指，用链表来表示一颗二叉树，即用链表来表示元素的逻辑关系。二叉树的链表存储的结点有三个域组成，除了数据域外，还有两个指针域，分别用来指向该节点的左子结点和右子结点的存储地址。当左子结点或者右子结点不存在的时候，相应的指针值域为空。二叉树的遍历是指按照某种顺序结构访问二叉树的每个结点，使每个结点仅被访问一次。限定先左后右，只有三种方式即为先序遍历、中序遍历、后序遍历。遍历其实是一个递归的过程，若二叉树为空，则遍历结束，不然就按照顺序依次访问根结点、左结点、右结点。 //031040102 二叉树 #include //定义二叉树结点 { elemtype data; BiTNode *lchild,*rchild;//两结点指针 }BiTree; BiTree *Create()//二叉树的创建,递归算法 { BiTree *bt;elemtype ch;cin>>ch;if(ch=='0'){ bt=NULL;} else { bt=new BiTNode[sizeof(BiTNode)]; bt->data=ch; bt->lchild=Create(); bt->rchild=Create();} return bt;}; void PreOrder(BiTree *bt) //先序遍历二叉树，递归算法 { if(bt==NULL) return;cout< void PostOrder(BiTree *bt) //先序遍历二叉树，递归算法 { if(bt==NULL) return;PostOrder(bt->lchild);PostOrder(bt->rchild);cout< void main(){ BiTree *bt;cout<<“输入所需字符（空结点以零代替）”< 输入所需字符（空结点以零代替）frt0e000qj00m00 先序遍历可得二叉树元素为 f r t e q j m 后序遍历可得二叉树元素为 e t r j m q f 实验三的收获 二叉树可以用计算机语言来读取，通过遍历可以恢复二叉树。通过这次试验更加深刻理解二叉树。本体操作不断调用函数，递归实现遍历。实际需要的时候对于已知的二叉树的每个结点逐一访问。一次完整的便利科室的一个二叉树的结点信息由非线性排列转变为意义上的线性排列。在二叉树的链表中无法根据结点找到其父结点。不过，二叉树的链表结构灵巧简便、操作方便。特别地还节省空间。对于一个庞大的工程型程序的话，空间与简便十分重要。同样的目的，同样的结果，需要比较选择，肯定是精巧简单操作性强等等优势作为判断取舍。 上机实践四 题目四：查找：顺序查找、二分查找 查找是许多程序中最为耗费时间的部分。因此需要方法提高运行的速度和效率。顺序查找又称为线性查找，也是最为基本的查找方法之一。具体实现为：从表的一端开始，依次将关键码与给定的值比较，若找到查找成功，并且给出数据元素在表中的位置，若整个表查找完成仍未找到相同的关键码，则查找失败给出失败信息。 二分法查找只适用于顺序存储的有序表。有序表即是表中数据元素按照关键码的升序或者降序排列。去中间元素作为比较对象，若给定值与中间元素的关键码相等，则为查找成功；若给定值小于中间元素的关键码，则在中间元素的左半区继续查找，若给定值大于中间元素的关键码，则在中间元素的右半区继续查找。不断重复上述的查找过程直到查找成功，或者所查找的区域，没有该元素查找失败。 //031040102顺序查找 #include #define MaxSize 1024 typedef struct { KeyType key; //定义关键码字段 ElemType elem;//定义其他字段 }elemtype; typedef struct //顺序存储结构定义 { elemtype elem[MaxSize];//定义数组 int length; //表长度 }S_TBL; S_TBL *Init_S_TBL() //顺序表的初始化 { S_TBL *s;s=new S_TBL[sizeof(S_TBL)];s->length=-1;return s;}; int s_search(S_TBL *tbl,KeyType kx)//在表tbl中查找关键码为kx的数据元素 { tbl->elem[0].key=kx; //存放检测 for(int i=tbl->length;tbl->elem[i].key!=kx;i--); //从表尾向前查找 return i;}; void main(){ S_TBL *tbl;tbl=Init_S_TBL();int i,k;cout<<“输入一组以-1结尾的数(关键码字段)”< tbl->length++; i=tbl->length+1; tbl->elem[i].key=k; cin>>k;} i=1;cout<<“输入一组以-1结尾的数(数据元素)”< tbl->elem[i].elem=k; i++; cin>>k;} cout<<“请输入所需查找数的关键码字段：”< { flag=mid; cout<<“查找成功”< break; cout<<“所查找的数为//查找成功，元素位置设置到flag中 ”< } } } else return flag; cout<<“查找失败”< //定义关键码字段 ElemType elem; //定义其他字段 }elemtype;typedef struct //顺序存储结构定义 { elemtype elem[MaxSize];//定义数组 int length; //表长度 }S_TBL;S_TBL *Init_S_TBL() //顺序表的初始化 { S_TBL *s;s=new S_TBL[sizeof(S_TBL)];s->length=-1;return s;};int Binary_search(S_TBL *tbl,KeyType kx)//在表tbl中查找关键码为kx的数据元素 { int mid,flag=0,low=1,high=tbl->length;//1.设置初始区间 while(low<=high) //2.表空测试 { //非空，进行比较测试 mid=(low+high)/2; //3.得到中间点 if(kx high=mid-1; //调整到左半区 else if(kx>tbl->elem[mid].key) low=mid+1; //调整到右半区 else { //返回该元素在表中的位置，或返回0 };void main(){ S_TBL *tbl;tbl=Init_S_TBL();int i,k;cout<<“输入一组以-1结尾的数(关键码字段)”< tbl->length++; i=tbl->length+1; tbl->elem[i].key=k; cin>>k;} i=1;cout<<“输入一组以-1结尾的数(数据元素)”< tbl->elem[i].elem=k; i++; cin>>k;} cout<<“输入所需查找数的关键码字段”< cout<<“查找成功”< cout<<“所查找的数为”< } else cout<<“查找失败”< -1结尾的数(数据元素)33 22 11 55 99 77 88 66 44-1 输入所需查找数的关键码字段3 查找成功 所查找的数为33 实验四的收获 查找的程序对我来说不陌生。两种基本方法的比较和应用里，我留意了最大查找次 数的不同。顺序查找的进行，如果查找不成功那么会议共比较N+1次。当数据量很大的时候，平均查找长度过大，当然顺序查找对于数据的存贮方式没有任何的要求。折半查找会有一个平均查找长度以及查找的最大长度。 我比较倾向于这本查找，其查找的效率明显会高于顺序查找。特别地，我还留意到对于单链表结构，无法进行二分法的查找，因为全部的元素的定位只能从指针开始。对于线性列表只能采取顺序查找的方式。 上机实践五 题目五：排序(插入排序选择排序冒泡排序)排序是数据处理中经常使用的一种重要的运算，其目的就是将一组数据按照规定的顺序进行排列。排序的目的是便于查询和处理。插入排序的基本思想是每一步将一个待排序的元素，按照其关键字吗的大小，插入到前面已经排序号的一组元素的适当的位置上，知道所有的元素都插入为止。一般地认为插入排序是一个稳定的排序方法。选择排序，每次从当前待排序的记录中，通过依次地进行关键字妈的比较从中选择一个关键字最小的记录，并且把它与当前待排序的第一个记录进行交换。直接选择排序是一个不稳定的排序方法。冒泡排序是一种简单的交换排序的方法。一次地比较相邻两个记录的关键字，若发现两个记录的次序相反（即位前一个记录的关键字大雨后有一个记录的关键字），进行记录的交换一直到没有反序为止。极端情况下，冒泡排序会有最短与最长时间，整个队列越是接近有序，则冒泡排序的进行次数越少。 //031040102 插入排序 #include //定义关键码字段 ElemType elem; //定义其他字段 }elemtype; typedef struct //顺序存储结构定义 { elemtype elem[MaxSize]; //定义数组 int length; //表长度 }S_TBL; S_TBL *Init_S_TBL() //顺序表的初始化 { S_TBL *s;s=new S_TBL[sizeof(S_TBL)];s->length=-1;return s;}; int Binary_search(S_TBL *tbl,KeyType kx)//在表tbl中查找关键码为kx的数据元素 { int mid,flag=0,low=1,high=tbl->length;//1.设置初始区间 while(low<=high) //2.表空测试 { //非空，进行比较测试 mid=(low+high)/2; //3.得到中间点 if(kx high=mid-1; //调整到左半区 else if(kx>tbl->elem[mid].key) low=mid+1; //调整到右半区 else { flag=mid; break; //查找成功，元素位置设置到flag中 } } Return flag;//返回该元素在表中的位置，或返回0 }; void main(){ S_TBL *tbl;tbl=Init_S_TBL();int i,k;cout<<“输入一组以-1结尾的数(关键码字段)”< tbl->length++; i=tbl->length+1; tbl->elem[i].key=k; cin>>k;} i=1;cout<<“输入一组以-1结尾的数(数据元素)”< while(k!=-1)};{ void Print(RecType R[],int n) tbl->elem[i].elem=k; i++; cin>>k;} cout<<“输入所需查找数的关键码字段”< cout<<“查找成功”< cout<<“所查找的数为”< cout<<“查找失败”< k=i; for(j=i+1;j<=n;j++) if(R[j].key k=j; if(k!=i) { R[0]=R[k]; R[k]=R[i]; R[i]=R[0]; } } //输出数组内所有元素 { cout<<“关键字段为：”< cout< cout< R[++n].key=x; cin>>x;} n=0;cout<<“请输入一组以-1结尾的数(数据元素)：”< R[++n].otherinfo=x; cin>>x;} cout<<“ 排序前 ”< Print(R,n);SelectSort(R,n);cout<<“排序后”< 请输入一组以-1结尾的数(数据元素)： 33 22 11 44 55 66 99 88 77-1 排序前 关键字段为： 6 9 7 4 1 5 6 8 3 所有元素为： 33 22 11 44 55 66 99 88 排序后 关键字段为： 1 3 4 5 6 6 7 8 9 所有元素为： 55 44 66 33 99 11 88 22 //031040102 冒泡排序 #include #define MaxSize 50 cin>>x;typedef struct RecType } //定义排序记录的形式 cout<<“排序前：”< 请输入一组以 -1结尾的数(关键码字段)： //选择排序函数 { int i,j,flag;for(i=1;i flag=1; for(j=1;j<=n-i;j++) if(R[j+1].key { flag=0; R[0]=R[j]; R[j]=R[j+1]; R[j+1]=R[0]; } if(flag==1) return;} };void Print(RecType R[],int n)//输出数组内所有元素 { cout<<“关键字段为：”< cout< cout< R[++n].key=x; cin>>x;} n=0;cout<<“请输入一组以-1结尾的数(数据元素)：”< R[++n].otherinfo=x;9 8 7 4 1 5 6-1 请输入一组以-1结尾的数(数据元素)： 11 22 33 44 66 55 77 88-1 排序前： 关键字段为： 6 9 8 7 4 1 5 6 所有元素为： 11 22 33 44 66 55 77 88 排序后： 关键字段为： 1 4 5 6 6 7 8 9 所有元素为： 55 66 77 11 88 44 33 22 实验五的收获 三种不同的排序方式，都是之前C++ 学习时候的重点掌握内容。 直接插入排序的算法很简洁，也很容易实现。从空间看，它只需要一个元素的辅助，从实践看该算法的主程序运行次数只比元素的个数少一。当然由于原列表的排序状况未知，其总比较次数和总的移动次数也是未定的，取平均数约为0.25N^2。对于直接选择排序，比较次数与原表元素的排列顺序无关，移动次数有关。根据冒泡排序的思想，待排序的记录有序之 后，则在下一趟的排序时候不会再有记录的交换位置，由此，我增加了一个标记flag，来直观表示每一次的排序是否需要发生交换，无交换则已经完成可以结束冒泡。特别地冒泡排序需要增加一个附加的单元来实现元素的交换。在交换时需要留意免得出错。 · 数据结构实验报告 课程 数据结构 _ 院 系 专业班级 实验地点 姓 名 学 号 实验时间 指导老师 数据结构上机实验报告1 一﹑实验名称： 实验一——链表 二﹑实验目的： 1.了解线性表的逻辑结构特性； 2.熟悉链表的基本运算在顺序存储结构上的实现，熟练掌握链式存储结构的描述方法； 3.掌握链表的基本操作（建表、插入、删除等）4.掌握循环链表的概念，加深对链表的本质的理解。5.掌握运用上机调试链表的基本方法 三﹑实验内容： （1）（2）（3）（4）创建一个链表 在链表中插入元素 在链表中删除一个元素 销毁链表 四﹑实验步骤与程序 #include LinkList p,q;L=(LinkList)malloc(sizeof(Lnode));L->next=NULL;q=L; cout<<“请输入一个链表：”< for(int i=0;i { p=(LinkList)malloc(sizeof(Lnode)); cin>>p->data; p->next=q->next; q->next=p; q=p; } } int PrintLinkList(LinkList &L){//输出链表L的数据元素 LinkList p; } void LinkListLengh(LinkList &L){//计算链表L的数据元素个数。int i=0;p=L->next;if(L->next==NULL){ } cout<<“链表的数据元素为:”;while(p) { cout< data<<“ ”; p=p->next;} cout<<“链表没有元素!”< } LinkList p;p=L->next;while(p){ i++; p=p->next; } cout<<“链表的数据元素个数为:”< LinkList p,s;int j=0;p=L; while(p&&j } if(!p||j>i-1){ p=p->next;++j; } } cout<<“插入元素的位置不合理!”;return 0;s=(LinkList)malloc(sizeof(LNode));s->data=x;s->next=p->next;p->next=s;return 1;int DeleteLinkList(LinkList &L,int i){//删除链表L的第I个数据元素。 LinkList p,q;int j=0;p=L;while(p->next&&j } if(!(p->next)||j>i-1){ p=p->next;++j; } } cout<<“删除元素的位置不合理!”;return 0;q=p->next;p->next=q->next;i=q->data;free(q);return 1;void DestroyLinkList(LinkList &L){//销毁链表L。 LinkList p,q;p=L->next;while(L->next!=NULL){ q=p->next;L->next=q; free(p);} p=q; free(L); cout<<“链表已经被销毁!”< LinkList L; int i,j,x;cout<<“第一次数据结构上机实验—链表”< CreatLinkList(L,j); LinkListLengh(L); PrintLinkList(L); cout<<“在第几个元素前插入:”;cin>>i;cout<<“输入插入的元素:”;cin>>x; InsertLinkList(L,i,x); LinkListLengh(L); PrintLinkList(L); cout<<“输入删除元素的位置:”;cin>>i; DeleteLinkList(L,i); LinkListLengh(L); PrintLinkList(L); cout<<“销毁程序后为:”< DestroyLinkList(L);} 五﹑实验结果 六﹑实验心得体会： 链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。 实验的程序设计规划（实现的功能、分几个模块、子函数）（1）编写链表创建子函数void CreatLinkList(L,j)（2）编写链表插入子函数 int InsertLinkList(LinkList &L, int i, int x)（3）链表的打印int PrintLinkList(LinkList &L)（4）编写链表删除子函数 int DeleteLinkList(LinkList &L,int i)（5）编写链表销毁子函数void DestroyLinkList(LinkList &L)（6）编写主函数Main()，通过功能菜单调用子函数（7）编译调试程序 经过多次的调试，修改，实验结果终于正确了，在这个过程中，经历了不知道怎么进行声明区的编写如包含文件，宏定义，函数声明，全局变量声明，结构体等的定义等的结合，到学会了使用先把程序主要规划为四个部分来写就简单多了，第一，定义；第二，写所要调用的子函数；第三，写主函数，调用子函数；第四就是程序的编译与调试，修改。数据结构实验需要我们对每个程序的算法有深刻的理解，才能应用到实际中去，因此我们需要在做实验之前要熟悉实验的内容，且先把所要实验的程序写出来，在实验中就可以查找错误并加以改正，这是一个成长的过程。 数据结构上机实验报告一﹑实验名称： 实验二—队列 二﹑实验目的： 1.掌握队列这种抽象数据类型的特点, 掌握栈与队列在实际问题中的应用和基本编程技巧,并能在相应的问题中选用它;2.熟练掌握循环队列和链队列的基本操作实现算法，特别是队满和队空的描述方法； 3．掌握栈与队列的数据类型描述及特点； 4.掌握栈的顺序和链式存储存表示与基本算法的实现； 5.掌握队列的链式存储表示与基本操作算法实现;6.按照实验题目要求，独立完成实际程序的编写编写、调试和运行，并通过用例数据的运行过程抓获相关屏面验证程序设计的正确性； 7.认真书写实验报告，并按时提交。 三﹑实验内容： 对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求： （1）掌握栈和队列的特点，即后进先出和先进先出的原则。（2）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空； （3）编写主函数进行测试。 四﹑实验步骤与程序 #include #define OK 1 #define ERROR 0 #define OVERFLOW 0 typedef struct QNode { int data;struct QNode *next;}QNode,*QueuePtr;typedef struct { QueuePtr front;QueuePtr rear;}LinkQueue;int InitQueue(LinkQueue &Q){ } Q.rear=Q.front=(QueuePtr)malloc(sizeof(QNode));if(!Q.rear)exit(OVERFLOW);Q.front->next=NULL;return OK;void QueueEmpty(LinkQueue Q){ } void EnQueue(LinkQueue &Q,int e){ } int EnnQueue(LinkQueue &Q,int e){ QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)printf(“error”);if(Q.front==Q.rear)printf(“该链队为空:”);else printf(“该链队不为空:”);p->data=e;Q.rear->next=p;Q.rear=p;printf(“元素%d入队成功”,e); } if(!p)return ERROR;p->data=e;Q.rear->next=p;Q.rear=p; return OK;void DeQueue(LinkQueue &Q){ } void GetHead(LinkQueue &Q){ QueuePtr p;QueuePtr p;if(Q.front==Q.rear)printf(“该链队为空”);p=Q.front->next;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);printf(“队首元素删除成功”); } if(Q.front==Q.rear)printf(“该链队为空”);p=Q.front->next;printf(“队首元素为:%d”,p->data);void OutQueue(LinkQueue &Q){ } void LengthQueue(LinkQueue &Q){ int f=0;QueuePtr p;if(Q.front==Q.rear)QueuePtr p;if(Q.front==Q.rear)printf(“该链队为空”);p=Q.front->next;while(p!=Q.rear->next){ } printf(“%d%,”,p->data);p=p->next; } printf(“该队列的长度为:%d”,f);else { } p=Q.front->next;while(p!=Q.rear->next){ } printf(“该队列的长度为:%d”,f);p=p->next;f++;void main(){ system(“cls”);int flag=1,i;LinkQueue Q;InitQueue(Q);printf(“************************链队列功能菜单***********************n”);printf(“1:初始化链队列，2:判断链队列是否为空, 3:进入队列，4:取出队首元素n”);printf(“5:输出该队列的所有元素,6:输出该队列的长度，7:结束程序，8:清屏n”); while(flag){ printf(“n请输入操作符:”);scanf(“%d”,&i);switch(i){ case 1: int e,n,k;printf(“请输入队列的长度:”);scanf(“%d”,&n);printf(“请输入队列的元素:”);for(e=1;e<=n;e++){ } printf(“初始化链队成功”);break;scanf(“%d”,&k);EnnQueue(Q,k);case 2: QueueEmpty(Q); break;case 3: int j;printf(“请输入要进入队列的元素”);scanf(“%d”,&j);EnQueue(Q,j);break;case 4: GetHead(Q);break;case 5: printf(“该队列的元素为:”);OutQueue(Q);break; case 6: LengthQueue(Q);break;case 7: flag=0;break;case 8: system(“cls”);} break; } } 五﹑实验结果 六﹑实验心得体会： 程序主要构造了主函数main（）和 InitQueue（），QueueEmpty（）EnQueue()，OutQueue()等调用函数，实现了队列的创立，队列是否为空的判断，入队和出队等功能。 通过此次实验，加深了对队列的存储结构的了解，同时也对程序设计能力有了提高，加深了对队列先进先出性质的理解，它允许在表的一端进行插入，在另一端删除元素，这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。我们往往写不出程序，这其中的原因我觉得是对程序的结构不是很了解，对实验的内容也不熟练的结果，数据结构给我们许多程序的算法和模型，对我们写程序的思维有很大的锻炼，我们应珍惜每次上机实验的机会去实践课堂上所学的东西并从中发现问题，从而达到提升写程序的能力。 数据结构上机实验报告一﹑实验名称： 实验三—二叉树的遍历 二﹑实验目的： 1、熟悉二叉树的结构特性，了解相应的证明方法； 2、掌握二叉树的生成，掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法； 3、理解二叉树的三种遍历方法：先序遍历、中序遍历和后序遍历； 4、学会编写实现树的各种操作的算法。 二、实验内容： 1、使用类定义实现二叉树，补充完整所缺的函数，并实现创建和遍历二叉树的基本操作； 2、编程实现在二叉链表这种存储方式下，实现二叉的遍历，可采用递归或者非递归实现，遍历算法为在先序、中序和后序遍历算法。 三、实验步骤与程序： #include void PreOrder(BiTree T)//先序 { if(T!=NULL){ printf(“%c”,T->data);PreOrder(T->lchild);PreOrder(T->rchild);} } void InOrder(BiTree T)//中序 { if(T!=NULL){ InOrder(T->lchild);printf(“%c”,T->data);InOrder(T->rchild);} } void PostOrder(BiTree T)//后序 { if(T!=NULL){ PostOrder(T->lchild);PostOrder(T->rchild);printf(“%c”,T->data);} } void main()//主函数 { printf(“------------二叉树的遍历-------------n”);printf(“请输入要遍历的数：”);BiTree Ta;Ta=CreateBiTree();printf(“先序遍历:”);printf(“n”);PreOrder(Ta);printf(“n”);printf(“中序遍历:”);printf(“n”);InOrder(Ta);printf(“n”);printf(“后序遍历:”);printf(“n”);PostOrder(Ta);} 五﹑实验结果 六﹑实验心得体会： 实验的程序设计规划（实现的功能、分几个模块、子函数）（1）先序遍历递归算法函数：void PreOrder(BiTree T)（2）中序遍历递归算法函数：void InOrder(BiTree T)（3）后续遍历递归算法函数：void PostOrder(BiTree T)（4）主函数的实现：void main() 在实验前我认真阅读关于二叉树的实现的内容，为编程实现第一步，本次实验通过按上述的实验步骤一步步实现的，实验过程中出现了一些错误，经过一步步的调试，修改错误，得到了二叉树的遍历用递归运算的方法的程序。通过这个实验，我体会到了理解数据结构的重要性，这有真正理解了定义数据类型的好处，才能用好这样一种数据结构。二叉树的先序，中序与后序的输出都用了递归的算法，而且用起来不是很复杂，这使我更进一步理解了函数递归调用并得到灵活运用；在实现算法上，从算法的效率看，递归方法书写形式较为简洁，更为直观，一般具有较好的空间效率。 总之，不管做什么实验，我们在做实验前都要先预习，对所做的实验有较深的理解，在做实验的时候需要很严谨，仔细的查找错误，从而能在实验中收获知识，提升自己。 数据结构上机实验报告4 一﹑实验名称： 实验四—查找 二﹑实验目的： 1、熟悉掌握顺序表的查找方法； 2、熟练掌握二叉排序树的构造方法和查找算法 3、掌握描述查找过程的判定树的构造方法，以及按照定义计算各种查找方法在等概率情况下查找成功时的平均查找长度； 4、学会定义线性表的储存类型，实现C++程序的基本结构对线性表的一些基本操作和具体的函数定义； 5、掌握顺序表的基本操作，实现顺序表的查找的等基本运算； 6、掌握对于多函数程序的输入，编辑，调试和运算过程。 二、实验内容： 1、实现顺序表的查找算法 2、关于衡量查找的主要操作—查找的查找平均效率的平均长度的讨论。 三、实验步骤与程序： #include element list[MAX_SIZE]; int seqsearch(element list[],int searchnum,int num);int main(){ int i,num,searchnum,k; printf(“---------------数据结构查找实验-------------n”);printf(“请输入数据元素的个数：”);scanf(“%d”,&num);printf(“请输入数据的元素：n”);for(i=0;i printf(“请输入要查询的数据元素:”);scanf(“%d”,&searchnum);k=seqsearch(list,searchnum,num);if(k!=-1){ printf(“所查询元素的下标为：”);printf(“%dn”,k);} else printf(“查询元素不存在。n”);} return 0;} int seqsearch(element list[],int searchnum,int num){ int j; list[num].key=searchnum; for(j=0;list[j].key!=searchnum;j++);return j 六﹑实验心得体会： 实验的程序设计规划为先写一个主函数int main()，再写一个查找的子函数int seqsearch(element list[],int searchnum,int num)，主函数通过调用子函数的方法实现程序的设计。 所谓“查找”即为在一个众多的数据元素（或记录）的查找表中找出某个“特定的”数据元素（或记录），通过本次实验，我更进一步的了解数据结构程序实验设计实现算法的基本模型，和算法实现等基本内容，学会了顺序表的查找方法。 数据结构上机实验报告5 一﹑实验名称： 实验五—内部排序 二﹑实验目的： 1、通过实现下述实验内容，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况，并加以灵活应用。 2、掌握各种排序时间复杂度的分析方法。 二、实验内容： 1、插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。 2、快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成。 3、讨论各种内部排序方法的基本思路，算法特点，排序过程及它们的时间复杂度的分析。 三、实验步骤与程序： #include } int x;void charu();void kuaisu();printf(“----------内部排序---------n”);printf(“ 1、插入排序：n”);printf(“ 2、选择排序：n”);printf(“请根据序号选择：”);scanf(“%d”,&x);if(x==1)charu();else kuaisu();void charu(){ int a[7],j,i,m; printf(“插入排序n”); printf(“请输入个您想排序的数据:n”); for(i=0;i<7;i++)scanf(“%d”,&a[i]); for(j=1;j<7;j++) { m=a[j]; for(i=j-1;i>=0;i--) { if(a[i] break; else a[i+1]=a[i]; } a[i+1]=m; } printf(“排序成功:”); for(i=0;i<7;i++) printf(“ %d”,a[i]); printf(“n”);} quick(int first,int end,int L[]){ int left=first,right=end,key; key=L[first]; while(left { while((left right--; if(left L[left++]=L[right]; while((left left++; if(left L[left]=key; return left; } quick_sort(int L[],int first,int end) { int split; if(end>first) { split=quick(first,end,L); quick_sort(L,first,split-1); quick_sort(L,split+1,end); } } void kuaisu(){ int a[7],i; printf(“快速排序n”); printf(“请输入个您想排序的数据:n”); for(i=0;i<7;i++) scanf(“%d”,&a[i]); quick_sort(a,0,9); printf(“排序成功:”); for(i=0;i<7;i++) printf(“ %d”,a[i]); printf(“n”);} 五﹑实验结果： 六﹑实验心得体会： 排序的功能是将一个数据元素（或记录）的任意序列，从新排成按关键字有序的序列；直接插入排序的稳定性比快速排序高，且算法较简单。本次实验运用到的是插入排序和快速排序。 实习报告 题 目 : 实现一个约瑟夫环程序 班级：031021姓名：王帅学号：03102076 一、需求分析 1． 本演示程序中，利用单向循环链表存储结构存储约瑟夫环数据（即n个人的编号和密码）。 2． 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中需要输入的数据，运算结果显示在其后。 3． 程序执行的命令包括： 1)构造单向循环链表；2）进行数值的输入，并作判断分析；3）约瑟夫算法的实现与结果输出；4）结束。 4． 测试数据 m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，（正确的出列顺序为6，1，4，7，2，1，3，5）。 二、概要设计 1．单向循环链表的抽象数据类型定义为： ADT List｛ 数据对象：D=｛ai | ai↔正整数，I=1，2，......，n,n≥0｝数据关系：R1=｛< ai-1，ai > |，ai-1，ai↔D,I=1，2，......，n｝基本操作： Init List(&L) 操作结果：构造一个空的线性表L。 List Insert(&L,i,e) 初始条件：线性表L已存在，1≤i≤List Length(L)+1.操作结果：在L中第i个位置之前插入新的数据元素e，L长度加1。List Delete(&L,i,&e) 初始条件：线性表L存在非空，1≤i≤List Length(L).操作结果：删除L的第i个元素，并用e返回其值，L长度减1。 2． 程序包含四个模块： 1）主程序模块： void main() { 初始化； for（;;） {} while（命令=开始） { 接受命令； 处理命令； } for（;;） { } } 2）有序表单元模块——实现有序表的抽象数据类型； 3）节点结构单元模块——定义有序表的节点结构； 4）数据输入分析模块——判断输入数据正确有效； 各模块之间的调用关系如下： 主程序模块 ↓ 有序表结构模块 ↓ 节点结构单元模块 ↓ 数据输入分析模块 三、详细设计 1、结点类型，指针类型 TypedefstructLNode{ int code,date;//code 为人所在位置 date为人持有的密码 struct LNode *next; };// 结点类型，指针类型 2、构造单向循环链表 struct LNode *p,*head,*q;//定义头节点，和指针 for(i=2;i<=n;i++) { struct LNode *s=(struct LNode *)malloc(sizeof(struct LNode));//分配 新结点空间 s->code=i; input(s->date); p->next=s; p=p->next; } p->next=head;//根据输入的人数，进行单项循环链表的创建，p指向最后一个结点，并与头节点链接，形成单项循环链表 3、约瑟夫环的程序实现部分 while(n!=1)//判断输入人数，如为1则直接输出结果，不循环 { for(i=1，m=m%n;i { p=p->next; } q=p->next;//找到要删除节点 p->next=q->next;//找到要删除节点的后继，并连接新环m=q->date;//找到下一个密码 printf(“%d”,q->code); free(q);//释放已删除节点空间 n--;//链表长度减一 } printf(“%d”,p->code);//约瑟夫环的结果输出 4、其他函数代码 数值的输入限制 int input() { int y,k,z=0; char c;//元素类型 char a[4];//数组初始化 if(!z)//输入判断，确定位数字或控制字符且位置和密码不为零 { for(y=0;y<4;y++) { c=getch(); if(c>=48&&c<=57)//确定为输入数字 {a[y]=c; putch(c); } else { y--; if(c=='r')//确定输入为控制字符 即回车或者删除 break; else if(c==8) {a[y]='n'; y--;} continue; } } k=atoi(a);//确定最终输入数字的值 printf(“n”); z=k; if(z==0) printf(“ERROR!The number couldn't be 0!n”);// 输入为零，重新输入 } return(k);//数值的返回 5、函数的调用关系图反映程序层次结构 Main→input 四、调试分析 1、早期程序只写了约瑟夫环的实现部分，没有对输入数据进行筛选，调试的时候会经常出错。比如是输入字母，或者输入0，大于32767溢出； 2、早期的循环过程中没有进行优化，导致循环次数过多，浪费时间； 3、为了输出时美观，分别在input和main函数主体内做了两次，输入非零的判断，浪费了资源； 4、算法的时空分析 为了限制在输入过程中不会上溢，只在输入中限定为四个不全为零的数字，但是做的是do……while循环，复杂度为o（1）; 当n大于1时： 在数据输入中，链表的创建是for循环，时间复杂度为o（n-1） 在约瑟夫环实现程序中，为for循环。时间复杂度为o（m%n-1） 当n=1时，复杂度为o（1）。 五、用户手册 用户根据提示，先输入起始密码m，然后输入人数n，再根据人数，分别输入每个人的密码date，数值均不能为0，否则会提示重新输入，输入为字母则自动丢弃，输入错误可用删除键进行修改，输入完成后按回车键确定本次输入完毕（若输入数字大于9999，则第五位自动转换为下一个数字的起始位，依此类推）。 当n个数字全部输入完毕，则自动显示结果，按任意键则退出本程序。 六、测试结果 第一组：m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，出列顺序为6，1，4，7，2，1，3，5。 第二组： m 的初值为30；n=8，7个人的密码依次为：5，1，6，9，4，7，2，3，出列顺序为6，5，2，3，7，1，4，8。 第三组 : m 的初值为15；n=6，7个人的密码依次为：5，3，4，7，6，9，出列顺序为3，1，2，6，4，5。 七、附录 源程序头文件名清单： #include “malloc.h”//内存空间分配头文件 #include “stdio.h”//输入输出函数头文件 #include “stdlib.h”//input函数中字符串转短整形函数的头文件 #include “conio.h”//最后显示结果、清屏函数头文件 数据结构上机实验六 实验内容:图的基本操作 实验要求: 1)图的遍历与基本操作要作为函数被调用.2)把自己使用的图结构明确的表达出来.3)基本上实现每个实验题目的要求.分组要求：可单独完成，也可两人一组。 实验目的: 1)熟悉C/C++基本编程,培养动手能力.2)通过实验,加深对图的理解.评分标准： 1)只完成第一和第二题，根据情况得4，5分； 2）完成前3题，根据情况得5至7分； 3）在2）基础上，选做四）中题目，根据情况得8至10分。 题目: 一)建立一个无向图+遍历+插入 (1)以数组表示法作为存储结构，从键盘依次输入顶点数、弧数与各弧信息建立一个无向图； (2)对（1）中生成的无向图进行广度优先遍历并打印结果； (3)向（1）中生成的无向图插入一条新弧并打印结果； 二)建立一个有向图+遍历+插入+删除 (1)以邻接表作为图的存储结构，从键盘输入图的顶点与弧的信息建立一个有向图； (2)对（1）中生成的有向图进行深度优先遍历并打印结果； (3)在（1）中生成的有向图中，分别插入与删除一条弧并打印其结果； (4)在（1）中生成的有向图中，分别插入与删除一个顶点并打印结果； (5)在（1）中生成的有向图中,各顶点的入度与出度并打印结果； 三）基本应用题 （1）编写算法，判断图中指定的两个顶点是否连通。 （2）编写算法，判断图的连通性。如果不连通，求连通分量的个数 （3）编写算法，判断图中任意两个顶点的连通性 （4）编写算法，判断图中是否存在回路。 （5）实现图的广度优先搜索算法。 四）高级应用题 （1）实现Prim算法 （2）实现Kruskal算法 （3）实现迪杰斯特拉算法 （4）实现拓扑排序算法 （5）实现关键路径算法 实验一 线性表 一、实验题 线性表的应用———多项式计算 二、程序设计思路 包括每个函数的功能说明，及一些重要函数的算法实现思路一链式存储： 1.void InitPoly(LNode *&p)初始化多项式 2.void TraversePoly(LNode *&p)遍历多项式 3.void ClearPoly(LNode *&p)清除多项式 4.void InsertPoly(LNode *&p, double a, int e)插入一项 5.void DeletetPoly(LNode *&p,int pos) 删除一项 6.double PolySum(LNode *&p, double x) 多项式求值 7.LNode * PolyAdd(LNode *&p1,LNode *& p2) 多项式相加 顺序存储： 1.void InitPoly1(SeqList &L)初始化多项式 2.void ClearPoly1(SeqList &L)清除多项式 3.void TraversePoly1(SeqList L) 遍历多项式 4.bool InsertPoly1(SeqList &L, ElemType item)插入一项 5.double PolySum1(SeqList L,double x) 多项式求值 6.bool DeleteList1(SeqList &L,int pos) 删除一项 7.SeqList PolyAdd1(SeqList &L1,SeqList& L2) 多项式相加 三、源程序代码 #include { if(pos>1||pos<-1)return false;NodeType *cp=p->next;NodeType *np=p;if(pos==0){ while(cp!=p){ if(cp->coef==a&&cp->exp==e)break;else{ np=cp;cp=cp->next;} } } else if(pos==-1)while(cp!=p){ 删除np=cp;cp=cp->next;} np->next=cp->next;delete cp;return true;} double PolySum(NodeType *p, float x)//多项式求值 { int i;double sum=0,item;NodeType *cp=p->next;while(cp!=p){ item=1;for(i=1;i<=cp->exp;i++)item=item*x;sum=sum+item*cp->coef;cp=cp->next;} return sum;} NodeType *PolyAdd(NodeType *p1, NodeType *p2)//多项式相加 { float coef;NodeType *a=p1->next,*b=p2->next,*c,*pc;InitPoly(c);pc=c;while(a!=p1&&b!=p2){ if(a->exp==b->exp){ coef=a->coef+b->coef;if(coef!=0){ InsertPoly(pc, coef, a->exp);pc=pc->next;} a=a->next;b=b->next;} else if(a->exp 输出多项式 } void ClearPoly1(ListType &p)//清除多项式 { if(p.list!=NULL){ delete []p.list;p.list=NULL;} p.size=0;} void InsertPoly1(ListType &p, float a, int e)//项 { p.list[e]=a;if(p.size { int i,n;if(p.size==0){ cout<<“多项式为空,删除无效!”< 插入一if(p.list[e]==a)p.list[e]=0;else if(pos==-1)p.list[p.size]=0;return true;} double PolySum1(ListType p, float x)//值 { double sum=0,item;int i,j;for(i=0;i<=p.size;i++){ item=1;for(j=1;j<=i;j++)item=item*x;sum=sum+item*p.list[i];} return sum;} ListType PolyAdd1(ListType p1, ListType p2)//项式相加 { ListType p;InitPoly1(p);float coef; 多项式求多int i,j;for(i=0;i<=p1.size;i++){ coef=p1.list[i]+p2.list[i];InsertPoly1(p, coef, i);} if(i<=p1.size)for(j=i;j<=p1.size;j++)InsertPoly1(p, p1.list[j], j);if(i<=p2.size)for(j=i;j<=p2.size;j++)InsertPoly1(p, p2.list[j], j);return p;四实验结果分析 五.心得体会 对于结构体的认识增加了，对于动态存储也有了更多的认识，也是在不知不觉中提高了。 实验二 字符串的操作 一、实验题目——字符串的操作 二、程序设计思路 采用定长顺序存储表示，由用户创建串s和串t，实现在串s中下标为pos的字符之前插入串t。 三、源程序代码 #define MAXLEN 10 typedef struct { /*串结构定义*/ char ch[MAXLEN]; int len;}SString;void createstring(SString *s) /*创建串s*/ { int i,j;char c;printf(“input the length of the string:”); scanf(“%d”,&j); for(i=0;i { printf(“input the %d:”,i+1); fflush(stdin); scanf(“%c”,&c); s->ch[i] = c; } s->len = j;} void output(SString *s) /*输出串s*/ { int i;for(i=0;i printf(“%c ”,s->ch[i]); printf(“n”);} int StrInsert(SString *s, int pos, SString *t)/*在串s中下标为pos的字符之前插入串t */ { int i;if(pos<0 || pos>s->len) /*插入位置不合法*/ return(0); if(s->len + t->len<=MAXLEN) /*插入后串长≤MAXLEN*/ { for(i=s->len + t->len-1;i>=t->len + pos;i--) s->ch[i]=s->ch[i-t->len];/*将下标为pos的字符后的元素往后移动t->len个长度*/ for(i=0;i s->ch[i+pos]=t->ch[i]; /*将串t从下标为pos位置开始插入到串s*/ s->len=s->len+t->len;} else { if(pos+t->len<=MAXLEN)/*插入后串长>MAXLEN,但串t的字符序列可以全部插入*/ { for(i=MAXLEN-1;i>t->len+pos-1;i--) s->ch[i]=s->ch[i-t->len]; for(i=0;i s->ch[i+pos]=t->ch[i]; /*将串t从下标为pos位置开始插入到串s*/ s->len=MAXLEN; } else /*插入后串长>MAXLEN,并且串t的部分字符也要舍弃*/ { for(i=0;i s->ch[i+pos]=t->ch[i]; /*直接从下标为pos的位置按顺序插入串t*/ s->len=MAXLEN; } return(1);} } void main(){ SString *str1;SString *str2;int i,j,k,pos;int flag=0;str1 =(SString *)malloc(sizeof(SString));str1->len = 0;printf(“creat the string 1:n”);createstring(str1);printf(“creat the string 2:n”);createstring(str2);printf(“input the insert local:”);scanf(“%d”,&pos);flag=StrInsert(str1,pos,str2);if(flag == 0) printf(“insert error!”);else { printf(“after insert:n”); output(str1);} } 四、实验结果 五、实验体会 通过本次实验，我加深了对串数据结构的理解。在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。在存储方式中，结点大小的选择和顺序存储方式的格式选择一样都很重要，它直接影响着串处理的效率。 实验三 一、实验题目——非递归算法对二叉树进行中前序遍历 二、程序设计思路 创建一棵10个节点构造的完全二叉树，并对其进行前、中、后序遍历。 三、源程序代码 #define STUDENT EType #define SType SType #define HeadEType int #include //定义数据结构类型 struct STUDENT { char name[8];int age;char number[15];char address[20];}; struct BinaryTreeNode { EType data;BinaryTreeNode *LChild;BinaryTreeNode *RChild;};typedef BinaryTreeNode BinaryTree; typedef struct { BinaryTreeNode *ptr;bool status;}SType; typedef struct { SType *element;int top;int MaxSize;}Stack; void CreatStack(Stack &S, int MaxStackSize){// 构造一个最大容量为MaxStackSize 的堆栈 S.MaxSize = MaxStackSize; S.element = new SType[S.MaxSize]; S.top =-1;} bool IsEmpty(Stack &S){// 判断堆栈S是否为空 if(S.top ==-1) return true; return false;} bool IsFull(Stack &S){// 判断堆栈S是否为空 if(S.top == MaxSize-1) return true; return false;} bool Push(Stack &S , SType &x){// x进s栈，返回进栈后的状态值 if(IsFull(S)) return false; S.top++; S.element[S.top] = x; return true;} bool Pop(Stack &S , SType &x){// 将s栈顶的值取至x中，返回出栈后的状态值 if(IsEmpty(S)) return false; x = S.element[S.top]; S.top--; return true;} BinaryTreeNode *MakeNode(EType &x) {//构造结点 BinaryTreeNode *ptr; ptr = new BinaryTreeNode; if(!ptr)return NULL; ptr->data = x; ptr-> LChild = NULL; ptr-> RChild = NULL; return ptr;} void MakeBinaryTree(BinaryTreeNode *root, BinaryTreeNode *left, BinaryTreeNode *right){// 联接root，left, right所指的结点指针为二叉树 root->LChild=left; root->RChild=right;} void PreOrderNoRecursive(BinaryTreeNode *BT){//二叉树前序遍历非递归的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假设堆的空间足够大，即MaxStackSize值足够大 CreatStack(S,MaxStackSize);//产生一个空栈 while(q||!IsEmpty(S)){ if(q) { cout< ele.ptr=q; Push(S,ele);//节点指针进栈，以后回溯时在退栈 q=q->LChild;//指针指向刚刚被访问的“根”节点的左子树 } else //当左子树为空时，利用堆栈回溯 if(!IsEmpty(S)) { Pop(S,ele);//退栈回溯 q=ele.ptr;//指针重新指向刚刚被访问的“根”节点 q=q->RChild;//指针指向该回溯节点的右子树 } } } void InOrderNoRecursive(BinaryTreeNode *BT){//二叉树的中序遍历非递归的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假设堆的空间足够大，即MaxStackSize值足够大 CreatStack(S,MaxStackSize);//产生一个空栈 while(q ||!IsEmpty(S)){ while(q)//找到最左边的子树 { ele.ptr=q; Push(S,ele);//指针非空时，将当前的“根”节点指针进栈，用于以后回溯 q=q->LChild;//指针继续指向该“根”节点的左子树 } if(!IsEmpty(S))//当左子树为空时，进行退栈回溯 { Pop(S,ele);//从堆栈中回溯节点指针（节点还未访问） q=ele.ptr; cout< q=q->RChild;//指针向回溯的节点右子树推进 } } } void PostOrderNoRecursive(BinaryTreeNode *BT){//二叉树的后序遍历非递归的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假设堆的空间足够大，即MaxStackSize值足够大 CreatStack(S,MaxStackSize);//产生一个空栈 while(q ||!IsEmpty(S)){ if(q)//找最左边的子树 { ele.ptr=q; ele.status=false;//进栈前标记为第一次进栈 Push(S,ele); q=q->LChild;//指针继续向左推进 } else if(!IsEmpty(S))//直到左子树为空时，退栈回溯 { Pop(S,ele);//从堆栈中弹出回溯节点（还未访问） q=ele.ptr;//q指向当前回溯节点 if(ele.status)//判断节点进栈标志，是否对其进行访问 { cout< q=NULL;//将q设为空，为了继续退栈 } else { ele.status=true;//改变回溯节点的进栈标记，以便再次进栈 Push(S,ele); q=q->RChild;//指针向该回溯节点的右孩子推进 } } } } //主函数 void main(){ BinaryTreeNode *ptr[11]; char Name[][8]={“ ”,“A”,“B”,“C”,“D”,“E”,“F”,“G”,“H”,“I”,“J”};EType x[11];for(int i=1;i<11;i++){ strcpy(x[11-i].name,Name[11-i]); ptr[11-i]=MakeNode(x[11-i]);//构造10个二叉树节点 } //将节点链接域填值，构造一个二叉树 //这里构造的是一棵有10个节点的完全二叉树 for(int j=1;j<5;j++){ MakeBinaryTree(ptr[j],ptr[2*j],ptr[2*j+1]);} MakeBinaryTree(ptr[5],ptr[10],NULL);//该完全二叉树构造完毕 //***********对已构造的完全二叉树进行前序非递归遍历************// cout<<“对该二叉树进行前序遍历结果：”< //***********对已构造的完全二叉树进行中序非递归遍历************// cout< //***********对已构造的完全二叉树进行中序非递归遍历************// cout< 四、实验结果分析 五、实验总结 二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。 实验四 一、实验题目——深度优先算法实现图的遍历 二、程序设计思路 以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先，并输出遍历的结点序列。首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先，并输出遍历的结果。 三、源程序代码 #include };struct vexnode { char vertex;edgenode* edgelink;};struct Graph { vexnode adjlists[MaxVerNum];int vexnum;int arcnum;};//队列的定义及相关函数的实现 struct QueueNode { int nData;QueueNode* next;};struct QueueList { QueueNode* front;QueueNode* rear;};void EnQueue(QueueList* Q,int e){ QueueNode *q=new QueueNode;q->nData=e;q->next=NULL;if(Q==NULL) return;if(Q->rear==NULL) Q->front=Q->rear=q;else { Q->rear->next=q; Q->rear=Q->rear->next;} } void DeQueue(QueueList* Q,int* e){ if(Q==NULL) return;if(Q->front==Q->rear){ *e=Q->front->nData; Q->front=Q->rear=NULL;} else { *e=Q->front->nData; Q->front=Q->front->next;} } //创建图 void CreatAdjList(Graph* G){ int i,j,k;edgenode* p1;edgenode* p2;cout<<“请输入顶点数和边数:”< cin>>G->adjlists[i].vertex; G->adjlists[i].edgelink=NULL;} cout<<“开始输入边表信息:”< cout<<“请输入边 cin>>i>>j; p1=new edgenode; p1->endver=j; p1->edgenext=G->adjlists[i].edgelink; G->adjlists[i].edgelink=p1; p2=new edgenode; p2->endver=i; p2->edgenext=G->adjlists[j].edgelink; G->adjlists[j].edgelink=p2; //因为是无向图，所以有两次建立边表的过程 } } //------------------------------深度优先遍历 void DFS(Graph *G,int i,int visit[]){ cout< DFS(G,p->endver,visit);} } void DFStraversal(Graph *G,char c)//深度优先遍历 { cout<<“该图的深度优先遍历结果为:”< visit[i]=0;//全部初始化为0，即未访问状态 } int m;for(i=0;i if(G->adjlists[i].vertex==c)//根据字符查找序号 { m=i; DFS(G,i,visit); break; } } //继续访问未被访问的结点 for(i=0;i if(visit[i]==0) DFS(G,i,visit);} cout< int e=0; DeQueue(Q,&e); cout< visit[e]=1; edgenode* p=new edgenode; p=G->adjlists[e].edgelink; if(p) { int m=p->endver; if(m==0) { EnQueue(Q,m); while(visit[m]==0) { p=p->edgenext; if(p==NULL) break; m=p->endver; EnQueue(Q,m); } } } } } void BFStraversal(Graph *G,char c){ cout<<“该图的广度优先遍历结果为:”< visited[i]=0;} int m;for(i=0;i if(G->adjlists[i].vertex==c) { m=i; BFS(G,i,visited); break; } } //继续访问未被访问的结点 for(i=0;i if(visited[i]==0) BFS(G,i,visited);} cout< 四、实验结果及分析 五、实验总结 本次试验采用的是邻接表的方式实现图的深度优先遍历和。对于深度优先遍历，主要是采用递归的方式。试验本身问题不是太大，但要注意输入的问题，什么时候用空格，什么时候用回车，这一点是需要注意的，因为一旦数据的输入有问题，结果当然也就不可能正确了。只有正确的输入数据，建立图，才能得出正确的遍历结果。第二篇：数据结构上机实验报告
第三篇：数据结构上机实验报告
第四篇：数据结构上机实验--图
第五篇：数据结构上机作业
点击咨询 