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

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

单链表应用(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; }

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

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

单链表应用(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) }

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

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

单链表应用(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) { }

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

顺序表应用(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]; }

算法阅读(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))； }

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

算法阅读(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;

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

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

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++; }

pop pop pop

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;

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

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

结点总数 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; }

叶子总数 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; }

高度 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; }

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

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);