答：应选用链式存储结构。因为顺序表是静态存储结构，只能预先分配，不能随着线性表长度的改变而变化。而链表则可根据需要动态地申请空间，因此适用于动态变化表长的线性表。
8．若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构？为什么？
答：应选用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为O(1)。 五、算法设计题
假设算法中用到的顺序表和链表结构如下： #define maxsize 100;
Typedef struct node1 {datatype data[maxsize]; int length } SeqList; Typedef struct node2 {datatype data; struct node2 *next } LinkedList ;
1．试用顺序表作为存储结构，实现将线性表(a0，a1，a2，?an-1)就地逆置的操作，所谓“就地”是指辅助空间为O(1)。
答：(1)顺序表的就地逆置
分析：分别用两个整型变量指向顺序表的两端，同时向中间移动，移动的同时互换两个下标指示的元素的值。 void Seqreverse(SeqList *L){／／顺序表的就地逆置 for(i=0；j=L->length-1；i {t=L->data[i]; L->data[i]=L.data[j]; L->data[j]=t; } } (2)链表的就地逆置 分析：本算法的思想是逐个地把L的当前元素r插入到新的链表头部。 void Linkedreverse(LinkedList *L){／／链表的就地逆置 p=L->next；L->next=NULL； while(p!=NULL) {r=p，p=p->next； ／／r指向当前待逆置的结点，p记下下—个结点 r->next=L—>next；L->next=r； ／／放到表头 } } 2．设顺序表L是一个递增(允许有相同的值)有序表，试写一算法将x插入L中，并使L仍为一个有序表。 答：分析：先找到x的正确插入位置，然后将大于x的元素从后向前依次向下移动，最后将x插入到其位置上，同时顺序表长度增1。 void SeqListinsert(SeqList *L，int x){／／x插入到递增有序的顺序表L中 i=0; while((i<=L->length-1)&&(x>=L->data[i])) i++； ／／找正确的插入位置 for(k=L->length-1;k>=i；k--) ／／元素从后往前依次后移 L->data[k+1]=L->data[k]； L->data[i]=x； ／／x插入到正确位置 L->length++； ) 3.设单链表L是一个递减有序表，试写一个算法将x插入其中后仍保持L的有序性。 答：分析：此问题的关键是在链表中找到x的插入位置，因此需要两个指针一前一后地依次向后移动。 void LinkListinsert(LinkedList *L，int x){／／x插入有序链表L中 q=L；p=q—>next； while(p!=NULL&&p—>data>x) ／／找到插入的位置 {q=p；p=p—>next； } s=(LinkedList*)malloc(sizeof(LinkedList))； ／／生成新结点 S—>data=x； S—>next=p； q—>next=s； } 4. 试写出在不带头结点的单链表的第i个元素之前插入一个元素的算法。 答：分析：对不带头结点的链表操作时，要注意对第一个结点和其他结点操作的不同。 void LinkedListlnsert(LinkedList *L，int x，int i) {／／不带头结点的单链表的第i个元素之前插入一个元素 p=L：j=1; while(p!=NULL&&j if(i<=0||p==NULL) printf(”插入位置不正确＼n”)； else {q=(LinkedList*)malloc(sizeof(LinkedList))；q—>data=x； if(i==1) {q—>next=L；L=q；} ／／在第一个元素之前插入 else{q—>next=p—>next；p—>next=q；} ／／在其他位置插入 } } 6 5．设A、B是两个线性表，其表中元素递增有序，长度分别为m和n。试写一算法分别以顺序存储和链式存储将A和B归并成一个仍按元素值递增有序的线性表C。 答：(1)分析：用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置，将A、B表中较小的元素写入C中，直到有一个表先结束。最后将没结束的表的剩余元素写入C表中。 SeqList *Seqmerge(SeqList A，SeqList B，SeqList *C){／／有序顺序表A和B归并成有序顺序表C i=0；j=0；k=0； ／／i，i，k分别为顺序表A，B，C的下标 while(i {if(A.data[i] else {C->data[k]=B.data[j];j++；} ／／B中当前元素较小 k++； } if (i==m) for(t=j；t VOid Linkmerge(LinkedList *A，LinkedList *B，LinkedList *C) {／／有序链表A和B归并成有序链表C pa=A—>next；pb=B—>next；C=A；pc=C； while(pa&&pb) ／／A和B都不为空时 {if(pa—>data {qa=pa->next； pC->next=pa； pc=pc->next； pa=qa；} else {qb=pb->next；pc->next=pb：pc=pc->next；pb=qb；} ／／B当前结点值较小 } if(pa)pc—>next=pa； ／／A没有结束，将A表剩余元素链接到C表 if(pb)pc—>next=pb； ／／B没有结束，将B表剩余元素链接到C表 free(B)； ／／释放B表的头结点 } 本算法需要遍历两个线性表，因此时间复杂度为O(m+n)。 6．设指针la和lb分别指向两个不带头结点的单链表的首结点，设计从表la中删除第i个元素起共len个元素，并将这些元素插入到lb中第j个结点之前的算法。 答：分析：先在la中找到第i个结点，分别用两个指针pre和p指向第i-1和第i个结点，然后用指针q从第i个结点起向后走len个元素，使q指向此位置。然后在lb中找到第j个结点，将p所指向的la表中的第i个及q所指向的最后一个共len个结点插入到lb中。 void Deletelnsert(LinkedList *la，LinkedList *lb，int i，int j, int len) {／／删除不带头结点的单链表la中第i个元素起共len个元素,并将这峰元素插入到单链表lb中第j个结点之前 if(i<0||j<0||len<0) exit(0)； p=la；k=1；pre=NULL； while(p&&k q=p；k=l； ／／p指向la表中第i个结点 while(q&&k 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) 7 {／／删除递减有序单链表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(LinkedList))； 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 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； } 11．假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前驱结点。 答：分析：因为既不知道此单循环链表的头指针，也不知道其尾指针，所以找s的前驱就只能从s开始，顺次向后寻找。 void DeletePre(Linkedlist *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．计算带头结点的循环链表的结点个数。 8 答：int number(Linkedlist *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； ／／分别构造三个单循环链表 pb=(LinkedList*)malloc(sizeof(LinkedList))； pc=(LinkedList*)malloc(sizeof(LinkedList))； 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(ilength&&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(ilength&&A->data[i] A->data[m++]=A->data[i++]；／／需保留的元素移动到新位置 while(i1ength&&A->data[i]==same; i++；／／跳过相同的元素 } } while(ilength) A->data[m++]=A->data[i++]； ／／A的剩余元素重新存储 A->1ength=m； } 15．双循环链表中，设计满足下列条件的算法。 (1)在值为x的结点之前插入值为y的结点。(2)删除值为x的结点。 答：分析：在双循环链表中插入和删除结点要注意修改双向的指针。 typedef struct Node {DataType data； struct Node *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的结点 9 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； } 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与其右边的一个结点进行交换。 答：typedef struct Node {DataType data； struct Node *prior，*next；}DLNode，*DLinkedList； 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在后 while(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))； r=head； printf(”输入系数和指数：”)； scanf(&n，&m)； while(n!=0) ／／若n=0则退出循环 10 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库软件基础习题 答案 - 图文(2)在线全文阅读。
相关推荐：