一、循环链表
循环链表是与单链表一样,是一种链式的存储结构,所不同的是,循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点,从而构成一个环形的链。
循环链表的运算与单链表的运算基本一致。所不同的有以下几点:
1、在建立一个循环链表时,必须使其最后一个结点的指针指向表头结点,而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。
2、在判断是否到表尾时,是判断该结点链域的值是否是表头结点,当链域值等于表头指针时,说明已到表尾。而非象单链表那样判断链域值是否为NULL。
二、双向链表
双向链表其实是单链表的改进。
当我们对单链表进行操作时,有时你要对某个结点的直接前驱进行操作时,又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域,那么能不能定义一个既有存储直接后继结点地址的链域,又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢?这就是双向链表。
在双向链表中,结点除含有数据域外,还有两个链域,一个存储直接后继结点地址,一般称之为右链域;一个存储直接前驱结点地址,一般称之为左链域。在c语言中双向链表结点类型可以定义为:typedef struct node
{
int data; /*数据域*/
struct node *llink,*rlink; /*链域,*llink是左链域指针,*rlink是右链域指针*/
}JD;
当然,也可以把一个双向链表构建成一个双向循环链表。
双向链表与单向链表一样,也有三种基本运算:查找、插入和删除。
双向链表的基本运算:
1、查找
假若我们要在一个带表头的双向循环链表中查找数据域为一特定值的某个结点时,我们同样从表头结点往后依次比较各结点数据域的值,若正是该特定值,则返回指向结点的指针,否则继续往后查,直到表尾。
下例就是应用双向循环链表查找算法的一个程序。
#include <stdio.h>
#include <malloc.h>
#define N 10
typedef struct node
{
char name[20];
struct node *llink,*rlink;
}stud;
stud * creat(int n)
{
stud *p,*h,*s;
int i;
if((h=(stud *)malloc(sizeof(stud)))==NULL) {
printf("不能分配内存空间!");
exit(0);
}
h->name[0]=’\0’;
h->llink=NULL;
h->rlink=NULL;
p=h;
for(i=0;i<n;i++)
{
if((s= (stud *) malloc(sizeof(stud)))==NULL) {
printf("不能分配内存空间!");
exit(0);
}
p->rlink=s;
printf("请输入第%d个人的姓名",i+1);
scanf("%s",s->name);
s->llink=p;
s->rlink=NULL;
p=s;
}
h->llink=s;
p->rlink=h;
return(h);
}
stud * search(stud *h,char *x)
{
stud *p;
char *y;
p=h->rlink;
while(p!=h)
{
y=p->name;
if(strcmp(y,x)==0)
return(p);
else p=p->rlink;
}
printf("没有查找到该数据!"); }
void print(stud *h)
{
int n;
stud *p;
p=h->rlink;
printf("数据信息为:\n"); while(p!=h)
{
printf("%s ",&*(p->name));
p=p->rlink;
}
printf("\n");
}
main()
{
int number;
char studname[20];
stud *head,*searchpoint;
number=N;
clrscr();
head=creat(number);
print(head);
printf("请输入你要查找的人的姓名:"); scanf("%s",studname);
searchpoint=search(head,studname);
printf("你所要查找的人的姓名是:%s",*&searchpoint->name);
}
/* 线性表的双向链表存储结构*/
typedef struct DuLNode
{
ElemType data;
struct DuLNode *prior,*next;
}DuLNode,*DuLinkList;
/*带头结点的双向循环链表的基本操作(14个) */
void InitList(DuLinkList *L)
{ /* 产生空的双向循环链表L */
*L=(DuLinkList)malloc(sizeof(DuLNode));
if(*L)
(*L)->next=(*L)->prior=*L;
else
exit(OVERFLOW);
}
void DestroyList(DuLinkList *L)
{ /* 操作结果:销毁双向循环链表L */ DuLinkList q,p=(*L)->next; /* p指向第一个结点*/ while(p!=*L) /* p没到表头*/
{
q=p->next;
free(p);
p=q;
}
free(*L);
*L=NULL;
}
void ClearList(DuLinkList L) /* 不改变L */
{ /* 初始条件:L已存在。操作结果:将L重置为空表*/ DuLinkList q,p=L->next; /* p指向第一个结点*/
while(p!=L) /* p没到表头*/
{
q=p->next;
free(p);
p=q;
}
L->next=L->prior=L; /* 头结点的两个指针域均指向自身*/
}
Status ListEmpty(DuLinkList L)
{ /* 初始条件:线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE */ if(L->next==L&&L->prior==L)
return TRUE;
else
return FALSE;
}
int ListLength(DuLinkList L)
{ /* 初始条件:L已存在。操作结果:返回L中数据元素个数*/
int i=0;
DuLinkList p=L->next; /* p指向第一个结点*/
while(p!=L) /* p没到表头*/
{
i++;
p=p->next;
}
return i;
}
Status GetElem(DuLinkList L,int i,ElemType *e)
{ /* 当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */ int j=1; /* j为计数器*/
DuLinkList p=L->next; /* p指向第一个结点*/
while(p!=L&&jnext;
j++;
}
if(p==L||j>i) /* 第i个元素不存在*/
return ERROR;
*e=p->data; /* 取第i个元素*/
return OK;
}
int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ /* 初始条件:L已存在,compare()是数据元素判定函数*/
/* 操作结果:返回L中第1个与e满足关系compare()的数据元素的位序。*/ /* 若这样的数据元素不存在,则返回值为0 */
int i=0;
DuLinkList p=L->next; /* p指向第1个元素*/
while(p!=L)
{
i++;
if(compare(p->data,e)) /* 找到这样的数据元素*/
return i;
p=p->next;
}
return 0;
}
Status PriorElem(DuLinkList L,ElemType cur_e,ElemType *pre_e)
{ /* 操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,*/ /* 否则操作失败,pre_e无定义*/
DuLinkList p=L->next->next; /* p指向第2个元素*/ while(p!=L) /* p没到表头*/
{
if(p->data==cur_e)
{
*pre_e=p->prior->data;
return TRUE;
}
p=p->next;
}
return FALSE;
}
Status NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e)
{ /* 操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,*/ /* 否则操作失败,next_e无定义*/
DuLinkList p=L->next->next; /* p指向第2个元素*/
while(p!=L) /* p没到表头*/
{
if(p->prior->data==cur_e)
{
*next_e=p->data;
return TRUE;
}
p=p->next;
}
return FALSE;
}
DuLinkList GetElemP(DuLinkList L,int i) /* 另加*/
{ /* 在双向链表L中返回第i个元素的地址。i为0,返回头结点的地址。若第i个元素不存在,*/ /* 返回NULL */
int j;
DuLinkList p=L; /* p指向头结点*/
if(i<0||i>ListLength(L)) /* i值不合法*/
return NULL;
for(j=1;j<=i;j++)
p=p->next;
return p;
实验二链表操作实现 实验日期: 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[]);/*保存单链表到文件*/
实验一顺序表与链表 一、实验目的 1、掌握线性表中元素的前驱、后续的概念。 2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。 3、对线性表相应算法的时间复杂度进行分析。 4、理解顺序表、链表数据结构的特点(优缺点)。 二、实验预习 说明以下概念 1、线性表:线性表是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限 序列。 2、顺序表:线性表的顺序存储结构或顺序映像,通常,称这种存储结构的线性表为顺序表。 3、链表:指针域中存储的信息称作指针或链。N个接点连接成一个链表,故又称线性链表。 三、实验内容和要求 1、阅读下面程序,在横线处填写函数的基本功能。并运行程序,写出结果。 ●#include
创建双向循环链表的源代码: #include
L->Length ++; } } //结点的输出 void Display( DuLinkList L) { DuLinkList p; printf("双向循环链表中的结点的数据为:"); for(p=L->next ;p->next !=L;) { printf("%d",p->data); printf(" 、"); p=p->next ; } printf("%d\n",p->data ); } int main() { DuLinkList L; int n,i; InitList(&L) ; printf("你想创建几个循环节点就输入几就行啦,请输入:"); scanf("%d",&n); Create(L,n); Display(L); } 双向循环链表插入源代码: #include
C语言程序设计实验报告 实验一:链表的基本操作一·实验目的 1.掌握链表的建立方法 2.掌握链表中节点的查找与删除 3.掌握输出链表节点的方法 4.掌握链表节点排序的一种方法 5.掌握C语言创建菜单的方法 6.掌握结构化程序设计的方法 二·实验环境 1.硬件环境:当前所有电脑硬件环境均支持 2.软件环境:Visual C++6.0 三.函数功能 1. CreateList // 声明创建链表函数 2.TraverseList // 声明遍历链表函数 3. InsertList // 声明链表插入函数 4.DeleteTheList // 声明删除整个链表函数 5. FindList // 声明链表查询函数 四.程序流程图 五.程序代码 #include
r=head;//r指向头结点 printf("输入数字:\n"); for(i=n;i>0;i--)//for 循环用于生成第一个节点并读入数据{ scanf("%d",&x); p=(node *)malloc(sizeof(node)); p->data=x;//读入第一个节点的数据 r->next=p;//把第一个节点连在头结点的后面 r=p;//循环以便于生成第二个节点 } r->next=0;//生成链表后的断开符 return head;//返回头指针 } void output (linklist head)//输出链表 { linklist p; p=head->next; do { printf("%3d",p->data); p=p->next; } while(p); printf("\n") } Status insert ( linklist &l,int i, Elemtype e)//插入操作 { int j=0; linklist p=l,s; while(j
江南大学物联网工程学院上机报告
课程名称 班 级 数据结构 上机名称 姓 名 链表的实现和应 用 上机日期 学 号 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
实 验 报 告 年级 班号 学号 姓名 实验名称: 第一次实验:简单学生管理系统 实验日期 2016年11月25日 计算机科学与技术系 2016年制
一、实验环境 Windows32位系统Microsoft Visual C++ 二、实验目的 掌握链表的使用 三、实验内容 用单向链表实现的简单学生管理系统 四、数据结构与算法思想描述 对单链表的增删查改 五、程序清单 /* 函数信息: 菜单选项 void Menu(); 初始化链表 void InitLink(node *head); 输出单个学生信息 void SingleShow(node *p); 尾插法 node* AddLink(node *p,char *num); 建立链表,并输入学生信息。 node *CreateLink(node *head); 查找学生信息,查找则返回查找位置前一个点 node *SearchLink(node *head, char *num); 增加学生信息,先进行查找,若已有则提示用户是否修改,否则增加void InsertLink(node *head, char *num); 修改学生信息,先进行查找,若已有则提示用户修改,否则退出 void ModifyLink(node *head, char *num); 删除学生信息 void DeleteLink(node *head, char *num); 显示所有学生信息 void Display(node *head) */ #include
#include
int i=-1; List *p,*data1,*q,*Last; data1=(List *)malloc(sizeof(List)); p=(List *)malloc(sizeof(List)); q=(List *)malloc(sizeof(List)); data1=head->next;//记住第一个数据地址 p=head->next; while(p->next!=NULL) { q=p; //q是前一个节点 p=p->next; //p是后一个节点 p->pre=q; //后一个节点的【前继指针】指向前一个节点的地址} Last=p; //p 就是【最后一个数据】的地址 data1->pre=Last; //【第一个元素】的【前继指针】指向【最后一个元素】的地址Last->next=data1; //【最后一个元素】的【后继指针】指向【第一个元素】的地址//双向链表构成 p=Last; printf("\n\n"); while(p->data!=1) { printf("%d ",p->data); p=p->pre; } printf("%d \n",p->data); }
《数据结构课程设计》报告 题目:单链表操作 专业:计算机科学与技术 班级: 单链表操作 针对带头结点的单循环链表,编写实现以下操作的算法函数。
实现要求: ⑴单链表建立函数create:先输入数据到一维数组A[M]中,然后根据一维 数组A[M]建立一个单循环链表,使链表中个元素的次序与A[M]中各元素的次序相同,要求该函数的时间复杂度为O(m); ⑵定位查找函数Locate:在所建立的单循环链表中查找并返回值为key的 第1个元素的结点指针;若找不到,则返回NULL; ⑶求出该链表中值最大和次大的元素值,要求该算法的时间复杂度为O(m), 最大和次大的元素值通过指针变量带回,函数不需要返回值; ⑷将链表中所有值比key(值key通过形参传入)小的结点作为值为key的结 点前驱,所有值比key大的结点作为值为key的结点后继,并尽量保持原有结点之间的顺序,要求该算法的时间复杂度为O(m); ⑸设计一个菜单,具有上述处理要求和退出系统功能。 ⒈本人完成的工作: 一、定义结构体:LNode 二、编写以下函数: (1)建立单循环链表 (2)建立定位查找函数 (3)求出链表中最大和次大值 (4)将链表中的值和输入的Key比较,小的作为key前驱结点,大的作为key 的后继结点 三、设计具有上述处理要求和退出系统菜单 ⒉所采用的数据结构:单链表 数据结构的定义: typedef struct Node //定义结点的结构体 { DataType data; //数据域 struct Node *next; //指针域
}LNode; //结点的类型 ⒊所设计的函数 (1)Create(void) LNode *Create(void) //建立单循环链表,链表头结点head作为返回值{ int i,j,n,A[M]; //建立数组A【M】 LNode *head,*p,*move; head=(LNode*)malloc(sizeof(LNode)); //创建空单循环链表head->next=head; move=head; printf("请输入数组元素的个数:"); //输入数组 scanf("%d",&n); printf("请输入数组:"); for(i=0;i
课程设计(论文) 题目名称单链表的基本操作 课程名称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。如下所示:
#include
void Display(DuLinkList L,int n){ int i; for(i=0;i
用双向循环链表求解约瑟夫环 学校:东北大学 专业:计算机科学与技术
1.问题描述 Josephus排列问题定义如下:假设n个竞赛者排成一个环形。给定一个正整数m≤n,从第1人开始,沿环计数,第m人出列。这个过程一直进行到所有人都出列为止。最后出列者为优胜者。全部出列次序定义了1,2,…n的一个排列。称为(n,m)Josephus排列。例如,(7,3)Josephus排列为3,6,2,7,5,1,4。【实验要求】 设计求解Josephus排列问题程序。 (1)采用顺序表、单链表或双向循环链表等数据结构。 (2)采用双向循环链表实现Josephus排列问题,且奇数次顺时针轮转,偶数次逆时针轮转。 (3)推荐采用静态链表实现Josephus排列问题。 2.需求分析 本程序要求根据输入的人数n和给定的正整数m,求得约瑟夫排列,且奇数次顺时针轮转,偶数次逆时针轮转。故可利用双向循环链表建立存储结构,利用双向循环链表的遍历与删除操作实现功能要求。 3.概要设计 1.抽象数据类型定义: typedef struct DuLNode { int data; struct DuLNode *prior; struct DuLNode *next; }DuLNode,*DuLinkList; //定义双向循环链表 2.基本操作 int InitList_Dul(DuLinkList &L) //建立一个只含头结点的空双向循环链表 int CreateList_DuL(DuLinkList &L,int n) //建立一个带头结点的含n个元素的 双向循环链表L int ListDelete_DuL(DuLinkList &L,DuLinkList x) //删除指针x指向的结点 3.设计思路 首先建立一个双向循环链表作为存储结构,每个结点的数据域存储每个人的编号,然后根据给定的m值对整个链表进行遍历,找到所要找的结点后,输出该结点的数据域的值,并在双向循环链表中删除该结点,重复这样的操作,一直到所有的人都出列,依次输出的数列即为所求的Josephus排列。 4.详细设计 typedef struct DuLNode { int data; struct DuLNode *prior;
list是双向循环链表,,每一个元素都知道前面一个元素和后面一个元素。在STL 中,list和vector 一样,是两个常被使用的容器。和vector不一样的是,list不支持 对元素的任意存取。list中提供的成员函数与vector类似,不过list提供对表首元素的操作 push_front、pop_front,这是vector不具备的。禾口vector另一点不同的是,list的迭代器不会存在失效的情况,他不像vector会保留备份空间,在超过容量额度时重新全部分配内存,导致迭代器失效;list没有备份空间的概念,出入一个元素就申请一个元素的空间,所以它的迭代器不会失效。还是举《C++之vector》中的 例子: int data[6]={3,5,7,9,2,4}; list< int> lidata(data, data+6); lidata.push_back(6); list初始化时,申请的空间大小为6,存放下了data中的6个元素,当向lidata插入第7个元素“6”,list申请新的节点单元,插入到list链表中,数据存放结构如图1所示: 插入节点"6拆之后的list 图1 list的存储结构 list每次增加一个元素,不存在重新申请内存的情况,它的成本是恒定的。而vector每当增加关键元素的时候,都需要重新申请新的更大的内存空间,会调用元素的自身的复制构造函数,存在构造成本。在销毁旧内存的时候,会调用析构函数, 存在析构成本。所以在存储复杂类型和大量元素的情况下,list比vector更有优势! List是一个双向链表,双链表既可以向前又向后链接他的元素。
#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);
13软工转本1 钱剑滨实验报告 双向链表实验报告 信息工程系 13软工转本1 日期 2016年03月12日 姓名钱剑滨学号 13131116 电话 一、实验内容 编写关于双向链表操作的C语言程序,要求包含双向链表的创建(生成)、输出(遍历)、查找、任意位置插入、有顺序插入、删除、等。 二、实验步骤 1.分析操作所需思路,熟练运用单链表的各种特点。 2.编写程序,利用函数特性进行操作。 3.运行程序,纠正错误,对预测结果进行验证。 4.分析总结单链表的优缺点,并可以做到熟练掌握双向链表的各种 操作。 三、设计概要 1.本实验包含了7个函数: a)主函数main() b)创建链表函数Listcreate() c)数据输出函数Listprint() d)查找数据函数Listlocate() e)无序插入函数Listinsert_discretion () f)有序插入函数Listinsert_order g)删除数据函数Listdelete() 2.明确函数的功能; a)Listcreate() 创建一个可控长度的斐波那契数列的双向链表。 b)Listprint() 将此链表中的数据全部输出。 c)Listlocate() 查找此链表中任意位置元素的值。 d)Listinsert_discretion ()向此链表的某个位置插入一组数据。 e)Listinsert_order() 向数列中插入一个数,使插入后的数列任 然有序 f)Listdelete() 将此链表的某个位置的一组数据删除。
四、程序设计 1.函数前包含的头文件名、结点类型定义、全局变量和函数声明 #include
实验一 要求:①建立双向循环链表 ②实现链表的插入、删除 运行程序点此处Demo_1.exe 实验程序源代码: #include "stdafx.h" #include
p->next =q; q->prior=p; q->next=L; L->prior =q; p=q; L->Length ++; } } //查找元素的位置 DuLinkList GetElemP(DuLinkList h,int i) { int j; DuLinkList p=h; for(j=1;j<=i;j++) p=p->next ; return p; } //结点的插入 status Listinsert(DuLNode *m,int i,int e) { //在带头结点的双链循环线性表L中第i个位置之前插入元素e,i的合法值为1≤i≤表长 DuLinkList p,q; if(i<1||i>(m->Length)) // i值不合法 return ERROR; p=GetElemP(m,i); if(!p) return ERROR; q=(DuLinkList)malloc(sizeof(DuLNode)); if(!q) return OVERFLOW; q->data=e; q->prior=p->prior; p->prior->next=q; q->next=p; p->prior=q; m->Length++; printf("您在双向循环链表第%d个位置之前插入了一结点元素:%d\n",i,e); return OK; } //结点的删除 status ListDelete(DuLinkList L,int i) { //删除带头结点的双链循环线性表L的第i个元素,i的合法值为1≤i≤表长
大学数据结构实验报告 课程名称数据结构实验第(四)次实验实验名称链表的基本操作 学生姓名于歌专业班级学号 实验成绩指导老师(签名)日期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
实验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.理解双链表的基本操作 2.了解双链表的建立和输出 3.掌握双链表的插入、删除等实现方法 二、实验内容 编写一个程序,实现双链表的各种基本运算(假设双链表的元素类型为char),并在此基础上设计一个程序,完成如下功能: (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)删除h的第3个元素; (11)输出双链表h; (12)释放双链表h。 三、设计思想 本次实验主要考察了多双链表的基本操作,包括初始化链表,插入节点,删除节点,寻找元素的位置,判断链表是否为空,输出链表等。本次实验在逻辑上没有什么难度,首先是构造一个结构体,包括向前的指针和向后的指针,其次是构造函数来实现不同的功能,最后是在主函数中初始化链表,再调用构造函数。 四、主要源代码
#include