实验二 单向链表的操作

实验2 链表的应用一、实验目的●了解并掌握链表的概念与定义●能够实现并运用链表●熟练运用链表的基本操作二、实验环境●个人计算机一台，CPU主频1GHz以上，1GB以上内存，2GB以上硬盘剩余空间。

●Windows2000、Windows XP或Win 7操作系统●Code::Blocks(版本12.11或近似版本，英文版)，或VC++ 6.0三、实验内容1 基本部分(必做)1．单向链表的创建与操作设单向链表中节点的数据域的数据类型为整型，编写函数实现以下操作：（1）实现单向链表的创建（包括初始化）与输出操作，节点的个数及节点的数据由用户输入。

（源代码：ds3-1.c）（2）查找给定的单链表中的第i个节点，并将其地址返回。

若不存在第i 个节点，则返回空地址。

（源代码：ds3-2.c）（3）查找给定的单链表中值为n的节点，并将其地址返回。

若不存在值为n的节点，则返回空地址。

同时，还应通过参数传回该节点的序号。

（源代码：ds3-3.c）（4）删除给定的单链表中的第i个节点，成功返回1，失败返回0。

（源代码：ds3-4.c）（5）删除给定的单链表中值为n的节点，成功返回1，失败返回0。

（源代码：ds3-5.c）（6）在给定的单链表的第i位上插入值为n的节点。

（源代码：ds3-6.c）（7）在给定单链表的值为m的节点的前面插入一个值为n的节点。

（源代码：ds3-7.c）2．双向循环链表的创建与操作设双向链表中节点的数据域的数据类型为整型，编写函数实现以下操作：（1）实现双向循环链表的创建（包括初始化）与输出操作，节点的个数及节点的数据可以在程序中直接确定。

（源代码：ds4-1.c）（2）删除给定的双向循环链表中值为n的节点，成功返回1，失败返回0。

（源代码：ds4-2.c）（3）在给定的双向循环链表中的第i位上插入值为n的节点，成功返回1，失败返回0。

（源代码：ds4-3.c）2 提高部分(选做)已知链表A和B中节点的值都按照从小到大的顺序排序，且任何两个节点的值都不相同。

实验二链式存储结构----单向链表的有关操作
一、实验目的
了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法。

二、实验内容
建立一个学生成绩信息（包括学号、姓名、成绩）的单向链表，学生记录按学号由小到大顺序排列，要求实现对成绩信息的插入、修改、删除和遍历操作。

三、实验要求
1. 根据实验内容编程，上机调试、得出正确的运行程序。

2. 写出实验报告（包括源程序和运行结果）。

四、实验学时
2学时。

五、实验步骤：
1．进入编程环境，建立一新文件；
2．类型定义
#include <stdio.h>
struct stud_node{ /*链表结点类型*/
char num[10];
char name[20];
int score;
struct stud_node *next;
}LNode,*LinkList;
3．为了算法实现简单，最好采用带头结点的单向链表。

4. 编译运行程序，观察运行情况和输出结果。

实验2链表的基本操作一、需求分析1，初始化链表2，调用插入函数建立一个链表3，链表的插入和删除4，链表元素的查找4，将链表分为奇链表和偶链表5，链表的逆置二、概要设计1.基础题1)编写链表基本操作函数typedefstruct list{Int data;Struct list* next}LIST;LIST* InitList() //初始化LIST* InsertList(LIST * L,int item,int re) //向链表指定位置插入元素LIST* InsertOrderList(LIST *L,int item) //向有序链表指定位置插入元素void FindList(LIST*L, int item)//查找链表中的元素void display(LIST *L)//显示链表void divide(LIST* La, LIST *Lb)//拆分链表LIST * turn(LIST *L)//转置链表2)调用上述函数实现下列操作，操作步骤如下。

A.初始化链表B.调用插入函数建立一个链表C.在链表中寻找指定的元素D.在链表中删除指定值的元素E.遍历并输出链表注意每完成一个步骤，必须及时输出顺序表元素，便于观察操作结果2.提高题a)将一个首结点指针为a的单链表A分解成两个单链表A和B，其首结点指针分别为a，b，使得链表A中含有原链表A中序号为奇数的元素，而链表B中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。

解题思路将单链表A中含有序号为偶数的元素删除，并在删除时把这些结点链接起来构成单链表B即可。

b)将链接存储线性表逆置，即最后一个结点变成第一个结点原来倒数第二个结点变成第二个结点，如此等等。

解题思路依次遍历源链表，将每个元素依次赋给一个新链表并将新链表从后到前连接。

3.主函数void main(){LIST *L1,*L2,*L3;int i;L1=InitList();printf("创建链表L1:\n");for(i=1;i<=5;i++){L1=InsertList(L1,i*2,i);}display(L1);for(i=1;i<=9;i+=4){printf("在L1的%d位置插入3:\n",i);L1=InsertList(L1,3,i);display(L1);}//有序表L2 = InitList();printf("\n有序表实验:\n");printf("创建链表L2:\n");for (i = 1; i <= 5; i++){L2 = InsertList(L2, i * 2, i); }display(L2);for (i = 1; i <= 13; i +=6 ){printf("插入%d:\n",i);L2 = InsertOrderList(L2,i);display(L2);}//删除元素实验printf("\n删除元素实验:\n"); printf("L2插入1:\n", i);L2 = InsertList(L2,1,1);display(L2);for (i = 1; i < 12; i += 5){printf("删除L2中%d\n",i);L2 = DeleteList(L2, i);display(L2);}//查找printf("\n查找元素实验:\n"); printf("查找L2中%d\n", 13); FindList(L2,13);printf("查找L2中%d\n", 6); FindList(L2, 6);//分解printf("\n分解实验:\n");printf("L2:\n");display(L2);L3 = InitList();printf("将L2偶序数拆分到L3\n"); divide(L2,L3);printf("L2:\n");display(L2);printf("L3:\n");display(L3);printf("\n逆序实验:\n");printf("L2:\n");display(L2);L2 = turn(L2);printf("转置L2:\n");display(L2);}三、详细分析插入实验，函数能够在链表前、中、后插入元素，并判断插入位置是否超过链表长度，若超过则接入链尾。

实验二单链表基本操作一、实验目的1．掌握握单链表的基本操作：新建、插入、删除、查找等运算。

二、实验要求1．认真阅读和掌握本实验的程序。

2．上机运行本程序。

3．保存和打印出程序的运行结果，并结合程序中的问题进行分析。

三、实验内容单链表基本操作的实现，这个程序中演示了单链表的创建、插入、删除和查找。

程序如下：#include<malloc.h>typedef struct node{int data;struct node *next;} NODE;/******************************************/NODE *Create()//问题1：该函数创建的带头结点的单链表，还是不带头结点的单链表？{NODE *p,*head;int x;head=(NODE *)malloc(sizeof(NODE));head->next=NULL;printf("Input data,-1 to End!\n");scanf("%d",&x);while(x!=-1){p=(NODE *)malloc(sizeof(NODE));p->data=x;p->next=head->next;head->next=p;scanf("%d",&x);}return(head);}/******************************************/void Output(NODE *head){NODE *p;p=head;printf("Begin to dump the LinkList...\n");while(p->next!=NULL){printf("->%d",p->next->data);p=p->next;}printf("\nThe LinkList ended!\n");}/******************************************/int Listlen(NODE *head){int i=0;NODE *p=head;while(p->next!=NULL){i++;p=p->next;}return(i);}/******************************************/int Get(NODE *head,int i)//问题2：将该函数修改成返回第i个元素的指针，若不存在，返回空{int j=0;NODE *p=head;while(p->next&&j<i){j++;p=p->next;}if(!p->next||j>i) return(0);else return(p->data);}/******************************************/void Del(NODE *head,int i){NODE *p=head;int j=0;while(p->next&&j<i-1){j++;p=p->next;}if(!p->next||j>i-1) printf("the position is wrong\n");elsep->next=p->next->next;}/******************************************/void Ins(NODE *head,int i,int e){NODE *p=head,*q;int j=0;while(p->next&&j<i-1){j++;p=p->next;}if(!p->next&&j>i-1) printf("Wrong position\n" );else{q=(NODE *)malloc(sizeof(NODE));q->data=e;q->next=p->next;p->next=q;}}/******************************************/main(){NODE *head;int length;int i,element;head=Create();Output(head);//以下函数调用（求长度、插入、删除、查找）能否改成菜单形式？如何改？length=Listlen(head);printf("the length of the link is %d\n",length);printf("input the order :\n");scanf("%d",&i);element=Get(head,i);printf("the element of the order is %d\n",element);printf("input the del position \n");scanf("%d",&i);Del(head,i);Output(head);printf("Input the insert posion and element:\n");scanf("%d%d",&i,&element);Ins(head,i,element);Output(head);}}。

实验二链表操作实现实验日期：2017 年 3 月16 日实验目的及要求1. 熟练掌握线性表的基本操作在链式存储上的实现；2. 以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；3. 掌握线性表的链式存储结构的定义和基本操作的实现；4. 通过本实验加深对C语言的使用（特别是函数的参数调用、指针类型的应用）。

实验内容已知程序文件linklist.cpp已给出学生身高信息链表的类型定义和基本运算函数定义。

（1）链表类型定义typedef struct {int xh; /*学号*/float sg; /*身高*/int sex; /*性别，0为男生，1为女生*/} datatype;typedef struct node{datatype data; /*数据域*/struct node *next; /*指针域*/} LinkNode, *LinkList;（2）带头结点的单链表的基本运算函数原型LinkList initList();/*置一个空表（带头结点）*/void createList_1(LinkList head);/*创建单链表*/void createList_2(LinkList head);/* 创建单链表*/void sort_xh(LinkList head);/*单链表排序*/void reverse(LinkList head);/*对单链表进行结点倒置*/void Error(char *s);/*自定义错误处理函数*/void pntList(LinkList head);/*打印单链表*/void save(LinkList head,char strname[]);/*保存单链表到文件*/任务一创建程序文件linklist.cpp，其代码如下所示，理解LinkList类型和基本运算函数后回答下列问题。

#include <stdio.h>#include <stdlib.h>/*单链表结点类型*/typedef struct {int xh; /*学号*/float sg; /*身高*/int sex; /*性别，0为男生，1为女生*/} datatype;typedef struct node{datatype data; /*数据域*/struct node *next; /*指针域*/} LinkNode, *LinkList;/*带表头的单链表的基本运算函数*/LinkList initList();/*置一个空表（带头结点）*/void createList_1(LinkList head);/*创建单链表*/void createList_2(LinkList head);/*创建单链表*/void sort_xh(LinkList head);/*单链表排序*/void reverse(LinkList head);/*单链表倒置*/void Error(char *s);/*自定义错误处理函数*/void pntList(LinkList head);/*打印单链表*/void save(LinkList head,char strname[]);/*保存单链表到文件*//*置一个空表*/LinkList initList(){ LinkList p;p=(LinkList)malloc(sizeof(LinkNode));p->next=NULL;return p;}/*创建单链表*/void createList_1(LinkList head){ FILE *fp;int xh;float sg;int sex;LinkList p;if((fp=fopen("records.txt","r"))==NULL){ Error("can not open file !");return ;}while(!feof(fp)){ fscanf(fp,"%d%f%d",&xh,&sg,&sex);p=(LinkList)malloc(sizeof(LinkNode));p->data.xh=xh;p->data.sg=sg;p->data.sex=sex;p->next=head->next;head->next=p;}fclose(fp);}/*创建单链表*/void createList_2(LinkList head){ FILE *fp;int xh;float sg;int sex;LinkList p,rear;if((fp=fopen("records.txt","r"))==NULL){ Error("can not open file !");return ;}rear=head;while(!feof(fp)){ fscanf(fp,"%d%f%d",&xh,&sg,&sex);p=(LinkList)malloc(sizeof(LinkNode));p->data.xh=xh;p->data.sg=sg;p->data.sex=sex;p->next=NULL;rear->next=p;rear=p;}fclose(fp);}/*单链表排序*/void sort_xh(LinkList head){LinkList q,p,u;p=head->next;head->next=NULL;/*利用原表头结点建新的空表*/while(p){ q=p; /*q为被插入的结点*/p=p->next;/*用p记录后继结点*//*遍历新链表查找插入位置*/u=head;while(u->next!=NULL)/*查找插入位置*/{ if(u->next->data.xh>q->data.xh)break;u=u->next;}/*插入在u结点的后面*/q->next=u->next;u->next=q;}}/*单链表倒置*/void reverse(LinkList head){ LinkList p, r;p=head->next;head->next=NULL;while(p){ r=p;p=p->next;/*r指向结点头插到链表*/r->next=head->next;head->next=r;}}/*输出单链表*/void pntList(LinkList head){ LinkList p;p=head->next;while(p!=NULL){printf("%2d: %.2f %d\n",p->data.xh,p->data.sg,p->data .sex);p=p->next;}}/*自定义错误处理函数*/void Error(char *s){ printf("\n %s", s);exit(1); /*返回OS,该函数定义在stdlib.h中*/}/*保存单链表到文件*/void save(LinkList head,char strname[]){ FILE *fp;LinkList p;if((fp=fopen(strname,"w"))==NULL){ printf("can not open file !");return ;}p=head->next;while(p!=NULL){ fprintf(fp,"%2d %5.2f %2d\n",p->data.xh,p->data.sg,p->data.sex);p=p->next;}fclose(fp);}请回答下列问题：（1）由单链表结点类型定义可知，该链表结点类型名为 LinkNode ，结点的指针类型为 LinkList ，向系统申请一个学生结点空间并把起始地址存于上述结点指针变量new 中的语句是： p=(LinkList)malloc(sizeof(LinkNode)); 。

数据结构实验二1、实验目的∙熟练掌握线性表的链式存储结构定义及基本操作∙理解循环链表和双链表的特点和基本运算2、实验内容：建立单链表，完成链表（带表头结点）的基本操作：建立链表、插入、删除、查找、输出、求前驱、求后继、两个有序链表的合并操作。

其他基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。

1．问题描述：利用线性表的链式存储结构,设计一组输入数据（假定为一组整数），能够对单链表进行如下操作：∙初始化一个带表头结点的空链表;∙创建一个单链表是从无到有地建立起一个链表，即一个一个地输入各结点数据，并建立起前后相互链接的关系。

又分为逆位序(插在表头)输入n 个元素的值和正位序(插在表尾)输入n 个元素的值;∙插入结点可以根据给定位置进行插入（位置插入），也可以根据结点的值插入到已知的链表中（值插入），且保持结点的数据按原来的递增次序排列，形成有序链表。

∙删除结点可以根据给定位置进行删除（位置删除），也可以把链表中查找结点的值为搜索对象的结点全部删除（值删除）;∙输出单链表的内容是将链表中各结点的数据依次显示，直到链表尾结点;∙求前驱结点是根据给定结点的值，在单链表中搜索其当前结点的后继结点值为给定的值，将当前结点返回;∙求后继结点是根据给定结点的值，在单链表中搜索其当前结点的值为给定的值，将后继结点返回;∙两个有序链表的合并是分别将两个单链表的结点依次插入到第3 个单链表中，继续保持结点有序;编写主程序，实现对各不同的算法调用。

其它的操作算法描述略。

2．实现要求：对链表的各项操作一定要编写成为C（C++）语言函数，组合成模块化的形式，还要针对每个算法的实现从时间复杂度和空间复杂度上进行评价。

∙“初始化算法”的操作结果：构造一个空的线性表L，产生头结点,并使L 指向此头结点;∙“建立链表算法”初始条件：空链存在;操作结果：选择逆位序或正位序的方法，建立一个单链表，并且返回完成的结果;∙“链表（位置）插入算法”初始条件：已知单链表L 存在;操作结果：在带头结点的单链线性表L 中第i 个位置之前插入元素e;∙“链表（位置）删除算法”初始条件：已知单链表L 存在;操作结果：在带头结点的单链线性表L 中，删除第i 个元素,并由e 返回其值;∙“输出算法”初始条件：链表L 已存在;操作结果：依次输出链表的各个结点的值;∙“求前驱算法”初始条件: 线性表L 已存在;操作结果: 若cur_e 是L 的数据元素,且不是第一个,则用pre_e 返回它的前驱;∙“求后继算法”初始条件: 线性表L 已存在;操作结果: 若cur_e 是L 的数据元素,且不是最后一个,则用next_e 返回它的后继;∙“两个有序链表的合并算法”初始条件: 线性表单链线性表La 和Lb 的元素按值非递减排列;操作结果:归并La 和Lb 得到新的单链表。

单向链表单向链表的基本操作,创建一个由6个节点组成的单向链表，显示链表中每个节点的数据，并且做增加、删除、查找节点以及计算单链表的长度等处理。

➢需求分析：1.功能（1）用尾插法创建一带头结点的由6个节点组成的单向链表：从键盘读入一组整数，作为单链表中的元素，输入完第6个结点后结束;将创建好的单链表元素依次输出到屏幕上。

（2）显示链表中每个节点的数据（3）从键盘输入一个数,查找在以上创建的单链表中是否存在该数；如果存在,显示它的位置，即第几个元素;如果不存在，给出相应提示如“No found node!”。

（4）在上述的单链表中的指定位置插入指定数据，并输出单链表中所有数据。

(5）删除上述单链表中指定位置的结点，并输出单链表中所有数据。

(6）求单链表的长度并输出.2．输入要求先输入单链表中结点个数n,再输入单链表中所有数据，在单链表中需查找的数据，需插入的数据元素的位置、值，要删除的数据元素的位置。

3。

测试数据单链表中所有数据：12，23,56，21，8，10在单链表中需查找的数据：56；24插入的数据元素的位置、值：1，28；7,28；0，28要删除的数据元素的位置:6➢概要设计：1.算法思想：由于在操作过程中要进行插入、删除等操作，为运算方便，选用带头结点的单链表作数据元素的存储结构.对每个数据元素，由一个数据域和一个指针域组成，数据域放输入的数据值，指针域指向下一个结点。

2.数据结构：单链表结点类型:typedef struct Liistnode ｛int data；struct Listnode *next;｝NODE;3.模块划分：a)用尾插法建立带头结点的单链表＊CreateList函数；b)显示链表中每个结点的数据PrintList函数;c)从键盘输入一个数，查找单链表中是否存在该数FoundList函数；d)在单链表中指定位置插入指定数据并输出单链表中所有数据InsertList函数;e)删除单链表中指定位置的结点并输出单链表中所有数据DeleteList函数；f)计算单链表的长度并在屏幕上输出LengthList函数;g)主函数main()，功能是给出测试数据值，建立测试数据值的带头结点的单链表,调用PrintList函数、FoundList函数、InsertList函数、DeleteList函数、LengthList函数实现问题要求。

实验二:单链表的基本操作编写一个完整的程序,实现单链表的建立、插入、删除、输出等基本操作。

(1)建立一个带头结点的单链表。

(2)计算单链表的长度,然后输出单链表。

(3)查找值为x的直接前驱结点q。

(4)删除值为x的结点。

(5)把单向链表中元素逆置(不允许申请新的结点空间)。

(6)已知单链表中元素递增有序,请写出一个高效的算法,删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素),同时释放被删结点空间,并分析你的算法的时间复杂度(注意:mink和maxk是给定的两个参变量,他们的值可以和表中的元素相同,也可以不同)。

(7)同(6)的条件,试写一高效的算法,删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同),同时释放被删结点空间,并分析你的算法时间复杂度。

(8)利用(1)建立的链表,实现将其分解成两个链表,其中一个全部为奇数,另一个全部为偶数(尽量利用已知的存储空间)。

(9)在主函数中设计一个简单的菜单,分别测试上述算法。

# include <stdio.h># include <stdlib.h>typedef struct node{int data;struct node * next;}Lnode, * LinkList;int m=sizeof(Lnode);//建立新的链表void Bulid_List(LinkList root){int num;LinkList s,p;s=root->next;int n;printf("请输入新建链表的长度n数据:\n"); scanf("%d",&n);printf("请依次建立链表:");for(int i=0;i<n;i++){scanf("%d",&num);s->data=num;p=(LinkList)malloc(m);s->next=p;s=p;s->next=NULL;}printf("链表已建立!\n");}//对链表的输出,包括长度和元素void OutPut_list(LinkList root) {int len=0;LinkList s;s=root->next;if(s->next==NULL)printf("单链表无数据,请先新建单链表。