下载文档原格式
《数据结构》上机报告_2011_年_ 3 _月_ 9 _日姓名_____ 学号_ _ 同组成员 __ _无_ __1.实验题目及要求编写一个程序，实现单链表的各种基本运算2.需求分析建立一个单链表，实现单链表的初始化，插入、删除节点等功能，以及确定某一元素在单链表中的位置。
（1）初始化单链表；（2）依次采用尾插入法插入a,b,c,d,e元素；（3）输出单链表L；（4）输出单链表L的长度；（5）判断单链表L是否为空；（6）输出单链表L的第三个元素；（7）输出元素a的位置；（8）在第4个元素位置上插入f元素；（9）输出单链表L；（10）删除L的第3个元素；（11）输出单链表L；（12）释放单链表。
3.概要设计（1）为了实现上述程序功能，需要定义一个简化的线性表抽象数据类型：ADT LinearList {数据对象：D={ a i|a i∈IntegerSet,i=0,1,2,…,n,n≥0}结构关系：R={<a i,a i+1>|a i,a i+1 ∈D}基本操作：InitList_L(L)操作前提：L是一个未初始化的线性表操作结果：将L初始化为一个空的线性表CreateList_L(L)操作前提：L是一个已初始化的空表操作结果：建立一个非空的线性表LListInsert_L(L,pos,e)操作前提：线性表L已存在操作结果：将元素e插入到线性表L的pos位置ListDelete_L(L,pos,e)操作前提：线性表L已存在操作结果：将线性表L中pos位置的元素删除，删除的元素值通过e返回LocateList_L(L,e)操作前提：线性表L已存在操作结果：在线性表L中查找元素e，若存在，返回元素在表中的序号位置；若不存在，返回-1DestroyList_L(&L)初始条件：线性表L已存在操作结果：销毁线性表ListEmpty_L(L)初始条件：线性表已存在操作结果：若L为空表，则返回ERROR，否则返回FALSEListLength_L(L)初始条件：线性表L已存在操作结果：返回L中数据元素个数GetElem_L(L,I,&e)初始条件：线性表L已存在操作结果：用e返回L中第i个数据元素值}（2）本程序包含10个函数：主函数main()初始化单链表函数InitList_L()显示单链表内容函数DispList_L()插入元素函数ListInsert_L()删除元素函数ListDelete_L()查找元素函数LocateList_L()创建链表函数CreateList_L()链表元素长度函数ListLength_L()判断链表是否为空函数ListEmpty_L()取值函数GetElem_L()各函数间调用关系如下：( 3 ) 主函数的伪码main(){ 说明一个单链表 L ； 初始化 L ； 建立 L ； 显示 L ； }4. 详细设计采用单链表实现概要设计中定义的抽象数据类型，有关的数据类型和伪码算法定义mainInitList DispList CreateList ListLength ListEmptyDestroyList GetElem ListInsert ListDelete LocateElem如下：（1）类型定义typedef int ElemType;typedef struct LNode{ ElemType data; //数据域struct LNode *next; //指针域} LNode,* LinkList;（2）基本操作的伪码算法初始化Bool InitLinkList(LinkList *L){ *L=申请新结点;如果申请失败，返回失败标志；(*L)->next=NULL;返回成功标志；}建立单链表Bool CrtLinkList(LinkList L)/* L是已经初始化好的空链表的头指针，通过键盘输入元素值，利用尾插法建单链表L */{ rear=L;打印输入提示：“请输入若干个正整数（用空格分隔），并用 -1 结束：”读入一个数x;当x不是结束标志时，循环做如下处理：{申请一个新结点s；如果申请失败，返回失败标志；将x送到s的data域;rear->next=s;rear=s;读入下一个数x;}rear->next=NULL;返回成功标志；}显示单链表（输出）void DispLinkList(LinkList L){p=首元素结点地址;while ( p不空 ){打印结点p 的元素值；p=下一个结点地址;}}插入操作bool InsLinkList(LinkList L, int pos, ElemType e)/*在带头结点的单链表L中第pos个位置插入值为e的新结点s*/ {从“头”开始，查找第i-1个结点 pre ;if (查找失败){ 显示参数错误信息;return ERROR;}else{申请一个新的结点s ;将e放入s的数据域;将s 插到pre 后面;return OK;}}删除操作bool DelLinkList(LinkList L, int pos, ElemType *e)/* 在带头结点的单链表L中删除第pos个元素，并将删除的元素保存到变量*e中 */ {查找待删除结点i的前驱结点，并用pre指向它;if (查找失败){ 显示参数错误信息;return ERROR;}else{r=pre->next;修改指针，删除结点r ;释放被删除的结点所占的内存空间;return OK;}}查找操作int LocLinkList(LinkList L, ElemType e)/ * 在带头结点的单链表L中查找其结点值等于e的结点，若找到则返回该结点的序号位置k，否则返回 -1 * /{p=首元素结点地址;while ( p不空 )if (p->data!=e){ p=p->next; k++; }else break;if ( p 不空 ) return k;else return -1;}5.调试分析开始运行时会出现Debug Error，DAMAGE: After Normal block，搜索后了解到是内存越界操作，检查后发现内存分配L和S=(LinkList)malloc(sizeof(LNode))写成了=(LinkList)malloc(sizeof(LinkList))，修改后正常。
实验一单链表的基本操作（必做）一、实验目的1.掌握单链表的存储、初始化、插入、删除等操作的程序实现。
2.加深对单链表基本概念,基本理论及相应算法的掌握与理解。
3.了解链表的处理方式，学习体会简单的单链表程序实现相关知识。
二、实验内容1.建立一个链表、设计链表的基本操作实现算法、输出一个链表表，调试并输出结果。
2.编写一个程序实现如下功能：让计算机产生出50个0~9之间的随机数并依次保存到单链表中;输出遍历单链表；从单链表中删除与给定值相等的所有结点；输出遍历单链表；输出单链表长度，调试并输出结果。
三、实验步骤1.定义一个链表结构体。
2.利用插入功能插入一个结点。
3.利用删除功能删除一个结点。
四、程序运行测试1.利用插入功能插入一个结点。
2.利用删除功能删除一个结点。
五、实验报告要求1.绘制链表操作实现的流程图。
2.详细给出程序运行测试结果（包括测试数据和测试结果）。
3.选试验步骤2-3中的任意一个，给出程序的详细注释。
4.参考程序中某一部分功能的改进（选做）5.实验心得与体会6.附录，实验用源程序六、参考源代码#include <iostream.h>#include <malloc.h>typedef struct LNode{int data;struct LNode *next;}Lnode, *LinkList;//假设下面的单链表均为带头结点。
void CreatLinkList(LinkList &L,int j){//建立一个单链表L,数据为整数，数据由键盘随机输入。
LinkList p,q;L=(LinkList )malloc(sizeof(Lnode));L->next=NULL;q=L;cout<<"在单链表内输入整数："<<endl;for(int i=0;i<j;i++) p=(LinkList)malloc(sizeof(Lnode)); cin>>p->data;p->next=q->next;q->next=p;q=p; }int PrintLinkList(LinkList &L){//输出单链表L的数据元素LinkList p;p=L->next;if(L->next==NULL){cout<<"链表没有元素!"<<endl;return 0;}cout<<"单链表的数据元素为:";while(p){cout<<p->data<<" ";p=p->next;}cout<<endl;return 1;}void LinkListLengh(LinkList &L){//计算单链表L的数据元素个数。
数据结构单链表实验报告一、实验目的本次实验的主要目的是深入理解和掌握数据结构中的单链表概念、原理和操作方法，通过实际编程实现单链表的创建、插入、删除、查找等基本操作，提高对数据结构的实际应用能力和编程技能。
二、实验环境本次实验使用的编程语言为C+＋，编程工具为Visual Studio 2019。
三、实验原理单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据域和指针域。
指针域用于指向下一个节点，从而形成链表的链式结构。
单链表的优点是可以动态地分配内存，灵活地插入和删除节点，但其缺点是访问特定位置的节点需要从头开始遍历，时间复杂度较高。
四、实验内容（一）单链表的创建创建单链表的基本思路是依次创建节点，并将节点通过指针链接起来。
以下是创建单链表的代码实现：｀｀｀cppinclude ＜iostream>using namespace std;／／定义链表节点结构体struct ListNode ｛int data;ListNode next;ListNode(int x) ： data(x)， next(NULL) ｛｝｝；／／创建单链表ListNode createList(）｛int num, value;cout ＜＜＂请输入节点个数: ＂；cin ＞＞ num;ListNode head ＝ NULL;ListNode tail ＝ NULL;for （int i ＝ 0; i ＜ num; i+＋）｛cout ＜＜＂请输入第＂＜＜ i ＋ 1 ＜＜＂个节点的值: ＂；cin ＞＞ value;if （head ＝＝ NULL) ｛head ＝ newNode;tail ＝ newNode;｝ else ｛tail>next ＝ newNode;tail ＝ newNode;｝｝return head;｝｀｀｀（二）单链表的插入操作单链表的插入操作可以分为在表头插入、在表尾插入和在指定位置插入。
实验截图（1）void InitList(LinkNode *&L)//初始化线性表{L=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点L->next=NULL;//单链表置为空表}void DestroyList(LinkNode *&L)//销毁线性表{LinkNode *pre=L,*p=pre->next;实验截图（2）bool GetElem(LinkNode *L,int i,ElemType &e) //求线性表中第i个元素值{ int j=0;if (i<=0) return false;//i错误返回假LinkNode *p=L;//p指向头结点,j置为0(即头结点的序号为0) while (j<i && p!=NULL)//找第i个结点p{ j++;p=p->next;}if (p==NULL)//存在值为e的结点,返回其逻辑序号ireturn(i);}实验截图（3）bool ListInsert(LinkNode *&L,int i,ElemType e) //插入第i个元素{ int j=0;if (i<=0) return false;//i错误返回假LinkNode *p=L,*s;//p指向头结点,j置为0(即头结点的序号为0) while (j<i-1 && p!=NULL)//查找第i-1个结点p{ j++;p=p->next;}}实验截图（4）编写exp2-2.cpp程序包含有关代码//文件名:exp2-2.cpp#include "linklist.cpp"int main(){LinkNode *h;ElemType e;printf("单链表的基本运算如下:\n");printf(" (1)初始化单链表h\n");InitList(h);printf(" (2)依次采用尾插法插入a,b,c,d,e元素\n");return 1;}实验截图（5）运行得到结果实验截图（6）。
单链表基本操作的实现单链表是一种常见的数据结构，它由多个节点组合而成，每个节点包含一个数据元素和一个指向下一个节点的指针。
通过指针，我们可以方便地在单链表中进行插入、删除和遍历等操作。
以下是关于单链表基本操作的实现。
1. 单链表的创建单链表的创建需要定义一个空的头结点，它的作用是方便在链表的头部进行添加和删除节点操作。
一个空的头节点可以在链表初始化的过程中进行创建。
```typedef struct Node{int data;struct Node *next;}Node;Node *createList(){Node *head = (Node*)malloc(sizeof(Node)); //创建空的头节点head->next = NULL;return head; //返回头节点的地址}```2. 单链表的插入单链表的插入可以分为在链表头部插入、在链表尾部插入和在链表中间插入三种情况。
a. 在链表头部插入节点：```void insertAtHead(Node *head, int data){Node *node = (Node*)malloc(sizeof(Node));node->data = data;node->next = head->next;head->next = node;}```b. 在链表尾部插入节点：```void insertAtTail(Node *head, int data){Node *node = (Node*)malloc(sizeof(Node));node->data = data;node->next = NULL;Node *p = head;while(p->next != NULL){p = p->next;}p->next = node;}```c. 在链表中间插入节点：```void insertAtMid(Node *head, int data, int pos){ Node *node = (Node*)malloc(sizeof(Node)); node->data = data;node->next = NULL;Node *p = head;int count = 0;while(p->next != NULL && count < pos-1){ p = p->next;count++;}if(count == pos-1){node->next = p->next;p->next = node;}else{printf("插入位置错误!");}}```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("单链表无数据,请先新建单链表。
- 1 -实验一：实现单链表各种基本运算的算法一、 实验目的1、 掌握单链表存储结构的类型定义；2、 实现单链表各种基本运算的算法。
二、 实验环境1、 Windows 操作系统；2、 Visual C++ 6.0三、 实验内容实现单链表各种基本运算的算法。
四、 概要设计1.存储结构的类型定义：Typedef struct LNode{ElemType data;Struct LNode *next;}LinkList;2.单链表示意图：3.项目组成图:4.algo2_2.cpp 的程序文件包含的函数原型及功能:InitList(LinkList *&L) 初始化单链表LDestroyList(LinkList *&L) 释放单链表LListEmpty(LinkList *L)判断单链表L 是否为空表ListLength(LinkList *L)返回单链表L 的元素个数DispList(LinkList *L)输出单链表LGetElem(LinkList *L,int i,ElemType &e)获取单链表L 的第i 个元素LocateElem(LinkList *L,ElemType e)在单链表L 中查找元素eListInsert(LinkList *&L,int i,ElemType e)在单链表L 中的第i 个位置上插入元素e…… head a 1 a 2 a 3 a n ∧ListDelete(LinkList *&L,int i,ElemType &e)在单链表L中删除第i个元素5.exp2_2.cpp程序文件简介:InitList(LinkList *&L) 初始化单链表LDestroyList(LinkList *&L) 释放单链表LListEmpty(LinkList *L) 判断单链表L是否为空表ListLength(LinkList *L) 返回单链表L的元素个数DispList(LinkList *L) 输出单链表LGetElem(LinkList *L,int i,ElemType &e) 获取单链表L的第i个元素LocateElem(LinkList *L,ElemType e) 在单链表L中查找元素eListInsert(LinkList *&L,int i,ElemType e) 在单链表L中的第i个位置上插入元素e ListDelete(LinkList *&L,int i,ElemType &e) 在单链表L中删除第i个元素6.proj2-2的项目的模块结构:在文件algo2-2中，(1)定义单链表结构类型；(2)初始化单链表(3)定义释放单链表的函数(4)定义判断单链表是否为空的函数(5)定义返回单链表元素个数的函数(6)定义输出单链表的函数(7)定义获取第i个元素的函数(8)定义查找元素的函数(9)定义插入元素的函数(10)定义删除元素的函数在文件exp2-2中分别调用algo2-2中所定义的函数7.函数调用关系图:五、详细设计源代码清单见附录。
实现单链表的各种基本运算。
单链表是一种常用的数据结构，它由一个头指针和一些节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。
单链表具有插入、删除、查找、排序等基本运算。
下面将介绍如何实现单链表的各种基本运算。
1. 创建单链表
首先需要定义一个节点结构，包含数据域和指针域。
然后声明一个头指针，表示单链表的头节点。
接着输入节点数据，逐个创建新节点，并将其插入链表中。
2. 插入节点
在单链表中插入节点有两种情况：插入到链表头部和插入到链表尾部。
插入节点时需要先找到插入位置的前一个节点，然后修改前一个节点的指针域，将其指向新节点，再修改新节点的指针域，将其指向插入位置的后一个节点。
3. 删除节点
在单链表中删除节点也有两种情况：删除链表头部的节点和删除链表任意位置的节点。
删除节点时需要先找到删除位置的前一个节点，然后修改前一个节点的指针域，将其指向待删除节点的后一个节点，最后释放待删除节点的空间。
4. 查找节点
在单链表中查找节点时需要从头节点开始遍历链表，逐个比较节点值，直到找到目标节点或者遍历到链表尾部为止。
5. 排序
单链表排序可以采用冒泡排序、选择排序、快速排序等多种算法。
其中最简单的是冒泡排序，即从头节点开始遍历链表，逐个比较相邻节点的值，如果前一个节点的值大于后一个节点的值，则交换两个节点的值，直到遍历到链表尾部为止。
以上就是单链表的各种基本运算的实现方法，其它高级运算（如合并链表、反转链表等）可以在此基础上进一步扩展。
软件技术基础实验一——单链表的各种基本运算的实现一、实验题目编写一个程序，实现单链表的各种基本运算，并在此基础上设计一个主程序完成如下功能：（1）初始化单链表（2）依次采用尾插法插入a,b,c,d,e元素（3）输出单链表（4）在第四个元素位置上插入f元素（5）删除该单链表的第三个元素二、实验目的1、理解单链表的概念及结构特点；2、掌握单链表的基本操作：查找、插入、删除等运算在链接存储结构上的运算。
三、调试通过并正确执行给定功能要求的实验代码#include "stdafx.h"#include<malloc.h>#include<iostream.h>struct link{char data;link *next;};link *rcreat(link *head,char x) //尾插法建立单链表{link *s,*r;r=head;s=new link;s->data=x;r->next=s;r=s;r->next=NULL;return r;}link *get(link *head,int i) //查找第i个元素，返回其地址{int j;link *p;j=1;p=head->next ;while((j<i-1)&&(p!=NULL)){j++;p=p->next;}return p;}void insert(link *head,int num,char y) //元素y之后插入x {link *p,*s;s=new link;s->data=y;if(head->next==NULL){head->next=s;s->next=NULL;}p=get(head,num);if(p==NULL) cout<<"插入位置非法";else{s->next=p->next;p->next=s;}}void delet(link *head,char x) //将指定元素x删除{link * p, * q;q=head;p=head->next;while((p!=NULL)&&(p->data!=x)){q=p;p=p->next;}if(p==NULL) cout<<"要删除的元素不存在";else{q->next=p->next;delete(p);}}void print(link *head) //输出单链表{link *p;p=head->next;while(p->next!=NULL){cout<<p->data<<"->";p=p->next;}cout<<p->data<<endl;}void main(int argc, char* argv[]){link *head,*p,*q,*r;char x,y;int n,dele,i=1,j=1;head=new link;head->next=NULL;r=head;while(j<=5){cout<<"请输入要插入的元素：";cin>>x;r=rcreat(r,x);j=j+1;}print(head);cout<<"请输入要插入元素的位置：";cin>>n;cout<<"请输入要插入的元素：";cin>>y;insert(head,n,y);cout<<"输出插入后的单链表："<<endl;print(head);cout<<"请输入要删除元素的位置：";cin>>dele;q=head;p=head->next;while(i<dele){q=p;p=p->next;i=i+1;}q->next=p->next;delete (p);cout<<"删除后的链表如下："<<endl;print(head);}四、实验结果。
单链表的实现实验报告篇一：数据结构单链表实验报告一、设计人员相关信息1. 设计者姓名、学号和班号：12地信李晓婧120122429832. 设计日期：2014.3. 上机环境：VC++6.0二、程序设计相关信息1. 实验题目：编写一个程序，实现单链表的各种基本运算（假设单链表的元素类型为char），并在此基础上设计一个程序，完成如下功能：（1）初始化单链表；（2）采用尾插法依次插入元素a,b,c,d,e;（3）输出单链表（4）输出单链表长度（5）判断单链表是否为空（6）输出单链表第3个元素（7）输出元素a的位置（8）在第4个元素位置上插入元素f（9）输出单链表（10）删除第三个元素（11）输出单链表（12）释放单链表2. 实验项目组成：（1）插入和删除节点操作（2）建立单链表尾插法建表（3）线性表基本运算在单链表中的实现初始化线性表销毁线性表判断线性表是否为空表求线性表的长度3. 实验项目的程序结构（程序中的函数调用关系图）：4. 实验项目包含的各个文件中的函数的功能描述：? 尾插法建表CreateListR：将新节点插到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾节点。
? 初始化线性表InitList：该运算建立一个空的单链表，即创建一个头节点；? 销毁线性表DestroyList：释放单链表占用的内存空间，即逐一释放全部节点的空间； ? 判断线性表是否为空表ListEmpty：若单链表没有数据节点，则返回真，否则返回假； ? 求线性表的长度ListLength：返回单链表中数据节点的个数；? 输出线性表DispList：逐一扫描单链表的每个数据节点，并显示各节点的data域值；? 求线性表中某个数据元素值GetElem：在单链表中从头开始找到第i个节点，若存在第i个数据节点，则将其data域值赋给变量e；? 按元素值查找LocateElem：在单链表中从头开始找第一个值域与e相等的节点，若存在这样的节点，则返回逻辑序号，否则返回0；? 插入数据元素ListInsert：先在单链表中找到第i1个节点*p，若存在这样的节点，将值为e的节点*s插入到*p节点的后面；? 删除数据元素ListDelete：先在单链表中找到第i1个节点*p，若存在这样的节点，且也存在后继节点*q；删除*q节点，返回TRUE；否则返回FALSE表示参数i错误。
