数据结构教程试题ppt课件.ppt

1 已知一个线性表的元素按元素非递减有序排列 编写一个过程删除线性表中多余的值相同的元素 2 有两个顺序存贮的线性表A 有m个元素 和B 有n个元素 其元素均以从小到大的升序排列 编写一个过程将它们合并成一个线性表C 要求C的元素也是以从小到大的升序排列 1 voiddel list n intlist n inti j i 0 while i n 1 if a i a i 1 i i 1 else for j i 1 j n j a j a j 1 n n 1 1 2 voidlink A B C m n inta B C m n inti k l j i 0 k 0 j 0 while i m 2 3 else C k B j j j 1 k k 1 if j n 1 for l i i m 1 for l j l n l C k B l k k 1 4 3 编写一个倒置顺序存贮的线性表的C函数 要求尽量用最少的附加存贮空间来完成 intlist intn i t for i 0 i n 2 i t list i list i list n 1 list n 1 t n print 5 4 假设有两个栈共享一个数组stack n 如下图 试编写对任一栈作进栈和出栈运算的C函数 push x i 和pop i i 1 2 i 1表示左边的栈i 2表示右边的栈要求在整个数组元素都被占用时才产生溢出 栈1底 栈2底 栈1顶 栈2顶 6 inttop1 0 top2 MAXN 1 charx inti if i 1 if top1 top2 return 1 stack top1 x return 0 if i 2 if top2 top1 return 1 stack top2 x return 0 7 if i 1 if top1 MAXN 1 return 1 p y stack top2 return 0 8 Top1 1 top2 maxnintpush x i charx inti if top1 top2 1 reutrn 0 elseif i 1 stack top1 x elsestack top2 x return 1 9 intpop pop i char pop inti if i 1 if top1 1 return 0 pop stack top1 return 1 else if top2 n return 0 pop stack top2 return 1 10 5 在一个最多可存放n个结点的顺序存贮的队列中 如果头指针指向队首结点 让尾指针指向下一个进队的存放位置 如下图 试分别编写实现进队和出队的C函数 ABC head tail 11 if head tail return 1 p y q head return 0 if tail MAXN return 1 q tail x return 0 12 6 设有一个环形队列 该队列只有一个队列头指针head 不设队列尾指针 而改置计数器count用以记录队列中结点的个数 试编写实现队列的五个运算 A 设置队列的初始空态B 判定队列是否为空C 取队列头结点的值给变量xD 将x元素入队E 删除队列头结点 13 head 0 count 0 intempty if count 0 reutrn 0 return 1 intgethead x charx if count 0 return 1 x q head 1 MAXN return 0 14 intenqueue x charx if count MAXN return 1 count q head count MAXN x return 0 15 intdequeue p y char p y if count 0 return 1 head head 1 MAXN p y q head count return 0 16 7 利用两个栈S1 S2模拟一个队列时 如何用栈的运算来实现该队列的运算 enqueue 插入一个元素 dequeue 删除一个元素 queue empty 判定队列为空 17 intenqueue x charx if top1 MAXN return 0 push s1 x return 1 18 intdequeue p y char p y inttop2 0 while sempty s1 push s2 pop s1 p y pop s2 while sempty s2 push s1 pop s2 19 作业 1 试编写一个求已知单链表的数据域的平均值的函数2 已知带有头结点的环形链表中头指针为head 试写出删除并释放数据域值为x的所有结点的函数3 线性表中的元素值按递增有序排列 针对顺序表和环形链表两种不同的存储方式 分别编写函数删除线性表中值介于a与b a b 之的元素 20 intaver node head inti 0 sum 0 ave node p p head while p null p p link i sum sum p data ave sum i return ave 21 voiddel link node head