数据结构课堂练习题ppt课件

1、习题课线性表：1.描画以下概念的区别： 头指针、头结点、首结点。2.顺序表中逻辑上相邻的元素物理位置 相邻， 单链表中逻辑上相邻的元素物理位置 相邻。3.知P为单链表中的非首尾结点，在P结点后插入S结点的语句为： 。s-next = p-next; p-next = s; .类型定义： 顺序表： #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct ElemType *elem; int length; int listsize; SqList; .单链表 typedef struct Lnode ElemType

2、 data; Struct Lnode *next; Lnode, *LinkList;4. 设顺序表va中的数据元素递增有序，试写一算法， 将X插入到顺序表的适当位置上，以坚持该表的有序性。.Status SqInsert(SqList &va, ElemType x) /线性表va的元素依次和数据元素x比较， /找到第一个比它大的元素后，之后一切 /数据后移，X元素放入。 L=va; if (L.length= L.listsize) newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)* sizeof(ElemT

3、ype); if (!newbase) exit (OVERFLOW); L.elem = newbase; L.listsize = L.listsize + LISTINCREMENT; . i=0; while (L.elemix & i=i; j-) L.elemj+1 = L.elemj; L.elemi=x; L.length +; return OK; /SqInsert.5.知指针ha和hb分别指向两个单链表的头结点，并且知两个链表的长度分别为m和n。试写一算法将这两个链表衔接在一同即令其中一个表的首元结点连在另一个表的最后一个结点后，假设指针hc指向衔接后的链表的头结点，并要

4、求算法以尽能够短的时间完成衔接运算。请分析他的算法的时间复杂度。mn.Status LinkListJoin(LinkList ha, LinkLis hb, LinkList &hc) /将ha, hb链表中长的一条链在短的一条后 /面，并放入hc中 if m n hc = hb; p = hb; q = ha-next; else hc = ha; p = ha; q = hb-next; while (!p-next) p=p-next; p-next = q; return ok; 算法时间复杂度分析： 时间：min(m,n) , O(n)阶 .8. 试写一算法，对单链表实现就地逆置

5、Status LinkConvert(LinkList &h) /假设有头结点，h为指向头结点的指针, /只需将头结点后结点依次参与新链， /参与总是放在新链的首元素位置上 p = h-next; q=p-next; while (p) p-next = h-next; h-next = p; p=q; q=q-next; return OK; 12312pq.9. 假设以两个元素递增有序陈列的线性表A和B分别表示两个集合即同一个表中元素各不一样，现要求其并集C，并坚持其元素递增有序，要求运用单链表。 138235qpts.Status assemjoin(LinkList ha, LinkL

6、ist hb, LinkList &hc) /集合以ha为根底，将hb中不同的元素 /参与，并坚持递增有序 hc = ha; p=ha-next; q=hc; t =hb-next; s=t-next; while (p&t) switch case (t-data = = p- data) free (t) ; t=s; s=s-next; q=p; p=p-next; break;. case (t-data p-data) q=p; p=p-next; break; case (t-data data) /插入 t-next = p; q-next = t; q = t; t=s; s=

7、s-next; break; /switch /while if (!p) q-next = t; return OK; /assemjoin hb集合和ha集合总比较次数 n次，O(n) .栈和队列类型定义： 顺序栈 #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack. 顺序循环队列：#define MAXQSIZE 100; typedef struct QElemType *base; i

8、nt front; int rear; SqQueue; 1.试写一个算法，识别依次读入的一个以 为终了符的字符序列能否形如序列1& 序列2方式的字符序列。其中序列1和序列2中都不含字符&, 且序列2是序列1的 逆序列。如a+b&b+a .int symmetry() /运用栈，对读入的字符在&之前的都 /压栈，之后弹栈并和读入数比较，直 /到栈空并且读入数为是对称，否那么 /为不对称。 InitStack(s); scanf(ch); while (ch “&) push(s, ch); scanf(ch); scanf(ch); while (ch “ &!empey(s) pop(s,x

9、); if (ch = = x) scanf(ch); else return 0; /while. if (ch = = “ & empty(s) return 1; else return 0; /symmetry 2. 在顺序存储构造上实现输出受限的双端循环队列的入列和出列只允许队头出列算法。设每个元素表示一个待处置的作业，元素值表示作业的预算时间。入队列采取简化的短作业优先原那么，假设一个新提交的作业的估计执行时间小于队头和队尾作业的平均时间，那么插入在队头，否那么插入在队尾。.Status EnQueue(SqQueue &Q, QElemType e) /插入受限，小于平均时间插入

10、队头，否那么/插入队尾if (Q.rear+1) %MAXQSIZE = = Q.front) return ERROR; /队列满 t = Q.baseQ.front+Q.base(Q.rear-1+ MAXQSIZE) %MAXQSIZE/2 if (e data) return ERROR; if (p-rchild) push(p-rchild); if (p-lchild) push(p-lchild); /while return OK; /PreOrderTraverse 思索一下后序？ .9. 编写递归算法，计算二叉树中叶子结点的数目。Status PreOrderTraverse(BiTree T, int s) /s为叶子树目，初值为0 if (T) if (!T-lchild) & (!T-rchild) s+; PreOrderTraverse(T-lchild, s); PreOrderTraverse(T-rchild, s); /if return OK; /PreOrderTraverse .10. 编写按层次顺序同一层自左至右遍历二叉树的算法Status LevelTraverse(BiTree T, status (*visit)(TElemType e) InitQueue(Q); if (T) EnQ