精华内容
下载资源
问答
  • 尾指针循环单链表带尾指针循环单链表基本操作定义存储结构类型尾插法创建尾指针循环单链表头插法创建带尾指针循环单链表将两个带尾指针循环单链表合并遍历尾指针循环单链表测试代码 带尾指针循环单链表基本操作 ...

    带尾指针循环单链表基本操作

    在这里插入图片描述

    定义存储结构类型

    typedef struct LNode
    {
    	int data;
    	struct LNode *next;
    } LNode,*LinkList;
    

    尾插法创建带尾指针循环单链表

    //尾插法
    void CreateList_R(LinkList *L,int n)   //LinkList *L L是指向尾指针
    {
    	LNode *p,*q;   //p是指向头结点指针  q是指向新节点指针 
    	int i;
    	p = q = (LinkList)malloc(sizeof(LNode));   //为头结点开辟空间,并让p、q同时指向它
    	printf("为单链表输入%d个元素:",n);
    	for(i=0;i<n;i++)
    	{
    		q->next = (LinkList)malloc(sizeof(LNode));   //第一次:头结点next指向下一个结点  第二次之后:前继结点指向新结点 
    		q = q->next;   //q指针向前移,指向新结点
    		scanf("%d",&q->data);
    		q->next = p;    //新结点next指向头结点,形成一个循环 
    		*L = q;      //尾指针指向新结点,直至链尾 
    	}
    }
    

    头插法创建带尾指针循环单链表

    //头插法
    void CreateList_H(LinkList *LTail,int n)  //L指向尾指针L的指针(二重指针) 
    {
    	int i;
    	*LTail = (LinkList)malloc(sizeof(LNode));   //尾结点 
    	LNode *LHead = (LinkList)malloc(sizeof(LNode));    //头结点 
    	(*LTail)->next = LHead;    //尾结点指针域指向头结点 
    	LHead->next = *LTail;       //头结点指向尾结点 
    	printf("为单链表输入%d个元素:",n);
    	scanf("%d",&((*LTail)->data));   //为尾结点输入数据 
    	for(i=0;i<n-1;i++)
    	{
    		LNode *tmp_node = (LinkList)malloc(sizeof(LNode));   //为新结点动态开辟空间单元,指针tmp_node指向新结点 
    		tmp_node->next = LHead->next;    //头结点指向的后继结点赋给新插入结点的指针域 
    		scanf("%d",&tmp_node->data);
    		LHead->next = tmp_node;        //让头结点指向新插入结点,完成链状 
    	}
    }
    

    将两个带尾指针循环单链表合并

    void Union(LinkList La,LinkList Lb)   //两个链表的尾指针 
    {
    	LNode *tmp_node = La->next;     //先保存La链头结点指针 
    	La->next = Lb->next->next;      //La链尾 连接Lb链首元结点 
    	free(Lb->next);            //释放Lb链内存单元 
    	Lb->next = tmp_node;           //与上一步不能颠倒,将Lb链连接La链头结点 
    } 
    

    遍历尾指针循环单链表

    //遍历 
    Status print(LinkList L)
    {
    	LNode *head;
    	head = L->next;  //头结点地址 
    	if(head == L) return ERROR;   //空链表(即当前头结点next域指向自己)  返回ERROR 
    	while(head != L)    //当前结点指针不是尾结点指针 
    	{ 
    		head = head->next;        //向前移动一个接着输出数据 
    		printf("%d ",head->data);    //输出数据 
    	} 
    	return OK;
    }
    

    测试代码

    #include <stdio.h>
    #include <stdlib.h>
    
    #define OK 1
    #define ERROR 0
    
    typedef int Status; 
    
    typedef struct LNode
    {
    	int data;
    	struct LNode *next;
    } LNode,*LinkList;
    
    //尾插法
    void CreateList_R(LinkList *L,int n)   //LinkList *L L是指向尾指针L的指针 
    {
    	LNode *p,*q;   //p是指向头结点指针  q是指向新节点指针 
    	int i;
    	p = q = (LinkList)malloc(sizeof(LNode));   //为头结点开辟空间,并让p、q同时指向它
    	printf("为单链表输入%d个元素:",n);
    	for(i=0;i<n;i++)
    	{
    		q->next = (LinkList)malloc(sizeof(LNode));   //第一次:头结点next指向下一个结点  第二次之后:前继结点指向新结点 
    		q = q->next;   //q指针向前移,指向新结点
    		scanf("%d",&q->data);
    		q->next = p;    //新结点next指向头结点,形成一个循环 
    		*L = q;      //尾指针指向新结点,直至链尾 
    	}
    }
    
    //头插法
    void CreateList_H(LinkList *LTail,int n)  //L指向尾指针L的指针(二重指针) 
    {
    	int i;
    	*LTail = (LinkList)malloc(sizeof(LNode));   //尾结点 
    	LNode *LHead = (LinkList)malloc(sizeof(LNode));    //头结点 
    	(*LTail)->next = LHead;    //尾结点指针域指向头结点 
    	LHead->next = *LTail;       //头结点指向尾结点 
    	printf("为单链表输入%d个元素:",n);
    	scanf("%d",&((*LTail)->data));   //为尾结点输入数据 
    	for(i=0;i<n-1;i++)
    	{
    		LNode *tmp_node = (LinkList)malloc(sizeof(LNode));   //为新结点动态开辟空间单元,指针tmp_node指向新结点 
    		tmp_node->next = LHead->next;    //头结点指向的后继结点赋给新插入结点的指针域 
    		scanf("%d",&tmp_node->data);
    		LHead->next = tmp_node;        //让头结点指向新插入结点,完成链状 
    	}
    }
    
    //遍历 
    Status print(LinkList L)
    {
    	LNode *head;
    	head = L->next;  //头结点地址 
    	if(head == L) return ERROR;   //空链表(即当前头结点next域指向自己)  返回ERROR 
    	while(head != L)    //当前结点指针不是尾结点指针 
    	{ 
    		head = head->next;        //向前移动一个接着输出数据 
    		printf("%d ",head->data);    //输出数据 
    	} 
    	return OK;
    }
    
    //合并
    void Union(LinkList La,LinkList Lb)   //两个链表的尾指针 
    {
    	LNode *tmp_node = La->next;     //先保存La链头结点指针 
    	La->next = Lb->next->next;      //La链尾 连接Lb链首元结点 
    	free(Lb->next);            //释放Lb链内存单元 
    	Lb->next = tmp_node;           //与上一步不能颠倒,将Lb链连接La链头结点 
    } 
    
    int main()
    {
    	LinkList La,Lb;
    	printf("------尾插法录入数据-------\n");
    	CreateList_R(&La,3);
    	printf("当前La链: ");
    	print(La);
    	printf("\n");
    	printf("------头插法录入数据-------\n");
    	CreateList_H(&Lb,4);
    	printf("当前Lb链: "); 
    	print(Lb);
    	printf("\n");
    	printf("----带尾指针循环链表合并-----\n");
    	Union(La,Lb);
    	printf("当前合链: ");
    	print(Lb);
    }
    
    展开全文
  • 在VC6.0环境下实现了使用尾指针创建循环单链表,输出第一个和最后一个节点的值
  • 合并两个带尾指针循环单链表

    千次阅读 2012-07-24 23:27:29
    #include typedef struct Node //结点类型定义 { char data; struct Node *next;... //LinkList为结构指针类型 LinkList CreateCLinkList(LinkList *); LinkList Merge(LinkList, LinkList); in
    #include<iostream>
    typedef struct Node   //结点类型定义 
    { 
    	char data;
    	struct Node *next;
    }Node, *LinkList;   //LinkList为结构指针类型
    LinkList CreateCLinkList(LinkList *);
    LinkList Merge(LinkList, LinkList);
    
    int main()
    {
    	LinkList L, ra, rb, rc, p;
    	ra = CreateCLinkList(&L); //创建循环单链表L,并用ra作为尾指针
    	p = L;
    	while(p->next != ra->next)
    	{
    		std::cout<<p->data<<"→";
    		p = p->next;
    	}
    	std::cout<<p->data<<"→*\n";  //打印循环单链表的最后一个节点
    
    	rb = CreateCLinkList(&L); //创建循环单链表L,并用rb作为尾指针
    	p = L;
    	while(p->next != rb->next)
    	{
    		std::cout<<p->data<<"→";
    		p = p->next;
    	}
    	std::cout<<p->data<<"→*\n";  //打印循环单链表的最后一个节点
    	
    	rc = Merge(ra, rb);  //合并链表ra和ra,用rc作为新链表的尾指针
    	p = rc->next;
    	while(p->next != rc->next)
    	{
    		std::cout<<p->data<<"→";
    		p = p->next;
    	}
    	std::cout<<p->data<<"→*\n";  //打印循环单链表的最后一个节点
    	return 0;
    }
    
    /*创建循环单链表,返回尾指针,该链表既有头指针也有尾指针*/
    LinkList CreateCLinkList(LinkList *L)
    {
    	LinkList s;
    	char ch = ' ';
    	*L= new Node;    
    	(*L)->next = (*L);   //初始化头结点时指向自己
        (*L)->data = '*';    
    	
    	std::cout<<"请输入结点的值:";
    	std::cin>>ch;
    	while(ch != '#')
    	{
    		s = new Node;
    		s->data = ch;
    		s->next = (*L)->next;
    		(*L)->next = s;
    		std::cin>>ch;		
    	}
    	s = *L;
    	while(s->next != *L)  //当s->next = *L时,s就是尾指针
    		s = s->next;
    	return s;  //返回尾指针
    }
    
    /*合并两个带尾指针的循环单链表*/
    LinkList Merge(LinkList ra, LinkList rb)
    {
    	LinkList p, q;
    
    	p = ra->next;
    	ra->next = rb->next->next;  //链表ra的尾指针指向rb的第一个节点
    	q = rb->next;  //q保存链表rb的头结点,用于释放
    	rb->next = p;  //链表rb的尾指针指向ra的头结点
    	delete q;  //释放掉链表rb的头结点
    
    	return rb;
    }
    

    展开全文
  • 我这里使用带头尾指针单链表来模拟队列的功能,采用这种方法较为方便,其入队出队操作可以分别使用单链表的尾插,头删(或者头插,尾删)来实现。先看结点和队列的结构体定义: typedef int Qdatatype; //结点 ...

    前言: 在观读本篇博客之前请先阅读我之前的一篇博客顺序表的相关操作. 其中的内容可以帮你更好的理解本篇博客。

    队列的实现

    我这里使用带头尾指针的单链表来模拟队列的功能,采用这种方法较为方便,其入队出队操作可以分别使用单链表的尾插,头删(或者头插,尾删)来实现。先看结点和队列的结构体定义:

    
    typedef int Qdatatype;
    
    //结点
    typedef struct Qnode {
    	Qdatatype data;             
    	struct Qnode* next;
    }Qnode;
    
    //队列
    typedef struct Queue {
    	
    	//头尾指针
    	struct Qnode*head;
    	struct Qnode*tail;
    
    }Queue;
    

    初始化----创建新结点

    初始化:创建一个空的队列
    创建新结点:将需要插入的数据定义为“struct Qnode”的结点形式

    //初始化
    void Init(Queue* q)
    {
    	if (q == NULL)
    		return;
    	q->head = q->tail = NULL;
    
    }
    
    
    
    //创建新结点
    struct Qnode* creatnode(Qdatatype val)
    {
    	struct Qnode* node = (struct Qnode*)malloc(sizeof(struct Qnode));
    	node->data = val;
    	node->next = NULL;
    	return node;
    }
    

    入队-尾插

    将单链表的尾结点视为队列的队尾进行插入,由于我们定义了尾结点,所以该操作的时间复杂度为O(1)。实际操作:若该队列存在且为空,将头尾指针同时指向新结点;若该队列不为空,将尾指针的next指针指向新结点,然后更新尾指针。

    //入队-插入
    void Queuepush(Queue* q,Qdatatype val)
    {
    	if (q == NULL)
    		return;
    	// 尾插
    	struct Qnode*node = creatnode(val);
    	if (q->head == NULL)
    		q->head = q->tail = node;
    	else
    	{
    		q->tail->next = node;
    		q->tail = node;
    	}
    }
    

    模块调试截图:
    在这里插入图片描述
    依次将1,2,3,4,5进行入队操作。队列有效元素:1 2 3 4 5

    出队-头删

    将单链表的头结点视为队首进行出队操作,时间复杂度为O(1)。具体操作:将头指针更新到下原头结点的下一个位置,同时释放原头结点。此处需要注意最后两行代码的功能:若该对俩仅有一个有效元素,则头尾指针指向同一位置,将头指针更新释放后,尾指针变成野指针,需要在此处进行处理。

    //出队-头删
    void Queuepop(Queue* q)
    {
    	if (q == NULL||q->head==NULL)
    		return;
    	//头删
    	struct Qnode* next = q->head->next;
    	free(q->head); 
    	q->head = next;
    	//若该队列只有一个结点,尾指针需要置空
    	if (q->head == NULL)
    		q->tail = NULL;
    }
    

    模块调试截图:在这里插入图片描述
    对原队列(1 2 3 4 5)进行三次出队操作,队列有效元素: 4 5

    获取队首/队尾元素

    直接返回头指针或尾指针所指向的数据元素,但是在调用这两个函数之前需要判断队列的合法性

    
    //获取队首元素
    Qdatatype Queuefront(Queue* q)
    {
    	return q->head->data;
    }
    
    //队尾元素
    Qdatatype Queueback(Queue* q)
    {
    	return q->tail->data;
    }
    
    

    判断队列是否为空

    若队列为空,返回1;
    若队列不为空,返回0.

    //判断队列是否为空
    int Queueempty(Queue* q)
    {
    	if (q->head == NULL)
    		return 1;
    	else
    		return 0;
    }
    

    完整代码展示

    //队列
    
    #define _CRT_SECURE_NO_WARNINGS 1
    #include<stdio.h>
    #include<stdlib.h>
    
    
    typedef int Qdatatype;
    typedef struct Qnode {
    	Qdatatype data;
    	struct Qnode* next;
    }Qnode;
    
    typedef struct Queue {
    	
    	//头尾指针
    	struct Qnode*head;
    	struct Qnode*tail;
    
    }Queue;
    
    
    //初始化
    void Init(Queue* q)
    {
    	if (q == NULL)
    		return;
    	q->head = q->tail = NULL;
    
    }
    
    //创建新结点
    struct Qnode* creatnode(Qdatatype val)
    {
    	struct Qnode* node = (struct Qnode*)malloc(sizeof(struct Qnode));
    	node->data = val;
    	node->next = NULL;
    	return node;
    }
    
    //入队-尾插
    void Queuepush(Queue* q,Qdatatype val)
    {
    	if (q == NULL)
    		return;
    	// 尾插
    	struct Qnode*node = creatnode(val);
    	if (q->head == NULL)
    		q->head = q->tail = node;
    	else
    	{
    		q->tail->next = node;
    		q->tail = node;
    	}
    }
    
    //出队-头删
    void Queuepop(Queue* q)
    {
    	if (q == NULL||q->head==NULL)
    		return;
    	//头删
    	struct Qnode* next = q->head->next;
    	free(q->head); 
    	q->head = next;
    	//若该队列只有一个结点,尾指针需要置空
    	if (q->head == NULL)
    		q->tail = NULL;
    }
    
    //获取队首元素
    Qdatatype Queuefront(Queue* q)
    {
    	return q->head->data;
    }
    
    //队尾元素
    Qdatatype Queueback(Queue* q)
    {
    	return q->tail->data;
    }
    
    //判断队列是否为空
    int Queueempty(Queue* q)
    {
    	if (q->head == NULL)
    		return 1;
    	else
    		return 0;
    }
    
    void test()
    {
    	Queue q;
    	Init(&q);
    	Queuepush(&q, 1);
    	Queuepush(&q, 2);
    	Queuepush(&q, 3);
    	Queuepush(&q, 4);
    	Queuepush(&q, 5);
    	Queuepush(&q, 6);
    	Queuepush(&q, 7);
    	Queuepush(&q, 8);
    
    	while (!Queueempty(&q))
    	{
    		printf("%d ", Queuefront(&q));
    		Queuepop(&q);
    	}
    	printf("\n");
    
    }
    int main()
    {
    	test();
    	return 0;
    }
    

    运行结果:在这里插入图片描述

    展开全文
  • 单链表实现如下功能: void InitList(List *list); //初始化单链表 bool push_back(List *list,ElemType x); //尾插法 void show_seqlist(List *list); //显示链表内容 bool push_front(List *list,ElemType x);//...
  • //初始化以尾指针表示的循环单链表 int ListInit(LinkList &L){ L=new Lnode; if(!L) exit(ERROR); L->next=L; return OK; } //头插法建立以尾指针表示的循环单链表 void HCreatInsert(LinkList &L,int n){ Lnode *...
  • 循环单链表的实现 */ #include<iostream> using namespace std; template<typename T> struct Node { T data; Node<T>*next; }; template<typename T> class CircleLink { private: ...
  • 循环单链表存储(有头结点,只设尾指针,不设头指针) 考研参考书上的代码风格不太能接受,为了巩固加深链表操作的理解,特地完成了循环单链表的各项操作, 加油,一研为定!! 大家有需要可以借鉴,欢迎各位指正...
  • //用只有节点指针rear的循环单链表作为队列存储结构,其中每个节点的类型为LinkNode,rear指针用于唯一标识链队 typedef struct LinkNode { int date; LinkNode *next; }; void initQueue(LinkNode *&rear) { ...
  • 有两个循环单链表,链表头指针分别为h1和h2,编写一函数,将链表h2链接到链表h1之后,要求链接后的链表仍保持循环链表的形式。 分析:把链表h1的尾指针,改为指向h2即可;将h2的尾指针指向h1的第一个结点; LinkList...
  • //设立尾指针的单循环链表(存储结构由c2-2.h定义)的12个基本操作 void InitList(LinkList *L) { // 操作结果:构造一个空的线性表L *L = (LinkList)malloc(sizeof(LNode)); // 产生头结点,并使L指向此头结点 if (!...
  • 更新中…
  • c语言头指针反转单链表 难题 给定一个无序的单个链表 ,请提供一种仅使用2个指针来反转此类链表的算法。 输入项 单个链接列表。 Example. 1 -> 4 -> 3 -> 2 -> 0 输出量 反向单链表。 Example....
  • 循环单链表

    2012-08-22 19:58:17
     设rear是单链表的尾指针,执行下列语句,使一条单链表成为一条循环单链表  rear.next = head;  当head.next = head时,循环单链表为空。  循环单链表类仍然使用单链表结点类,与单链表类的操作相似,详见...
  • 利用尾指针连接两个单链表
  • 目录循环单链表循环单链表的操作插入头节点插入节点插入删除遍历查找循环单链表的C语言实现 循环单链表 循环单链表的操作 插入 头节点插入 节点插入 删除 遍历 查找 循环单链表的C语言实现 ...
  • 1.单链表实现 #include <iostream>//引入输入输出流 using namespace std; //将单链表的结点结构定义,单链表类定义和...//指针域 }Node; //单链表的实现 class LinkList{ public: LinkList();//建立只.
  • //尾指针指向头节点,使其变成一个循环单链表 //Tail->pNext = pHead->pNext; //如果写成这样,那么就是指向了头指针,即第一个有效数据 } return pHead; } /* 函数名:traverse_linlist(); 参数:...
  • 2.6循环单链表

    2020-05-23 20:20:44
    2.6循环单链表 单链形式的循环链表结构是首尾相接的单链表,即最后一个结点的指针指 向链表的表头结点或第一个结点。 判别当前结点 p 是否为循环单链表 L 的表尾结点的判别条件: p->next!=L, 即 p->next ...
  • 将两个用尾指针表示的循环单链表合并成一个用尾指针表示的循环单链表合并成一个用尾指针表示的循环单链表 这个模板出了一点问题,主要问题在于,我是直接套用了之前的做法,其实循环单链表,不用头指针,只用尾指针...
  • 循环单链表的合并

    2017-02-05 17:44:56
    循环单链表的合并
  • 主要介绍了C语言实现的循环单链表功能,结合实例形式分析了基于C语言实现的循环单链表定义、创建、添加、删除、打印、排序等相关操作技巧,需要的朋友可以参考下
  • 循环单链表 实现: package pers.zhang.linearList; /** * @author zhang * @date 2020/1/14 - 15:16 ... * 循环单链表 ...public class ... //头指针,指向循环单链表的头结点 public Node<T> he...
  • 循环单链表 循环单链表是单链表的另一种形式,其结构特点是链表中最后一个结点的指针域指向整个链表的第一个结点,从而使 链表形成一个环。 优点:从链到链头比较方便。 标题 ...
  • 尾指针循环队列

    千次阅读 多人点赞 2020-06-29 14:48:27
    假设以带头结点的单循环链表实现链式队列,并且要求只设尾指针,不设头指针,编写实现这种链式队列初始化、入队列和出队列操作的函数 题目分析: 队列具有队头和队尾,即头指针和尾指针。本题要求只使用尾指针,在...
  • 在设计循环单链表时,仅设计指向终端结点的尾指针可以提高效率,此时查找开始结点和终端结点就很方便了,下面以此来实现循环单链表 三、循环单链表的基本操作 1.循环单链表的整表创建 typedef int ElemType; ...
  •   一般对循环单链表只设尾指针不设头指针,其原因是,如果设的是头指针,对表尾进行操作需要O(n)的时间复杂度,而若设的是尾指针r,那么r->next即为头指针,对表头与表尾进行操作都只需要O(1)的时间复杂度。  ...
  • 1.循环单链表和单链表的区别在于链表中最后一个结点的指针不是指向NULL,而是指向头结点,这样链表结点就形成了一个环。循环单链表是一个环,所以在链表中任意位置插入或者删除结点时都是等价的,不需要根据所操作...
  • 设一个没有头结点指针单链表,有一指针指向此单链表中一个结点(非第一个,也非最后一个结点),将该结点从单链表中删除,要求时间复杂度O(1)。 没有头指针,则不可能遍历该单链表,况且要求时间复杂度为是常数,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,032
精华内容 7,612
关键字:

带尾指针的循环单链表