第一章 线性表

发表于 |
字数统计: 1.1k | 阅读时长 ≈ 5

第一章 线性表

1. 编写一个将给定的线性链表逆转的C 函数，只允许改变结点的指针值，不允许移动结点值。给出调用方法。

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
/*
typedef struct node
{
	int data; //存储数据
	struct node* next; //指向下一个节点的指针
} NODE;
*/
Node * reverse_LinkList (NODE * head)
{
	//单向链表，请说明自己写的程序是否带表头结点，必须考虑链表为空的情况
	//带有表头结点的链表
	if(head -> next == NULL)
		return head;//链表为空
	NODE* now = head -> next, t = head -> next;
	NODE* t = t -> next;
	while(t -> next != NULL)
	{
		t -> next = &now;//当前结点的next指向上一个结点的地址
		now = t;
		t = t -> next;//now和t都向后移动
	}
	head -> next = t;//表头结点
	return head;
}
//调用方法：
//a为一带表头的链表的表头
reverse_LinkList(a);

2. 对于给定的线性链表，编写一个把值为a的结点插在值为b的结点的前面的C函数。若值为b的结点不在线性链表中，则把a插在链表的最后。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//分两种情况：带表头结点和不带表头结点，必须考虑链表为空的情况。函数参数部分的“？”请自己补充，并分别给出调用方法。
int insertLinkListBefore-WithHeadNode（NODE* head, int a, int b）
{
	NODE * t = head -> next;
	if(t == NULL) //链表为空
	{
		NODE* temp = (NODE*)malloc(sizeof(NODE));
		temp -> data = a;
		head -> next = temp;
		return 0;
	}
	NODE *now = head;
	while(t -> next != NULL)
	{
		if(t -> data == b)//找到值为b的结点
		{
			NODE* temp = (NODE*)malloc(sizeof(NODE));
			temp -> data = a;
			now -> next = temp;//前一个结点的下一个值指向temp
			temp -> next = t;/／值为a的下一个结点指向当前结点(值为b的结点)
			break;
		}
		now = t;
		t = t -> next;//now和t都向前移动
	}
	if（t -> data == b）//如果存在值为b的结点
		return 0;
	else
	{   //不在线性链表中，则把a插在链表的最后。
		NODE* temp = (NODE*)malloc(sizeof(NODE));
		temp -> data = a;
		temp -> next = NULL;
		t -> next = temp;
	}
}
int insertLinkListBefore-WithOutHeadNode（NODE* head, int a, int b）
{
	if(head == NULL)
	{
		head = (NODE*)malloc(sizeof(NODE));
		head -> data = b;
		head -> next = NULL;
		return 0;
	}
	NODE *now = head;
	NODE *t = head -> next;
	while(t -> next != NULL)
	{
		if(t -> data == b)//找到值为b的结点
		{
			NODE* temp = (NODE*)malloc(sizeof(NODE));
			temp -> data = a;
			now -> next = temp;//前一个结点的下一个值指向temp
			temp -> next = t;//值为a的下一个结点指向当前结点(值为b的结点)
			break;
		}
		now = t;
		t = t -> next;//now和t都向前移动
	}
	if（t -> data == b）//如果存在值为b的结点
		return 0;
	else
	{   //不在线性链表中，则把a插在链表的最后。
		NODE* temp = (NODE*)malloc(sizeof(NODE));
		temp -> data = a;
		temp -> next = NULL;
		t -> next = temp;
	}
}
//调用方法：
//px为一带表头的链表的head py为一不带表头的链表的head 
//a b为两个变量
insertLinkListBefore-WithHeadNode(px, a, b);
insertLinkListBefore-WithOutHeadNode(py, a, b);

3. 对比P33页的程序，说明利用带表头结点的环形链表使得程序段发生了什么变化，为什么？

判断两链是否为空时条件发生变化。带表头结点时只有当两个表都遍历完以后才会结束循环
原因：表头结点的exp字段为-1，当其中一个遍历完后其exp值始终为-1向后进行的一定是另一个环形链表，而且一定会结束。

4. 假设A和B是两个按结点值从小到大排列的有序环形链表。试编写一个将这两个有序的环形链表归并为一个按节点值从小到大排列的有序环形链表的C函数。

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
44
45
NODE * MergeLinkList（NODE* A，NODE * B）
{
	//要求返回新链表的head 指针，不为新链表申请新的存储空间
	NODE* A_head = A -> next;
	NODE* B_head = B -> next;
	NODE *pa = A_head, *pb = B_head;
	NODE * now;
	if(pa -> data < pb -> data)
	{
	   A -> next = pa;
	   now = pa;
	   pa = pa -> next;
	}
	else
	{
		A -> next = pb;
		now = pb;
		pb = pb ->next;
	}
	while(pa -> next != A_head && pb -> next == B_head)
	{
		if(pa -> data < pb -> data)
		{
			now.next = pa;
			pa = pa -> next;
		}
		else
		{
			now.next = pb;
			pb = pb -> next;
		}
	}
	while(pa -> next != A_head)//如果链表A没遍历完
	{
		now.next = pa;
		pa = pa -> next;
	}
	//两个只会执行其中一个
	while(pb -> next != B_head)//如果链表B没遍历完
	{
		now.next = pb;
		pb = pb -> next;
	}
	return A;
}

5.求广义表的深度。我们规定空的广义表的深度为0，而一般地有&¥#¥#！@#——）^%()%^

看不懂