数据结构上机报告：编写一个程序,实现单链表的各种基本运算

实现单链表的基本运算单链表是一种常见的数据结构，它由一组节点组成，每个节点包含数据和一个指向下一个节点的指针。

单链表具有插入、删除、查找等基本运算，是程序设计中不可或缺的一部分。

本文将介绍如何实现单链表的基本运算，包括创建、插入、删除、查找和遍历等操作。

一、创建单链表创建单链表的过程是将一组数据按照顺序存储到链表中。

首先需要定义一个节点结构体，包含数据和指向下一个节点的指针。

然后定义一个头节点指针，用于指向链表的头节点。

接着，遍历数据，创建节点并将其插入链表中。

最后返回头节点指针，表示链表的开始。

二、插入节点插入节点是指将一个新节点插入到链表中的某个位置，可以将其插入到链表的头部、尾部或任意位置。

插入节点的过程需要先找到插入位置的前一个节点，然后将新节点的指针指向后一个节点，再将前一个节点的指针指向新节点。

如果是在链表头部插入节点，只需要将新节点的指针指向原来的头节点，再将头节点指针指向新节点即可。

三、删除节点删除节点是指将链表中的某个节点删除。

删除节点的过程需要先找到要删除的节点的前一个节点，然后将前一个节点的指针指向要删除节点的后一个节点。

如果要删除的节点是头节点，需要特殊处理，将头节点指针指向要删除节点的后一个节点。

四、查找节点查找节点是指在链表中查找某个节点是否存在。

查找节点的过程需要遍历整个链表，逐个比较节点的数据是否与目标数据相等。

如果找到了目标节点，返回节点指针；如果遍历完整个链表仍未找到目标节点，返回空指针。

五、遍历链表遍历链表是指依次访问链表中的每个节点，并对每个节点进行操作。

遍历链表的过程需要从头节点开始，依次访问每个节点，直到遍历到链表的末尾。

遍历链表可以用循环或递归两种方式实现。

以上就是实现单链表的基本运算的过程，通过对单链表的创建、插入、删除、查找和遍历等操作，可以实现对数据的存储和操作。

在程序设计中，单链表是一种非常常见和实用的数据结构，掌握其基本操作对于提高程序的效率和可读性都有很大的帮助。

《算法与数据结构》上机报告姓名：班级：学号：实验一链表的操作一．实验名称：链表的基本操作二．实验目的：通过该实验，了解线性表的链式存储结构,熟悉链式存储结构的存储特点，掌握利用链式存储的线性表进行插入和删除基本算法。

三．实验原理：线性表有各种存储方式，链表是用链式存储方式存放的线性表，它是用一组地址不一定连续的单元存放一组连续的数据，数据之间的相邻关系是通过数据节点中指针域的值加以体现的。

对于线性表SLSL=(a1,a2,…ai-1,ai,…an);在第i个位置插入一个数据元素x后，线性表SL就变为SL’=(a1,a2,…ai-1, x,ai,…an);要使得链表中的数据和线性表中的数据保持一致，就要修改数据节点中指针域的值，在p指针所指节点后插入一个新数据节点S的操作为:① s=(LinkList *)malloc(sizeof(LinkList));② s->data=x;③ s->next=p->next;④ p->next=s;同样，对于线性表SL，在第i个位置删除一个数据元素后，线性表SL就变为SL’’=(a1,a2,…ai-1,ai+1,…an);要使得链表中的数据和线性表中的数据保持一致，删除p指针所指节点后面的数据节点的操作为：① s=p->next;② p->next=p->next->next;③ free(s);四．实验内容：实验题2.2 编写一个程序algo2-2.cpp，实现单链表的各种基本运算（假设单链表的元素类型为char），并在此基础上设计一个程序exp2-2 .cpp ，完成如下功能：(1)初始化单链表h(2)采用尾插法依次插入a,b,c,d,e元素(3)输出单链表h(4)输出单链表h长度(5)判断单链表h是否为空(6)输出单链表h的第3个元素(7)输出元素a的位置(8)在第4个元素位置上插入f元素(9)输出单链表h(10)删除L的第3个元素(11)输出单链表h(12)释放单链表h五．算法步骤：实验题 2.3编写一个程序algo2-3.cpp，实现双链表的各种基本运算（假设双链表的元素类型为char），并在此基础上设计一个程序exp2-3.cpp，完成如下功能：(1)初始化双链表h(2)依次采用尾插法插入a,b,c,d,e元素(3)输出双链表h(4)输出双链表h长度(5)判断双链表h是否为空(6)输出双链表h的第3个元素(7)输出元素a的位置(8)在第4个元素位置上插入f元素(9)输出双链表h(10)删除L的第3个元素(11)输出双链表h(12)释放双链表h五．算法步骤：六．程序源代码：实验题2.2//文件名:algo2-2.cpp#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct LNode{ElemType data;struct LNode *next;}LinkList;void InitList(LinkList *&L) //初始化线性表{L=(LinkList *)malloc(sizeof(LinkList));L->next=NULL;}void DestroyList(LinkList *&L){LinkList *p=L,*q=p->next;while(q!=NULL){free(p);p=q;q=p->next;}free(p);}bool ListEmpty(LinkList *L) //判断线性表是否为空{return(L->next==NULL);}int ListLength(LinkList *L){int n=0;LinkList *p=L;while(p->next!=NULL){n++;p=p->next;}return(n);}void DispList(LinkList *L) //输出线性表{LinkList *p=L->next;while(p!=NULL){printf("%c",p->data);p=p->next;}printf("\n");}bool GetElem(LinkList *L,int i,ElemType &e) //求线性表中某个数据元素值{int j=0;LinkList *p=L;while(j<i&&p!=NULL){j++;p=p->next;}if(p==NULL)return false;else{e=p->data;return true;}}int LocateElem(LinkList *L,ElemType e) //按元素值查找{int i=1;LinkList *p=L->next;while(p!=NULL&&p->data!=e){p=p->next;i++;}if (p==NULL)return (0);elsereturn (i);}bool ListInsert(LinkList *&L,int i,ElemType e) //插入数据元素{int j=0;LinkList *p=L,*s;while(j<i-1&&p!=NULL){j++;p=p->next;}if(p==NULL)return false;else{s=(LinkList *)malloc(sizeof(LinkList));s->data=e;s->next=p->next;p->next=s;return true;}}bool ListDelete(LinkList *&L,int i,ElemType &e) //删除数据元素{int j=0;LinkList *p=L,*q;while(j<i-1&&p!=NULL){j++;p=p->next;}if(p==NULL)return false;else{q=p->next;if(q==NULL)return false;e=q->data;p->next=q->next;free(q);return true;}}//文件名:exp2-2.cpp#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct LNode //定义单链表结点类型{ElemType data;struct LNode *next;} LinkList;extern void InitList(LinkList *&L);extern void DestroyList(LinkList *&L);extern bool ListEmpty(LinkList *L);extern int ListLength(LinkList *L);extern void DispList(LinkList *L);extern bool GetElem(LinkList *L,int i,ElemType &e);extern int LocateElem(LinkList *L,ElemType e);extern bool ListInsert(LinkList *&L,int i,ElemType e); extern bool ListDelete(LinkList *&L,int i,ElemType &e); void main(){LinkList *h;ElemType e;printf("单链表的基本运算如下所示:\n");printf("(1)初始化单链表h\n");InitList(h);printf("(2)采用尾插法插入a,b,c,d,e元素\n");ListInsert(h,1,'a');ListInsert(h,2,'b');ListInsert(h,3,'c');ListInsert(h,4,'d');ListInsert(h,5,'e');printf("(3)输出单链表h:");DispList(h);printf("(4)单链表h长度=%d\n",ListLength(h));printf("(5)单链表h为%s\n",(ListEmpty(h)?"空":"非空"));GetElem(h,3,e);printf("(6)单链表h的第3个元素=%c\n",e);printf("(7)元素a的位置=%d\n",LocateElem(h,'a'));printf("(8)在第4个元素位置上插入f元素\n");ListInsert(h,4,'f');printf("(9)输出单链表h:");DispList(h);printf("(10)删除h的第3个元素\n");ListDelete(h,3,e);printf("(11)输出单链表h:");DispList(h);printf("(12)释放单链表h\n");DestroyList(h);}实验题2.3//文件名:algo2-3.cpp#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct DNode //定义双链表结点类型{ElemType data;struct DNode *prior;struct DNode *next;} DLinkList;void InitList(DLinkList *&L) //初始化{L=(DLinkList *)malloc(sizeof(DLinkList));L->prior=L->next=NULL;}void DestroyList(DLinkList *&L){DLinkList *p=L,*q=p->next;while (q!=NULL){free(p);p=q;q=p->next;}free(p);}bool ListEmpty(DLinkList *L) //判线性表是否为空表{return(L->next==NULL);}int ListLength(DLinkList *L) //求线性表的长度{DLinkList *p=L;int i=0;while (p->next!=NULL){i++;p=p->next;}return(i);}void DispList(DLinkList *L) //输出线性表DLinkList *p=L->next;while (p!=NULL){printf("%c ",p->data);p=p->next;}printf("\n");}bool GetElem(DLinkList *L,int i,ElemType &e) //求线性表中某个数据元素值{int j=0;DLinkList *p=L;while (j<i && p!=NULL){j++;p=p->next;}if (p==NULL)return false;else{e=p->data;return true;}}int LocateElem(DLinkList *L,ElemType e) //按元素值查找{int n=1;DLinkList *p=L->next;while (p!=NULL && p->data!=e){n++;p=p->next;}if (p==NULL)return(0);elsereturn(n);}bool ListInsert(DLinkList *&L,int i,ElemType e) //插入数据元素{int j=0;DLinkList *p=L,*s;while (j<i-1 && p!=NULL){j++;p=p->next;}if (p==NULL)return false;else{s=(DLinkList *)malloc(sizeof(DLinkList));s->data=e;s->next=p->next;if (p->next!=NULL) p->next->prior=s;s->prior=p;p->next=s;return true;}}bool ListDelete(DLinkList *&L,int i,ElemType &e) //删除数据元素{int j=0;DLinkList *p=L,*q;while (j<i-1 && p!=NULL){j++;p=p->next;}if (p==NULL)return false;else{q=p->next;if (q==NULL) return false;e=q->data;p->next=q->next;if (p->next!=NULL) p->next->prior=p;free(q);return true;}}void Sort(DLinkList *&head) //双链表元素排序{DLinkList *p=head->next,*q,*r;if (p!=NULL){r=p->next;p->next=NULL;p=r;while (p!=NULL){r=p->next;q=head;while (q->next!=NULL && q->next->data<p->data)q=q->next;p->next=q->next;if (q->next!=NULL) q->next->prior=p;q->next=p;p->prior=q;p=r;}}}//文件名:exp2-3.cpp#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct DNode //定义双链表结点类型{ElemType data;struct DNode *prior;struct DNode *next;} DLinkList;extern void InitList(DLinkList *&L);extern void DestroyList(DLinkList *&L);extern bool ListEmpty(DLinkList *L);extern int ListLength(DLinkList *L);extern void DispList(DLinkList *L);extern bool GetElem(DLinkList *L,int i,ElemType &e); extern int LocateElem(DLinkList *L,ElemType e);extern bool ListInsert(DLinkList *&L,int i,ElemType e); extern bool ListDelete(DLinkList *&L,int i,ElemType &e); void main(){DLinkList *h;ElemType e;printf("双链表的基本运算如下所示:\n");printf("(1)初始化双链表h\n");InitList(h);printf("(2)依次采用尾插法插入a,b,c,d,e元素\n");ListInsert(h,1,'a');ListInsert(h,2,'b');ListInsert(h,3,'c');ListInsert(h,4,'d');ListInsert(h,5,'e');printf("(3)输出双链表h:");DispList(h);printf("(4)双链表h长度=%d\n",ListLength(h));printf("(5)双链表h为%s\n",(ListEmpty(h)?"空":"非空"));GetElem(h,3,e);printf("(6)双链表h的第3个元素=%c\n",e);printf("(7)元素a的位置=%d\n",LocateElem(h,'a'));printf("(8)在第4个元素位置上插入f元素\n");ListInsert(h,4,'f');printf("(9)输出双链表h:");DispList(h);printf("(10)删除h的第3个元素\n");ListDelete(h,3,e);printf("(11)输出双链表h:");DispList(h);printf("(12)释放双链表h\n");DestroyList(h);}六．运行结果及分析：实验2.2实验2.3。

大学数据结构实验报告课程名称数据结构实验第（四）次实验实验名称链表的基本操作学生姓名于歌专业班级学号实验成绩指导老师（签名）日期2018年10月01日一、实验目的1. 学会定义单链表的结点类型，实现对单链表的一些基本操作和具体的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。

2. 掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。

二、实验要求1．预习C语言中结构体的定义与基本操作方法。

2．对单链表的每个基本操作用单独的函数实现。

3．编写完整程序完成下面的实验内容并上机运行。

4．整理并上交实验报告。

三、实验内容：1．编写程序完成单链表的下列基本操作：（1）初始化单链表La（2）在La中插入一个新结点（3）删除La中的某一个结点（4）在La中查找某结点并返回其位置（5）打印输出La中的结点元素值（6）清空链表（7）销毁链表2 .构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、Lb合并成一个有序单链表Lc。

四、思考与提高：1．如果上面实验内容2中合并的表内不允许有重复的数据该如何操作？2．如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb，Lc，使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点？五、实验设计1．编写程序完成单链表的下列基本操作：（1）初始化单链表LaLinkList InitList(){int i,value,n;LinkList H=(LinkList)malloc(sizeof(LNode));LinkList P=H;P->next=NULL;do{printf("请输入链表的长度:");scanf("%d",&n);if(n<=0)printf("输入有误请重新输入！\n");}while(n<=0);printf("请输入各个元素:\n");for(i=0; i<n; i++){scanf("%d",&value);LinkList NEW = (LinkList)malloc(sizeof(LNode)); NEW->data=value;P->next=NEW;NEW->next=NULL;P=NEW;}printf("链表建立成功！\n");return H->next;}（2）在La中插入一个新结点LinkList InsertList(LinkList L,int i,ElemType value) {LinkList h,q,t=NewLNode(t,value);int x=0;h=q=L;if(i==1)t->next=h, h=t;else{while(x++<i-2)q=q->next;t->next=q->next;q->next=t;}printf("插入成功！\n");return h;}（3）删除La中的某一个结点LinkList DeleteList(LinkList L,int i){LinkList h,q,de;int x=0;h=q=L;int t;if(i==1)h=h->next;else{while(x++<i-2)q=q->next;de=q->next;if(de->next==NULL)q->next=NULL;elseq->next=de->next;}printf("删除成功！\n");return h;}（4）在La中查找某结点并返回其位置Status LocateList(LinkList L,ElemType value){LinkList q=L;int i=0,t;while(q!=NULL){i++;if(q->data==value){printf("该结点在链表中的位置为第%d个\n",i); return OK;}q=q->next;}printf("该链表中没有该结点！\n");return ERROR;}（5）打印输出La中的结点元素值Status Print(LinkList L){LinkList q=L;printf("该链表的每个元素为:\n");while(q!=NULL){printf("%8d",q->data);q=q->next;}printf("\n");return OK;}（6）清空链表LinkList EmptyList(LinkList L){free(L->data);L->next=NULL;printf("清空成功！\n");return L;}（7）销毁链表LinkList FreeList(LinkList L){printf("释放成功！\n");free(L);}（8）主函数int main(){LinkList L=InitList();int n,i,j;Pr();scanf("%d",&n);while(n>0&&n<7){switch(n){case 1:printf("请输入要插入的结点的值和插入的位置:"); scanf("%d %d",&i,&j);InsertList(L,j,i);break;case 2:printf("请输入要删除的结点的位置:");scanf("%d",&i);DeleteList(L,i);break;case 3:printf("请输入要查找的结点的值:");scanf("%d",&i);LocateList(L,i);break;case 4:Print(L);break;case 5:EmptyList(L);break;case 6:FreeList(L);break;}Pr();scanf("%d",&n);}if(n==7)printf("退出成功！");return 0;}2．构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、Lb合并成一个有序单链表LcLinkList ConnectList(LinkList La,LinkList Lb){LinkList Lc,a,b,c;a=La;b=Lb;if(La->data<Lb->data)Lc=La,a=a->next;elseLc=Lb,b=b->next;c=Lc;while(a!=NULL||b!=NULL){if(a==NULL)c->next=b,break;if(b==NULL)c->next=a;break;if(a->data<b->data)c->next=a,a=a->next,c=c->next;elsec->next=b,b=b->next,c=c->next;return Lc;}3．如果上面实验内容2中合并的表内不允许有重复的数据该如何操作LinkList ConnectList(LinkList La,LinkList Lb){int i=1;LinkList Lc,a,b,c,q,p;a=La;b=Lb;if(La->data<Lb->data)Lc=La;a=a->next;elseLc=Lb;b=b->next;c=Lc;while(a!=NULL||b!=NULL){if(a==NULL)c->next=b，break;if(b==NULL)c->next=a，break;if(a->data<b->data)c->next=a，a=a->next，c=c->next;elsec->next=b，b=b->next，c=c->next;}c=Lc;q=c->next;while(q!=NULL){if(c->data==q->data){c->next=q->next;}c=c->next;q=c->next;}return Lc;}4．如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb，Lc，使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点？Status PartList(LinkList Lc){int n1=0,n2=0;LinkList La,Lb,L;LinkList a,b;L=Lc;while(L!=NULL){if(L->data%2==0){if(n1==0){a=La=L;L=L->next;}else{a->next=L;L=L->next;}}else{if(n2==0){b=Lb=L;L=L->next;}else{b->next=L;L=L->next;}}}a->next=NULL;b->next=NULL;return OK;}六、实验测试1．编写程序完成单链表的下列基本操作：七、总结附录1：源代码#include<stdio.h>#include<stdlib.h>#define OK 1#define ERROR 0#define OVERFLOW -2typedef int ElemType;typedef int Status;typedef struct LNode{ElemType data;struct LNode *next;} LNode,*LinkList;LinkList NewLNode(LNode *P,ElemType data){P = (LNode *)malloc(sizeof(LNode));P->data = data;P->next = NULL;return P;}LinkList InitList(){int i,value,n;LinkList H=(LinkList)malloc(sizeof(LNode));LinkList P=H;P->next=NULL;do{printf("请输入链表的长度:");scanf("%d",&n);if(n<=0)printf("输入有误请重新输入！\n");}while(n<=0);printf("请输入各个元素:\n");for(i=0; i<n; i++){scanf("%d",&value);LinkList NEW = (LinkList)malloc(sizeof(LNode)); NEW->data=value;P->next=NEW;NEW->next=NULL;P=NEW;}printf("链表建立成功！\n");return H->next;}LinkList InsertList(LinkList L,int i,ElemType value) {LinkList h,q,t=NewLNode(t,value);int x=0;h=q=L;if(i==1){t->next=h;h=t;}else{while(x++<i-2)q=q->next;t->next=q->next;q->next=t;}printf("插入成功！\n");return h;}LinkList DeleteList(LinkList L,int i){LinkList h,q,de;int x=0;h=q=L;int t;if(i==1)h=h->next;else{while(x++<i-2)q=q->next;de=q->next;if(de->next==NULL)q->next=NULL;elseq->next=de->next;}printf("删除成功！\n");return h;}Status LocateList(LinkList L,ElemType value){LinkList q=L;int i=0,t;while(q!=NULL){i++;if(q->data==value){printf("该结点在链表中的位置为第%d个\n",i); return OK;}q=q->next;}printf("该链表中没有该结点！\n");return ERROR;}Status Print(LinkList L){LinkList q=L;printf("该链表的每个元素为:\n");while(q!=NULL){printf("%8d",q->data);q=q->next;}printf("\n");return OK;}LinkList EmptyList(LinkList L){free(L->data);L->next=NULL;printf("清空成功！\n");return L;}LinkList FreeList(LinkList L){printf("释放成功！\n");free(L);}void Pr(){printf("\n1.插入新结点\n");printf("2.删除链表中的结点\n");printf("3.查找结点\n");printf("4.输出链表\n");printf("5.清空链表\n");printf("6.销毁链表\n");printf("7.退出\n");printf("请输入要使用的功能:");}int main(){LinkList L=InitList();int n,i,j;Pr();scanf("%d",&n);while(n>0&&n<7){switch(n){case 1:printf("请输入要插入的结点的值和插入的位置:"); scanf("%d %d",&i,&j);InsertList(L,j,i);break;case 2:printf("请输入要删除的结点的位置:");scanf("%d",&i);DeleteList(L,i);break;case 3:printf("请输入要查找的结点的值:");scanf("%d",&i);LocateList(L,i);break;case 4:Print(L);break;case 5:EmptyList(L);break;case 6:FreeList(L);break;}Pr();scanf("%d",&n);}if(n==7)printf("退出成功！"); return 0;}。

实验一：实现单链表各种基本运算的算法一、 实验目的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 ListDelete(LinkList *&L,int i,ElemType &e)在单链表L 中删除第i 个元素……5、exp2_2.cpp程序文件简介：(1)初始化单链表h: InitList(h);(2)依次采用尾插法插入a,b,c,d,e元素：ListInsert(h,1,'a');ListInsert(h,2,'b');ListInsert(h,3,'c');ListInsert(h,4,'d');ListInsert(h,5,'e');(3)输出单链表h: DispList(h);(4)单链表h长度：ListLength(h)(5)判断单链表h 是否为空：ListEmpty(h)?"空":"非空"(6)查找单链表h的第3个元素：GetElem(h,3,e);(7)查找元素f的位置：LocateElem(h,'f')(8)在第4个元素位置上插入f元素：ListInsert(h,4,'f');(9)输出单链表h：DispList(h);(10)删除h的第3个元素：ListDelete(h,3,e);(11)输出单链表h：DispList(h);(12)释放单链表h：DestroyList(h);6、oj2-2的项目的模块结构：在文件algo2-2中，1.定义单链表结构类型；2.初始化单链表3.定义释放单链表的函数4.定义判断单链表是否为空的函数5.定义返回单链表元素个数的函数6.定义输出单链表的函数7.定义获取第i个元素的函数8.定义查找元素的函数9.定义插入元素的函数10.定义删除元素的函数在文件exp2-2中分别调用algo2-2中所定义的函数 函数调用关系图。