习题配套
第一章
2．C、A、B、B、A、A、D
3．
D={A,B,C,E,F,G,H,I,J};
R={<A,B>,<A,C>,<A,E>,<B,F>,<B,G>,<E,H>,<E,I>,<E,J>,<H,I>,<I,J>}
J
4．顺序、链式、索引、哈希。
*5．解：100n2>2nn至少要多大
6.Ｏ(n)、Ｏ(n)、Ｏ(n)、Ｏ()、
(5)当n>m，Ｏ(n),当m>n，Ｏ(m)
7．n!
2100>lgn>n1/2>n3/2>(3/2)n>2n>nlgn>nn
第二章
1．×、√、×、√、√
2．AAD
4．顺序表
void Delete_SeqListx(SeqList *L,ElemType x)
/*删除表中值为x元素*/
{inti,j;
for(i=1;i<=L->length;i++){
if(L->elem[i]==x){
for(j=i;j<=L->length-1;j++)
L->elem[j]=L->elem[j+1];
L->length--;
}/*向上移动*/
}
O(n2)
链表
void del_link(LinkList H，int x)/*删除数据域为x的结点*/
{
LNode *p，*q;
p=H;q=H->next;
while(q!=NULL)
{
if(q->data==x){
p->next=q->next;free(q);q=p->next;
}
else{p=q;q=q->next;}
}
}
O(n)
5．
int Delete_SeqListx(SeqList *L,int i,int k)
/*删除表中删除自第i个结点开始的k个结点*/
{intj;
if(i<1||k<0||i+k-1>L->length)
/*检查空表及删除位置的合法性*/
{printf(＂不存在第i个元素＂);
return ERROR;}
for(j=i;j<=L->length-k;j++)
L->elem[j]=L->elem[j+k]; /*向上移动*/
L->length-=k;
Return OK;/*删除成功*/
}
O(n)
6．
void Delete_SeqListx(SeqList *L,ElemType x)
/*将表中值为x元素换成y*/
{inti,j;
for(i=1;i<=L->length;i++){
if(L->elem[]==x){
L->elem[i]=y;
}/* */
}
O(n)
7．写一算法在循环单链表上实现线性表的CList_length(L)运算。
int link_length(LinkList  H)
{
LNode *p;int i=0;
p=H;
while(p->next!=H)
{i++;
p=p->next;
}
return i;
}
O(n)
8．
在用头指针表示的单循环链表中，查开始结点a1的时间是O(1)，然而要查终端结点则需从头指针开始遍历整个链表，其时间是O(n)。但在很多实际问题中，表的操作常常是在表的首、尾位置上进行，如果改用尾指针rear来表示单循环链表，则查开始结点a1和终端结点an都很方便，它们的存储位置分别是c语言listinsert函数rear->next->next和rear，显然，查时间都是O(1)。
9.
int Insert_LinkListab(LinkList H, ElemType a,ElemType b)
/*在单链表中值为a的结点前插入一个值为b的结点*/
{LNode*q=H,*s;*p=H->next;
while(p!=NULL&&p->data!=a) /*q->next&&q->next->data!=a*/
{q=p;p=p->next;
}/*查a结点*/
s=(LinkList)malloc(sizeof(LNode));/*申请、填装结点*/
s->data=b;
s->next=q->next;/*新结点插入在第i-1个结点的后面*/
q->next=s；
return OK;
}/*Insert_LinkListab*/
10．顺序表
void Reverse_Sq(SqList *L)/*顺序表的就地逆置*/
{
for(i=1，j=L.len;i<j;i++)
{t=L.elem[i];L.elem[i]=L.elem[L.len-i+1];L.elem[L.len-i+1]=t;}
}/*Reverse_Sq*/
单链表
void  Reverse_L(LinkList *H)/*为简化算法，假设表长大于2*/
{
p=H->next;q=p->next;s=q->next;p->next=NULL;
while(s->next)
{
q->next=p;p=q;
q=s;s=s->next;/*把H的元素逐个插入新表表头*/
}
q->next=p;s->next=q;H->next=s;
}/*Reverse_L*/
分析：本算法的思想是，逐个地把L的当前元素q插入新的链表头部，p为新表表头。
11．
void merge1(LinkList &A,LinkList &B,LinkList &C)
/*把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间*/
{p=A->next;q=B->next;C=A;
while(p&&q)
{
s=p->next;p->next=q;/*将B的元素插入*/
if(s)
{
t=q->next;q->next=s;/*如A非空,将A的元素插入*/
}
p=s;q=t;
}/*while*/
}/*merge1*/
12．
Status  Delete_Pre(CiLNode  s)/*删除单循环链表中结点p的直接前驱*/
{
q=p;
while(q->next->next!=p)q=q->next;/*到p的前驱的前驱*/
s=q->next;q->next=p;free(s);
return OK;
}/*Delete_Pre*/
13．
Status Insert_SqList(SeqList  &L，int x)
{
if(L->length+1>m-1)return ERROR;
L->length++;i=L->length;
while(L->elem[i]>x&&i>0;)
{L->elem[i+1]=L->elem[i];i--;}
L->elem[i+1]=x;
return OK;
}/*Insert_SqList
14．
intInsert_Linkx(LinkList H,ElemType x)
/*在值递增单链表中插入一个值为x的结点，仍递增*/
{LNode*q=H,*s;*p=H->next;
while(p!=NULL&&p->data<x)/*q->next&&q->next->data<x*/
{q=p;p=p->next;
}/*查a结点*/
s=(LinkList)malloc(sizeof(LNode));/*申请、填装结点*/
s->data=x;
s->next=q->next;/*新结点插入*/
q->next=s；
return OK;
}/*Insert_Linkx*/
15．
源程序代码：（在TubroC2.0测试通过）
#include<stdlib.h>
#include<alloc.h>
structnode
{
intnumber;/*人的序号*/
intcipher;/*密码*/
structnode*next;/*指向下一个节点的指针*/
};
structnode*CreatList(intnum)/*建立循环链表*/
{
inti;
structnode*ptr1,*head;
if((ptr1=(structnode*)malloc(sizeof(structnode)))==NULL)
{
perror("malloc");
returnptr1;
}
head=ptr1;
ptr1->next=head;
for(i=1;i<num;i++)
{
if((ptr1->next=(structnode*)malloc(sizeof(structnode)))==NULL)
{
perror("malloc");
ptr1->next=head;
returnhead;
}
ptr1=ptr1->next;
ptr1->next=head;
}
returnhead;
}
main()
{
inti,n=30,m;/*人数n为30个*/
structnode*head,*ptr;
randomize();
head=CreatList(n);
for(i=1;i<=30;i++)
{
head->number=i;
head->cipher=rand();
head=head->next;
}
m=rand();/*m取随机数*/
i=0;/*因为我没办法删除head指向的节点，只会删除head的下一节点，所以只能从0数起。*/
while(head->next!=head)/*当剩下最后一个人时，退出循环*/
{
if(i==m)
{
ptr=head->next;/*ptr记录数到m的那个人的位置*/
printf("number:%d\n",ptr->number);
printf("cipher:%d\n",ptr->cipher);
m=ptr->cipher;/*让m等于数到m的人的密码*/
head->next=ptr->next;/*让ptr从链表中脱节，将前后两个节点连接起来*/
head=hea/d->next;/*head移向后一个节点*/
free(ptr);/*释放ptr指向的内存*/
i=0;/*将i重新置为0，从0再开始数*/
}
else
{
head=head->next;
i++;
}
}
printf("number:%d\n",head->number);
printf("cipher:%d\n",head->cipher);
free(head);/*让最后一个人也出列*/
}
16．
void SqList_Intersect(SqList A,SqList B,SqList &C)/*求元素递增排列的线性表A和B的元素的交集并存入C中*/

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。