数据结构c语言版（题目）

分类： 编程思想和算法2012-09-15 22:24 1759人阅读 评论(0) 收藏 举报

如果TCPhashlistJuli采用线性表的顺序存储结构，则可以随机存取表中任一终端，但插入和删除终端时，需要移动大量元素，巧妙地终端离线不进行删除操作。

数组，存储的元素应该是线性表顺序存储结构的数据结构。

线性表题目类型：线性表在顺序结构上各种操作的实现；线性链表的各种操作；两个或多个线性表的各种操作；循环链表和双向链表；稀疏多项式及其运算在线性表的两种存储结构上的实现。

线性表

线性表在顺序结构上各种操作的实现

题目1：（线性表顺序存储结构上的操作_Delete）从顺序存储结构的线性表a中删除第i个元素起的k个元素。(《数据结构题集 C语言版》P16)

题目2：（线性表顺序存储结构上的操作_Insert）设顺序表va中的数据元素递增有序。试写一算法，将x插入到循序表的适当位置上，以保持该表的有序性。(《数据结构题集 C语言版》P17) 题目3：（线性表顺序存储结构上的操作_逆置）

试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表逆置。(《数据结

构题集 C语言版》2.21) 线性表

线性链表的各种操作

题目1：（Insert）试写一算法，在无头结点的动态单链表上实现线性表的Insert(L,i,b),并和在带头结点的动态单链表上实现同样操作的算法进行比较。(《数据结构题集 C语音版》P17)

题目2：（Delete）同上题要求，实现线性表操作Delete(L,i). 题目3：已知线性表中的元素以值递增有序排序，并以单链表作为存储结构。试写一高效算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）同时释放被删除结点空间，并分析你的算法的事件复杂度（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。(《数据结构题集 C语言版》P17)

题目4：同上题条件，试写一高效算法，删除表中所有值相同的多余元素（使得操作后的线性表所有元素的值均不相同），同是释放被删结点空间，并分析你算法的时间复杂度。(《数据结构题集 C语音版》P18)

对比题目2至4可知：线性表链表的删除操作的题目常有：带头结点和不带头结点的单链表的删除操作对比；删除所有值大于mink且小于maxk的元素；删除相同的多余元素同事释放结点空间。

题目5：（逆置）试写一算法，对单链表实现就地逆置。(《数据结构题集 C语言版》2.22)

两个或多个线性表的各种操作

题目1：（连接） 已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。(《数据结构题集 C语言版》2.15)

题目2：（删除+插入）知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第i个元素之前。试问此算法是否正确？若有错，请改正之。(《数据结构题集 C语言版》2.16)

Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len) {

if(i<0||j<0||len<0) return INFEASIBLE; p=la; k=1;

while(knext; k++; } q=p;

while(k<=len){ q=q->next; k++; } s=lb; k=1;

while(knext; k++; } s->next=p; q->next=s->next; return OK; }

题目3：（归并）假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。(《数据结构题集 C语言版》2.24)

题目4：（集合求交，集合求并，集合求余）

2.25 假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各不相同），现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素有依值递增有序排列。试对顺序表编写求C的算法。 2.26 要求同2.25题。试对单链表编写求C的算法。

2.27 对2.25题的条件作以下两点修改，对顺序表重新编写求得表C的算法。

(1) 假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；

(2) 利用A表空间存放表C。