数据结构经典例题

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐数据结构经典例题数据结构经典例题

1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。

voidsplit(LinkList*//p指向第1个数据节点

L1=L;//L1利用本来L的头节点

r1=L1;//r1始终指向L1的尾节点

L2=(LinkList*)malloc(sizeof(LinkList));//创建L2的头节点

L2->next=NULL;//置L2的指针域为NULL

while(p!=NULL)

{r1->next=p;//采纳尾插法将*p(data值为ai)插入L1中

r1=p;

p=p->next;//p移向下一个节点(data值为bi)

q=p->next;//因为头插法修改p的next域,故用q保存*p的后继节点

p->next=L2->next;//采纳头插法将*p插入L2中

L2->next=p;

p=q;//p重新指向ai+1的节点

}

r1->next=NULL;//尾节点next置空

}

2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找胜利，算法输出该节点的data域的值，并返回1；否则，只返回0。

typedefstructLNode

{intdata;

structLNode*link;

}*LinkList;

intSearchk(LinkListlist,intk)

{LinkListp,q;

intcount=0;

p=q=list->link;

while(p!=NULL)

{if(countlink;

p=p->link;

}

if(countdata);

return(1);

}

}

3.假定采纳带头节点的单链表保存单词，当两个单词有相同的后缀时，则可分享相同的后缀存储空间。设str1和str2分离指向两个单词所在单链表的头节点请设计一个时光上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置。

typedefstructNode

{chardata;

structNode*next;

}SNODE;

SNODE*Findlist(SNODE*str1,SNODE*str2)

{intm,n;

SNODE*p,*q;

m=Listlen(str1);//求单链表str1的长度m

n=Listlen(str2);//求单链表str2的长度n

for(p=str1;m>n;m--)//若m大，则str1后移m-n+1个节点p=p->next;

for(q=str2;mnext;

while(p->next!=NULL//p、q两步后移找第一个指针值相等的节点q=q->next;

}

returnp->next;

}

intListlen(SNODE*head)//求单链表的长度

{intlen=0;

while(head->next!=NUL)

{len++;

head=head->next;

}

returnlen;

}

4.设计一个算法，删除一个单链表L中元素值最大的节点。

voiddelmaxnode(LinkList*

while(p!=NULL)//用p扫描囫囵单链表,pre始终指向其前驱节点

{if(maxp->datadata)//若找到一个更大的节点{maxp=p;//更改maxp

maxpre=pre;//更改maxpre

}

pre=p;//p、pre同步后移一个节点

p=p->next;

}

maxpre->next=maxp->next;//删除*maxp节点

free(maxp);//释放*maxp节点

}

5.有一个带头节点的单链表L（至少有一个数据节点），设计一个算法使其元素递增有序罗列。

voidsort(LinkList*

p=L->next->next;//p指向L的第2个数据节点

L->next->next=NULL;//构造只含一个数据节点的有序表

while(p!=NULL)

{q=p->next;//q保存*p节点后继节点的指针

pre=L;//从有序表开始举行比较,pre指向插入*p的前驱节点

while(pre->next!=NULL//在有序表中找插入*p的前驱节点*pre

p->next=pre->next;//将*pre之后插入*p

pre->next=p;

p=q;//扫描原单链表余下的节点

}

}

6.有一个带头节点的双链表L，设计一个算法将其全部元素逆置，即第1个元素变为最后一个元素，第2个元素变为倒数第2个元素，…，最后一个元素变为第1个元素。

voidreverse(DLinkList*//p指向开好节点

L->next=NULL;//构造惟独头节点的双链表L

while(p!=NULL)//扫描L的数据节点

{q=p->next;//用q保存其后继节点

p->next=L->next;//采纳头插法将*p节点插入

if(L->next!=NULL)//修改其前驱指针

L->next->prior=p;

L->next=p;

p->prior=L;

p=q;//让p重新指向其后继节点

}

}

7.编写出推断带头节点的双向循环链表L是否对称相等的算法。

intEqueal(DLinkList*L)

{intsame=1;

DLinkList*p=L->next;//p指向第一个数据节点

DLinkList*q=L->prior;//q指向最后数据节点

while(same==1)

if(p->data!=q->data)

same=0;

else

{

if(p==q)break;//数据节点为奇数的状况

q=q->prior;

if(p==q)break;//数据节点为偶数的状况

p=p->next;

}

returnsame;

}

8.假设有两个有序表LA和LB表示，设计一个算法，将它们合并成一个有序表LC。要求不破坏原有表LA和LB。

voidUnionList(SqList*LA,SqList*LB,SqList*//i、j分离为LA、LB的下标,k为LC中元素个数LC=(SqList*)malloc(sizeof(SqList));//建立有序挨次表LC

while(ilength

i++;k++;

}

else//LA->data[i]>LB->data[j]

{LC->data[k]=LB->data[j];

j++;k++;

}

}

while(ilength)//LA尚未扫描完,将其余元素插入LC中

{LC->data[k]=LA->data[i];

i++;k++;

}

while(jlength)//LB尚未扫描完,将其余元素插入LC中

{LC->data[k]=LB->data[j];

j++;k++;

}

LC->length=k;

}

9.设有4个元素a、b、c、d进栈，给出它们全部可能的出栈次序。

解：全部可能的出栈次序如下:

abcdabdcacbdacdb

adcbbacdbadcbcad

bcdabdcacbadcbda

cdbadcba

10.编写一个算法利用挨次栈推断一个字符串是否是对称串。所谓对称串是指从左向右读和从右向左读的序列相同。

boolsymmetry(ElemTypestr[])

{inti;ElemTypee;

SqStack*st;

InitStack(st);//初始化栈

for(i=0;str[i]!='\0';i++)//将串全部元素进栈

Push(st,str[i]);//元素进栈

for(i=0;str[i]!='\0';i++)

{Pop(st,e);//退栈元素e

if(str[i]!=e)//若e与当前串元素不同则不是对称串

{DestroyStack(st);//销毁栈

returnfalse;

}

}

DestroyStack(st);//销毁栈

returntrue;

}

11.编写一个算法推断输入的表达式中括号是否配对（假设只含有左、右圆括号）boolMatch(charexp[],intn)

{inti=0;chare;boolmatch=true;SqStack*st;

InitStack(st);//初始化栈

while(inext!=NULLp->next->data='z';//替换为xyz

q=(LiString*)malloc(sizeof(LiString));

q->data='y';q->next=p->next;p->next=q;

find=1;

}

elsep=p->next;

}

}

13.含n个节点的三次树的最小高度是多少？最大高度是多少？

解：设含n个节点的（为彻低三次树时高度最小）的三次树的最小高度为h，则有：

1+3+9+…+3h-2＜n≤1+3+9+…+3h-1

(3h-1-1)/2＜n≤(3h-1)/2

3h-1＜2n+1≤3h

即：h=log3(2n+1)

最大高度为n-2。

14.假设图G采纳邻接表存储，设计一个算法，输出图G中从顶点u到v的全部容易路径。

voidPathAll(ALGraph*G,intu,intv,intpath[],intd)

//d是到当前为止已走过的路径长度，调用时初值为-1

{intw，i;ArcNode*p;

visited[u]=1;d++;//路径长度增1

path[d]=u;//将当前顶点添加到路径中

if(u==v

for(i=0;iadjlist[u].firstarc;//p指向u的第一条边

while(p!=NULL)

{w=p->adjvex;//w为u的邻接顶点

if(visited[w]==0)//若顶点未标记拜访，则递归拜访之

PathAll(G,w,v,path,d);

p=p->nextarc//找u的下一个邻接顶点}

visited[u]=0;//恢复环境

}

voidmain()

{intpath[MAXV],u=1,v=4,i,j;

MGraphg;

ALGraph*G;

g.n=5;g.e=6;

intA[MAXV][MAXV]={{0,1,0,1,0}