数据结构单链表实验报告实用文档

洛阳理工学院实验报告系别计算机系班级学号姓名课程名称数据结构实验日期11.7实验名称链表的基本操作成绩实验目的：熟悉掌握线性表链式存储结构，掌握与应用查找、插入、删除等基本操作算法，训练和提高结构化程序设计能力及程序调试能力。实验条件：计算机一台，VisualC++6.0实验内容：问题描述以单链表为存储结构实现以下基本操作：在第i个元素前插入一个新元素。查找值为x的某个元素。若成功，给出x在表中的位置；不成功给出提示信息。删除第i个元素，若成功，给出提示信息并显示被删元素的值；不成功给出失败的提示信息。数据结构类型定义typedefstructLinkNode{ intValue; structLinkNode*Next;}Node,*LinkList;模块划分（1）初始化链表：voidInitList(LinkList*L);（2）创建链表:尾插法：intCreateFromTail(LinkListL);（3）在指定位置插入元素：intInsList(LinkListL,inti,inte);（4）在指定位置删除元素：intDelList(LinkListL,inti,int*e);返回值说明：返回ERROR插入失败，返回OK插入成功;（5）按位置查找链表元素：intGetList(LinkListL,inti,int*e);详细设计voidinit_linklist(LinkList*l)/*对单链表进行初始化*/{ *l=(LinkList)malloc(sizeof(Node));/*申请结点空间*/ (*l)->next=NULL;/*置为空表*/}voidCreateFromHead(LinkListL){ Node*s; char c; int flag=1; while(flag)/*flag初值为1，当输入"$"时，置flag为0，建表结束*/ { c=getchar(); if(c!='$') { s=(Node*)malloc(sizeof(Node));/*建立新结点s*/ s->data=c; s->next=L->next;/*将s结点插入表头*/ L->next=s; } else flag=0; }}voidCreateFromTail(LinkListL){ Node*r,*s; charc; intflag=1;/*设置一个标志，初值为1，当输入"$"时，flag为0，建表结束*/ r=L;/*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/ while(flag)/*循环输入表中元素值，将建立新结点s插入表尾*/ { c=getchar(); if(c!='$') { s=(Node*)malloc(sizeof(Node)); s->data=c; r->next=s; r=s; } else { flag=0; r->next=NULL;/*将最后一个结点的next链域置为空，表示链表的结束*/ } }}Node*Get(LinkListL,inti)/*在带头结点的单链表L中查找第i个结点，若找到(1≤i≤n)，则返回该结点的存储位置;否则返回NULL*/{ intj; Node*p; p=L; j=0;/*从头结点开始扫描*/ while((p->next!=NULL)&&(j<i)) { p=p->next;/*扫描下一结点*/ j++;/*已扫描结点计数器*/ } if(i==j) returnp;/*找到了第i个结点*/ else returnNULL;/*找不到，i≤0或i>n*/}Node*Locate(LinkListL,ElemTypekey)/*在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL*/{ Node*p; p=L->next;/*从表中第一个结点开始*/ while(p!=NULL) { if(p->data!=key) p=p->next; else break;/*找到结点值=key时退出循环*/ } returnp;}intInsList(LinkListL,inti,ElemTypee)/*在带头结点的单链表L中第i个位置插入值为e的新结点s*/{ Node*pre,*s; intk; pre=L; k=0;/*从"头"开始，查找第i-1个结点*/ while(pre!=NULL&&k<i-1)/*表未查完且未查到第i-1个时重复，找到pre指向第i-1个*/ { pre=pre->next; k=k+1; } /*查找第i-1结点*/ if(!pre)/*如当前位置pre为空表已找完还未数到第i个，说明插入位置不合理*/ { printf("插入位置不合理!"); returnERROR; } s=(Node*)malloc(sizeof(Node));/*申请一个新的结点S*/ s->data=e;/*值e置入s的数据域*/ s->next=pre->next; /*修改指针，完成插入操作*/ pre->next=s; returnOK;}intDelList(LinkListL,inti,ElemType*e)/*在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中*/{ Node*pre,*r; intk; pre=L; k=0; while(pre->next!=NULL&&k<i-1) /*寻找被删除结点i的前驱结点i-1使p指向它*/ { pre=pre->next; k=k+1; } /*查找第i-1个结点*/ if(!(pre->next))/*即while循环是因为p->next=NULL或i<1而跳出的,而是因为没有找到合法的前驱位置，说明删除位置i不合法。*/ { printf("删除结点的位置i不合理!"); returnERROR; } r=pre->next; pre->next=pre->next->next;/*修改指针，删除结点r*/ *e=r->data; free(r);/*释放被删除的结点所占的内存空间*/ printf("成功删除结点!"); returnOK;}int ListLength(LinkListL)/*求带头结点的单链表L的长度*/{ Node*p; intj; p=L->next; j=0;/*用来存放单链表的长度*/ while(p!=NULL) { p=p->next; j++; } returnj; /*j为求得的单链表长度*/}5.测试数据及结果实验总结：在调试的时候发现在头插法的时候出现错误，经过逻辑思考与调试，发现错误所在，并且更改。实验一、单链表的插入和删除一、目的了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。二、要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。三、程序源代码#include"stdio.h"#include"string.h"#include"stdlib.h"#include"ctype.h"typedefstructnode//定义结点{chardata[10];//结点的数据域为字符串structnode*next;//结点的指针域}ListNode;typedefListNode*LinkList;//自定义LinkList单链表类型LinkListCreatListR1();//函数，用尾插入法建立带头结点的单链表ListNode*LocateNode();//函数，按值查找结点voidDeleteList();//函数，删除指定值的结点voidprintlist();//函数，打印链表中的所有值voidDeleteAll();//函数，删除所有结点，释放内存//==========主函数==============voidmain(){charch[10],num[10];LinkListhead;head=CreatListR1();//用尾插入法建立单链表，返回头指针printlist(head);//遍历链表输出其值printf("Deletenode(y/n):");//输入“y”或“n”去选择是否删除结点scanf("%s",num);if(strcmp(num,"y")==0||strcmp(num,"Y")==0){printf("PleaseinputDelete_data:");scanf("%s",ch);//输入要删除的字符串DeleteList(head,ch);printlist(head);}DeleteAll(head);//删除所有结点，释放内存}//==========用尾插入法建立带头结点的单链表===========LinkListCreatListR1(void){charch[10];LinkListhead=(LinkList)malloc(sizeof(ListNode));//生成头结点ListNode*s,*r,*pp;r=head;r->next=NULL;printf("Input#toend");//输入“#”代表输入结束printf("PleaseinputNode_data:");scanf("%s",ch);//输入各结点的字符串while(strcmp(ch,"#")!=0){pp=LocateNode(head,ch);//按值查找结点，返回结点指针if(pp==NULL){//没有重复的字符串，插入到链表中s=(ListNode*)malloc(sizeof(ListNode));strcpy(s->data,ch);r->next=s;r=s;r->next=NULL;}printf("Input#toend");printf("PleaseinputNode_data:");scanf("%s",ch);}returnhead;//返回头指针}//==========按值查找结点，找到则返回该结点的位置，否则返回NULL==========ListNode*LocateNode(LinkListhead,char*key){ListNode*p=head->next;//从开始结点比较while(p&&strcmp(p->data,key)!=0)//直到p为NULL或p->data为key止p=p->next;//扫描下一个结点returnp;//若p=NULL则查找失败，否则p指向找到的值key的结点}//==========删除带头结点的单链表中的指定结点=======voidDeleteList(LinkListhead,char*key){ListNode*p,*r,*q=head;p=LocateNode(head,key);//按key值查找结点的if(p==NULL){//若没有找到结点，退出printf("positionerror");exit(0);}while(q->next!=p)//p为要删除的结点，q为p的前结点q=q->next;r=q->next;q->next=r->next;free(r);//释放结点}//===========打印链表=======voidprintlist(LinkListhead){ListNode*p=head->next;//从开始结点打印while(p){printf("%s,",p->data);p=p->next;}printf("\n");}//==========删除所有结点，释放空间===========voidDeleteAll(LinkListhead){ListNode*p=head,*r;while(p->next){r=p->next;free(p);p=r;}free(p);}运行结果：加的添加结点的代码：intInsert(ListNode*head)//theinsertfunction{ListNode*in,*p,*q;intwh;printf("inputtheinsertnode:");in=(ListNode*)malloc(sizeof(ListNode));in->next=NULL;p=(ListNode*)malloc(sizeof(ListNode));p->next=NULL;q=(ListNode*)malloc(sizeof(ListNode));q->next=NULL;if(!in)return0;scanf("%s",in->data);printf("inputtheplacewhereyouwanttoinsertyoudata:");scanf("%d",&wh);for(p=head;wh>0;p=p->next,wh--);q=p->next;p->next=in;in->next=q;return1;}运行结果：最后提示为OK添加成功。实验心得：这个实验中主要修改的是ch和num把它们由指针改成数组因为不改的话在后面delect函数中会出现没有地址的情况找不到地址就不能执行功能然后把locate函数的判断语句改一下避免矛盾的出现。实验二、二叉树操作目的掌握二叉树的定义、性质及存储方式，各种遍历算法。要求采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。程序源代码#include"stdio.h"#include"string.h"#defineMax20//结点的最大个数typedefstructnode{chardata;structnode*lchild,*rchild;}BinTNode;//自定义二叉树的结点类型typedefBinTNode*BinTree;//定义二叉树的指针intNodeNum,leaf;//NodeNum为结点数，leaf为叶子数//==========基于先序遍历算法创建二叉树==============//=====要求输入先序序列，其中加入虚结点“#”以示空指针的位置==========BinTreeCreatBinTree(void){BinTreeT;charch;if((ch=getchar())=='#')return(NULL);//读入#，返回空指针else{T=(BinTNode*)malloc(sizeof(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){Inorder(T->lchild);//中序遍历左子树printf("%c",T->data);//访问结点Inorder(T->rchild);//中序遍历右子树}}//==========LRN后序遍历============voidPostorder(BinTreeT){if(T){Postorder(T->lchild);//后序遍历左子树Postorder(T->rchild);//后序遍历右子树printf("%c",T->data);//访问结点}}//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========intTreeDepth(BinTreeT){inthl,hr,max;if(T){hl=TreeDepth(T->lchild);//求左深度hr=TreeDepth(T->rchild);//求右深度max=hl>hr?hl:hr;//取左右深度的最大值NodeNum=NodeNum+1;//求结点数if(hl==0&&hr==0)leaf=leaf+1;//若左右深度为0，即为叶子。return(max+1);}elsereturn(0);}//====利用“先进先出”（FIFO）队列，按层次遍历二叉树==========voidLevelorder(BinTreeT){intfront=0,rear=1;BinTNode*cq[Max],*p;//定义结点的指针数组cqcq[1]=T;//根入队while(front!=rear){front=(front+1)%NodeNum;p=cq[front];//出队printf("%c",p->data);//出队，输出结点的值if(p->lchild!=NULL){rear=(rear+1)%NodeNum;cq[rear]=p->lchild;//左子树入队}if(p->rchild!=NULL){rear=(rear+1)%NodeNum;cq[rear]=p->rchild;//右子树入队}}}//==========主函数=================voidmain(){BinTreeroot;inti,depth;printf("\n");printf("CreatBin_Tree；Inputpreorder:");//输入完全二叉树的先序序列，//用#代表虚结点，如ABD###CE##F##root=CreatBinTree();//创建二叉树，返回根结点do{//从菜单中选择遍历方式，输入序号。printf("\t**********select************\n");printf("\t1:PreorderTraversal\n");printf("\t2:IorderTraversal\n");printf("\t3:Postordertraversal\n");printf("\t4:PostTreeDepth,Nodenumber,Leafnumber\n");printf("\t5:LevelDepth\n");//按层次遍历之前，先选择4，求出该树的结点数。printf("\t0:Exit\n");printf("\t*******************************\n");scanf("%d",&i);//输入菜单序号（0-5）switch(i){case1:printf("PrintBin_treePreorder:");Preorder(root);//先序遍历break;case2:printf("PrintBin_TreeInorder:");Inorder(root);//中序遍历break;case3:printf("PrintBin_TreePostorder:");Postorder(root);//后序遍历break;case4:depth=TreeDepth(root);//求树的深度及叶子数printf("BinTreeDepth=%dBinTreeNodenumber=%d",depth,NodeNum);printf("BinTreeLeafnumber=%d",leaf);break;case5:printf("LevePrintBin_Tree:");Levelorder(root);//按层次遍历break;default:exit(1);}printf("\n");}while(i!=0);}执行程序先序遍历中序遍历后序遍历结点数叶子数高度5..层次遍历自己设计的：abdhl##m##i##e#jn###cf#ko###g##1.预计先序遍历结果：abdhlmiejncfkog2.预计中序遍历结果：lhmdibenjafokcg3.预计后序遍历结果：lmhidnjebokfgca4.结点数15高度5叶子数6实际结果：实验心得：这次实验主要是要让我们熟练树及其相关知识熟练掌握先序中序后序遍历，层次遍历然后我们自己画一个图会实现以上功能以及叶子数结点数还有高度的计算程序里面大量运用了递归以及队的应用，实验三、图的遍历操作目的掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。要求采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。DFS和BFS的基本思想深度优先搜索法DFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后选择一个与Vo相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问，……依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。广度优先算法BFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后访问与Vo相邻的所有未被访问过的顶点V1，V2，……，Vt；再依次访问与V1，V2，……，Vt相邻的起且未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。程序源代码邻接矩阵作为存储结构的程序示例#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum100//定义最大顶点数typedefstruct{charvexs[MaxVertexNum];//顶点表intedges[MaxVertexNum][MaxVertexNum];//邻接矩阵，可看作边表intn,e;//图中的顶点数n和边数e}MGraph;//用邻接矩阵表示的图的类型//=========建立邻接矩阵=======voidCreatMGraph(MGraph*G){inti,j,k;chara;printf("InputVertexNum(n)andEdgesNum(e):");scanf("%d,%d",&G->n,&G->e);//输入顶点数和边数scanf("%c",&a);printf("InputVertexstring:");for(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,CreatAdjacencyMatrix\n");for(k=0;k<G->e;k++){//读入e条边，建立邻接矩阵scanf("%d%d",&i,&j);//输入边（Vi，Vj）的顶点序号G->edges[i][j]=1;G->edges[j][i]=1;//若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句}}//=========定义标志向量，为全局变量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度优先遍历的递归算法======voidDFSM(MGraph*G,inti){//以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵intj;printf("%c",G->vexs[i]);//访问顶点Vivisited[i]=TRUE;//置已访问标志for(j=0;j<G->n;j++)//依次搜索Vi的邻接点if(G->edges[i][j]==1&&!visited[j])DFSM(G,j);//（Vi，Vj）∈E，且Vj未访问过，故Vj为新出发点}voidDFS(MGraph*G){inti;for(i=0;i<G->n;i++)visited[i]=FALSE;//标志向量初始化for(i=0;i<G->n;i++)if(!visited[i])//Vi未访问过DFSM(G,i);//以Vi为源点开始DFS搜索}//===========BFS：广度优先遍历=======voidBFS(MGraph*G,intk){//以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;//队列初始化printf("%c",G->vexs[k]);//访问源点Vkvisited[k]=TRUE;cq[r]=k;//Vk已访问，将其入队。注意，实际上是将其序号入队while(cq[f]!=-1){//队非空则执行i=cq[f];f=f+1;//Vf出队for(j=0;j<G->n;j++)//依次Vi的邻接点Vjif(G->edges[i][j]==1&&!visited[j]){//Vj未访问printf("%c",G->vexs[j]);//访问Vjvisited[j]=TRUE;r=r+1;cq[r]=j;//访问过Vj入队}}}//==========main=====voidmain(){inti;MGraph*G;G=(MGraph*)malloc(sizeof(MGraph));//为图G申请内存空间CreatMGraph(G);//建立邻接矩阵printf("PrintGraphDFS:");DFS(G);//深度优先遍历printf("\n");printf("PrintGraphBFS:");BFS(G,3);//以序号为3的顶点开始广度优先遍历printf("\n");}调试结果：自己画的图：1对应顶点下标0以此类推9对应下标8预计运行结果：DFS:012345678BFS:324105687对应我这个图：DFS：123456789BFS：435216798实验心得：图在数据结构中是相当重要的一部分联系很多现实问题图的根本就是顶点和边通过顶点和边建立邻接矩阵以及邻接链表广度搜索和深度搜索是此算法着重关注的地方。要学会自己画图然后写出这两种搜索的结果，程序中用了队的算法是亮点通过TRUE和FAUSE来标记顶点是否以及访问避免重复实验四、排序目的掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。要求实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。程序示例#include"stdio.h"#include"stdlib.h"#defineMax100//假设文件长度typedefstruct{//定义记录类型intkey;//关键字项}RecType;typedefRecTypeSeqList[Max+1];//SeqList为顺序表，表中第0个元素作为哨兵intn;//顺序表实际的长度直接插入排序的基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已排序好的子文件中的适当位置，直到全部记录插入完成为止。//==========直接插入排序法======voidInsertSort(SeqListR){//对顺序表R中的记录R[1‥n]按递增序进行插入排序inti,j;for(i=2;i<=n;i++)//依次插入R[2]，……，R[n]if(R[i].key<R[i-1].key){//若R[i].key大于等于有序区中所有的keys，则R[i]留在原位R[0]=R[i];j=i-1;//R[0]是R[i]的副本do{//从右向左在有序区R[1‥i-1]中查找R[i]的位置R[j+1]=R[j];//将关键字大于R[i].key的记录后移j--;}while(R[0].key<R[j].key);//当R[i].key≥R[j].key是终止R[j+1]=R[0];//R[i]插入到正确的位置上}//endif}冒泡排序的基本思想：设想被排序的记录数组R[1‥n]垂直排序。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上“漂浮”（交换），如此反复进行，直到最后任意两个气泡都是轻者在上，重者在下为止。//==========冒泡排序=======typedefenum{FALSE,TRUE}Boolean;//FALSE为0，TRUE为1voidBubbleSort(SeqListR){//自下向上扫描对R做冒泡排序inti,j;Booleanexchange;//交换标志for(i=1;i<n;i++){//最多做n-1趟排序exchange=FALSE;//本趟排序开始前，交换标志应为假for(j=n-1;j>=i;j--)//对当前无序区R[i‥n]自下向上扫描if(R[j+1].key<R[j].key){//两两比较，满足条件交换记录R[0]=R[j+1];//R[0]不是哨兵，仅做暂存单元R[j+1]=R[j];R[j]=R[0];exchange=TRUE;//发生了交换，故将交换标志置为真}if(!exchange)//本趟排序未发生交换，提前终止算法return;}//endfor（为循环）}快速排序的基本思想：在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录作为支点（又称基准记录）（pivot），将所有关键字比它小的记录放置在它的位置之前，将所有关键字比它大的记录放置在它的位置之后(称之为一次划分过程)。之后对所分的两部分分别重复上述过程，直到每部分只有一个记录为止。//1.========一次划分函数=====intPartition(SeqListR,inti,intj){//对R[i‥j]做一次划分，并返回基准记录的位置RecTypepivot=R[i];//用第一个记录作为基准while(i<j){//从区间两端交替向中间扫描，直到i=jwhile(i<j&&R[j].key>=pivot.key)//基准记录pivot相当与在位置i上j--;//从右向左扫描，查找第一个关键字小于pivot.key的记录R[j]if(i<j)//若找到的R[j].key<pivot.key，则R[i++]=R[j];//交换R[i]和R[j]，交换后i指针加1while(i<j&&R[i].key<=pivot.key)//基准记录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}R[i]=pivot;//此时，i=j，基准记录已被最后定位returni;//返回基准记录的位置}//2.=====快速排序===========voidQuickSort(SeqListR,intlow,inthigh){//R[low..high]快速排序intpivotpos;//划分后基准记录的位置if(low<high){//仅当区间长度大于1时才排序pivotpos=Partition(R,low,high);//对R[low..high]做一次划分，得到基准记录的位置QuickSort(R,low,pivotpos-1);//对左区间递归排序QuickSort(R,pivotpos+1,high);//对右区间递归排序}}直接选择排序的基本思想：第i趟排序开始时，当前有序区和无序区分别为R[1‥i-1]和R[i‥n]（1≤i≤n-1），该趟排序则是从当前无序区中选择出关键字最小的记录R[k]，将它与无序区的的第一个记录R[i]交换，有序区增加一个记录，使R[1‥i],和R[i+1‥n]分别为新的有序区和新的无序区。如此反复进行，直到排序完毕。//======直接选择排序========voidSelectSort(SeqListR){inti,j,k;for(i=1;i<n;i++){//做第i趟排序（1≤i≤n-1）k=i;for(j=i+1;j<=n;j++)//在当前无序区R[i‥n]中选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}堆排序的基本思想：它是一种树型选择排序，特点是：在排序的过程中，将R[1‥n]看成是一个完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。即：把待排序文件的关键字存放在数组R[1‥n]子中，将R看成是一棵二叉树，每个结点表示一个记录，源文件的第一个记录R[1]作为二叉树的根，以下各记录R[2‥n]依次逐层从左到右排列，构成一棵完全二叉树，任意结点R[i]的左孩子是R[2i]，右孩子是R[2i+1]，双亲是R[i/2]。对这棵完全二叉树的结点进行调整，使各结点的关键字满足下列条件：R[i].key≤R[2i].key并且R[i].key≤R[2i+1].key称小堆根或R[i].key≥R[2i].key并且R[i].key≥R[2i+1].key称大堆根//==========大根堆调整函数=======voidHeapify(SeqListR,intlow,inthigh){//将R[low..high]调整为大根堆，除R[low]外，其余结点均满足堆性质intlarge;//large指向调整结点的左、右孩子结点中关键字较大者RecTypetemp=R[low];//暂存调整结点for(large=2*low;large<=high;large*=2){//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]的左右孩子结点中关键字较大者if(temp.key>=R[large].key)//temp始终对应R[low]break;//当前调整结点不小于其孩子结点的关键字，结束调整R[low]=R[large];//相当于交换了R[low]和R[large]low=large;//令low指向新的调整结点，相当于temp已筛下到large的位置}R[low]=temp;//将被调整结点放入最终位置上}//==========构造大根堆==========voidBuildHeap(SeqListR){//将初始文件R[1..n]构造为堆inti;for(i=n/2;i>0;i--)Heapify(R,i,n);//将R[i..n]调整为大根堆}//==========堆排序===========voidHeapSort(SeqListR){//对R[1..n]进行堆排序，不妨用R[0]做暂存单元inti;BuildHeap(R);//将R[1..n]构造为初始大根堆for(i=n;i>1;i--){//对当前无序区R[1..i]进行堆排序，共做n-1趟。R[0]=R[1];R[1]=R[i];R[i]=R[0];//将堆顶和堆中最后一个记录交换Heapify(R,1,i-1);//将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质。}}二路归并排序的基本思想：假设初始序列n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列；再两两归并，……，如此重复，直到一个长度为n的有序序列为止。//=====将两个有序的子序列R[low..m]和R[m+1..high]归并成有序的序列R[low..high]==voidMerge(SeqListR,intlow,intm,inthigh){inti=low,j=m+1,p=0;//置初始值RecType*R1;//R1为局部量R1=(RecType*)malloc((high-low+1)*sizeof(RecType));//申请空间while(i<=m&&j<=high)//两个子序列非空时取其小者输出到R1[p]上R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++];while(i<=m)//若第一个子序列非空，则复制剩余记录到R1R1[p++]=R[i++];while(j<=high)//若第二个子序列非空，则复制剩余记录到R1中R1[p++]=R[j++];for(p=0,i=low;i<=high;p++,i++)R[i]=R1[p];//归并完成后将结果复制回R[low..high]}//=========对R[1..n]做一趟归并排序========voidMergePass(SeqListR,intlength){inti;for(i=1;i+2*length-1<=n;i=i+2*length)Merge(R,i,i+length-1,i+2*length-1);//归并长度为length的两个相邻的子序列if(i+length-1<n)//尚有一个子序列，其中后一个长度小于lengthMerge(R,i,i+length-1,n);//归并最后两个子序列//注意：若i≤n且i+length-1≥n时，则剩余一个子序列轮空，无须归并}//==========自底向上对R[1..n]做二路归并排序===============voidMergeSort(SeqListR){intlength;for(length=1;length<n;length*=2)//做[lgn]趟排序MergePass(R,length);//有序长度≥n时终止}//==========输入顺序表========voidinput_int(SeqListR){inti;printf("Pleaseinputnum(int):");scanf("%d",&n);printf("Plaseinput%dinteger:",n);for(i=1;i<=n;i++)scanf("%d",&R[i].key);}//==========输出顺序表========voidoutput_int(SeqListR){inti;for(i=1;i<=n;i++)printf("%4d",R[i].key);}//==========主函数======voidmain(){inti;SeqListR;input_int(R);printf("\t********Select**********\n");printf("\t1:InsertSort\n");printf("\t2:BubbleSort\n");printf("\t3:QuickSort\n");printf("\t4:StraightSelectionSort\n");printf("\t5:HeapSort\n");printf("\t6:MergeSort\n");printf("\t7:Exit\n");printf("\t***************************\n");scanf("%d",&i);//输入整数1-7，选择排序方式switch(i){case1:InsertSort(R);break;//值为1，直接插入排序case2:BubbleSort(R);break;//值为2，冒泡法排序case3:QuickSort(R,1,n);break;//值为3，快速排序case4:SelectSort(R);break;//值为4，直接选择排序case5:HeapSort(R);break;//值为5，堆排序case6:MergeSort(R);break;//值为6，归并排序case7:exit(0);//值为7，结束程序}printf("Sortreult:");output_int(R);}运行结果：直接插入排序：冒泡法排序：快速排序：直接选择排序：堆排序：归并排序：实验心得：关于排序的数据结构实验。感觉各种排序方法都有各自的特点。直接插入排序是根据前面一个数的位置和后面一个相比较直接排而冒泡法则要经过n*(n-1)次每次确定一个数的位置但是这种方法有点复杂要循环n次，而快速排序则是从中间到两边任选一个数出来把小的排前面大的排后面然后重复以上过程这样可以有效地节约时间每一步都为下一步节约了时间。而直接选择排序有两个序列也是每一步都为下一步节约了世界堆排序巧妙地利用了树中双亲与孩子的关系归并排序则是发散的通过递归成2的n次方排，通过这几种排序方法我更加了解了排序也知道了许多数据结构。目录TOC\o"1-3"\h\u166971选题背景2232202方案与论证3258412.1链表的概念和作用3265912.3算法的设计思想4187062.4相关图例5150312.4.1单链表的结点结构5277712.4.2算法流程图5122303实验结果6220343.1链表的建立6258113.2单链表的插入6320213.3单链表的输出7190563.4查找元素7135493.5单链表的删除8325073.6显示链表中的元素个数（计数）9165624结果分析1098784.1单链表的结构1050594.2单链表的操作特点10204464.2.1顺链操作技术10123154.2.2指针保留技术10131654.3链表处理中的相关技术10226005设计体会及今后的改进意见1119571参考文献1214900附录代码：131选题背景陈火旺院士把计算机60多年的发展成就概括为五个“一”：开辟一个新时代信息时代，形成一个新产业信息产业，产生一个新科学计算机科学与技术，开创一种新的科研方法计算方法，开辟一种新文化计算机文化，这一概括深刻影响了计算机对社会发展所产生的广泛而深远的影响。数据结构和算法是计算机求解问题过程的两大基石。著名的计算机科学家P.Wegner指出，“在工业革命中其核心作用的是能量，而在计算机革命中其核心作用的是信息”。计算机科学就是“一种关于信息结构转换的科学”。信息结构（数据结构）是计算机科学研究的基本课题，数据结构又是算法研究的基础。2方案与论证2.1链表的概念和作用链表是一种链式存储结构，链表属于线性表，采用链式存储结构，也是常用的动态存储方法。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象)+

指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性链表（单链表）单链表是链式存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素。因此，查找第i个数据元素的基本操作为：移动指针，比较j和i单链表1、链接存储方法链接方式存储的线性表简称为链表（LinkedList）。链表的具体存储表示为：①用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）②链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）注意：链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。2、链表的结点结构┌───┬───┐│data│next│└───┴───┘data域--存放结点值的数据域next域--存放结点的直接后继的地址（位置）的指针域（链域）注意：①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。②每个结点只有一个链域的链表称为单链表（SingleLinkedList）。3、头指针head和终端结点指针域的表示单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。注意：链表由头指针唯一确定，单链表可以用头指针的名字来命名。终端结点无后继，故终端结点的指针域为空，即NULL。2.2实验的基本要求（软硬件）用VC++6.0软件平台，操作系统：WindowsXP硬件：内存要求：内存大小在256MB，其他配置一般就行。2.3算法的设计思想（a）定义一个创建链表的函数，通过该头插法创建一个带头结点的链表，在接下来的链表操作中使用。（b）定义输出链表的算法，遍历结点的指针域判断是否为空，如果不为空则输出其数据域，直到指针域为空为止。（c）定义一个遍历查找的算法，通过遍历的数据域，分别与要查询的元素进行比较，如果查找到则返回并输出，如入查找失败则返回错误提示信息。（d）定义插入结点的算法，首先查找指针域为空的结点，并申请空间插入在结点的后边，并且将其指针域置空。（e）定义删除节点的操作，这个算法用于对链表中某个多余节点的删除工作，其关键在于前驱结点的保留，查找到需删除的结点，将其删除，并将其后继结点连到其前驱结点。2.4相关图例2.4.1单链表的结点结构如图2-1所示,为单链表的结点结构示意图：Data域Next域Data域Next域图2-1单链表的结点结构2.4.2算法流程图如图2-2所示，为此算法流程图：开始开始定义结构体Node定义结构体Node构建各种对链表操作的函数（插入、删除、查找、输出），并写出相应的算法及实现过程创建一个单链表，用于之前所定义的函数对其进行操作按要求输出结果结束图2-2算法流程图3实验结果3.1链表的建立图3-1链表的建立3.2单链表的插入图3-2单链表的插入3.3单链表的输出图3-3输出单链表元素3.4查找元素图3-4查找成功图3-5查找失败3.5单链表的删除图3-6删除成功图3-6删除失败3.6显示链表中的元素个数（计数）图3-7输出长度4结果分析4.1单链表的结构一般情况下，使用链表，只关心链表中结点间的逻辑顺序，并不关心每个结点的实际存储位置，因此通常情况下用箭头来表示链域中的指针，于是链表就可以更直观的画成用箭头链接起来的结点序列，如下图所示：ABABCDE^H图4-1单链表的示例图4.2单链表的操作特点4.2.1顺链操作技术从“头”开始，访问单链表L中的结点i（p指向该节点）时，由于第i个结点的地址在第i-1个结点（pre指向该结点，为p的前驱）的指针域中存放，查找必须从单链表的“首结点”开始（p=L）；通过p=p->next并辅助计数器来实现。4.2.2指针保留技术通过对第i个结点进行插入、删除等操作时，需要对第i-1个结点的指针域进行链址操作（pre->next），因此在处理过程中始终需要维持当前指针p与其前驱指针pre的关系，将这种技术称为“指针保留技术”。4.3链表处理中的相关技术1）单链表与多重链表的差别在于指针域的个数。2）判断当前结点p是否为表尾。一半链表中，p结点是表尾的条件是：该节点的后继结点为空指针，即p->next==NULL;3）链表的长度并未显示保存。由于链表是动态生成的结构，其长度要通过顺链查找到表尾得到。因此在处理链表时，往往是以当前处理结点p是否为表尾作为控制条件，而不是长度n作为控制条件。5设计体会及今后的改进意见通过这次实验加深了我对于单链表的进一步了解，了解到了单链表在内存中的存储结构，最重要的是学会了如何运用C语言将单链表的建立，插入、删除、添加等操作。在程序实现中也遇到了一些困难，在单链表初始化时，使用了0作为结束输入符，导致单链表不能存储数据0；单链表中只能存储相同类型的数据，在存储不同类型的数据时需要改变输入结束标志，程序通用性比较差。在进行程序设计的时候没有考虑好删除和查找的方式，只进行了输入元素的查找和删除，而且进行链表的插入时，只考虑了头插法在结尾插入，而没有考虑输入结点插入等，程序的灵活性比较低。通过这次课程设计，让我充分认识到数据结构在编写程序方面的重要地位。不仅仅是单链表的操作，还有栈和队列等特殊的单链表操作，以及其他一些常用的数据结构对于程序的效率和内存使用有很大的帮助。我希望在接下来的学习中收获更多的东西。参考文献[1]耿国华.数据结构--用C语言描述[M].北京:高等教育出版社,2021.6.[2]谭浩强.C程序设计[M].北京:清华大学出版社,2004.6.附录代码：结构体定义：#pragmaonce#include<stdio.h>#include<stdlib.h>enummy_enum{_EXIT,_CREATE,_INSERT,_PRINT,_SEARCH,_DELETE,_COUNT,};staticintcount=0;typedefintElemtype;typedefstructNode/*单链表结构体的定义*/{Elemtypedata;structNode*next;}Node,*LinkList;voidtest();/*测试函数*/voidmain_menu();//主菜单函数voidCreatFromHead(LinkList*l);/*头插法建立单链表*/voidInsert(LinkListl);//单链表的插入voidPrint(LinkListl);/*单链表的输出*/intSearch(LinkListl,Elemtypee);//查找指定的元素voidDeletelist(Lin