下载文档原格式
单链表的逆置（头插法，就地逆转）1.头插法，将链表中的每个元素都插到链表头部，进⾏逆转。
void reverse1(Node*head)
{//头插法逆转单链表
Node*p,*q;
p=head->next;
head->next=NULL;
while(p)
{
q=p;
p=p->next;
q->next=head->next;
head->next=q;
}
}
2.就地逆置，将链表中的指针指向改变，最后将head指向链表最后⼀个元素(逆置后的第⼀个)。
void reverse2(Node*head)
{//就地逆转法
Node *p, *s, *t;
p = head; // p开始指向头结点的
s = p->next; // s最开始是指向第⼀个节点的
while ( s->next != null ) // 没有到最后⼀个节点就继续
{
t = s->next; // ⽤t指向s后⾯的⼀个节点
s->next = p; // 把s指向的那个节点想在转换成指向它前⾯的那个节点，这个时候就实现了逆序，⽽且是就地逆序
p = s; // p向后移动到s的位置
s = t; // s向后移动到t的位置，这时候完成了第⼀步的置序，后⾯继续重复之前的动作就OK了
}
head->next = null;
head->next = s;
}。
编写算法：实现带头结点单链表的逆置算法标题：探讨带头结点单链表的逆置算法实现及其应用在计算机科学和算法领域，链表是一种非常重要的数据结构，它能够以一种灵活的方式存储和组织数据。
在链表的操作中，逆置算法是一种常见且有用的操作，它能够将链表的顺序颠倒，为问题的解决提供便利。
本文将从简到繁，由浅入深地探讨带头结点单链表的逆置算法的实现及其应用。
1. 带头结点单链表的定义和特点带头结点单链表是一种特殊的链表结构，它在链表的头部增加了一个额外的结点，这个结点并不存储实际的数据，而是作为头结点来方便链表的操作。
带头结点单链表的特点是可以方便地插入和删除操作，同时也更容易处理空链表的情况。
2. 逆置算法的基本思路在带头结点单链表中，逆置算法的基本思路是从链表的第一个结点开始，依次改变每个结点的指针指向，将整个链表的方向颠倒过来。
在实现逆置算法时，需要注意处理好结点指针的指向关系，以免出现指针丢失或者内存泄露的情况。
3. 逆置算法的具体实现（1）需要判断链表是否为空或只有一个结点，如果是的话，则无需进行逆置操作。
（2）使用三个指针分别表示当前结点、前驱结点和后继结点，通过改变指针的指向来逆置链表。
（3）循环迭代链表，直到当前结点为空，完成链表的逆置操作。
4. 逆置算法的应用带头结点单链表的逆置算法在实际应用中有着广泛的使用场景，例如在字符串操作、图论算法、树算法等方面都能够发挥重要作用。
通过逆置算法，可以方便地实现字符串逆置、图的拓扑排序、二叉树镜像等复杂的数据操作。
带头结点单链表的逆置算法是一种非常重要的链表操作，它能够为问题的解决提供便利。
通过对逆置算法的深入理解和应用，可以为算法的设计和问题的解决提供更多的灵感和思路。
希望本文的内容能够帮助读者更深入地理解带头结点单链表的逆置算法，并在实际应用中发挥重要作用。
个人观点：带头结点单链表的逆置算法是一种非常有趣且实用的算法操作，它能够为链表操作和数据处理提供更多的灵活性和便利性。
数据结构与算法的课程设计课程设计题目：数据结构的逆置算法院系名称：信息技术学院专业（班级）：计算机2班姓名：学号：指导教师：实验内容：分别用一维数组，单链表，双链表实现逆置（一）使用一维数组实现逆置1.需求分析：定义一个一维数组（整型），用for语句实现循环，给数组元素赋值，并将数组元素逆序输出。
2.详细设计：main(){ int a[3],i; /*定义元素个数为3的一维数组*/for(i=0;i<3;i++)scanf("%d",&a[i]);for(i=2;i>=0;i--)printf("%d ",a[i]);getch();}3.运行及调试：4.附录：#include<stdio.h>void main(){ int a[3],i; /*定义一维数组*/for(i=0;i<3;i++)scanf("%d",&a[i]);for(i=2;i>=0;i--)printf("%d ",a[i]);getch();}（二）单链表实现逆置1.需求分析：创建一个单链表并实现逆序输出2.详细设计：定义的所有数据类型，对每个操作写出伪码算法；对主程序和其他模块也都写出伪码算法。
（1）单链表的定义typedef struct node{ int data;/*数据域为整型*/struct node* next; /*定义结点的指针域*/}LinkList;/*数据结点*/（2）头插法建立单链表Tnode *CreatList(){ Tnode *head; /*头指针*/LinkList *p;/*工作指针/int ip;head=(Tnode *)malloc(sizeof(Tnode));head->next=NULL;/*链表开始为空*/printf("please input the number:\n");scanf("%d",&ip); /*向链表中添加元素*/while(ip!=000){ p=(LinkList *)malloc(sizeof(LinkList));/*生成新结点*/ p->data=ip; /*将值赋给新生结点*/p->next=head->next;head->next=p;scanf("%d",&ip);}if(ip==000) /*当输入的数值为000时结束*/printf("\nthe ip is end!\n\n");return head;}（3）读取链表中的数据void ReadList(Tnode *head){ LinkList *p;p=head->next;while(p){ printf("%d ",p->data);p=p->next;}printf("\n");}（4）链表的倒置void ExchangeList(Tnode *head){ LinkList *r,*s;r=head->next;head->next=NULL;while(r){ s=r->next;r->next=head->next;head->next=r;r=s;}3.运行及调试5.附录：/*带头结点的链表建立*/#include<stdio.h>#include<malloc.h>#include<conio.h>typedef struct node /*结点类型定义*/{ int data; /*结点的数据域*/struct node* next; /*结点的指针域*/}LinkList;/*数据结点*/typedef struct{ int length; /**链表的长度/struct node*next; /*结点的指针域*/}Tnode; /*头结点*/Tnode *CreatList()/*头插法建立单链表*/{ Tnode *head;LinkList *p;/*工作指针*/int ip;head=(Tnode *)malloc(sizeof(Tnode));head->next=NULL; /*链表开始为空*/printf("please ip the number:\n");scanf("%d",&ip);while(ip!=000){ p=(LinkList *)malloc(sizeof(LinkList)); /*生成新结点*/ p->data=ip; /*将元素值赋给新生结点p*/p->next=head->next;head->next=p; /*head指向p结点*/scanf("%d",&ip);if(ip==000)printf("\nthe ip is end!\n\n");return head;}void ReadList(Tnode *head) /*读取链表中的数据*/{ LinkList *p;p=head->next;while(p){printf("%d ",p->data);p=p->next;}printf("\n");}void ExchangeList(Tnode *head) /*链表的倒置*/{ LinkList *r,*s;r=head->next;head->next=NULL;while(r){ s=r->next;r->next=head->next;head->next=r;r=s;}}void Readme(){ printf("press 1 to set libiao\n");printf("press 0 to exit\n");printf("-------------------------------------------------------------------------------\n"); }void main(){ Tnode *head;int choice;while(choice){ Readme();scanf("%d",&choice);switch(choice){ case 1:head=CreatList(); /*创建单链表*/printf("the number are:\n\n");ReadList(head);printf("\n");ExchangeList(head); /**逆置后的单链表/printf("the exchange number are:\n\n"); /*打印逆置后的单链表*/ReadList(head); /*读取单链表中的数据*/getch();break;}}}（三）双链表实现逆置1.需求分析：创建一个双链表并实现逆序输出2.详细设计：定义的所有数据类型，对每个操作写出伪码算法；对主程序和其他模块也都写出伪码算法。
单链表反转（4种算法实现）反转链表，又可以称为翻转或逆置链表，它们表达的是同一个意思。
以图 1 所示的链表为例经过反转（翻转、逆置）后，得到的新链表如图 2 所示：通过对比图 1 和图 2 中的链表不难得知，所谓反转链表，就是将链表整体“反过来”，将头变成尾、尾变成头。
那么，如何实现链表的反转呢？常用的实现方案有4 种，这里分别将它们称为迭代反转法、递归反转法、就地逆置法和头插法。
值得一提的是，递归反转法更适用于反转不带头节点的链表；其它3 种方法既能反转不带头节点的链表，也能反转带头节点的链表。
将以图1 所示，即不带头节点的链表为例，给大家详细讲解各算法的实现思想。
1、迭代反转链表该算法的实现思想非常直接，就是从当前链表的首元节点开始，一直遍历至链表的最后一个节点，这期间会逐个改变所遍历到的节点的指针域，另其指向前一个节点。
具体的实现方法也很简单，借助 3 个指针即可。
以图 1 中建立的链表为例，首先我们定义3 个指针并分别命名为beg、mid、end。
它们的初始指向如图 3 所示：在上图的基础上，遍历链表的过程就等价为：3 个指针每次各向后移动一个节点，直至mid 指向链表中最后一个节点（此时end 为NULL）。
需要注意的是，这 3 个指针每移动之前，都需要做一步操作，即改变 mid 所指节点的指针域，另其指向和 beg 相同。
1)在图 3 的基础上，我们先改变 mid 所指节点的指针域指向，另其和 beg 相同（即改为 NULL），然后再将 3 个指针整体各向后移动一个节点。
整个过程如图 4 所示：2)在图4 基础上，先改变mid 所指节点的指针域指向，另其和beg 相同（指向节点 1 ），再将 3 个指针整体各向后移动一个节点。
整个过程如图 5 所示：3)在图5 基础上，先改变mid 所指节点的指针域指向，另其和beg 相同（指向节点 2 ），再将 3 个指针整体各向后移动一个节点。
整个过程如图 6 所示：4)图 6 中，虽然 mid 指向了原链表最后一个节点，但显然整个反转的操作还差一步，即需要最后修改一次mid 所指节点的指针域指向，另其和beg相同（指向节点 3）。
单链表原地逆置算法
单链表原地逆置算法是指将单链表中各节点的顺序逆置，使得原先排在前面的节点现在排在后面，原先排在后面的节点现在排在前面，但是不改变节点的值。
实现此算法需要用到指针操作，具体步骤如下：
1. 定义三个指针分别为 p, q, r，其中 p 指向单链表的头节点，q 指向 p 的下一个节点，r 指向 q 的下一个节点。
2. 将 p 的 next 指针指向 NULL，表示将头节点从链表中删除。
3. 将 q 的 next 指针指向 p，即将原先的头节点连接到 q 的
后面。
4. 将 p 指向 q，q 指向 r，r 指向 q 的下一个节点，继续进
行步骤 2 和 3 直到 r 指向 NULL。
5. 最后将原先的尾节点指向 p，完成单链表的原地逆置。
单链表原地逆置算法的时间复杂度为 O(n)，空间复杂度为 O(1)，是比较高效的一种算法。
- 1 -。
实验二单链表的逆转一、实验要求逆转一个单链表二、数据结构使用了单向链表，链表的节点都使用的是结构体。
三、算法描述1、定义一个结构体struct node{int data;node *next;};定义一个名为node的结构体，为了简便起见，结构体中只包含一个int型数据和指针。
定义四个函数：node *Input() //数据录入函数void Output(node *head) //数据输出函数void Delete(node *h) //节点删除函数node *Reverse(node *head) //链表逆序函数2、建立一条无序链表node *Input()：使用三个指针 p1、p2、head，head指向第一个节点，p2为最后一个节点，p1为新节点。
每次操作时使p2->next=p1，p2=p1。
当输入为-1时使p2->next=0。
由此链表建立完成。
返回新建链表的头指针。
3、单链表的逆转总的思想：1）首先，使p1、p、p2依次指向head开始的前三个node，然后使p1赋给p->next，由此实现了p1和p的逆转；2）再将三个指针依次向后移一个node。
p1的下一个是p，p的下一个是p2，p2的下一个是p2->next；3）重复步骤2和3直至p2->next==nil，node* Reverse(node *head){node *p1,*p,*p2;p1=head;p=p1->next;p1->next=0; //使用3个指针，p1、p和p2。
令p1->next=0if(p->next!=0){p2=p->next; //使p1、p、p2依次指向head开始的前三个nodewhile(p2->next!=0){p->next=p1; //p->next，由此实现了p1和p的逆转p1=p;p=p2;p2=p2->next; //将三个指针依次向后移一个node}p->next=p1; //当p2->next==nil，完成单链表的逆转，只需再将最后两个节点p、p2的指针再分别指向p1、p即可p2->next=p;return p2;}else{p->next=p1;return p;}}四、测试数据输入数据产生无序链表，以-1结束1378-1链表上各结点的数据:1 3 7 8逆转后链表上各结点的数据:8 7 3 1输入四个数据，成功实现逆转。
单链表的就地逆置一．实验目的。
1. 握单链表的一些基本操作和具体的函数定义。
2. 能够利用单链表实现一些具体的功能。
二．实验要求。
1. 预习c语言中结构体的定义与基本操作。
2. 对单链表的每个操作用单独函数实现。
3. 编写完整的程序完成下面的实验内容，并上机运行。
三．实验内容。
构造一个单链表，实现对单链表的逆置。
四．程序实现。
/*对链表就地逆置*/#include#include//链表结构体typedef struct LNode{char data;LNode *next;}*LList;//创建链表void ListCreate(LList &L,int n,char *inputLList p;int i;L=(LNode *malloc(sizeof(LNode; L->next=NULL;for(i=n-1;i>=0;i--{p=(LNode *malloc(sizeof(LNode; p->data=input[i];p->next=L->next;L->next=p;}}//输出链表void ListOutput(LList &L{LList p;p=L->next;while(p{printf("%c ",p->data;p=p->next;}printf("\n";}//逆置bool ListInverse(LList &LLList p,q,r;p=L->next;if(!p return false;L->next=NULL;while(p{r=p->next;p->next=L->next;L->next=p;p=r;}return true;}//主程序int main({LList L;char *input;int NumOfMem;printf("首先创建单链表\n\n请输入单链表中元素个数："; scanf("%d",&NumOfMem;getchar(;//错误处理while(NumOfMem<=0|NumOfMem>=65535printf("\n请输入合适的单链表中元素个数！\n"; scanf("%d",&NumOfMem;getchar(;}input=(char *malloc(NumOfMem*sizeof(char;printf("\n请输入单链表中的元素，按Enter键结束\n"; gets(input;//错误处理if(input[0]=='\0'{printf("空表！\n\n";return 0;}ListCreate(L,NumOfMem,input;printf("\n原链表为：\n";ListOutput(L;if(ListInverse(L{printf("逆置后\n";ListOutput(L;printf("\n";}elseprintf("空表！\n\n"; return 0;}程序截图五．实验心得。
