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

{ printf(\＂表满＂\表空间已满，不能插入*/ for(j=L->last;xdata[j]&&j>0;j--) L->data[j+1]=L->data[j]; /* 结点移动 */ L->data[j+1]=x; /*新元素插入*/ L->last++; /*last仍指向最后元素*/ return (1); /*插入成功，返回*/ }

int dele(SeqList *L) /*这是本题的主要函数*/ {int i,j; /*设置两个下标指针*/ i=j=0;

while(j<=L->last)

if( L->data[i]==L->data[j])j++; /*如果相当，则只移动j指针*/ else

L->data[++i]=L->data[j++]; /*否则，将j指针数据移动到i位置*/ L->last=i; return(i); }

main()

{int i,j,x; SeqList *L;

L=init_SeqList(); for(i=0;i<20;i++) {x=i/2;

Insert_SeqList(L,x); }

printf(\

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

printf(\

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

3． 编写一个函数，从一给定的顺序表A中删除值在x~y(x<=y)之间的所有元素，要求以较

6

高的效率来实现。

提示：可以先将顺序表中所有值在x~y之间的元素置成一个特殊的值，并不立即删除它们，然后从最后向前依次扫描，发现具有特殊值的元素后，移动其后面的元素将其删除掉。

Ⅰ、直接使用数组的写法： #define MAXSIZE 30 #include \

int dele(int a[],int m,int x,int y) {int i,c,k=0;

if(x>y){c=x;x=y;y=c;} for(i=0;i

if(a[i]>=x&&a[i]<=y)k++; /*统计x和y之间已有元素的个数 */

else

a[i-k]=a[i]; /*将后面元素向前移动*/ return(m-k); /*返回剩余元素的个数*/ }

void main()

{ int a[MAXSIZE],i,n,x,y; scanf(\ printf(\ for(i=0;i

{ printf(\ scanf(\ printf(\ }

printf(\ scanf(\ n=dele(a,n,x,y); printf(\ for(i=0;i

printf(\}

Ⅱ。使用线性表结构的程序： #include \ #include \ #define MAXSIZE 100 typedef struct

{int data[MAXSIZE];

7

int last; } SeqList;

SeqList *init_SeqList( ) { SeqList *L;

L=malloc(sizeof(SeqList)); L->last=-1; return L; }

int Insert_SeqList(SeqList *L,int x) {int j; if (L->last==MAXSIZE-1) { printf(\＂表满＂\表空间已满，不能插入*/ for(j=L->last;xdata[j]&&j>0;j--) L->data[j+1]=L->data[j]; /* 结点移动 */ L->data[j+1]=x; /*新元素插入*/ L->last++; /*last仍指向最后元素*/ return (1); /*插入成功，返回*/ }

int dele(SeqList *L,int x,int y) /*这是本题的主要函数*/ {int i,j,c;

if(x>y){c=x;x=y;y=c;} i=j=0;

while(j<=L->last)

if(L->data[j]>=x&&L->data[j]<=y)j++; else

L->data[i++]=L->data[j++]; L->last=i-1; return(i-1); }

main()

{int i,j,x,y; SeqList *L;

L=init_SeqList(); for(i=0;i<20;i++) {x=i/2;

Insert_SeqList(L,x);

8

}

printf(\

for(i=0;i<=L->last;i++) printf(\ printf(\ scanf(\ dele(L,x,y); printf(\

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

4． 线性表中有n个元素，每个元素是一个字符，现存于向量R[n]中，试写一算法，使R

中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素移动次数最小。（研54） #define MAXSIZE 30 #include \

void move1(char a[],int m) /*不保持原来的字母顺序，但算法简单*/ {int i,j,k; char c;

k=0;i=0; j=m-1; /*K是要将字母移动过来的位置*/ while(i

{while((a[i]>=65&&a[i]<=90||a[i]>=97&&a[i]<=122)&&i

while(!(a[j]>=65&&a[j]<=90||a[j]>=97&&a[j]<=122)&&j>i) j--; /*如果不是字母 继续向前找*/ if(i

{c=a[i];a[i]=a[j];a[j]=c;/*前面的非字母与后面的字母交换*/ i++;j--; } } i++; j=m-1; while(i

{while((a[i]>=48&&a[i]<=57)&&i

while(!(a[j]>=48&&a[j]<=57)&&j>i) j--; /*如果不是数字 继续找*/

9

if(i

{c=a[i];a[i]=a[j];a[j]=c; /*前面的非数字与后面的数字交换*/ i++;j--; } } }

void move2(char a[],int m) /*可保持原来的字母顺序，算法复杂*/ {int i,j,k; char c;

k=0;i=0; /*K是要将字母移动过来的位置*/ while(i

{while(!(a[i]>=65&&a[i]<=90||a[i]>=97&&a[i]<=122)&&i=m)break;

if(i>k) /*如果i处是字母,k处不是字母，移动字母到K*/ {c=a[i];

for(j=i;j>k;j--) a[j]=a[j-1]; a[k++]=c; }

else /*如果i和k处都是字母，都向前移动一个位置*/ {i++;k++;} } i=k; while(i

{while(!(a[i]>=48&&a[i]<=57)&&i=m)break;

if(i>k) /*如果i处是数字,k处不是数字字母，移动数字字母到K*/ {c=a[i];

for(j=i;j>k;j--) a[j]=a[j-1]; a[k++]=c; }

else /*如果i和k处都是数字字母，都向前移动一个位置*/ {i++;k++;} } }

10