数据结构与算法(线性表)练习题(27页).doc

-数据结构与算法(线性表)练习题-第 27 页三、写一个算法合并两个已排序的线性表。（用两种方法：数组表示的线性表（顺序表）和指针表示的线性表（链表）要求：1、定义线性表节点的结构，并定义节点的型和位置的型。 2、定义线性表的基本操作 3、在1，2的基础上，完成本题。 4、在main函数中进行测试：先构建两个有序的线性表，然后合并这两个线性表。四、已知一个单向链表，试给出复制该链表的算法。要求：1、定义线性表的节点的结构以及节点的型和位置的型。 2、定义线性表的基本操作 3、在1，2的基础上，完成本题。 4、在main函数中进行测试：先构建一个线性表，并定义一个空线性表，然后进行复制。五、写出从一个带表头的单链表中删除其值等于给定值x的结点的算法函数：int delete(LIST &L, int x);如果x在该链表中，则删除对应结点，并返回其在链表中的位置（逻辑位置，第一个结点的逻辑位置为1），否则返回-1。要求：1、定义线性表的节点的结构以及节点的型和位置的型。2、定义线性表的基本操作3、在1，2的基础上，完成本题。4、在main函数中进行测试：先构建一个线性表，然后调用函数删除值等于给定值的节点。六、写出一个将两个静态链表（属于同一个存储池）合并的算法函数： void Merge(cursor M, cursor N); 合并的方法是将N链表中的所有结点添加到M链表的后面，并将N链表的表头结点添加到空闲结点链表中。要求：1、定义静态链表的结点的结构以及结点的型SPACE以及位置（position）和游标（cursor）的型。2、定义静态链表的基本操作：void Initialize(); 初始化，将所有存储池中的结点设置为空闲；cursor GetNode(); 从空闲链中获取一个结点；void FreeNode(cursor q); 将结点q加入到空闲链； void Insert ( elementtype x, position p, cursor M ); 在链表M中的位置为p的元素后面添加一个值为x的结点；void Delete (cursor M, position p ); 在链表M中删除位置为p的元素的后一个元素。3、在1、2的基础上完成本题。4、在main函数中进行测试：先构建一个存储池，然后在该存储池中创建两个静态表，最后将这两个静态表合并。七、利用指针表示的线性表(链表)表示一个多项式，并实现两个多项式的相加和相乘运算。假设多项式形式为： 其中，系数ai0，指数ei满足em>em-1>>e2>e1>=0。要求：1、定义多项式每一项的结构。2、定义两个多项式的相加和相乘运算函数。3、在main函数中，构建两个多项式，并测试相加和相乘运算。八、试编写一个整数进制转换的通用函数convert(int num, STACK S, int n)，要求将整数m转换为n进制数，n进制数的各位依次存放在栈S中。并在主函数中进行测试。要求：1、定义栈以及栈的型。2、定义栈的各种操作。 3、实现函数convert。 4、在main函数中，通过调用函数convert将num的n进制数存放到一个栈中，并通过出栈的方法输出该n进制数九、设有一个循环队列Queue，只有头指针front，不设尾指针，另设一个含有元素个数的计数器count，试写出相应的判断队列空、判断队列满、出队算法和入队算法。要求：1、定义相应的循环队列的型（只有头指针，没有尾指针，但有一个元素个数的计数器）；2、定义该队列的四个算法：判断队列空、判断队列满、出队算法和入队算法；3、在main函数验证算法的正确性。十、设主串T=“abcaabbabcabaacbacba“，模式为p=“abcabaa”。 1、计算模式p的nextval函数值2、不写算法，只画出利用KMP算法进行模式匹配时，每一趟的匹配过程。要求：1、写出模式p的nextval值；2、画出KMP算法的每一趟匹配过程（可参照教材P61从第8行开始的内容）；3、不需要编写程序。十一、假设表达式中允许包含三种括号：圆括号、方括号和大括号。设计一个算法采用顺序栈（用数组表示的栈）判断表达式中的括号是否正确配对。要求： 1、定义栈以及栈的型，栈中所存放元素的类型为字符型，定义枚举类型Boolean，其中两个元素分别为TRUE和FALSE。2、定义栈的各种操作。3、定义函数Boolean check(char *s); 判断s中的括号是否正确配对，如果正确配对，返回TRUE，否则返回FALSE。4、在主函数中验证所编写函数的正确性。十二、设有一个带头结点的双向链表h，设计一个算法用于查找第一个元素之为x的结点，并将其与其前驱结点进行交换。要求： 1、定义带头结点的双向链表的型DLIST。 2、定义双向链表DLIST的基本操作。 3、定义函数int swap(elementtype x, DLIST &h)，查找第一个元素之为x的结点，如果在链表中存在元素值为x的结点，并其与其前驱结点进行交换，并返回1，否则返回0。 4、在主函数中测试所编写函数的正确性。十三、试编写一个求三元组顺序表示的稀疏矩阵对角线元素之和的算法十四、当具有相同行值和列值的稀疏矩阵A和B均以三元组顺序表方式存储时，试写出矩阵相加的算法，其结果存放在以行逻辑链接顺序表方式存储的矩阵C中。十五、设有一个稀疏矩阵：1、写出三元组顺序表存储表示2、写出十字链表存储的顺序表示十六、画出广义表LS=( ), (e), (a, (b, c, d)的头尾链表存储结构(类似于教材P70图2-27.9)。要求：按照教材中的事例画出相应的图形，不需要编程。t 其中第一个节点如下：十七、试编写求广义表中原子元素个数的算法。要求：1、定义广义表的节点的型；2、定义广义表的基本操作；3、定义本题要求的函数int elements(listpointer L)；函数返回值为广义表中原子的个数。例如，广义表(a, b, c, d)原子的个数为4，而广义表(a, (a, b), d, e, (i, j), k)中院子的个数为3。提示：先利用基本操作Cal(L)获得表头，判断表头是不是原子，再利用基本操作Cdr(L)获得除第一个元素外的其他元素所形成的表L1，利用递归的方法求L1中原子的个数。要求：1、上述作业要求在单独完成；2、完成后，于规定期限内提交到ftp服务器的相应目录中中，注意，在提交时将所编写的程序统一拷贝到一个Word文件中，文件名格式为“学号+姓名”三（数组表示）#include<iostream>using namespace std;#define maxlength 100typedef int position;typedef int Elementtype;struct LISTElementtype elementsmaxlength;int last;position End(LIST L)/线性表长度 return (L.last+1);void Insert(Elementtype x,position p,LIST&L)position q;if(L.last>=maxlength-1)cout<<"list is full"<<endl;else if(p>L.last+1)|(p<1)cout<<"position does not exit"<<endl;elsefor(q=L.last;q>=p;q-)L.elementsq+1=L.elementsq;L.last=L.last+1;L.elementsp=x;void Delete(position p,LIST &L)position q;if(p>L.last)|(p<1)cout<<"position does not exist"<<endl;elseL.last=L.last-1;for(q=p;q<=L.last;q+)L.elementsq=L.elementsq+1;position Locate(Elementtype x,LIST L)position q;for(q=1;q<=L.last;q+)if(L.elementsq=x)return q;return(L.last+1); void merge(LIST&L,LIST&L1,LIST&L2)position p=0,p1,p2;position len1=End(L1);position len2=End(L2);L.last=len1+len2-1;for(p1=0;p1<End(L1);p1+)L.elementsp=L1.elementsp1;p+; p-;for(p2=0;p2<End(L2);p2+)L.elementsp=L2.elementsp2;p+; p-;void read(LIST &L)cout<<endl;cout<<"请输入线性表长度"<<endl;cin>>L.last;for(int i=0;i<L.last;i+)cin>>L.elementsi; void write(LIST &L) for(int i=0;i<L.last;i+) cout<<L.elementsi<<"t"cout<<endl;int main()LIST L,L1,L2;read(L1);write(L1);read(L2);write(L2);merge(L,L1,L2);write(L);数据结构三（指针）#include<iostream>using namespace std;typedef int Elementtype;struct celltypeElementtype element;celltype *next;typedef celltype *LIST;typedef celltype *position;position End(LIST L)position p;p=L;while(p->next!=NULL)p=p->next;return p;void Insert(Elementtype x,position p)position q;q=new celltype;q->element=x;q->next=p->next;p->next=q;void Delete(position p)/删除p的下一个节点 position q;if(p->next!=NULL)q=p->next;p->next=q->next;delete q;position Locate(Elementtype x,LIST L)position p;p=L;while(p->next!=NULL)if(p->next->element=x)return p;elsep=p->next;return p;position MakeNull(LIST&L)L=new celltype;L->next=NULL;return L; void merge(LIST&L,LIST&L1,LIST&L2)position p,p1,p2;for(p1=L1;p1;p1=p1->next)p=new celltype;p->element=p1->element;if(L=0)L=p;p2=p;elsep2->next=p;p2=p;p2->next=NULL;for(p1=L2;p1;p1=p1->next)p=new celltype;p->element=p1->element;if(L=0)L=p;p2=p;elsep2->next=p;p2=p;p2->next=NULL;void Read(LIST &L)position p1,p2;/p1=new celltype;cout<<"请输入数据以-1结束"<<endl;for(;)p1=new celltype;cin>>p1->element;if(p1->element=-1)break;if(L=0)L=p1;p2=p1;elsep2->next=p1;p2=p1;p2->next=NULL;void write(LIST&L)position p;p=L;for(;p;p=p->next)cout<<p->element<<"t"cout<<endl;int main()LIST L=NULL,L1=NULL,L2=NULL;Read(L1);write(L1);Read(L2);write(L2);merge(L,L1,L2);write(L);数据结构四#include<iostream>using namespace std;typedef int Elementtype;struct celltypeElementtype element;celltype *next;typedef celltype *LIST;typedef celltype *position;position End(LIST L)position p;p=L;while(p->next!=NULL)p=p->next;return p;void Insert(Elementtype x,position p)/节点插p节点之后 position q;q=new celltype;q->element=x;q->next=p->next;p->next=q;void Delete(position p)/删除P节点的下一个节点 position q;if(p->next!=NULL)q=p->next;p->next=q->next;delete p;position Locate(Elementtype x,LIST L)position p;p=L;while(p->next!=NULL)if(p->next->element=x)return p;else p=p->next;return p;position MakeNull(LIST &L)L=new celltype;L->next=NULL;return L;void Copy(LIST &L1,LIST &L2) position p1,p2,p3;for(p2=L2;p2;p2=p2->next)p1=new celltype;p1->element=p2->element;if(L1=0)L1=p1;p3=p1;elsep3->next=p1;p3=p1;p3->next=NULL;void Read(LIST &L)position p1,p2;p1=new celltype;cout<<"请输入数据以-1结束"<<endl;for(;)p1=new celltype;cin>>p1->element;if(p1->element=-1)break;if(L=0)L=p1;p2=p1;elsep2->next=p1;p2=p1;p2->next=NULL;void Write(LIST &L)position p=L;for(;p;p=p->next)cout<<p->element<<"t"cout<<endl;int main()LIST L1=NULL,L2=NULL;Read(L2);Write(L2);Copy(L1,L2);Write(L1);数据结构五#include<iostream>using namespace std;typedef int Elementtype;struct celltypeElementtype element;celltype *next; typedef celltype *LIST; typedef celltype *position;position End(LIST L)position p;p=L;while(p->next!=NULL)p=p->next;return p;void Insert(Elementtype x,position p)/插入到P后面的一个节点 position q;q->element=x;q->next=p->next;p->next=q;void Delete(position p)/删除P后面一个节点 position q;if(p->next!=NULL)q=p->next;p->next=q->next;delete q;int Delete(LIST &L,int x)position p=L;int count=1;if(p->element=x)return count;p=p->next;while(p->next!=NULL)count+;if(p->next->element=x)if(p->next->next!=NULL)position q;q=p->next;p->next=q->next;delete q;return count;elsedelete p->next;p->next=NULL;return count;elsep=p->next;return -1;position Locate(Elementtype x,LIST L)position p=L;while(p->next!=NULL)if(p->next->element=x)return p;elsep=p->next;return p;position MakeNull(LIST&L)L=new celltype;L->next=NULL;return L;void Read(LIST &L)position p1,p2;p1=new celltype;cout<<"请输入数据以-1结束"<<endl;for(;)p1=new celltype;cin>>p1->element;if(p1->element=-1)break;if(L=0)L=p1;p2=p1;elsep2->next=p1;p2=p1;p2->next=NULL;void Write(LIST &L)position p=L;for(;p;p=p->next)cout<<p->element<<"t"cout<<endl;int main()LIST L1=NULL;Read(L1);Write(L1);cout<<Delete(L1,3);cout<<endl;Write(L1);数据结构六#include<iostream>using namespace std;#define maxsize 100typedef int Elementtype;typedef structElementtype element;int next;spacestr;/节点类型 spacestr SPACEmaxsize;/存储池 typedef int position,cursor;cursor available;/游标变量，标识线性表 void Initialize()int j;for(j=0;j<maxsize-1;j+)SPACEj.next=j+1;/链接池中节点 SPACEj.next=-1;available=0;/标识线性表，将所有存储池中的节点设置为空闲，avaailable为头节点不利用 cursor GetNode()/从空闲链中获取一个节点 position p;if(SPACEavailable.next=-1)p=-1;elsep=SPACEavailable.next;SPACEavailable.next=SPACEp.next;return p;void FreeNode(cursor q)/将结点q加入到空闲链 SPACEq.next=available;available=q;void Insert(Elementtype x,position p,cursor M)/在链表M中的位置为p的元素后面添加一个值为x的结点position q;q=GetNode();SPACEq.element=x;SPACEq.next=SPACEp.next;SPACEp.next=q;void Delete(cursor M,position p)/在链表M中删除位置为P的元素的后一个元素 position q;q=GetNode();if(SPACEp.next!=-1)if(SPACESPACEp.next.next!=-1)q=SPACEp.next;SPACEp.next=SPACEq.next;FreeNode(q);elseq=SPACEp.next;FreeNode(q);/*合并:将N链表中的所有结点添加到M链表的后面，并将N链表的表头结点添加到空闲结点链表中。*/void Merge(cursor M,cursor N)position p=M;position q=N;while(SPACEp.next!=-1)p=SPACEp.next;SPACEp.next=SPACEq.next;position r=available;SPACEN.next=r;available=N;void Input(cursor M)/创建静态链表 Elementtype x;cursor p=0;cout<<"请输入静态链表的值以-1结束"<<endl;while(1)cin>>x;if(x!=-1)Insert(x,p,M);p=SPACEp.next;elseSPACEp.element=-1;p=-1;break;void Output(cursor M)position p;p=M;while(p!=-1)cout<<SPACEp.element<<"t"p=SPACEp.next; cout<<endl;int main()/spacestr s;Initialize();/position p=GetNode();SPACE0.element = 2; SPACE0.next = 6;SPACE1.element = 4; SPACE1.next = 3;SPACE2.next = 4;SPACE3.element = 8; SPACE3.next = -1;SPACE4.element = 10; SPACE4.next = 7;SPACE5.next = 0;SPACE6.element = 16; SPACE6.next = 1;SPACE7.element = 18; SPACE7.next = 9;SPACE8.element = 20; SPACE8.next = -1;SPACE9.element = 22; SPACE9.next = 8;available = 10;cursor M = 2;cursor N = 5;Output(M);Output(N);Merge(M, N);Output(M);Delete(M,3);Insert(34,3,M);Output(M);return 0;数据结构七#include<iostream>using namespace std;struct PolyNodeint coef;/系数 int expn;/指数PolyNode *next;typedef PolyNode *LIST;typedef PolyNode *position;void Input(LIST &L,int n)position p1,p2;cout<<"输入数据系数和指数(并且以指数从大到小方式输入)"<<endl;for(int i=0;i<n;i+)p1=new PolyNode; cin>>p1->coef>>p1->expn;if(L=0)L=p1;p2=p1;elsep2->next=p1;p2=p1;p2->next=NULL; void Output(LIST&L)position p;p=L;for(;p;p=p->next)cout<<"+"<<p->coef<<"X"<<p->expn;cout<<endl;void Plus(LIST &L,LIST &L1,LIST &L2)position p,p1=L1,p2=L2,pp;while(p1!=NULL|p2!=NULL)p=new PolyNode;if(p1=NULL&&p2!=NULL)p->coef=p2->coef;p->expn=p2->expn;if(L=0)L=p;pp=p;elsepp->next=p;pp=p;p2=p2->next;if(p1!=NULL&&p2=NULL)p->coef=p1->coef;p->expn=p1->expn;if(L=0)L=p;pp=p;elsepp->next=p;pp=p;p1=p1->next;elseif(p1->expn>p2->expn)p->coef=p1->coef;p->expn=p1->expn;if(L=0)L=p;pp=p;elsepp->next=p;pp=p;p1=p1->next;if(p1->expn<p2->expn)p->coef=p2->coef;p->expn=p2->expn;if(L=0)L=p;pp=p;elsepp->next=p;pp=p;p2=p2->next;elsep->coef=(p1->coef)+(p2->coef);p->expn=p1->expn;if(L=0)L=p;pp=p;elsepp->next=p;pp=p;p1=p1->next;p2=p2->next;pp->next=NULL;void Multiply(LIST &L,LIST&L1,LIST &L2)position p,p1,p2,pp;p1=new PolyNode;p1=L1;while(p1!=NULL)p2=new PolyNode;p2=L2;while(p2!=NULL)p=new PolyNode;p->coef=(p1->coef)*(p2->coef);p->expn=(p1->expn)*(p2->expn);if(L=0)L=p;pp=p;elsepp->next=p;pp=p;p2=p2->next;p1=p1->next;pp->next=NULL;int main()LIST L1=NULL,L2=NULL,L3=NULL,L4=NULL;Input(L1,3);Output(L1);Input(L2,3);Output(L2);Plus(L3,L1,L2);Output(L3);Multiply(L4,L1,L2);Output(L4);return 0;数据结构八#include<iostream>using namespace std;#define maxlength 100typedef int Elementtype;struct STACKint top;Elementtype elementsmaxlength;void MakeNull(STACK &S)/将栈设置为空 S.top=maxlength;bool Empty(STACK &S)/测试栈是否为空 if(S.top>=maxlength)return true;elsereturn false;Elementtype Top(STACK S)/返回栈顶元素 if(Empty(S)cout<<"stack is empty"<<endl;elsereturn (S.elementsS.top);void Pop(STACK &S)/删除栈顶元素 if(Empty(S)cout<<"stack is empty"<<endl;elseS.top=S.top+1;void Push(Elementtype x,STACK &S)if(S.top=0)cout<<"stack is full"<<endl;elseS.top=S.top-1;S.elementsS.top=x;void Convert(int num,STACK &S,int n)MakeNull(S);while(num!=0) Push(num%n,S);num=num/n;void Output(STACK &S)while(!Empty(S)cout<<S.elementsS.top;S.top+;cout<<endl;int main()STACK S;Convert(8,S,3);Output(S);数据结构九#include<iostream>using namespace std;#define maxlength 100typedef int Elementtype;struct QUEUEint front;int count;Elementtype elementsmaxlength;void MakeNull(QUEUE &Q)/将队列设置为空 Q.front=0;Q.count=0;bool Empty(QUEUE Q)/测试队列是否为空 if(Q.count=0)return true;elsereturn false;bool Full(QUEUE Q)if(Q.count=maxlength)return true;else return false;Elementtype Front(QUEUE Q)/返回队列的第一个元素 if(Empty(Q)