《数据结构与算法线性表练习题》由会员分享，可在线阅读，更多相关《数据结构与算法线性表练习题（35页珍藏版）》请在金锄头文库上搜索。
1、三、写一个算法合并两个已排序的线性表。用两种方法：数组表示的线性表顺序表和指针表示的线性表链表要求：1、定义线性表节点的结构，并定义节点的型和位置的型。 2、定义线性表的根本操作 3、在1，2的根底上，完成此题。 4、在main函数中进行测试：先构建两个有序的线性表，然后合并这两个线性表。四、一个单向链表，试给出复制该链表的算法。要求：1、定义线性表的节点的结构以及节点的型和位置的型。 2、定义线性表的根本操作 3、在1，2的根底上，完成此题。 4、在main函数中进行测试：先构建一个线性表，并定义一个空线性表，然后进行复制。五、写出从一个带表头的单链表中删除其值等于给定值x的结点的算法函数：
2、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、定义静态链表
3、的结点的结构以及结点的型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、
4、在1、2的根底上完成此题。4、在main函数中进行测试：先构建一个存储池，然后在该存储池中创立两个静态表，最后将这两个静态表合并。七、利用指针表示的线性表(链表)表示一个多项式，并实现两个多项式的相加和相乘运算。假设多项式形式为：其中，系数ai0，指数ei满足emem-1e2e1=0。要求：1、定义多项式每一项的结构。2、定义两个多项式的相加和相乘运算函数。3、在main函数中，构建两个多项式，并测试相加和相乘运算。八、试编写一个整数进制转换的通用函数convert(int num, STACK S, int n)，要求将整数m转换为n进制数，n进制数的各位依次存放在栈S中。并在主函数中进行测
5、试。要求：1、定义栈以及栈的型。2、定义栈的各种操作。 3、实现函数convert。 4、在main函数中，通过调用函数convert将num的n进制数存放到一个栈中，并通过出栈的方法输出该n进制数九、设有一个循环队列Queue，只有头指针front，不设尾指针，另设一个含有元素个数的计数器count，试写出相应的判断队列空、判断队列满、出队算法和入队算法。要求：1、定义相应的循环队列的型只有头指针，没有尾指针，但有一个元素个数的计数器；2、定义该队列的四个算法：判断队列空、判断队列满、出队算法和入队算法；3、在main函数验证算法的正确性。十、设主串T=“abcaabbabcabaacbac
6、ba“，模式为p=“abcabaa。 1、计算模式p的nextval函数值2、不写算法，只画出利用KMP算法进行模式匹配时，每一趟的匹配过程。要求：1、写出模式p的nextval值；2、画出KMP算法的每一趟匹配过程可参照教材P61从第8行开始的内容；3、不需要编写程序。十一、假设表达式中允许包含三种括号：圆括号、方括号和大括号。设计一个算法采用顺序栈用数组表示的栈判断表达式中的括号是否正确配对。要求： 1、定义栈以及栈的型，栈中所存放元素的类型为字符型，定义枚举类型Boolean，其中两个元素分别为TRUE和FALSE。2、定义栈的各种操作。3、定义函数Boolean check(char
7、*s); 判断s中的括号是否正确配对，如果正确配对，返回TRUE，否那么返回FALSE。4、在主函数中验证所编写函数的正确性。十二、设有一个带头结点的双向链表h，设计一个算法用于查找第一个元素之为x的结点，并将其与其前驱结点进行交换。要求： 1、定义带头结点的双向链表的型DLIST。 2、定义双向链表DLIST的根本操作。 3、定义函数int swap(elementtype x, DLIST &h)，查找第一个元素之为x的结点，如果在链表中存在元素值为x的结点，并其与其前驱结点进行交换，并返回1，否那么返回0。 4、在主函数中测试所编写函数的正确性。十三、试编写一个求三元组顺序表示的稀疏矩阵
8、对角线元素之和的算法十四、当具有相同行值和列值的稀疏矩阵A和B均以三元组顺序表方式存储时，试写出矩阵相加的算法，其结果存放在以行逻辑链接顺序表方式存储的矩阵C中。十五、设有一个稀疏矩阵：1、写出三元组顺序表存储表示2、写出十字链表存储的顺序表示十六、画出广义表LS=( ), (e), (a, (b, c, d)的头尾链表存储结构(类似于教材P70图2-27.9)。要求：按照教材中的事例画出相应的图形，不需要编程。t其中第一个节点如下：十七、试编写求广义表中原子元素个数的算法。要求：1、定义广义表的节点的型；2、定义广义表的根本操作；3、定义此题要求的函数int elements(listpoi
9、nter 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文件中，文件名格式为“学号+姓名三数组表示#includeusing namespace std;#defin
10、e 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)coutlist is fullL.last+1)|(p1)coutposition does not exit=p;q-)L.eleme
11、ntsq+1=L.elementsq;L.last=L.last+1;L.elementsp=x; void Delete(position p,LIST &L)position q;if(pL.last)|(p1)coutposition does not existendl;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
12、;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;p1End(L1);p1+)L.elementsp=L1.elementsp1;p+; p-;for(p2=0;p2End(L2);p2+)L.elementsp=L2.elementsp2;p+; p-;void read(LIST &L)coutendl;cout请输入线性表长度L.last;for(int
13、 i=0;iL.elementsi; void write(LIST &L) for(int i=0;iL.last;i+)coutL.elementsit;coutendl; int main()LIST L,L1,L2;read(L1);write(L1);read(L2);write(L2);merge(L,L1,L2);write(L); 数据结构三指针#includeusing 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
