投稿
  1. 簡單一點首頁
  2. 編程

c語言中asl公式,c語言求ascll碼

小藍 • • 編程

本文目錄一覽：

請問這道二分查找的平均長度為什麼不能用公式直接算出?

設關鍵字個數為n，在各關鍵字等概率查找的前提下，

1、順序查找的平均查找長度asl=(n+1)/2，

2、在n趨於無窮大時，折半查找的asl=((n+1)log2(n+1))/n

–

1，當n大於50時，asl約等於log2(n+1)-1

3、設分塊查找中將長為

n

的表分成均等的

b

個塊，每塊

s

個元素，則

b

=

(n

/

s)上取整，如果索引表中採用順序查找，則asl=(b+1)/2+(s+1)/2；如果索引表中採用折半查找，則asl=(s+1)/2+log2(b+1)-1

2．C語言程序設計

#include “stdio.h”

#include “string.h”

#include “stdlib.h”

#define NULL 0

#define TRUE 1

#define FALSE 0

typedef struct bitnode{

int data;

int sl; /*查找長度*/

struct bitnode *lchild,*rchild;

}bitnode,*bitree;

/*二杈排序樹的查找*/

int searchbst(bitree t,int key,bitree f,bitree *p){

/*在以t為根的樹中查找關鍵字為key的結點,查找成功返回TRUE,

則指針p指向該結點,否則指向上次訪問的最後一個結點,返回FALSE,

指針f指向t的雙親,初始調用值為NULL*/

if(!t){

*p=f;

return FALSE;

}

else if(key==t-data){

*p=t;

return TRUE;

}

else if(keyt-data){

return searchbst(t-lchild,key,t,p);

}

else{

return searchbst(t-rchild,key,t,p);

}

}

/*二杈排序樹的插入*/

int insertbst(bitree *t,int e,int *count){

/*當t中不存在結點為e的時候插入e並返回TRUE,否則返回FALSE*/

bitree p,s;

if(!searchbst(*t,e,NULL,p)){

s=(bitree)malloc(sizeof(bitnode));

s-data=e;

s-lchild=s-rchild=NULL;

if(!p){

*t=s;

(*t)-sl=1;

(*count)++; /*結點個數加一*/

}

else if(ep-data){

s-sl=p-sl+1;

p-lchild=s;

(*count)++;

}

else{

s-sl=p-sl+1;

p-rchild=s;

(*count)++;

}

return TRUE;

}

else return FALSE;

}

/*二杈排序樹的結點刪除查找*/

int delschbst(bitree *t,int key,int *count){

if(!t) return FALSE;

else{

if(key==(*t)-data)

return deletebst(t,count);

else if(key(*t)-data)

return delschbst(((*t)-lchild),key,count);

else if(key(*t)-data)

return delschbst(((*t)-rchild),key,count);

}

}

/*二杈排序樹的結點刪除函數*/

int deletebst(bitree *p,int *count){

bitree q,s;

/*右子樹為空只需重接它的左子樹*/

if(!(*p)-rchild){

q=*p;

*p=(*p)-lchild;

(*count)–;/*結點個數減一*/

free(q);

}

/*右子樹為空只需重接它的左子樹*/

else if(!(*p)-lchild){

q=*p;

*p=(*p)-rchild;

(*count)–;

free(q);

}

/*左右子樹均非空*/

else{

q=*p;

s=(*p)-lchild;

while(s-rchild){

q=s;

s=s-rchild;

}

(*p)-data=s-data;

if(q!=(*p)) q-rchild=s-lchild;

else q-lchild=s-lchild;

(*count)–;

free(s);

}

return TRUE;

}

/*先序遞歸遍歷*/

int preorder(bitree t,int ssl){

if(t){

ssl+=t-sl;/*總查找長度*/

printf(“%d:%d “,t-data,t-sl);

ssl=preorder(t-lchild,ssl);

ssl=preorder(t-rchild,ssl);

}

return ssl;

}

main(){

int i,e;

int ssl=0,count=0;

float asl=0.0;

bitree t=NULL;

for(i=0;i12;i++){

scanf(“%d”,e);

insertbst(t,e,count);

}

printf(“preorder:\n”);

ssl=preorder(t,0);

asl=ssl/1.0/count;

printf(“\nASL=%d/%d=%f”,ssl,count,asl);

printf(“\n”);

/*刪除後遍歷*/

printf(“The key of delete:”);

scanf(“%d”,e);

delschbst(t,e,count);

ssl=preorder(t,0);

asl=ssl/1.0/count;

printf(“\nASL=%d/%d=%f”,ssl,count,asl);

printf(“\n”);

system(“pause”);

}

數據結構 哈希表，C語言解答

#include stdio.h

#includemalloc.h

#includestring.h

//#include

#define HASH_LEN 50 //哈希表的長度

#define M 47

#define NAME_NO 30 //人名的個數

typedef struct NAME

{

char *py; //名字的拼音

int k; //拼音所對應的整數

}NAME;

NAME NameList[HASH_LEN];

typedef struct hterm //哈希表

{

char *py; //名字的拼音

int k; //拼音所對應的整數

int si; //查找長度

}HASH;

HASH HashList[HASH_LEN];

/*———————–姓名（結構體數組）初始化———————————*/

void InitNameList()

{ int i;

char *f;

int r,s0;

NameList[0].py=”chenghongxiu”;

NameList[1].py=”yuanhao”;

NameList[2].py=”yangyang”;

NameList[3].py=”zhanghen”;

NameList[4].py=”chenghongxiu”;

NameList[5].py=”xiaokai”;

NameList[6].py=”liupeng”;

NameList[7].py=”shenyonghai”;

NameList[8].py=”chengdaoquan”;

NameList[9].py=”ludaoqing”;

NameList[10].py=”gongyunxiang”;

NameList[11].py=”sunzhenxing”;

NameList[12].py=”sunrongfei”;

NameList[13].py=”sunminglong”;

NameList[14].py=”zhanghao”;

NameList[15].py=”tianmiao”;

NameList[16].py=”yaojianzhong”;

NameList[17].py=”yaojianqing”;

NameList[18].py=”yaojianhua”;

NameList[19].py=”yaohaifeng”;

NameList[20].py=”chengyanhao”;

NameList[21].py=”yaoqiufeng”;

NameList[22].py=”qianpengcheng”;

NameList[23].py=”yaohaifeng”;

NameList[24].py=”bianyan”;

NameList[25].py=”linglei”;

NameList[26].py=”fuzhonghui”;

NameList[27].py=”huanhaiyan”;

NameList[28].py=”liudianqin”;

NameList[29].py=”wangbinnian”;

for (i=0;iNAME_NO;i++)// *求出各個姓名的拼音所對應的整數

{

s0=0;

f=NameList[i].py;

for (r=0;*(f+r) != ‘\0’;r++) //方法：將字符串的各個字符所對應的ASCII碼相加，所得的整數做為哈希表的關鍵字

s0=*(f+r)+s0;

NameList[i].k=s0;

}

}

/*———————–建立哈希表———————————*/

void CreateHashList()

{int i;

for ( i=0; iHASH_LEN;i++)//哈希表的初始化

{

HashList[i].py=””;

HashList[i].k=0;

HashList[i].si=0;

}

for (i=0; iNAME_NO;)

{

int sum=0;

int adr=(NameList[i].k) % M; //哈希函數

int d=adr;

if(HashList[adr].si==0) //如果不衝突

{

HashList[adr].k=NameList[i].k;

HashList[adr].py=NameList[i].py;

HashList[adr].si=1;

}

else //衝突

{

do

{

d=(d+((NameList[i].k))%10+1)%M; //偽散列

sum=sum+1; //查找次數加1

}while (HashList[d].k!=0);

HashList[d].k=NameList[i].k;

HashList[d].py=NameList[i].py;

HashList[d].si=sum+1;

}i++;

}

}

/*————————————-查找————————————*/

void FindList()

{ int r;

char name[20]={0};

int s0=0;

int sum=1;

int adr;

int d;

printf(“\n\n請輸入姓名的拼音: “); //輸入姓名

scanf(“%s”,name);

for ( r=0;r20;r++) //求出姓名的拼音所對應的整數(關鍵字)

s0+=name[r];

adr=s0 % M; //使用哈希函數

d=adr;

if(HashList[adr].k==s0) //分3種情況進行判斷

printf(“\n姓名:%s 關鍵字:%d 查找長度為: 1”,HashList[d].py,s0);

else if (HashList[adr].k==0)

printf(“無該記錄!”);

else

{

int g=0;

do

{

d=(d+s0%10+1)%M; //偽散列

sum=sum+1;

if (HashList[d].k==0)

{

printf(“無記錄! “);

g=1;

}

if (HashList[d].k==s0)

{

printf(“\n姓名:%s 關鍵字:%d 查找長度為:%d”,HashList[d].py,s0,sum);

g=1;

}

}while(g==0);

}

}

/*——————————–顯示哈希表—————————-*/

void Display()

{int i;

float average=0;

printf(“\n\n地址\t關鍵字\t\t搜索長度\tH(key)\t\t拼音 \n”); //顯示的格式

for( i=0; i15; i++)

{

printf(“%d “,i);

printf(“\t%d “,HashList[i].k);

printf(“\t\t%d “,HashList[i].si);

printf(“\t\t%d “,(HashList[i].k)%M);

printf(“\t %s “,HashList[i].py);

printf(“\n”);

}

// printf(“按任意鍵繼續顯示…\n”); //由於數據比較多，所以分屏顯示（以便在Win9x／DOS下能看到所有的數據）

// getch();

for( i=15; i30; i++)

{

printf(“%d “,i);

printf(“\t%d “,HashList[i].k);

printf(“\t\t%d “,HashList[i].si);

printf(“\t\t%d “,(HashList[i].k)%M);

printf(“\t %s “,HashList[i].py);

printf(“\n”);

}

// printf(“按任意鍵繼續顯示…\n”);

// getch();

for( i=30; i40; i++)

{

printf(“%d “,i);

printf(“\t%d “,HashList[i].k);

printf(“\t\t%d “,HashList[i].si);

printf(“\t\t%d “,(HashList[i].k)%M);

printf(“\t %s “,HashList[i].py);

printf(“\n”);

}

//printf(“按任意鍵繼續顯示…\n”);

//getch();

for( i=40; i50; i++)

{

printf(“%d “,i);

printf(“\t%d “,HashList[i].k);

printf(“\t\t%d “,HashList[i].si);

printf(“\t\t%d “,(HashList[i].k)%M);

printf(“\t %s “,HashList[i].py);

printf(“\n”);

}

for (i=0;iHASH_LEN;i++)

{average+=HashList[i].si;

average/=NAME_NO;

printf(“\n\n平均查找長度：ASL(%d)=%f \n\n”,NAME_NO,average);

}

}

/*——————————–主函數—————————-*/

void main()

{

/* ::SetConsoleTitle(“哈希表操作”); //Windows API函數,設置控制台窗口的標題

HANDLE hCon = ::GetStdHandle(STD_OUTPUT_HANDLE); //獲得標準輸出設備的句柄

::SetConsoleTextAttribute(hCon, 10|0); //設置文本顏色

*/

printf(“\n————————哈希表的建立和查找———————-“);

InitNameList();

CreateHashList ();

while(1)

{ char ch1;

printf(“\n\n”);

printf(” 1. 顯示哈希表\n”);

printf(” 2. 查找\n”);

printf(” 3. 退出\n”);

err:

scanf(“%c”,ch1);

if (ch1==’1′)

Display();

else if (ch1==’2′)

FindList();

else if (ch1==’3′)

return;

else

{

printf(“\n請輸入正確的選擇!”);

goto err;

}

}

}

如何計算哈希表的ASL

哈希表的建立計算：

key： 0 1 2 3 4 5 6 7 8 9 10 11 12

55 68 11 79 14 27 23 84 19 20 10 1

ASL=(1+1+1+1+1+1+3+2+2+6+11)/12

做此類題應注意哈希衝突函數怎麼構建，此題採用線性探測法，即如果產生衝突方法為H+1一直到沒有衝突為止。哈希表的建立；是依照key依次算對應的哈希碼。

線性表—解決衝突(c語言)

開放地址法

1.衝突處理方法一—開放地址法

當發生地址衝突後，求解下一個地址用：

ND

=(

D+di）%m　i=1,2,…,k(k=

m-1)

其中:

m為哈希表長度,di為增量序列。增量序列的不同取法，又構成不同的開放地址法。

(1)線性探測再散列

D

=

H(key);

ND

=

(D+di)%m;　di取1,2,3,……,m-1

線性探測再散列處理衝突的基本思想:若數據元素在存儲地址D發生衝突，則放到存儲地址（D＋1）%m；若又發生衝突則放到存儲地址（D＋2）%m；若再發生衝突則放到存儲地址（D＋3）%m；……；直到碰到第一個為空的存儲地址（D＋i）%m，則將數據元素存放在該存儲空間。

(2)二次探測再散列

D

=

H(key);

ND

=

(D+di)%m;　di取1*1,-1*1,2*2,-2*2,……,K*K,-K*K

(K≤m/2)

(3)雙散列法

首先使用第一個散列函數H1(key)及逆行那個散列，一旦發生衝突，則使用第二個函數H2(key)計算改項到達下一個存儲地址的增量，其取值p和key有關，範圍在1和m之間，並且與m互質的正整數。

D

=

H1(key);

p

=

H2(key);

ND

=

(D+p)%m;

值得提醒的是，對利用開放地址法查了衝突所產生的哈希表中刪除一個元素，不能簡單地直接刪除，因為這樣將截斷其它具有相同哈希地址的元素的查找地址，所以應設定一個特殊的標誌以表明該元素已被刪除。

不知道對你是否有用

為什麼高度為2,總結點數是3的二叉排序樹，查找成功的平均查找長度為: ASL = (1*1 + 2*2) / 3

1) 二叉排序樹,高度為2,總結點數n是3,如下:

        36

       /  \

      24   52

要成功查找結點36,需要比較一次,就是與36作比較,所以其查找長度是1

要成功查找結點24,需要比較兩次,分別與36和24作比較,所以其查找長度是2

要成功查找結點52,需要比較兩次,分別與36和52作比較,所以其查找長度是2

該二叉排序樹查找成功的總長度是 1*1+2*2

因為總結點數是3,所以,查找成功的平均查找長度為: ASL = (1*1 + 2*2) / 3 = 5/3

也可以用公式: ASL = [(n+1)/n] * log2(n+1) – 1 = [(3+1)/3] * log2(3+1) – 1 = 5/3

2) 二叉排序樹,高度為3,總結點數n是7,如下:

             36

          /      \

         24      52

        / \     /  \

      10   30  41  90

要成功查找結點36,需要比較一次,就是與36作比較,所以其查找長度是1

要成功查找結點24,需要比較兩次,分別與36和24作比較,所以其查找長度是2

要成功查找結點52,需要比較兩次,分別與36和52作比較,所以其查找長度是2

要成功查找結點10,需要比較三次,分別與36,24,10作比較,所以其查找長度是3

同樣,要成功查找點30,41,90,這每個結點都是需要比較三次,所以每個結點的查找長度都是3

該二叉排序樹查找成功的總長度是 1*1+2*2+3*4

因為總結點數是7,所以,查找成功的平均查找長度為: ASL = (1*1+2*2+3*4) / 7 = 17/7

也可以用公式: ASL = [(n+1)/n] * log2(n+1) – 1 = [(7+1)/7] * log2(7+1) – 1 = 17/7

3) 二叉排序樹,高度為4,總結點數n是15,如下:

 

               36

          /           \

         24            52

        /  \         /    \

      10    30      41     90

     / \    / \    /  \    / \

    8  12  28  31 38  42  61  91

逐個結點計數,查找成功的平均查找長度為:

ASL = (1*1 + 2*2 + 3*4 + 4*8) / 15 = 49/15

 

也可以用公式: ASL = [(n+1)/n] * log2(n+1) – 1 =  [(15+1)/15] * log2(15+1) – 1 = 49/15

原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-hant/n/242821.html

贊 (0)
打賞 微信掃一掃 微信掃一掃 支付寶掃一掃 支付寶掃一掃
小藍的頭像小藍
0 0
上一篇 2024-12-12 12:52
下一篇 2024-12-12 12:52

相關推薦

  • AES加密解密算法的C語言實現

    AES（Advanced Encryption Standard）是一種對稱加密算法，可用於對數據進行加密和解密。在本篇文章中，我們將介紹C語言中如何實現AES算法，並對實現過程進…

    NDMZX的頭像 NDMZX
    編程 2025-04-29

  • 學習Python對學習C語言有幫助嗎？

    Python和C語言是兩種非常受歡迎的編程語言，在程序開發中都扮演着非常重要的角色。那麼，學習Python對學習C語言有幫助嗎？答案是肯定的。在本文中，我們將從多個角度探討Pyth…

    LZXFS的頭像 LZXFS
    編程 2025-04-29

  • Python被稱為膠水語言

    Python作為一種跨平台的解釋性高級語言，最大的特點是被稱為”膠水語言”。 一、簡單易學 Python的語法簡單易學，更加人性化，這使得它成為了初學者的入…

    GNIUY的頭像 GNIUY
    編程 2025-04-29

  • OpenJudge答案1.6的C語言實現

    本文將從多個方面詳細闡述OpenJudge答案1.6在C語言中的實現方法，幫助初學者更好地學習和理解。 一、需求概述 OpenJudge答案1.6的要求是，輸入兩個整數a和b，輸出…

    IQCOK的頭像 IQCOK
    編程 2025-04-29

  • Python按位運算符和C語言

    本文將從多個方面詳細闡述Python按位運算符和C語言的相關內容，並給出相應的代碼示例。 一、概述 Python是一種動態的、面向對象的編程語言，其按位運算符是用於按位操作的運算符…

    WFJIT的頭像 WFJIT
    編程 2025-04-29

  • Python語言由荷蘭人為中心的全能編程開發工程師

    Python語言是一種高級語言，很多編程開發工程師都喜歡使用Python語言進行開發。Python語言的創始人是荷蘭人Guido van Rossum，他在1989年聖誕節期間開始…

    RQWRD的頭像 RQWRD
    編程 2025-04-28

  • Python語言設計基礎第2版PDF

    Python語言設計基礎第2版PDF是一本介紹Python編程語言的經典教材。本篇文章將從多個方面對該教材進行詳細的闡述和介紹。 一、基礎知識 本教材中介紹了Python編程語言的…

    GVEXI的頭像 GVEXI
    編程 2025-04-28

  • Python語言實現人名最多數統計

    本文將從幾個方面詳細介紹Python語言實現人名最多數統計的方法和應用。 一、Python實現人名最多數統計的基礎 1、首先，我們需要了解Python語言的一些基礎知識，如列表、字…

    DBGVW的頭像 DBGVW
    編程 2025-04-28

  • Python作為中心語言，在編程中取代C語言的優勢和挑戰

    Python一直以其簡單易懂的語法和高效的編碼環境而著名。然而，它最近的發展趨勢表明Python的使用範圍已經從腳本語言擴展到了從Web應用到機器學習等廣泛的開發領域。與此同時，C…

    GAQCK的頭像 GAQCK
    編程 2025-04-28

  • Python基礎語言

    Python作為一種高級編程語言擁有簡潔優雅的語法。在本文中，我們將從多個方面探究Python基礎語言的特點以及使用技巧。 一、數據類型 Python基礎數據類型包括整數、浮點數、…

    LGOOI的頭像 LGOOI
    編程 2025-04-28

發表回復

登錄後才能評論