长沙理工大学数据结构链表的实现及应用实验报告

数据结构单链表实验报告实验目的：掌握单链表的基本操作，学会使用单链表实现各种算法。

实验内容：实现单链表的基本操作，包括创建、插入、删除、访问等。

利用单链表完成以下算法：- 单链表逆序- 查找单链表中的中间节点- 删除单链表中的倒数第K个节点- 合并两个有序单链表为一个有序单链表实验步骤：1. 创建单链表在创建单链表时，先定义一个结构体Node来表示链表中的节点，节点包括数据域和指针域，指针域指向下一个节点。

然后，用指针p指向链表的头节点，将头节点的指针域初始化为NULL。

2. 插入节点在单链表中插入节点的操作分为两种情况：- 在链表头插入节点- 在链表中间或尾部插入节点无论是哪种情况，先将新节点的指针域指向要插入的位置的下一个节点，再将要插入的位置的指针域指向新节点即可。

3. 删除节点删除链表节点的操作同样分为两种情况：- 删除头节点- 删除中间或尾部节点要删除头节点，先用一个指针将头节点指向的下一个节点保存起来，再将头节点释放掉。

要删除中间或尾部节点，先用一个指针指向要删除节点的前一个节点，然后将指向要删除节点的前一个节点的指针域指向要删除节点的下一个节点，最后将要删除的节点释放掉。

4. 单链表逆序单链表逆序可以使用三个指针来完成，分别为pre指针、cur指针和next指针。

首先将pre指针和cur指针指向NULL，然后循环遍历链表，将cur指针指向当前节点，将next指针指向当前节点的下一个节点，然后将当前节点的指针域指向pre指针，最后将pre指针和cur指针向前移动一个节点，继续进行循环。

5. 查找单链表中的中间节点查找单链表中的中间节点可以使用双指针法，将两个指针p1和p2都指向链表头，然后p1每次向前移动一个节点，而p2每次向前移动两个节点，当p2指向了链表尾部时，p1指向的节点即为中间节点。

6. 删除单链表中的倒数第K个节点删除单链表中的倒数第K个节点可以使用双指针法，在链表中定义两个指针p1和p2，p1指向链表头，p2指向第K个节点，然后p1和p2同时向前移动，直到p2指向链表尾部，此时p1指向的节点即为要删除的节点。

数据结构实验报告2一、实验目的本次数据结构实验旨在通过实际操作和编程实践，深入理解和掌握常见的数据结构，如链表、栈、队列、树等，并能够运用所学知识解决实际问题，提高编程能力和算法设计能力。

二、实验环境本次实验使用的编程语言为C+＋，开发环境为Visual Studio 2019。

三、实验内容（一）链表的实现与操作1、单向链表的创建首先，定义了链表节点的结构体，包含数据域和指向下一个节点的指针域。

然后，通过函数实现了单向链表的创建，从用户输入获取节点的数据，依次创建新节点并连接起来。

2、链表的遍历编写函数实现对单向链表的遍历，依次输出每个节点的数据。

3、链表的插入与删除实现了在指定位置插入节点和删除指定节点的功能。

插入操作时，需要找到插入位置的前一个节点，修改指针完成插入。

删除操作时，同样找到要删除节点的前一个节点，修改指针并释放删除节点的内存。

（二）栈的实现与应用1、栈的基本操作使用数组实现了栈的数据结构，包括入栈、出栈、判断栈空和获取栈顶元素等操作。

2、表达式求值利用栈来实现表达式求值的功能。

将表达式中的数字和运算符分别入栈，按照运算规则进行计算。

（三）队列的实现与应用1、队列的基本操作使用循环数组实现了队列，包括入队、出队、判断队空和队满等操作。

2、模拟银行排队系统通过创建队列来模拟银行客户的排队情况，实现客户的入队和出队操作，统计平均等待时间等。

（四）二叉树的遍历1、二叉树的创建采用递归的方式创建二叉树，用户输入节点数据，构建二叉树的结构。

2、先序、中序和后序遍历分别实现了二叉树的先序遍历、中序遍历和后序遍历，并输出遍历结果。

四、实验结果与分析（一）链表实验结果成功创建、遍历、插入和删除单向链表。

通过对链表的操作，深入理解了链表的动态存储特性和指针的运用。

在插入和删除操作中，能够正确处理指针的修改和内存的释放，避免了内存泄漏和指针错误。

（二）栈实验结果栈的基本操作运行正常，能够正确实现入栈、出栈等功能。

大学数据结构实验报告课程名称数据结构实验第（四）次实验实验名称链表的基本操作学生姓名于歌专业班级学号实验成绩指导老师（签名）日期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;}。

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

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

对于线性表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。

数据结构第二章实验报告一、实验目的数据结构第二章主要涉及线性表的相关知识，本次实验的目的在于通过实际操作和编程实现，深入理解线性表的概念、存储结构以及基本操作，巩固所学的理论知识，并提高编程能力和问题解决能力。

二、实验环境本次实验使用的编程语言为C+＋，编程环境为Visual Studio 2019。

三、实验内容（一）顺序表的实现顺序表是一种用顺序存储方式实现的线性表。

在实验中，我们定义了一个结构体来表示顺序表，包括存储数据的数组和表示表长度的变量。

实现了顺序表的初始化、插入、删除、查找等基本操作。

（二）链表的实现链表是一种通过指针链接实现的线性表。

我们分别实现了单向链表和双向链表。

在单向链表中，每个节点包含数据和指向下一个节点的指针；双向链表则在此基础上增加了指向前一个节点的指针，使得链表的操作更加灵活。

（三）线性表的应用运用实现的线性表解决了一些实际问题，如数据排序、查找特定元素等。

四、实验步骤（一）顺序表的实现步骤1、定义顺序表结构体，包括数据数组和长度变量。

2、实现顺序表的初始化函数，将长度初始化为 0。

3、插入操作：首先判断表是否已满，如果未满，在指定位置插入元素，并将后续元素后移。

4、删除操作：首先判断指定位置是否合法，然后将该位置元素删除，并将后续元素前移。

5、查找操作：遍历表中的元素，找到目标元素返回其位置，否则返回－1。

（二）链表的实现步骤1、单向链表定义单向链表节点结构体，包含数据和指向下一个节点的指针。

实现链表的初始化函数，创建头节点。

插入操作：分为头插法和尾插法，根据插入位置的不同选择相应的方法。

删除操作：找到要删除的节点，将其前后节点连接起来，释放删除节点的内存。

查找操作：遍历链表，找到目标元素返回节点指针，否则返回NULL。

2、双向链表定义双向链表节点结构体，包含数据、指向前一个节点和指向下一个节点的指针。

初始化函数与单向链表类似，但需要同时处理前后指针。

插入和删除操作：在单向链表的基础上，同时更新前后节点的指针。

实验报告年级班号学号实验名称：栈的实现及其应用：算术表达式的计算实验日期2016年12月2日计算机科学与技术系2016年制一、实验环境32位操作系统下的Window平台Microsoft Visual C++二、实验目的掌握栈的实现及使用三、实验容1.实现栈的存储结构2.实现栈的基本操作的有关算法3.利用栈解决*算术表达式求值问题四、数据结构与算法思想描述顺序读取中缀表达式：1、当遇到数字时，将数字入数字栈2、当遇到操作符时，与操作符栈栈顶比较：If(当前操作符优先级大于操作符栈栈顶的优先级)If(非”)”操作符)将当前操作符进操作符栈;ElseWhile(操作符栈栈顶不等于”(“)取操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;ElseIf(非(“操作符)While(操作符栈栈顶不等于”(“)取操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;Continue;(直到当前操作符比栈顶操作符优先级大)Else将当前操作符进操作符栈;3、While(操作符栈非空)操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;4、在数字栈取最后结果并输出。

五、程序清单//10*8^2+16.3+5*(5.2*5+3.01)/4-(-10)+0.1000060+4.00416-40 = 666.666666 //100+(-100)-(-10^2) = 100//(((2016-2017+(((2015-2014)))))) = 0//-1+(((((((((1^0))))))))+100%10^2 = 0#include<iostream>#include<stdio.h>#include<math.h>#include<string.h>#include<iomanip>#include<map>using namespace std;const int MAX = 105;typedef double Type;typedef struct{Type TypeStack[MAX];char charStack[MAX];int TypeTop, charTop;}Stack;//初始化栈void InitStack(Stack *S){S->charTop = S->TypeTop = 0; }//判断charStack是否为空bool IsEmpty_Char(Stack S){return S.charTop == 0;}//判断TypeStack是否为空bool IsEmpty_Type(Stack S){return S.TypeTop == 0;}//判断charStack是否为满bool IsFull_Char(Stack S){return S.charTop == MAX;}//判断TypeStack是否为满bool IsFull_Type(Stack S){return S.TypeTop == MAX;}void Push_Char(Stack *S, char ch){//charStack不为满则入栈，否则输出提示if(!IsFull_Char(*S))S->charStack[S->charTop++] = ch;elsecout << " The CharStack Is Full! " << endl; }void Push_Type(Stack *S, Type a){//TypeStack不为满则入栈，否则输出提示if(!IsFull_Type(*S))S->TypeStack[S->TypeTop++] = a;elsecout << " The TypeStack Is Full! " << endl; }char Pop_Char(Stack *S){if(!IsEmpty_Char(*S)){S->charTop--;return S->charStack[S->charTop];}elsecout << " The CharStack Is Empty! " << endl;return -1;}Type Pop_Type(Stack *S){if(!IsEmpty_Type(*S)){S->TypeTop--;return S->TypeStack[S->TypeTop];}elsecout << " The TypeStack Is Empty! " << endl;return -1;}char Top_Char(Stack S){if(!IsEmpty_Char(S))return S.charStack[--S.charTop];elsecout << " The CharStack Is Empty! " << endl;return -1;}Type Top_Type(Stack S){if(!IsEmpty_Type(S))return S.TypeStack[--S.TypeTop];elsecout << " The TypeStack Is Empty! " << endl;return -1;}Type Calculate(Type left, Type right, char op){Type value = 0;switch(op){case '+': value = left + right; break;case '-': value = left - right; break;case '*': value = left * right; break;case '/': if(right != 0)value = left / right;elsecout << "被除数不能为零!" << endl;break;case '%': i f(right != 0)value = (int)left % (int)right;elsecout << "被余数不能为零!" << endl;break;case '^': value = pow(left,right);/*value = 1;if(right >= 0)while(right--)value *= left;else{right = -right;while(right--)value /= left;}*/}return value;}void Computer(char *mid_equotion, Type len){Type right, left , result;char *p_mid_equotion = mid_equotion;char after_equotion = ' ';map<char,Type> Oper;Oper['#'] = 1; Oper['('] = 2; O per['+'] = 3;Oper['-'] = 3; O per['*'] = 4; Oper['/'] = 4;Oper['%'] = 4; Oper['^'] = 5; Oper[')'] = 6;Stack MyStack;InitStack(&MyStack);Push_Char(&MyStack,'#');char top_oper, current_oper;for(;*p_mid_equotion != '\0';){top_oper = Top_Char(MyStack);current_oper = *p_mid_equotion;if(!Oper[current_oper]){Push_Type(&MyStack,strtod(p_mid_equotion, &p_mid_equotion));continue;}//end ifelse //为操作符{if(Oper[current_oper] > Oper[top_oper]){if(current_oper != ')')Push_Char(&MyStack,current_oper);else{while(top_oper != '('){right = Pop_Type(&MyStack);if(!IsEmpty_Type(MyStack))left = Pop_Type(&MyStack);elseleft = 0;Push_Type(&MyStack,Calculate(left, right, Top_Char(MyStack)));Pop_Char(&MyStack);top_oper = Top_Char(MyStack);}Pop_Char(&MyStack);}//end else}//end ifelse{if(current_oper == '('){Push_Char(&MyStack,current_oper);if(*(p_mid_equotion + 1) == '-')Push_Type(&MyStack,0);}else{right = Pop_Type(&MyStack);if(!IsEmpty_Type(MyStack))left = Pop_Type(&MyStack);elseleft = 0;Push_Type(&MyStack,Calculate(left, right, top_oper));Pop_Char(&MyStack);continue;}}//end else}//end elsep_mid_equotion++;}//end fortop_oper = Pop_Char(&MyStack);while(top_oper != '#'){right = Pop_Type(&MyStack);if(!IsEmpty_Type(MyStack))left = Pop_Type(&MyStack);elseleft = 0;Push_Type(&MyStack,Calculate(left, right, top_oper));top_oper = Pop_Char(&MyStack);}// cout << setprecision(6) << "\nThe Result = " << (result = Pop_Type(&MyStack)) << endl;printf("The Result = %lf\n\n",(result = Pop_Type(&MyStack)));}int main(){char s[MAX] = "";Type i = 0;cout << "请输入你要求值的表达式!(以-1结束)\n";while(cin >> s && strcmp(s,"-1") != 0){Computer(s,strlen(s));cout << "请输入你要求值的表达式!(以-1结束)\n";}return 0;}六、程序执行结果及其分析对“+” , “-” , “*” , “/” , “%” , “^”运算的实现可运算多位数和小数，求余，求平方，括号里包含负数如（-1），及首个数字为负数如-1+1。

数据结构单链表实验报告一、实验目的本实验的目的是通过设计和实现单链表数据结构，加深对于单链表的理解和掌握，并能够灵活应用单链表解决实际问题。

二、实验内容1·理解单链表的概念和基本操作2·设计并实现单链表数据结构3·实现单链表的创建、插入、删除和查找操作4·应用单链表解决实际问题三、实验步骤1·理解单链表的概念和基本操作单链表是一种常见的线性链表结构，它由多个节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

单链表的基本操作包括创建链表、插入节点、删除节点和查找节点等。

2·设计并实现单链表数据结构首先，定义单链表节点的结构，包含数据元素和指向下一个节点的指针。

然后，定义一个链表结构，包含头节点和尾节点的指针。

3·实现单链表的创建、插入、删除和查找操作●创建链表：通过依次插入节点的方式创建一个空的链表。

●插入节点：根据插入位置，将新节点插入到链表中的适当位置。

●删除节点：根据节点的值或位置，删除链表中的对应节点。

●查找节点：根据节点的值或位置，在链表中查找对应节点。

4·应用单链表解决实际问题通过设计和实现单链表数据结构，应用单链表解决实际问题，如实现一个通讯录、一个待办事项列表等。

四、实验结果根据实验步骤，我们成功设计并实现了单链表数据结构，并应用单链表解决了实际问题。

经过测试，单链表的创建、插入、删除和查找操作均正常工作。

五、实验总结通过本次实验，我们深入学习了单链表的概念和基本操作。

通过设计和实现单链表数据结构，并应用单链表解决实际问题，加深了对于单链表的理解和掌握。

六、附件本实验报告涉及的附件包括实验代码和测试数据。

七、法律名词及注释1·数据结构：数据结构是计算机存储、组织数据的方式，是程序设计和算法设计的基础。

2·单链表：单链表是一种常见的线性链表结构，它由多个节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

实验链表实验报告一、实验目的本次实验的主要目的是深入理解链表这种数据结构的概念、特点和操作方法，并通过实际编程实现来提高对链表的应用能力。

二、实验环境本次实验使用的编程语言为C+＋，开发工具为Visual Studio 2019。

三、实验原理链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

与数组不同，链表的内存分配是动态的，并且可以方便地进行插入和删除操作，而不需要移动大量的元素。

链表分为单向链表、双向链表和循环链表等多种类型。

在本次实验中，我们主要实现单向链表。

单向链表的节点结构通常包含数据域和指针域。

数据域用于存储节点的数据，指针域用于指向下一个节点。

通过遍历链表的指针，可以访问链表中的每个节点。

四、实验内容1、链表节点的定义｀｀｀cppstruct ListNode ｛int data;ListNode next;ListNode(int x) ： data(x)， next(NULL) ｛｝｝；｀｀｀2、链表的创建｀｀｀cppListNode createList(）｛ListNode head ＝ NULL;ListNode tail ＝ NULL;int num;cout ＜＜＂请输入链表中的数字（输入－1 结束）：＂；cin ＞＞ num;while （num!＝－1) ｛ListNode newNode ＝ new ListNode(num)；if （head ＝＝ NULL) ｛head ＝ newNode;tail ＝ newNode;｝ else ｛tail>next ＝ newNode;tail ＝ newNode;｝cin ＞＞ num;｝return head;｝｀｀｀3、链表的遍历｀｀｀cppvoid traverseList(ListNode head) ｛ListNode curr ＝ head;while （curr!＝ NULL) ｛cout ＜＜ curr>data ＜＜＂＂；curr ＝ curr>next;｝cout ＜＜ endl;｝｀｀｀4、链表的插入｀｀｀cppvoid insertNode(ListNode& head, int position, int value) ｛ListNode newNode ＝ new ListNode(value)；if （position ＝＝ 0) ｛newNode>next ＝ head;head ＝ newNode;return;｝ListNode curr ＝ head;int count ＝ 0;while （curr!＝ NULL ＆＆ count ＜ position 1) ｛curr ＝ curr>next;count+＋；｝if （curr ＝＝ NULL) ｛cout ＜＜＂插入位置超出链表长度" ＜＜ endl; return;｝newNode>next ＝ curr>next;curr>next ＝ newNode;｝｀｀｀5、链表的删除｀｀｀cppvoid deleteNode(ListNode& head, int position) ｛if （head ＝＝ NULL) ｛cout ＜＜＂链表为空，无法删除" ＜＜ endl; return;｝if （position ＝＝ 0) ｛ListNode temp ＝ head;head ＝ head>next;delete temp;return;｝ListNode curr ＝ head;ListNode prev ＝ NULL;int count ＝ 0;while （curr!＝ NULL ＆＆ count ＜ position) ｛prev ＝ curr;curr ＝ curr>next;count+＋；｝if （curr ＝＝ NULL) ｛cout ＜＜＂删除位置超出链表长度" ＜＜ endl; return;｝prev>next ＝ curr>next;delete curr;｝｀｀｀五、实验结果通过对上述链表操作函数的调用，我们成功地创建、遍历、插入和删除了链表中的节点。

计算机科学与技术系实验报告专业名称计算机科学与技术课程名称《数据结构》项目名称链表实现学生管理班级学号姓名同组人员无实验日期一、实验目的与要求：（简述本次实验要求达到的目的，涉及到的相关知识点，实验的具体要求。

）（一）实验目的：应用链表来实现对数据的操作。

（二）实验要求：用链表实现对数据的，增，删，改，查（三）实验环境：VC++6.0.二、实验内容#include <stdio.h>#include <malloc.h>#include <string.h>#define Error 0#define OK 1typedef struct node{char name[10];char stuno[20];float score;struct node *next;}LinkList;/*置空表*/LinkList *setnull(LinkList *L){L->next = NULL;return L;}/*创建表*/LinkList *createList(){LinkList *L, *S, *H;int i = 1;L = (LinkList *) malloc (sizeof (LinkList));L->next = NULL;H = L;while(i < 5){printf("请输入第 %d 个学生的姓名，学号，成绩\n", i);S = (LinkList *) malloc (sizeof (LinkList));scanf("%s",(S->name));scanf("%s",(S->stuno));scanf("%f",&(S->score));//scanf("%s%s%f",(S->name), (S->stuno), &(S->score));/*gets(S->name);gets(S->stuno);scanf("%f",&S->score);*/S->next = NULL;H->next = S;H = S;i++;}return L;}/*链表的删除*/LinkList *deleteList(LinkList *L, char stuno[]){if(L->next == NULL){printf("此链表已经为空\n");return Error;}while(L->next != NULL){if(strcmp(L->next->stuno, stuno) == 0){L->next = L->next->next;printf("--------------------------------------------------------");printf("\n删除成功\n");printf("--------------------------------------------------------");return L;}elseL = L->next;}printf("--------------------------------------------------------");printf("\n对不起，没有找到你想要删除的学号，删除失败。