17 软专

数据结构

1、带头结点的双链表l，每个节点有4个数据成员，前驱节点llink，后继节点rlink，数据成员data，访问频度freq，且已知双向链表L中节点一直按访问频度递减的顺序排列且频繁访问的节点一直靠近表头，初始状态l中的所有节点freq的节点都为0，对双链表的locate操作，每操作一次，将数据值x的节点访问频度+1，设计一个算法，对双链表l的locate操作，要求操作后L中的节点仍然按照频度的递减顺序排列

思路：

• 先找到结点值为x的节点，频度加1，然后断链

• 然后找到需要插入的节点，分情况讨论

  • 插在最后一个，只需接三条链
  • 不是插在最后一个，需要接四条链

代码：

typedef struct dnode{
	int data;
	int freq;
	struct dnode *llink, *rlink;
}*dlist; 

void locate(dlist head, int x){
	dlist p = head->rlink,q;
	while(p != NULL && p->data != x) p = p->rlink;			//找到节点值为x的节点 												//访问频度加1
	if(p!=NULL){											//找到节点 
		p->freq++;											//频度加1 
		if(p->llink == head) return;						//第一个节点，不用调整 
		q = p;												//保存需要操作的节点
		
		p->llink->rlink = p->rlink;							//断开p左右节点的链并接上 
		if(p->rlink!=NULL) 									//右链得保证存在才能接 
			p->rlink->llink = p->llink; 
			
		p = q->llink;										//从q的前一个结点找到q的freq大的节点 
		while(p != head && p->freq < q->freq) p = p->llink;	//找到需要插入的节点   
		if(p->rlink==NULL){									//q插到p节点前 ,注意这里的插法
			q->llink = p;
			q->rlink = p->rlink;			
			p->rlink = q;
		}
		else{												//不是插到最后一个节点 
			p->rlink->llink = q;
			q->llink = p;			
			q->rlink = p->rlink;
			p->rlink = q;
		}
	}		
 	p = head->rlink;
 	while(p){
 		printf("%d %d\n",p->data,p->freq);
 		p = p->rlink;
	 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

程序设计

第一题

1、设计字符串S以及长度为n的字符型一维数组a，编写一个函数，统计a中每个字符在字符串S中出现的次数，要求该函数以s,a,n为形参，一维整型数组为返回值

思路：

• 数组hash实现，定义一个长度为255的长度的数组，保证所有的字符串都考虑进去
• 然后统计s中所有字符各自出现的次数，然后访问字符串数组a，然后将结果，加入到result中

代码：

//思路：先统计S中每个字符出现的次数，然后再遍历a，通过hash表反应a中每个字符在s中出现的次数 
int *count(char *s, char a[], int n){
	int *hash = (int *)malloc(sizeof(int)*255);		//C语言中char类型默认是有符号类型,字符串的ASCII码范围是0-255
	int *result = (int *)malloc(sizeof(int)*n);		//保存结果 
	memset(hash,0,sizeof(int)*255);					//初始化赋值 
	int i = 0;
	while(s[i]!='\0'){
		hash[s[i++]]++;
	}
	for(i=0; i < n; i++){
		printf("%c在S中出现的次数为%d\n",a[i],hash[a[i]]);
		result[i] = hash[a[i]]; 
	}
	return result;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

第二题

2、m行n列矩阵，编写程序将矩阵中值小于0的元所在行与列上的所有元素置为0，并输出

思路：

• 不能直接赋值为0
• 得先把0暂时放到第一行或者第一列
• 同时保存原来第一行和第一列的是否有0
• 然后遍历非第一行和第一列的所有元素，判断第一行或者第一列是否为0，如果是，将非第一行和第一列的该行该列所有元素置为0
• 然后判断当前第一行和第一列是否最初就有0元素，有的话，则置该行或者该列为0

代码：

//思路：不能直接赋值为0，得先把0放到第一行或者第一列，然后还需要两个变量来保存第一行或者第一列来保存最开始的结果
 
void outQuadrix(int a[][N], int m, int n){
	int row = 0, col = 0;				//判断第一行或者第一列是否为0的标志 
	for(int i = 0; i < m; i++){
		for(int j = 0; j < n; j++){
			if(a[i][j]<=0){
				if(i==0){
					row = 1;
				}
				if(j==0){
					col = 1;
				}
				a[0][j]=0;			//第一行的第j列置为0 
				a[i][0]=0;	 		//第一列的第i行置为0 
			}
		}
	}
	
	for(int i = 1; i < m; i++){
		for(int j = 1; j < n; j++){
			if(a[i][0]==0 || a[0][j]==0){		//如果该行或者该列存在0，则该行或者该列的元素全部置为0 
				a[i][j] = 0;
			}
		}
	}	
	
	if(col){
		for(int i = 0; i < m; i++)
			a[i][0] = 0;
	}
	if(row){
		for(int i=0; i < n; i++){
			a[0][i] = 0;
		}
	}
	for(int i = 0; i < m; i++){
		for(int j = 0; j < n; j++){
			printf("%-4d",a[i][j]);
		}
		printf("\n");
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43