1、參考醫學實驗一、單鏈表的插入和刪除一、目的了解和掌握線性表的邏輯結構和鏈式存儲結構，掌握單鏈表的基本算法及相關的時間性能分析。二、要求：建立一個數據域定義為字符串的單鏈表，在鏈表中不允許有重復的字符串；根據輸入的字符串，先找到相應的結點，后刪除之。三、程序源代碼#include"stdio.h"#include"string.h"#include"stdlib.h"#include"ctype.h"typedef struct node/定義結點char data10;/結點的數據域為字符串struct node

2、*next;/結點的指針域ListNode;typedef ListNode * LinkList; /自定義LinkList單鏈表類型LinkList CreatListR1();/函數，用尾插入法建立帶頭結點的單鏈表參考醫學ListNode *LocateNode();/函數，按值查找結點void DeleteList();/函數，刪除指定值的結點void printlist();/函數，打印鏈表中的所有值void DeleteAll();/函數，刪除所有結點，釋放內存/=主函數 =void main()char ch10,num10;LinkList head;head=CreatLis

3、tR1();/用尾插入法建立單鏈表，返回頭指針printlist(head);/遍歷鏈表輸出其值printf(" Delete node (y/n):");/輸入“ y”或“ n”去選擇是否刪除結點scanf("%s",num);if(strcmp(num,"y")=0 | strcmp(num,"Y")=0) printf("Please input Delete_data:");scanf("%s",ch);/輸入要刪除的字符串DeleteList(head,ch);pr

4、intlist(head);DeleteAll(head);/刪除所有結點，釋放內存參考醫學/=用尾插入法建立帶頭結點的單鏈表=LinkList CreatListR1(void)char ch10;LinkListhead=(LinkList)malloc(sizeof(ListNode);/ 生成頭結點ListNode *s,*r,*pp;r=head;r->next=NULL;printf("Input # to end "); / printf("Please input Node_data:");輸入“ #”代表輸入結束scanf(&qu

5、ot;%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 # to end ");參考醫學printf("Please input Node_data:

6、");scanf("%s",ch);return head;/返回頭指針/=按值查找結點，找到則返回該結點的位置，否則返回NULL=ListNode *LocateNode(LinkList head, char *key)ListNode *p=head->next; /從開始結點比較while(p&&strcmp(p->data,key)!=0 ) /直到p 為NULL或p->data為key止p=p->next;/掃描下一個結點return p;/若 p=NULL則查找失敗，否則p 指向找到的值key 的結點/=刪除帶

7、頭結點的單鏈表中的指定結點=void DeleteList(LinkList head,char *key)ListNode *p,*r,*q=head;p=LocateNode(head,key);/按key值查找結點的if(p=NULL ) /若沒有找到結點，退出參考醫學printf("position error");exit(0);while(q->next!=p)/p為要刪除的結點， q 為 p 的前結點q=q->next;r=q->next;q->next=r->next;free(r);/釋放結點/=打印鏈表 =void prin

8、tlist(LinkList head)ListNode *p=head->next;while(p)printf("%s,",p->data);p=p->next;/從開始結點打印printf("n");/=刪除所有結點，釋放空間=void DeleteAll(LinkList head)參考醫學ListNode *p=head,*r;while(p->next)r=p->next;free(p);p=r;free(p);運行結果：加的添加結點的代碼：int Insert(ListNode *head)/ the inse

9、rt functionListNode *in,*p,*q;int wh;printf("input the insert node:");參考醫學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)return 0;scanf("%s",in->data)

10、;printf("input the place where you want to insert you data:");scanf("%d",&wh);for(p=head;wh>0;p=p->next,wh-);q=p->next;p->next=in;in->next=q;return 1;參考醫學運行結果：最后提示為 OK 添加成功。實驗心得：這個實驗中 主要修改的是 ch 和 num 把它們由指針改成數組 因為不改的話在后面 delect函數中會出現沒有地址的情況 找不到地址就不能執行功能 然后把 loc

11、ate函數的判斷語句改一下 避免矛盾的出現。參考醫學實驗二、二叉樹操作一、目的掌握二叉樹的定義、性質及存儲方式，各種遍歷算法。二、要求采用二叉樹鏈表作為存儲結構，完成二叉樹的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結點總數的操作。三、程序源代碼#include"stdio.h"#include"string.h"#define Max 20/typedef struct nodechar data;struct node *lchild,*rchild;結點的最大個數BinTNode;/自定義二叉樹的結點類型typedef BinTNod

12、e *BinTree;/定義二叉樹的指針int NodeNum,leaf;/NodeNum為結點數，leaf為葉子數/=基于先序遍歷算法創建二叉樹=/= 要求輸入先序序列，其中加入虛結點“#”以示空指針的位置=參考醫學BinTree CreatBinTree(void)BinTree T;char ch;if(ch=getchar()='#')return(NULL);/讀入 #，返回空指針elseT=(BinTNode *)malloc(sizeof(BinTNode); / T->data=ch;生成結點T->lchild=CreatBinTree();/構造左

13、子樹T->rchild=CreatBinTree();/構造右子樹return(T);/=NLR 先序遍歷 =void Preorder(BinTree T)if(T) printf("%c",T->data);/訪問結點Preorder(T->lchild);/先序遍歷左子樹Preorder(T->rchild);/先序遍歷右子樹參考醫學/=LNR 中序遍歷 =void Inorder(BinTree T)if(T) Inorder(T->lchild);/中序遍歷左子樹printf("%c",T->data);/訪

14、問結點Inorder(T->rchild);/中序遍歷右子樹/=LRN 后序遍歷 =void Postorder(BinTree T)if(T) Postorder(T->lchild);/后序遍歷左子樹Postorder(T->rchild);/后序遍歷右子樹printf("%c",T->data);/訪問結點/= 采用后序遍歷求二叉樹的深度、結點數及葉子數的遞歸算法=int TreeDepth(BinTree T)參考醫學int hl,hr,max;if(T)hl=TreeDepth(T->lchild);/ 求左深度hr=TreeDept

15、h(T->rchild);/求右深度max=hl>hr? hl:hr;/取左右深度的最大值NodeNum=NodeNum+1;/求結點數if(hl=0&&hr=0) leaf=leaf+1;/ 若左右深度為0，即為葉子。return(max+1);else return(0);/= 利用“先進先出”（FIFO）隊列，按層次遍歷二叉樹 =void Levelorder(BinTree T)int front=0,rear=1;BinTNode *cqMax,*p;/定義結點的指針數組cqcq1=T;/根入隊while(front!=rear)front=(front+

16、1)%NodeNum;p=cqfront;/出隊參考醫學printf("%c",p->data);/if(p->lchild!=NULL)rear=(rear+1)%NodeNum;出隊，輸出結點的值cqrear=p->lchild;/左子樹入隊if(p->rchild!=NULL)rear=(rear+1)%NodeNum;cqrear=p->rchild;/右子樹入隊/=主函數 =void main()BinTree root;int i,depth;printf("n");printf("Creat Bin_

17、Tree；Input preorder:");/ 輸入完全二叉樹的先序序列，/用#代表虛結點，如ABD#CE#F#root=CreatBinTree();/創建二叉樹，返回根結點do /從菜單中選擇遍歷方式，輸入序號。參考醫學printf("t* select *n");printf("t1: Preorder Traversaln");printf("t2: Iorder Traversaln");printf("t3: Postorder traversaln");printf("t4: P

18、ostTreeDepth,Node number,Leaf numbern");printf("t5: Level Depthn"); /按層次遍歷之前，先選擇4，求出該樹的結點數。printf("t0: Exitn");printf("t*n");scanf("%d",&i);/輸入菜單序號（ 0-5 ）switch (i)case 1: printf("Print Bin_tree Preorder: ");Preorder(root);/先序遍歷break;case 2:

19、 printf("Print Bin_Tree Inorder: ");Inorder(root);/中序遍歷break;case 3: printf("Print Bin_Tree Postorder: ");Postorder(root);/后序遍歷break;case 4: depth=TreeDepth(root);/求樹的深度及葉參考醫學子數printf("BinTreeDepth=%dBinTreeNodenumber=%d",depth,NodeNum);printf(" BinTree Leaf number

20、=%d",leaf);break;case 5: printf("LevePrint Bin_Tree: ");Levelorder(root);/按層次遍歷break;default: exit(1);printf("n"); while(i!=0);執行程序1. 先序遍歷2. 中序遍歷參考醫學3. 后序遍歷4. 結點數 葉子數 高度5.層次遍歷自己設計的：abdhl#m#i#e#jn#cf#ko#g#1.預計先序遍歷結果：abdhlmiejncfkog2.預計中序遍歷結果：lhmdibenjafokcg3.預計后序遍歷結果：lmhidnje

21、bokfgca4.結點數15 高度 5 葉子數6參考醫學實際結果：實驗心得 ：這次實驗主要是要讓我們熟練樹及其相關知識熟練掌握先序中序后序遍歷， 層次遍歷然后我們自己畫一個圖會實現以上功能 以及葉子數結點數還有高度的計算程序里面大量運用了遞歸以及隊的應用，參考醫學實驗三、圖的遍歷操作一、目的掌握有向圖和無向圖的概念；掌握鄰接矩陣和鄰接鏈表建立圖的存儲結構；掌握 DFS 及 BFS 對圖的遍歷操作；了解圖結構在人工智能、工程等領域的廣泛應用。二、要求采用鄰接矩陣和鄰接鏈表作為圖的存儲結構，完成有向圖和無向圖的 DFS 和 BFS 操作。三、DFS 和 BFS 的基本思想深度優先搜索法 DFS 的

22、基本思想：從圖 G 中某個頂點 Vo 出發，首先訪問 Vo，然后選擇一個與 Vo 相鄰且沒被訪問過的頂點 Vi 訪問，再從 Vi 出發選擇一個與 Vi 相鄰且沒被訪問過的頂點 Vj 訪問， 依次繼續。如果當前被訪問過的頂點的所有鄰接頂點都已被訪問，則回退到已被訪問的頂點序列中最后一個擁有未被訪問的相鄰頂點的頂點 W ，從 W 出發按同樣方法向前遍歷。直到圖中所有的頂點都被訪問。廣度優先算法 BFS 的基本思想： 從圖 G 中某個頂點 Vo 出發，首先訪問 Vo，然后訪問與 Vo 相鄰的所有未被訪問過的頂點 V1 ，V2， ， Vt ；再依次訪問與 V1， V2， ， Vt 相鄰的起且未被參考醫

23、學訪問過的的所有頂點。如此繼續，直到訪問完圖中的所有頂點。四、程序源代碼1鄰接矩陣作為存儲結構的程序示例#include"stdio.h"#include"stdlib.h"#define MaxVertexNum 100/定義最大頂點數typedef structchar vexsMaxVertexNum;/頂點表int edgesMaxVertexNumMaxVertexNum;/鄰接矩陣，可看作邊表int n,e;/圖中的頂點數n 和邊數eMGraph;/用鄰接矩陣表示的圖的類型/=建立鄰接矩陣 =void CreatMGraph(MGraph *

24、G)int i,j,k;char a;printf("Input VertexNum(n) and EdgesNum(e): ");scanf("%d,%d",&G->n,&G->e);/輸入頂點數和邊數scanf("%c",&a);printf("Input Vertex string:");for(i=0;i<G->n;i+)參考醫學scanf("%c",&a);G->vexsi=a;/讀入頂點信息，建立頂點表for(i=0;i&

25、lt;G->n;i+)for(j=0;j<G->n;j+)G->edgesij=0; / 初始化鄰接矩陣 printf("Input edges,Creat Adjacency Matrixn");for(k=0;k<G->e;k+) /讀入e 條邊，建立鄰接矩陣scanf("%d%d",&i,&j);/輸入邊（ Vi ，Vj ）的頂點序號G->edgesij=1;G->edgesji=1;/ 若為無向圖，矩陣為對稱矩陣；若建立有向圖，去掉該條語句/=定義標志向量，為全局變量=typedef

26、 enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度優先遍歷的遞歸算法=void DFSM(MGraph *G,int i) / 以 Vi 為出發點對鄰接矩陣表示的圖 G進行 DFS搜索，鄰接矩陣是 0，1 矩陣參考醫學int j;printf("%c",G->vexsi);/訪問頂點Vivisitedi=TRUE;/置已訪問標志for(j=0;j<G->n;j+)/依次搜索Vi的鄰接點if(G->edgesij=1 && ! visitedj)DFSM(G,j);/

27、（Vi ，Vj ） E，且Vj未訪問過，故 Vj 為新出發點void DFS(MGraph *G)int i;for(i=0;i<G->n;i+)visitedi=FALSE;/標志向量初始化for(i=0;i<G->n;i+)if(!visitedi)DFSM(G,i);/Vi/未訪問過以 Vi 為源點開始DFS搜索/=BFS：廣度優先遍歷 =void BFS(MGraph *G,int k)/以 Vk為源點對用鄰接矩陣表示的圖G進行廣度優先搜索int i,j,f=0,r=0;參考醫學int cqMaxVertexNum;/定義隊列for(i=0;i<G->

28、;n;i+)visitedi=FALSE;/標志向量初始化for(i=0;i<G->n;i+)cqi=-1;/隊列初始化printf("%c",G->vexsk);/訪問源點Vkvisitedk=TRUE;cqr=k;/Vk已訪問，將其入隊。注意，實際上是將其序號入隊while(cqf!=-1) /隊非空則執行i=cqf; f=f+1;/Vf出隊for(j=0;j<G->n;j+)/依次Vi的鄰接點Vjif(G->edgesij=1 && !visitedj) /Vj未訪問printf("%c",G-&

29、gt;vexsj);/訪問Vjvisitedj=TRUE;r=r+1; cqr=j;/訪問過Vj入隊/=main=void main()參考醫學int i;MGraph *G;G=(MGraph*)malloc(sizeof(MGraph);/為圖 G申請內存空間CreatMGraph(G); / printf("Print Graph DFS: ");建立鄰接矩陣DFS(G);/深度優先遍歷printf("n");printf("Print Graph BFS: ");BFS(G,3);/以序號為3 的頂點開始廣度優先遍歷print

30、f("n");參考醫學調試結果：自己畫的圖：1 對應頂點下標0 以此類推9 對應下標 8預計運行結果：DFS:012345678參考醫學BFS:324105687對應我這個圖：DFS：123456789BFS：435216798實驗心得：圖在數據結構中是相當重要的一部分聯系很多現實問題圖的根本就是頂點和邊通過頂點和邊建立鄰接矩陣以及鄰接鏈表廣度搜索和深度搜索是此算法著重關注的地方。要學會自己畫圖然后寫出這兩種搜索的結果， 程序中用了隊的算法是亮點 通過 TRUE和 FAUSE 來標記頂點是否以及訪問避免重復參考醫學實驗四、排序一、目的掌握各種排序方法的基本思想、排序過程、算

31、法實現，能進行時間和空間性能的分析， 根據實際問題的特點和要求選擇合適的排序方法。二、要求實現直接排序、冒泡、直接選擇、快速、堆、歸并排序算法。比較各種算法的運行速度。三、程序示例#include"stdio.h"#include"stdlib.h"#define Max 100/假設文件長度typedef struct/定義記錄類型int key;/關鍵字項RecType;typedef RecType SeqListMax+1; /SeqList為順序表，表中第0個元素作為哨兵int n;/順序表實際的長度1、直接插入排序的基本思想： 每次將一個待排

32、序的記錄， 按其關鍵字大小插入到前面已排序好的子文件中的適當位置，直到全部記錄插入完成為止。參考醫學/=直接插入排序法 =void InsertSort(SeqList R)/對順序表 R 中的記錄 R1n 按遞增序進行插入排序int i,j;for(i=2;i<=n;i+)/依次插入R2， ， Rnif(Ri.key<Ri-1.key) /若Ri.key大于等于有序區中所有的keys，則Ri留在原位R0=Ri;j=i-1;do /R0是 Ri從右向左在有序區的副本R1i-1中查找Ri的位置Rj+1=Rj;/將關鍵字大于Ri.key的記錄后移j-;while(R0.key<R

33、j.key);/當 Ri.key Rj.key是終止Rj+1=R0;/Ri插入到正確的位置上/endif2、冒泡排序的基本思想： 設想被排序的記錄數組R1n 垂直排序。根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組R，凡掃描到違反本原則的輕氣泡，就使其向上“漂浮”（交換），如此反復進行，直到最后任意兩個氣泡都是輕者在上，重者在下為參考醫學止。/=冒泡排序 =typedef enumFALSE,TRUE Boolean; /FALSE為 0，TRUE為 1void BubbleSort(SeqList R)/自下向上掃描對R做冒泡排序int i,j;Boolean exchange;for(

34、i=1;i<n;i+) /exchange=FALSE;for(j=n-1;j>=i;j-)/交換標志最多做 n-1 趟排序本趟排序開始前，交換標志應為假對當前無序區 Ri n自下向上掃描if(Rj+1.key<Rj.key)/兩兩比較，滿足條件交換記錄R0=Rj+1;/R0不是哨兵，僅做暫存單元Rj+1=Rj;Rj=R0;exchange=TRUE;/發生了交換，故將交換標志置為真if(!exchange)/本趟排序未發生交換，提前終止算法return;參考醫學/endfor （為循環）3、快速排序的基本思想：在待排序的n 個記錄中任取一個記錄（通常取第一個記錄），把該記錄

35、作為支點（又稱基準記錄）（ pivot），將所有關鍵字比它小的記錄放置在它的位置之前，將所有關鍵字比它大的記錄放置在它的位置之后 (稱之為一次劃分過程)。之后對所分的兩部分分別重復上述過程，直到每部分只有一個記錄為止。/1.= 一次劃分函數 =int Partition(SeqList R,int i,int j) /對 Ri j 做一次劃分，并返回基準記錄的位置RecType pivot=Ri;/用第一個記錄作為基準while(i<j)/從區間兩端交替向中間掃描，直到i=jwhile(i<j &&Rj.key>=pivot.key)/基準記錄 pivot相當

36、與在位置 i 上j-;/從右向左掃描，查找第一個關鍵字小于pivot.key的記錄Rjif(i<j)/ 若找到的 Ri+=Rj; /Rj.key < pivot.key交換 Ri 和 Rj，則，交換后i指針加1while(i<j&&Ri.key<=pivot.key)/ 基準記錄參考醫學pivot相當與在位置j 上i+;/從左向右掃描，查找第一個關鍵字小于pivot.key的記錄 Riif(i<j)/若找到的 Ri.key > pivot.key，則Rj-=Ri; /交換Ri和Rj，交換后j指針減1Ri=pivot;/此時， i=j，基準記錄

37、已被最后定位return i;/返回基準記錄的位置/2.= 快速排序 =void QuickSort(SeqList R,int low,int high)/Rlow.high快速排序int pivotpos;/劃分后基準記錄的位置if(low<high) /僅當區間長度大于1 時才排序pivotpos=Partition(R,low,high); /對Rlow.high做一次劃分，得到基準記錄的位置QuickSort(R,low,pivotpos-1);/對左區間遞歸排序QuickSort(R,pivotpos+1,high);/對右區間遞歸排序4、 直接選擇排序的基本思想： 第 i 趟排序開始時，當前有序區和無序區分別為 R1i-1 和 Ri n （1i n-1 ），該趟排序