实验一
要求:①建立双向循环链表
②实现链表的插入、删除
运行程序点此处
实验程序源代码:
#include ""
#include<>
#include<>
#define OVERFLOW -2
#define ERROR 0
#define OK 1
typedef int status;
//双向循环链表的存储结构
typedef struct DuLNode
{
int data;
int Length;
struct DuLNode *prior;
struct DuLNode *next;
} DuLNode,*DuLinkList;
//构建一个空的双向循环链表
void InitList(DuLNode **p)
{
*p=(DuLNode *)malloc(sizeof(DuLNode));
if(*p)
{
(*p)->next=(*p)->prior=*p;
(*p)->Length=0;
}
else
exit(OVERFLOW);
}
//双向循环链表的创建
void Create(DuLinkList &L,int n)
{
//输入n个元素的值,建立带头结点的双线循环链表L DuLinkList p=L,q;
int i;
for(i=1;i<=n;i++)
{
q=(DuLinkList)malloc(sizeof(DuLNode));
printf("您该输入第%d个元素的值了:",i);
scanf("%d",&q->data);
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≤表长
DuLinkList p;
if(i<1) /* i值不合法 */
return ERROR;
p=GetElemP(L,i);
if(!p)
return ERROR;
p->prior->next=p->next;
p->next->prior=p->prior;
L->Length --;
printf("删除了双线循环链表中第%d个结点,元素值为:%d\n",i,p->data); free(p);
return OK;
}
//结点的输出
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 );
}
//主函数实现链表的创建,插入,删除等操作
void main()
{
DuLinkList L;
int n,i;
InitList(&L) ;
printf("你想创建几个循环节点就输入几就行啦,请输入:");
scanf("%d",&n);
Create(L,n);
Listinsert(L,3,3);//结点的插入
printf("您想删除哪个结点呢");
scanf("%d",&i);
printf("您确定删除此结点吗1:YES 2:NO(回复数字确认)");
if(i=2)
{
printf("您想删除哪个结点呢");
scanf("%d",&i);
ListDelete(L,i);
}
else
{ListDelete(L,i);}//结点的删除
Display(L);
printf("双向循环链表中结点的个数为:%d\n",L->Length); }
数组作为存放同类数据的集合,给我们在程序设计时带来很多的方便,增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定,不能在程序中进行调整,这样一来,在程序设计中针对不同问题有时需要3 0个大小的数组,有时需要5 0个数组的大小,难于统一。我们只能够根据可能的最大需求来定义数组,常常会造成一定存储空间的浪费。我们希望构造动态的数组,随时可以调整数组的大小,以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间,决不构成对存储区的浪费。 链表是一种复杂的数据结构,其数据之间的相互关系使链表分成三种:单链表、循环链表、双向链表,下面将逐一介绍。 7.4.1 单链表 图7 - 3是单链表的结构。 单链表有一个头节点h e a d,指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型,节点有两个成员:整型成员(实际需要保存的数据)和指向下一个结构体类型节点的指针即下一个节点的地址(事实上,此单链表是用于存放整型数据的动态数组)。链表按此结构对各节点的访问需从链表的头找起,后续节点的地址由当前节点给出。无论在表中访问那一个节点,都需要从链表的头开始,顺序向后查找。链表的尾节点由于无后续节点,其指针域为空,写作为N U L L。 图7 - 3还给出这样一层含义,链表中的各节点在内存的存储地址不是连续的,其各节点的地址是在需要时向系统申请分配的,系统根据内存的当前情况,既可以连续分配地址,也可以跳跃式分配地址。 看一下链表节点的数据结构定义: struct node { int num; struct node *p; } ; 在链表节点的定义中,除一个整型的成员外,成员p是指向与节点类型完全相同的指针。在链表节点的数据结构中,非常特殊的一点就是结构体内的指针域的数据类型使用了未定义成功的数据类型。这是在C中唯一规定可以先使用后定义的数据结构。 ?单链表的创建过程有以下几步: 1 ) 定义链表的数据结构。 2 ) 创建一个空表。 3 ) 利用m a l l o c ( )函数向系统申请分配一个节点。 4 ) 将新节点的指针成员赋值为空。若是空表,将新节点连接到表头;若是非空表,将新 节点接到表尾。 5 ) 判断一下是否有后续节点要接入链表,若有转到3 ),否则结束。 ?单链表的输出过程有以下几步 1) 找到表头。
创建双向循环链表的源代码: #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
单链表的插入和删除实验日志 指导教师刘锐实验时间2010 年10 月11 日 学院数理专业数学与应用数学 班级学号姓名实验室S331-A 实验题目:单链表的插入和删除 实验目的:了解和掌握线性表的逻辑结构和链式存储结构,掌握单链表的基本算法及相关的时间性能分析。 实验要求:建立一个数据域定义为字符串的单链表,在链表中不允许有重复的字符串;根据输入的字符串,先找到相应的结点,后删除之。 实验主要步骤: 1、分析、理解程序(相关程序见附录) 。 2、调试程序,并设计输入字符串数据(如:aa, bb , cc , dd, ee,#),测试程序的如下功能: 不允许重复字符串的插入;根据输入的字符串,找到相应的结点并删除。 3、修改程序: (1)增加插入结点的功能。 (2)将建立链表的方法改为头插入法。 实验结果: 1、不允许重复字符串的插入功能结果如下:
3、删除和插入结点的功能如下:
心得体会: 通过这次实验我学会了单链表的建立和删除,基本了解了线性表的逻辑结构和链式存储结构,掌握了单链表的基本算法,使我受益匪浅。在调试程序的过程中,遇见了一系列的问题,后来在同学的帮助下,修改了几个语句后,终于把它给调试出来了。有时候一个标点符号的问题就可能导致程序无法运行。所以在分析调试程序的时候一定要仔细。 附加程序代码: 1、调试之后的程序如下(其中蓝色字体部分为修改过的): #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数,用尾插入法建立带头结点的单链表ListNode *LocateNode(); //函数,按值查找结点
用双向循环链表求解约瑟夫环 学校:东北大学 专业:计算机科学与技术
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;
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
#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); }
双向链表 输入一个双向链表,显示些双向链表并对此双向链表排序运行结果: 源程序: #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;/*尾结点成为头结点*/ }
/*从键盘读入一个字符串,把它存入一个链表(每个结点存储1个字符),并按相反的次序将字符串输出到显示屏。 要求至少写出以下方法或函数,初始化链表、插入结点、删除结点、查找、显示、销毁链表*/ #include
return; } if(n==1) { s->next=head; head->last=s; head=s; return; } p=head; for(int i=1;i
编写程序,演示在双向链表上的插入和删除算法。 问题分析:1、在双向链表上操作首先要生成一个双向链表: 1>节点定义struct DuLNode{ ElemType data; DuLNode *prior; DuLNode *next; }; 2.> 创建双列表 L=(DuLinkList)malloc(sizeof(DuLNode)); L->next=L->prior=L; 3>输入链表数据; 2、 3、对向链表进行插入操作算法: 在节点p的前面加入一个新的节点q: q=(DuLinkList)malloc(sizeof(DuLNode)); q->data=e; q->prior=p->prior; q->next=p; p->prior->next=q; p->prior=q; 4、对双向链表进行删除操作算法 删除给定节点p 得到的代码如下: #include
DuLNode *next; }; typedef DuLNode *DuLinkList; status DuListInsert_L(DuLinkList L,int i , ElemType e)//插入函数 { DuLinkList p=L; //定义两个指向头节点的指针 DuLinkList q=L; int j=0; while(p->next!=L&&jnext; j++; } if(p->next==L||jdata=e; q->prior=p->prior; q->next=p; p->prior->next=q; p->prior=q; return OK; } status DuListDelete_L(DuLinkList L,int i , ElemType &e)//删除 { DuLinkList p=L; int j=0; while(p->next!=L&&jnext;j++; } if(p->next==L||jprior->next=p->next; p->next->prior=p->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是一个双向链表,双链表既可以向前又向后链接他的元素。
实验一 要求:①建立双向循环链表 ②实现链表的插入、删除 运行程序点此处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≤表长
实验报告名称:线性表及其应用 实验目的: 1.掌握单向链表的存储特点及其实现。 2.掌握单向链表的插入、删除算法及其应用算法的程序实现。实验报告(实验内容、实验步骤、实验运行结果分析、实验小结) 实验内容: 在单向链表中删除所有的偶数元素结点。 #include
} void shanou(link head) { link p,q; q=head; p=head->next; while(p) { if((p->data%2!=0)) { p=p->next; q=q->next; } else {q->next=p->next; p=p->next; } } printf("shanou后的链式表为:\n"); p=head->next; while(p) {printf("%3d",p->data); p=p->next; } printf("\n"); } void main() {link head; int n; printf("请输入线性表L的长度:\n"); scanf("%d",&n); head=createlink(n); print(head); shanou(head); } 运行结果:
#include
for(;i
#include
typedef struct node { ElemType data; struct node *prior, *next; }DLink; void InitList(DLink **L); //初始化运算 int GetLength(DLink *L); //求表长运算 int GetElem(DLink *L, int num, ElemType *e); //求线性表中第i个元素运算int Locate(DLink *L, ElemType x); //按值查找运算 int InsElem(DLink *L, ElemType x, int i); //插入节电运算 int DelElem(DLink *L, int num); //删除结点运算 void DispList(DLink *L); //输出线性表 #endif [cpp] view plaincopyprint? #include
int main() { pNode pHead = NULL; // 定义初始化头节点,等价于struct Node *pHead == NULL int data; // 作为Insert_Node函数的第三个参数 int num; // 作为Inset_Node函数第二个参数 int choose; int return_val; pHead = CreateList(); // 创建一个非循环单链表,并将该链表的头结点的地址付给pHead printf("你输入的数据是:"); TraverseList(pHead); // 调用遍历链表函数 printf("是否还要进行如下操作:\n"); printf("1.插入数据 2.删除数据\n"); printf("请输入:"); scanf("%d",&choose); switch (choose) { case 1: { printf("请输入要在第几个节点前插入数据:"); scanf("%d",&num); printf("请输入要插入的数据:"); scanf("%d",&data); if(Insert_Node(pHead,num,data) == true) { printf("插入成功\n插入后的数据是:\n"); TraverseList(pHead); } else { printf("插入失败\n"); } printf("操作完成后的数据是:"); TraverseList(pHead); break; } case 2: { printf("请输入要删除第几个节点的数据:"); scanf("%d",&num); return_val = Del_Node(pHead,num); if (return_val == 0) {
链表的C语言实现之删除结点 假如我们已经知道了要删除的结点p的位置,那么要删除p结点时只要令p结点的前驱结点的链域由存储p结点的地址该为存储p的后继结点的地址,并回收p结点即可。 以下便是应用删除算法的实例: #include <stdio.h> #include <malloc.h> #include <string.h> #define N 10 typedef struct node { char name[20]; struct node *link; }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->link=NULL; p=h; for(i=0;i<n;i ) { if((s= (stud *) malloc(sizeof(stud)))==NULL) { printf("不能分配内存空间!"); exit(0); } p->link=s; printf("请输入第%d个人的姓名",i 1); scanf("%s",s->name); s->link=NULL; p=s; } return(h); } stud * search(stud *h,char *x) /*查找函数*/ {
stud *p; char *y; p=h->link; while(p!=NULL) { 软件开发网 y=p->name; if(strcmp(y,x)==0) return(p); else p=p->link; } if(p==NULL) printf("没有查找到该数据!"); } stud * search2(stud *h,char *x) /*另一个查找函数,返回的是上一个查找函数的直接前驱结点的指针,*/ /*h为表头指针,x为指向要查找的姓名的指针*/ /*其实此函数的算法与上面的查找算法是一样的,只是多了一个指针s,并且s总是指向指针p所指向的结点的直接前驱,*/ /*结果返回s即是要查找的结点的前一个结点*/ { stud *p,*s; char *y; p=h->link; s=h; while(p!=NULL) { y=p->name; if(strcmp(y,x)==0) return(s); else { p=p->link; s=s->link; } } if(p==NULL) printf("没有查找到该数据!"); } void del(stud *x,stud *y) /*删除函数,其中y为要删除的结点的指针,x为要删除的结点的前一个结点的指针*/ { stud *s;
List-DuLinkedList-双向循环链表-Locate(L,x) 2.38 设有一个双向循环链表,每个结点中除了有prior、data和next三个域外,还增设了一个访问频度域freq。在链表被启用之前,频度域freq的值均初始化为零,而每当对链表进行一次Locate(L, x)的操作后,被访问的结点(即元素值等于x的结点)中的频度域freq的值便增加1,同时调整链表中结点之间的次序,使其按访问频度非递增的次序顺序排列,以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的Locate操作的算法。#include