第二次课013H
1、问题描述
请实现一个函数，将一个字符串中的每个空格替换成“ ”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We Are Happy。 2、思路
从后往前开始替换，首先遍历一遍字符串，统计出空格的个数，并由此能够计算出替换之后的字符串的长度。
每替换一个空格，长度增加2，因此替换以后字符串的长度等于原来的长度加上2乘以空格数目。以\为例，\这个字符串的长度为14（包括结尾符号\），里面有两个空格，因此替换之后字符串的长度是18。 接着再次从后往前遍历字符串，同时设置两个指针P1和P2，P1指向原始字符串末尾，P2指向替换之后的字符串末尾。我们向前移动P1，逐个把它指向的字符复制到P2指向的位置，直到碰到第一个空格为止。然后把P1向前移动一格，在P2之前插入字符串“ ”，同时P2向前移动3格。重复此过程，直到所有的空格都已替换完。这样只需要扫描一遍，时间复杂度为O(n)。 移动示意图如下：
2、源代码
#include
void replaceSpace(char ch[]) {
int i = 0;
int conlength= 0; int spaceNum = 0; int newLength= 0; char *p1,*p2; while(ch[i] !='\\0') {
if(ch[i]==' ')
spaceNum++; i++; }
newLength = i + 2*spaceNum; p1 = &ch[i];
p2 = &ch[newLength]; while (p1 != p2) {
if (*p1 != ' ') {
*p2 = *p1; } else {
p2-=2;
strncpy(p2,\ } p1--; p2--; } }
int main() {
char ch[1000001]={'\\0'}; while(gets(ch)) {
replaceSpace(ch); puts(ch); } }
3、结果
第二次课013H
1、问题描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
2、源代码
#include
typedef struct node* List; struct node {
int data;
struct node *next; };
List Read() {
int x;
List q, r, head; scanf(\
head = (List)malloc(sizeof(struct node)); r = head; while(x != -1) {
q = (List)malloc(sizeof(struct node)); q->data = x; r->next = q; r = q;
scanf(\ }
r->next = NULL; return head; }
List LinkList(List La, List Lb) {
List Lc, pa, pb, pc, ptr; pa = La->next; pb = Lb->next; Lc = La; pc = La;
while(pa != NULL && pb != NULL) {
if(pa->data < pb->data) {
pc->next = pa; pc = pa;
pa = pa->next; }
else if(pa->data > pb->data) {
pc->next = pb; pc = pb;
pb = pb->next; } else {
pc->next = pa; pc = pa;
pa = pa->next; ptr = pb;
pb = pb->next; free(ptr); } }
if(pa != NULL)
pc->next = pa; else
pc->next = pb; return (Lc); }
void Print(List s) {
int k; k = 0;
s = s->next; if(s == NULL) {
printf(\ return ; }
while(s != NULL) {
if(k != 0)
printf(\
printf(\->data); s = s->next; k++; }
printf(\ return ; }
int main() {
int x;
List s1, s2, s3; s1 = Read(); s2 = Read();
s3 = LinkList(s1, s2); Print(s3); return 0; } 3、结果
第二次课013H和016H
