数据结构线性表操作与例题总结

2. 所有链表操作前先判断是否为空if (first->next == NULL)return;

1. 设有一个整数顺序表，编写函数将其调整为奇数在前，偶数在后。

思路为left从表头出发找到第一个偶数，right从表尾出发，找到第一个奇数，若此时left<right则交换两个元素
简化了答案的操作，方便理解与记忆。

void revise(int a[], int n)
{
	int left = 0;
	int right = n - 1;
	int tmp = 0;
	while (left < right)
	{
		while (a[right] % 2 == 0) right--;//右侧扫描
		while (a[left] % 2 != 0) left++;//左侧扫描

		if (left < right)
		{
			tmp = a[left];
			a[left] = a[right];
			a[right] = tmp;
		}
	}
}

要注意while循环扫描的判断条件是满足条件“指针”移动

2)调整为负数在前，正数在后。

只需将取余为零的判断条件，修改为大于0或小于0

void revise(int a[], int n)
{
	int left = 0;
	int right = n - 1;
	int tmp = 0;
	while (left < right)
	{
		while (a[right] >= 0) right--;//右侧扫描
		while (a[left] <= 0) left++;//左侧扫描

		if (left < right)
		{
			tmp = a[left];
			a[left] = a[right];
			a[right] = tmp;
		}
	}
}

3)在单链表中实现。

1.交换数据版

设立工作指针p、q，让p先出发找第一个偶数，找到后在定位q=p->next，保证寻找到的奇数在偶数后面（避免p超过q的位置，将已经在最终位置的元素调整到错误位置）

void LinkList::revise()
{
    if(first->next==NULL) return;
	Node* p = first->next;
	Node* q = p->next;
	int temp = 0;
	while (q != NULL && p != NULL)
	{
		while (p&&p->data % 2 != 0)p = p->next;
		q=p->next;
		//保证q从一个偶数开始
		while (q&&q->data % 2 == 0)q = q->next;
	
		if (q != NULL && p != NULL)
		{
			temp = q->data;
			q->data = p->data;
			p->data = temp;
		}
	}
}

2. 交换节点版

思路为：
将链表打散，用两个指针分别存储新的两个链表

例如：当第一个节点为奇数则将其链接到odd后面

第三个节点为偶数：将其链接到even后面

void LinkList::revise() 
{
    if (first->next == NULL)return;
	Node* work = first->next;//带头结点的形式（这里指向第一个节点）
	Node* odd_first = new Node;//生成头节点
	Node* even_first =new Node;
	Node* odd = odd_first;
	Node* even= even_first;

	
	while (work!=NULL)
	{
	//若为奇数，添加到奇数指针后
		if (work->data % 2 != 0) {
			odd->next = work;
			odd = odd->next;
		}
		else
		{
			even->next = work;
			even = even->next;
		}
		work = work->next;
	}
	even->next = NULL;//最后一个节点置空
	odd->next = even_first->next;
	delete even_first;
	first = odd_first;//注意这里有头节点
}

2.编写函数oddevenList把不带头结点的单链表中所有奇数编号的结点调整到所有偶数编号的结点前面。

思路同上面的题，代码只是判断条件改变

void LinkList::revise() {

   if (first->next == NULL)return;
	Node* work = first->next;//带头结点的形式（这里指向第一个节点）
	Node* odd_first = new Node;//生成头节点
	Node* even_first =new Node;
	Node* odd = odd_first;
	Node* even= even_first;
	int i = 1;
	
	while (work!=NULL)
	{
		if (i % 2 != 0) {
			odd->next = work;
			odd = odd->next;
		}
		else
		{
			even->next = work;
			even = even->next;
		}
		work = work->next;
		i++;
	}
	even->next = NULL;
	odd->next = even_first->next;
	delete even_first;
	first = odd_first;

}

3.设计一个在带头结点的单链表中删除一个最小值结点的高效算法。

思路:
设立一个工作指针q，负责遍历链表（在访问元素的前一个节点，方便后续删除节点）；另外一个p用于指向最小节点前面一个节点

void LinkList::delmin() 
{
	Node* p, * q;
	if (first->next == NULL)   return;
	p = first;//p存放最小节点的前一个
	q = first->next;

	while (q->next != NULL)
	{
	    //若该节点比最小值节点要小，则更换
		if (q->next->data <p->next->data)
		{
			p = q;
		}
		q = q->next;
	}
     //现在p指向的为最小节点的前一个节点
    Node* temp = p->next;
	p->next = temp->next;
	delete temp;
	//若不需要删除该节点只需：
	//p->next = p->next->next;
}

4.设计一个算法，在带头结点的单链表中删除值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同）。

思路：
两个指针同步移动，p在前q在后，q来识别是否满足删除条件，若满足，p将q架空，并删除q所指节点，删除后将q归位至p节点的后面；若不满足条件，两个指针同步后移。

void LinkList::del(int mink, int maxk)
{
    if(first->next==NULL) return;
	Node* p = first;
	Node* q = first->next;
	while (q!=NULL)
	{
		if (q->data > mink&& q->data < maxk)
		{
			p->next = q->next;//把q架空
			delete q;
			q = p->next;
		}
		else {
			//整体后移
			q = q->next;
			p = p->next;	
		}

	}
}

5. 编写函数查找带头结点的单链表中倒数第4个元素。

思路：
设置两个指针，相差3个节点，同步移动，当p2成为NULL后p1的位置即为倒数第四个节点

要注意的是p1向前移动的判断条件为p1->next != NULL，否则若正好三个节点，p1将指向NULL，没有指向第四个节点，但此时只有三个节点，不满足条件

int LinkList::findLast4th()
{
    if(first->next==NULL) return;
	Node* p1 = first;
	Node* p2 = first;
	//p1先走4步。
	for (int i = 0; i < 4; i++)
	{
		if (p1->next != NULL)
		{
			p1 = p1->next;
		}
		else
		{
			cout << "链表长度不够" << endl;
			return false;//链表长度不够
		}
	}
	//同步移动
	while (p1 != NULL)
	{
		p1 = p1->next;
		p2 = p2->next;
	}
	return p2->data;

}

6. 设采用两个递增有序的单链表分别表示A和B，编写函数生成新的单链表C，其中C=A∩B。

思路:
1.初始化

2. pa、pb向后移动的过程中，判断pa和pb所指向的值是否相等
3. 若值相等，pCEnd后增加节点，将pa、pb同时向后移动一位，
4. 若pa->data< pb->data则,pa向后移动一位，
5. 若pa->data> pb->data则,pb向后移动一位，
6. 最后将pCEnd->next=NULL;完成链表构造

Node* intersection(Node* pA, Node* pB)
{
    if(first->next==NULL) return;
	Node* pa = pA->next;
	Node* pb = pB->next;
	Node* pCHead = new Node;  //A与B交集头指针
	Node* pCEnd = pCHead;  //A与B交集尾指针
	
	while (pa!=NULL&&pb!=NULL)
	{
		if (pa->data<pb->data)
		{
			pa = pa->next;
		}
		//相等则链表向后拓展一位
		else if (pa->data == pb->data)
		{
			Node* s = new Node;
			s->data = pa->data;
			pCEnd->next = s;
			pCEnd = s;
			//遇到相同的元素后都向后移动一个位置
			pa = pa->next;
			pb = pb->next;
		}
		//pa->data<pb->data的情况
		else {
			pb = pb->next;
		}
	}
	pCEnd->next = NULL;
	return pCHead;

}