while (p&&q)

{ if (p->datadata) { s=p;p=p->next; } else

{s=q;q=q->next;} /*从原AB表上摘下较小者*/ r->next=s; /*插入到C表的尾部*/ r=s; r->next=NULL; } /*while */ if (p==NULL) p=q;

r->next=p; /* 将剩余的结点链到C表的尾部*/ return(C); }

void printf_LinkList( LinkList L) /*输出单链表L中各结点*/ { Lnode * p=L->next; printf(\ while ( p!=NULL)

{ printf(\ p=p->next; }

return ; }

void main() { int n,m;

LinkList A,B; n=5;m=7;

A=Creat_LinkList1(n ); B=Creat_LinkList1(m ); printf_LinkList(A); printf_LinkList(B);

printf_LinkList(merge( A, B)); }

8． 假设长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点

的指针，编写一个函数删除该结点的前趋结点。 #define MAXSIZE 30 #include \

16

#include \typedef int datatype; typedef struct node { datatype data;

struct node *next; } Lnode,*LinkList;

LinkList Creat_LinkList1(int n ) /*建立无头结点单循环链表*/ { LinkList L=NULL; /*空表*/ Lnode *s,*r;

int x,y,i; /*设数据元素的类型为int*/ y=n%3+1;

s=malloc(sizeof(Lnode)); s->data=1; s->next=L; L=s;r=s;

for(i=1;i

s=malloc(sizeof(Lnode)); /*在尾部插入结点*/ s->data=x; s->next=L; r->next=s; r=s; }

return L; }

void printf_LinkList( LinkList L) /*输出单链表L中各结点*/ { Lnode * p=L; printf(\ do

{ printf(\ p=p->next; }

while ( p!=L); return ; }

void dele_prior(LinkList A, LinkList p)

17

{ LinkList q,r;

q=p; /*指向链表头结点后的数据结点*/

while (q->next->next!=p) /*查找p前趋的前趋结点*/ q=q->next; r=q->next;

q->next=p; free(r); }

void main() { int i,n;

LinkList A,p; n=10;

A=Creat_LinkList1(n ); printf(\

printf_LinkList(A); p=A;

for(i=0;i<5;i++) p=p->next;

printf(\ dele_prior( A,p); printf_LinkList(A); }

9． 已知两个单链表A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和B

的交集C，要求C同样以元素递增的单链表形式存储。 #define MAXSIZE 30 #include \#include \typedef int datatype; typedef struct node { datatype data;

struct node *next; } Lnode,*LinkList;

LinkList Creat_LinkList1(int n ) { LinkList L=NULL;/*空表*/

18

Lnode *s,*r;

int x,y,i; /*设数据元素的类型为int*/ y=n%4+1;

s=malloc(sizeof(Lnode)); /*建立头结点*/ s->next=L; L=s;r=s;

for(i=1;i<=n;i++) {x=y*i-1;

s=malloc(sizeof(Lnode)); /*在尾部插入结点*/ s->data=x; s->next=NULL; r->next=s; r=s; }

return L; }

void printf_LinkList( LinkList L) /*输出单链表L中各结点*/ { Lnode * p=L->next; printf(\ while ( p!=NULL)

{ printf(\ p=p->next; }

return ; }

void merge(LinkList A, LinkList B, LinkList C) { LinkList a,b,c,s;

a=A->next; /*指向链表头结点后的数据结点*/ b=B->next;

c=C; /*指向链表C的头结点*/ while (a!=NULL && b!=NULL)

{if(a->data==b->data) /*将共同元素复制的C链表*/ {s=malloc(sizeof(Lnode)); c->next=s; s->data=a->data; s->next=NULL; c=s;

19

a=a->next;b=b->next; /*将两链表的指针共同向后移动一个位置*/ } else

if(a->datadata) /*将两链表中较小的结点向后移动一个位置*/ a=a->next; else b=b->next; } return; }

void main() { int n,m,x;

LinkList A,B,C; n=14;m=11;

A=Creat_LinkList1(n ); B=Creat_LinkList1(m ); C=Creat_LinkList1(0); printf_LinkList(A); printf_LinkList(B); merge( A, B, C); printf_LinkList(C); } 10． 设有一个双向链表，每个结点中除有prior、data和next域外，还有一个访问频度

freq域，在链表被起用之前，该域其值初始化为零。每当在链表进行一次Locata(L,x)运算后，令值为x的结点中的freq域增1，并调整表中结点的次序，使其按访问频度的递减序列排列，以便使频繁访问的结点总是靠近表头。试写一个算法满足上述要求的Locata(L,x)算法。 #define MAXSIZE 30 #include \#include \typedef int datatype; typedef struct node { datatype data; int freq;

struct node *prior,*next;

20