数据结构-线性表

数据结构-线性表

码农世界 2024-05-22 后端 59 次浏览 0个评论

顺序表的基本操作

1. 顺序表的插入操作

在顺序表L的第i个位置插入新元素e

bool ListInsert(SqList &L, int i, ElemType e) {
    if(i < 1 || i > L.length + 1) return false;
    if(L.length >= MaxSize) return false;
    for(int j = L.length; j >= i; j--) //i之后的元素右移
    	L.data[j] = L.data[j - 1];
    L.data[i - 1] = e;  //在i位置放入e
    L.length++;
    return true;
}
2.顺序表的删除操作

删除顺序表L中第i个位置的元素，若成功则返回true，并将被删除的元素用引用变量e返回，否则返回false

bool ListDelete(SqList &L, int i, ElemType &e) {
    if(i < 1 || i > L.length) return false;
    e = L.data[i - 1]; //可以返回被删除的元素
    for(int j = i; j < L.length; j++) //i之后的元素前移
    	L.data[j - 1] = L.data[j];
    L.length++;
    return true;
}
3.顺序表的按值查找

在顺序表L中查找第一个元素值等于e的元素，并返回其位序

bool ListDelete(SqList L, ElemType e) {
    for(int i = 0; i < L.length; i++) {
    	if(L.data == e) return i + 1;
    }
    retrun 0;
}
4.线性表的逆置问题

将长度为n的数组的前端k（k 

void reverse(int a[], int left, int right, int k) {
	int temp;
	for(int i = left, j = right; i < left + k && i < j; i++, j--) {
		temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

将长度为n的数组的前端k（k 

void MoveToEnd(int a[], int left, int right, int k) {
	reverse(a, 0, k - 1, k);
	reverse(a, 0, n - 1, k);
}

将长度为n的数组循环左移p个位置

void MoveP(int a[], int n, int p) {//只需将前p个元素逆置，然后将后面的元素逆置，最后逆置整个数组
	reverse(a, 0, p - 1, p);
	reverse(a, p, n - 1, n - p);
	reverse(a, 0, n - 1, n);
}

单链表的基本操作

1.头插法建立单链表
LinkList List_HeadInsert(LinkList &L) {
	LNode *s; int x;
	L = (LinkList)malloc(sizeof(LNode));//把结构体LNode的指针起名为LinkList
	L->next = NULL;
	cin >> x;
	while(x != 9999) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
		cin >> x;
	}
	return L;
}
2,尾插法建立单链表
LinkList List_HeadInsert(LinkList &L) {
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	LNode *s, *r = L; //r为链表尾指针
	cin >> x;
	while(x != 9999) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		r->next ->s;
		r = s; //更新尾指针	
		cin >> x;
	}
	r->next = NULL;
	return L;
}
3.按照序号查找节点值
LNode *GetElem(LinkList L, int i) {
	int j = 1;
	LNode *p = L->next;
	if(i == 0) return L;
	if(i < 1) return NULL;
	while(p && j < i) {
		p = p->next;
		j++;
	}
	return p;
}
4.按值查找表节点
p = GetElem(L, i - 1); //找到插入位置的前驱节点
s->next = p->next;
p->next = s;
temp = p->data;
p->data = s->data;
s->data = temp;
5.后插入节点操作
p = GetElem(L, i - 1); //找到插入位置的前驱节点
s->next = p->next;
p->next = s;
6.前插入节点操作
p = GetElem(L, i - 1); //找到插入位置的前驱节点
s->next = p->next;
p->next = s;
temp = p->data;
p->data = s->data;
s->data = temp;
7.删除节点操作
p = GetElem(L, i - 1); //P指向的是前一个节点
q = p->next; //找到被删除的节点
p->next = q->next;
free(q);
8.删除节点*p
q = p->next; //找到p的后继节点
p->data = p->next->data; //和后继节点交换数据域
p->next = q->next; //将*q节点断开
free(q);

双链表的基本操作

1.双链表的插入操作
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
2.双链表的删除操作
p->next = q->next;
q->next->prior = p;
free(q);

例题：

1.已知非空线性链表第一个节点的指针为list，写一个算法，找出链表中数据域最小的那个节点，并将其链接到链表的最前面，要求:
  1. 描述算法的基本设计思想
  2. 用算法描述语言描述算法
  3. 给出算法的时间复杂度分析
答案：

审题，找出链表中数据域最小的节点，将其连接到链表的最前面

算法思想

1.从第一个节点开始，通过指针p和前驱pre，沿链域遍历链表，首先令min = 第一个节点的数据域，遍历结点同时比较当前指针节点的数据域 x 与 min 的大小，若 x < min，则令 min = x，一直找到最后，返回 p 和 pre

2.创建新的节点q，数据域min，并令 q->next = list->next，list->next = q（头插法）

代码
void find_min(LNode* list) {
	LNode *p, *pre;
	LNode *min_node = list;
	LNode *min_node_pre = list;
	LNode *q = (LNode*)malloc(sizeof(LNode));
	p = list, pre = list;
	while(p) {
		pre = p;
		p = p->next;
		if(p->data < min_node->data) {
			min_node = p;
			min_node_pre = pre;
		}
	}
	if(min_node == list) return ;
	q->data = min_node->data;
	q->next = list;
	list = q;
	min_node_pre->next = min_pre->next;
	free(min_node);
}
时间复杂度分析

遍历链表找出最小的结点，时间复杂度为O(n)

2.给定两个单链表（为简化，假设两个链表均不含有环）的头指针分别为head1和head2，请设计一个算法判断这两个单链表是否相交，如果相交则返回第一个交点，要求算法的时间复杂度为O(length1+length2)。其中，length1和length2分别为两个链表的长度。
答案：

要求我们找到两个单链表相交的起始节点，时间复杂度要求O(length1 + length2) 

算法思想
  1. 双指针，定义两个指针p,q；
  2. p遍历完链表A后，开始遍历链表B；
  3. q遍历完链表B后，开始遍历链表A；
  4. 相当于两个指针都遍历了一次两个链表相同的部分和不同的部分，如果存在相同的部分，两指针相遇，如果没有共同的路，又由于一样的路程，那么最后会以 p == NULL && q == NULL; 结束循环。
代码
typedef struct LNode {
	int data;
	Struct LNode *next;
}LNode,*LinkList;
Struct LNode *getIntersectionNode(LNode *head1, LNode *head2) {
	Struct LNode *p = head1;
	Struct LNode *q = head2;
	while(p != q) {
		if(p == NULL) p = head2;
		else p = p->next;
		if(q == NULL) q = head1;
		else q = q->next;
	}
	return p;
}

 这个代码其实是O(len1*len2)的代码，但是红皮书上面就是这个代码，所以我也感觉很奇怪，如果我们要O(len1+len2)的代码，我们首先要遍历两个链表得到他们的长度，并求出两个长度之差，在长的链表上先遍历长度之差个节点之后，再同步遍历两个链表，直到找到他们相同节点，或者一直到链表结束，此时，该方法的时间复杂度才是O(len1+len2)

3.在带头节点的单链表L中，删除所有值为ｘ的节点，并释放其空间，假设值为ｘ的节点不唯一，试编写算法以实现上述操作
答案：
算法思想

用 p 从头至尾扫描单链表，pre 指向 *p 节点的前缀。若 p 所指向节点的值为 x ，则删除，并让 p 移向下一个节点，否则让 pre，p 指针同步向后移一个节点。

代码
void Del_X_1(LinkList &L, ElemType x) {
	LNode *p = L->next, *pre = L, *q;
	while(p != NULL) {
		if(p->data == x) {
			q = p;
			p = p->next;
			pre->next = p;
			free(q);
		}
		else {
			pre = p;
			p = p->next;
		}
	}
}

本算法是在无序单链表中删除满足某种条件的所有节点，如果要更改其他条件只需要修改 if 语句，若要求删除值介于 mink 到 maxk 之间的所有节点，只需将 if 语句修改为 if(p->data > mink && p->data < maxk)。

时间复杂度分析

时间复杂度为O(n)，空间复杂度为O(1)

4.编写在带头节点的单链表L中删除一个最小值节点的高效算法（假设该节点唯一）
答案：
算法思想

用 p 从头至尾扫描单链表，pre 指向 *p 节点的前驱，用 minp 保存最小节点的指针（初值为p），minpre 指向 *minp 节点的前驱（初值为 pre）。一边扫描，一边比较，若 p->data 小于 minp->data， 则将 p, pre 分别赋值给 minp, minpre ，当 p 扫描结束时，minp 指向最小值节点，minpre，指向最小值节点的前驱节点，再将 minp 所指的节点删掉。

代码
LinkList Delete_Min(LinkList &L) {
	LNode* pre = L, *p = pre->next;
	LNode* minpre = pre, *minp = p;
	while(p != NULL) {
		if(p->data < minp->data) {
			minp = p;
			minpre = pre;
		}
		pre = p;
		p = p->next;
	}
	minpre->next = minp->next;
	free(minp);
	return L;
}
时间复杂度分析

时间复杂度为O(n)

5.编写算法将带头节点的单链表就地逆置，所谓就地就是指空间复杂度为O(1)
答案：

由于是面向考研，所以不是很建议用递归的方法书写

算法思想

pre, p, r 指向三个相邻的节点，我们将 pre 初始指向 L头节点，所以我们只需要让 p 节点之后的节点的 next 指向他前一个节点即可，但是由于我们一旦改变指针指向，那么后面的就会断开，所以用 r 来当作已经断开的第一个节点， 然后每次递推遍历到最后一个节点，再把头节点指向最后一个节点，处理时候只需要注意两点，我们处理第一个节点的时候应该把他的 next 域置为 NULL，而不是再指向头节点，在处理完最后一个节点的时候我们要让头节点指向他

代码
LinkList Reverse_2(LinkList L) {
	LNode* pre, *p = L->next, *r = p->next;
	p->next = NULL;
	while(r != NULL) {
		pre = p;
		p = r;
		r = r->next;
		p->next = pre;
	}
	L->next = p;
	return L;
}
时间复杂度分析

时间复杂度为O(n)

6.在一个带头节点的单链表中，所有节点的元素值无序，编写一个函数，删除表内所有介于给定的两个值之间的元素
答案：
算法思想

这个题就是之前3题的加强版，只需更改 if 

代码
void RangeDelete(LinkList &L, int min, int max) {
	LNode* pre = L, *p = L->next, *q;
	while(p != NULL) {
		if(p->data > min && p->data next;
			pre->next = p;
			free(q);
		}
		else {
			pre = p;
			p = p->next;
		}
	}
}
时间复杂度分析

时间复杂度为O(n)

7.设C = {a1, b1, a2, b2 .....   an, bn}为线性表，采用带头节点的单链表存放，设计一个就地算法，将其拆分为两个线性表，使得A = {a1, a2, ..... , an}，B = {bn, bn-1......., b1}
答案：
算法思想

循环遍历链表C，采用尾插法将一个节点插入表A，采用头插法将一个节点插入表B

代码
LinkList DisCreat_2 (LinkList &L) {
	LinkList B = (LinkList)malloc(sizeof(LNode));
	B->next = NULL;
	LNode *p = A->next, *q;
	LNode *ra = A;
	while(p != NULL) {
		ra->next = p; //尾插法
		ra = p;
		p = p->next;
		if(p != NULL) { //头插法
			q = p->next;
			p->next = B->next;
			B->next = p;
			p = q;
		}
	}    
	ra->next = NULL;
	return B;                      
}
时间复杂度分析

注意，头插法插入节点之后，*p 的指针域已经发生改变，我们需要使用变量保存他的后继节点

8.在一个递增有序的单链表中，存在重复的元素，设计算法删除重复的元素
答案：
算法思想

由于是有序表，因此所有相同值域的节点都是相邻的。用 p 扫描递增单链表L，若 *p 节点的值域等于其后继节点的值域，则删除后者，否则 p 移向下一个节点

代码
void Del_Same(LinkList &L) {
	LNode *p = L->next, *q;
	if(p == NULL) return ;
	while(p->next != NULL) {
		q = p->next;
		if(p->data == q->data) {
			p->next = q->next;
			free(q);
		}
		else {
			p = p->next;
		}
	}
}
时间复杂度分析 

时间复杂度为O(n)

9.A和B是两个单链表（带头节点），其中元素递增有序。设计算法从A和B中的公共元素产生单链表C，要求不破坏A，B的节点
答案：
算法思想

表A，B都有序，可从第一个元素起依次比较A，B两表的元素，若元素值不等，则值小的指针往后移。若元素值相等，则创建一个值等于两节点的元素值的新节点，使用尾插法插入到新的链表中，并将两个原表指针往后移一位，直到其中一个链表遍历到表尾

代码
void Get_Common(LinkList A, LinkList B) {
	LNode *p = A->next, *q = B->next, *ra, *s;
	LinkList C = (LinkList)malloc(sizeof(LNode));
	ra = C;
	while(p != NULL && q != NULL) {
		if(p->data < q->data) p = p->next;
		else if(p->data > q->data) q = q->next;
		else {
			s = (LinkList)malloc(sizeif(LNode));
			s->data = p->data;
			r->next = s;
			r = s;
			p = p->next;
			q = q->next;
		}
	}
	r->next = NULL;
}
时间复杂度分析
10.已知两个链表A和B分别表示两个集合，其元素递增排列，编制函数，求A与B的交集，并存放于A链表中
答案：
算法思想

采用归并的思想，设置两个工作指针 pa 和 pb ，对两个链表进行扫描，只有同时出现在两个集合中的元素才能链接到结果表中且仅保留一个，其他的节点全部释放，当一个链表遍历完毕后，释放另一个链表剩下的全部节点

代码
LinkList Union(LinkList &la, LinkList &lb) {
	LNode *pa = la->next;
	LNode *pb = lb->next;
	LNode *pc = la, *u;
	while(pa && Pb) {
		if(pa->data == pb->data) {
			pc->next = pa;
			pc = pa;
			pa = pa->next;
			u = pb;
			pb = pb->next;
			free(u);
		}
		else if(pa->data < pb->data) {
			u = pa;
			pa = pa->next;
			free(u);
		}
		else {
			u = pb;
			pb = pb->next;
			free(u);
		}
	} 
	while(pa) {
		u = pa;
		pa = pa->next;
		free(pa);
	}
	while(pb) {
		u = pb;
		pb = pb->next;
		free(pb);
	}
	pc->next = NULL;
	free(lb);
	return la;
}
时间复杂度分析

时间复杂度为O(len1 + len2)

11.两个整数序列A，B，已经存入两个单链表中，设计一个算法，判断序列 B 是否是序列 A 的连续子序列
答案：
算法思想

操作从两个链表的第一个节点开始，若对应数据相等，则后移指针，若对应数据不等，则A链表从上次开始比较的节点的后继节点开始比较，B链表仍然从第一个节点开始比较，直到B链表到尾则表示匹配成功，A链表到尾但是B链表未到尾则表示匹配失败，操作中应记住A链表每次开始的节点

代码
int Pattern(LinkList A, LinkList B) {
	LNode *p = A;
	LNode *pre = p;
	LNode *q = B;
	while(q && p) {
		if(p->data == q->data) {
			p = p->next;
			q = q->next;
		}
		else {
			pre = pre->next;
			p = pre;
			q = B;
		}
	}
	if(q == NULL) return 1;
	else return 0;
}
时间复杂度分析
12.设计一个算法用来判断带头节点的循环双链表是否对称
答案：
算法思想

让 p 从左向右开始扫描，让 q 从右向左开始扫描，直到他们指向同一个节点或相邻，若他们所指节点值相同，则继续进行下去，否则返回 0，若比较全部相等，则返回 1

代码
int Symmetry(DLinkList L) {
	DNode *p = L->next, *q = L->prior;
	while(p != q && q->next != p) {
		if(p->data == q->data) {
			 p = p->next;
			 q = q->next;
		}
		else return 0;
	}
	return 1;
}
时间复杂度分析
13.有两个循环单链表，链表头指针分别为 h1 和 h2，编写一个函数将链表 h2 链接到链表 h1 之后，要求连接后的链表仍保持循环链表形式
答案：
算法思想

先找到两个链表的尾指针，将第一个链表的尾指针与第二个链表的头指针节点链接到一起，再把第二个链表的尾指针指向第一个链表的头指针使之成为循环

代码
LinkList Link(LinkList &h1, LinkList &h2) {
	LNode *p, *q;
	p = h1;
	while(p->next != NULL) {
		p = p->next;
	}
	q = h2;
	while(q->next != NULL) {
		q = q->next;
	}
	p->next = h2;
	q->next = h1;
	return h1;
}
时间复杂度
14.设有一个带头节点的非循环双链表L，其每个节点中除有 pre, data 和 next 域外，还有一个访问频度域 frep，其值均初始化为零。每当链表中进行一次 Locate(L, x) 运算时，令值为 x 的节点中 frep 域的值增加 1，并使此链表中的节点保持按访问频度递减的顺序排列，且最近访问的节点排在频度相同的节点之前，以便使频繁访问的节点总是靠近表头。试编写符合上述要求的 Locate(L, x) 函数，返回找到节点的地址，类型为指针型
答案：
算法思想

首先在双向链表中查找数据值为 x 的节点，查到后，将节点从链表上摘下来，然后顺着节点的前驱链找到该节点的插入位置，并插入到该位置

代码
DLinkList Locate(DLinkList &L, ElemType x) {
	DNode *p = L->next, *q;
	while(p && p->next != x) {
		p = p->next;
	}
	if(!p) exit(0);
	else {
		p->frep++;
		if(p->pre == L || p->pre->frep > p->frep) {
			return p;
		}
		if(p->next != NULL) p->next->pre = p->pre;
		p->pre->next = pre->next;
		q = p->pre;
		while(q != L && q->frep <= p->frep) {
			q = q->pre;
		}		
		p->next = q->next;
		if(q->next != NULL) q->next->pre = p;
		p->pre = q;
		q->next = p;
	}
	return p;
}
时间复杂度 
15.设将 n（n ＞1）个整数存放到不带头节点的单链表 L 中，设计算法将 L 中保存的序列循环右移 k（0
答案：
算法思想

遍历链表计算表长 n，并找到链表的尾节点，将其与首节点相连，得到一个循环单链表，然后，找到新链表的尾节点，它为原链表的第 n - k 个节点，令 L 指向新链表尾节点的下一个节点，并将环断开，得到新的链表

代码
LNode *Converse(LNode *L, int k) {
	int n = 1;
	LNode *p = L;
	while(p->next != NULL) {
		p = p->next;
		n++;
	}
	p->next = L;
	for(int i = 1; i <= n - k; i++) {
		p = p->next;
	}
	L = p->next;
	p->next = NULL;
	return L;
}
时间复杂度

时间复杂度是O(n)

16.单链表有环，是指单链表的最后一个节点的指针指向了链表中的某一个节点，试编写算法判断单链表是否存在环
答案：
算法思想

设置快慢指针 fast 和 slow 最初都指向链表头 head。slow每次都一步，即 slow = slow->next; fast 每次走两步，即 fast = fast->next->next。fast 比 slow 走得快，若有环，则 fast 一定先进入环，而 slow 后进入环。两个指针都进入环后，经过若干操作后两个指针定能在环上相遇。这样就可以判断一个链表是否有环。从头节点到环的入口点的距离等于 n 倍的环长减去环入口点到相遇点的距离。即 a = n * r - x，当 r = 1的时候，slow 指针只需要再走 n - x，而 head 指针只需要再走 a = n - x 所以他们走的路程相等。因此可以设置两个指针，一个指向 head，一个指向相遇点，两个指针同步移动，相遇点即为环的入口点。

代码
LNode* FindLoopStart(LNode *head) {
	LNode* fast = head, *slow = head;
	while(fast != NULL && fast->next != NULL) {
		slow = slow->next;
		fast = fast->next->next;
		if(slow == fast) break;
	}
	if(fast == NULL || fast->next == NULL) return NULL;
	LNode *p1 = head, *p2 = slow;
	while(p1 != p2) {
		p1 = p1->next;
		p2 = p2->next;
	}
	return p1;
}
时间复杂度

当 fast 与 slow 相遇的时候 slow 肯定没有遍历完链表，所以算法的时间复杂度为O(n)

17.设有一个长度 n（n 为偶数）的不带头节点的单链表，且节点值都大于0，设计算法求这个单链表的最大孪生和。孪生和定义为一个节点值与其孪生节点值之和，对于第 i 个节点（从 0 开始），其孪生节点为第 n-i-1 个节点
答案：
算法思想

设置快慢两个指针分别为 fast 和 slow，初始时 slow 指向 L (第一个节点)，fast 指向 L->next (第二个节点)，之后 slow 每次走一步，fast 每次走两步。当 fast 指向表尾（第 n 个节点时），slow 正好指向链表的中间点（第 n/2 个节点），即 slow 正好指向链表前半部分的最后一个节点。将链表的后半部分逆置，然后设置两个指针分别指向链表前半部分和后半部分的首节点，在遍历过程中计算两个指针所指节点的元素之和，并维护最大值

代码
int PairSum(LinkList L) {
	LNode *fast = L->next, *slow = L;
	while(fast != NULL && fast->next != NULL) {
		fast = fast->next->next;
		slow = slow->next;
	}
	LNode *newHead = NULL, *p = slow->next, *tmp;
	while(p != NULL) {
		tmp = p->next;
		p->next = newHead;
		newHead = p;
		p = tmp;
	}
	int mx = 0;
	p = L;
	LNode *q = newHead;
	while(p != NULL) {
		if((p->data + q->data) > mx) mx = p->data + q->data;
		p = p->next;
		q = q->next;
	}
	return mx;
}
时间复杂度

时间复杂度为O(n)

18.已知一个带有头节点的单链表，节点结构为

数据结构-线性表

假设该链表只给出了头指针 list 。在不改变链表的前提下，设计一个尽可能告诉高效的算法，查找链表中倒数第 k 个位置上的节点（ k 为正整数）。若查找成功，算法输出该节点的 data 域的值，并返回 1；否则，只返回 0
答案：
算法思想

定义两个指针变量 p 和 q，初始时均指向头节点的下一个节点（链表的第一个节点），p 指针沿链表移动，当 p 指针移动到第 k 个节点时，q 指针开始与 p 指针同时移动，当 p 指针移动到最后一个节点时，q 指针所指示节点为倒数第 k 个节点。以上过程只对链表进行一次扫描

代码
typedef int ElemType;
typedef struct LNode {
	ElemType data;
	struct LNode *link;
}LNode, *LinkList;
int search_k(LinkList list, int k) {
	LNode *p = list->link, *q = list->link;
	int cnt = 0;
	while(p != NULL) {
		if(cnt < k) cnt++;
		else q = q->next;
		p = p->next;
	}
	if(cnt < k) return 0;
	else {
		cout << q->data << endl;
	}
	return 1;
}
时间复杂度
19.假定采用带头节点的单链表保存单词，当两个单词有相同的后缀时，可共享相同的后缀存储空间，例如，loading 和 being 的存储映像如下图所示，
设 str1 和 str2 分别指向两个单词所在单链表的头节点，链表节点结构为，请设计一个时间上尽可能高效的算法，找出由 str1 和 str2 所指向两个链表共同后缀的起始位置
答案：
算法思想
  1. 分别求出 str1 和 str2 所指的两个链表长度 m 和 n
  2. 将两个链表的表尾对齐，令指针 p 和 q 分别指向 str1 和 str2 的头节点，若 m >= n，则 p 指针先走，使 p 指向链表中的第 m - n +１个节点，若 m < n，则 q 指向链表中的第 n - m + 1 个节点，即使指针 p 和 q 所指向的节点到表尾的长度相等
  3. 反复将指针 p 和 q 同步向后移动，并判断他们是否指向同一节点。当 p ，q 指向同一节点，则该店即为所求的共同后缀的起始位置
代码
typedef struct Node {
	char data;
	struct Node *next;
}SNode;
int listlen(SNode *head) {
	int len = 0;
	while(head->next != NULL){
		len++;
		head = head->next;
	}
	return len;
}
SNode* find_list(SNode *str1, SNode *str2) {
	int m, n;
	SNode *p, *q;
	m = listlen(str1);
	n = listlen(str2);
	for(p = str1; m > n; m--) p = p->next;
	for(q = str2; m < n; n--) q = q->next;
	while(q->next != p->next && q->next != NULL) {
		p = p->next;
		q = q->next;
	} 
	return p->next;
}
时间复杂度

时间复杂度为O( len1 + len 2) 或者 O(max(len1, len2)

20.用单链表保存 m 个整数，节点的结构为，且 data 的 绝对值时正整数，先要求设计一个时间复杂度尽可能高效的算法，对于链表中 data 绝对值相等的节点，仅保留第一次出现的节点而删除其余绝对值相等的节点
答案：
算法思想

算法的核心思想是用空间换时间，使用辅助数组记录链表中已出现的数值，从而只需对链表进行一次扫描

因为data 的绝对值 <= n，故辅助数组 q 的大小为 n + 1，个元素初值均是 0，依次扫描链表中的各节点，同时检查 q 的值，若为 0 则保留该节点，病令 q 的值为 1，否则将该节点从链表中删除

代码
typedef struct Node {
	int data;
	struct Node *link;
}Node;
Typedef Node *PNode;
void func(PNode h, int n) {
	PNode p = h, r;
	int *q, m;
	q = (int *)malloc(sizeof(int)*(n + 1));
	for(int i = 0; i < n + 1; i++) *(q + i) = 0;
	while(p->link != NULL) {
		m = p->link->data > 0? p->link->data :　-p->link->data;
		if(*(q + m) == 0) {
			*(q + m) = 1;
			p = p->link;
		}
		else {
			r = p->link;
			p->link = r->link;
			free(r);
		}
	}
	free(q);
}
时间复杂度

时间复杂度为O(n)，空间复杂度为O(n)

21.将带头结点的单链表a1, a2, a3......an-1，an 重新排列为 a1，an，a2，an-1，a3......，要求空间复杂度为O(1)
答案：
算法思想

观察结果链表发现都是在原链表摘取第一个元素，在摘取倒数一个元素.......依次合并而成的，为了方便链表后半段取元素，需要先将链表后半段原地逆置，否则每次取最后一个节点都需要遍历一次链表，先找出链表 L 的中间节点，为此设置两个指针 p 和 q，指针 p 每次走一步，指针 q 每次走两步，当指针 q 到达链尾时，指针 p 正好在链表的中间节点，然后将 L 的后半段节点原地逆置，从单链表前后两段中依次各取一个节点，按要求重排

代码
void rearrange(node* head)
{
    node* p1 = head, * p2 = head;
    //该循环得到的p1是原链表的中间结点，也是最终所需的链表的最后一个结点
    //得到的p2是原链表的最后一个结点
    while (p2->next != nullptr)
    {
        p1 = p1->next;
        p2 = p2->next;
        if (p2->next != nullptr) p2 = p2->next;
        else break;
    }
 
    //将p2设为p1的下一个结点，即后半段链表的第一个结点
    p2 = p1->next;
    //这里是个妙招，先将p1->next改为nullptr，可以方便地让逆置后的链表的尾结点指向nullptr
    p1->next = nullptr;
    //用p1->next和p2来逆置后半段链表
    //在这个过程中p1位置始终不变
    //该循环得到的p1->next是逆置后的后半段链表的第一个结点
    while (p2 != nullptr)
    {
        node* temp = p2->next;
        p2->next = p1->next;
        p1->next = p2;
        p2 = temp;
    }
 
    //left是前半段链表的第一个结点，right是逆置后的后半段链表的第一个结点
    node* left = head->next;
    node* right = p1->next;
    //p1一直是原链表的中间结点，也是最终所需的链表的最后一个结点，于是可以将p1->next赋为nullptr
    p1->next = nullptr;
    //将逆置后的后半段链表中的结点，逐个插入到前半段链表中
    while (right != nullptr)
    {
        node* temp = right->next;
        right->next = left->next;
        left->next = right;
        left = right->next;
        right = temp;
    }
}
时间复杂度

时间复杂度是O(n)

转载请注明来自码农世界，本文标题：《数据结构-线性表》

百度分享代码，如果开启HTTPS请参考李洋个人博客
37815篇文章 站点 微博
每一天，每一秒，你所做的决定都会改变你的人生！

发表评论

快捷回复：

评论列表 （暂无评论，59人围观）参与讨论

还没有评论，来说两句吧...

Top