數(shù)據(jù)結(jié)構(gòu)課本算法實現(xiàn)

1、線性結(jié)構(gòu)一 類型定義1 順序表 # define maxsize 100 typedef struct nodetypedef struct elemtype data; elemtype data maxsize; struct node * next; int length; slink;sqlist;2 單鏈表3雙鏈表typedef struct node elemtype data; struct node *prior,*next;dlink;二 基礎(chǔ)要點1單鏈表 2雙鏈表三 算法1 刪除順序表中重復(fù)元素void delsame( int a, int count ) int i,

2、j, k; if( n 1 ) j = 1; for( i =1; i n; i+ ) k = 0; while( k = j ) aj+ = ai; aj = 0 2 給無序表建有序索引表typedef struct indexelem keytype key; /關(guān)鍵字int sn; /序號indextype; /索引項indextype idx1.m; /索引表datatype data1.m; /原順序表for( i = 1; i 0 & idxj.key datai.key ) /把大于datai.key的所有idxj.key后移 idxj+1 = idxj;j-;idxj+1.ke

3、y = datai.key; /插入datai.key至idx中，并記下其序號iidxj+1.sn = i;3 逆置單鏈表void reverse( linklist h ) snode *p, *temp; p = h-next; h-next = null; while( p ) temp = p; p = p-next; temp-next = h-next; h-next = temp; void reverse( linklist h ) snode *p, *q, *temp; p = h-next; q = null; while( p ) temp = p; p = p-nex

4、t; temp-next = q; q = temp; h-next = q;4拆分單鏈表decompese( snode *l,snode *ha,snode *hb,snode *hc ) snode *temp,*p;p = l;ha = (snode*)malloc(sizeof(snode);hb = (snode*)malloc(sizeof(snode);hc = (snode*)malloc(sizeof(snode);ha-next = ha;hb-next = hb;hc-next = hc;while( p ) if( (p-data = a & p-data data

5、= a & p-data next; temp-next = ha-next; ha-next = temp; else if(p-data = 0 & p-data next; temp-next = hb-next; hb-next = temp;else temp = p; p = p-next; temp-next = hc-next; hc-next = temp; 5 刪除單鏈表重復(fù)元素void delete(linklist h) snode *p,*q,*r; p = h-next; while( p != null ) q=p; while ( q-next ) if ( q

6、-next-data = p-data ) r = q-next; q-next = r-next; free(r); else q = q-next; p = p-next; 6 合并單鏈表linklist merge(linklist a,linklist b) linklist c; snode *p,*q; p = a-next;q = b-next; c = a; c-next = null;free(b);while ( p & q ) if (p-datadata) s = p;p = p-next; else s = q;q = q-next; s-next = c-next;

7、 /*插入到c表的頭部*/ c-next = s;if ( p = null ) r = q;if ( q=null) r=p;while (r ) /* 將剩余的結(jié)點一個個摘下，插入到c表的頭部*/ s =r;r = r-next;s-next = c-next; c-next = s; 7 順序表和鏈表的遞歸輸出已知head是帶頭結(jié)點的單鏈表的頭指針，試編寫逆序/順序輸出表中各元素的遞歸算法；有一個整數(shù)數(shù)組an，按順序/逆序遞歸輸出數(shù)組中的各元素output( linklist *head ) if( head != null ) output( head-next ); printf(

8、“%d”,head-data ); /printf在output下為逆序輸出，在上為順序輸出 8帶訪問頻度的雙向鏈表的查找8 置逆棧void reverse( stack *s ) stack s1, s2; elemtype x; initstack( s1 ); initstack( s2 ); /將s棧中的內(nèi)容轉(zhuǎn)移到s1棧中 while( stackempty( s ) != 0 ) pop( s, x );push( s1, x ); /將s1棧中的內(nèi)容轉(zhuǎn)移到s2棧中 while( stackempty( s1 ) != 0 ) pop( s1, x );push( s2, x );

9、/將s2棧中的內(nèi)容轉(zhuǎn)移到s棧中 while( stackempty( s2 ) != 0 ) pop( s2, x );push( s, x ); 9 用棧實現(xiàn)隊列操作int enqueue( stack *s1, stack *s2, elemtype x ) if( s1-top = maxsize ) /隊列上溢 return -1; else push( s1, x ); return 0; int dequeue( stack *s1, stack *s2, elemtype *x ) elemtype y; while( stackempty(s1) != 0 ) /將s1的所有元

10、素退棧進入s2中 pop( s1, y ); push( s2, y ); pop( s2, x ); /將s2的棧頂元素退棧并賦給x while( stackempty(s2) != 0 ) /將s2余下的元素退棧后進入s1中 pop( s2, y ); push( s1, y ); 10共享存儲空間的棧的基本操作top1 = 1;top2 = m;int push( elemtype x, int i ) if( top1 = top2 - 1 ) return -1; /上溢出else if( i = 1 ) /對第一個棧進行進棧操作 top1+;ctop1 = x;else /對第二個

11、棧進行進棧操作 top2-;ctop2 = x;return 0;int pop( elemtype *x, int i ) if( i = 1 ) /對第一個棧進行出棧操作 if( top1 = 0 ) return -1; /棧1下溢出else x = ctop1;top1-;else /對第二個棧進行出棧操作 if( top2 = m + 1 ) return -1; /棧2下溢出else x = ctop2;top2+;return 0;void setnull( int i ) if( i = 1 ) top1 = 1;else top2 = m;11 括號匹配檢驗#define m

12、 100correct(exp,tag) int top=0; i=1; tag=1while(i0) tag=0;四 查找排序算法1 折半查找#define max 100typedef struct keytype key;elemtype date;rectype;typedef struct rectype rmax;int length;sqlist;int binary_search( sqlist r, keytype k ) int mid, low=1, high=r.length； while( low = high ) mid = ( low + high ) / 2；

13、if( k r.rmid.key ) low = mid + 1； else return mid;return -1;2 分塊查找3 哈希表的插入hashinsert( int s, int m, int key ) h = hash( key );if( sh = 空 ) sh = key;else h1 = (h+1)%m;while( sh1 != 空 ) h1 = (h1+1)%m;sh1 = key;4 哈希表的查找hashsearch( int s, int m, int key ) h = hash( key );if( sh = 空 ) return -1;else if(

14、sh = key ) return h;else h1 = (h+1)%m;while( sh1 != key & sh1 != 空 & h1 != h ) h1 = (h1+1)%m;if( sh1 = key ) return h1;else return -1;5 哈希表的刪除用除留余數(shù)法作為哈希函數(shù)，用線性探測再散列解決沖突，設(shè)計算法刪除關(guān)鍵字并將所有可以前移的元素前移填空位置，以盡量保證不斷裂hashdelete( elemtype s, int m, int key ) h = hash(key);if( sh = 空 ) return -1; else if( sh = key

15、) delete( s, h, h, key );else h1 = (h+1)%m;while( sh1 != key & sh1 != 空 & h1 != h ) h1 = (h1+1)%m;if( sh1 = key ) delete( s, h, h1, key );else return -1delete( elemtype s, int i, int j, int key ) last = j;h1 = (j+1)%m;while( h1 != i ) if( sh1 = 空 ) break;else if( hash(sh1 = i ) ) last = h1;h1 = (h1+

16、1)%m;sj = slast; /將最后一個同義詞前移slast = 空; /置空/i為hash(key)得到的值；j為key在s中的位置；/本函數(shù)的作用是將s中和關(guān)鍵字key是同義詞的關(guān)鍵字找到并確定其/最后一個位置,然后將最后一個填充到j(luò)的位置，將最后一個的置空6 直接插入排序 #define max 100struct rec keytype key; /關(guān)鍵字域 elemtype data; / /其他數(shù)據(jù)域;typedef struct rec sqlistmax; /假定要排序的記錄存儲在上面這種結(jié)構(gòu)的表中void insertsort(sqlist r, int n ) int

17、 i,j;for( i=2; i=n; i+ ) r0 = ri; for( j=i-1; r0.key0 ) for( i = gap+1; i=n; i+ ) if( ri.key 0 & r0.keyrj.key; j=j-gap ) rj+gap = rj; rj+gap = r0; /if/forgap = gap/2;/while8 冒泡排序void bubblesort( sqlist r, int n ) int i,j,exchange; struct rec temp; for( i=1; i=i+1; j- ) if( rj.keyrj-1.key ) temp = rj

18、; rj = rj-1; rj-1 = temp; exchange = 1; if(exchange = 0 ) return; 9 快速排序void quicksort( sqlist r, int s, int t ) int low = s, high = t; r0 = rlow; while( low high ) while( low = r0.key ) high-; rlow = rhigh; while( low high & rlow.key = r0.key ) low+; rhigh = rlow; rlow = r0; quicksort( r, s, low -

19、1 ); quicksort( r, low + 1, t );非遞歸算法10 簡單選擇排序void selectsort( sqlist r, int n ) int i, j, k; struct rec temp; for( i=1; i=n-1; i+ ) k = i; for( j=j+1; j=n; j+ ) if( rj.key rk.key ) k = j; temp = ri; ri = rk; rk = temp; 11 堆排序void heapadjust( sqllist r, int s, int m ) /*rsm中的記錄關(guān)鍵碼除rs外均滿足堆的定義，本函數(shù)將對第s

20、個結(jié)點為根的子樹篩選，使其成為大頂堆*/ struct rec temp;temp = rs; for( j = 2*s; j = m; j = j*2 ) if( j m & rj.key rj+1.key ) j = j + 1; if( temp.key 0; i- ) heapadjust( h, i, n ); /* 將r1.n建成大頂堆 */ for( i=n; i1; i- ) r1ri; /* 堆頂與堆低元素交換 */ heapadjust( h, 1, i-1 ); /*將r1.i-1重新調(diào)整為堆*/ 12 兩路歸并排序void merge(sqllist *r，sqllis

21、t *rf，int u，int v，int t) /將有序的ruv和rv+1t歸并為有序的rfutfor( i=u,j=v,k=u; iv&j=t; k+ )if(ri.keyrj.key)rfk=ri;i+;elserfk=rj;j+;if(i=v) rfkt=riv-1;if(jdata); /訪問隊列的首節(jié)點的數(shù)據(jù)域 if( p-left != null ) queuerear+ = p-left; /若節(jié)點存在左孩子，則左孩子節(jié)點指針進入隊列 if( p-right != null ) queuerear+ = p-right; /若節(jié)點存在右孩子，則右孩子節(jié)點指針進入隊列 層次遍歷二

22、叉樹時，統(tǒng)計二叉樹的每一層的信息int levelorder( bitree *bt ) bitree *queue100, *p; int front = rear = 0;int level = count = 1; /level表示當前的層數(shù)；count表示當前層元素的個數(shù) if( bt = null ) return;queuerear+ = bt;while( front != rear ) int temp = 0; /暫時保存當前層結(jié)點的個數(shù) for( int i = 1; i lchild != null ) temp+;queuerear+ = p-lchild; if( p

23、-rchild != null ) temp+;queuerear+ = p-rchild;/ /forcount = temp;level+;/whileb 二叉樹先序（中序）遍歷preorder( bitree *bt ) /先序非遞歸遍歷/ inorder( bitree *bt ) /中序非遞歸遍歷 int maxsize = 100, top = 0;bitree *stackmaxsize, *p = bt;if( bt = null ) return;while( !( p = null & top = 0 ) ) while( p != null ) visite( p-dat

24、e ); /visite()在此表示先序遍歷二叉樹stacktop+ = p; p = p-left;if( top != 0 ) p = stacktop-; visite( p-date ); /visite()在此表示中序遍歷二叉樹 p = p-right;c 二叉樹的后序遍歷typedef struct bitree link; int flag;stacktype;postorder( bitree *bt ) int maxsize = 100, top = 0;bitree *p = bt;stacktype stackmaxsize;if ( bt = null ) retur

25、n;while( !( p = null & top = 0 ) ) while( p != null ) stacktop.link = p; stacktop.flag = 1; p = p-left; top+; while( top != 0 & stacktop.flag = 2 ) p = stack-top.link; visite(p-data); if( top != 0 ) stacktop.flag = 2; p = stacktop.link-right; postorder( bitree *bt ) /這種算法沒有第一種結(jié)構(gòu)清晰和常見，但是它沒有用標志位 int m

26、axsize = 100, top = -1;bitree *stackmaxsize, *p = bt;while( !( p = null & top = -1 ) ) /當棧非空或者p指針非空時執(zhí)行循環(huán) while( p != null ) /p非空則進棧，并向左子樹深入若左子樹為空則向右子樹深入直到p為空 stack+top = p; if( p-left ) p = p-left;else p = p-right; p = stacktop-; /退棧得到的結(jié)點可能是葉子，也可能是無右子樹的單分支節(jié)點visite(p-data); /若循環(huán)條件成立，則表明右子樹已經(jīng)訪問完畢，應(yīng)退棧并

27、輸出該節(jié)點的值while( top != -1 & stacktop-right = p ) /此結(jié)點必為右子樹非空的分支節(jié)點 p = stacktop-; visite(p-data);if( top != -1 ) p = stacktop-right /為了向右子樹繼續(xù)遍歷而修改p的值else p = null2 線索二叉樹a 建立中序線索二叉樹（遞歸）int inorderthr(bithrtree head,bithrtree t) /中序遍歷二叉樹t，并將其中序線索化，*head指向頭結(jié)點。 if (!(*head =( bithrtree *)malloc(sizeof(bith

28、rtree) return 0;head-ltag=0; head-rtag=1; /建立頭結(jié)點 head-rchild=head; /右指針回指 if ( !t ) head-lchild = head; /若二叉樹為空，則左指針回指 else head-lchild=t; pre= head; inthreading(t); /中序遍歷進行中序線索化 pre-rchild=head; pre-rtag=1; /最后一個結(jié)點線索化 head-rchild=pre; return 1;void intreading(bithrtree p) /中序遍歷進行中序線索化 if( p ) inthr

29、eading(p-lchild); /左子樹線索化 if( !p-lchild ) /前驅(qū)線索 p-ltag=1; p-lchild=pre; if( !pre-rchild ) /后繼線索 pre-rtag=1; pre-rchild=p; pre=p; inthreading(p-rchild); /右子樹線索化 b中序線索樹上查找前驅(qū)結(jié)點gedbfcah 中序線索二叉樹的示例（d b g e h a c f ）bithrtree prenode(bithrtree p) bithrtree pre; if( p-ltag = 1 ) pre = p-lchildelse pre = p-

30、lchild;while( pre-rtag = 0 ) pre = pre-rchild; return( pre );c中序線索樹上查找后繼結(jié)點bithrtree postnode(bithrtree p) bithrtree post; if ( p-rtag = 1 ) post = p-rchildelse post = p-rchild; while( post-ltag = 0 ) post=post-lchild; return(post); d 先序線索樹上查找前驅(qū)和后繼結(jié)點（了解）gedbfcah 先序線索二叉樹示例（ a b d e g h c f ）求后繼結(jié)點bithr

31、tree postnode(bithrtree p) bithrtree post; if ( p-rtag = 1 ) post p-rchild;else if( p-ltag = 0 ) post = p-lchild;else post = p-rchild; return(post); 求前驅(qū)結(jié)點bithrtree prenode(bithrtree p) bithrtree pre;if( p-ltag = 1 ) pre = p-lchild;else if( p = father-lchild ) pre = father; /father表示p的父親結(jié)點的指針else /訪問

32、其父親結(jié)點的左子樹中先序遍歷的最后一個結(jié)點 pre = father-lchild; while( pre-ltag = 0 | pre-rtag = 0 ) if( pre-rtag = 0 ) /有右兒子的先找右兒子，沒有右兒子的才找左兒子 pre = pre-rchild; /始終是右兒子優(yōu)先else pre = pre-lchild; return( pre );e 后序線索樹上查找前驅(qū)和后繼結(jié)點（了解） hebfcadgilkj 后序線索二叉樹示例（ g d l k j h i e b f c a ）求前驅(qū)結(jié)點bithrtree prenode(bithrtree p) bithrt

33、ree pre;if( p-ltag = 1 ) pre = p-lchildelse if( p-rtag = 0 ) pre = p-rchild;else pre = p-lchild; return( pre );求后繼結(jié)點bithrtree postnode(bithrtree p) bithrtree post;if( p-rtag = 1 ) post = p-lchild;else if( p = father-rchild ) post = father-rchild;else post = father-rchild; while( post-ltag = 0 | post

34、-rtag = 0 ) if( post-ltag = 0 ) post = post-lchild; else post = post-rchild; return( post );f 中序線索樹中查找父親結(jié)點bithrtree fathernode（ bithrtree p ） bithrtree fahter; father = p; /查找p的最左子孫的左線索while( father-ltag = 0 ) father = father-lchild;father = father-lchild;if( father & father-rchild = p ) return(father); father = p; /查找p的最右子孫的右線索while( father-rtag = 0 ) father = father-rchild;father = father-rchild;if( father & father-lchild = p