网页制作基础教程黄洪杰,网站推广优化排名公司,温岭建设网站,忠益网站建设【问题描述】试实现线性表的就地逆置算法#xff0c;即在原表的存储空间将线性表#xff08;a1,a2,a3....an#xff09;逆置为#xff08;an...a3,a2,a1#xff09;. [分析]就地逆置就是不需要额外申请结点空间#xff0c;只需要利用原来的表中的结点空间。若对顺序表中的…【问题描述】试实现线性表的就地逆置算法即在原表的存储空间将线性表a1,a2,a3....an逆置为an...a3,a2,a1. [分析]就地逆置就是不需要额外申请结点空间只需要利用原来的表中的结点空间。若对顺序表中的元素进行逆置可 以借助“交换”前后相应元素的方法实现但是对于单链表就不能“交换”时间复杂度就会达到O(n^2)。 【思想】逆置后的单链表初始化为空表表中的结点不是新生成的而是从原链表中依次“删除”再逐个以头插法放置到逆置表中如此循环直至原链表为空表止。 #include stdio.h
#include stdlib.h
#define ElemType char
typedef struct Node /*结点类型定义*/
{ ElemType data;struct Node * next;
}Node, *LinkList; /* LinkList为结构指针类型*/LinkList CreateFromTail()
/*通过键盘输入表中元素值利用尾插法建单链表,并返回该单链表头指针L*/
{ LinkList L;Node *r, *s;char c;int flag 1; /*设置一个标志初值为1当输入$时flag为0建表结束*/L(Node * )malloc(sizeof(Node)); L-nextNULL; /*为头结点分配存储空间建立空的单链表L*/rL; /*r指针动态指向链表的当前表尾以便于做尾插入其初值指向头结点*/while(flag) /*循环输入表中元素值将建立新结点s插入表尾*/{cgetchar();if(c!$){s(Node*)malloc(sizeof(Node));s-datac;r-nexts;rs;}else{flag0;r-nextNULL; /*将最后一个结点的next链域置为空表示链表的结束*/}} return L;
} void ReverseList(LinkList L)
{ Node *p,*q;pL-next;L-nextNULL;while(p!NULL){ qp-next; /*q指针保留p-next得值*/p-nextL-next;L-nextp; /*将p结点头插入到单链表L中*/pq; /*p指向下一个要插入的结点*/}
}int main()
{LinkList l;Node *p;printf(用尾插法建立单链表,请输入链表数据,以$结束!\n);l CreateFromTail();printf(输入的单链表为:\n);p l-next;while(p!NULL){printf(%c\n,p-data);pp-next;}ReverseList(l);printf(逆置后的单链表为:\n);p l-next;while(p!NULL){printf(%c ,p-data);pp-next;}printf(\n);return 0;
}
