数据结构习题课 信息学院 赵明 2005年秋.

Presentation on theme: "数据结构习题课 信息学院 赵明 2005年秋."— Presentation transcript:

1 数据结构习题课 信息学院 赵明 2005年秋

2 单链表应用(1) 已知单链表H，写一算法将其倒置。 H 29 76 18 45 25 ^ H 25 45 18 76 29 ^

3 单链表应用(1) 算法思路：依次取原链表中的每个节点，将其作为第一个节点插入到新链表中去。
void Reverse(Linklist L) { p=H->next; H->next=NULL; while(p) { q=p; p=p->next; q->next=H->next; H->next=q; }

4 单链表应用(2) 已知单链表L，写一算法，删除其重复节点。 H 10 15 18 15 10 ^ H 10 15 18 ^

5 单链表应用(2) 算法思路：用指针p指向第一个节点，从它的后继开始直到结束，找出与其值相同的节点并删除之；p往后走，直至结束。

6 单链表应用(2) void Pur_Linklist(Linklist H) { p=H->next;
if(p==NULL) return; while(p->next) { q=p; while(q->next) { if(q->next->data==p->data) { r=q->next; q->next=r->next; free(r); } //end of if else q=q->next; } //end of while(q->next) p=p->next; } //end of while(p->next) }

7 单链表应用(3) 设有两个单链表A、B，其中元素递增有序，编写算法，将A、B归并成一个按元素值递减（允许有相同值）有序的链表C，要求用A、B中的节点形成，不能重新申请节点。

8 单链表应用(3) 算法思路：利用A、B两表有序的特点，依次进行比较，将当前值较小者摘下，插入到C表的头部。

9 单链表应用(3) LinkList Merge(Linklist A, Linklist B) {
p=A->next; q=B->next; C=A; C->next=NULL; free(B); while(p&&q) { if(p->data<q->data) { s=p; p=p->next; } //end of if else { s=q; q=q->next; } //end of else s->next=C->next; C->next=s; } //end of while(p&&q) if(p==NULL) p=q; while(p) { }

10 顺序表应用(1) 有顺序表A和B，其元素升序排列，写一算法将它们合并成一个顺序表C，要求C的元素也是升序排列。

11 顺序表应用(1) void Merge(SqList A, SqList B, SqList &C) { i=0; j=0; k=0;
while(i<=A.length&&j<=B.length) if(A.data[i]<B.data[j]) C.data[k++]=A.data[i++]; else C.data[k++]=B.data[i++]; while(i<A.length) C.data[k++]=A.data[i+1]; while(j<B.length) C.data[k++]=B.data[j+1]; }

12 算法阅读(1) void algo(Stack *S) { int i=0; Queue Q; Stack T;
设栈S=(1,2,3,4,5,6,7),其中7为栈顶元素。请写出调用algo(&s)后栈S的状态。 void algo(Stack *S) {      int i=0;    Queue Q; Stack T;      InitQueue(&Q); InitStack(&T);      while (!StackEmpty(S)) {        if((i=!i)!=0) Push(&T,Pop(&S));        else EnQueue(&Q,Pop(&S));       }       while(!QueueEmpty(Q))         Push(&S,DeQueue(&Q));       while(!StackEmpty(T))         Push(&S,Pop(&T))； }

13 算法阅读(2) 已知串的存储结构为动态存储分配的顺序串 写出执行函数Strc(s, r)的结果，其中s=‘aba’，r=‘abababa’

14 算法阅读(2) int strc(Hstring *sub, Hstring *str) { int i=0, j, k, count=0;
while(i<str->length-sub->length+1) { j=i; k=0; while(k<sub->length&&str->ch[j]==sub->ch[k]) { j++; k++; } if(k==sub->length) { count++; i=j-sub->lengh+1; else i++; return count;

15 简答 设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3,s4, s6, s5, s1，则顺序栈的容量至少应为多少？

16 算法设计 有两个栈S1和S2共享存储空间C[1..m0]，其中一个栈底设在c[1]处，另一个栈底设在c[m0]处。分别编写S1和S2的进栈、出栈和设置栈空的函数。

17 void push(int i, int x) { if(top1==top2-1) return OVERFLOW; else if(i==1) { top1++; c[top1]=x; } else { top2--; c[top2]=x; void pop(i) { if(i=1) if(top1==0) return ERROR; else top1--; if(top1==m0+1) top2++; }

18

19 pop pop pop

20

21

22 void DisplayList(LinkList H) {
LinkList p; p = H; while(p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); void HandleList(LinkList &H){ LinkList p, q, r; if(p == NULL) return; while(p->next) { q = p; while(q->next) { if(q->next->data == p->data) { r = q->next; q->next = r->next; free(r); else q = q->next; #include "stdio.h" #include "malloc.h" #define ElemType int typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; LinkList InitList() { LinkList H, p; int iData; H = NULL; scanf("%d", &iData); while(iData != -1) { p = (LinkList) malloc(sizeof(LNode)); p->data = iData; p->next = H; H = p; } return H;

23 void main() { LinkList Head; printf("Input data: "); Head = InitList(); printf("List before handled: "); DisplayList(Head); HandleList(Head); printf("List after handled: "); }

24 二叉树 以二叉链表为存储结构，分别写出求二叉树结点总数及叶子总数的算法。 以二叉链表为存储结构，写出求二叉树高度的算法。

25 结点总数 int CountNode(BiTree *root) { int numL, numR;
if(root==NULL) return 0; else if(root->lchild==NULL&&root->rchild==NULL) return 1; else { numL=CountNode(root->lchild); numR=CountNode(root->rchild); return numL+numR+1; }

26 叶子总数 int CountLeafs(BiTree *root) { int numL, numR;
if(root==NULL) return 0; else if(root->lchild==NULL&&root->rchild==NULL) return 1; else { numL=CountNode(root->lchild); numR=CountNode(root->rchild); return numL+numR; }

27 高度 int Depth(BiTree *root) { int depL, depR; if(root==NULL) return 0;
else { depL=Depth(root->lchild); depR=Depth (root->rchild); if(depL>depR) return depL+1; else return depR+1; }

28 三叉链表 假设二叉树T采用三叉链表存储，其结点的lchild和rchild指针域分别指向其左、右孩子结点，而parent域为空。请编写一个递归算法，将该存储结构中各结点的parent域的值修改成指向双亲结点的指针。

29 void FillParent(BiTree *root) {
if (root==NULL) return; if(root->lchild!=NULL){ root->lchild->parent=root; FillParent(root->lchild); } if(root->rchild!=NULL){ root->rchild->parent=root; FillParent(root->rchild);

30