单链表的逆置的实现
单链表的逆置的实现:
(1)算法
struct link
{
int data;
struct link *next;
};
link reverse(link x)
{
if( NULL==x )
return NULL;
link t=NULL;
link r=NULL, y=x; //(0)
while(y!=NULL)
{
t = y->next; //(1)
y->next = r; //(2)
r = y; //(3)
y = t; //(4)
}
return r; //返回逆置后的链表
}
(二)原理
(0)(1)(2)(3)(4)分别对应以上程序的各序号
第一次while循环
-------------------------------------------
(0) r=NULL, y=x
r=NULL a ---> b ---> c ---> d --> NULL |(0)
y
-------------------------------------------
(1) t =y->next
r=NULL a ---> b ---> c ---> d --> NULL |(0) | (1)
y t
--------------------------------------------
(2) y->next = r
a ---> NULL
b --->
c --->
d --> NULL |(0) (2) | | (1)
y r t
---------------------------------------------
(3) r = y
a ---> NULL
b --->
c --->
d --> NULL |(0) (2) | (1)
y t
|(3)
r
---------------------------------------------
(4) y = t
a ---> NULL
b --->
c --->
d --> NULL |(0) (2) | (1)
| t
|(3) | (4)
r y
第二次while循环(并对上面进行整理)
---------------------------------------------
(1) t = y->next
a ---> NULL
b --->
c --->
d --> NULL | | |(1)
r y t
---------------------------------------------
(2) y->next = r
b ---> a ---> NULL
c --->
d --> NULL
| (2) | |(1)
y r t
---------------------------------------------
(3) r = y
b ---> a ---> NULL
c --->
d --> NULL | (2) |(1)
y t
| (3)
r
---------------------------------------------
(4) y = t
b ---> a ---> NULL
c --->
d --> NULL | (2) |(1)
| t
| (3) |(4)
r y
第三个循环(并对上面的进行整理)
---------------------------------------------
(1) t = y->next
b ---> a ---> NULL
c --->
d --> NULL | | |(1)
r y t
以后的与第二次循环同, 最终可得:
d ---> c ---> b ---> a ---> NULL
倒置单链表的算法
倒置单链表的算法 void pur_LinkList(LinkList H) { LNode *p,*q,*r; p=H->next; /*p指向第一个结点*/ if(p==NULL) return; while (p->next) { q=p; while (q->next) /* 从*p的后继开始找重复结点*/ { if (q->next->data==p->data) { r=q->next; /*找到重复结点,用r指向,删除*r */ q->next=r->next; free(r); } /*if*/ else q=q->next; } /*while(q->next)*/ p=p->next; /*p指向下一个,继续*/ } /*while(p->next)*/ } ―――――――――――――――――――――――――――――――――――――status LinkListReverse(LinkList L) /*对单链表中的元素倒置*/ { int a[N] ,i=0,count=0; LinkList Lb; Node *p,*q; p=L->next; while(p!=NULL) { a[i++]=p->data; p=p->next; count++; } ―――――――――――――――――――――――――――――――― 2.21 void reverse(SqList &A)//顺序表的就地逆置 { for(i=1,j=A.length;i
数据结构C语言版顺序表和单链表的逆置
数据结构C语言版顺序表和单链表的逆置 公司标准化编码 [QQX96QT-XQQB89Q8-NQQJ6Q8-MQM9N]
实验1-1 顺序表的逆置操作 程序原码 #include<> // 创建顺序表，确定元素个数，插入各个元素，逆置列表。#include<> #include<> #define max_list_size 100 //定义给顺序表分配空间大小 typedef struct{ int *elem; int length; }list_node; //指向顺序表首地址的结构体单元 list_node L; //这里使用了全局变量，在所有的函数里可以随意修改其值int list[max_list_size]; void init(); // 初始化操作 void inversion(); // 倒置部分
void creat(); // 建表部分 void display(); // 显示部分 //*************主函数****************** int main() { init(); creat(); printf("\n您输入的顺序表的结点数: \n"); display(); inversion(); printf("\n倒置顺序表的结点数: \n"); display(); } //*************初始化操作分配空间******************
void init() { = (int *) malloc (max_list_size * sizeof(int) ); if (! { printf("顺序表已满"); exit(-1); } = 0; } //*************以下为建表部分****************** void creat(){ int a, b, i; printf("请输入顺序表的结点数: "); scanf("%d", &a); if(a<=0){
(数据结构C语言版)顺序表和单链表的逆置
} 实验 1-1 顺序表的逆置操作 程序原码 // 创建顺序表，确定元素个数，插入各个元素，逆置列表。 #include
单链表算法
1.已知非空带表头结点的线性链表由list指出，链结点的结构为（data，next）， 请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。 delinsert(LinkList list) { p=list->next; //工作指针 pre=list; //最小元素结点前驱 q=p; //最小元素结点 while(p->next!=NULL) { if(p->next->data
数据结构8581线性链表逆置
#include
} printf("\n"); return OK; } int LoadLink_L2(LinkList &L) { LinkList p=L->next,t,q; q=p; if(p==NULL)printf("The List is empty!"); else { printf("The turned List is:"); while(p->next!=NULL) { t=p; p=p->next; } printf("%d ",p->data); while(q!=NULL) { p=L->next; while(p->next!=NULL) { if(p->next==t) { printf("%d ",t->data); t=p; break; } p=p->next; } q=q->next; } printf("%d ",L->next->data); } printf("\n"); return OK; } int main() { LinkList T1;
数据结构单链表、双链表的逆置算法
数据结构与算法 的课程设计 课程设计题目：数据结构的逆置算法 院系名称：信息技术学院 专业（班级）：计算机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
{ 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;
单链表实验报告
数据结构 课程设计 设计题目：单链表 专业班级：11软会四班 指导教师：吉宝玉 日期：2012 目录 一、实验目的 (2) 1、 (2) 2、 (2) 二、实验内容 (3)
三、实验基本要求（软、硬件） (3) 四、算法设计思想 (3) 1、 (3) 2、 (3) 3、 (3) 4、 (3) 5、 (3) 6、 (3) 7、 (3) 8、 (3) 五、算法流程图 (4) 六、算法源代码 (4) 七、运行结果 (9) 1、 (9) 2、 (10) 3、 (11) 4、 (11) 5、 (11) 6、 (12) 7、 (12) 8、 (13) 9、 (13) 八、收获及体会 (14) 一、实验目的 1、理解并掌握单链表的结构特点和相关概念； 2、学会单链表的基本操作：建立、插入、删除、查找、 输入、撤销、逆置、求前驱和后继等并实现其算法。
二、实验内容 利用头插建立一个带头结点的单链表，并用算法实现该单链表的插入、删除查找、输出、求前驱和后继、再把此单链表逆置，然后在屏幕上显示每次操作的结果当所有操作完成后能撤销该单链表。 三、实验基本要求（软、硬件） 用VC++6.0软件平台，操作系统：Windows XP 硬件：内存要求：内存大小在256MB，其他配置一般就行。 四、算法设计思想 1、定义一个创建链表的函数，通过该函数可以创建一个链表，并为下面的函数应用做 好准备。 2、定义输出链表的算法，通过对第一步已经定义好的创建链表函数的调用，在这一步 通过调用输出链表的函数算法来实现对链表的输出操作。 3、定义一个遍历查找的算法，通过此算法可以查找到链表中的每一个节点是否存在。 4、定义查找链表的每一个前驱和后继，通过定义这个算法，可以很容易的实现对链表 的前驱和后继的查找工作。 5、定义插入节点的算法，通过定义这个算法，并结合这查找前驱和后继的算法便可以 在连链表的任意位置进行插入一个新节点。 6、定义删除节点的操作，这个算法用于对链表中某个多余节点的删除工作。 7、定义一个逆置单链表的操作，通过定义这个算法，可以逆置输出单链表。 8、定义一个撤销链表的算法，这个算法用于删除单链表中的所有节点，使链表为空。
单链表逆置
#include
带头结点单链表中数据就地逆置
实验3 ：带头结点单链表中数据就地逆置 一、实验目的： 1. 会定义单链表的结点类型； 2. 熟悉对单链表的一些基本操作和具体的函数定义； 3. 了解和掌握单链表的调用格式。 二、实验要求： 1. 认真阅读和掌握实验内容所给的程序，并上机运行； 2. 保存程序运行结果，并结合程序进行分析； 3. 尝试自己调试修改程序并试运行。 三、实验内容： 编写算法实现带头结点单链表的就地逆置，即利用原带头结点单链表的结点空间把数据元素序列逆置。 四、实验程序： #include
converse(slnode*head); main(void) { datatype test[6]={64,6,7,89,12,24}; slnode*head,*p; int n=6,i; sllinitiate(&head); for(i=1;i<=n;i++) sllinsert(head,i,test[i-1]); linlistsort(head); linlistinsert(head,25); converse(head); p=head->next; while(p!=NULL) { printf("%d",p->data); p=p->next; } } sllinitiate(slnode**head) { if((*head=(slnode*)malloc(sizeof(slnode)))==NULL)exit(1); (*head)->next=NULL; } int sllinsert(slnode*head,int i,datatype x) { slnode*p,*q; int j;
单链表原地逆置(头插法)
原地逆置单链表（头插法） /* 原地逆置头插法伪算法 本函数使用的是带头节点的链表 1.将p指针指向有效数据的第二个节点 2.将p指针始终插入到phead后面，第一个有效节点前面，即插入到它俩中间位置，不论第一个有效节点是否被更改，这样就可以完全逆置单链表 3.p和q指针后移，直至移动到最后一个节点，完成插入操作 */ #include
PNODE create_list() { intval; PNODE phead,ptail,s; phead = (PNODE)malloc(sizeof(NODE)); if(phead == NULL) { printf("分配失败，程序终止\n"); exit(-1); } ptail=phead; printf("请输入每个节点的值，以-1结束\n"); scanf("%d",&val); while(val!=-1) { s=(PNODE)malloc(sizeof(NODE)); //新建一个节点 if(s == NULL) { printf("分配失败，程序终止\n"); exit(-1); } s->data = val; //s->next = NULL; ptail->next = s; //链接到节点后面 ptail = ptail->next; //使ptail永远指向最后一个节点 scanf("%d",&val); } ptail->next = NULL; printf("创建成功!\n"); returnphead; } voidtraverse_list(PNODE phead) { PNODE p; if(phead == NULL) { printf("链表为空，请创建链表!\n"); } else { p = phead->next;
单链表实验
实验1 单链表 专业班级学号姓名报告日期 实验类型：●验证性实验○综合性实验○设计性实验 一、实验目的或任务 通过指导学生上机实践，对常用数据结构的基本概念及其不同的实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。 二、实验教学基本要求 1.了解实验目的及实验原理； 2.编写程序，并附上程序代码和结果图； 3.总结在编程过程中遇到的问题、解决办法和收获。 三、实验教学的内容或要求 1.编写函数,实现随机产生或键盘输入一组元素,建立一个带头结点的单链表（无序） 2.编写函数,实现遍历单链表 3.编写函数,实现把单向链表中元素逆置 4.编写函数,建立一个非递减有序单链表 5.编写函数,利用以上算法，建立两个非递减有序单链表,然后合并成一个非递减链表。 6.编写函数,在非递减有序单链表中插入一个元素使链表仍然有序 7.编写函数,实现在非递减有序链表中删除值为x的结点 8.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法 四、实验总结
1.主菜单 2.编写函数,实现随机产生或键盘输入一组元素,建立一个带头结点的单链表（无序） 3.编写函数,实现遍历单链表 4.编写函数,实现把单向链表中元素逆置 5.编写函数,建立一个非递减有序单链表 6.编写函数,利用以上算法，建立两个非递减有序单链表,然后合并成一个非递减链表。
7.编写函数,在非递减有序单链表中插入一个元素使链表仍然有序。 8.编写函数,实现在非递减有序链表中删除值为x的结点 9.退出程序 实验总结： 1.调试时出现的问题及解决的方法 在编写按值查找函数时，由于没有处理好指针类型的原因，导致指针无法正常返回，
单链表基本操作实验
实验2 链表的操作 实验容： 1）基础题：编写链表基本操作函数，链表带有头结点 （1）CreatList_h()//用头插法建立链表 （2）CreateList_t()//用尾插法建立链表 （3）InsertList（）向链表的指定位置插入元素 （4）DeleteList（）删除链表中指定元素值 （5）FindList（）查找链表中的元素 （6）OutputList（）输出链表中元素 2）提高题： （1）将一个头节点指针为heada的单链表A分解成两个单链表A和B，其头结点指针分别为heada和headb，使得A表中含有原单链表A中序号为奇数的元素，B表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。 （2）将一个单链表就地逆置。 即原表（a1，a2，。。。。。。 an），逆置后新表（an，an-1，。。。。。。。a1） /* 程序功能 :单链表基本功能操作 编程者 :天啸 日期 :2016-04-14 版本号 :3.0 */ #include { printf("请输入第%d个数:\n",i+1); scanf("%d",&goal); p = (struct List*)malloc(sizeof(struct List)); p -> data = goal; p -> next = L->next; //将L指向的地址赋值给p; L -> next = p; } } void CreateList_t(List *L) //尾插法 { int i; int n; int goal; List *p; List *q=L; printf("请输入数据的个数:\n"); scanf("%d",&n); for (i=0;i 实验1-1 顺序表的逆置操作 程序原码 #include 单链表的逆置 问题描述 设计一个程序，实现单链表的逆置。 一、需求分析 ⑴按程序提示输入并创建一个单链表，带有头结点 ⑵可自定义链表的长度，可自定义链表储存的数据类型，注意更改相应的输入输出方式 ⑶实现单链表的逆置，直观地输出结果 二、概要设计 为实现上述程序功能，需创建以下抽象数据类型： ADT LinkList { 数据对象：D={ai|ai∈（0，1，…，9），i=0,1，2，…，n，n≥0} 数据关系：R={ typedef int ElemType;//元素类型 typedef struct node{ ElemType data; struct node *next; }Node,*LinkList;//节点类型、 2.基本操作和所需调用的函数 //初始化一个链表 Status InitList(LinkList *L) { *L=(LinkList)malloc(sizeof(node)); if(!(*L)) exit(-2);//内存分配失败 (*L)->next=NULL; return 1; } //在初始化的基础上按顺序创建一个链表 Status CreatList(LinkList L,int n) { LinkList p=L; int i; for(i=0;i 单链表的逆置的实现: (1)算法 struct link { int data; struct link *next; }; link reverse(link x) { if( NULL==x ) return NULL; link t=NULL; link r=NULL, y=x; //(0) while(y!=NULL) { t = y->next; //(1) y->next = r; //(2) r = y; //(3) y = t; //(4) } return r; //返回逆置后的链表 } (二)原理 (0)(1)(2)(3)(4)分别对应以上程序的各序号 第一次while循环 ------------------------------------------- (0) r=NULL, y=x r=NULL a ---> b ---> c ---> d --> NULL |(0) y ------------------------------------------- (1) t =y->next r=NULL a ---> b ---> c ---> d --> NULL |(0) | (1) y t -------------------------------------------- (2) y->next = r a ---> NULL b ---> c ---> d --> NULL |(0) (2) | | (1) y r t --------------------------------------------- (3) r = y a ---> NULL b ---> c ---> d --> NULL |(0) (2) | (1) y t |(3) r --------------------------------------------- (4) y = t a ---> NULL b ---> c ---> d --> NULL |(0) (2) | (1) | t |(3) | (4) r y 第二次while循环(并对上面进行整理) --------------------------------------------- (1) t = y->next a ---> NULL b ---> c ---> d --> NULL | | |(1) r y t --------------------------------------------- (2) y->next = r b ---> a ---> NULL c ---> d --> NULL | (2) | |(1) y r t --------------------------------------------- #include } void oppverse(LinkList *&L) //逆置所有结果、点{ LinkList *p=L,*q,*s; while(p->next!=NULL) { s=p->next; p=p->next; } p=L; q=L->next; ElemType temp; while(p->next!=s) { temp=s->data; s->data=q->data; q->data=temp; q=q->next; while(p->next!=s) { p=p->next; } s=p; p=q; } } void main() { LinkList *L; Initial(L); Input(L); DisplayLink(L); oppverse(L); cout<<"逆置后的单链表为："< 一、单链表逆置问题 1)实验问题：用函数create()、disp(nodetype *h)、invert(nodetype *h) 实现单链表的逆置 问题。 2)基本思想：在遍历原表的时候，从原表的第一个结点开始，将各个结点的指针逆转， 最后修改头结点的指针域，使其指向原表的最后一个结点，即新表的第一个结点。 3)算法流程图： 4)测试数据及结果运行图： 5)源代码： #include 实验02单链表的基本操作 实验学时：2学时 实验类型：上机 背景知识：单链表的插入、删除及应用。 目的要求： 1．掌握单链表的存储特点及其实现。 2．掌握单链表的插入、删除算法及其应用算法的程序实现。 实验内容： 编写一个完整的程序，实现单链表的生成、插入、删除、输出等基本操作。 （1）随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。 （2）计算单链表的长度，遍历单链表。 （3）把单链表中的元素逆置（不允许申请新的结点空间）。 （4）在单链表中删除所有值为偶数的元素结点。 （5）编写在非递减有序单链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单链表。 （6）* 利用算法5建立两个非递减有序单链表，然后合并成一个非递增有序链表。 （7）* 利用算法5建立两个非递减有序单链表，然后合并成一个非递减有序链表。 （8）* 利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。 （9）*采用单链表实现一元多项式的存储并实现两个多项式相加并输出结果。 （10）在主函数中设计一个简单的菜单，分别调试上述算法。 （11）*综合训练： 1）利用链表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等，并能够实现将数据存储到文件中） 2）约瑟夫环问题：设有n个人围坐在圆桌周围，从某个位置开始编号为1，2，3，…，n，坐在编号为1的位置上的人从1开始报数，数到m的人便出列；下一个（第m+1个）人又从1开始报数，数到m的人便是第二个出列的人；如此重复下去，直到最后一个人出列为止，得到一个出列的编号顺序。例如，当n=8，m=4时，若从第一个位置数起，则出列的次序为4，8，5，2，1，3，7，6。试编写程序确定出列的顺序。要求用不带头结点的单向循环链表作为存储结构模拟此过程，按照出列顺序打印出个人编号。 实验说明： 1．类型定义 typedefintElemType; //元素类型 typedefstructnode { ElemType data; 单链表练习实验 实验目的：熟练掌握单的基本操作及简单应用。 实验内容： ?实验题目 1 .书上习题2.6中的第5题。(单链表的逆置） 2.书上习题2.6中第6题。（删除已知值k的结点） ?程序代码 #include { struct node *p; int cnt=0; for (p=head->next;p!=NULL;p=p->next) cnt++; return cnt; } void append(ELEMTYPE item) {struct node *p; p=(struct node *)malloc(sizeof(struct node)); if (!p) exit(0); p->element=item; p->next=tail->next; tail->next=p; tail=p; } struct node *search(ELEMTYPE item) { struct node *p; p=head->next; while(p!=NULL) { if (p->element==item) return p; else p=p->next; } return NULL; } void insert_x(ELEMTYPE x)//将元素x按序插入到单链表函数{struct node *p,*q,*item; item=(struct node *)malloc(sizeof(struct node));//创建结点 if(!item) exit(0); item->element=x; p=head->next; while(p)//从第一个结点开始比较与x的大小 {if(p->element>item->element) {q=head; while(q->next!=p)//求前驱 q=q->next; item->next=p;//实现插入操作 q->next=item;(数据结构C语言版)顺序表和单链表的逆置
单链表逆置
单链表的逆置的实现
把一个带头结点的单链表所有数据结点逆置
单链表的逆置问题
数据结构实验指导书——单链表的基本操作
单链表实验报告