数据结构课本算法实现.doc

线性结构一 类型定义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;二 基础要点1单链表 2双链表三 算法1 删除顺序表中重复元素void delsame( int a, int count ) int i, 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; /关键字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.key = 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-next; 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 = 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 删除单链表重复元素void delete(linklist h) snode *p,*q,*r; p = h-next; while( p != null ) q=p; while ( q-next ) if ( q-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; /*插入到c表的头部*/ c-next = s;if ( p = null ) r = q;if ( q=null) r=p;while (r ) /* 将剩余的结点一个个摘下，插入到c表的头部*/ s =r;r = r-next;s-next = c-next; c-next = s; 7 顺序表和链表的递归输出已知head是带头结点的单链表的头指针，试编写逆序/顺序输出表中各元素的递归算法；有一个整数数组an，按顺序/逆序递归输出数组中的各元素output( linklist *head ) if( head != null ) output( head-next ); printf( “%d”,head-data ); /printf在output下为逆序输出，在上为顺序输出 8带访问频度的双向链表的查找8 置逆栈void reverse( stack *s ) stack s1, s2; elemtype x; initstack( s1 ); initstack( s2 ); /将s栈中的内容转移到s1栈中 while( stackempty( s ) != 0 ) pop( s, x );push( s1, x ); /将s1栈中的内容转移到s2栈中 while( stackempty( s1 ) != 0 ) pop( s1, x );push( s2, x ); /将s2栈中的内容转移到s栈中 while( stackempty( s2 ) != 0 ) pop( s2, x );push( s, x ); 9 用栈实现队列操作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的所有元素退栈进入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 /对第二个栈进行进栈操作 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 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； 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( 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 哈希表的删除用除留余数法作为哈希函数，用线性探测再散列解决冲突，设计算法删除关键字并将所有可以前移的元素前移填空位置，以尽量保证不断裂hashdelete( elemtype s, int m, int key ) h = hash(key);if( sh = 空 ) return -1; else if( sh = key ) 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+1)%m;sj = slast; /将最后一个同义词前移slast = 空; /置空/i为hash(key)得到的值；j为key在s中的位置；/本函数的作用是将s中和关键字key是同义词的关键字找到并确定其/最后一个位置,然后将最后一个填充到j的位置，将最后一个的置空6 直接插入排序 #define max 100struct rec keytype key; /关键字域 elemtype data; / /其他数据域;typedef struct rec sqlistmax; /假定要排序的记录存储在上面这种结构的表中void insertsort(sqlist r, int n ) int 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; 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 - 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中的记录关键码除rs外均满足堆的定义，本函数将对第s个结点为根的子树筛选，使其成为大顶堆*/ 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重新调整为堆*/ 12 两路归并排序void merge(sqllist *r，sqllist *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); /访问队列的首节点的数据域 if( p-left != null ) queuerear+ = p-left; /若节点存在左孩子，则左孩子节点指针进入队列 if( p-right != null ) queuerear+ = p-right; /若节点存在右孩子，则右孩子节点指针进入队列 层次遍历二叉树时，统计二叉树的每一层的信息int levelorder( bitree *bt ) bitree *queue100, *p; int front = rear = 0;int level = count = 1; /level表示当前的层数；count表示当前层元素的个数 if( bt = null ) return;queuerear+ = bt;while( front != rear ) int temp = 0; /暂时保存当前层结点的个数 for( int i = 1; i lchild != null ) temp+;queuerear+ = p-lchild; if( p-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-date ); /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 ) return;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 ) /这种算法没有第一种结构清晰和常见，但是它没有用标志位 int maxsize = 100, top = -1;bitree *stackmaxsize, *p = bt;while( !( p = null & top = -1 ) ) /当栈非空或者p指针非空时执行循环 while( p != null ) /p非空则进栈，并向左子树深入若左子树为空则向右子树深入直到p为空 stack+top = p; if( p-left ) p = p-left;else p = p-right; p = stacktop-; /退栈得到的结点可能是叶子，也可能是无右子树的单分支节点visite(p-data); /若循环条件成立，则表明右子树已经访问完毕，应退栈并输出该节点的值while( top != -1 & stacktop-right = p ) /此结点必为右子树非空的分支节点 p = stacktop-; visite(p-data);if( top != -1 ) p = stacktop-right /为了向右子树继续遍历而修改p的值else p = null2 线索二叉树a 建立中序线索二叉树（递归）int inorderthr(bithrtree head,bithrtree t) /中序遍历二叉树t，并将其中序线索化，*head指向头结点。 if (!(*head =( bithrtree *)malloc(sizeof(bithrtree) return 0;head-ltag=0; head-rtag=1; /建立头结点 head-rchild=head; /右指针回指 if ( !t ) head-lchild = head; /若二叉树为空，则左指针回指 else head-lchild=t; pre= head; inthreading(t); /中序遍历进行中序线索化 pre-rchild=head; pre-rtag=1; /最后一个结点线索化 head-rchild=pre; return 1;void intreading(bithrtree p) /中序遍历进行中序线索化 if( p ) inthreading(p-lchild); /左子树线索化 if( !p-lchild ) /前驱线索 p-ltag=1; p-lchild=pre; if( !pre-rchild ) /后继线索 pre-rtag=1; pre-rchild=p; pre=p; inthreading(p-rchild); /右子树线索化 b中序线索树上查找前驱结点gedbfcah 中序线索二叉树的示例（d b g e h a c f ）bithrtree prenode(bithrtree p) bithrtree pre; if( p-ltag = 1 ) pre = p-lchildelse pre = p-lchild;while( pre-rtag = 0 ) pre = pre-rchild; return( pre );c中序线索树上查找后继结点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 先序线索树上查找前驱和后继结点（了解）gedbfcah 先序线索二叉树示例（ a b d e g h c f ）求后继结点bithrtree 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); 求前驱结点bithrtree prenode(bithrtree p) bithrtree pre;if( p-ltag = 1 ) pre = p-lchild;else if( p = father-lchild ) pre = father; /father表示p的父亲结点的指针else /访问其父亲结点的左子树中先序遍历的最后一个结点 pre = father-lchild; while( pre-ltag = 0 | pre-rtag = 0 ) if( pre-rtag = 0 ) /有右儿子的先找右儿子，没有右儿子的才找左儿子 pre = pre-rchild; /始终是右儿子优先else pre = pre-lchild; return( pre );e 后序线索树上查找前驱和后继结点（了解） hebfcadgilkj 后序线索二叉树示例（ g d l k j h i e b f c a ）求前驱结点bithrtree prenode(bithrtree p) bithrtree pre;if( p-ltag = 1 ) pre = p-lchildelse if( p-rtag = 0 ) pre = p-rchild;else pre = p-lchild; return( pre );求后继结点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-rtag = 0 ) if( post-ltag = 0 ) post = post-lchild; else post = post-rchild; return( post );f 中序线索树中查找父亲结点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