单链表就地逆置算法C语言版
Status Contrary(LinkList L) LinkList p,q;
p=L->next;
L->next=NULL;
while(p!=NULL)
{
q=p;
p=p->next;
q->next=L->next;
L->next=q;
}
return OK;
}
倒置单链表的算法
倒置单链表的算法 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){
单链表算法
1.已知非空带表头结点的线性链表由list指出，链结点的结构为（data，next）， 请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。 delinsert(LinkList list) { p=list->next; //工作指针 pre=list; //最小元素结点前驱 q=p; //最小元素结点 while(p->next!=NULL) { if(p->next->data
数据结构单链表、双链表的逆置算法
数据结构与算法 的课程设计 课程设计题目：数据结构的逆置算法 院系名称：信息技术学院 专业（班级）：计算机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、定义一个撤销链表的算法，这个算法用于删除单链表中的所有节点，使链表为空。
带头结点单链表中数据就地逆置
实验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.调试时出现的问题及解决的方法 在编写按值查找函数时，由于没有处理好指针类型的原因，导致指针无法正常返回，
(数据结构C语言版)顺序表和单链表的逆置
实验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; 什么单链表的逆置 问题描述 设计一个程序，实现单链表的逆置。 一、需求分析 ⑴按程序提示输入并创建一个单链表，带有头结点 ⑵可自定义链表的长度，可自定义链表储存的数据类型，注意更改相应的输入输出方式 ⑶实现单链表的逆置，直观地输出结果 二、概要设计 为实现上述程序功能，需创建以下抽象数据类型： 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.掌握编程工具的使用 2.掌握算法时间效率的事后统计 3.掌握通过计算机编程解决问题的基本方法 二、实验内容和代码 设A ＝（a 1，…，a m ）和B ＝（b 1，…，b n ）均为顺序表，A ’和B ’分别为A 和B 中除去最大共同前缀后的子表（例如，A ＝（x ，y ，y ，z ，x ，z ），B ＝（x ，y ，y ，z ，y ，x ，x ，z ），则两者中最大的共同前缀为（x ，y ，y ，z ），在两表中除去最大共同前缀后的子表分别为A ’＝（x ，z ）和B ’＝（y ，x ，x ，z ））。若A ’＝B ’＝空表，则A ＝B ；若A ’＝空表，而B ’≠空表，或者两者均不为空，且A ’的首元小于B ’的首元，则A < B ，否则A > B 。试写一个比较A 、B 大小的算法（请注意：在算法中，不要破坏原表A 和B ，并且也不一定先求得A ’和B ’才进行比较）。 装订 线 试写一算法，对单链表实现就地（原地）逆置。 装 订 线 装订 线 实验结果与分析 1． 2. 装 订 线 讨论、心得 通过这次实验我较深入学习编程工具VC 6.0的使用，通过模仿老师的程序，在网上查相关资料，从而完成这次实验。通过实验我对数据结构的相关知识特别是链表有了更加深刻的理解和认识。我锻炼自己结合数据结构思想来编写程序的能力，也大大自己增加了对于数据结构相关知识的兴趣。 装 订 线 算法例题 1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。 答： [题目分析]因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时，将链表结点逆置。 LinkedList Union(LinkedList la,lb) ∥la,lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算法将两链表合并成一个按元素值递减次序排列的单链表。 { pa=la->next; pb=lb->next;∥pa，pb分别是链表la和lb的工作指针 la->next=null; ∥la作结果链表的头指针，先将结果链表初始化为空。 while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data) { r=pa->next; ∥将pa 的后继结点暂存于r。 pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=r; ∥恢复pa为当前待比较结点。 } else {r=pb->next; ∥ 将pb 的后继结点暂存于r。 pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=r; ∥恢复pb为当前待比较结点。 } while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null) {r=pb->next; pb->next=la->next; la->next=pb; pb=r; } }∥算法Union结束。 ［算法讨论］上面两链表均不为空的表达式也可简写为while(pa&&pb),两递增有序表合并成递减有序表时，上述算法是边合并边逆置。也可先合并完，再作链表逆置。后者不如前者优化。算法中最后两个while语句，不可能执行两个，只能二者取一，即哪个表尚未到尾，就将其逆置到结果表中，即将剩余结点依次前插入到结果表的头结点后面。 2. 试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。void delete（Linklist &L） 答： [题目分析] 本题要求在单链表中删除最小值结点。单链表中删除结点，为使结点删除后不出现“断链”，应知道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知 #include void show(linklist *head) { linklist *p; p=head->next; while(p!=NULL) { printf("%4d",p->data); p=p->next; } } int main() { linklist *head; head=creatlistr(); reverseLinklist(head); show(head); printf("\n"); system("pause"); return 0; } 经过codeblocks验证，完美运行。 适用于数据结构2.6 习题 更多数据结构————adam单链表的逆置问题
数据结构实验指导书——单链表的基本操作
单链表实验报告
C语言实现单链表逆置
单链表实现就地(原地)逆置和比较线性表AB大小
算法例题
设计一算法,逆置带头结点的动态单链表L