数据结构-顺序串基本操作实验报告

数据结构-顺序串基本操作实验报告实验一：线性表实验目的：在于帮助学生熟练掌握线性表的基本操作在两种存储结构上的实现，其中以各种链表的操作和应用为重点内容。实验题目：1.顺序表逆置算法..2.单链表的逆置算法.1.顺序表逆置算法..//-----结构的定义及宏定义----#include<iostream>#include"stdio.h"#include"malloc.h"#defineERROR0#defineOK1#defineOVERFLOW-2#defineLIST_INIT_SIZE100#defineLISTINCREMENT10usingnamespacestd;typedefintElemType;typedefstruct{ElemType*elem;intlength;intlistsize;}Sqlist;typedefintStatus;//-----初始化顺序表----------StatusInitList(Sqlist&L)//加&是会改变顺序表，不加则不会改变{L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));//if(!L->elem)exit(OVERFLOW)L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}//--------顺序表的插入-----------StatusListInsert_Sq(Sqlist&L,inti,ElemTypee){ElemType*newbase,*q,*p;if(i<1||i>L.length+1){returnERROR;}if(L.length<=L.listsize){newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));//if(!newbase)exit(OVERFLOW)L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p>=q;--p){*(p+1)=*p;}*q=e;++L.length;returnOK;}//---------顺序表的转置（反过来）-----------------Statusrev(Sqlist&L){ElemTypetemp;for(inti=0;i<L.length/2;i++){temp=L.elem[i];L.elem[i]=L.elem[L.length-1-i];L.elem[L.length-1-i]=temp;}returnOK;}//---------顺序表的输出-----------------StatusOutput(SqlistL){cout<<endl;//<<L.length;//调试：查看当前表中元素个数for(inti=0;i<L.length;i++){cout<<L.elem[i];}returnOK;}//--------主函数-----------intmain(){inti,e;SqlistL;InitList(L);for(i=1;i<10;i++){cin>>e;ListInsert_Sq(L,i,e);}Output(L);rev(L);Output(L);system("pause");return0;}2.单链表的逆置算法.#include<iostream>#include"malloc.h"#include"stdio.h"#defineNULL0#defineERROR0#defineOK1usingnamespacestd;typedefintElemType;typedefintStatus;typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;//-------建立单链表-----------------LinkListCreateList_L(intn){LinkListL,p;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;for(inti=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));cin>>p->data;p->next=L->next;L->next=p;}returnL;}//-------单链表的转置---------Statusrev(LinkList&L){LinkListP,Q;P=L->next;if(L->next&&P->next){Q=P->next;P->next=NULL;for(;Q;){P=Q;Q=Q->next;P->next=L->next;L->next=P;}}returnOK;}//------------顺序表遍历输出---------------StatusOutput(LinkList&L){LinkListP=L->next;cout<<'\n';for(;P;P=P->next){cout<<P->data<<'\t';}returnOK;}//---------主函数----------intmain(){LinkListL;L=CreateList_L(10);Output(L);rev(L);Output(L);system("pause");return0;}实验二：栈与队列实验目的：使学生深入了解栈与队列的特性，以便在实际背景下灵活运用他们，同时还将巩固这两种结构的构造方法。实验题目：1、检测表达式中{},[],()扩号匹配算法.2、检测字符串是否回文的算法算法参考答案：#include"stdio.h"#include"string.h"#include"malloc.h"#defineSTACK_INIT_SIZE30#defineSTACKINCREMENT10#defineOK1#defineERROR0#defineOVERFLOW-2typedefintStatus;typedefcharSElemType;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;//-----------初始化栈------------StatusInitStack(SqStack&S){//--------------压栈----------------StatusPush(SqStack&S,SElemTypee){}//------------------出栈------------------StatusPop(SqStack&S,SElemType*e){}//--------------取栈顶元素----------------StatusGetTop(SqStackS,SElemType*e){}//---------括号区配-----------------intpair(char*s){}//--------------回文-----------------------intIshuiwen(char*s){}//--------------主函数------------intmain(){}实验三二叉树与树实验目的:掌握二叉树的性质，二叉树的遍历，二叉树的线索化及构造赫夫曼树。二叉树上各种算法特别是递归算法的设计实验题目：1、用先序方法建立一棵二叉树.(二叉链表)算法.2、先，中，后序遍历二叉树算法算法参考答案://-------结构定义及宏定义------------#include"stdio.h"#include"malloc.h"typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;//-------建立二叉树---------------BiTreeCreateBiTree(){}//------先序遍历--------------voidPreOrder(BiTreeT){}//------中序遍历--------------voidInOrder(BiTreeT){}//------后序遍历--------------voidLastOrder(BiTreeT){}//-------主函数-------------intmain(){}实验四查找实验目的:掌握静态查找表,动态查找表,及哈希表查找.实验题目：折半查找算法.算法参考答案：-------------折半查找算法---------------intbinseach(inta[],intdata){}---------主函数-------------main(){//验证部分}实验五内部排序实验目的:掌握各种排序方法.实验题目：1.快速排序算法.2.堆排序算法.算法参考答案：1.堆排序算法.-------结构定义及宏定义------------------#include<stdio.h>#defineMAXSIZE20typedefstruct{intelemword[MAXSIZE];intlength;}SqList;voidInitialSqList();voidHeapSort();voidHeapAdjust();voidPrintSqList();------------初始化顺序表----------------voidInitialSqList(SqList*L){}-------------堆排序----------------voidHeapSort(SqList*L){}voidHeapAdjust(SqList*H,ints,intm){}---------输出顺序表------------voidPrintSqList(SqList*L){}--------------主函数--------main(){//验证部分}2.快速排序算法.-----------结构定义及宏定义------------#include<stdio.h>#defineMAXSIZE20typedefstruct{intelemword[MAXSIZE];intcount;}SqList;--------初始化顺序表--------------voidInitialSqList(SqList*L){}-----------