Question

求教几个数据结构算法题的解法

1.试写算法让一个带头结点的单链表逆置，如L=(b1,b2,...,bn)逆置为L2=(bn,bn-1,...,b2,b1)
2.设n个元素的线性表存储在一维数组x[1,...,m]的前n个位置，试写算法，完成在第i个位置插入一个元素x或删除一个元素i
3.设算法将一个带头结点的单循环列表分解为两个列表，要求分解后的一个链表为原链表的奇数结点，另一个链表为原链表的偶数结点。
答好了还有附加分。

Answer 1

各题详细的程序代码如下:(算法及完整的程序)
保存代码时,以.C为后缀名.用VC6.0编译
第1题：
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
typedef struct node
{
int data;
struct node *next;
}node;
node *headLink;/*链表表头指针*/
/*以下是函数声明*/

void CreateHeadLink(void);
node *MallocNode(void);
void GetInformation(node *t);
void OutputInformation(void);
void InsertOneNode(node *t);
void DesplayOneNode(node *p);
void ReverseLink(node *head);/*实现链表倒序功能,其它函数用于测试*/
/*主函数*/
void main()
{
int i;
node *p;
CreateHeadLink();
for(i=0;i<5;i++)
{
p=MallocNode();/*先申请一个新结点*/
GetInformation(p);/*要求用户输入信息到新结点中*/
InsertOneNode(p);/*将新结点加到链表中*/
}
printf("没有倒序前：\n");
OutputInformation();
ReverseLink(headLink);/*调用倒序函数*/
printf("\n倒序后：\n");
OutputInformation();
getch();
}

/************************************
函数功能：建立链表表头
************************************/
void CreateHeadLink(void)
{
node *p;
p=(node*)malloc(sizeof(node));
headLink=p;
p->next=NULL;
}
/************************************
函数功能：申请一个新结点，并将其初始化
************************************/
node *MallocNode(void)
{
node *p;
p=(node*)malloc(sizeof(node));
if(p==NULL)
return NULL;
p->data=0;
p->next=NULL;
return p;
}
/************************************
函数功能：取得用户输入的数据信息
************************************/
void GetInformation(node *t)
{

printf("请输入一个整数：\n");
scanf("%d",&(t->data));
}
/************************************
函数功能：在链表的结尾处增加一个结点
************************************/
void InsertOneNode(node *t)
{
node *p;
p=headLink;
while(p->next)
{
p=p->next;
}
p->next=t;
}

/************************************
函数功能：输出一个结点的信息
************************************/
void DesplayOneNode(node *t)
{
printf("%d\t",t->data);
}

/************************************
函数功能：显示所有数据的信息
************************************/
void OutputInformation(void)
{
node *p;
p=headLink->next;
printf("数据:\t");
while(p)
{
DesplayOneNode(p);
p=p->next;
}
}
void ReverseLink(node *head)/*实现链表倒序*/
{
node *s,*p;
p=head->next;
head->next=NULL;
while(p)
{
s=p;
p=p->next;
s->next=head->next;
head->next=s;
}
}

第2题：
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<process.h>

#define MAX 50

int test[MAX];/*定义一个线性表*/
int offset=0;
void InserOrData(int flag,int i,int *p);
void Menu(void);
/*主函数*/
void main()
{
for(offset=0;offset<6;offset++)
test[offset]=offset;
Menu();
getch();
}
/*根据flag来执行相应的操作*/
void InserOrData(int flag,int i,int *p)
{
int n;
if(flag==1)/*删除*/
{
for(n=i;i<MAX-1;i++)
*(p+i)=*(p+i+1);
offset--;
}
else if(flag==2)/*插入*/
{
for(n=MAX-1;n>i;n--)
*(p+n)=*(p+n-1);
printf("请输入插入的元素值:\n");
scanf("%d",(p+i));
offset++;
}
}
/*用于显示菜单*/
void Menu(void)
{
int choose;
int in;
printf("\n1-->删除操作\t2-->插入操作\t3-->显示线性表数据\t4-->退出\n");
scanf("%d",&choose);
switch(choose)
{
case 1:
printf("请输入删除位置：\n");
scanf("%d",&in);
InserOrData(choose,in,test);
break;
case 2:
printf("请输入插入位置：\n");
scanf("%d",&in);
InserOrData(choose,in,test);
break;
case 3:
for(in=0;in<offset;in++)
printf("%d ",test[in]);
break;
case 4:
exit(0);
break;
default:
break;
}
Menu();
}

第3题：
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
typedef struct node
{
int data;
struct node *next;
}node;
node *headLink;/*链表表头指针*/

/*以下是函数声明*/
void CreateHeadLink(void);
node *MallocNode(void);
void GetInformation(node *t);
void OutputInformation(node *head);
void InsertOneNode(node *t);
void InsertOneNode2(node *head,node *t);
void DesplayOneNode(node *p);
void ReverseLink(node *headOdd,node *headEven,node *head);/*实现链表分为奇偶两个链表(其它函数是为测试用的)*/

/*主函数*/
void main()
{
int i;
node *p;
node *headOdd,*headEven;
CreateHeadLink();
for(i=0;i<9;i++)
{
p=MallocNode();/*先申请一个新结点*/
GetInformation(p);/*要求用户输入信息到新结点中*/
InsertOneNode(p);/*将新结点加到链表中*/
}
printf("原来的链表数据：\n");
OutputInformation(headLink);
headOdd=MallocNode();
headEven=MallocNode();
ReverseLink(headOdd,headEven,headLink);
printf("\n分解后的奇数链表：\n");
OutputInformation(headOdd);
printf("\n分解后的偶数链表：\n");
OutputInformation(headEven);
getch();
}

/************************************
函数功能：建立链表表头
************************************/
void CreateHeadLink(void)
{
node *p;
p=(node*)malloc(sizeof(node));
headLink=p;
p->next=NULL;
}
/************************************
函数功能：申请一个新结点，并将其初始化
************************************/
node *MallocNode(void)
{
node *p;
p=(node*)malloc(sizeof(node));
if(p==NULL)
return NULL;
p->data=0;
p->next=NULL;
return p;
}
/************************************
函数功能：取得用户输入的结点数据
************************************/
void GetInformation(node *t)
{

printf("请输入一个整数：\n");
scanf("%d",&(t->data));
}
/************************************
函数功能：在链表的结尾处增加一个结点
************************************/
void InsertOneNode(node *t)
{
node *p;
p=headLink;
while(p->next)
{
p=p->next;
}
p->next=t;
}
/************************************
函数功能：在链表head的结尾处增加一个结点
************************************/
void InsertOneNode2(node *head,node *t)
{
node *p;
p=head;
while(p->next)
{
p=p->next;
}
p->next=t;
}
/************************************
函数功能：输出一个结点的信息
************************************/
void DesplayOneNode(node *t)
{
printf("%d\t",t->data);
}

/************************************
函数功能：显示所有数据的信息
************************************/
void OutputInformation(node *head)
{
node *p;
p=head->next;
printf("数据:\t");
while(p)
{
DesplayOneNode(p);
p=p->next;
}
}
/*实现链表分为奇偶两个链表*/
void ReverseLink(node *headOdd,node *headEven,node *head)
{
node *p,*q;
int count=0;
p=head->next;
while(p)
{
count++;
q=MallocNode();/*先申请一个新结点*/
q->data=p->data;
if(count%2==0)
{
InsertOneNode2(headEven,q);
}
else
{
InsertOneNode2(headOdd,q);
}
p=p->next;
}
}

Answer 2

1.试写算法让一个带头结点的单链表逆置，如L=(b1,b2,...,bn)逆置为L2=(bn,bn-1,...,b2,b1)
解法如下：
假定head为头节点，
p=head->next;
if(p==NULL) return;
pnow = NULL;
while(p->next)
{
q = p->next;
p->next = pnow;
pnow = p;
p = q;
}
p->next = pnow;
head->next = p;