数据结构第2章参考答案08

void main() { int n;

char a[MAXSIZE]=\ n=14;

printf(\ printf(\ move1(a,n); printf(\ printf(\}

5． 线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个元

素和后n个元素进行整体互换。即将线性表

（a1, a2, ? , am, b1, b2, ? , bn） 改变为： （b1, b2, ? , bn , a1, a2, ? , am）。

#顺序表方式

#define MAXSIZE 30 #include \#include \typedef int datatype; typedef struct

{int data[MAXSIZE]; int last; } SeqList;

void process(SeqList *L,int m,int n) {int i,k,x;

if(mdata[0];

for(k=1;k<=L->last;k++) L->data[k-1]=L->data[k]; L->data[L->last]=x; } else

for(i=1;idata[L->last];

for(k=L->last;k>=0;k--)

11

L->data[k+1]=L->data[k]; L->data[0]=x; }

return; }

算法复杂度O(m*n) main()

{int i,m,n; SeqList *L;

SeqList a={{0,1,2,3,4,5,6,6,7,8,9,},9}; L=&a;

printf(\

for(i=0;i<=L->last;i++) printf(\ printf(\ scanf(\ process(L,m,n); printf(\

for(i=0;i<=L->last;i++) printf(\ }

数组方式

#define MAXSIZE 30 #include \

void move(char a[],int n,int m) {int i,j,k; char c;

for(i=0;i

{c=a[0]; /*将首元素保存到C,将其他元素向左移动一位，再将赋值给最后的元素，实现一次循环移动一位，共进行M次这样的移位 即可实现*/ for(j=0;j

return; }

算法复杂度O(m*n) void main()

12

{ int n,m;

char a[MAXSIZE]=\ n=14; m=6;

printf(\ printf(\ move(a,n,m); printf(\ printf(\}

6． 已知带头结点的单链表L中的结点是按整数值递增排列的，试写一算法，将值为x 的

结点插入到表L中，使得L仍然有序。并且分析算法的时间复杂度。 #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; /*空表*/ Lnode *s,*r;

int x,i; /*设数据元素的类型为int*/

s=(Lnode *)malloc(sizeof(Lnode)); /*建立头结点*/ s->next=L;L=s;r=s; /*r指向尾部结点*/ for(i=1;i<=n;i++) {x=3*i-1;

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

return L; }

13

void Insert_LinkList( LinkList L, datatype x) /*在有序单链表L中查插入新结点x使其仍有序*/ { Lnode *p=L->next,*s;

while(p->next!=NULL && p->data next; /*查找第一个不小于小的结点*/ s=(Lnode *)malloc(sizeof(Lnode)); /*申请、填装结点*/ s->data=x; s->next=p->next; /*新结点插入在第p个结点的后面*/ p->next=s; if(p->data>x)

{ s->data=p->data; /*交换两各结点的值*/ p->data=x; } return ; }

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

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

return ; }

void main() { int n,x; LinkList L; n=10;

L=Creat_LinkList1(n ); printf_LinkList(L); printf(\ scanf(\

Insert_LinkList(L,x); printf_LinkList(L);

14

}

7． 假设有两个已排序的单链表A和B，编写一个函数将他们合并成一个链表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;/*空表*/ Lnode *s,*r;

int x,y,i; /*设数据元素的类型为int*/ y=n%3+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; }

LinkList merge(LinkList A,LinkList B) /*设A、B均为带头结点的单链表*/ { LinkList C; LNode *p,*q,*s,*r; p=A->next;q=B->next; C=A; /*C表的头结点*/ C->next=NULL; r=C; free(B);

15