陜西高等教育自學(xué)考試

1、陜西省高等教育自學(xué)考試計算機(jī)軟件基礎(chǔ)課程實踐環(huán)節(jié)考核報告準(zhǔn)考證號： 考生姓名：張小飛所在專業(yè)：通信工程 專業(yè)層次：本科考核地點：西安電子科技大學(xué) 考核時間：2010年5月16日考核桌（機(jī)）號： 同組考核者姓名： 實踐考核評語及成績評定（由教師填寫）教師簽名：年 月 日主考院校：西安電子科技大學(xué)一、 實驗名稱：鏈表的插入和刪除二、 目的與要求： 線性表是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。其邏輯結(jié)構(gòu)是數(shù)據(jù)元素的有序序列：（aa.a）。三、 具體題目：#include<stdio.h>#include"malloc.h"#include<iostream.h>

2、#define M 5#define CHA 0 /插入位置#define del 1/刪除位置 #define NULL 0void main()/printf("hello word!");typedef struct nodechar data;struct node *link;NODE;NODE *FR5;/數(shù)據(jù)結(jié)構(gòu) 的定義for(int j=0;j<5;j+)FRj=(NODE *)malloc(sizeof(NODE);/*NODE *FR1;NODE *FR2;NODE *FR3;NODE *FR4;*/初始化鏈表 的定義FR0->data=&#

3、39;A'FR1->data='B'FR2->data='C'FR3->data='D'FR4->data='E'/向數(shù)據(jù)區(qū)寫入字符printf("/n");printf(" 這是單鏈表 簡單實驗an");printf("/n");for(int i=0;i<5;i+)/printf("%s",FRi->data);printf("這是第 %d 個元素： %cn",i+1,FRi->

4、data);/顯示鏈表 的元素/NODE *head,*P;P=(NODE *)malloc(sizeof(NODE);head=FR0;for(int s=0;s<M-1;s+)FRs->link=FRs+1;FRM->link=NULL;/建立連接 的 過程 /test/printf("this is a test %can",FR0->link->link->data);/插入char X;X='m'if(CHA=0)P->data=X;P->link=head;head=P;printf("第

5、一個插入元素為： %can",head->data);head->link=FRdel+1;free(FRdel);printf("刪除B 顯示 下一個元素 ： %can",head->link->data);for(int f=0;f<5;f+)delete(FRi);#include <iostream.h>#include <conio.h>#define MAXSIZE 50/*typedef struct /定義排序表的結(jié)構(gòu)int elemwordMAXSIZE; /數(shù)據(jù)元素關(guān)鍵字int length

6、; /表中當(dāng)前元素的個數(shù)SqList;void InitialSqList(SqList &L, int R, int n)/表初始化int i;L.length = n;for(i = 1; i <= L.length; i+)L.elemwordi = Ri-1;*/void SelectSort (int R, int n)/選擇排序,升序/ 對記錄序列R0.n-1作簡單選擇排序int min;int j;for (int i = 0; i < n; i+) / 選擇第i小的記錄，并交換j = i;min = Ri;for (int k = i; k < n;

7、k+) / 在Ri.n-1中選擇最小的記錄if (Rk < min) min = Rk;j = k;if (i != j) / 與第i個記錄交換int temp = Ri;Ri = Rj;Rj = temp;/ SelectSortvoid BubbleSort (int R, int n)/冒泡排序,升序/ 設(shè)待排記錄放在R0到Rn-1中for(int i = 0; i < n; i+) for(int j = 0; j < n - i - 1; j+) if(Rj > Rj+1)/ 交換元素,每次尋找最大的讓其沉底int temp = Rj+1;Rj+1 = Rj;

8、Rj = temp;/ BubbleSortvoid BiInsertionSort (int R, int n)/折半插入排序,升序int low, high, temp, m;for (int i = 1; i < n; i+) temp = Ri; / 將Ri暫存到templow = 0; high = i - 1;while (low <= high) / 在R0.i-1中折半查找插入位置 m = (low + high) / 2; / 折半if (temp < Rm) high = m - 1; / 插入點在低半?yún)^(qū)else low = m + 1; / 插入點在高半

9、區(qū)for (int j = i - 1; j > high; j-)Rj + 1 = Rj; / 記錄后移Rhigh + 1 = temp; / 插入/ for/ BInsertSortint SeqSearch (int R, int n, int m)/順序從前往后查找for (int i = 0; i < n; i+)if (Ri = m)return i+1;return -1;/找不到則返回-1int BiSearch (int R, int n, int m)/折半查找int low, high, mid;low = 0;high = n - 1;while (low

10、<= high)mid = (low + high) / 2;if (Rmid = m)return mid+1;if (m > Rmid)low = mid + 1;elsehigh = mid - 1;return -1;/找不到則返回-1int Partition (int R, int low, int high) int pivotkey = Rlow;/ 樞軸 while (low < high) while (low < high) && (Rhigh >= pivotkey)/ 從右向左搜索high-;Rlow = Rhigh;wh

11、ile (low < high) && (Rlow <= pivotkey)/ 從左向右搜索low+;Rhigh = Rlow;Rlow = pivotkey;return low; / 返回樞軸所在位置/ Partitionvoid QSort (int R, int s, int t) / 對記錄序列Rs.t進(jìn)行快速排序if (s < t) / 長度大于1int pivotloc = Partition(R, s, t);/ 對 Rs.t 進(jìn)行一次劃分QSort(R, s, pivotloc - 1);/ 對低子序列遞歸排序，pivotloc是樞軸位置QS

12、ort(R, pivotloc + 1, t);/ 對高子序列遞歸排序/ QSortvoid HeapAdjust(int R, int s, int m)/已知Rs.m中除Rs之外均滿足堆的定義,本函數(shù)調(diào)整Rs/使Rs.m成為一個大頂堆int j,rc;rc=Rs;for(j=2*s;j<=m;j*=2) /沿關(guān)鍵字叫大的結(jié)點向下篩選if(j<m&&Rj<Rj+1)+j; /j為關(guān)鍵字較大的記錄的下標(biāo)if(rc>=Rj)break; /rc應(yīng)插入在位置s上Rs=Rj;s=j;Rs=rc; /插入void HeapSort(int R, int n)/對

13、順序表R做堆排序int i,t;for(i=n/2;i>0;-i) /把R1.n建成大頂堆HeapAdjust(R,i,n);for(i=n;i>1;-i)/大頂堆t=R1; /將堆頂記錄和當(dāng)前未經(jīng)排序子序列R1.i R1=Ri; /中的最后一個記錄相互交換Ri=t;/此交換將最大元素放在末尾,即取出堆頂元素HeapAdjust(R,1,i-1); /將R1.i-1重新調(diào)整為大頂堆void main()char next = 'y'int n, i, m2;int *num;int *num2;int *num3;cout<<"請輸入元素個數(shù):

14、"<<endl;cin>>n;num = new intn;num2 = new intn;num3 = new intn + 1;cout<<"請依次輸入每個元素:"<<endl;for(i = 0; i < n; i+)cin>>numi;cout<<"您輸入的元素為:"<<endl;for(i = 0; i < n; i+)cout<<numi<<" "cout<<endl;for(i =

15、 0; i < n; i+)num2i=numi;cout<<"選擇排序:"<<endl;SelectSort(num2, n);for(i = 0; i < n; i+)cout<<num2i<<" "cout<<endl;for(i=0; i<n; i+)num2i=numi;cout<<"冒泡排序:"<<endl;BubbleSort(num2, n);for(i = 0; i < n; i+)cout<<nu

16、m2i<<" "cout<<endl;for(i = 0; i < n; i+)num2i=numi;cout<<"折半插入排序:"<<endl;BiInsertionSort(num2, n);for(i = 0; i < n; i+)cout<<num2i<<" "cout<<endl;for(i = 0; i < n; i+)num2i=numi;cout<<"快速排序:"<<endl

17、;QSort(num2, 0, n-1);for(i = 0; i < n; i+)cout<<num2i<<" "cout<<endl;for(i = 0; i < n; i+)num3i + 1=numi;cout<<"堆排序:"<<endl;HeapSort(num3, n);for(i = 0; i < n; i+)cout<<num3i+1<<" "cout<<endl;cout<<"您輸入的元素為:"<<endl;for(i = 0; i < n; i+)cout<<numi<<" "cout<<endl;while(next != 'n')cout<<"請輸入要查找的元素:"<<endl;cin>>m2;cout<<"順序查找(原始序列):"<<endl<<SeqSearch(num, n, m2)<<endl;cout<