网站开发的技术内容/网络营销的概念及内容

带头结点的双向循环链表L(a1,a2...an)转换为L'(a1,a3,...,an,...,a4,a2)

解题思路：

这道题主要考察结点移动时修改结点信息的逻辑关系，而我需要补的是链表的基本操作代码。。。

现在大致形成一个链表的模板了，以后大概就是在这个基础上补充修改了

不加注释:

#include<stdio.h>
#include<algorithm>
using namespace std;typedef struct Node
{int data;struct Node *left;struct Node *right;
} Node,*List;bool InitList(List &L)
{L=(Node*)malloc(sizeof(Node));if(L==NULL) {printf("内存分配失败!\n");return false;}L->left=NULL;L->right=NULL;return true;
}void CreateList(List &L)
{Node *p;p=L; int a[7]={1,2,3,4,5,6,7};for(int i=0;i<7;i++){Node *q=(Node*)malloc(sizeof(Node));q->data=a[i];q->right=p->right;p->right=q;q->left=p;p=q;}p->right=L;L->left=p;
}void TraversalList(List &L)
{printf("当前该链表遍历序列为:\n");Node *p; p=L->right;while(p!=L){printf("%d ",p->data);p=p->right;}printf("\n");
}void ChangeList(List &L)
{Node *tail=L->left;Node *p=L->right;int num=1;while(p!=tail){if(num%2==0){Node *cur=p;p=p->right;cur->left->right=p;p->left=cur->left;cur->right=tail->right;tail->right->left=cur;tail->right=cur;cur->left=tail;}else{p=p->right;}num++;}
}int main()
{List L;InitList(L);CreateList(L);TraversalList(L);ChangeList(L);TraversalList(L);return 0;
}

加注释：（不写注释自己以后也会不认识...）

#include<stdio.h>
#include<algorithm>
using namespace std;typedef struct Node//定义链表结点结构体 
{int data;struct Node *left;struct Node *right;
} Node,*List;//用Node* q主要强调当前声明的是一个结点指针q指向一个结点,List L强调当前声明的是一个结点指针L指向一个链表头结点(从头结点开始顺着结点的next可以遍历一整个链表) bool InitList(List &L)//初始化链表。传入链表头结点的指针，直接对这个链表进行修改(这里说的对链表进行修改其实还是从头结点开始找到一整个链表) 
{L=(Node*)malloc(sizeof(Node));//向内存申请一块Node大小的区域,让指针L指向这块区域 if(L==NULL) {printf("内存分配失败!\n");return false;}L->left=NULL;//头结点的左右指针域初始为NULL L->right=NULL;return true;//bool类型,可以在调用这个函数的时候用来判断有没有分配成功 
}void CreateList(List &L)//尾插法构建双向循环链表 
{Node *p;//声明一个遍历链表L的指针pp=L; int a[7]={1,2,3,4,5,6,7};for(int i=0;i<7;i++){Node *q=(Node*)malloc(sizeof(Node));//申请一个q结点用来存放新结点的信息,然后把q插入链表 q->data=a[i];//存放信息 q->right=p->right;//这几句是插入链表,考试主要考的是这里,好好盘逻辑 p->right=q;q->left=p;p=q;}p->right=L;//这两句话使双向链表首尾相接 L->left=p;//令最后一个结点的下一个结点是头结点,注意头结点没有存放任何信息,为了方便写代码 
}void TraversalList(List &L)//遍历序列 
{printf("当前该链表遍历序列为:\n");Node *p;//声明一个遍历链表L的指针pp=L->right;//L指向的是链表头结点,头结点没有存放数据只是方便写代码,所以头结点的下一个结点才是链表中存放数据的第一个结点 while(p!=L)//在创建链表时我们令最后一个结点的下一个结点是头结点 {printf("%d ",p->data);p=p->right;}printf("\n");
}void ChangeList(List &L)//调整链表顺序,题目考察部分,好好盘逻辑 
{Node *tail=L->left;//声明一个尾结点指针指向链表最后一个结点 Node *p=L->right;//声明一个遍历链表L的指针pint num=1;//奇偶数计数器 while(p!=tail){if(num%2==0)//第偶数个链表结点,需要调整,考察的就是这里,画画图,好好盘逻辑{Node *cur=p;//cur记录下当前p所指结点,让p接着移动 p=p->right;cur->left->right=p;p->left=cur->left;cur->right=tail->right;tail->right->left=cur;tail->right=cur;cur->left=tail;}else//第奇数个链表结点不需调整 {p=p->right;}num++;}
}int main()
{List L;InitList(L);CreateList(L);TraversalList(L);ChangeList(L);TraversalList(L);return 0;
}

简单的画个图（45min...）

先Mark，明天继续。。。

（坑已填，放上面了）

#include<stdio.h>
#include<algorithm>
using namespace std;typedef struct Node
{int data;struct Node *next;
} Node,*List;//初始化一个单链表 
bool InitList(List &L)//传入地址 
{L=(Node*)malloc(sizeof(Node));//向内存申请一个结点空间,L指向这个结点 if(L==NULL) return false;//内存不足，分配失败 L->next=NULL;//头结点后暂时还没有结点 return true;
}bool isEmpty(List L)//判断单链表是否为空(带头结点) 
{if(L->next==NULL) return true;else return false;
}void createList(List &L)
{Node *p;p=L;int x;for(int i=0;i<5;i++){printf("输入数字:\n");scanf("%d",&x);Node *q=(Node*)malloc(sizeof(Node));printf("***********\n");q->data=x;q->next=p->next;p->next=q;}
}void traversalList(List &L)
{printf("\n到达遍历函数\n");Node *p;p=L->next;while(p!=NULL){printf("%d ",p->data);p=p->next;}
}int main()
{List L;InitList(L);createList(L);traversalList(L);
}

#include<stdio.h>
#include<algorithm>
using namespace std;typedef struct Node
{int data;Node* left;Node* right;
}Node,*List;//使用Node* q和List q作用一样
//使用两种声明方式是为了侧重说明q是结点(指针指向一个结点)还是链表(链表也是指针指向一个结点，通过每个结点的next连起来表示一个链表) 
List head=(Node*)malloc(sizeof(Node));//向内存申请一个新的结点空间，head指向这个结点 void build()//尾插法构建双向链表(还是个循环双链表)
{head->right=NULL;head->left=NULL;int a[7]={1,2,3,4,5,6,7};Node *q;//申请一个指针 q=head;//指向头结点 for(int i=0;i<7;i++){Node* p=(Node*)malloc(sizeof(Node));p->data=a[i];p->right=q->right;q->right=p;p->left=q;q=p; }q->right=head;head->left=q; 
}void change(List head)
{List tail=head->left;int num=1;List p=head->right;while(p!=tail){if(num%2==0){List cur=p;p=p->right;cur->left->right=p;p->left=cur->left;cur->right=tail->right;tail->right->left=cur;tail->right=cur;cur->left=tail;}else{p=p->right;}num++;}
}int main()
{build();//输出循环双链表 List p=head->right;while(p!=head){printf("%d ",p->data);p=p->right;}printf("\n"); change(head);//输出循环双链表p=head->right;while(p!=head){printf("%d ",p->data);p=p->right;}printf("\n");return 0;
}

解题思路2：

（感谢ljt同学提供的思路,祝ljt同学150500985~~）

尾插法建立双向循环链表L存储1,2,3,4,5,6,7,... 

设两个双向循环链表L1,L2和数组a[],b[]

数组a中保存L1中的奇数，数组b中保存L2中的偶数

把数组a中的元素使用尾插法插入L1，把数组b中的元素使用头插法插入L2

把L1和L2合并

L1即为所得

代码如下：

#include<stdio.h>
#include<stdlib.h>typedef struct node
{int data;struct node *left;struct node *right;
}Node,*LinkList;void InitList(LinkList &L)//初始化双向循环链表 
{L=(Node*)malloc(sizeof(Node));L->left=L;L->right=L;
}//void TailInsertList(LinkList &L)//双向循环链表尾插 
//{
//	Node *p=L;
//	int a[7]={1,2,3,4,5,6,7};
//	for(int i=0;i<7;i++)
//	{
//		Node *q=(Node*)malloc(sizeof(Node));
//		q->data=a[i];
//		
//		q->right=p->right;
//		q->left=p;
//		p->right=q;
//		//p->left=q;不要加 
//		p=q;
//	}
//	L->left=p;
//}void TailInsertList(LinkList &L,int a[],int len)//双向循环链表尾插 
{Node *p=L;for(int i=0;i<len;i++){Node *q=(Node*)malloc(sizeof(Node));q->data=a[i];q->right=p->right;q->left=p;p->right=q;//p->left=q;不要加 p=q;}L->left=p;
}void HeadInsertList(LinkList &L,int a[],int len)//双向循环链表头插 
{Node *p;for(int i=0;i<len;i++){Node *q=(Node*)malloc(sizeof(Node));q->data=a[i];q->right=L->right;q->left=L;L->right=q;if(i==0){p=q;	}}L->left=p;
}void PrintList(LinkList L)//遍历输出双向循环链表 
{printf("双向循环链表的序列为:\n");Node *p=L->right;while(p!=L){printf("%d ",p->data);p=p->right;}printf("\n");
}void zhaiList(LinkList L,LinkList &L1,LinkList &L2)//把L中的奇数摘出来保存到L1,把L中的偶数摘出来保存到L2 
{int index=1;Node *p=L->right;int a[100],b[100];int cnt1=0,cnt2=0;while(p!=L){Node *q=(Node*)malloc(sizeof(Node));if(index%2==1)//是奇数,建立a数组 {a[cnt1++]=p->data;}else if(index%2==0)//是偶数,建立b数组  {b[cnt2++]=p->data;}index++;p=p->right;}TailInsertList(L1,a,cnt1);HeadInsertList(L2,b,cnt2);
}void MergeList(LinkList &L1,LinkList &L2)//L2接到L1的后面 
{L1->left->right=L2->right;L2->right->left=L1->left;L2->left->right=L1;L1->left=L2->left; 
}int main()
{LinkList L;InitList(L);LinkList L1;InitList(L1);LinkList L2;InitList(L2);LinkList L3;InitList(L3);int a[7]={1,2,3,4,5,6,7};TailInsertList(L,a,7);PrintList(L);zhaiList(L,L1,L2);PrintList(L1);PrintList(L2);MergeList(L1,L2);PrintList(L1);return 0; 
}