数据结构习题课-线性表.ppt

文档介绍：数据结构习题课
1、某百货公司仓库中有一批电视机,按其价格从低到高的次序构成了一个单链表存在计算机中,链表的每个结点之处同样价格的若干台。现在有新到 m 台价格为 h 的电视机入库。试编写出仓库电视机链表增加电视机的算法。
struct CellType {
float price;
int num;
struct CellType *next;};
typedef struct CellType * LIST;
LIST create_link() //创建仓库
{ LIST p,q,head;
float x; int y;
head=new CellType; //建立表头结点
head->next=NULL;
printf("输入库中现有电视机的价格和台数,以逗号间隔,输入0,0结束:\n");
scanf("%f,%d",&x,&y);
while(x!=0)
{ q=new CellType;
q->price=x; q->num=y;
q->next=NULL;
p=head;
while((p->next!=NULL)&&(p->next->price<=x))
p=p->next;
q->next=p->next;
p->next=q;
scanf("%f,%d",&x,&y);
}
return(head);
}
void insert( LIST head ) //新的电视到货
{
LIST p,q;
p=head->next;
float x;int y;
printf("新到电视的价格,台数?:");
scanf("%f,%d",&x,&y);
while((p->next!=NULL)&&(p->next->price<=x))
p=p->next;
if(p->price==x)
p->num=p->num+y;
else
{ q=new CellType;
q->price=x; q->num=y;
q->next=p->next;
p->next=q;
}
};
2、假设有一个单循环链表,其结点含有三个域:pre,data和link,其中data为数据域,link为指针域,他指向后继结点,pre为指针域,他的值为空指针。试编写算法,将此表改成双向链表。
struct CellType {
int data;
struct CellType *pre,*link;};
typedef struct CellType * LIST;
LIST create_link() //创建单向循环链表
{ LIST p,q,head;
int x;
printf("输入链表结点值,-999结束:\n");
cin>>x;
if(x==-999) return(NULL);
head=new CellType; //建立表头结点
head->data=x;
head->link=NULL;
head->pre=NULL;
p=head;
scanf("%d",&x);
while(x!=-999)
{ q=new CellType;
q->data=x; q->link=NULL;q->pre=NULL;
q->link=p->link;
p->link=q;
p=q;
cin>>x;
}
p->link=head;
return(p);
}
void double_link(LIST head) //单向链表变成双向链表
{
LIST p,q;
p=q=head->link;
do{
q->link->pre=q;
q=q->link;
}while(q!=p);
}
void output_double( LIST head ) //输出双向链表
{
LIST p;
p=head;
printf("\n双向循环链表如下:\n");
do{
printf("%d,",p->data);
p=p->pre;
}while(p!=head);
};
3、设有一个双向链表,每个结点中除有pre、data和next三个域外,还增设了一个访问频度域freq。在链表被启用后,频度域freq的值均初始化为零,而每当对链表进行一次LOCATE(L,x)的操作后,被访问的节点(即元素值等于x的结点)中的频度域freq的值便增1,同时,调整链表中结点之间的次序,使其按访问频度非递增的次序顺利排列,以便始终保持被频繁访问的节点总是靠近表头结点。试编写符合上述要求的LOCATE 操作的算法。