單鏈表的插入和刪除實(shí)驗(yàn)報(bào)告優(yōu)質(zhì)資料(可以直接使用，可編輯優(yōu)質(zhì)資料，歡迎下載）

單鏈表的插入和刪除實(shí)驗(yàn)報(bào)告優(yōu)質(zhì)資料(可以直接使用，可編輯優(yōu)質(zhì)資料，歡迎下載）實(shí)驗(yàn)一、單鏈表的插入和刪除一、目的了解和掌握線性表的邏輯結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，掌握單鏈表的基本算法及相關(guān)的時間性能分析。二、要求：建立一個數(shù)據(jù)域定義為字符串的單鏈表，在鏈表中不允許有重復(fù)的字符串；根據(jù)輸入的字符串，先找到相應(yīng)的結(jié)點(diǎn)，后刪除之。三、程序源代碼#include"stdio.h"#include"string.h"#include"stdlib.h"#include"ctype.h"typedefstructnode//定義結(jié)點(diǎn){chardata[10];//結(jié)點(diǎn)的數(shù)據(jù)域?yàn)樽址畇tructnode*next;//結(jié)點(diǎn)的指針域}ListNode;typedefListNode*LinkList;//自定義LinkList單鏈表類型LinkListCreatListR1();//函數(shù)，用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表ListNode*LocateNode();//函數(shù)，按值查找結(jié)點(diǎn)voidDeleteList();//函數(shù)，刪除指定值的結(jié)點(diǎn)voidprintlist();//函數(shù)，打印鏈表中的所有值voidDeleteAll();//函數(shù)，刪除所有結(jié)點(diǎn)，釋放內(nèi)存//==========主函數(shù)==============voidmain(){charch[10],num[10];LinkListhead;head=CreatListR1();//用尾插入法建立單鏈表，返回頭指針printlist(head);//遍歷鏈表輸出其值printf("Deletenode(y/n):");//輸入“y”或“n”去選擇是否刪除結(jié)點(diǎ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);//刪除所有結(jié)點(diǎn)，釋放內(nèi)存}//==========用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表===========LinkListCreatListR1(void){charch[10];LinkListhead=(LinkList)malloc(sizeof(ListNode));//生成頭結(jié)點(diǎn)ListNode*s,*r,*pp;r=head;r->next=NULL;printf("Input#toend");//輸入“#”代表輸入結(jié)束printf("PleaseinputNode_data:");scanf("%s",ch);//輸入各結(jié)點(diǎn)的字符串while(strcmp(ch,"#")!=0){pp=LocateNode(head,ch);//按值查找結(jié)點(diǎn)，返回結(jié)點(diǎn)指針if(pp==NULL){//沒有重復(fù)的字符串，插入到鏈表中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;//返回頭指針}//==========按值查找結(jié)點(diǎn)，找到則返回該結(jié)點(diǎn)的位置，否則返回NULL==========ListNode*LocateNode(LinkListhead,char*key){ListNode*p=head->next;//從開始結(jié)點(diǎn)比較while(p&&strcmp(p->data,key)!=0)//直到p為NULL或p->data為key止p=p->next;//掃描下一個結(jié)點(diǎn)returnp;//若p=NULL則查找失敗，否則p指向找到的值key的結(jié)點(diǎn)}//==========刪除帶頭結(jié)點(diǎn)的單鏈表中的指定結(jié)點(diǎn)=======voidDeleteList(LinkListhead,char*key){ListNode*p,*r,*q=head;p=LocateNode(head,key);//按key值查找結(jié)點(diǎn)的if(p==NULL){//若沒有找到結(jié)點(diǎn)，退出printf("positionerror");exit(0);}while(q->next!=p)//p為要刪除的結(jié)點(diǎn)，q為p的前結(jié)點(diǎn)q=q->next;r=q->next;q->next=r->next;free(r);//釋放結(jié)點(diǎn)}//===========打印鏈表=======voidprintlist(LinkListhead){ListNode*p=head->next;//從開始結(jié)點(diǎn)打印while(p){printf("%s,",p->data);p=p->next;}printf("\n");}//==========刪除所有結(jié)點(diǎn)，釋放空間===========voidDeleteAll(LinkListhead){ListNode*p=head,*r;while(p->next){r=p->next;free(p);p=r;}free(p);}運(yùn)行結(jié)果：加的添加結(jié)點(diǎn)的代碼：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;}運(yùn)行結(jié)果：最后提示為OK添加成功。實(shí)驗(yàn)心得：這個實(shí)驗(yàn)中主要修改的是ch和num把它們由指針改成數(shù)組因?yàn)椴桓牡脑捲诤竺鎑elect函數(shù)中會出現(xiàn)沒有地址的情況找不到地址就不能執(zhí)行功能然后把locate函數(shù)的判斷語句改一下避免矛盾的出現(xiàn)。實(shí)驗(yàn)二、二叉樹操作目的掌握二叉樹的定義、性質(zhì)及存儲方式，各種遍歷算法。要求采用二叉樹鏈表作為存儲結(jié)構(gòu)，完成二叉樹的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結(jié)點(diǎn)總數(shù)的操作。程序源代碼#include"stdio.h"#include"string.h"#defineMax20//結(jié)點(diǎn)的最大個數(shù)typedefstructnode{chardata;structnode*lchild,*rchild;}BinTNode;//自定義二叉樹的結(jié)點(diǎn)類型typedefBinTNode*BinTree;//定義二叉樹的指針intNodeNum,leaf;//NodeNum為結(jié)點(diǎn)數(shù)，leaf為葉子數(shù)//==========基于先序遍歷算法創(chuàng)建二叉樹==============//=====要求輸入先序序列，其中加入虛結(jié)點(diǎn)“#”以示空指針的位置==========BinTreeCreatBinTree(void){BinTreeT;charch;if((ch=getchar())=='#')return(NULL);//讀入#，返回空指針else{T=(BinTNode*)malloc(sizeof(BinTNode));//生成結(jié)點(diǎn)T->data=ch;T->lchild=CreatBinTree();//構(gòu)造左子樹T->rchild=CreatBinTree();//構(gòu)造右子樹return(T);}}//========NLR先序遍歷=============voidPreorder(BinTreeT){if(T){printf("%c",T->data);//訪問結(jié)點(diǎn)Preorder(T->lchild);//先序遍歷左子樹Preorder(T->rchild);//先序遍歷右子樹}}//========LNR中序遍歷===============voidInorder(BinTreeT){if(T){Inorder(T->lchild);//中序遍歷左子樹printf("%c",T->data);//訪問結(jié)點(diǎn)Inorder(T->rchild);//中序遍歷右子樹}}//==========LRN后序遍歷============voidPostorder(BinTreeT){if(T){Postorder(T->lchild);//后序遍歷左子樹Postorder(T->rchild);//后序遍歷右子樹printf("%c",T->data);//訪問結(jié)點(diǎn)}}//=====采用后序遍歷求二叉樹的深度、結(jié)點(diǎn)數(shù)及葉子數(shù)的遞歸算法========intTreeDepth(BinTreeT){inthl,hr,max;if(T){hl=TreeDepth(T->lchild);//求左深度hr=TreeDepth(T->rchild);//求右深度max=hl>hr?hl:hr;//取左右深度的最大值NodeNum=NodeNum+1;//求結(jié)點(diǎn)數(shù)if(hl==0&&hr==0)leaf=leaf+1;//若左右深度為0，即為葉子。return(max+1);}elsereturn(0);}//====利用“先進(jìn)先出”（FIFO）隊(duì)列，按層次遍歷二叉樹==========voidLevelorder(BinTreeT){intfront=0,rear=1;BinTNode*cq[Max],*p;//定義結(jié)點(diǎn)的指針數(shù)組cqcq[1]=T;//根入隊(duì)while(front!=rear){front=(front+1)%NodeNum;p=cq[front];//出隊(duì)printf("%c",p->data);//出隊(duì)，輸出結(jié)點(diǎn)的值if(p->lchild!=NULL){rear=(rear+1)%NodeNum;cq[rear]=p->lchild;//左子樹入隊(duì)}if(p->rchild!=NULL){rear=(rear+1)%NodeNum;cq[rear]=p->rchild;//右子樹入隊(duì)}}}//==========主函數(shù)=================voidmain(){BinTreeroot;inti,depth;printf("\n");printf("CreatBin_Tree；Inputpreorder:");//輸入完全二叉樹的先序序列，//用#代表虛結(jié)點(diǎn)，如ABD###CE##F##root=CreatBinTree();//創(chuàng)建二叉樹，返回根結(jié)點(diǎn)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，求出該樹的結(jié)點(diǎn)數(shù)。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);//求樹的深度及葉子數(shù)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);}執(zhí)行程序先序遍歷中序遍歷后序遍歷結(jié)點(diǎn)數(shù)葉子數(shù)高度5..層次遍歷自己設(shè)計(jì)的：abdhl##m##i##e#jn###cf#ko###g##1.預(yù)計(jì)先序遍歷結(jié)果：abdhlmiejncfkog2.預(yù)計(jì)中序遍歷結(jié)果：lhmdibenjafokcg3.預(yù)計(jì)后序遍歷結(jié)果：lmhidnjebokfgca4.結(jié)點(diǎn)數(shù)15高度5葉子數(shù)6實(shí)際結(jié)果：實(shí)驗(yàn)心得：這次實(shí)驗(yàn)主要是要讓我們熟練樹及其相關(guān)知識熟練掌握先序中序后序遍歷，層次遍歷然后我們自己畫一個圖會實(shí)現(xiàn)以上功能以及葉子數(shù)結(jié)點(diǎn)數(shù)還有高度的計(jì)算程序里面大量運(yùn)用了遞歸以及隊(duì)的應(yīng)用，實(shí)驗(yàn)三、圖的遍歷操作目的掌握有向圖和無向圖的概念；掌握鄰接矩陣和鄰接鏈表建立圖的存儲結(jié)構(gòu)；掌握DFS及BFS對圖的遍歷操作；了解圖結(jié)構(gòu)在人工智能、工程等領(lǐng)域的廣泛應(yīng)用。要求采用鄰接矩陣和鄰接鏈表作為圖的存儲結(jié)構(gòu)，完成有向圖和無向圖的DFS和BFS操作。DFS和BFS的基本思想深度優(yōu)先搜索法DFS的基本思想：從圖G中某個頂點(diǎn)Vo出發(fā)，首先訪問Vo，然后選擇一個與Vo相鄰且沒被訪問過的頂點(diǎn)Vi訪問，再從Vi出發(fā)選擇一個與Vi相鄰且沒被訪問過的頂點(diǎn)Vj訪問，……依次繼續(xù)。如果當(dāng)前被訪問過的頂點(diǎn)的所有鄰接頂點(diǎn)都已被訪問，則回退到已被訪問的頂點(diǎn)序列中最后一個擁有未被訪問的相鄰頂點(diǎn)的頂點(diǎn)W，從W出發(fā)按同樣方法向前遍歷。直到圖中所有的頂點(diǎn)都被訪問。廣度優(yōu)先算法BFS的基本思想：從圖G中某個頂點(diǎn)Vo出發(fā)，首先訪問Vo，然后訪問與Vo相鄰的所有未被訪問過的頂點(diǎn)V1，V2，……，Vt；再依次訪問與V1，V2，……，Vt相鄰的起且未被訪問過的的所有頂點(diǎn)。如此繼續(xù)，直到訪問完圖中的所有頂點(diǎn)。程序源代碼鄰接矩陣作為存儲結(jié)構(gòu)的程序示例#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum100//定義最大頂點(diǎn)數(shù)typedefstruct{charvexs[MaxVertexNum];//頂點(diǎn)表intedges[MaxVertexNum][MaxVertexNum];//鄰接矩陣，可看作邊表intn,e;//圖中的頂點(diǎn)數(shù)n和邊數(shù)e}MGraph;//用鄰接矩陣表示的圖的類型//=========建立鄰接矩陣=======voidCreatMGraph(MGraph*G){inti,j,k;chara;printf("InputVertexNum(n)andEdgesNum(e):");scanf("%d,%d",&G->n,&G->e);//輸入頂點(diǎn)數(shù)和邊數(shù)scanf("%c",&a);printf("InputVertexstring:");for(i=0;i<G->n;i++){scanf("%c",&a);G->vexs[i]=a;//讀入頂點(diǎn)信息，建立頂點(diǎn)表}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）的頂點(diǎn)序號G->edges[i][j]=1;G->edges[j][i]=1;//若為無向圖，矩陣為對稱矩陣；若建立有向圖，去掉該條語句}}//=========定義標(biāo)志向量，為全局變量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度優(yōu)先遍歷的遞歸算法======voidDFSM(MGraph*G,inti){//以Vi為出發(fā)點(diǎn)對鄰接矩陣表示的圖G進(jìn)行DFS搜索，鄰接矩陣是0，1矩陣intj;printf("%c",G->vexs[i]);//訪問頂點(diǎn)Vivisited[i]=TRUE;//置已訪問標(biāo)志for(j=0;j<G->n;j++)//依次搜索Vi的鄰接點(diǎn)if(G->edges[i][j]==1&&!visited[j])DFSM(G,j);//（Vi，Vj）∈E，且Vj未訪問過，故Vj為新出發(fā)點(diǎn)}voidDFS(MGraph*G){inti;for(i=0;i<G->n;i++)visited[i]=FALSE;//標(biāo)志向量初始化for(i=0;i<G->n;i++)if(!visited[i])//Vi未訪問過DFSM(G,i);//以Vi為源點(diǎn)開始DFS搜索}//===========BFS：廣度優(yōu)先遍歷=======voidBFS(MGraph*G,intk){//以Vk為源點(diǎn)對用鄰接矩陣表示的圖G進(jìn)行廣度優(yōu)先搜索inti,j,f=0,r=0;intcq[MaxVertexNum];//定義隊(duì)列for(i=0;i<G->n;i++)visited[i]=FALSE;//標(biāo)志向量初始化for(i=0;i<G->n;i++)cq[i]=-1;//隊(duì)列初始化printf("%c",G->vexs[k]);//訪問源點(diǎn)Vkvisited[k]=TRUE;cq[r]=k;//Vk已訪問，將其入隊(duì)。注意，實(shí)際上是將其序號入隊(duì)while(cq[f]!=-1){//隊(duì)非空則執(zhí)行i=cq[f];f=f+1;//Vf出隊(duì)for(j=0;j<G->n;j++)//依次Vi的鄰接點(diǎn)Vjif(G->edges[i][j]==1&&!visited[j]){//Vj未訪問printf("%c",G->vexs[j]);//訪問Vjvisited[j]=TRUE;r=r+1;cq[r]=j;//訪問過Vj入隊(duì)}}}//==========main=====voidmain(){inti;MGraph*G;G=(MGraph*)malloc(sizeof(MGraph));//為圖G申請內(nèi)存空間CreatMGraph(G);//建立鄰接矩陣printf("PrintGraphDFS:");DFS(G);//深度優(yōu)先遍歷printf("\n");printf("PrintGraphBFS:");BFS(G,3);//以序號為3的頂點(diǎn)開始廣度優(yōu)先遍歷printf("\n");}調(diào)試結(jié)果：自己畫的圖：1對應(yīng)頂點(diǎn)下標(biāo)0以此類推9對應(yīng)下標(biāo)8預(yù)計(jì)運(yùn)行結(jié)果：DFS:012345678BFS:324105687對應(yīng)我這個圖：DFS：123456789BFS：435216798實(shí)驗(yàn)心得：圖在數(shù)據(jù)結(jié)構(gòu)中是相當(dāng)重要的一部分聯(lián)系很多現(xiàn)實(shí)問題圖的根本就是頂點(diǎn)和邊通過頂點(diǎn)和邊建立鄰接矩陣以及鄰接鏈表廣度搜索和深度搜索是此算法著重關(guān)注的地方。要學(xué)會自己畫圖然后寫出這兩種搜索的結(jié)果，程序中用了隊(duì)的算法是亮點(diǎn)通過TRUE和FAUSE來標(biāo)記頂點(diǎn)是否以及訪問避免重復(fù)實(shí)驗(yàn)四、排序目的掌握各種排序方法的基本思想、排序過程、算法實(shí)現(xiàn)，能進(jìn)行時間和空間性能的分析，根據(jù)實(shí)際問題的特點(diǎn)和要求選擇合適的排序方法。要求實(shí)現(xiàn)直接排序、冒泡、直接選擇、快速、堆、歸并排序算法。比較各種算法的運(yùn)行速度。程序示例#include"stdio.h"#include"stdlib.h"#defineMax100//假設(shè)文件長度typedefstruct{//定義記錄類型intkey;//關(guān)鍵字項(xiàng)}RecType;typedefRecTypeSeqList[Max+1];//SeqList為順序表，表中第0個元素作為哨兵intn;//順序表實(shí)際的長度直接插入排序的基本思想：每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已排序好的子文件中的適當(dāng)位置，直到全部記錄插入完成為止。//==========直接插入排序法======voidInsertSort(SeqListR){//對順序表R中的記錄R[1‥n]按遞增序進(jìn)行插入排序inti,j;for(i=2;i<=n;i++)//依次插入R[2]，……，R[n]if(R[i].key<R[i-1].key){//若R[i].key大于等于有序區(qū)中所有的keys，則R[i]留在原位R[0]=R[i];j=i-1;//R[0]是R[i]的副本do{//從右向左在有序區(qū)R[1‥i-1]中查找R[i]的位置R[j+1]=R[j];//將關(guān)鍵字大于R[i].key的記錄后移j--;}while(R[0].key<R[j].key);//當(dāng)R[i].key≥R[j].key是終止R[j+1]=R[0];//R[i]插入到正確的位置上}//endif}冒泡排序的基本思想：設(shè)想被排序的記錄數(shù)組R[1‥n]垂直排序。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上“漂浮”（交換），如此反復(fù)進(jìn)行，直到最后任意兩個氣泡都是輕者在上，重者在下為止。//==========冒泡排序=======typedefenum{FALSE,TRUE}Boolean;//FALSE為0，TRUE為1voidBubbleSort(SeqListR){//自下向上掃描對R做冒泡排序inti,j;Booleanexchange;//交換標(biāo)志for(i=1;i<n;i++){//最多做n-1趟排序exchange=FALSE;//本趟排序開始前，交換標(biāo)志應(yīng)為假for(j=n-1;j>=i;j--)//對當(dāng)前無序區(qū)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;//發(fā)生了交換，故將交換標(biāo)志置為真}if(!exchange)//本趟排序未發(fā)生交換，提前終止算法return;}//endfor（為循環(huán)）}快速排序的基本思想：在待排序的n個記錄中任取一個記錄（通常取第一個記錄），把該記錄作為支點(diǎn)（又稱基準(zhǔn)記錄）（pivot），將所有關(guān)鍵字比它小的記錄放置在它的位置之前，將所有關(guān)鍵字比它大的記錄放置在它的位置之后(稱之為一次劃分過程)。之后對所分的兩部分分別重復(fù)上述過程，直到每部分只有一個記錄為止。//1.========一次劃分函數(shù)=====intPartition(SeqListR,inti,intj){//對R[i‥j]做一次劃分，并返回基準(zhǔn)記錄的位置RecTypepivot=R[i];//用第一個記錄作為基準(zhǔn)while(i<j){//從區(qū)間兩端交替向中間掃描，直到i=jwhile(i<j&&R[j].key>=pivot.key)//基準(zhǔn)記錄pivot相當(dāng)與在位置i上j--;//從右向左掃描，查找第一個關(guān)鍵字小于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)//基準(zhǔn)記錄pivot相當(dāng)與在位置j上i++;//從左向右掃描，查找第一個關(guān)鍵字小于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，基準(zhǔn)記錄已被最后定位returni;//返回基準(zhǔn)記錄的位置}//2.=====快速排序===========voidQuickSort(SeqListR,intlow,inthigh){//R[low..high]快速排序intpivotpos;//劃分后基準(zhǔn)記錄的位置if(low<high){//僅當(dāng)區(qū)間長度大于1時才排序pivotpos=Partition(R,low,high);//對R[low..high]做一次劃分，得到基準(zhǔn)記錄的位置QuickSort(R,low,pivotpos-1);//對左區(qū)間遞歸排序QuickSort(R,pivotpos+1,high);//對右區(qū)間遞歸排序}}直接選擇排序的基本思想：第i趟排序開始時，當(dāng)前有序區(qū)和無序區(qū)分別為R[1‥i-1]和R[i‥n]（1≤i≤n-1），該趟排序則是從當(dāng)前無序區(qū)中選擇出關(guān)鍵字最小的記錄R[k]，將它與無序區(qū)的的第一個記錄R[i]交換，有序區(qū)增加一個記錄，使R[1‥i],和R[i+1‥n]分別為新的有序區(qū)和新的無序區(qū)。如此反復(fù)進(jì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++)//在當(dāng)前無序區(qū)R[i‥n]中選key最小的記錄R[k]if(R[j].key<R[k].key)k=j;//k記下目前找到的最小關(guān)鍵字所在的位置if(k!=i){////交換R[i]和R[k]R[0]=R[i];R[i]=R[k];R[k]=R[0];}//endif}//endfor}堆排序的基本思想：它是一種樹型選擇排序，特點(diǎn)是：在排序的過程中，將R[1‥n]看成是一個完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系，在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大（或最?。┑挠涗?。即：把待排序文件的關(guān)鍵字存放在數(shù)組R[1‥n]子中，將R看成是一棵二叉樹，每個結(jié)點(diǎn)表示一個記錄，源文件的第一個記錄R[1]作為二叉樹的根，以下各記錄R[2‥n]依次逐層從左到右排列，構(gòu)成一棵完全二叉樹，任意結(jié)點(diǎn)R[i]的左孩子是R[2i]，右孩子是R[2i+1]，雙親是R[i/2]。對這棵完全二叉樹的結(jié)點(diǎn)進(jìn)行調(diào)整，使各結(jié)點(diǎn)的關(guān)鍵字滿足下列條件：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稱大堆根//==========大根堆調(diào)整函數(shù)=======voidHeapify(SeqListR,intlow,inthigh){//將R[low..high]調(diào)整為大根堆，除R[low]外，其余結(jié)點(diǎn)均滿足堆性質(zhì)intlarge;//large指向調(diào)整結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)中關(guān)鍵字較大者RecTypetemp=R[low];//暫存調(diào)整結(jié)點(diǎn)for(large=2*low;large<=high;large*=2){//R[low]是當(dāng)前調(diào)整結(jié)點(diǎn)//若large>high,則表示R[low]是葉子，調(diào)整結(jié)束；否則先令large指向R[low]的左孩子if(large<high&&R[large].key<R[large+1].key)large++;//若R[low]的右孩子存在且關(guān)鍵字大于左兄弟，則令large指向它//現(xiàn)在R[large]是調(diào)整結(jié)點(diǎn)R[low]的左右孩子結(jié)點(diǎn)中關(guān)鍵字較大者if(temp.key>=R[large].key)//temp始終對應(yīng)R[low]break;//當(dāng)前調(diào)整結(jié)點(diǎn)不小于其孩子結(jié)點(diǎn)的關(guān)鍵字，結(jié)束調(diào)整R[low]=R[large];//相當(dāng)于交換了R[low]和R[large]low=large;//令low指向新的調(diào)整結(jié)點(diǎn)，相當(dāng)于temp已篩下到large的位置}R[low]=temp;//將被調(diào)整結(jié)點(diǎn)放入最終位置上}//==========構(gòu)造大根堆==========voidBuildHeap(SeqListR){//將初始文件R[1..n]構(gòu)造為堆inti;for(i=n/2;i>0;i--)Heapify(R,i,n);//將R[i..n]調(diào)整為大根堆}//==========堆排序===========voidHeapSort(SeqListR){//對R[1..n]進(jìn)行堆排序，不妨用R[0]做暫存單元inti;BuildHeap(R);//將R[1..n]構(gòu)造為初始大根堆for(i=n;i>1;i--){//對當(dāng)前無序區(qū)R[1..i]進(jìn)行堆排序，共做n-1趟。R[0]=R[1];R[1]=R[i];R[i]=R[0];//將堆頂和堆中最后一個記錄交換Heapify(R,1,i-1);//將R[1..i-1]重新調(diào)整為堆，僅有R[1]可能違反堆性質(zhì)。}}二路歸并排序的基本思想：假設(shè)初始序列n個記錄，則可看成是n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到[n/2]個長度為2或1的有序子序列；再兩兩歸并，……，如此重復(fù)，直到一個長度為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)//若第一個子序列非空，則復(fù)制剩余記錄到R1R1[p++]=R[i++];while(j<=high)//若第二個子序列非空，則復(fù)制剩余記錄到R1中R1[p++]=R[j++];for(p=0,i=low;i<=high;p++,i++)R[i]=R1[p];//歸并完成后將結(jié)果復(fù)制回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);}//==========主函數(shù)======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);//輸入整數(shù)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，結(jié)束程序}printf("Sortreult:");output_int(R);}運(yùn)行結(jié)果：直接插入排序：冒泡法排序：快速排序：直接選擇排序：堆排序：歸并排序：實(shí)驗(yàn)心得：關(guān)于排序的數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)。感覺各種排序方法都有各自的特點(diǎn)。直接插入排序是根據(jù)前面一個數(shù)的位置和后面一個相比較直接排而冒泡法則要經(jīng)過n*(n-1)次每次確定一個數(shù)的位置但是這種方法有點(diǎn)復(fù)雜要循環(huán)n次，而快速排序則是從中間到兩邊任選一個數(shù)出來把小的排前面大的排后面然后重復(fù)以上過程這樣可以有效地節(jié)約時間每一步都為下一步節(jié)約了時間。而直接選擇排序有兩個序列也是每一步都為下一步節(jié)約了世界堆排序巧妙地利用了樹中雙親與孩子的關(guān)系歸并排序則是發(fā)散的通過遞歸成2的n次方排，通過這幾種排序方法我更加了解了排序也知道了許多數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告四——哈希表查找名字（字符串）實(shí)驗(yàn)題目：哈希表查找名字（字符串）實(shí)驗(yàn)?zāi)繕?biāo)：輸入一組名字（至少50個），將其保存并利用哈希表查找。輸出哈希查找沖突次數(shù)，哈希表負(fù)載因子、查找命中率。數(shù)據(jù)結(jié)構(gòu)：哈希表和數(shù)組（二維）。二維數(shù)組用于靜態(tài)順序存儲名字（字符串），哈希表采用開放定址法，用于存儲名字（字符串）對應(yīng)的關(guān)鍵字并實(shí)現(xiàn)對名字（字符串）的查找。需要的操作有：1.關(guān)鍵字求?。ㄖ骱瘮?shù)中兩次出現(xiàn)，未單獨(dú)編為函數(shù)）關(guān)鍵字key=abs（字符串首位ASCII碼值-第二位ASCII碼值+第（[n2]+1）位ASCII碼值-最后一位ASCII碼值-倒數(shù)第二位ASCII碼值）*2.處理關(guān)鍵字的哈希函數(shù)（Hash）利用平方取中法求關(guān)鍵值key在哈希表中的位置。公式add=（key*key）%1000/LENGTH（add為key在哈希表中的地址）。intHash(intkey){return((key*key)/1000%LENGTH);}3.處理哈希表中沖突的函數(shù)（Collision）利用線性探測再散列處理沖突，利用全局變量count統(tǒng)計(jì)沖突次數(shù)。intCollision(intkey,intHashtable[]){inti;for(i=1;i<=LENGTH;i++) {if(Hashtable[(Hash(key)+i)%LENGTH]==-1)return((Hash(key)+i)%LENGTH);count++; }}4.哈希表初始化（InitHash）voidInitHash(intHashtable[]){inti;for(i=0;i<LENGTH;i++)Hashtable[i]=-1;}5.向哈希表中插入關(guān)鍵字（InsertHash）voidInsertHash(intkey,intHashtable[]){intadd;add=Hash(key);if(Hashtable[add]==-1)Hashtable[add]=key;else {add=Collision(key,Hashtable);Hashtable[add]=key; }}6.查找關(guān)鍵字在哈希表中的存儲位置（SearchHash）intSearchHash(intkey,intHashtable[]){intadd;add=Hash(key);if(Hashtable[add]==key)returnadd;while(Hashtable[add]!=key&&Hashtable[add]!=-1)add=Collision(key,Hashtable);returnadd;}7.輸出哈希表（PrintHash）（幫助調(diào)試用）voidPrintHash(intHashtable[]){inti;for(i=0;i<LENGTH;i++)if(Hashtable[i]!=-1)printf("%3d:%d\n",i+1,Hashtable[i]);}8.求字符串長度（strlen）（函數(shù)庫<string.h>包含）以及求整數(shù)的絕對值（abs）（函數(shù)庫<math.h>包含）算法設(shè)計(jì)：1建立長度為LENGTH的哈希表Hash（LENGTH具體值由宏定義決定）。2輸入要插入的字符串總數(shù)num（num小于等于LENGTH），再輸入num個字符串，將這num個字符串的關(guān)鍵值key計(jì)算出來后插入哈希表中。3輸出哈希表（幫助調(diào)試用，并非實(shí)驗(yàn)?zāi)康模?依次查找這num個字符串對應(yīng)的關(guān)鍵字在哈希表中位置，并統(tǒng)計(jì)沖突次數(shù)，記為count。根據(jù)公式計(jì)算負(fù)載因子和命中率（負(fù)載因子=表中填入的記錄數(shù)/哈希表的長度，命中率=元素個數(shù)/查找次數(shù)）。輸出元素個數(shù)、沖突次數(shù)、查找次數(shù)、負(fù)載因子、命中率。源程序（將LENGTH定義為60，實(shí)際調(diào)試中定義為60和100各一次）：#include<stdio.h>#include<stdlib.h>#include<math.h>#include<string.h>#defineLENGTH60/*實(shí)際調(diào)試中定義為60和100各一次*/intHash(intkey);intCollision(intkey,intHashtable[]);voidInitHash(intHashtable[]);voidInsertHash(intkey,intHashtable[]);intSearchHash(intkey,intHashtable[]);voidPrintHash(intHashtable[]);intcount=0,num=0;voidmain(){inti,key,collapsetime,searchtime,Hash[LENGTH];floatloadelem,hitprob;charnames[LENGTH][20];InitHash(Hash);printf("inputthenumberofnames(number<=%d).\n",LENGTH);scanf("%d",&num);printf("inputnames.\n");for(i=0;i<num;i++) {scanf("%s",&names[i]); key=(abs((int)names[i][0]-(int)names[i][1]+(int)names[i][strlen(names[i])/2]-(int)names[i][strlen(names[i])-2]-(int)names[i][strlen(names[i])-1]))*strlen(names[i]); /*上式為關(guān)鍵字求取，公式：關(guān)鍵字key=abs（字符串首位ASCII碼值-第二位ASCII碼值+第（[n/2]+1）位ASCII碼值-最后一位ASCII碼值-倒數(shù)第二位ASCII碼值）*字符串長度（abs為求整數(shù)絕對值的函數(shù)）。*/InsertHash(key,Hash); } count=0;/*將count置零，清除插入過程中產(chǎn)生的沖突次數(shù)*/PrintHash(Hash);for(i=0;i<num;i++) { key=(abs((int)names[i][0]-(int)names[i][1]+(int)names[i][strlen(names[i])/2]-(int)names[i][strlen(names[i])-2]-(int)names[i][strlen(names[i])-1]))*strlen(names[i]); /*上式為關(guān)鍵字求取，公式同上*/SearchHash(key,Hash); }collapsetime=count;searchtime=count+num;loadelem=(float)num/LENGTH;hitprob=(float)num/searchtime;printf("元素個數(shù)：%d\n",num);printf("沖突次數(shù)：%d\n",collapsetime);printf("查找次數(shù)：%d\n",searchtime);printf("負(fù)載因子：%f\n",loadelem);printf("命中率=總?cè)藬?shù)/查找數(shù)：%f\n",hitprob);}intHash(intkey)/*處理關(guān)鍵字的哈希函數(shù)*/{return((key*key)/1000%LENGTH);}intCollision(intkey,intHashtable[])/*處理哈希表中沖突*/{inti;for(i=1;i<=LENGTH;i++) {if(Hashtable[(Hash(key)+i)%LENGTH]==-1)return((Hash(key)+i)%LENGTH); count++;/*統(tǒng)計(jì)沖突次數(shù)*/ }}voidInitHash(intHashtable[])/*初始化哈希表*/{inti;for(i=0;i<LENGTH;i++)Hashtable[i]=-1;}voidInsertHash(intkey,intHashtable[])/*向哈希表中插入關(guān)鍵字*/{intadd;add=Hash(key);if(Hashtable[add]==-1)Hashtable[add]=key;else { add=Collision(key,Hashtable);/*處理哈希表中沖突，注意：這里count也會計(jì)數(shù)，所以結(jié)束插入過程后應(yīng)將count清零*/Hashtable[add]=key; }}intSearchHash(intkey,intHashtable[])/*查找關(guān)鍵字在哈希表中的地址*/{intadd;add=Hash(key);if(Hashtable[add]==key)returnadd;while(Hashtable[add]!=key&&Hashtable[add]!=-1) add=Collision(key,Hashtable);/*處理哈希表中沖突*/returnadd;}voidPrintHash(intHashtable[])/*輸出哈希表（幫助調(diào)試用）*/{inti;for(i=0;i<LENGTH;i++)if(Hashtable[i]!=-1)printf("%3d:%d\n",i+1,Hashtable[i]);}截圖第一組（LENGTH宏定義為60）輸入：50個名字（字符串，采用英文單詞）輸出結(jié)果：輸出：1.哈希表（幫助調(diào)試用）2.實(shí)驗(yàn)要求的各項(xiàng)參數(shù)元素個數(shù)：50，沖突次數(shù)：77，查找次數(shù)：127，負(fù)載因子：0.833333，命中率：0.393701.根據(jù)線性探測在散列成功查找時的公式ASL=12(1+11-α)（其中，ASL表示平均查找長度，α表示負(fù)載因子）。ASL=3.5，總平均查找次數(shù)為175，平均命中率為0.285714。顯然，本程序?qū)崿F(xiàn)的哈希查找在截圖第二組（LENGTH宏定義為100）輸入：50個名字（字符串，采用英文單詞）輸出：1.哈希表（幫助調(diào)試用）2.實(shí)驗(yàn)要求的各項(xiàng)參數(shù)元素個數(shù)：50，沖突次數(shù)：27，查找次數(shù)：77，負(fù)載因子：0.500000，命中率：0.649351.根據(jù)線性探測在散列成功查找時的公式ASL=12(1+11-α)（其中，ASL表示平均查找長度，α表示負(fù)載因子）。ASL=1.5，總平均查找次數(shù)為75，平均命中率為0.666667。顯然，本程序?qū)崿F(xiàn)的哈希查找在附：輸入的50個字符串a(chǎn)bandonalacrityarchipelagoassessattenuatebigotbrakebuffooncircumspectcommittedconfrontconstringeconvictioncovendefusedetractdimensiondiscreditdoldrumsencomiumennobleepitheteuphemismexcursivefeasiblesensitiveshrewdstationarygreasyobscurepersistentprevalentprominentrelevantvulnerableinevitablypresumablyguaranteelegislationmechanismpatternessencereputationthresholdoverwhelmhinderwreckwiltfloutnovel實(shí)驗(yàn)總結(jié)與心得：構(gòu)造合適的關(guān)鍵字和哈希函數(shù)對于增加命中率非常關(guān)鍵，哈希函數(shù)最終選用了平方取中法。而關(guān)鍵字，對于字符串形式的存儲元素作用相當(dāng)重要。起初打算用（字符串首位ASCII碼值*字符串長度）作為關(guān)鍵字，但發(fā)現(xiàn)命中率不到0.2；因此加上了最后一位和第二位，命中率可提高到0.26（仍不如平均狀況）；加上倒數(shù)第二位提高到0.3，最后加上第（[n/2]+1）位形成了五位相加減的狀況，將命中率提高到了現(xiàn)在的0.39（以上所述的狀況是LENGTH為60，輸入字符串?dāng)?shù)目為50，這也是調(diào)試所用的宏定義狀況，第二組輸出結(jié)果是將LENGTH直接改為100時實(shí)現(xiàn)的）。這充分表明了本次實(shí)驗(yàn)需要一定的耐心。HUNAN課程實(shí)習(xí)報(bào)告題目：哈希表學(xué)生姓名唐鵬學(xué)生學(xué)號202108080216專業(yè)班級物聯(lián)2班指導(dǎo)老師吳帆2021年4月2日本程序來自于圖書館靠書名來檢索想要查找的書問題。本程序要求：（1）根據(jù)輸入建立圖書名稱表，采用創(chuàng)建散列表實(shí)現(xiàn)。（2）建散列表后，如果想要查找的數(shù)據(jù)在散列表中輸出yes否則輸出no。結(jié)構(gòu)中存在關(guān)鍵字和K相等的記錄，則必定存儲在f(K）的位置上。由此，不需比較便可直接取得所查記錄。這個對應(yīng)關(guān)系f稱為散列函數(shù)(Hashfunction），按這個思想建立的表為散列表。*對不同的關(guān)鍵字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2），這種現(xiàn)象稱沖突。具有相同函數(shù)值的關(guān)鍵字對該散列函數(shù)來說稱做同義詞。*綜上所述，根據(jù)散列函數(shù)H(key）和處理沖突的方法將一組關(guān)鍵字映象到一個有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“象”，作為這條記錄在表中的存儲位置，這種表便稱為散列表，這一映象過程稱為散列造表或散列，所得的存儲位置稱散列地址。這個現(xiàn)象也叫散列桶，在散列桶中，只能通過順序的方式來查找，一般只需要查找三次就可以找到?？茖W(xué)家計(jì)算過，當(dāng)負(fù)載因子(loadfactor)不超過75%，查找效率最高。*若對于關(guān)鍵字集合中的任一個關(guān)鍵字，經(jīng)散列函數(shù)映象到地址集合中任何