數(shù)據(jù)結構單鏈表實驗報告實用文檔

洛陽理工學院實驗報告系別計算機系班級學號姓名課程名稱數(shù)據(jù)結構實驗日期11.7實驗名稱鏈表的基本操作成績實驗目的：熟悉掌握線性表鏈式存儲結構，掌握與應用查找、插入、刪除等基本操作算法，訓練和提高結構化程序設計能力及程序調試能力。實驗條件：計算機一臺，VisualC++6.0實驗內容：問題描述以單鏈表為存儲結構實現(xiàn)以下基本操作：在第i個元素前插入一個新元素。查找值為x的某個元素。若成功，給出x在表中的位置；不成功給出提示信息。刪除第i個元素，若成功，給出提示信息并顯示被刪元素的值；不成功給出失敗的提示信息。數(shù)據(jù)結構類型定義typedefstructLinkNode{ intValue; structLinkNode*Next;}Node,*LinkList;模塊劃分（1）初始化鏈表：voidInitList(LinkList*L);（2）創(chuàng)建鏈表:尾插法：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指針動態(tài)指向鏈表的當前表尾，以便于做尾插入，其初值指向頭結點*/ while(flag)/*循環(huán)輸入表中元素值，將建立新結點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++;/*已掃描結點計數(shù)器*/ } 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時退出循環(huán)*/ } 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為空表已找完還未數(shù)到第i個，說明插入位置不合理*/ { printf("插入位置不合理!"); returnERROR; } s=(Node*)malloc(sizeof(Node));/*申請一個新的結點S*/ s->data=e;/*值e置入s的數(shù)據(jù)域*/ 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循環(huán)是因為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.測試數(shù)據(jù)及結果實驗總結：在調試的時候發(fā)現(xiàn)在頭插法的時候出現(xiàn)錯誤，經(jīng)過邏輯思考與調試，發(fā)現(xiàn)錯誤所在，并且更改。實驗一、單鏈表的插入和刪除一、目的了解和掌握線性表的邏輯結構和鏈式存儲結構，掌握單鏈表的基本算法及相關的時間性能分析。二、要求：建立一個數(shù)據(jù)域定義為字符串的單鏈表，在鏈表中不允許有重復的字符串；根據(jù)輸入的字符串，先找到相應的結點，后刪除之。三、程序源代碼#include"stdio.h"#include"string.h"#include"stdlib.h"#include"ctype.h"typedefstructnode//定義結點{chardata[10];//結點的數(shù)據(jù)域為字符串structnode*next;//結點的指針域}ListNode;typedefListNode*LinkList;//自定義LinkList單鏈表類型LinkListCreatListR1();//函數(shù)，用尾插入法建立帶頭結點的單鏈表ListNode*LocateNode();//函數(shù)，按值查找結點voidDeleteList();//函數(shù)，刪除指定值的結點voidprintlist();//函數(shù)，打印鏈表中的所有值voidDeleteAll();//函數(shù)，刪除所有結點，釋放內存//==========主函數(shù)==============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把它們由指針改成數(shù)組因為不改的話在后面delect函數(shù)中會出現(xiàn)沒有地址的情況找不到地址就不能執(zhí)行功能然后把locate函數(shù)的判斷語句改一下避免矛盾的出現(xiàn)。實驗二、二叉樹操作目的掌握二叉樹的定義、性質及存儲方式，各種遍歷算法。要求采用二叉樹鏈表作為存儲結構，完成二叉樹的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結點總數(shù)的操作。程序源代碼#include"stdio.h"#include"string.h"#defineMax20//結點的最大個數(shù)typedefstructnode{chardata;structnode*lchild,*rchild;}BinTNode;//自定義二叉樹的結點類型typedefBinTNode*BinTree;//定義二叉樹的指針intNodeNum,leaf;//NodeNum為結點數(shù)，leaf為葉子數(shù)//==========基于先序遍歷算法創(chuàng)建二叉樹==============//=====要求輸入先序序列，其中加入虛結點“#”以示空指針的位置==========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);//訪問結點}}//=====采用后序遍歷求二叉樹的深度、結點數(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;//求結點數(shù)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;//定義結點的指針數(shù)組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;//右子樹入隊}}}//==========主函數(shù)=================voidmain(){BinTreeroot;inti,depth;printf("\n");printf("CreatBin_Tree；Inputpreorder:");//輸入完全二叉樹的先序序列，//用#代表虛結點，如ABD###CE##F##root=CreatBinTree();//創(chuàng)建二叉樹，返回根結點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，求出該樹的結點數(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í)行程序先序遍歷中序遍歷后序遍歷結點數(shù)葉子數(shù)高度5..層次遍歷自己設計的：abdhl##m##i##e#jn###cf#ko###g##1.預計先序遍歷結果：abdhlmiejncfkog2.預計中序遍歷結果：lhmdibenjafokcg3.預計后序遍歷結果：lmhidnjebokfgca4.結點數(shù)15高度5葉子數(shù)6實際結果：實驗心得：這次實驗主要是要讓我們熟練樹及其相關知識熟練掌握先序中序后序遍歷，層次遍歷然后我們自己畫一個圖會實現(xiàn)以上功能以及葉子數(shù)結點數(shù)還有高度的計算程序里面大量運用了遞歸以及隊的應用，實驗三、圖的遍歷操作目的掌握有向圖和無向圖的概念；掌握鄰接矩陣和鄰接鏈表建立圖的存儲結構；掌握DFS及BFS對圖的遍歷操作；了解圖結構在人工智能、工程等領域的廣泛應用。要求采用鄰接矩陣和鄰接鏈表作為圖的存儲結構，完成有向圖和無向圖的DFS和BFS操作。DFS和BFS的基本思想深度優(yōu)先搜索法DFS的基本思想：從圖G中某個頂點Vo出發(fā)，首先訪問Vo，然后選擇一個與Vo相鄰且沒被訪問過的頂點Vi訪問，再從Vi出發(fā)選擇一個與Vi相鄰且沒被訪問過的頂點Vj訪問，……依次繼續(xù)。如果當前被訪問過的頂點的所有鄰接頂點都已被訪問，則回退到已被訪問的頂點序列中最后一個擁有未被訪問的相鄰頂點的頂點W，從W出發(fā)按同樣方法向前遍歷。直到圖中所有的頂點都被訪問。廣度優(yōu)先算法BFS的基本思想：從圖G中某個頂點Vo出發(fā)，首先訪問Vo，然后訪問與Vo相鄰的所有未被訪問過的頂點V1，V2，……，Vt；再依次訪問與V1，V2，……，Vt相鄰的起且未被訪問過的的所有頂點。如此繼續(xù)，直到訪問完圖中的所有頂點。程序源代碼鄰接矩陣作為存儲結構的程序示例#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum100//定義最大頂點數(shù)typedefstruct{charvexs[MaxVertexNum];//頂點表intedges[MaxVertexNum][MaxVertexNum];//鄰接矩陣，可看作邊表intn,e;//圖中的頂點數(shù)n和邊數(shù)e}MGraph;//用鄰接矩陣表示的圖的類型//=========建立鄰接矩陣=======voidCreatMGraph(MGraph*G){inti,j,k;chara;printf("InputVertexNum(n)andEdgesNum(e):");scanf("%d,%d",&G->n,&G->e);//輸入頂點數(shù)和邊數(shù)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：深度優(yōu)先遍歷的遞歸算法======voidDFSM(MGraph*G,inti){//以Vi為出發(fā)點對鄰接矩陣表示的圖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為新出發(fā)點}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：廣度優(yōu)先遍歷=======voidBFS(MGraph*G,intk){//以Vk為源點對用鄰接矩陣表示的圖G進行廣度優(yōu)先搜索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){//隊非空則執(zhí)行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);//深度優(yōu)先遍歷printf("\n");printf("PrintGraphBFS:");BFS(G,3);//以序號為3的頂點開始廣度優(yōu)先遍歷printf("\n");}調試結果：自己畫的圖：1對應頂點下標0以此類推9對應下標8預計運行結果：DFS:012345678BFS:324105687對應我這個圖：DFS：123456789BFS：435216798實驗心得：圖在數(shù)據(jù)結構中是相當重要的一部分聯(lián)系很多現(xiàn)實問題圖的根本就是頂點和邊通過頂點和邊建立鄰接矩陣以及鄰接鏈表廣度搜索和深度搜索是此算法著重關注的地方。要學會自己畫圖然后寫出這兩種搜索的結果，程序中用了隊的算法是亮點通過TRUE和FAUSE來標記頂點是否以及訪問避免重復實驗四、排序目的掌握各種排序方法的基本思想、排序過程、算法實現(xiàn)，能進行時間和空間性能的分析，根據(jù)實際問題的特點和要求選擇合適的排序方法。要求實現(xiàn)直接排序、冒泡、直接選擇、快速、堆、歸并排序算法。比較各種算法的運行速度。程序示例#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大于等于有序區(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];//將關鍵字大于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}冒泡排序的基本思想：設想被排序的記錄數(shù)組R[1‥n]垂直排序。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組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--)//對當前無序區(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ā)生了交換，故將交換標志置為真}if(!exchange)//本趟排序未發(fā)生交換，提前終止算法return;}//endfor（為循環(huán)）}快速排序的基本思想：在待排序的n個記錄中任取一個記錄（通常取第一個記錄），把該記錄作為支點（又稱基準記錄）（pivot），將所有關鍵字比它小的記錄放置在它的位置之前，將所有關鍵字比它大的記錄放置在它的位置之后(稱之為一次劃分過程)。之后對所分的兩部分分別重復上述過程，直到每部分只有一個記錄為止。//1.========一次劃分函數(shù)=====intPartition(SeqListR,inti,intj){//對R[i‥j]做一次劃分，并返回基準記錄的位置RecTypepivot=R[i];//用第一個記錄作為基準while(i<j){//從區(qū)間兩端交替向中間掃描，直到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){//僅當區(qū)間長度大于1時才排序pivotpos=Partition(R,low,high);//對R[low..high]做一次劃分，得到基準記錄的位置QuickSort(R,low,pivotpos-1);//對左區(qū)間遞歸排序QuickSort(R,pivotpos+1,high);//對右區(qū)間遞歸排序}}直接選擇排序的基本思想：第i趟排序開始時，當前有序區(qū)和無序區(qū)分別為R[1‥i-1]和R[i‥n]（1≤i≤n-1），該趟排序則是從當前無序區(qū)中選擇出關鍵字最小的記錄R[k]，將它與無序區(qū)的的第一個記錄R[i]交換，有序區(qū)增加一個記錄，使R[1‥i],和R[i+1‥n]分別為新的有序區(qū)和新的無序區(qū)。如此反復進行，直到排序完畢。//======直接選擇排序========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++)//在當前無序區(qū)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]看成是一個完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系，在當前無序區(qū)中選擇關鍵字最大（或最?。┑挠涗洝＜矗喊汛判蛭募年P鍵字存放在數(shù)組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稱大堆根//==========大根堆調整函數(shù)=======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指向它//現(xiàn)在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--){//對當前無序區(qū)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);}//==========主函數(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，結束程序}printf("Sortreult:");output_int(R);}運行結果：直接插入排序：冒泡法排序：快速排序：直接選擇排序：堆排序：歸并排序：實驗心得：關于排序的數(shù)據(jù)結構實驗。感覺各種排序方法都有各自的特點。直接插入排序是根據(jù)前面一個數(shù)的位置和后面一個相比較直接排而冒泡法則要經(jīng)過n*(n-1)次每次確定一個數(shù)的位置但是這種方法有點復雜要循環(huán)n次，而快速排序則是從中間到兩邊任選一個數(shù)出來把小的排前面大的排后面然后重復以上過程這樣可以有效地節(jié)約時間每一步都為下一步節(jié)約了時間。而直接選擇排序有兩個序列也是每一步都為下一步節(jié)約了世界堆排序巧妙地利用了樹中雙親與孩子的關系歸并排序則是發(fā)散的通過遞歸成2的n次方排，通過這幾種排序方法我更加了解了排序也知道了許多數(shù)據(jù)結構。目錄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顯示鏈表中的元素個數(shù)（計數(shù)）9165624結果分析1098784.1單鏈表的結構1050594.2單鏈表的操作特點10204464.2.1順鏈操作技術10123154.2.2指針保留技術10131654.3鏈表處理中的相關技術10226005設計體會及今后的改進意見1119571參考文獻1214900附錄代碼：131選題背景陳火旺院士把計算機60多年的發(fā)展成就概括為五個“一”：開辟一個新時代信息時代，形成一個新產(chǎn)業(yè)信息產(chǎn)業(yè)，產(chǎn)生一個新科學計算機科學與技術，開創(chuàng)一種新的科研方法計算方法，開辟一種新文化計算機文化，這一概括深刻影響了計算機對社會發(fā)展所產(chǎn)生的廣泛而深遠的影響。數(shù)據(jù)結構和算法是計算機求解問題過程的兩大基石。著名的計算機科學家P.Wegner指出，“在工業(yè)革命中其核心作用的是能量，而在計算機革命中其核心作用的是信息”。計算機科學就是“一種關于信息結構轉換的科學”。信息結構（數(shù)據(jù)結構）是計算機科學研究的基本課題，數(shù)據(jù)結構又是算法研究的基礎。2方案與論證2.1鏈表的概念和作用鏈表是一種鏈式存儲結構，鏈表屬于線性表，采用鏈式存儲結構，也是常用的動態(tài)存儲方法。鏈表中的數(shù)據(jù)是以結點來表示的，每個結點的構成：元素(數(shù)據(jù)元素的映象)+

指針(指示后繼元素存儲位置)，元素就是存儲數(shù)據(jù)的存儲單元，指針就是連接每個結點的地址數(shù)據(jù)。以“結點的序列”表示線性表稱作線性鏈表（單鏈表）單鏈表是鏈式存取的結構，為找第i個數(shù)據(jù)元素，必須先找到第i-1個數(shù)據(jù)元素。因此，查找第i個數(shù)據(jù)元素的基本操作為：移動指針，比較j和i單鏈表1、鏈接存儲方法鏈接方式存儲的線性表簡稱為鏈表（LinkedList）。鏈表的具體存儲表示為：①用一組任意的存儲單元來存放線性表的結點（這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的）②鏈表中結點的邏輯次序和物理次序不一定相同。為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還必須存儲指示其后繼結點的地址（或位置）信息（稱為指針（pointer）或鏈(link)）注意：鏈式存儲是最常用的存儲方式之一，它不僅可用來表示線性表，而且可用來表示各種非線性的數(shù)據(jù)結構。2、鏈表的結點結構┌───┬───┐│data│next│└───┴───┘data域--存放結點值的數(shù)據(jù)域next域--存放結點的直接后繼的地址（位置）的指針域（鏈域）注意：①鏈表通過每個結點的鏈域將線性表的n個結點按其邏輯順序鏈接在一起的。②每個結點只有一個鏈域的鏈表稱為單鏈表（SingleLinkedList）。3、頭指針head和終端結點指針域的表示單鏈表中每個結點的存儲地址是存放在其前趨結點next域中，而開始結點無前趨，故應設頭指針head指向開始結點。注意：鏈表由頭指針唯一確定，單鏈表可以用頭指針的名字來命名。終端結點無后繼，故終端結點的指針域為空，即NULL。2.2實驗的基本要求（軟硬件）用VC++6.0軟件平臺，操作系統(tǒng)：WindowsXP硬件：內存要求：內存大小在256MB，其他配置一般就行。2.3算法的設計思想（a）定義一個創(chuàng)建鏈表的函數(shù)，通過該頭插法創(chuàng)建一個帶頭結點的鏈表，在接下來的鏈表操作中使用。（b）定義輸出鏈表的算法，遍歷結點的指針域判斷是否為空，如果不為空則輸出其數(shù)據(jù)域，直到指針域為空為止。（c）定義一個遍歷查找的算法，通過遍歷的數(shù)據(jù)域，分別與要查詢的元素進行比較，如果查找到則返回并輸出，如入查找失敗則返回錯誤提示信息。（d）定義插入結點的算法，首先查找指針域為空的結點，并申請空間插入在結點的后邊，并且將其指針域置空。（e）定義刪除節(jié)點的操作，這個算法用于對鏈表中某個多余節(jié)點的刪除工作，其關鍵在于前驅結點的保留，查找到需刪除的結點，將其刪除，并將其后繼結點連到其前驅結點。2.4相關圖例2.4.1單鏈表的結點結構如圖2-1所示,為單鏈表的結點結構示意圖：Data域Next域Data域Next域圖2-1單鏈表的結點結構2.4.2算法流程圖如圖2-2所示，為此算法流程圖：開始開始定義結構體Node定義結構體Node構建各種對鏈表操作的函數(shù)（插入、刪除、查找、輸出），并寫出相應的算法及實現(xiàn)過程創(chuàng)建一個單鏈表，用于之前所定義的函數(shù)對其進行操作按要求輸出結果結束圖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顯示鏈表中的元素個數(shù)（計數(shù)）圖3-7輸出長度4結果分析4.1單鏈表的結構一般情況下，使用鏈表，只關心鏈表中結點間的邏輯順序，并不關心每個結點的實際存儲位置，因此通常情況下用箭頭來表示鏈域中的指針，于是鏈表就可以更直觀的畫成用箭頭鏈接起來的結點序列，如下圖所示：ABABCDE^H圖4-1單鏈表的示例圖4.2單鏈表的操作特點4.2.1順鏈操作技術從“頭”開始，訪問單鏈表L中的結點i（p指向該節(jié)點）時，由于第i個結點的地址在第i-1個結點（pre指向該結點，為p的前驅）的指針域中存放，查找必須從單鏈表的“首結點”開始（p=L）；通過p=p->next并輔助計數(shù)器來實現(xiàn)。4.2.2指針保留技術通過對第i個結點進行插入、刪除等操作時，需要對第i-1個結點的指針域進行鏈址操作（pre->next），因此在處理過程中始終需要維持當前指針p與其前驅指針pre的關系，將這種技術稱為“指針保留技術”。4.3鏈表處理中的相關技術1）單鏈表與多重鏈表的差別在于指針域的個數(shù)。2）判斷當前結點p是否為表尾。一半鏈表中，p結點是表尾的條件是：該節(jié)點的后繼結點為空指針，即p->next==NULL;3）鏈表的長度并未顯示保存。由于鏈表是動態(tài)生成的結構，其長度要通過順鏈查找到表尾得到。因此在處理鏈表時，往往是以當前處理結點p是否為表尾作為控制條件，而不是長度n作為控制條件。5設計體會及今后的改進意見通過這次實驗加深了我對于單鏈表的進一步了解，了解到了單鏈表在內存中的存儲結構，最重要的是學會了如何運用C語言將單鏈表的建立，插入、刪除、添加等操作。在程序實現(xiàn)中也遇到了一些困難，在單鏈表初始化時，使用了0作為結束輸入符，導致單鏈表不能存儲數(shù)據(jù)0；單鏈表中只能存儲相同類型的數(shù)據(jù)，在存儲不同類型的數(shù)據(jù)時需要改變輸入結束標志，程序通用性比較差。在進行程序設計的時候沒有考慮好刪除和查找的方式，只進行了輸入元素的查找和刪除，而且進行鏈表的插入時，只考慮了頭插法在結尾插入，而沒有考慮輸入結點插入等，程序的靈活性比較低。通過這次課程設計，讓我充分認識到數(shù)據(jù)結構在編寫程序方面的重要地位。不僅僅是單鏈表的操作，還有棧和隊列等特殊的單鏈表操作，以及其他一些常用的數(shù)據(jù)結構對于程序的效率和內存使用有很大的幫助。我希望在接下來的學習中收獲更多的東西。參考文獻[1]耿國華.數(shù)據(jù)結構--用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();/*測試函數(shù)*/voidmain_menu();//主菜單函數(shù)voidCreatFromHead(LinkList*l);/*頭插法建立單鏈表*/voidInsert(LinkListl);//單鏈表的插入voidPrint(LinkListl);/*單鏈表的輸出*/intSearch(LinkListl,Elemtypee);//查找指定的元素voidDeletelist(Lin