数据结构习题1

别采用数组和链表两种方式存储,编写算法将两部分元素换位成

(b0,b1,...,bm-1,a0,a1,...,an-1),分析两种存储方式下算法的时间和空间复杂度。

9.用循环链表作线性表(a0,a1,...,an-1)和（b0,b1,...,bm-1）的存储结构,头指针分别为ah和bh，设计C函数，把两个线性表合并成形如

（a0,b0,a1,b1,?）的线性表，要求不开辟新的动态空间,利用原来循环链表的结点完成合并操作,结构仍为循环链表,头指针为head,并分析算法的时间复杂度。

10.试写出将一个线性表分解为两个带有头结点的循环链表，并将两个循环链表的长度放在各自的头结点的数据域中的C函数。其中,线性表中序号为偶数的元素分解到第一个循环链表中,序号为奇数的元素分解到第二个循环链表中。

11.试写出把线性链表改为循环链表的C函数。

12.己知非空线性链表中x结点的直接前驱结点为y,试写出删除x结点的C函数。 参考答案： 一、选择题

1. B 2.C 3. D 4. B 5. A 6.A 7、C 二、判断题:

参考答案：1、×2、√3、×4、×5、√ 三、填空题

1、s->next=p->next; p->next=s; 2、一定；不一定 3、n/2 4、q->prior=p; 5、(1)6) 3) (2) 2) 9）1) 7) 四、算法设计题

1、

#include \#include \typedef struct node {int data; struct node *link; }NODE;

int aver(NODE *head)

{int i=0,sum=0,ave; NODE *p; p=head; while(p!=NULL) {p=p->link;++i; sum=sum+p->data;} ave=sum/i; return (ave);} 2、

#include \#include \typedef struct node {

int data; /* 假设数据域为整型 */ struct node *link; }NODE;

void del_link(NODE *head,int x) /* 删除数据域为x的结点*/ {

NODE *p,*q,*s; p=head; q=head->link; while(q!=head)

{if(q->data==x) {p->link=q->link; s=q; q=q->link; free(s);} else { p=q; q=q->link; } } } 3、

void del(NODE *head,float price,int num) {

NODE *p,*q,*s; p=head;q=head->next;

while(q->pricenext; }

if(q->price==price) q->num=q->num-num; else

printf(\无此产品\if(q->num==0) {

p->next=q->next;

free(q); } } 4、

#include \#include \typedef struct node {

float price; int num;

struct node *next; }NODE;

void ins(NODE *head,float price,int num) {

NODE *p,*q,*s; p=head;q=head->next;

while(q->pricenext; }

if(q->price==price) q->num=q->num+num; else {

s=(NODE *)malloc(sizeof(NODE)); s->price=price; s->num=num; s->next=p->next;