分别用顺序表和单链表作为存储结构,实现将线性表(a0,a1,...an-1)就地逆置的操作,所谓"就地"指辅助空间应为O(1)。
谢谢了
//先定义一个顺序表,例如
typedef struct{
int list[100];
int size;
}L;
//建立...给各个节点赋值
//然后逆置
int temp;//一个辅助空间
for(int i=0;i<L.size/2;i++)
{
temp=L->list[i];
L->list[i]=L->list[L.size-i-1];
L->list[L.size-i-1]=temp;
}
//...
//链表..结构自己写吧 建立好了 给节点赋值
//逆置
void converse(node* head)
{
node *p,*q;
p=head->next;
head->next=NULL;
while(p!=NULL){
q=p;
p=p->next;
q->next=head->next;
head->next=q;
}
这是我在网上看到你说的原题:
1. 顺序表:
要将该表逆置,可以将表中的开始结点与终端结点互换,第二个结点与倒数第二个结点互换,如此反复,就可将整个表逆置了。算法如下:
// 顺序表结构定义同上题
void ReverseList( Seqlist *L)
{
DataType temp ; //设置临时空间用于存放data
int i;
for (i=0;i<=L->length/2;i++)//L->length/2为整除运算
{ temp = L->data[i]; //交换数据
L -> data[ i ] = L -> data[ L -> length-1-i];
L -> data[ L -> length - 1 - i ] = temp;
}
}
2. 链表:
分析:
可以用交换数据的方式来达到逆置的目的。但是由于是单链表,数据的存取不是随机的,因此算法效率太低。可以利用指针改指来达到表逆置的目的。具体情况入下:
(1)当链表为空表或只有一个结点时,该链表的逆置链表与原表相同。
(2)当链表含2个以上结点时,可将该链表处理成只含第一结点的带头结点链表和一个无头结点的包含该链表剩余结点的链表。然后,将该无头结点链表中的所有结点顺着链表指针,由前往后将每个结点依次从无头结点链表中摘下,作为第一个结点插入到带头结点链表中。这样就可以得到逆置的链表。算法是这样的:
结点结构定义如下:
typedef char DataType; //假设结点的数据域类型的字符
typedef struct node{ //结点类型定义
DataType data; //结点的数据域
struct node *next;//结点的指针域
}ListNode;
typedef ListNode *LinkList;
ListNode *p;
LinkList head;
LinkList ReverseList( LinkList head )
{// 将head 所指的单链表(带头结点)逆置
ListNode *p ,*q ;//设置两个临时指针变量
if( head->next && head->next->next)
{ //当链表不是空表或单结点时
p=head->next;
q=p->next;
p -> next=NULL; //将开始结点变成终端结点
while (q)
{ //每次循环将后一个结点变成开始结点
p=q;
q=q->next ;
p->next = head-> next ;
head->next = p;
}
return head;
}
return head; //如是空表或单结点表,直接返回head
}