西北大学《数据结构》典型例题（1-5章）(2)

2.19

status del-l(LinkList &la, int mink, int maxk){

//la为带头结点的单链表的头指针，单链表中的结点以值递增有序排列 //本算法删除表中所有值大于mink且小于maxk的元素，mink=maxk) return ERROR p=la;

while (p->next<>NULL && p->next->data<=mink) p=p->next; q=p;

while (q->next<>NULL && q->next->datanext ; q=q->next; p1=p->next;

while (p1<>q) {q1=p1; p1=p1->next; free(q1);} p->next=q; }//del-l 2.21

LinkList priou(LinkList la, LinkList q1){

//返回指向单链表la中结点的指针p1，p1->next=q1 p1=la;

while (p1->next!=q1) p1=p1->next; return p1; }//priou

void Reverse-List-l(LinkList &la) { //就地逆置单链表la（算法1） if (!la->next) return;

p=la->next; q=priou(la, NULL);

while (p!=q) {

p->data〈-〉q->data; if (p=q) return; q=priou(la, q); }

}//Reverse-List-l

void Reverse-List-l(LinkList &la) { //就地逆置单链表la（算法2） p=priou(la, NULL); last=p; pre=priou(la,p); while (pre!=la) { p->next=pre; p=pre; pre=priou(la,p); }

p->next=NULL; la->next=last; }//Reverse-List-l

void Reverse-List-l(LinkList &la) { //就地逆置单链表la（算法3） if (!la->next) return; pre=la->next; if (!pre->next) return;

p=pre->next; pre->next=NULL; next=p->next;

while (p) { p->next=pre; pre=p; p=next;

if (p) next=p->next; }

la->next=pre; return; }//Reverse-List-l

void Reverse-List-l(LinkList &la) { //就地逆置单链表la（算法4） p=la->next;

if (!p || !p->next) return; pn=p->next; p->next=NULL; while (pn) {

p=pn; pn=pn->next;

p->next=la->next; la->next=p; } return; }//Reverse-List-l 2.24

void MergeList(LinkList &a, LinkList &b, LinkList &c) { //已知单链表a和b的元素按值递增有序排列

//归并a和b得到新的单链表c，c的元素按值递减有序 c=a; p=a->next; q=b->next; c->next=NULL;

while (p && q) if (p->datadata) {

pn=p->next; p->next=c->next; c->next=p; p=pn; } else {

qn=q->next; q->next=c->next; c->next=q; q=qn; }

while (p) {pn=p->next; p->next=c->next; c->next=p; p=pn;} while (q) {qn=q->next; q->next=c->next; c->next=q; q=qn;} free(b); }//MergeList 2.33

void CutApart-LinkList(LinkList &l, LinkList la, LinkList lb, LinkList lc){ //单链表l中的元素含有三类字符：字母、数字和其它字符

//本算法将l分割为la、lb和lc三个循环链表，它们分别只含字母、数字和其它字符 la=(LinkList)malloc(sizeof(LNode)); la->next=la; lb=(LinkList)malloc(sizeof(LNode)); lb->next=lb; lc=(LinkList)malloc(sizeof(LNode)); lc->next=lc; pn=l->next; while (pn){

p=pn; pn=pn->next; switch {

case ('a'<=p->data && p->data<='z')

||('A'<=p->data && p->data<='Z') : p->next=la->next; la->next=p; break;

case ('0'<=p->data && p->data<='9') : p->next=lb->next; lb->next=p; break; default : p->next=lc->next; lc->next=p; }//switch }//while free(l);

}//CutApart-LinkList 2.39

typedef struct { float coef; int expn; }*Poly, ElemType;

float Polynomial(Poly &p, int m, float x0){

//多项式p的顺序存储结构中依次存放有c1,e1,c2,e2,...,cm,em //x0为给定值，本算法计算pn(x0)的值 x=x0^p[0].expn; pn=p[0].coef*x; for (i=1; i<=m; ++i){

x=x*x0^(p[i].expn-p[i-1].expn); pn=pn+p[i].coef*x; } retrun pn; }//Polynomial

(以下内容来自http://bbs.kaoyan.com)

第二章 线性表