单链表逆置

时间:2023-05-01 08:06:27 资料 我要投稿
  • 相关推荐

单链表逆置

单链表逆置

题目:创建一个单链表并且逆置单链表

完成日期:

一、需求分析

1、有一个单链表的第一个结点指针为head,编写一个函数将该单链表逆置,即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点。在逆置中不能建立新的单链表.

2、 程序执行的命令包括:

(1)创建第一个单链表;(2)逆位序输入n个元素的值,建立带表头节点的单链线性表L;

(3)逆置链表设置头结点由指向第一个结点改成指向最后一个结点;(4)输出销毁。

3、测试数据

输入: 10 9 8 7 6 5 4 3 2 1

二、概要设计

1、 链表的抽象数据类型定义为:

typedef struct LNode{

int data;

struct LNode* next;

}LNode, *LinkList;

/* 创建一个链表*/

void CreateList_1(LinkList *L, int n)

{

/*逆位序输入n个元素的值,建立带表头节点的单链线性表L*/

int i;

LNode* p = NULL;

*L = (LinkList)malloc(sizeof(LNode));

(*L)->next = NULL; /*先建立一个带头结点的单链表*/

for (i = n; i > 0; --i)

{

p = (LinkList)malloc(sizeof(LNode)); /*生成新结点*/

scanf("%d", &(p->data));

p->next = (*L)->next;

(*L)->next = p;

}

}

2、本程序包含五个模块:

(1)主程序模块:

void main(){

定义头结点;

创建一个链表;

输出;

逆置;

输出;

销毁;

}

(2)逆位序输入n个元素的值,建立带表头节点的单链线性表L

(3)先建立一个带头结点的单链表在生成新结点;

(4)输出链表数据,逆置链表,设置头结点由指向第一个结点改成指向最后一个结点;

(5)把结点1的指针域设置为NULL,最后返回L。

三、详细设计

1、定义头文件

#include

#include

2、 类型定义,类型声明

typedef struct LNode{

int data;

struct LNode* next;

}LNode, *LinkList;

3、创建链表

void CreateList_1(LinkList *L, int n)

{

/*逆位序输入n个元素的值,建立带表头节点的单链线性表L*/

int i;

LNode* p = NULL;

*L = (LinkList)malloc(sizeof(LNode));

(*L)->next = NULL; /*先建立一个带头结点的单链表*/

for (i = n; i > 0; --i)

{

p = (LinkList)malloc(sizeof(LNode)); /*生成新结点*/

scanf("%d", &(p->data));

p->next = (*L)->next;

(*L)->next = p;

}

}

/* 创建一个链表 2*/

LinkList CreateList( int n)

{

/*逆位序输入n个元素的值,建立带表头节点的单链线性表L*/

int i;

LNode* p = NULL, *L=NULL;

L = (LinkList)malloc(sizeof(LNode));

L->next = NULL; /*先建立一个带头结点的单链表*/

for (i = n; i > 0; --i)

{

p = (LinkList)malloc(sizeof(LNode)); /*生成新结点*/

scanf("%d", &(p->data));

p->next = L->next;

L->next = p;

}

return L;

}

/* 输出链表数据 */

void out_list(LinkList L)

{

LinkList p = NULL;

p = L->next;/*这里L是带头结点的链表,所以p指向第一个数据结点*/

while (p != NULL)

{

printf("%d ", p->data);

p = p->next;

}

printf("\n");

}

4、 逆置链表

LinkList reverse_List(LinkList L)

{

LinkList p, q, r;

/* 如果链表为空或者只有一个元素,直接返回该链表*/

if (L->next == NULL || L->next->next==NULL)

{

return L;

}

/*如何不为空,把所有结点的指针域由后指变成前指,如链表1->2->3->4的指针,变成1

/*例如,当前链表为:head->头结点->1->2->3->4->5->^*/

p = L ->next; /*p指向1*/

q = L->next->next;/*q指向2*/

while(q != NULL)

{

r = q->next;/*r指向3,作为一个临时变量,防止指针断链*/

q->next = p;/*开始反向指向前继元素: 14,别忘了这里r指向3,防止3后面的结点丢失*/

p = q;/*处理下一个*/

q = r;

}

/*设置头结点由指向第一个结点改成指向最后一个结点*/

L->next->next = NULL;/*把结点1的指针域设置为NULL*/

L->next = p;

/*最后返回L*/

return L;

}

/*主函数*/

void main()

{

LinkList head = NULL;

int n =10;

/*创建一个链表*/

head=CreateList( n);

/*输出*/

out_list(head);

/*逆置*/

head=reverse_List(head);

/*输出*/

out_list(head);

system("pause");

}

四、调试分析

1、在创建一个单链表并且建立带表头节点的单链线性表L,这样采用指针就能迅速存入数据,再逆位输出数值。

2、在逆置中不能建立新的单链表,这里就要求生成一个新结点。

3、逆置链表时,如果链表为空或者只有一个元素,直接返回该链表。何不为空,把所有结点的指针域由后指变成前指,如链表1->2->3->4的指针,变成1头结点单链表逆置->1->2->3->4->5->^ ,r = q->next; 指向作为一个临时变量,防止指针断链 q->next = p; 开始反向指向前继元素: 14,别忘了这里r指向,防止后面的结点丢失 p = q;处理下一个 。

4、逆置完成:设置头结点由指向第一个结点改成指向最后一个结点,L->next->next = NULL;把结点1的指针域设置为NULL,L->next = p;最后返回L

五、运行结果

六、实验环境

(1) 编程环境:VC6.0++

七、实验体会

通过本次实验我对于C语言,数据结构的相关知识有了更加深刻的理解,对于链表的使用也有了深刻的认识。锻炼了结合数据结构思想来编写程序的能力,也增加了对于学习数据结构相关知识的兴趣。

【单链表逆置】相关文章:

唐代置观制度述略04-27

如何置核能死地而后生04-29

手捧爱,置心尖作文04-17

逆袭的作文07-24

逆市调价?05-01

逆战的作文09-05

顺与逆作文07-21

水环境逆边界逆动态混合控制精确算法04-27

位置作文600位置作文12-16

巧置课堂情境培养学生思维04-29