下载文档原格式
单链表的基本操作实验报告单链表的基本操作实验报告引言：单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。
在本次实验中，我们将学习和实践单链表的基本操作，包括创建链表、插入节点、删除节点以及遍历链表等。
一、实验目的本次实验的主要目的是掌握单链表的基本操作，包括链表的创建、插入节点、删除节点和遍历链表。
通过实践操作，加深对单链表的理解，并掌握如何应用单链表解决实际问题。
二、实验过程1. 创建链表首先，我们需要创建一个空链表。
链表可以通过一个头节点来表示，头节点不存储数据，只用于标识链表的起始位置。
我们可以定义一个指针变量head，将其指向头节点。
2. 插入节点在链表中插入节点是常见的操作。
我们可以选择在链表的头部、尾部或者指定位置插入节点。
插入节点的过程可以分为以下几个步骤：a. 创建一个新节点，并为其赋值；b. 找到要插入位置的前一个节点；c. 将新节点的指针指向前一个节点的下一个节点；d. 将前一个节点的指针指向新节点。
3. 删除节点删除节点是另一个常见的操作。
我们可以选择删除链表的头节点、尾节点或者指定位置的节点。
删除节点的过程可以分为以下几个步骤：a. 找到要删除节点的前一个节点；b. 将前一个节点的指针指向要删除节点的下一个节点；c. 释放要删除节点的内存空间。
4. 遍历链表遍历链表是为了查看链表中的元素。
我们可以从头节点开始，依次访问每个节点，并输出节点的值。
三、实验结果在本次实验中，我们成功完成了单链表的基本操作。
通过创建链表、插入节点、删除节点和遍历链表等操作，我们可以方便地对链表进行增删改查操作。
四、实验总结通过本次实验，我们对单链表的基本操作有了更深入的了解。
单链表是一种非常重要的数据结构，广泛应用于各个领域。
掌握了单链表的基本操作，我们可以更好地解决实际问题，并且为以后学习更复杂的数据结构打下坚实的基础。
在实验过程中，我们还发现了一些问题和不足之处。
数据结构-单链表基本操作实现（含全部代码）今天是单链表的实现，主要实现函数如下：InitList(LinkList &L) 参数：单链表L 功能：初始化时间复杂度 O(1)ListLength(LinkList L) 参数：单链表L 功能：获得单链表长度时间复杂度O(n)ListInsert(LinkList &L,int i,ElemType e) 参数：单链表L,位置i，元素e 功能：位置i后插时间复杂度O(n)[加⼊了查找]若已知指针p指向的后插 O(1)ListDelete(LinkList &L,int i) 参数：单链表L，位置i 功能：删除位置i元素时间复杂度O(n)[加⼊了查找]若已知p指针指向的删除最好是O(1),因为可以与后继结点交换数据域，然后删除后继结点。
最坏是O(n),即从头查找p之前的结点,然后删除p所指结点LocateElem(LinkList L,ElemType e) 参数：单链表L，元素e 功能：查找第⼀个等于e的元素，返回指针时间复杂度O(n)代码：/*Project: single linkeed list (数据结构单链表)Date: 2018/09/14Author: Frank YuInitList(LinkList &L) 参数：单链表L 功能：初始化时间复杂度 O(1)ListLength(LinkList L) 参数：单链表L 功能：获得单链表长度时间复杂度O(n)ListInsert(LinkList &L,int i,ElemType e) 参数：单链表L,位置i，元素e 功能：位置i后插时间复杂度O(n)[加⼊了查找]若已知指针p指向的后插 O(1)ListDelete(LinkList &L,int i) 参数：单链表L，位置i 功能：删除位置i元素时间复杂度O(n)[加⼊了查找]若已知p指针指向的删除最好是O(1),因为可以与后继结点交换数据域，然后删除后继结点。
数据结构实验二（单链表基本操作）题目和源程序实验2：单链表基本操作一、实验目的1.学会定义单链表的结点类型，实现对单链表的一些基本操作和具体的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。
2.掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。
二、实验要求1．预习C语言中结构体的定义与基本操作方法。
2．对单链表的每个基本操作用单独的函数实现。
3．编写完整程序完成下面的实验内容并上机运行。
4．整理并上交实验报告。
三、实验内容1．编写程序完成单链表的下列基本操作：(1)初始化单链表La。
(2)在La中第i个元素之前插入一个新结点。
(3)删除La中的第i个元素结点。
(4)在La中查找某结点并返回其位置。
(5)打印输出La中的结点元素值。
2 .构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、Lb合并成一个有序单链表Lc。
合并思想是：程序需要3个指针：pa、pb、pc，其中pa，pb分别指向La表与Lb表中当前待比较插入的结点，pc 指向Lc表中当前最后一个结点。
依次扫描La和Lb中的元素，比较当前元素的值，将较小者链接到*pc 之后，如此重复直到La或Lb结束为止，再将另一个链表余下的内容链接到pc所指的结点之后。
3．构造一个单链表L，其头结点指针为head，编写程序实现将L 逆置。
（即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。
）四、思考与提高1．如果上面实验内容2中合并的表内不允许有重复的数据该如何操作？2．如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb，Lc，使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点？/*----------------------------------------* 02_单链表.cpp -- 单链表基本操作* 对单链表的每个基本操作都用单独的函数来实现* 水上飘2009年写----------------------------------------*/// ds02.cpp : 定义控制台应用程序的入口点。
实验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);}}。
实验二、链表基本操作
一、实验目的
1．掌握链表的概念，学会对链表进行操作。
2．加深对链式存储结构的理解，逐步培养解决实际问题的能力。
二、实验内容
（1）编写链表基本操作函数
●创建一个包含n个结点的单链表，要求返回头指针；
CreateList_L(LinkList &L,int n)
●在单链表中数据元素值为a的结点前插入值为b的结
点，要求如果值为a的结点不存在，则插在表尾；
InsertList_L(LinkList &L, char a,char b)
●在单链表中删除数据元素值为c的结点，要求如果存
在，则返回1，否则返回0；
DeleteList_L(LinkList &L,char c)
注意：每完成一个步骤，必须及时输出链表元素，便于观察操作结果。
（2）用主函数调用上述函数，实现相应功能。
三、实验要求
1．C完成算法设计和程序设计并上机调试通过。
2．撰写实验报告，提供实验结果和数据。
3．分析算法，简要给出算法设计小结和心得。
四、程序运行情况
写出输入数据及运行结果五、源程序清单。
实验二:单链表的基本操作编写一个完整的程序,实现单链表的建立、插入、删除、输出等基本操作。
(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("单链表无数据,请先新建单链表。
实验2：单链表基本操作一、实验目的1.学会定义单链表的结点类型，实现对单链表的一些基本操作和具体的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。
2.掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。
二、实验要求1．预习C语言中结构体的定义与基本操作方法。
2．对单链表的每个基本操作用单独的函数实现。
3．编写完整程序完成下面的实验内容并上机运行。
4．整理并上交实验报告。
三、实验内容1．编写程序完成单链表的下列基本操作：(1)初始化单链表La。
(2)在La中第i个元素之前插入一个新结点。
(3)删除La中的第i个元素结点。
(4)在La中查找某结点并返回其位置。
(5)打印输出La中的结点元素值。
2 .构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、Lb合并成一个有序单链表Lc。
合并思想是：程序需要3个指针：pa、pb、pc，其中pa，pb分别指向La表与Lb表中当前待比较插入的结点，pc 指向Lc表中当前最后一个结点。
依次扫描La和Lb中的元素，比较当前元素的值，将较小者链接到*pc 之后，如此重复直到La或Lb结束为止，再将另一个链表余下的内容链接到pc所指的结点之后。
3．构造一个单链表L，其头结点指针为head，编写程序实现将L逆置。
（即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。
）四、思考与提高1．如果上面实验内容2中合并的表内不允许有重复的数据该如何操作？2．如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb，Lc，使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点？/*----------------------------------------* 02_单链表.cpp -- 单链表基本操作* 对单链表的每个基本操作都用单独的函数来实现* 水上飘2009年写----------------------------------------*/// ds02.cpp : 定义控制台应用程序的入口点。
//#include "stdafx.h"#include<iostream>#include<iomanip>#include<ctime>using namespace std;typedef int ElemType;typedef struct LNode{ElemType data;struct LNode *next;}LNode, *LinkList;//确保输入的数据正确int Oncemore(){int n ;cout << "输入错误，请重新输入：" ;cin >> n ;cout << endl ;if( n <= 2 )n = Oncemore( ) ;return n ;}//初始化单链表Lvoid InitList(LinkList &L){L = (LinkList)malloc(sizeof(LNode));L->next = NULL;}//逆位序创建一个带头结点的单链线性表LinkList CreateList( LinkList &L, int n ){LinkList p ;for( int i = 0; i < n; i++ ){p = (LinkList)malloc(sizeof(LNode)) ;p->data = (int)(rand()%100) ; //给新生成的结点随机赋一个值p->next = L->next ; L->next = p ; //插入到表头}return L;}//在L中第i个元素之前插入一个新结点void Insert(LinkList &L, int i){LNode *p;LNode *p1;int m;p1 = L->next ;p = (LinkList)malloc(sizeof(LNode)) ;p->data = (int)(rand()%100) ; //给新生成的结点随机赋一个值for(m = 2; m < i; m++)p1 = p1->next ;if(m == i){p->next = p1->next ;p1->next = p;cout << "在L中第i个元素之前插入一个新结点成功.";}else cout << "在L中第i个元素之前插入一个新结点失败.";}//删除La中的第i个元素结点void Delete(LinkList &L, int j){LNode *p;LNode *p1;int m;p1 = L->next ;for(m = 1; m < j; m++){p1 = p1->next ;if(m == (j-2))p = p1; //p指向欲删除结点的前一个结点}if(m == j){p->next = p1->next ; //p结点指向欲删除结点的下一个结点delete p1;cout << "删除L中的第j个元素结点成功．";}else cout << "删除La中的第j个元素结点失败．";}//在L中查找某结点并返回其值int Lookup(LinkList &L, int k){LNode *p;p = L->next ;int i;for(i = 1; i < k; i++)p = p->next ;if(i == k){cout << "在L中查找第ｉ个结点并返回其值成功.";return p->data ;}else{cout << "在L中查找ｉ个结点并返回其值失败.";return 0;}}/*LinkList mix(LinkList &L){LinkList p1,p2,p3;p1 = L->next ;p2 = L->next ;p3 = L->next ;while(p1->next != NULL){if(p1->data > p1->next->data)p2 = p1->next ;p1 = p1->next ;}if(p3->next = NULL){L->next = NULL;return p1;}else{p3 = L->next ;while(p3->next != p2 && !p3->next)p3 = p3->next ;p3->next = p2->next ;p2->next = NULL ;return p2;}}void Union(LinkList &La,LinkList &Lb,LinkList &Lc) {LinkList pa,pb,pc;pc = Lc;while(La->next != NULL && Lb->next != NULL) {pa = mix(La);pb = mix(Lb);if(pa->data < pb->data){pc->next = pa ;pc = pa;}else{pc->next = pb ;pc = pb;}}if(La->next != NULL)pc->next = La->next ;if(Lb->next != NULL)pc->next = Lb->next ;}*///使线性表按值非递减排列void Notdegression( LinkList &L, int n ){int m ;LinkList pa;while(n){pa = L->next ;while( pa->next ) //当pa不为最后一个结点{if( pa->data > pa->next->data ) //交换两个结点的值{m = pa->data ;pa->data = pa->next->data ;pa->next->data = m ;pa = pa->next ; //移向下一个结点}else{pa = pa->next ; //移向下一个结点continue ;}}n-- ;}}//归并La和Lb，得到元素也按非递减排列的Lcvoid Merger( LinkList &La, LinkList &Lb, LinkList &Lc ){Lc = (LinkList)malloc(sizeof(LNode));LinkList pa, pb, pc ;pa = La->next ;pb = Lb->next ;Lc->next = NULL ; //初始化pc = Lc ;while(pa && pb) //当pa或pb没有到最后一个结点{if(pa->data < pb->data) //pa结点插入到Lc表的末端{pc->next = pa ;pc = pa ;pa = pa->next;}else{ //pb结点插入到Lc表的末pc->next = pb ;pc = pb;pb = pb->next ;}}pc->next = pa ? pa : pb ; /*判断La表和Lb表是否已插入完，若没有，则剩下的插入到Lc的末端*/delete La;delete Lb; //释放头结点}//将L逆置（即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。
）void CutBack(LinkList &L){LinkList p1,p2,p3;p1 = L->next ;p3 = L ;while(p1->next) //p1指向最后一个结点，p3指向倒数第二个结点{p1 = p1->next ;p3 = p3->next ;}p2 = p1; //p2指向最后一个结点while(p3 != L) //实现倒置{p2->next = p3;p3->next = NULL ;p2 = L->next ; //指向第一个结点p3 = L ; //指向头结点while(p2->next) //p2指向新表的最后一个结点，p3指向倒数第二个结点{p2 = p2->next ;p3 = p3->next ;}}p2->next = NULL ; //让新表最后一个结点指向空p3->next = p1 ; //让p3即L头结点指向新表的第一个结点}//输出单链表Lvoid OutputList( LinkList &L ){cout << endl;LNode *L1 ;int i = 0 ;L1 = L->next ; //L1指向第一个结点while(L1->next != NULL){cout << setw(5) << L1->data ;L1 = L1->next ;i++ ;if( i % 5 == 0)cout << endl ;}cout << setw(5) << L1->data ; //输出最后一个结点的值cout << endl << endl ;}//第一题void FirstTitle(){cout << "第一题开始：" << endl;LinkList L;int n;cout << "输入表的元素个数:";cin >> n;if(n <= 2)n = Oncemore();InitList(L);CreateList(L,n);OutputList(L);int i,j;cout << "输入插入的位置:";cin >> i;Insert(L,i);OutputList(L);cout << "输入删除的位置:";cin >> j;Delete(L,j);OutputList(L);int k,m;cout << "输入要查找的结点的序号：";cin >> k;m = Lookup(L,k);cout << endl << "第" << k << "个结点的值是：" << m << endl;}//第二题void SecondTitle(){cout << "第二题开始：" << endl;LinkList La,Lb,Lc;int a,b;cout << "输入La的元素个数：";cin >> a;InitList(La);CreateList(La,a);OutputList(La);cout << "输入Lb的元素个数：";cin >> b;InitList(Lb);CreateList(Lb,b);OutputList(Lb);//Union(La,Lb,Lc); //第二题的第二种方法Notdegression(La,a);cout << "La按非递减排序后：" << endl ;OutputList(La);Notdegression(Lb,b);cout << "Lb按非递减排序后：" << endl ;OutputList(Lb);Merger(La,Lb,Lc);cout << "最后结果：" << endl;OutputList(Lc);}//第三题void ThirdTitle(){cout << "第三题开始：" << endl ;LinkList L;int a;cout << "输入L的元素个数：";cin >> a;InitList(L);CreateList(L,a);OutputList(L);CutBack(L);cout << "改变后的链表为：" << endl;OutputList(L);}void main(){srand(time(NULL));FirstTitle();cout << "---------------------------------------------------" << endl;SecondTitle();cout << "---------------------------------------------------" << endl;ThirdTitle();}。
