#include<stdio.h>
#include<stdlib.h>
/*1在头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设为x的结点不唯一
*/
//算法思想：找到前驱，用p遍历整个链表，用q标记找到的元素然后删除q
void Del_x (Linklist &L, Elemtype x){
Lnode *pre = L;
Lnode *p = L->next;
Lnode *q;
while(p!=null){
if(p->data == x){
q = p;
p = p->next;
pre->next = p;
free(q);
}
else{
pre = p;
p = p->next;
}
}
}
/*2将两个有序顺序表合并成一个新的有序顺序表，并由函数返回结果顺序表*/
//算法思想：比较A和B中较小的元素依次存入C中，若剩余则依次存入C
bool Merge(SqList A, SqList B, SqList &C){
if(A.length+B.length>C.MaxSize){
return false;
}
int i,j,k=0;
while(i<A.length&&j<B.length){
if(A.data[i]<B.data[j]){
C.data[k++]=A.data[i++];
}
else{
C.data[k++]=B.data[j++];
}
}
while(i<A.length){
C.data[k++]=A.data[i++];
}
while(j<B.length){
C.data[k++]=B.data[j++];
}
C.length=k;
return true;
}
/*3设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)*/
//算法思想：将第0个和第n个交换，第1个和第n-1个交换......第i个和第n-1个交换
void Reverse(SqList &L){
Elemtype temp;
for(i=0;i<L.length/2;i++){
temp=L.data[i];
L.data[i]=L.data[L.length-i-1];//数组从0开始编址，所以数组长度需要减去1
L.data[L.length-i-1]=temp;
}
}
//3.2递归法
void Swap(i,j) {
Elemtype temp;
temp=i;
i=j;
j=temp;
}
void Reverse(int* A,int low,int high){
if(low < high){
swap(A[low],A[high]);
Reverse(A,low+1,high-1);
}
}
/*4对长度为n的顺序表，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素*/
//算法思想：扫描一次顺序表，记录下其中值为x的个数，将其中不是k的元素向前移动k个单位
//找到值为x的数据元素，然后进行删除（将后面元素移过来进行覆盖）
//O(n)扫描一次顺序表；O(1)申请常数个辅助空间
void Del_x(SqList& L, Elemtype x) {
int i = 0; int k = 0;
for (i = 0; i < L.length; i++) {
if (L.data[i] == x) {
k++;
}
else {
L.data[i - k] = L.data[i];
}
}
L.length = L.length - k;
}
//4.2算法思想：遍历顺序表，保留下不是x的值
void Del_x(SqList L, Elemtype x){
int k = 0;
for (int i = 0; i < L.length; i++){
if (L.data[i] != x){
L.data[k] = L.data[i];
k++;
}
}
L.length = k;
}
/*5从顺序表中删除其值在给定s和t之间（包含s和t，要求s<t）的所有元素，如果s或t不合理或者顺序表为空，则显示出错信息并退出运行*/
//算法思想：扫描一次顺序表，记录下其中在给定s和t之间（包含s和t，要求s<t）的的个数k，将其中不是k的元素向前移动k个单位
bool delete(SqList& L, ElemType s, ElemType t){
if (s >= t || L.length == 0)
return false;
int k = 0;
for (int i = 0; i < L.length; i++)
{
if (L.data[i] >= s && L.data[i] <= t)
++k;
else
L.data[i - k] = L.data[i];
}
L.length = L.length - k;
return true;
}
/*6从顺序表中删除所有其数值重复的元素，使表中所有元素的值均不相同。*/
//算法思想：第一个元素肯定不重复，依次向后扫描，不重复就保留，重复就不保留
//用指针i记录需要保留的元素，指针j来遍历表
bool Del_same(SqList L) {
int i = 0,j = 1;
if (L.length == 0) {
return false;
}
for (j = 1; j < L.length; j++) {
if (L.data[j] != L.data[i]) {
i++;
L.data[i] = L.data[j];
}//等于 L.data[++i] = L.data[j];
L.length = i + 1;//i从0开始编址
return true;
}
}
/*7已知在一维数组A[m + n]中依次存放网线个顺a表的位置互换,即将(b1, b2,b3...,bn)。试编写一个函数,将数组中两个顺序表的位置互换,
即将(b1, b2,b3...bn)放在(a1, a2,a3..., am)的前面*/
//算法思想：将前m个(a1,a2,......am)逆置，将后n个(b1,b2,......bn)，再将整个表逆置(第三题）
void Reverse(ElemType A[], int i, int j) {
ElemType temp;
for (int i = 0; i < A.length / 2; i++) {
temp = A.data[i];
A.data[i] = A.data[A.length - i - 1];
A.data[A.length - i - 1] = temp;
}
}
void exchange(ElemType A[], int m, int n) {//m:前m个元素，n：后n个元素
Reverse(A, 0, m - 1);
Reverse(A, m, m + n - 1);
Reverse(A, 0, m + n - 1);
}
/*8设将n（n>1）个整数存放到一位数组R中，设计一个在时间和空间两个方面都尽可能高的算法，
将R中保存的序列循环左移p（0<p<n）个位置，即将R中的数据由（X0,X1,X2,Xn-1）变成（Xp,Xp+1…Xn-1,X0,X1,Xp-1）*/
//算法思想：将前p个(X0,X1,,,,,Xp-1)逆置，将后n-p个(Xp,Xp+1......Xn-1)，再将整个表逆置
void Reverse(int R[], int from, int to) {
int temp, i;
for (i = 0; i < (to - from + 1) / 2; i++) {
temp = R[from + i];
R[from + i] = R[to - i];
R[to - i] = temp;
}
}
void exchange(int R[], int m, int n) {
Reverse(R, 0, p - 1);
Reverse(R, p, n - 1);
Reverse(R, 0, n - 1);
}
//时间复杂度分析：
//三句逆置代码分别为 O(p/2),O((n-p)/2),O(n/2)
//时间复杂度O(n),空间复杂度O(1)
/*9试编写带头结点的的单链表L中删除一个最小值结点的高效算法(假设最小值结点是唯一的)*/
//算法思想：用p遍历链表，用minp标记最小值，找到到最小值;
//找到后进行删除，所以不仅要标记最小值节点，还需要标记前驱指针pre和最小值前驱节点minpre
LinkList Delete_min(LinkList& L) {
LNode* pre = L, * p = L->next;
LNode* minpre = pre, * minp = p;
while (p) {
if (p->data < minp->data) {//找到最小值结点
minp = p;
minpre = pre;
}
else {
pre = p;
p = p->next;
}
}
minpre->next = minp->next;//删除最小值的结点
free(minp);
return L;
}
/*10头插法建立单链表*/
//逆置链表可以使用,输入数据的次序和生成链表的顺序相反
LinkList List_HeadInsert(LinkList& L) {
LNode* s, int x;//标记创建的新结点
L = (LinkList)malloc(sizeof(LNode));//创建头结点
L->next = NULL;//建立单链表元素为空
scanf("%d", &x);
while (x != -1) {
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
scanf("%d", &x);
}
return L;
}
/*11尾插法建立单链表*/
//输入数据的次序和生成链表的顺序相同，重点标记表尾
LinkList List_TailInsert(LinkList& L) {
int x;
L = (LinkList)malloc(sizeof(LNode));//创建头结点
LNode* s, * r = L;//r为表尾指针,指向头结点
//尾指针：当操作单链表表尾时，无需从头开始遍历，直接用尾指针进行增加结点
scanf("%d", &x);
while (x != -1) {
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s;//r指向新的表尾结点
scanf("%d", &x);
}
r->next = NULL;//尾结点置空
return L;
}
/*12试编写算法将带头结点的单链表就地逆置，所谓的“就地”是指辅助空间的复杂度为O (1)*/
//算法思想：头插法进行逆置，用p遍历标记结点，用r标记p的后续指针防止头插p结点后造成断链
//因为是头插法，插入得第一个元素就是完成之后最后一个，则需要先将头变空初始化（将头节点和原链表断开，相当于把L拿出来，然后再头插法逆置）
//但是不会断链，因为有r指针
//如果最后操作将尾节点变空，则又要遍历一次链表。同时，这样操作，也有利循环体的书写
LinkList Reverse_LinkList(LinkList& L) {
LNode* p, * r;
p = L->next;
L->next = NULL;
while (p != NULL) {
r = p->next;//保存p的后继结点
p->next = L->next;
L->next = p;
p = r;
}
return L;
}
//12.2算法思想：pre用来标记p的前驱，r用来标记p的后继，让p指向pre，然后pre和p，r后移一位继续
void ListReverse_L(LinkList& L) {
//指针反转
LNode* front, * p = L->next, * back = p->next;
p->next = NULL;//第一个结点指针反转后指向null
while (back != NULL) {//p的下一个是空说明p是最后一个节点
front = p;//依次后移
p = back;//依次后移
back = back->next;//依次后移
p->next = front;//指针反转
}
L->next = p;//最后一个节点连到头结点上
}
/*13设在一个带表头结点的单链表中所有元素的结点的数据值无序，试编写一个函数，删除表中所有介入给定的两个值（作为函数的参数给出）之间的元素的元素（若存在）*/
//算法思想：1.遍历链表，找min<x<max
//2.删掉x
void Delete(LinkList& L, int min, int max)
{
LNode* pre = L;
LNode* p = L->next;
while (p != null)
{
if (p->data > min && p - data < max)
{
pre->next = p->next;
free(p);
p = pre->next;
}
else
{
pre = p;
p = p->next;
}
}
}
/*14给定两个单链表，编写算法找出两个单链表的公共结点（公共结点之后的归并成一条链表）*/
//算法思想：暴力循环法，通过p,q指针分别遍历两个链表，然后一个动一个不动，寻找相同结点，直至两个指针都指向表尾
//时间复杂度：O（L1表长*L2表长）
Linklist Search_Common(LinkList& L1, LinkList& L2)
{
LNode* p = L1->next;
LNode* q = L2->next;
while (p != null)
{
while (q != null)
{
if (p = q)
return p; //找到公共结点，返回
else
q = q->next;//p不动，q向后移动
}
p = p->next; //p向后移动一位
q = L2->next; //重置q，进行新一轮的扫描
}
}
//14.2算法思想：（双指针问题）同时到达表尾时，若有公共结点则至少到最后一个结点是公共结点
//如果两条链表长度相等，则p和q同时移动即可
//若两条链表长度不想等，用较长的链表长度减去较短的链表长度得到差k，然后长链表先移动k位，然后再同步向后移动
//时间复杂度:O（L1表长+L2表长）线性复杂度
LinkList Search_Common(ListList& L1, LinkList& L2)
{
Lnode *p, *q;
int k;
int len1 = length(L1);
int len2 = length(L2);
//找较长的链表长度
if (len1 - len2 > 0)
{
k = len1 - len2;
p = L1->next; //让p指针始终指向较长的链表
q = L2->next;
}
else
{
k = len2 - len1;
p = L2->next;
q = L1->next;
}
while (k--) {
p = p->next;//让长链表先移动k位
}
while (p != null)
{
if (p = q) //若相等，则找到了公共结点
return p;
else //否则，同时向后移动一位
{
p = p->next;
q = q->next;
}
}
//已经移动到表尾，还没找到表明没有公共结点
return 0;
}
/*15将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变*/
//算法思想：相对顺序不变：尾插法
//用i进行计数，如果i % 2 == 0, 偶数，插入B中，否则插入A中
LinkList create(LinkList& A)
{
int i = 0;
B = (LinkList)malloc(sizeof(LNode));
B->next = NULL;//初始化B
LNode* p = A->next;
LNode* ra = A;
LNode* rb = B;
A->next = NULL;//把A头结点摘出来，在原A中遍历分别放至A和B中
while (p != NULL)
{
i++；
if (i % 2 == 0)
{
rb->next = p;
rb = p;
}
else
{
ra->next = p;
ra = p;
}
p = p->next;
}
ra->next = NULL;
rb->next = NULL;
return B;
}
//15.2算法思想：将第一个元素插入A，第二个元素插入B，交替插入
LinkList create(LinkList& A)
{
B = (LinkList)malloc(sizeof(LNode));
B->next = NULL;
Lnode *rb = B;
Lnode *ra = A;
LNode* p = A->next;
A->next = NULL;
while (p != NULL)
{
//将第一个元素插入A，第二个元素插入B，交替插入
ra->next = p;
ra = p;
p = p->next;
if (p->next != null)
{
rb->next = p;
rb = p;
p = p->next;
}
}
ra->next = NULL;
rb->next = NULL;
return B;
}
/*16设C={a1,b1,a2,b2,…an,bn}为线性表，采用带头结点的hc单链表存放，设计一个就地算法，将其拆分为两个线性表，使得A={a1…an}，B={bn,bn-1…b1}。*/
//算法思想：A链表采用尾插法，B链表采用头插法
//遍历C链表，将奇数号结点尾插在A中，将偶数号结点头插在B中
LinkList DisCreate2(LinkList& hc) {
LinkList A = (LinkList)malloc(sizeof(LNode));
LinkList B = (LinkList)malloc(sizeof(LNode));
A->next = NULL;
B->next = NULL;
//ra尾插法的尾指针
LNode* ra = A, * p, * r;
p = hc->next;//遍历指针
hc->next = NULL;
while (p != NULL) {
//尾插先进行，头插后进行
ra->next = p;
ra = p;//尾指针不断指向表尾
p = p->next;
if (p) {
r = p->next;//头插后，*p将断链，r暂时保存p的后继
p->next = B->next;
B->next = p;
p = r;
}
}
ra->next = NULL;//头插防断链，尾插留尾针
return A, B;
}
/*17在一个递增有序的线性表中，有数值相同的元素存在，若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素*/
//算法思想：递增有序，重复元素必定相邻，只要保留第一个元素，用pre和p的data比较（双指针）
void Del_Common(LinkList& L)
{
LNode* pre = L->next;//pre指向第一个结点，第一个结点不可能重复
LNode* p = pre->next;//p是遍历指针
while (p != null)
{
if (pre->data = p->data)//找到相同结点
{
pre->next = p->next;//释放相同结点
free(p);
p = pre->next;
}
else
{
pre = p;//如果结点不相同，指针同步向后移动
p = p->next;
}
}
}
//另一种写法
void Del_same(LinkList& L) {
LNode* p = L->next, * q;
while (p->next != NULL) {
q = p->next;
if (p->data == q->data) {
p->next = q->next;
free(q);
}
else {
p = p->next;
}
}
}
/*18假设有两个按元素值递增次序排列的线性表，均以单链表的形式存储，
编写算法将这两个单链表归并为一个按照元素次序递减排列的单链表，并要求利用原本的单链表的结点存放归并后的单链表*/
//算法思想：递增变递减，考虑用头插法，用p和q遍历两个链表，比较pq的数值的大小，将小的头插入合并链表，直到其中一条为空，将非空的结点依次以头插法插入合并链表
LinkList Merge(LinkList& A, LinkList& B) {
LNode* PA = A->next, * PB = B->next, * r;
A->next = NULL;//将A的头指针置空
while (PA != NULL && PB != NULL) {
if (PA->data < PB->data) {//如果PA的数值小于PB的数值则头插入合并链表
r = PA->next;//指针r用来防止断链
PA->next = A->next;
A->next = PA;
PA = r;
}
else {
r = PB->next;
PB->next = A->next;
A->next = PB;
PB = r;
}
}
while (PA) {//若A有剩余，则将A中结点全部头插合并链表
r = PA->next;
PA->next = A->next;
A->next = PA;
PA = r;
}
while (PB) {
r = PB->next;
PB->next = A->next;
A->next = PB;
PB = r;
}
return A;
}
/*19设A和B是两个单链表，带头结点，其中元素递增有序，设计一个算法从A和B的公共元素产生单链表C，要求不破坏A和B的结点*/
//算法思想：要求不破坏结点，则需要重新申请结点。
//比较A和B的结点元素数值，将元素值小的指针往后移动，一旦两个相等，则说明是公共值，创建一个新结点值等于此数值，
//用尾插法，并将两个同时向后移动，如果其中一个结束，则算法结束，因为余下的未遍历的结点值中已经不可能有公共元素
LinkList Common(LinkList A, LinkList B)
{
LNode* p = A->next;
LNode* q = B->next;
LinkList C = (LinkList)malloc(sizeof(LNode));
C->next = null;
LNode* r = C;
while (p != null && q != null)
{
if (p->data < q->data) //如果p的数值小，则后移一位
{
p = p->next;
}
else if (p->data > q->data)
{
q = q->next;
}
else if (p->data == q->data)
{
s = (LNode*)malloc(sizeof(LNode));
s->data = p->data; //若相等，申请新结点，将相等的值赋值给新结点，然后将新结点尾插进
r->next = s;
r = s;
p = p->next; //遍历指针同步向后移动一位
q = q->next;
}
}
r->next = null;
return C;
}
/*20已知两个链表A和B分别表示两个集合，其元素递增有序排列，编写函数，求A和B的交集，并存放于A链中*/
//算法思想：A中只能剩交集元素。依次扫描A,B结点，一边扫描结点的data域值，将较小的元素值指针向后移动（移动时释放该空间），
// 若两者相等，就尾插在A链表中，直至遍历到A或者B的表尾，若A中还有剩余，则逐个释放剩余元素（只保留公共空间即可，其他结点释放空间）
LinkList Union(LinkList& A, LinkList& B) {
LNode* p = A->next, * q = B->next;
A->next = NULL;//尾插法的代码
LNode* u, * r = A;//尾插法的代码
while (p != NULL && q != NULL) {//谁小释放谁
if (p->data < q->data) {
u = p;
p = p->next;
free(u);
}
else if (q->data < p->data) {
u = q;
q = q->next;
free(u);
}
else {
r->next = p;//将相等的元素尾插入A
r = p;
p = p->next;
u = q;
q = q->next;
free(u);//释放q结点
}
}
while (p) {// 若A中有剩余，则释放空间
u = p;
p = p->next;
free(u);
}
while (q) {
u = q;
q = q->next;
free(u);
}
r->next = NULL;
free(B);
return A;
}
/*21两个整数序列A=a1,a2,a3…am和B=b1,b2,b3,…bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的连续子集*/
//算法思想：暴力法：用p和q遍历A和B，若pq指针数值域相同，则同步后移；
//若不等，则p重置回初始位然后后移一位（需要pre指针辅助重置标记位），q重置回初始位，再同步移动，
//直到B链表到末尾，表示匹配成功，
//若A链表到尾，而B未到末尾，则匹配失败
bool Son_(LinkList A, LinkList B)
{
LNode* p = A->next;
LNode* q = B->next;
LNode* pre = p;
while (p != null && q != null)
{
//若不等，则p重置回初始位然后后移一位（需要pre指针辅助重置标记位），q重置回初始位
if (p->data != q->data)
{
pre = pre->next;
p = pre;
q = B->next;
}
//相等则同步后移
else
{
p = p->next;
q = q->next;
}
}
if (q == null)//B链表到末尾，表示匹配成功，
return true;
else
return false;
}
//双链表的结点类型定义
typedef struct DNode {
ElemType data;
struct DNode* prior, * next;
}DNode, * DLinklist;
/*22设计一个算法判断带头结点的循环双链表是否对称*/
//算法思想：让p从左往后扫描，q从右向左扫描，直到他们指向同一结点,相遇或者相邻返回1表示是对称双链表
int Symmetry(DLinkList L) {
DNode* p = L->next, * q = L->prior;
while (p != q && p->next != q) {
//p!=q && q->prior != p
//或直接p != q，因为不论奇偶最终都会相遇
if (p->data == q->data) {
p = p->next;
q = q->prior;
}
else {
return 0;
}
}
return 1;
}
/*23有两个循环单链表，链表头指针分别为h1和h2，编写一个函数将链表h2连接到h1之后，要求链接后的链表任保持循环链表的形式*/
//算法思想：找到h1的表尾p和h2的表尾q，将p指向h2，q指向h1
LinkList Link(ListList& h1, ListList& h2)
{
LNode* p = h1->next;
LNode* q = h2->next;
while (p->next != h1)
{
p = p->next;
}
while (q->next != h2)
{
q = q->next;
}
p->next = h2;
q->next = h1;
}
/*24(同T9）设有一个带头结点的循环单链表，其结点值均为正整数，设计一个算法，
反复找出单链表中结点最小的值并输出，然后将该结点从中删除，直到单链表为空位置，再删除表头结点*/
//算法思想：反复找出当前的最小值结点，并删除直至链表为空，释放头结点L
void Del(CLinkList& L)
{
LNode* p, * pre, * minp, * minpre;
while (L->next != L) //遍历整个链表进行最小值删除
{
//反复重置然后找新最小值
pre = L;
p = L->next;
minp = p;
minpre = pre;
while (p != L) //找到最小值结点，输出值并删除
{
if (p->data < minp->data)
{
minp = p;
minpre = pre;
}
else
{
pre = p;
p = p->next;
}
}
printf("%d", minp->data);
minpre->next = minp->next;
free(minp);
}
free(L);
}
/*25设头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred，data和next域外，还有一个访问频度域freq。
在链表被使用前，其值均初始化为0，每当在链表中进行依次Locate（L，x）运算时，
令元素值为x的结点中的freq域的值增加1，并使此链表中结点保持按频度非增（递减）的顺序排列，
同时，最近访问的结点排在频度相同的结点前面，以便使频繁访问的结点总是靠近表头*/
//算法思想：找到含x的结点；使其freq++；取下该x结点；根据freq的大小插入第一个比他大的结点后面（从右往左看）；
//操作：取下结点，插入结点
//非双循环链表的删除
p->next = q->next;
q->next->prior = p;
free(p);
//非双循环链表的插入
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
//注意：最后一步要放在前两步的后面(p->next域不能提前改变)
DLNode Locate(DLNode& L, int x)
{
DLNode* p = L->next;
DLNode* q;
while (p != null && p->data != x) //查找x的结点指针
p = p->next;
if (p == null)
{
printf("不存在%d的结点", x)
exit(0);
}
else //找到了x的值
{
p->freq++; //freq加一
if (p->next != null) //取下该结点
{
p->next->pred = p->pred;
p->pred->next = p->next;
}
//查找p的插入位置
while (q != L && q->freq <= p->freq) //因为q是往前回溯所以终止条件是找到头结点，当q的频度小于p的频度，q继续往前移动
q = q->pred;
//将p插入到合适的位置
p->next = q->next;
q->next->pred = p;//注意q->next域不能提前改变！最后一步要放在前两步的后面
p->pred = q;
q->next = p;
}
return p;
}
/*26已知一个带有表头结点的单链表，结点的结构为data link，假设该链表只给出头指针list，在不改变链表的前提下，设计一个尽可能高效的算法，
查找链表中倒数第k个位置上的结点（k为正整数）若查找成功，算法输出该结点data域的值，并返回1，否则返回0*/
//算法思想：找出倒数第k个位置；
//1.遍历一次链表得到length，第二次遍历length - k得到所求结点（浪费时间）
//2.申请一个顺序表作为辅助空间，将链表存入数组中，然后直接访问第k下标的元素（浪费空间）
//3.先将p移动到第k个位置，p, q一起向后移动，直至p到达表尾，则此时q所指向的结点为所求结点（利用双指针中“间隔一定，同步后移”）
int Search_k(LinkList L, int k)
{
LNode* p = L->next;//pq指向第一个结点
LNode* q = L->next;
int count = 0;
while (p != null)
{
//count<k,只执行p=p->link;即 将p移动到第k个位置
if (count < k)
count++;
else //如果count=k,则q开始和p同步向后移动
q = q->link;
p = p->link; //无论如何，这句都在执行
if (count < k) //k非法则返回0
return 0;
else //找到了则输出q的值
printf("%d", q->data);
return 1;
}
}
/*27（同T14）假定采用带头结点的单链表保存两个单词有相同的后缀时，可享受相同的后缀存储空间，设str1和str2分别指向两个单词的单链表的头结点，
链表结点结构为data,next 请设计一个在时间上尽可能高的算法，找出str1和str2所指向的两个链表共同后缀的起始位置*/
//算法思想：暴力法：双重循环
//遍历一次，间隔一定，同步后移，（双指针问题）
//求出str1和str2所指链表的长度m和n
//用较长的链表长度减去较短的链表长度得到差k，然后长链表先移动k位，
//然后再同步向后移动，直至pq指向同一位置
//求链表的长度
int Len(LNode* head)
{
int len = 0;
LNode* p = head->next;
while (p != null)
{
len++;
p = p->next;
}
return len;
}
LNode Fun_search_common(LinkList str1, Linklist str2)
{
int m = Len(str1);
int n = Len(str2);
LNode* p, * q;
for (p = str1->next; m > n; m--) //若m大，则q先移动m-k个位置
p = p->next;
for (q = str2->next; m < n; n--) //若n大，则q先移动m-k个位置
q = q->next;
//同步向后移动
while (p != null && q != q)
{
p = p->next;
q = q->next;
}
if (p == null)
return 0;
else
return p;
}
/*28用单链表保存m个整数，结点的结构为data link，且data的绝对值是小于等于n的正整数，
现要求设计一个时间复杂度尽可能高效的算法，对于链表中的绝对值相等的结点，仅保留第一次出现的结点，而删除其余绝对值相等的结点。*/
//算法思想：时间上尽可能高效（暗示：以时间换空间），可以考虑开辟一个辅助数组，申请一个n+1辅助空间（0-n）,初始值均为0，
//第一次出现，保留（将该值对应的数组中的下标从0变为1），否则删除结点（绝对值相同）；
//考虑标记数组，将链表中的值转换为数组中的次序，从而达到标记的目的
//用空间换时间
//时间复杂度：O(m);空间复杂度：O(n);
//单链表结点的数据类型定义
typedef struct node {
int data;
struct node* link;
}Node;
void function(LinkList& head, int n) {
Node* p = head->link, * pre = head;
int* C, m;
C = (int*)malloc(sizeof(int) * (n + 1));
for (int i = 0; i <= n; i++) {
C.data[i] = 0;
}
while (p != NULL) {
m = p->data > 0 ? p->data : -(p->data);
if (C.data[m] == 0) {//当第一次出现某个数，将标记数组改为1，保留该数字
C.data[m] = 1;
pre = p;
p = p->link
}
else {
pre->link = p->link;
free(p);
p = pre->link;
}
}
free(C);//释放辅助数组
}
/*29设线性表L=(a1,a2,a3…an)采用带头结点的单链表存储，链表的结点定义如下
Typedef struct node
{
int data;
struct node *next;
}NODE;
设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得出线性表L1=(a1,an,a2,an-1…)。*/
//算法思想：空间O(1)不允许申请额外空间
//将后半段链表逆置，依次插入L的前半段
//1.如何找到单链表的中间结点？设置两个指针，（间隔一定，同步后移），q每次移动两次，p移动一次，则当p到达表尾时，q到达链表的中间位置（同T14）
//2.后半段逆置（头插法）
//3.选择合适位置直接合并
void change(NODE* L)
{
NODE* p, * q, * r, * s;
p = L->next;
q = L->next;
while (q->next != null) //寻找中间结点
{
p = p->next; //p走一步
q = q->next; //q走两步
if (q->next != null)
q = q->next;
}
q = p->next; //p所指的结点为中间结点，q重置为后半段链表的首结点
p->next = null; //断开 后续进行头插法逆置
while (q != null)
{
//将q头插到p之后
r = q->next;
q->next = p ->next;
p->next = q;
q = r;
}
s = L->next; //s指向前半段的第一个数组结点，即插入点
q = p->next; //q指向后半段的第一个数据结点
p->next = null;
while (q != null) //将链表的后半段结点插入到指定的位置
{
//将q依次插入到s之后，类似头插
r = q->next; //防止断链
q->next = s->next;
s->next = q;
s = q->next; //更改s的位置
q = r; //防止断链
}
}
void change_list(Node* h) {
Node* p, * q, * s, * r;
p = q = h;
//找到中间结点
while (q->next != NULL) {
p = p->next;
q = q->next;
if (q->next != NULL) {//当下一步不为虚无，q再走一步
q = q->next;
}
}
//逆置单链表的后半段
q = p->next;
p->next = NULL;
while (q != NULL) {
r = q->next;
q->next = p->next;
p->next = q;
q = r;
}
s = h->next;
//后半链表插入到前半段链表
s = h->next;//s指向前半段第一个结点
q = p->next;//q指向后半段第一个结点
p->next = NULL;
while (q != NULL) {
r = q->next;//防止断链
q->next = s->next;
s->next = q;
s = q->next;//s指向下下个结点，因为插入了一个结点
q = r;//防止断链
}
}
/*30
总结：
1. 头插法
2. 尾插法
3. 逆置法(顺序表和单链表)
4. 归并法(分解)
5. 双指针法(取较小结点合成链表，倒数第K个元素，中间元素)
6. 双循环链表法(插入和删除，注意断链问题)
7. 标志数组
*/