数据结构与算法练习题

1、三、写一个算法合并两个已排序的线性表。 (用两种方法：数组表示的线性表(顺序表)和 指针表示的线性表(链表) )要求： 1、定义线性表节点的结构，并定义节点的型和位置的型。2 、定义线性表的基本操作3 、在 1，2 的基础上，完成本题。4 、在 main 函数中进行测试： 先构建两个有序的线性表， 然后合并这两个线性表。四、已知一个单向链表，试给出复制该链表的算法。要求： 1、定义线性表的节点的结构以及节点的型和位置的型。2 、定义线性表的基本操作3 、在 1，2 的基础上，完成本题。4 、在 main 函数中进行测试： 先构建一个线性表，并定义一个空线性表， 然后进 行复制。五、写出从一个带

2、表头的单链表中删除其值等于给定值 x 的结点的算法函数：int delete(LIST &L, int x);如果 x 在该链表中，则删除对应结点，并返回其在链表中的位置(逻辑位置，第一个结点的逻辑位置为1)，否则返回 -1 。要求： 1、定义线性表的节点的结构以及节点的型和位置的型。2、定义线性表的基本操作3、在 1，2 的基础上，完成本题。4、在 main 函数中进行测试： 先构建一个线性表， 然后调用函数删除值等于给定 值的节点。六、写出一个将两个静态链表(属于同一个存储池)合并的算法函数：void Merge(cursor M, cursor N); 合并的方法是将 N 链表中的所有结

3、点添加到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的结点；v

4、oid Delete (cursor M, position p );在链表M中删除位置为p的元素的后一个元素。3、在 1、 2 的基础上完成本题。4、在 main 函数中进行测试：先构建一个存储池，然后在该存储池中创建两个静态 表，最后将这两个静态表合并。七、利用指针表示的线性表 ( 链表 ) 表示一个多项式，并实现两个多项式的相加和相乘运算。 假设多项式形式为： A(x) amt em am 1xem1 . a1xe1其中，系数 ai工0,指数 ei满足emem-1“28=0。要求： 1、定义多项式每一项的结构。2、定义两个多项式的相加和相乘运算函数。3、在 main 函数中,构建两个多项

5、式,并测试相加和相乘运算。八、试编写一个整数进制转换的通用函数 convert(int num, STACK S, int n) ，要求将整 数 m 转换为 n 进制数， n 进制数的各位依次存放在栈 S 中。并在主函数中进行测试。 要求： 1、定义栈以及栈的型。2、定义栈的各种操作。3 、实现函数 convert 。4 、在 main 函数中，通过调用函数 convert 将 num 的 n 进制数存放到一个栈中， 并通过出栈的方法输出该 n 进制数九、设有一个循环队列Queue,只有头指针front，不设尾指针，另设一个含有元素个数的计数器 count ，试写出相应的判断队列空、判断队列满

6、、出队算法和入队算法。要求：1、定义相应的循环队列的型 (只有头指针, 没有尾指针, 但有一个元素个数的计数器)2、定义该队列的四个算法：判断队列空、判断队列满、出队算法和入队算法；3、在 main 函数验证算法的正确性。十、设主串 T=“ abcaabbabcabaacbacba “,模式为 p=“ abcabaa”。1 、计算模式 p 的 nextval 函数值2、不写算法，只画出利用KMP算法进行模式匹配时，每一趟的匹配过程。要求：1、写出模式 p 的 nextval 值；2、 画出KMP算法的每一趟匹配过程(可参照教材 P61从第8行开始的内容)；3、不需要编写程序。十一、 假设表达式

7、中允许包含三种括号： 圆括号、 方括号和大括号。设计一个算法采用顺序 栈(用数组表示的栈)判断表达式中的括号是否正确配对。要求：1 、定义栈以及栈的型,栈中所存放元素的类型为字符型,定义枚举类型Boolean,其中两个元素分别为 TRUE和FALSE2、定义栈的各种操作。3、定义函数 Boolean check(char *s); 判断 s 中的括号是否正确配对,如果正确配对, 返回TRUE否则返回FALSE4、在主函数中验证所编写函数的正确性。十二、设有一个带头结点的双向链表h，设计一个算法用于查找第一个元素之为x的结点，并将其与其前驱结点进行交换。要求：1 、定义带头结点的双向链表的型 D

8、LIST。2 、定义双向链表 DLIST的基本操作。3 、定义函数 int swap(elementtype x, DLIST &h) ，查找第一个元素之为 x 的结 点，如果在链表中存在元素值为 x 的结点，并其与其前驱结点进行交换，并返回 1，否则返 回 0。4 、在主函数中测试所编写函数的正确性。十三、试编写一个求三元组顺序表示的稀疏矩阵对角线元素之和的算法十四、当具有相同行值和列值的稀疏矩阵A和B均以三元组顺序表方式存储时，试写出矩阵相加的算法，其结果存放在以行逻辑链接顺序表方式存储的矩阵C中。卜五、设有个稀疏矩阵：04000000003001800000000050000700020

9、00060001、写出三元组顺序表存储表示2、写出十字链表存储的顺序表示十六、画出广义表 LS=( ), (e), (a, (b, c, d) 图。的头尾链表存储结构(类似于教材P70要求：按照教材中的事例画出相应的图形，不需要编程。其中第一个节点如下:t1十七、试编写求广义表中原子元素个数的算法。要求：1、定义广义表的节点的型；2、定义广义表的基本操作；3、 定义本题要求的函数int eleme nts(listpoi nter L);函数返回值为广义表中原子的个数。例如，广义表(a, b, c, d)原子的个数为4，而广义表(a, (a, b), d, e, (i,j),k)中院子的个数为

10、3。提示：先利用基本操作Cal(L)获得表头，判断表头是不是原子，再利用基本操作Cdr(L)获得除第一个元素外的其他元素所形成的表L1,利用递归的方法求 L1中原子的个数。要求：1、上述作业要求在单独完成；2、 完成后，于规定期限内提交到ftp服务器的相应目录中中，注意，在提交时将所编写的程序统一拷贝到一个 Word文件中，文件名格式为“学号+姓名”三(数组表示)#in cludeusing n amespace std;#defi ne maxle ngth 100typedef int positi on;typedef int Eleme nttype;struct LISTElemen

11、ttype elementsmaxlength;int last;position End(LIST L)ext=j+1;ext=-1;available=0;ext=-1)p=-1;elsep=SPACEavailable.next;SPACEavailable.next=SPACEp.next;return p;void FreeNode(cursor q)ext=available;available=q;void Insert(Elementtype x,position p,cursor M)lement=x;SPACEq.next=SPACEp.next;SPACEp.next=q

12、;void Delete(cursor M,position p)ext!=-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

13、=SPACEq.next;position r=available; SPACEN.next=r; available=N;void Input(cursor M)ext;else SPACEp.element=-1; p=-1;break;void Output(cursor M)position p; p=M; while(p!=-1) coutSPACEp.elementt; p=SPACEp.next;coutendl;int main()lement = 2; SPACE0.next = 6;SPACE1.element = 4; SPACE1.next = 3; SPACE2.ne

14、xt = 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

15、(M); Output(N);Merge(M, N);Output(M);Delete(M,3);In sert(34,3,M); Output(M); return 0;数据结构七#in clude using n amespace std; struct PolyNodeint coef;一次比较：主串abcaabbabcabaacbacba i=5模式串 abcabj=5,匹配失败第二次比较：主串abcaabbabcabaacbacbai=7模式串abcj=3,匹配失败第三次比较：主串abcaabbabcabaacbacbai=7模式串aj=1,匹配失败第四次比较：主串abcaabbab

16、cabaacbacbai=8模式串abcabaaj=1,匹配成功数据结构一#in clude using n amespace std;#defi ne maxle ngth 100 typedef char Eleme nttype;struct STACKint top;Eleme nttype eleme ntsmaxle ngth;en um Boolea nFALSE,TRUE;67801413-3161void MakeNull(STACK &S)20833541-74525362JI数据结构十六0142 0813-3161L41-7335452536数据结构十七#in clude

17、using n amespace std; struct list no delist node *li nk;bool tag;unionchar data;list node *dli nk;eleme nt;typedef list node *listpo in ter;判断广义表是否相同bool Equal(listpo in ter S,listpo in ter T) bool x,y;y=false;if(S=NULL)&(T=NULL)y=true;else if(S!=NULL)&(T!=NULL)if(S-tag=T-tag)if(S-tag=false)if(S-=T-

18、x=true; elsex=false; elsex=Equal(S-,T-; if(x=true) y=Equal(S-link,T-link);return y;listpointer Cal(listpointer L)/if (L=NULL)return NULL;elsereturn L;listpointer Cdr(listpointer L)/if (L = NULL)return NULL;elsereturn L-link;int elements(listpointer L)/if(L=NULL)return 0;else获得表头获得表尾求广义表原子个数if(L-tag=false)return elements(Cdr(L)+1;elsereturn elements(Cdr(L);int main(