目录
1 选题背景 (1)
2 方案与论证 (1)
2.1 链表的概念和作用 (1)
2.2 实验的基本要求(软硬件) (1)
2.3 算法的设计思想 (1)
2.4 相关图例 (2)
2.4.1 单链表的结点结构 (2)
2.4.2 算法流程图 (2)
3 过程论述 (3)
3.1 链表的建立 (3)
3.2 取出链表中的元素 (4)
3.3 插入元素 (4)
3.4 删除元素 (5)
3.5 查找元素 (6)
4 结果分析 (6)
4.1 单链表的结构 (6)
4.2 单链表 (6)
4.2.1 顺链操作技术 (6)
4.2.2 指针保留技术 (7)
5 结论与总结 (7)
参考文献 (8)
附录代码: (9)
数据结构课程设计
1 选题背景
陈火旺院士把计算机60多年的发展成就概括为五个“一”:开辟一个新时代----信息时代,形成一个新产业----信息产业,产生一个新科学----计算机科学与技术,开创一种新的科研方法----计算方法,开辟一种新文化----计算机文化,这一概括深刻影响了计算机对社会发展所产生的广泛而深远的影响。
数据结构和算法是计算机求解问题过程的两大基石。著名的计算机科学家P.Wegner指出,“在工业革命中其核心作用的是能量,而在计算机革命中其核心作用的是信息”。计算机科学就是“一种关于信息结构转换的科学”。信息结构(数据结构)是计算机科学研究的基本课题,数据结构又是算法研究的基础。
2 方案与论证
2.1 链表的概念和作用
链表是一种链式存储结构,链表属于线性表,采用链式存储结构,也是常用的动态存储方法。为了克服顺序表的缺陷,可以采用链式方式存储线性表。通常将采用链式存储结构的线性表称为线性链表。单链表的结构包括数据域和指针域,这两部分总称为结点(Node)。单链表中每个结点的存储地址放在其前驱结点的指针域中,由于线性表中的第一个结点无前驱,所以应设一个头指针H指向第一个结点。由于线性表的最后一个节点没有直接后继,则制定单链表的最后一个结点的指针域为空(NULL)。它可以和随意的在其任意一个位置进行插入和删除操作,这对于动态的数据处理十分的有利。利用头插建立一个带头结点的单链表,并用算法实现该单链表的插入、删除查找、输出、求前驱和后继、再把此单链表逆置,然后在屏幕上显示每次操作的结果当所有操作完成后能撤销该单链表。
2.2 实验的基本要求(软硬件)
用VC++6.0软件平台,操作系统:Windows XP 硬件:内存要求:内存大小在256MB,其他配置一般就行。
2.3 算法的设计思想
(1)定义一个创建链表的函数,通过该函数可以创建一个链表,并为下面的函数应用做好准备。
(2)定义输出链表的算法,通过对第一步已经定义好的创建链表函数的调用,在这一步通过调用输出链表的函数算法来实现对链表的输出操作。
链表操作
(3)定义一个遍历查找的算法,通过此算法可以查找到链表中的每一个节点是否存在。
(4)定义查找链表的每一个前驱和后继,通过定义这个算法,可以很容易的实现对链表的前驱和后继的查找工作。
(5)定义插入节点的算法,通过定义这个算法,并结合这查找前驱和后继的算法便可以在连链表的任意位置进行插入一个新节点。
(6)定义删除节点的操作,这个算法用于对链表中某个多余节点的删除工作。
2.4 相关图例
2.4.1 单链表的结点结构
如图2-1所示,为单链表的结点结构示意图:
Data域 Next域
图2-1 单链表的结点结构
2.4.2 算法流程图
如图2-2所示,为此算法流程图:
定义结构体node
构建各种对联表操作的函数(插入、删除、
查找、输出),并写出相应的算法及实现
过程
创建一个单链表,用于之前所定义的函数
对其进行操作
按要求输出结果
结束
图2-2 算法流程图
数据结构课程设计
3 过程论述
3.1 链表的建立
图 3-1 链表的建立
图 3-2 建立链表并打印链表中的元素
链表操作
3.2 取出链表中的元素
图3-3 取出链表中的元素3.3 插入元素
图3-4 插入元素
数据结构课程设计
3.4 删除元素
图3-5 删除元素
图3-6 删除元素后打印链表
链表操作
3.5
查找元素
图3-7 查找位置为6的元素
4 结果分析
4.1 单链表的结构
一般情况下,使用链表,只关心链表中结点间的逻辑顺序,并不关心每个结点的实际存储位置,因此通常情况下用箭头来表示链域中的指针,于是链表就可以更直观的画成用箭头链接起来的结点序列,如下图所示:
H
图4-1 单链表的示例图 4.2 单链表
4.2.1 顺链操作技术
从“头”开始,访问单链表L 中的结点i (p 指向该节点)时,由于第i 个结点的地址在第i-1个结点(pre 指向该结点,为p 的前驱)的指针域中存放,查找必须从单链表的“首结点”开始(p=L );通过p=p->next 并辅助计数器来实现。
A B C
D E ^
数据结构课程设计
4.2.2 指针保留技术
通过对第i个结点进行插入、删除等操作时,需要对第i-1个结点的指针域进行链址操作(pre->next),因此在处理过程中始终需要维持当前指针p与其前驱指针pre的关系,将这种技术称为“指针保留技术”。
5 结论与总结
通过这十几天的时间,最后终于完成了这次数据结构课程设计任务,内心激动的同时,也是十分的辛苦的,从选题、审题、查资料到开始构思,这个过程是最慢的,也是最难的。通过这次的课程设计,我们对数据结构中单链表的应用有了更深的理解,并且使我们深刻的认识到实践的重要性,只有理论与实践相结合才能达到很好的学习效果,学到很多东西,同时也发现仅仅书本的知识是远远不够的,需要把知识运用到实践中去,能力才能得到提高。由于刚开始对单链表的应用总体结构不熟悉,对书本知识的学习不够扎实,刚拿到题目的时候,还不好下手,就请教了一些学习成绩好一点的同学,并认真查找了一些资料,才对这次课程设计有了初步的了解。
根据对数据结构的了解,我们觉得我们对单链表的认识要深一点。因此我们选择了单链表的实验,作为线性表的一种存储结构,它的特点是可以从分利用存储单元来存储数据,并且可以方便的实现对数据进行插入、删除、输出等操作。在我们进行课程设计时,虽然在大体上算法是正确的,但时常会出现一些小问题,使我们不得不花一些时间来查找、修改错误。
通过这次课程设计,让我们充分认识到数据结构在编写程序方面的重要地位。由于我们在课程设计中编写的是对单链表的基本操作,因此我们在这次课程设计中收获了很多关于单链表的应用方面的知识。由于课程设计的题目还有很多,因此没有对其他的题目进行深入的了解而感到遗憾,因此我们希望在以后的学习过程中,能够多多的学习这方面没知识来弥补不足。
最后,通过本次数据结构课设,我学会了如何与别人共同探讨、解决问题;当发现问题时,能学会利用身边一切资料,包括图书、网上资料等等来解决问题,并最终完成任务。
链表操作
参考文献
[1]耿国华.数据结构--用C语言描述[M].北京:高等教育出版社,2011.6.
[2]谭浩强.C程序设计[M].北京:清华大学出版社,2004.6.
数据结构课程设计
附录代码:
#include
#include
typedef struct node//定义node结点
{
int data;
struct node *next;
}linklist;
void setnull(linklist *H)//清空单链表
{
H->next=NULL;
}
void creatlist(linklist *H)//创建单链表
{
linklist *p,*s;int x;
p=H;
printf("please input x:");
scanf("%d",&x);
while(x!=-1){
s=(linklist *)malloc(sizeof(linklist)); s->data=x;
s->next =p->next;
p->next =s;
p=p->next ;
printf("please input x:");
scanf("%d",&x);
}
p->next=NULL ;
}
链表操作
void Leng(linklist *H)//求单链表长度
{
linklist *p;
int k;
p=H;k=0;
while(p->next!=NULL){
p=p->next;
k++;
}
printf("The linklist is:%d\n",k);
}
int GetElem(linklist *H,int i)//取单链表中的某个元素
{
linklist *p;
int k;
p=H;k=0;
while(p->next!=NULL&&k
p=p->next;
k++;
}
if(k==i&&p!=NULL)
printf("i position data is %d\n",p->data);
else
printf("No find!\n");
}
void Insert(linklist *H,int i,int x)//向单链表中插入某个元素{
linklist *p;int k;linklist *s;
p=H;k=0;
while(p->next!=NULL&&k p=p->next;k++; } 数据结构课程设计 if(k==i-1&&p->next!=NULL){ s=(linklist *)malloc(sizeof(linklist)); s->data=x; s->next=p->next; p->next=s; } else printf("插入错误r\n"); } void Delete(linklist *H,int x)//删除元素 { linklist *p,*q;int k; p=H;k=0; while(p->next!=NULL&&p->next->data!=x){ p=p->next; k++; } if(p->next->data==x) { q=p->next; p->next=q->next; free(q); } else printf("no find!\n"); } void print(linklist *H)//输出单链表 { linklist *p;int k; p=H;k=0; if(p->next==NULL) printf("链表为空!"); 链表操作 while(p->next!=NULL){ k++; p=p->next; printf("%3d",p->data); } } int Locate(linklist *H,int x)//查找元素 { linklist *p;int k; p=H;k=0; while(p->next!=NULL&&p->data!=x){ p=p->next; k++; } if(p->data==x) printf("要查询元素的位置是%d\n",k); else printf("没有找到!\n"); } /* void destroylist(linklist *H)//销毁单链表{ H->next=NULL; H->data=NULL; } */ void main() { linklist *H;int k,x,i;int f; H=(linklist *)malloc(sizeof(linklist)); 数据结构课程设计 setnull(H); printf("\n请选择以下操作数,选择-1为结束"); printf("\n1:creatlinklist(H)"); printf("\n2:leng(H)"); printf("\n3:GetElem(H,i)"); printf("\n4:Insert(H,i,x)"); printf("\n5:Delete(H,x)"); printf("\n6:print(H)"); printf("\n7:Locate(H,x)\n"); scanf("%d",&f); while(f!=-1){ switch (f) { case 1:creatlist(H);break; case 2:Leng(H);break; case 3:printf("\n请输入要得到元素的位置:"); scanf("%d",&i); GetElem(H,i);break; case 4:printf("\n请输入的插入位置、长度以及元素:"); scanf("%d,%d",&i,&x); Insert(H,i,x);break; case 5:printf("\n请输入要删除的位置及元素:"); scanf("%d",&x); Delete(H,x);break; case 6: print(H);break; case 7:printf("请输入要查找的元素:"); scanf("%d",&x); Locate(H,x);break; } printf("\n请选择以下操作数,选择-1为结束"); printf("\n1:creatlinklist(H)"); printf("\n2:leng(H)"); printf("\n3:GetElem(H,i)"); printf("\n4:Insert(H,i,x)"); 链表操作 printf("\n5:Delete(H,x)"); printf("\n6:print(H)"); printf("\n7:Locate(H,x)\n"); scanf("%d",&f); } } 实验二链表操作实现 实验日期: 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[]);/*保存单链表到文件*/ 任务: 编写一个能向表尾插入结点,并输出链表中所有数据元素的小程序 #ifndef _LINKLIST #define _LINKLIST #include } void printList_link(PLIST head ) { /*在此处完成任务,输出head为表头的单链表数据元素*/ //begin PLIST p =new NODE; p=head->next; while(p){ printf("%d ",p->data); p=p->next; } //end } void insertDataTail(PLIST head , int insData ) { /*在此处完成任务,在head为表头的单链表表尾插入数据元素insData*/ //begin PLIST p; p=head->next; while(p->next!=NULL){ p=p->next; } PLIST q = new NODE; //初始化结点 p->next=q; q->data=insData; q->next=NULL; //end } #endif 实验一单链表 #include "stdio.h" #include "stdlib.h" typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList; void creatLNode(LinkList &head) { int i,n; LNode *p; head=(LNode*)malloc(sizeof(LNode)); head->next=NULL; printf("请输入链表的元素个数:"); scanf("%d",&n); for(i=n;i>0;i--) { p=(LNode*)malloc(sizeof(LNode)); printf("第%d个元素:",i); scanf("%d",&p->data); p->next=head->next; head->next=p; } } void InsertLNode(LinkList &L) { LNode *p=L; int i,j=0,e; printf("请输入你要插入的位置(超过链表长度的默认插在最后!):"); scanf("%d",&i); printf("请输入你要插入的元素:"); scanf("%d",&e); while (p->next&&j LNode *s; s=(LNode*)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; } int DeleteLNode(LinkList &L,int i,int &e) { LNode *p; p=L; LNode *q; int j=0; while (p->next&&j 数据结构的概念: 数据的逻辑结构+ 数据的存储结构+ 数据的操作; 数据的数值:=====》数据===》数值型数据整形浮点数ASCII 非数值型数据图片声音视频字符 =====》数据元素=====》基本项组成(字段,域,属性)的记录。 数据的结构: 逻辑结构 ----》线性结构(线性表,栈,队列) ----》顺序结构 ----》链式结构 ----》非线性结构(树,二叉树,图) ----》顺序结构 ----》链式结构 存储结构 -----》顺序存储 -----》链式存储 -----》索引存储 -----》哈希存储==散列存储 数据的操作: 增 删 改 查 DS ====》数据结构===》DS = (D,R); 数据结构中算法: 1、定义:有穷规则的有序集合。 2、特性: 有穷性 确定性 输入 输出 3、算法效率的衡量 时间复杂度计算===》算法中可执行依据的频度之和,记为:T(n)。 是时间的一种估计值不是准确值。 计算结果的分析:1 将最终结果的多项式中常数项去掉 2 只保留所有多项式中最高阶的项 3 最后的最高阶项要去掉其常数项 时间复杂度的量级关系: 常量阶====》对数阶===》线性阶===》线性对数阶====》平方阶===》立方阶===》指数阶 以上关系可以根据曲线图来判断算法对时间复杂度的要求 空间复杂度计算====》算法执行过程中所占用的存储空间的量级,记为:D(n)。 计算方法是在运行过程中申请的动态内存的量级计算。 ///////////////////////////////////////////////////////////////////////////////////////////////// 线性表 顺序存储====》顺序表(数组) 链式存储====》单链表 特征:对于非空表,a0是表头没有前驱。 an-1 是表尾没有后继 ai的每个元素都有一个直接前驱和直接后继 基本操作:创建表=====》增加元素====》删除元素====》改变元素值====》查询元素 1、顺序表的操作 1.1 创建顺序表=====》定义个指定类型的数组====》int a[100] ={0}; 目录 1 选题背景 (2) 2 方案与论证 (3) 2.1 链表的概念和作用 (3) 2.3 算法的设计思想 (4) 2.4 相关图例 (5) 2.4.1 单链表的结点结构 (5) 2.4.2 算法流程图 (5) 3 实验结果 (6) 3.1 链表的建立 (6) 3.2 单链表的插入 (6) 3.3 单链表的输出 (7) 3.4 查找元素 (7) 3.5 单链表的删除 (8) 3.6 显示链表中的元素个数(计数) (9) 4 结果分析 (10) 4.1 单链表的结构 (10) 4.2 单链表的操作特点 (10) 4.2.1 顺链操作技术 (10) 4.2.2 指针保留技术 (10) 4.3 链表处理中的相关技术 (10) 5 设计体会及今后的改进意见 (11) 参考文献 (12) 附录代码: (13) 1 选题背景 陈火旺院士把计算机60多年的发展成就概括为五个“一”:开辟一个新时代----信息时代,形成一个新产业----信息产业,产生一个新科学----计算机科学与技术,开创一种新的科研方法----计算方法,开辟一种新文化----计算机文化,这一概括深刻影响了计算机对社会发展所产生的广泛而深远的影响。 数据结构和算法是计算机求解问题过程的两大基石。著名的计算机科学家P.Wegner指出,“在工业革命中其核心作用的是能量,而在计算机革命中其核心作用的是信息”。计算机科学就是“一种关于信息结构转换的科学”。信息结构(数据结构)是计算机科学研究的基本课题,数据结构又是算法研究的基础。 2 方案与论证 2.1 链表的概念和作用 链表是一种链式存储结构,链表属于线性表,采用链式存储结构,也是常用的动态存储方法。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。 以“结点的序列”表示线性表称作线性链表(单链表) 单链表是链式存取的结构,为找第 i 个数据元素,必须先找到第 i-1 个数据元素。 因此,查找第 i 个数据元素的基本操作为:移动指针,比较 j 和 i 单链表 1、链接存储方法 链接方式存储的线性表简称为链表(Linked List)。 链表的具体存储表示为: ① 用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的,也可以是不连续的) ② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址(或位置)信息(称为指针(pointer)或链(link)) 注意: 链式存储是最常用的存储方式之一,它不仅可用来表示线性表,而且可用来表示各种非线性的数据结构。 2、链表的结点结构 ┌───┬───┐ │data │next │ └───┴───┘ data域--存放结点值的数据域 next域--存放结点的直接后继的地址(位置)的指针域(链域) 注意: ①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。 ②每个结点只有一个链域的链表称为单链表(Single Linked List)。 江南大学物联网工程学院上机报告 实验名称:实验一单链表的基本操作 实验目的 熟练掌握线性表两类存储结构的描述方法。 实验内容 从键盘读入若干个整数,建一个整数单链表,并完成下列操作: (1)打印该链表; (2)在链表中插入一个结点,结点的数据域从键盘读入,打印该链表; (3)在链表中删除一个结点,被删结点的位置从键盘读入,打印该链表; (4)在链表中做查找:从键盘读入要查找的整数,将该整数在链表中的位置打印出来,若要查找的整数不在链表中,返回一个信息。 算法设计分析 (一)数据结构的定义 单链表存储结构定义为: struct Node; typedef struct Node * pnode; struct Node { int info; pnode link; }; typedef struct Node * LinkList; (二)总体设计 程序由主函数、创建单链表函数、链表长度函数、链表打印函数、插入正整数函数、删除函数、查询函数组成。其功能描述如下: (1)主函数:调用各个函数以实现相应功能 int main(void) //主函数 { printf("单链表的基本操作实验:\n"); struct list *pnode; pnode = creat(); //创建 print(pnode); //输出 insert(pnode); //插入 print(pnode); //输出 _delete(pnode); //删除 print(pnode); //输出 _located(pnode); //查找 print(pnode); //输出 return 0 ; } (三)各函数的详细设计: Function1: struct list *creat()//创建链表; 上机实验报告 学院:计算机与信息技术学院 专业:计算机科学与技术(师范)课程名称:数据结构 实验题目:单链表建立及操作 班级序号:师范1班 学号:201421012731 学生姓名:邓雪 指导教师:杨红颖 完成时间:2015年12月25号 一、实验目的: (1)动态地建立单链表; (2)掌握线性表的基本操作:求长度、插入、删除、查找在链式存储结构上的实现; (3)熟悉单链表的应用,明确单链表和顺序表的不同。 二、实验环境: Windows 8.1 Microsoft Visual c++ 6.0 三、实验内容及要求: 建立单链表,实现如下功能: 1、建立单链表并输出(头插法建立单链表); 2、求表长; 3、按位置查找 4、按值查找结点; 5、后插结点; 6、前插结点 7、删除结点; 四、概要设计: 1、通过循环,由键盘输入一串数据。创建并初始化一个单链表。 2、编写实现相关功能函数,完成子函数模块。 3、调用子函数,实现菜单调用功能,完成顺序表的相关操作。 五、代码: #include #include if(!p||j>i-1) return; lnode *s=new lnode; s->data=e; s->next=p->next; p->next=s; }//插入 void deletelist(lnode *&head,int i,int &e){ lnode *p=head; int j=0; while(p->next&&j 课程设计(论文) 题目名称单链表的基本操作 课程名称C语言程序课程设计 学生姓名 学号 系、专业信息工程系、网络工程专业 指导教师成娅辉 2013年6月6 日 目录 1 前言 (3) 2 需求分析 (3) 2.1 课程设计目的 (3) 2.2 课程设计任务 (3) 2.3 设计环境 (3) 2.4 开发语言 (3) 3 分析和设计 (3) 3.1 模块设计 (3) 3.2 系统流程图 (4) 3.3 主要模块的流程图 (6) 4 具体代码实现 (9) 5 课程设计总结 (12) 5.1 程序运行结果 (12) 5.2 课程设计体会 (12) 参考文献 (13) 致谢 (13) 1 前言 我们这学期学习了开关语句,循环语句、链表、函数体、指针等的应用,我们在完成课程设计任务时就主要用到这些知识点,本课题是单链表的简单操作,定义四个子函数分别用来创建链表、输出链表、插入数据以及删除数据,主函数中主要用到开关语句来进行选择调用哪个子函数,下面就是课程设计的主要内容。 2 需求分析 2.1 课程设计目的 学生在教师指导下运用所学课程的知识来研究、解决一些具有一定综合性问题的专业课题。通过课程设计(论文),提高学生综合运用所学知识来解决实际问题、使用文献资料、及进行科学实验或技术设计的初步能力,为毕业设计(论文)打基础。 2.2 课程设计任务 输入一组正整数,以-1标志结束,用函数实现:(1)将这些正整数作为链表结点的data域建立一个非递减有序的单链表,并输出该单链表;(2)往该链表中插入一个正整数,使其仍保持非递减有序,输出插入操作后的单链表;(3)删除链表中第i个结点,输出删除操作后的单链表,i从键盘输入。 2.3 设计环境 (1)WINDOWS 7系统 (2)Visual C++ 2.4 开发语言 C语言 3 分析和设计 3.1 模块设计 定义链表结点类型struct node表示结点中的信息,信息包括数据域data(用于存放结点中的有用数据)以及指针域next(用于存放下一个结点的地址),并将链表结点类型名改为NODE。如下所示: 单链表 1 题目编写一个程序,实现链表的各种基本运算,包括:链表操作:初始化链表、输出链表、输出链表长度和释放链表链表元素操作:插入元素、删除元素、输出元素(注意元素的位置) 2 目标熟悉单链表的定义及其基本操作的实现 3 设计思想 链表由多个结点通过next 指针连接成一个完整的数据结构,每个几点包括一个数据域和一个指向下一个结点的next 指针。通过对指针的改写与结点的增减,我们可以实现单链表的插入、删除、输入、输出、求长等操作。 4 算法描述 (1 )初始化链表:输入元素个数n ,分配n 个结点空间,输入元素值,按元素顺序初始化next 指针,使之连接成串,尾指针赋值NULL 。 (2 )输出链表:从表头开始沿next 指针遍历各结点,每次访问结点输出结点数据值,直至next 为空。 (3 )输出链表长度:从表头开始沿next 指针遍历各结点,每次访问结点计数器加一,直至next 为空,返回计数器值。 (4 )释放链表:沿next 指针从前向后依次释放结点,直至next 指空。 (5 )插入元素:指针沿next 指向移动指定位,新分配一个空间并存入数据,其next 赋值为当前指针指向结点的next ,修改当前指针指向结点的next 指向新加结点。 (6 )删除元素:指针沿next 指向移动指定位,修改待删结点的前一结点的next 指针指向待删结点的下一结点,保存数值,释放删除结点。 (7 )输出元素:指针沿next 指向移动指定位,指针指向结点数据区,读出数值返回。 5 程序结构图 6源程序 #i nclude #i nclude 双向链表 输入一个双向链表,显示些双向链表并对此双向链表排序运行结果: 源程序: #include typedef struct Link/*双向链表结构体*/ { int data; struct Link *lift; struct Link *right; }linkx,*linky; linky Init();/*建立双向链表*/ void PrLink(linky p);/*输出双向链表*/ linky Sort(linky head);/*对双向链表排序*/ linky Swap(linky head,linky one,linky two);/*任意交换双向链表两个结点的地址*/ void main(void) { linky head; head=Init(); head=Sort(head); PrLink(head); } linky (Init())/*建立链表*/ { linky p,q,head; int n=0; head=p=q=(linky)malloc(sizeof(linkx)); printf("排序前的链表: "); scanf("%d",&p->data);/*输入数据*/ head->lift=NULL; n++; while(n!=10)/*一直输入到规定的数字个数停止*/ { q=p; p=(linky)malloc(sizeof(linkx)); scanf("%d",&p->data);/*输入数据*/ q->right=p; p->lift=q; n++; } p->right=NULL; return(head); } linky Swap(linky head,linky one,linky two)/*任意交换两个结点*/ {linky temp; if(one->lift==NULL&&two->right==NULL)/*首和尾巴的交换*/ { if(one->right==two)/*只有两个结点的情况下*/ { two->right=one; two->lift=NULL; one->lift=two; one->right=NULL; head=two; } else/*有间隔的首尾交换*/ { one->right->lift=two; two->lift->right=one; two->right=one->right; one->lift=two->lift; two->lift=one->right=NULL; head=two;/*尾结点成为头结点*/ } #include "stdio.h"/*单链表方式的实现*/ #include "malloc.h" typedef char ElemType ; typedef struct LNode/*定义链表结点类型*/ { ElemType data ; struct LNode *next; }LNode,*LinkList;/*注意与前面定义方式的异同*/ /*建立链表,输入元素,头插法建立带头结点的单链表(逆序),输入0结束*/ LinkList CreateList_L(LinkList head) { ElemType temp; LinkList p; printf("请输入结点值(输入0结束)"); fflush(stdin); scanf("%c",&temp); while(temp!='0') { if(('A'<=temp&&temp<='Z')||('a'<=temp&&temp<='z')) { p=(LinkList)malloc(sizeof(LNode));/*生成新的结点*/ p->data=temp; p->next=head->next; head->next=p;/*在链表头部插入结点,即头插法*/ } printf("请输入结点值(输入0结束):"); fflush(stdin); scanf("%c",&temp); } return head; } /*顺序输出链表的内容*/ void ListPint_L(LinkList head) { LinkList p; int i=0; p=head->next; while(p!=NULL) { i++; printf("单链表第%d个元素是:",i); #include } LinkList InitList(void) { int i=1; char ch;//判断是否还输入 LinkList head=0,r,t;//r指向新创建的结点,t指向r的前一个结点 head=(struct nodes *)malloc(sizeof(struct nodes)); if(!head) { printf("存储空间分配失败\n"); return 0; } head->front=head; head->next=head; head->data='a'; t=r=head; while(1) { r=(struct nodes *)malloc(sizeof(struct nodes)); if(!r) { printf("存储空间分配失败\n"); return 0; } 大学数据结构实验报告 课程名称数据结构实验第(四)次实验实验名称链表的基本操作 学生姓名于歌专业班级学号 实验成绩指导老师(签名)日期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)初始化单链表La 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 数据结构C语言版循环链表表示和实现.txt37真诚是美酒,年份越久越醇香浓烈;真诚是焰火,在高处绽放才愈显美丽;真诚是鲜花,送之于人,手有余香。/* 数据结构C语言版循环链表表示和实现 P35 编译环境:Dev-C++ 4.9.9.2 日期:2011年2月10日 */ #include 实验名称:链表 班级:学号___________姓名:报告日期: 一、实验目的及要求 1. 掌握单链表的存储结构形式及其描述。 2. 掌握单链表的建立、查找、插入和删除操作。 二、实验内容 1. 编写函数,实现随机产生或键盘输入一组元素,建立一个带头结点的单链表(无序)。 2. 编写函数,实现遍历单链表。 3. 编写函数,实现把单向链表中元素逆置(不允许申请新的结点空间)。 4. 编写函数,建立一个非递减有序单链表。 5. 编写函数,利用以上算法,建立两个非递减有序单链表,然后合并成一个非递减链表。 6. 编写函数,在非递减有序单链表中插入一个元素使链表仍然有序。 7. 编写函数,实现在非递减有序链表中删除值为x的结点。 8. 编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法。 三、实验结果 四、实验总结: 这次实验使我在已经掌握单链表的存储结构,单链表的建立、查找、插入和删除操作的思想的基础上,可以对其利用C语言进行编程的实现,不仅对单链表的有关内容有了更深的理解,同时也对C语言编程的学习有了很大的进步。期间也遇到不少麻烦,;例如在编好程序后,编译运行时出现很多错误,但是在同学和网络的帮助下,将其成功解决。此外,需要注意的就是在用C语言进行编程时,一定要细心,注意基础知识的积累。同时算法思想也很重要。 源代码: #include typedef struct LNode { ElemType data; struct LNode *next; }LNode,*Linklist; void Createlist(Linklist &L) { Linklist p,s; ElemType x; L=(Linklist)malloc(sizeof(LNode)); L->next=NULL; p=L; scanf("%d",&x); while(x) { s=(Linklist)malloc(sizeof(LNode)); s->data=x; s->next=NULL; p->next=s; p=s; scanf("%d",&x);} } void printlist(Linklist &L) { Linklist p; p=L; while(p->next!=NULL){ p=p->next; printf("%d ",p->data);} printf("\n"); } void nizhi(Linklist &L) { Linklist p,s; p=L->next; L->next=NULL; while(p) { s=p; p=p->next; s->next=L->next; L->next=s;} } void charu(Linklist &L,ElemType x) 实验2 链表基本操作实验 一、实验目的 1. 定义单链表的结点类型。 2. 熟悉对单链表的一些基本操作和具体的函数定义。 3. 通过单链表的定义掌握线性表的链式存储结构的特点。 二、实验内容与要求 该程序的功能是实现单链表的定义和主要操作。如:单链表建立、输出、插入、删除、查找等操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。程序中的单链表(带头结点)结点为结构类型,结点值为整型。 要求: 同学们可参考指导书实验2程序、教材算法及其他资料编程实现单链表相关操作。必须包括单链表创建、输出、插入、删除操作,其他操作根据个人情况增减。 三、 算法分析与设计。 头结点 ...... 2.单链表插入 s->data=x; s->next=p->next; p->next=s; 3.单链表的删除: p->next=p->next->next; 四、运行结果 1.单链表初始化 2.创建单链表 3.求链表长度 4.检查链表是否为空 5.遍历链表 6.从链表中查找元素 7.从链表中查找与给定元素值相同的元素在顺序表中的位置 8.向链表中插入元素 插入元素之后的链表 9.从链表中删除元素 删除位置为6的元素(是3) 10.清空单链表 五、实验体会 经过这次单链表基本操作实验,自己的编程能力有了进一步的提高,认识到自己以前在思考一个问题上思路不够开阔,不能灵活的表达出自己的想法,虽然在打完源代码之后出现了一些错误,但是经过认真查找、修改,最终将错误一一修正,主要是在写算法分析的时候出现了障碍,经过从网上查找资料,自己也对程序做了仔细的分析,对单链表创建、插入、删除算法画了详细的N-S流程图。 目录 1 选题背景 (1) 2 方案与论证 (2) 2.1 链表的概念和作用 (2) 2.3 算法的设计思想 (3) 2.4 相关图例 (4) 2.4.1 单链表的结点结构 (4) 2.4.2 算法流程图 (4) 3 实验结果 (5) 3.1 链表的建立 (5) 3.2 单链表的插入 (5) 3.3 单链表的输出 (6) 3.4 查找元素 (6) 3.5 单链表的删除 (7) 3.6 显示链表中的元素个数(计数) (8) 4 结果分析 (9) 4.1 单链表的结构 (9) 4.2 单链表的操作特点 (9) 4.2.1 顺链操作技术 (9) 4.2.2 指针保留技术 (9) 4.3 链表处理中的相关技术 (9) 5 设计体会及今后的改进意见 (10) 参考文献 (11) 附录代码: (12) 1 选题背景 陈火旺院士把计算机60多年的发展成就概括为五个“一”:开辟一个新时代----信息时代,形成一个新产业----信息产业,产生一个新科学----计算机科学与技术,开创一种新的科研方法----计算方法,开辟一种新文化----计算机文化,这一概括深刻影响了计算机对社会发展所产生的广泛而深远的影响。 数据结构和算法是计算机求解问题过程的两大基石。著名的计算机科学家P.Wegner指出,“在工业革命中其核心作用的是能量,而在计算机革命中其核心作用的是信息”。计算机科学就是“一种关于信息结构转换的科学”。信息结构(数据结构)是计算机科学研究的基本课题,数据结构又是算法研究的基础。 2 方案与论证 2.1 链表的概念和作用 链表是一种链式存储结构,链表属于线性表,采用链式存储结构,也是常用的动态存储方法。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。 以“结点的序列”表示线性表称作线性链表(单链表) 单链表是链式存取的结构,为找第 i 个数据元素,必须先找到第 i-1 个数据元素。 因此,查找第 i 个数据元素的基本操作为:移动指针,比较 j 和 i 单链表 1、链接存储方法 链接方式存储的线性表简称为链表(Linked List)。 链表的具体存储表示为: ① 用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的,也可以是不连续的) ② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址(或位置)信息(称为指针(pointer)或链(link)) 注意: 链式存储是最常用的存储方式之一,它不仅可用来表示线性表,而且可用来表示各种非线性的数据结构。 2、链表的结点结构 ┌───┬───┐ │data │next │ └───┴───┘ data域--存放结点值的数据域 next域--存放结点的直接后继的地址(位置)的指针域(链域) 注意: ①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。 ②每个结点只有一个链域的链表称为单链表(Single Linked List)。实验二 链表操作实现
数据结构—链表应用能力测评
数据结构 单链表基本操作代码
数据结构 单链表详解
数据结构课程设计单链表
实验三四 链表的实现和应用
课程名称 班 级 数据结构 上机名称 姓 名 链表的实现和应 用 上机日期 学 号 2016.3.11 上机报告要求 1.上机名称 2.上机要求 3.上机环境 4.程序清单(写明运行结果) 5.上机体会
1.上机名称
链表的实现和应用
2.上机要求
⑴定义线性表的链式存储表示; ⑵基于所设计的存储结构实现线性表的基本操作; ⑶编写一个主程序对所实现的线性表进行测试; ⑷线性表的应用:①设线性表 L1和 L2分别代表集合 A 和 B,试设计算法求 A 和 B 的并集 C,并用线 性表 L3代表集合 C;②设线性表 L1和 L2中的数据元素为整数,且均已按值非递减有序排列,试 设计算法对 L1和 L2进行合并,用线性表 L3保存合并结果,要求 L3中的数据元素也按值非递减 有序排列。 ⑸设计一个一元多项式计算器,要求能够:①输入并建立多项式;②输出多项式;③执行两个多项式 相加;④执行两个多项式相减;⑤(选做)执行两个多项式相乘。
3.上机环境
Visual C++ 6.0
4.程序清单(写明运行结果)
(1) #include数据结构(C语言)单链表的基本操作
单链表的基本操作
数据结构链表代码
单链表的基本操作 C语言课程设计
数据结构与算法问题分析与源代码之单链表
双向链表基本操作
单链表的建立及其基本操作的实现(完整程序)
数据结构双向链表实战应用(c语言源程序)
链表的基本操作-数据结构实验报告
数据结构C语言版 循环链表表示和实现
数据结构实验 链表
链表基本操作实验报告
数据结构课程设计单链表