发布时间 : 星期五 文章计算机软件技术基础所有题目答案-自学更新完毕开始阅读ead69b2e5727a5e9856a61a9
if(!q) exit(0)；
if(pre==la) la=q—>next； ／／i=1的情况 else pre—>next=q—>next； ／／完成删除 ／／将从la中删除的结点插入到lb中
if(j==1) {q->next=lb； lb=p； } ／／j=1时 else { r=lb; k=1； ／／j>1时
while(r&&k
q—>next=r—>next；r—>next=p； ／／完成插入 } }
7．单链表L是一个递减有序表，试写一高效算法，删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删结点空间，这里min和max是两个给定的参数。 答：LinkedList delete(LinkedList L，int min，int max) {／／删除递减有序单链表L中值大于min且小于max的结点 q=L；
if(min>max) {printf(”min>max＼n”)；exit(0)；} else p=L—>next； ／／q始终指向p的前驱
while(p—>data>=max) ／／当前元素大于或等于max，则p、q依次向后移动 {q=p；p=p—>next；}
while((p!=NULL)&&(p一>data>min))
{／／当前元素的值比min大同时比max小，删除p指向的结点 q—>next=p—>next， free(p)；p=q—>next； } return L； }．
8．编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B，其头结点指针分别为pa和pb，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。
答：分析：用两个工作指针p和q分别指示序号为奇数和序号为偶数的结点，将q所指向的结点从A表删除，并链接到B表。
void decompose(LinkedList A，LinkedList B)
{／／单链表A分解成元素序号为奇数的单链表A和元素序号为偶数的单链表B p=A->next； B=(LinkedList)malloc(sizeof(LNode))； r=B；
while(p!=NULL&&p->next!=NULL)
{q=p—>next； ／／q指向偶数序号的结点 p—>next=q—>next； ／／将q从A表中删除
r—>next=q； ／／将q结点链接到B链表的末尾 r=q； ／／r总是指向B链表的最后—·个结点
p=p—>next； ／／p指向原链表A中的奇数序号的结点 }
r—>next=NULL； ／／将生成B链表中的最后一个结点的next域置为空 }
9．假设以两个元素依值递增有序排列的线性表A、B分别表示两个集合，要求另辟空间构造一个线性表C，其元素为两集合的交集，且表C中的元素也依值递增有序排列。对顺序表编写求C的算法。
答：分析：用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置，若A、B表中当前元素值相同，则写入C中，并使i、j、k值增1；若A表元素值较小，则使i增1；若B表元素值较小，则使j增1，直到有一个表先结束。
SeqLiSt intersection(SeqList A，SeqList B，SeqList C) {／／求元素依值递增有序排列的顺序表A、B的交集C
9
i=0； j=0；k=0；
while((i<=A.length-1)&&(j<=B.length-1))
{if(A.data[i]==B.data[j]) ／／找到值相同的元素 {C.data[k]=A.data[i]； ／／相同元素写入C表中 k++；i++；j++； } else
if(A.data[i] C.length=k； return C； } 10．设有线性表A=(a1，a2，?，am)和B=(b1，b2，?，bn)。试编写合并A、B为线性表C的算法，使得： C=(a1，b1，?，am，bm，bm+1，?bn)(当m≤n时)或 (a1，b1，?，an，bn， an+1，?am)（当m>n时），线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表的结点空间。 答：分析：使p和q指向A和B表当前元素，并分别使nextp和nextq指向p和q的后继，这样将q所指向的结点链接到p的后面，再把nextp和nextq的值赋给p和q，处理下一个结点。 void merge(LinkedList A，LinkedList B，LinkedList C) {／／把链表A和B合并为C，A和B的元素间隔排列，且使用原存储空间 p=A—>next；q=B—>next；C=A； while(p&&q) {nextp=p—>next；p—>next=q； ／／将B的元素插入 if(nextp) {nextq=q->next；q->next=nextp；}／／如果A非空，将A的元素插入 p=nextp； q=nextq； } } 11．假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前驱结点。 答：分析：因为既不知道此单循环链表的头指针，也不知道其尾指针，所以找s的前驱就只能从s开始，顺次向后寻找。 void DeletePre(LinkedNode *s) {／／删除单循环链表中结点s的直接前驱 p=s； while(p—>next—>next!=s) p=p—>next； ／／找到s的前驱的前驱p q=p—>next； ／／q是p的后继，即s的前驱 p—>next=s； ／／将q删除 free(q)； } 12．计算带头结点的循环链表的结点个数。 答：int number(LinkedNode head) {／／计算单循环链表中结点的个数 p=head—>next； i=0； while(p!=head) {i++；p=p->next；} return i； } 13．已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其他字符)，试编写算法构造三个以循环链表表示的线性表，使得每个表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。 答：分析：p指向待处理的单链表的首元结点，构造三个空的单循环链表，分别存储三类字符，其中一个可使用原来的单链表。q指向p的下一个结点，根据*p的数据域的值将其插入到不同的链表上。再把q的值给p，处理下一个结点。 void change(LinkedList L，LinkedList pa，LinkedList pb，LinkedList pc) {／／分解含有三类字符的单链表为三个以循环链表表示的线性表，使其分别含有三类字符 p=L—>next； pa=L； pa—>next=pa； ／／分别构造三个单循环链表 10 pb=(LinkedList)malloc(sizeof(LNode))； pc=(LinkedList)malloc(sizeof(LNode))； pb—>next=pb；pc—>next=pc； while(p!=L) {q=p—>next；· ／／q记下L中下一个结点的位置 if(p—>data<=’z’&&p—>data>=’a’) ／／链接到字母链表的头部 {p—>next=pa—>next；pa—>next=p；} else if (p—>data<=’9’ &&(p—>data>=’0’) ／／链接到数字链表的头部 {p—>next=pb—>next；pb—>next=p；} else{p->next=pc->next；pc->next=p；}／／链接到其他字母链表的头部 p=q； } } 14、己知A、B和C为三个递增有序的线性表，现要求对A表进行如下操作：删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法(注：题中未特别指明同一表中的元素值各不相同)。 答：分析：先从B和C中找出共有元素，记为same，再在A中从当前位置开始，凡小于same的元素均保留(存到新的位置)，等于same的就跳过，到大于same时就再找下一个Same SeqList IntersectDelete(SeqList A，SeqList B，SeqList C) {／／对顺序表A删去那些既在B表中出现又在C表中出现的元素 i=0；j=0；k=0；m=0; ／／i指示A中元素原来的位置，m为移动后的位置 while(i else if(B.data[j]>C.data[k]) k++; else {same=B.data[j]； ／／找到了相同元素same while(B.data[j]==same) j++； while(C.data[k]==same) k++； ／j、k后移到新的元素 while(i A.data[m++]=A.data[i++]；／／需保留的元素移动到新位置 while(i while(i A.data[m++]=A.data[i++]； ／／A的剩余元素重新存储 A.1ength=m； } 15．双循环链表中，设计满足下列条件的算法。 (1)在值为x的结点之前插入值为y的结点。(2)在值为x的结点之后插入值为y的结点。(3)删除值为x的结点。 答：分析：在双循环链表中插入和删除结点要注意修改双向的指针。 typedef struct DLNode {DataType data； struct DLNode*prior，*next；}DLNode，*DLinkedList； void DLinsertl(DLinkedList L，int x，int y) { ／／在双循环链表中插入结点 p=L->next； while(p!=L&&p->data!=x) p=p->next； ／／在链表中查找值为x的结点 if(p->data==x) ／／找到值为x的结点 {q=p->prior； ／／q指向值为x的结点的前驱 s=(DLinkedList)malloc(sizeof(DLNode))； s->data=y； s->next=p； s->prior=q； ／／将y插入到q与p指向的结点之间 p->prior=s；q->next=s； } 11 else{printf(”没有值为x的结点”)；exit(0)；} } void DLDelete(DLinkedList L，int x) {／／在双循环链表中删除结点 p=L->next； while(p!=L&&p->data!=x)p=p->next； if(p->data==x) {p->prior->next=p->next；p->next->prior=p->prior；free(p)；} else{printf(”没有值为x的结点”)；exit(0)；} } 16．设有一个双循环链表，其中有一结点的指针为p，编写算法将p与其右边的一个结点进行交换。 答：void DLchange(DLinkedList p) {／／将双循环链表中p指向的结点与其右边的一个结点进行交换 q=p—>next； ／／q指向p的后继 p—>prior—>next=q；q—>prior=p—>prior； ／／将p的前驱与q相链接 p—>next=q—>next；p—>prior=q； ／／将p插入到q之后 q->next—>prior=p；q—>next=p； } 17．设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个可访问颊度域freq，在链表启用之前，其值均初始为0。每当链表进行一次LocateNode(L，x)操作时令元素值为x的结点中freq域的值加l，并调整表中结点的次序，使其按访问频度的递减次序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode操作的算法。 答：分析：先在双链表中查找值为x的结点，若找到则使其freq值增1，然后从头至尾扫描链表，将此结点插入到按freq递减顺序排列的正确位置。 typedef struct DLNode {int data，freq；struct DLNode *prior，*next；}DLNode，*DLinkedList； void LocateNode(DLinkedList head，int x) {／／双链表按访问频度域freq递减次序排列 p2=head； p1=p2—>next； ／／p2在前，p1在后 whue(p1) ／／查找单链表中值为x的结点 if(pl—>data==x) {pl—>freq++； break；}／／使值为x的结点的freq加1 else {p2=pl；p1=p2—>next；} if(p1==NULL) printf(”Not found.＼n”)； else{if(p1—>next==NULL) {p2—>next=p1—>next；temp=p1；} ／／在链表中找temp所指向的结点，按freq值递减应插入的位置 else{p2—>next=p1—>next； ／／插入链表中间的某一位置 p1—>next->prior=p2； temp=pl；} for(p2=head，p1=p2->next；pl&&p1->freq>temp->freq；p2=p1，pl=p2->next)；／／插 入 if(p1==NULL) {p2->next=temp；temp->prior=p2；temp->next=NULL；} else {p2->next=temp；temp->prior=p2；temp->next=pl；p1->prior=temp；} } } 18．给出用单链表存储多项式的结构，并编写一个按指数值递增次序输入所产生的多项式链表的过程。 答：typedef struct PNode {int coef； ／／系数 int exp； ／／指数 struct Pnode *next；}*PLink； PLink CreatPoly( ) {／／建立多项式 head=(PLink)malloc(sizeof(struct PNode))； 12