1设线性表存放在向量A[arrsize]的前elenum个分量中,且递增有序。试写一算法,将x插入到线性表的适当位置上,以保持线性表的有序性,并且分析算法的时间复杂度。
【提示】直接用题目中所给定的数据结构(顺序存储的思想是用物理上的相邻表示逻辑上的相邻,不一定将向量和表示线性表长度的变量封装成一个结构体),因为是顺序存储,分配的存储空间是固定大小的,所以首先确定是否还有存储空间,若有,则根据原线性表中元素的有序性,来确定插入元素的插入位置,后面的元素为它让出位置,(也可以从高下标端开始一边比较,一边移位)然后插入x ,最后修改表示表长的变量。
int insert(int A[],int *elenum,int x){if(*elenum==arrsize-1)return 0;else{i=*elenum;while(i>=0&&A[i]>x){A[i+1]=A[i];i--;}A[i+1]=x;(*elenum)++;return 1;}
}
2已知一顺序表 A,其元素值非递减有序排列,编写一个算法删除顺序表中多余的值相同的元素。
【提示】对顺序表 A,从第一个元素开始,查找其后与之值相同的所有元素,将它们删除;再对第二个元素做同样处理,依此类推。
void delete(SeqList *A){i=0;while(i<A->last){k=i+1;while(k<=A->last&&A->data[i]==A->data[k]){k++;}n=k-i-1;for(j=k;j<=A->last;j++){A->data[j-n]=A->data[j];}A->last=A->last-n;i++;}
}
3写一个算法,从一个给定的顺序表 A 中删除值在 x~y(x<=y)之间的所有元素,要求以较高的效率来实现。
【提示】对顺序表 A,从前向后依次判断当前元素 A->data[i]是否介于 x 和 y 之间,若是,并不立即删除,而是用 n 记录删除时应前移元素的位移量;若不是,则将 A->data[i]向前移动 n 位。n 用来记录当前已删除元素的个数。
void delete(SeqList *A,int x,int y){i=0;n=0;while(i<=A->last){if(A->data[i]>=x&&A->data<=y){n++;}else{A->data[i-n]=A->data[i];i++;}A->last=A->last-n;}
}
4.线性表中有 n 个元素,每个元素是一个字符,现存于向量 R[n]中,试写一算法,使 R 中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间,元素移动次数最小。
【提示】对线性表进行两次扫描,第一次将所有的字母放在前面,第二次将所有的数字放在字母之后,其它字符之前。
int zimu(char c){if(c>='a'&&c<='z'||c>='A'&&c<='Z'){return 1;}else {return 0;}
}
int number(char c){if(c>='0'&&c<='9'){return 1;}else{return 0;}
}
void process(char R[n]){low=0;high=n-1;while(low<high){while(low<high&&zimu(R[low]))low++;while(low<high&&!zimu(R[high]))high--;if(low<high){k=R[low];R[low]=R[high];R[high]=k;}}low=low+1;high=n-1;while(low<high){while(low<high&&number(R[low]))low++;while(low<high&&!number(R[high]))high--;if(low<high){k=R[low];R[low]=R[high];R[high]=k;}}
}
5线性表用顺序存储,设计一个算法,用尽可能少的辅助存储空间将顺序表中前 m 个元素和后 n 个元素进行整体互换。即将线性表:(a1, a2, … , am, b1, b2, … , bn)改变为:
(b1, b2, … , bn , a1, a2, … , am)。
【提示】比较 m 和 n 的大小,若 m<n,则将表中元素依次前移 m 次;否则,将表中元素依次后移 n 次。
void process(SeqList *L,int m,int n){if(m<=n){for(i=1;i<=m;i++){x=L->data[0];for(k=1;k<=L->last;k++){L->data[k-1]=L->data[k];}L->data[L->last]=x;}else{for(i=1;i<n;i++){x=L->data[L->next];for(k=L->last-1;k>=0;k--){L->data[k+1]=L->data[k];}L->data[0]=x;}}}}
6已知带头结点的单链表 L 中的结点是按整数值递增排列的,试写一算法,将值为 x 的结点插入到表 L 中,使得 L 仍然递增有序,并且分析算法的时间复杂度。
LinkList insert(LinkList L,int x){p=l;while(p->next&&x>p->next->data){p=p->next;}s=(LNode*)malloc(sizeof(LNode));s->data=x;s->next=p->next;p->next=s;return(L);
}
7假设有两个已排序(递增)的单链表 A 和 B,编写算法将它们合并成一个链表 C 而不改变其排序性。
LinkList combine(LinkList A,LinkList B){C=A;//将新生成的链表C初始化为链表A,这样新链表一开始就包含了链表A的头节点。rc=C;//rc是一个指向链表C当前最后一个节点的指针,初始时也指向链表C的头节点。pa=A->next;pb=B->next;free(B);while(pa&&pb){if(pa->data<pb->data){rc->next=pa;rc=pa;pa=pa->next;}else{rc->next=pb;rc=pb;pb=pb->next;}if(pa) rc->next=pa;else rc->next=pb;return(C);}
}