单链表的插入和删除实验报告

实验一、单链表的插入和删除一、目的了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。二、要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点,后删除之.三、程序源代码#include”stdio.h"#include"string。h"＃include”stdlib。h"＃include"ctype。h”typedefstructnode｛chardata［10]；串//结点的数据域为字符//结点的指针域structnode＊next;｝ListNode；typedefListNode*//自定义LinkList单链表类型LinkListCreatListR1(）;带头结点的单链表//函数,用尾插入法建立数据结构实验报告ListNode*LocateNode（)；void点//函数，按值查找结点//函数，删除指定值的结void值//函数,打印链表中的所有void//==========主函数==============voidmain()//函数,删除所有结点,释放内存{charch[10]，num［10］;LinkListhead=CreatListR1()；printlist（head);//遍历链表输出其值printf("Deletenode(y/n）:");//输入“y”或“n”去选择是否删除结点if（strcmp（num，"y”)==0|｜printf（"PleaseinputDelete_data:");scanf("％s",ch)；printlist(head)；//输入要删除的字符串}2数据结构实验报告//删除所有结点，释放内存｝//==========用尾插入法建立带头结点的单链表===========LinkListCreatListR1（void）{charLinkList//生成头结点ListNode＊s,*r，*pp;r=head;r—>next=NULL;printf("Input＃toend//输入“#”代表输入结束printf（”PleaseinputNode_data:");//输入各结点的字符串｛//按值查找结点，返回结点指针中｛//没有重复的字符串，插入到链表s=（ListNode*)malloc（sizeof(ListNode）)；strcpy(s-〉data,ch)；r—〉next=s;3数据结构实验报告r=s;r-〉next=NULL；}printf（”Input＃toendprintf（"Pleaseinputscanf（"％s",ch);｝return//返回头指针}//==========按值查找结点，找到则返回该结点的位置,否则返回NULL==========ListNode*LocateNode(LinkListhead,char＊key)｛ListNode＊p=head—〉next;//从开始结点比较）//直到p为NULL或p->data为key止p=p—〉next；returnp;//扫描下一个结点p=NULL则查找失败，否则p指向找到的值key的结点}//==========删除带头结点的单链表中的指定结点=======voidDeleteList（LinkListhead，char*key)4数据结构实验报告｛ListNode*p,*r,*q=head；p=LocateNode(head,key)；if（p==NULL){key值查找结点的//若没有找到结点，退出printf（”positionexit(0)；}//p为p的前结点q=q—〉next；r=q—>next；q->next=r—〉next；//释放结点｝//===========打印链表=======voidprintlist(LinkList｛ListNode＊p=head->next；while(p){//从开始结点打印printf（"％s,p=p—>next；｝5数据结构实验报告｝//==========删除所有结点，释放空间===========voidDeleteAll（LinkListhead){ListNode*p=head，*r;r=p-〉next;free（p);p=r;｝free（p);｝运行结果:加的添加结点的代码：intInsert(ListNode*head)//theinsertfunction｛ListNode＊in，*q;intwh;printf(”inputtheinsertnode:”in=（ListNode（sizeof（ListNodein-next=NULL;p=（ListNodemalloc(sizeof（ListNode);p->next=NULL；6数据结构实验报告q=(ListNode）mallocsizeof（ListNodeq-next=NULL;if（!in)return0;scanf(”%s",in->dataprintf（”inputtheplacewhereyouwanttoinsertyou；scanf(”%d”，＆）;forp=head；wh>0;p=p->next，——）;q=p->next；p—>next=in;in->next=q;return1；｝运行结果：最后提示为OK添加成功。实验心得:这个实验中主要修改的是ch和num把它们由指针改成数组因为不改的话在后面delect函数中会出现没有地址的情况找不到地址就不能执行功能然后把locate函数的判断语句改一下避免矛盾的出现。实验二、二叉树操作一、目的掌握二叉树的定义、性质及存储方式各种遍历算法。7数据结构实验报告二、要求采用二叉树链表作为存储结构完成二叉树的建立序以及按层次遍历的操作，求所有叶子及结点总数的操作.三、程序源代码＃include"stdio。h"#include”string.h”#defineMax20typedefstructchar//结点的最大个数structnode＊lchild,*rchild；｝BinTNode；//自定义二叉树的结点类型typedefBinTNode*BinTree;intNodeNum，leaf；//定义二叉树的指针//NodeNum为结点数，leaf为叶子数//==========基于先序遍历算法创建二叉树==============//=====要求输入先序序列，其中加入虚结点“＃”以示空指针的位置==========BinTreeCreatBinTree（void）｛BinTreecharif((ch=getchar(）)==’＃’)return（NULL）;//读入＃，返回空指针8数据结构实验报告else{T=（BinTNode//生成结点T—>data=ch;T->lchild=CreatBinTree();T—>rchild=CreatBinTree(）;return(T)；//构造右子树}}//========NLR先序遍历=============voidPreorder（BinTreeT){if(T）{printf（”％c",T-〉data);//访问结点Preorder(T-〉lchild);//先序遍历左子树Preorder(T—>rchild);//先序遍历右子树}}//========LNR中序遍历===============voidInorder(BinTreeT){if(T）｛9数据结构实验报告Inorder(T->lchild)；//中序遍历左子树//访问结点Inorder（T->rchild)；//中序遍历右子树}}//==========LRN后序遍历============voidPostorder(BinTree{if（T）{Postorder（T-〉lchild)；//后序遍历左子树//后序遍历右子树//访问结点}｝//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========intTreeDepth（BinTree{inthl,hr，max;if（T)｛hl=TreeDepth(T—〉lchild）;hr=TreeDepth（T->rchild）;//求左深度//求右深度10数据结构实验报告max=hl〉hr?hl：hr;NodeNum=NodeNum+1；//取左右深度的最大值//求结点数if(hl==0&＆hr==0）leaf=leaf+1;//若左右深度为}elsereturn(0）;}voidLevelorder（BinTreeT){intfront=0，rear=1;BinTNode//定义结点的指针数组cqcq［1]=T;while（front!=rear)｛front=（front+1)％NodeNum;p=cq［front］;if（p-〉lchild!=NULL）{//出队,输出结点的值rear=（rear+1)％NodeNum；cq［rear］=p->lchild;//左子树入队}11数据结构实验报告rear=（rear+1)%NodeNum；cq[rear]=p—>rchild;//右子树入队}}}//==========主函数=================voidmain(）{BinTreeroot;inti，depth;printf(”\n"）;printf（"CreatBin_Tree；Inputpreorder：");//输入完全二叉树的先序序列，//用#代表虚结点,如ABD＃＃＃CE＃＃F##root=CreatBinTree（)；//创建二叉树，返回根结点//从菜单中选择遍历方式，输入序号.do｛select＊*＊*＊＊＊*＊＊＊＊\n")；printf(”\t1：PreorderTraversal\n");printf（"\t2:IorderTraversal\n"）;12数据结构实验报告printf("\t3：Postorderprintf（"\t4:PostTreeDepth,Nodenumber，Leafnumber\n")；printf（”\t5:LevelDepth\n”)；//按层次遍历之前,先选择4,求出该树的结点数。printf（"\t0:Exit\n")；printf（"\t＊**＊***＊＊＊******＊＊＊＊****＊＊**＊**\n”);scanf（"％d”,&i）;switch//输入菜单序号（0—5)case1:printf（”PrintBin_treePreorder:"Preorder（root)；break；//先序遍历case2：printf（"PrintBin_TreeInorder:");break;//中序遍历case3:printf(”PrintBin_Treebreak；//后序遍历case4：depth=TreeDepth(root)；叶子数//求树的深度及printf（”BinTreeBinTreeNode13数据结构实验报告printf（”BinTreeLeafbreak；case5:printf("LevePrintBin_Tree://按层次遍历break;default:｝printf（"\n”);｝while（i！=0)；｝执行程序1.先序遍历2.中序遍历3.后序遍历4.结点数叶子数高度5..层次遍历自己设计的：abdhl＃#i##e#jn#cf＃kog#＃1.预计先序遍历结果：abdhlmiejncfkog2。预计中序遍历结果：lhmdibenjafokcg3。预计后序遍历结果:lmhidnjebokfgca14数据结构实验报告4.结点数15高度5叶子数6实际结果:实验心得：这次实验主要是要让我们熟练树及其相关知识熟练掌握然后我们自己画一个图会实现以上功能以及叶子数结点数还有高度的计算程序里面大量运用了递归以及队的应用，实验三、图的遍历操作一、目的掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用.二、要求采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。三、DFS和BFS的基本思想深度优先搜索法DFSG中某个顶点出发，首先访问相邻且没被访问过的顶点Vi,再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点，从W出发按同样方法向前遍历。直到图中所有的顶15数据结构实验报告点都被访问。广度优先算法BFS的基本思想：从图G中某个顶点,首先访问然后访问与相邻的所有未被访问过的顶点V1，V2，……；再依次访问与V1，，……，Vt相邻的起且未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。四、程序源代码．邻接矩阵作为存储结构的程序示例＃include"stdio。h"＃include"stdlib.h”＃defineMaxVertexNum100typedefcharvexs［MaxVertexNum];intedges[MaxVertexNum][MaxVertexNum];//邻接矩阵，可看作边表int｝MGraph;//图中的顶点数n和边数e//用邻接矩阵表示的图的类型//=========建立邻接矩阵=======voidCreatMGraph(MGraph*G){inti，j,k；chara;printf(”InputVertexNum（n）andEdgesNum（e）:16数据结构实验报告//输入顶点数和边数scanf（”％c",&a)；printf（"InputVertexfor（i=0；i〈G-〉n;i++）｛scanf("%c",&a)；G—〉vexs[i]=a;//读入顶点信息,建立顶点表}for(i=0;i〈G->n;i++)for（j=0；j〈G—〉n；j++）G—〉edges［i][j］=0;//初始化邻接矩阵printf(”Inputedges,CreatAdjacencyfor（k=0；k<G-〉e；k++）｛//读入e条边，建立邻接矩阵序号G—>edges[i]［j］=1；//若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句｝｝17数据结构实验报告//=========定义标志向量，为全局变量=======typedefenum｛FALSE，TRUE｝Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度优先遍历的递归算法======voidDFSM(MGraph＊G，int{//以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵int//访问顶点Vivisited[i］=TRUE；//置已访问标志for(j=0；j<G—〉n；j++）//依次搜索Vi的邻接点！visited[j］)DFSM(G,j);故Vj为新出发点}Vj未访问过，voidDFS(MGraph＊G）｛intfor（i=0；i<G->n；i++)visited［i]=FALSE；for(i=0；i<G—〉n;i++）if(！visited［i])//标志向量初始化//Vi未访问过18数据结构实验报告DFSM(G,i)；Vi为源点开始DFS搜索}//===========BFS:广度优先遍历=======voidBFS(MGraph＊G，int｛Vk为源点对用邻接矩阵表示的图G进行广度优先搜索inti，j,f=0,r=0；intcq[MaxVertexNum]；for（i=0;i<G-〉n;i++)visited[i]=FALSE；//定义队列//标志向量初始化for(i=0；i<G—〉n；i++)cq［i］=-1；//访问源点Vkprintf(”%c",G—〉vexs［k]）;visited[k］=TRUE;cq［r］=k;//Vk已访问，将其入队。注意，实际上是将其序号入队while（cq［f]！=—1){i=cq[f］;f=f+1；for（j=0;j〈G->n；j++)//队非空则执行//Vf出队Vi的邻接点Vj&&｛//Vj未访问Vj19数据结构实验报告visited［j］=TRUE；r=r+1;//访问过Vj入队}}}//==========main=====voidmain()｛inti;MGraph＊G；G=(MGraph//为图G申请内存空间CreatMGraph（G）;printf（"PrintGraphDFS://建立邻接矩阵DFS(G)；//深度优先遍历printf（"PrintGraphBFS(G,3）;//以序号为3的顶点开始广度优先遍历｝printf（"\n"）;调试结果：20数据结构实验报告自己画的图：1对应顶点下标0以此类推9对应下标8预计运行结果：DFS:012345678BFS:324105687对应我这个图：DFS：123456789BFS：435216798实验心得:图在数据结构中是相当重要的一部分联系很多现实问题图的根本就是顶点和边通过顶点和边建立邻接矩阵以及邻接链表广度搜索和深度搜索是此算法着重关注的地方。要学会自己画图然是亮点通过TRUE和FAUSE来标记顶点是否以及访问避免重复实验四、排序一、目的掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析,根据实际问题的特点和要求选择合适的排序方法。二、要求实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度.21数据结构实验报告三、程序示例＃include"stdio。h"#include”stdlib。h"＃defineMax100typedefintkey;//定义记录类型}RecType；typedefRecType//SeqList为顺序表，表中第0个元素作为哨兵intn;//顺序表实际的长度、直接插入排序的基本思想:每次将一个待排序的记录，按其关键字大小插入到前面已排序好的子文件中的适当位置，直到全部记录插入完成为止。//==========直接插入排序法======voidInsertSort（SeqList｛//对顺序表R中的记录R[1‥n］按递增序进行插入排序inti,j;for（i=2;i〈=n；i++)//依次插入R[2］,……，R[n］R[i］.key大于等于有序区中所有的keys，则R[i]留在原位R［0]=R［i]；j=i—1;do｛//R［0]是R［i］的副本//从右向左在有序区22数据结构实验报告找R[i］的位置//将关键字大于的记录后移j——;//当是终止//R[i］插入到正确的位置上｝//endif}2、R[1‥n]垂直排止。//==========冒泡排序=======typedefenum｛FALSE，TRUE}Boolean;//FALSE为0,TRUE为1voidBubbleSort(SeqListR)｛//自下向上扫描对R做冒泡排序inti，j；Booleanexchange；//交换标志for(i=1;i〈n；i++){n-1趟排序23数据结构实验报告exchange=FALSE；//本趟排序开始前，交换标志应为假//对当前无序区R[i‥n］自下向上扫描//两两比较，满足条件交换记录元R［j]=R[0］;exchange=TRUE；//本趟排序未发生交换，提前终止真｝if(!exchange）算法return;endfor（为循环）}、快速排序的基本思想：在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录作为支点（又称基准记录)（pivot有关键字比它大的记录放置在它的位置之后（称之为一次划分过程）之后对所分的两部分分别重复上述过程，直到每部分只有一24数据结构实验报告个记录为止。//1。========一次划分函数=====intPartition（SeqListi,intj)｛//对R[i‥j］做一次划分，并返回基准记录的位置RecTypewhile(i〈j）{//用第一个记录作为基准//从区间两端交替向中间扫描，直到i=jwhile(i<j//基准记录pivot相当与在位置i上j-—;pivot。key的记录R[j]//从右向左扫描，查找第一个关键字小于if（i〈j)//若找到的R［j]。key〈pivot。key，则R［i++］=R[j］;//交换R[i]和i指针加1录pivot相当与在位置j上//基准记i++；//从左向右扫描,查找第一个关键字小于pivot。key的记录R［i］if（i<j）//若找到的R[i］.key>pivot.key，则R[j——］=R[i];//交换R[i］和R［j]，交换后j指针减1｝25数据结构实验报告R［i]=pivot;return//此时，i=j，基准记录已被最后定位//返回基准记录的位置}//2.=====快速排序===========voidQuickSort（SeqListlow，inthigh）｛//划分后基准记录的位置//仅当区间长度大于1时才排序intif(low<high）{R［low..high］做一次划分，得到基准记录的位置QuickSort(R，low，pivotpos-1);//对左区间递归排序//对右区间递归排序QuickSort（R，pivotpos+1,high);}}、i趟排序开始时当前有序区和无序区分别为R[1‥i—1］和1）,该趟排序则是从当前无序区中选择出关键字最小的记录的的第一个记录和R［i+1‥n］分别为新的有序区和新的无序区。如此反复进行，直到排序完毕。//======直接选择排序========voidSelectSort(SeqListR)26数据结构实验报告｛inti,j,k;for(i=1;i〈n；i++）{k=i；i趟排序（1≤i≤n1）//在当前无序区key最小的记录R[k］if(R［j]。key<R[k].key)k=j;//k记下目前找到的最小关键字所在的位置if（k!=i)｛//R[i］和R［k]R［0]=R[i]；R［i］=R［k］;R［k］=R［0];}//endif｝//endfor｝、的过程中，将‥］看成是一个完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录.:把待排序文件的关键字存放在数组［1n］子中，将R看成是一棵二叉树，每个结点表示一个记录源文件的第一个记录R［1］作为二叉树的根,以下各记录R［2‥n］依次逐层从左到右排列，构成一棵完全二叉树，任意结点［的左孩子是R2i］右孩子是R[2i+1]，双27数据结构实验报告亲是R[i/2字满足下列条件：［i并且［称小堆根或［并且称大堆根//==========大根堆调整函数=======voidHeapify（SeqListR，intlow,inthigh)｛//将均满足堆性质intlarge;//large指向调整结点的左、右孩子结点中关键字较大者RecTypetemp=R[low］;//暂存调整结点for（large=2*low;//R[low]是当前调整结点large〉high,则表示R［low]是叶子，调整结束;否则先令large指向R[low］的左孩子if(large<high&&R[large].key〈R[large+1]。key)large++；//若R［low］的右孩子存在且关键字大于左兄弟，则令large指向它//现在R[large］是调整结点R［low]的左右孩子结点中关键字较大者28数据结构实验报告//temp始终对应break;束调整//相当于交换了low=large；//令lowtemp已筛下到large的位置｝R[low]=temp；//将被调整结点放入最终位置上}//==========构造大根堆==========voidBuildHeap(SeqList{//将初始文件R[1.。n］构造为堆intfor（i=n/2;i〉0；i--)//将R［i。.n]调整为大根堆}//==========堆排序===========voidHeapSort(SeqListR)｛元intBuildHeap(R);R[1.。n］构造为初始大根堆29数据结构实验报告排序，共做n-1趟。//对当前无序区R[0］=R[1]；R[1］=R[i］;R[i］=R[0];中最后一个记录交换//将1]重新调整为堆，仅有R[1］可能违反堆性质。//将堆顶和堆｝｝、n是n个有序的子序列，每个子序列的长度为1，然后两两归并,得2或1的有序子序列;再两两归并,……,如此重复,直到一个长度为n的有序序列为止。//=====将两个有序的子序列R[m+1.。high］归并成有序的序列R［low。.high］==voidMerge(SeqListlow,inthigh）{inti=low，j=m+1，p=0;//置初始值RecType*R1;//R1为局部量R1=(RecType//申请空间＆＆j<=high）者输出到R1［p］上//两个子序列非空时取其小30数据结构实验报告R1［p++］=（R［i].key<=R[j].key)?R［i++］:R[j++]；while(i<=m)//若第一个子序列非空，则复制剩余记录到R1R1[p++]=R[i++]；到R1中for（p=0,i=low；i<=high;p++,i++）R[i]=R1[p];//归并完成后将结果复制回｝//=========对R［1。.n］做一趟归并排序========voidMergePass（SeqListR,intlength){intfor（i=1；i+2＊length—1<=n;i=i+2＊length）//归并长度为length的两个相邻的子序列//尚有一个子序列，其中后一