1、顺序表递增有序，插入元素x，仍递增有序 int find ( Sqlist L, int x ) for ( int i=0; iL.length; +i ) if( x=p;-j ) L.dataj+1=L.dataj ; L.datap=x ; +( L.length ) ; 删除顺序表中所有值为x的数据元素 法一： void delete ( Sqlist &L, int x ) int k=0 ; for ( int i=0; i=L.length-1;+i ) if( L.datai !=x ) L.datak=L.datai ; +k ; L.length=k ; 法二： void
2、 delete ( Sqlist &L, int x ) int k=0 ; for ( int i=0; i=t ) return false ; for ( i=0; i=s & L.datai=t ) +k ; else L.datai-k=L.datai ; L.length-=k ; return ture ; 从有序表中删除所有值重复的元素 bool delete ( Sqlist &L ) if ( L.length=0 ) return false ; int i, j ; for ( i=0, j=1; j=t | L.length=0 ) return false ; fo
3、r ( i=0; iL.length & L.datai=L.length ) return false ; for (j=i; jL.length & L.dataj=t; +j ) ; for ( ; jC.maxsize ) return false ; int i=j=k=0 ; while ( iA.length & jB.length ) if ( A.dataiB.dataj ) C.datak+=A.datai+ ; else C.datak+=B.dataj+ ; while ( iA.length ) C.datak+=A.datai+ ; while ( j=n | n=
4、arry ) return ; int mid=(m+n)/2 ; for ( int i=0; i=mid-m; +i ) int temp=Am+i ; Am+i=An-i ; An-i=temp ; void change ( int A , int m, int n, int size ) Reverse ( A, 0, m+n-1, size ) ; Reverse ( A, 0, n-1, size ) ; Reverse ( A, n, m+n-1, size ) ; 设计一个时间上尽可能高效的算法，找出数组中 未出现的最小正整数 int find ( int A , int n
5、 ) int *B ; B=(int *) malloc( sizeof (int) *n ) ; for ( int i=0; in; +i ) Bi=0 ; for ( int i=0; i0 & Ai=n ) BAi-1=1 ; for ( i=0; in; +i ) if ( Bi=0 ) break ; return i+1 ; 若一个整数序列中有过半相同元素，则称其为主 元素，设计算法找出数组A( a0,a1an-1 )的 主元素。（其中0ain）若存在主元素则输出， 否则返回-1 int fun ( int A , int n ) int *B =(int *) malloc(
6、sizeof (int) *n ) ; for ( int i=0; in; +i ) Bi=0 ; int i, k ; int max=0 ; for ( i=0; i0 & Ai=n ) BAi-1+ ; for ( i=0; imax ) max=Bi ; k=i ; if ( maxn/2 ) return k+1 ; else return -1 ; (WD答案较复杂，这里采用空间换时间的思想) 3 两个递增有序的单链表，设计算法成一个非递减 有序的链表 void fun(LNode *A, LNode *B, LNode *&C) LNode *p=A-next ; LNode
7、*q=B-next ; LNode *r ; C=A; C-next=NULL ; free (B) ; r=C ; while ( p !=NULL & q !=NULL ) if ( p-datadata )/若递减有序 r-next=p ;/s=p, p=p-next ; p=p-next ;/s-next=C-next ; r=r-next ;/ C-next=s ; /后面的循环同上 else r-next=q ; q=q-next ; r=r-next ; r-next=NULL ; if ( p !=NULL ) /递减有序的话需要头插法 r-next=p ;/ 逐个插入 if
8、(q !=NULL ) r-next=q ; 查找链表中是否存在一个值为x的节点，若存在， 则删除结点并返回1，否则返回0 int finddelete ( LNode *&C, int x ) LNode *p, q ; p=C ; while ( p-next !=NULL ) if ( p-next-data=x ) break ; p=p-next ; if ( p-next=NULL ) return 0 ; else q=p-next ; p-next=q-next ; free (q) ; return 1; 在带头结点的单链表L中删除所有值为x的结点， 并释放空间 法一： vo
9、id delete ( LNode *&L, int x ) LNode *p=L-next ; LNode *pre=L ; LNode *q ; while (p !=NULL ) if ( p-data=x ) q=p ; pre-next=p-next ; p=p-next ; free (q) ; else pre=p ; p=p-next ; 4 法二： void delete ( LNode *&L, int x ) LNode *p=L-next ; LNode *r=L ; LNode *q ; while ( p !=NULL ) if ( p-data !=x ) r-n
10、ext=p ; r=p ; p=p-next ; else q=p ; p=p-next ; free (q) ; r-next=NULL ; 试编写在带头结点的单链表L中删除最小值点 的高效算法（已知最小值唯一） void delete ( LNode *&L ) LNode *pre=L ; LNode *p=L-next ; LNode *minpre =L ; LNode *minp=L-next ; while ( p !=NULL ) if ( p-datadata ) minp=p ; minpre=pre ; pre=p ; p=p-next ; minpre-next=min
11、p-next ; free ( minp ) ; 试编写算法将单链表就地逆置 法一： void reverse ( LNode *&L ) LNode *p=L-next, r=p-next ; LNode *pre ; p-next=NULL ; while ( r !=NULL ) pre=p； p=r； r=r-next； p-next=pre ; L-next=p ; 法二： void reverse ( LNode *&L ) LNode *p, r ; p=L-next ; L-next=NULL ; while ( p !=NULL ) r=p-next； p-next=L-ne
12、xt ; L-next=p ; p=r ; 5 给定两个单链表，找到两个链表公共结点 Linklist Search ( LNode *L1, LNode *L2 ) int len1=length (L1), len2=length (L2) ; int dist ; LNode *long, short ; if ( len1len2 ) long=L1-next ; short=L2-next ; dist=len1-len2 ; else long=L2-next ; short=L1-next ; dist=len2-len1 ; while ( dist- ) long=long-
13、next ; while ( long !=NULL ) if ( long=short ) return long ; else long=long-next ; short=short-next ; return NULL ; 给定一个单链表，按递增排序输出的单链表中各 结点的数据元素 void delete ( LNode *&head ) while ( head-next !=NULL ) pre=head ; p=pre-next ; while ( p-next !=NULL ) if( p-next-datanext-data ) pre=p ; p=p-next ; prin
14、t( pre-next-data ) ; u=pre-next ; pre-next=u-next ; free (u) ; free (head) ; ) 将一个带头节点的单链表A分解成两个带头节 点的单链表A和B，使A中含奇数元素，B中含 偶数元素，且相对位置不变 B=( LNode *) malloc( sizeof (LNode) *n ) ; B-next=NULL ; void creat ( LNode *&A, LNode *&B ) int i=0 ; LNode *p=A ; LNode *q=B ; r=A-next ; A-next=NULL ; while ( r !
15、=NULL ) +i ; if ( i%2=0 ) q-next=r ; q=r ; else p-next=r ; p=r ; r=r-next ; p-next=NULL ; q-next=NULL ; 6 将a1,b1,a2,b2an,bn拆分成 a1,a2an 和 bn,bn-1,b1 B=( LNode *) malloc ( sizeof (LNode) *n ) ; B-next=NULL ; void creat ( LNode *&A, LNode *&B ) LNode *p=A-next ; LNode *ra=A ; LNode *q ; while ( p !=NUL
16、L ) ra-next=p ; ra=p ; p=p-next ; q=p-next ; p-next=B-next ; B-next=p ; p=q ; ra-next=NULL ; 删除递增链表中重复的元素 void delete ( LNode *&L ) LNode *p=L-next ; LNode *q ; if ( p=NULL ) return ; while ( p-next !=NULL ) q=p-next ; if ( p-data=q-data ) p-next=q-next ; free (q) ; else p=p-next ; 法二： while ( p !=N
17、ULL ) if ( p-data=pre-data ) s=p ; pre-next=p-next ; p=p-next ; free (s) ; else pre=p ; p=p-next ; A,B两个单链表递增有序，从A，B中找出公共 元素产生单链表C，要求不破环A，B结点 void creat ( LNode *A, LNode *B ) LNode *p=A-next ; LNode *q=B-next ; LNode *r, s, C ; C= ( LNode *) malloc( sizeof (LNode) ) ; r=C ; while ( p !=NULL & q !=N
18、ULL ) if ( p-datadata ) p=p-next ; else if ( p-dataq-data ) q=q-next ; else s=( LNode *) malloc(sizeof (LNode) ) ; s-data=p-data ; r-next=s ; r=s ; p=p-next ; q=q-next ; r-next=NULL ; 7 继续上题，将交集放到A链表中 void Union ( LNode *&A, LNode *&B ) LNode *pa=A-next, *pb=B-next ; LNode *pc=A ; while ( pa !=NULL
19、& pb !=NULL ) if ( pa-data=pb-data ) pc-next=pa, pc=pa ; pa=pa-next ; u=pb, pb=pb-next, free (u) ; else if ( pa-datadata ) u=pa, pa=pa-next, free (u) ; else u=pb, pb=pb-next, free (u) ; while ( pa !=NULL ) u=pa, pa=pa-next, free (u) ; while ( pb !=NULL ) u=pb, pb=pb-next, free (u) ; pc-next=NULL ; f
20、ree (B) ; 查找单链表中倒数第k个结点，若成功，则输出 该节点的data，并返回1，否则返回0 int find ( LNode *head, int k ) LNode *p1=head-next ; LNode *p=head ; int i=1 ; while ( p !=NULL ) p1=p1-next ; +i ; if ( ik ) p=p-next ; if ( p=head ) return 0 ; else printf ( “%d”, p-data ) ; return 1 : 用单链表保存m个整数，并且|data|n，现在 要求设计时间复杂度尽可能高效的算法，对
21、于 data绝对值相等的点，仅保留第一次出现的点 void fun ( LNode *h, int n ) LNode *p=h ; LNode *r ; int *q=(int *) malloc (sizeof(int) * (n+1) ) ; int m ; for ( int i=0; inext != NULL ) if ( p-next-data0 ) m=p-next-data ; else m=-p-next-data ; if ( qm=0 ) qm=1 ; p=p-next ; else r=p-next ; p-next=r-next ; free (r) ; free
22、(q) ; 8 判断带头结点的循环双链表是否对称 int fun ( Dnode *L ) Dnode *p=L-next ; Dnode *q=L-prior ; while ( p !=q & p-next !=q ) if ( p-data=q-data ) p=p-next ; q=q-prior ; else return 0 ; return 1 ; 有两个循环单链表，链表头指针分别为h1,h2, 试编写函数将h2链表接到h1之后，要求链接后 仍保持循环链表形式 void link ( LNode *&h1, LNode *&h2 ) LNode *p, q ; p=h1, q=h
23、2 ; while ( p-next !=h1 ) p=p-next ; while ( q-next !=h2 ) q=q-next ; p-next=h2 ; q-next=h1 ; 设有一个带头结点的循环单链表，其结点值为正 整数，设计算法反复找出链表内最小值并不断输 出，并将结点从链表中删除，直到链表为空，再 删除表头结点 void delete ( LNode *&L ) LNode *p, pre, minp, minpre ; while ( L-next !=L ) p=L-next ; pre=L ; minp=p ; minpre=pre ; while ( p !=L )
24、 if ( p-datadata ) min=p ; minpre=pre ; pre=p; p=p-next ; print ( minp-data ) ; minpre-next=minp-next ; free (minp) ; free (L) ; 带头结点的非循环双向链表 preddatafreq(频度)next 设计算法使其按freq递减排序 void fun ( Dnode *&L, int x ) Dnode *p=L-next ; Dnode *q ; while ( p !=NULL & p-data !=x ) p=p-next ; if ( p=NULL ) print
25、f ( “不存在” ); exit (0) ; else p-freq+ ; q=p-pred ; p-next-pred=q ; p-pred-next=p-next ; while ( q !=L & q-freqfreq ) q=q-pred ; p-next=q-next ; q-next-pred=p ; p-pred=q ; q-next=p : 9 设计算法判断单链表的全部n个字符是否中心 对称，例如xyx，xyyx都是中心对称 int fun ( LNode *L, int n ) int i ; char s(n/2) ;/s 是字符栈 p=L-next ; for ( i=
26、0; idata ; p=p-next ; i- ; if ( n%2=1 ) p=p-next ; while ( p !=NULL & si=p-data ) i- ; p=p-next ; if ( i=-1 ) return 1 ; else return 0 ; 利用一个栈实现以下递归函数的非递归计算 1n=0 Pn（x）2xn=1 2xPn-1(x)-2(n-1)Pn-2(x)n1 double p ( int n, double x ) struct stack int no ; double val ; stMaxsize ; int top=-1 ; double fv1=1
27、, fv2=2*x ; for ( i=n; i=2; i- ) top+ ; sttop .no=i ; while ( top=0 ) sttop .val=2*x*fv1-2*( sttop .no-1 )*fv1 ; fv1=fv2 ; fv2=sttop.val ; top- ; if ( n=0 ) return fv1 ; return fv2 ; 计算二叉树中所有结点个数 法一： int count ( BTNode *p ) int n1, n2 ; if ( p=NULL ) return 0 ; else n1=count ( p-lchild ) ; n2=count
28、( p-rchild ) ; return n1+n2+1 ; 法二： int n=0 ; void count ( BTNode *p ) if ( p !=NULL ) +n ; count ( p-lchild ) ; count ( p-rchild ) ; 10 计算二叉树中所有叶子节点的个数 法一： int count ( BTNode *p ) int n1, n2 ; if ( p=NULL ) return 0 ; if( p-lchild=NULL & p-rchild=NULL) return 1 ; else n1=count ( p-lchild ) ; n2=cou
29、nt ( p-rchild ) ; return n1+n2 ; 法二： int n=0 ; void count ( BTNode *p ) if ( p !=NULL ) if( p-lchild=NULL&p-rchild=NULL) +n ; count ( p-lchild ) ; count ( p-rchild ) ; (a-(b+c)*(d/e)存储在二叉树，遍历求值 int comp ( BTNode *p ) int A, B ; if ( p !=NULL ) if(p-lchild !=NULL&p-rchild !=NULL) A=comp ( p-lchild )
30、; B=comp ( p-rchild ) ; return op ( A, B, p-data ) ; else return p-data-0 ; else return 0 ; / 计算二叉树的深度 int getDepth ( BTNode *p ) int LD, RD ; if ( p=NULL ) return 0 ; else LD=getDepth ( p-lchild ) ; RD=getDepth ( p-rchild ) ; return ( LDRD ? LD : RD )+1 ; 判断两个二叉树是否相似（指都为空或者都只有 一个根节点，或者左右子树都相似） int
31、fun ( BTNode *T, BTNode *T ) int left, right ; if ( T1=NULL & T2=NULL ) return 1 ; if ( T1=NULL | T2=NULL ) return 0 ; else right=fun ( T1-lchild, T2-rchild ) ; left=fun ( T1-lchild, T2-rchild ) ; return left & right ; 把二叉树所有节点左右子树交换 void swap ( BTNode *p ) if ( p !=NULL ) swap ( p-lchild ) ; swap (
32、 p-rchild ) ; temp=p-lchild ; p-lchild=p-rchild : p-rchild=temp ; 11 查找二叉树中data域等于key的结点是否存在， 若存在，将q指向它，否则q为空 void fun (BTNode *p, BTNode *&q, int key) if ( p !=NULL ) if ( p-data=key ) q=p; else fun (p-lchild, q, key ) ; fun (p-rchild, q, key ) ; 输出先序遍历第k个结点的值 int n=0 ; void trave ( BTNode *p, int
33、k ) if ( p !=NULL ) +n ; if ( k=n ) printf ( “%d”, p-data ) ; return ; trave ( p-lchild, k ) ; trave ( p-rchild, k ) ; 利用结点的右孩子指针将一个二叉树的叶子节 点从左向右连接成一个单链表（head指向第一 个，tail指向最后一个） void link ( Bt *p, Bt*&head, Bt *&tail ) if ( p !=NULL ) if ( ! p-lchild & ! p-rchild ) if ( head=NULL ) head=p ; tail=p ;
34、else tail-rchild=p ; tail=p ; link ( p-lchild, head, tail ) ; link ( p-rchild, head, tail ) ; 增加一个指向双亲节点的parent指针，并给指 针赋值，并输出所有节点到根节点的路径 typedef Struct BTNode char data ; Struct BTNode *parent, lchild, rchild ; BTNode ; void fun ( BTNode *p, BTNode *q ) if ( p !=NULL ) p-parent=q ; q=p ; fun ( p-lch
35、ild, q ) ; fun ( p-rchild, q ) ; void printpath ( BTNode *p ) while ( p !=NULL ) printf ( “%c”, p-data ) ; p=p-parent ; void allpath ( BTNode *p ) if ( p !=NULL ) printpath (p) ; allpath (p-lchild ) ; allpath (p-rchild ) ; 12 求二叉树中值为x的层号 int L1=1 ; void fun ( BTNode *p, int x ) if ( p !=NULL ) if (
36、p-data=x ) printf ( “%d”, L1 ) ; +L1 ; fun ( p-lchild, x ) ; fun ( p-rchild, x ) ; -L1 ; 输出根节点到每个叶子结点的路径 int i, top=0 ; char pathstack maxsize ; void allpath ( BTNode *p ) if ( p !=NULL ) pathstacktop=p-data ; +top ; if ( ! p-lchild & ! p-rchild ) for ( i=0; ilchild ) ; allpath ( p-rchild ) ; -top ; 已知满二叉树先序序列存在于数组中，设计算法将其变成后序序列 void change ( char pre , int L1, int R1, char post , int L2, int R2 ) if ( L1data=AL1 ; for ( i=L2; Bi !=root-data; i+ ) ; i
