数据结构习题1

p->next=s; } }

5、顺序表：

算法思想：从0开始扫描线性表，用k记录下元素值在a与b之间的元素个数，对于不满足该条件的元素，前移k个位置，最后修改线性表的长度。 void del（elemtype list[]，int *n，elemtype a，elemtype b） {

int i=0，k=0； while（i

if(list[i]>=a&&list[i]<=b) k++; else

list[i-k]=list[i]; i++; }

*n=*n-k; /* 修改线性表的长度*/ } 循环链表:

void del(NODE *head,elemtype a,elemtype b) {

NODE *p,*q;

p= head;q=p->link; /* 假设循环链表带有头结点 */ while(q!=head && q->datalink; }

while(q!=head && q->data

{ r=q; q=q->link; free(r); } if(p!=q) p->link=q; } 6、

#define MAXSIZE 100

int listA[MAXSIZE],listB[MAXSIZE]; int n,m;

int compare(int a[],int b[]) { int i=0;

while(a[i]==b[i]&&i

if(n==m&&i==n) return(0); if(nm&&i==m) return(1); if(i

if(a[i]b[i]) return(1); } 7、

void del(DUNODE **head,int i) {

DUNODE *p;

if(i==0) {

*head=*head->next; *head->prior=NULL; return(0); } Else

{for(j=0;jnext;

if(p==NULL||j>i) return(1); p->prior->next=p->next; p->next->prior=p->proir; free(p); return(0); } 8. 顺序存储:

void convert(elemtype list[],int l,int h) /* 将数组中第l个到第h个元素逆置*/ { int i;

elemtype temp;

for(i=h;i<=(l+h)/2;i++) {

temp=list[i]; list[i]=list[l+h-i]; list[l+h-i]=temp; } }

void exchange(elemtype list[],int n,int m); {

convert(list,0,n+m-1); convert(list,0,m-1); convert(list,m,n+m-1); }

该算法的时间复杂度为O(n+m),空间复杂度为O(1) 链接存储:(不带头结点的单链表) typedef struct node {

elemtype data; struct node *link; }NODE;

void convert(NODE **head,int n,int m) {

NODE *p,*q,*r; int i; p=*head; q=*head;

for(i=0;i

q=q->link; /*q指向an-1结点 */ r=q->link; q->link=NULL; while(r->link!=NULL)

r=r->link; /*r指向最后一个bm-1结点 */ *head=q; r->link=p; }

该算法的时间复杂度为O(n+m),但比顺序存储节省时间(不需要移动元素,只需改变指针),空间复杂度为O(1)