精华内容
下载资源
问答
  • 循环链表与单链表操作实现的差异: 1.在初始化函数中把语句(*head)->next = NULL 改为 (*head)->next =head 2.在其他函数中把循环条件p->next!=NULL 和 p->next->next !=NULL 中的 NULL 该为头指针 ...

    循环链表的实现指导说明

    循环链表与单链表操作实现的差异:
    1.在初始化函数中把语句(*head)->next = NULL 改为 (*head)->next =head
    2.在其他函数中把循环条件p->next!=NULL 和 p->next->next !=NULL 中的 NULL 该为头指针 head 即可

    展开全文
  • 文章目录带头结点的双向循环链表单链表区别面试题:写一个双向链表代码实现 带头结点的双向循环链表单链表区别   相比我们讲的无头单向非循环的单链表结构,他的插入和删除都是O(1),也不需要增容,浪费...

    带头结点的双向循环链表和单链表的区别

      相比我们讲的无头单向非循环的单链表结构,他的插入和删除都是O(1),也不需要增容,浪费空间换取时间,但是需要申请和释放空间。

    面试题:写一个双向链表

    思路
      主要实现函数ListInsert,ListFind,ListErase,其他的函数如头插,尾插,头删,尾删等函数可以用以上几个关键的函数代替实现。

    代码实现

    void ListPushFront(ListNode* phead, LTDataType x)
    {
    	assert(phead);
    	ListNode* node = (ListNode*)malloc(sizeof(ListNode*));
    	node->val = x;
    
    	ListNode* next = head->next;
    	node->next = next;
    	head->next = node;
    	next->prev = node;
    	node->prev = head;
    }
    
    void ListPopBack(ListNode* phead)
    {
    	assert(phead);
    	assert(phead->next != head);
    
    	ListNode* tail = phead->prev;
    	ListNode* tailPrev = tail->prev;
    
    	free(tail);
    	tailPrev->next = phead;
    	phead->prev = tailPrev;
    }
    
    void ListPopFront(ListNode* phead)
    {
    	assert(phead);
    	assert(phead->next != head);
    
    	ListNode* node = phead->next;
    	ListNode* next = node->next;
    	head->next = next;
    	next->prev = head;
    	free(node);
    }
    
    void ListInsert(ListNode* phead, LTDataType x)
    {
    	assert(pos);
    	ListNode* newNode = BuyListNode(x);
    	ListNode posPrev = pos->prev;
    
    	posPrev->next = newNode;
    	newNode->next = pos;
    	pos->prev = newNode;
    	newNode->prev = posPrev;
    }
    
    void ListFind(ListNode* phead, LTDataType x)
    {
    	assert(phead);
    
    	ListNode* cur = phead->next;
    	while (cur != phead)
    	{
    		if (cur->data == x)
    		{
    			retrun cur;
    		}
    		cur = cur->next;
    	}
    	return NULL;
    }
    
    void ListErase(ListNode* pos)
    {
    	assert(pos);
    	//pos不能是phead,否则头结点没了
    	//assert(pos != phead);
    
    	ListNode* posPrev = pos->prev;
    	ListNode* posNext = pos->next;
    
    	posPrev->next = posNext;
    	posNext->prev = posPrev;
    	free(pos);
    }
    
    void ListDestory(ListNode* phead)
    {
    	ListNode* cur = phead->next;
    	while (cur != phead)
    	{
    		ListNode* next = cur->next;
    		ListErase(cur);
    		cur = next;
    	}
    	free(phead);0
    }
    
    展开全文
  • 对于单链表,由于每个结点只存储了向后的指针,到了尾标志就停止了向后链的操作,如此...其实循环链表单链表的主要区别在于循环的判断条件上,由p->next是否为空改为p->next是否等于头结点,等于头结点则循环结束。

            对于单链表,由于每个结点只存储了向后的指针,到了尾标志就停止了向后链的操作,如此一来,链表中的结点就无法访问它的前驱(除非从头开始访问)。将单链表中终端结点的指针由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表。其实循环链表和单链表的主要区别在于循环的判断条件上,由p->next是否为空改为p->next是否等于头结点,等于头结点则循环结束。

            在单链表中,我们可以通过头结点用O(1)的时间访问第一个结点,却需要通过O(n)的时间访问最后一个结点;在循环链表中,我们可以改造一下,使用指向终端的尾指针,用O(1)的时间访问头结点和终端节点。下图为循环链表示意图:


           循环链表中的大多数操作与单链表相同,但在合并操作中,循环链表因为存在尾指针就可以变得非常简单。所以我们重点来看合并操作。

    代码预处理与循环链表定义

    #include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>
    typedef struct LNODE{
    	int data;
    	struct LNODE*next;
    }LNode,*Linklist;

    创建循环链表

    void CreatCir(Linklist &L){
    	Linklist p, nail;
    	L = (LNode*)malloc(sizeof(LNode));
    	L->next = L;
    	nail = L;
    	p = (LNode*)malloc(sizeof(LNode));
    	printf("请输入循环链表元素,按Ctrl+Z结束:\n");
    	while ((scanf("%d", &(p->data))) != EOF){
    		p->next = L;
    		nail->next = p;
    		nail = p;
    		p = (LNode*)malloc(sizeof(LNode));
    	}
    }

    打印循环链表

    void PrintCir(Linklist L){
    	Linklist p;
    	printf("建立的循环单链表为:\n");
    	p = L->next;
    	while (p!=L){
    		printf("%d ", p->data);
    		p = p->next;
    	}
    	printf("\n");
    }

    合并操作

    void Mergelist(Linklist &L1, Linklist &L2){
    	CreatCir(L2);
    	Linklist pA,pB,rear;
    	pA = L1->next;
    	pB = L2->next;
    	while (pA->next != L1)
    		pA = pA->next;//使pA指向L1最后一个结点
    	while (pB->next != L2)
    		pB = pB->next;//使pB指向L2最后一个结点         
            rear = pA->next;//保存pA的下一个结点,即L1头结点
           pA->next = pB->next->next;//使L1的尾结点与L2的第一个结点相连
           pB->next = rear;//使L2的尾结点与L1头结点相连
           free(L2);//不再需要L2头结点,所以释放L2头结点
    }


     
    

    主函数调用

    int main(){
    	Linklist list,listSec;
    	CreatCir(list);
    	PrintCir(list);
    	Mergelist(list, listSec);
    	PrintCir(list);
    	system("pause");
    	return 0;
    }
             本期循环链表到此结束,有关单链表的其他方面的改进请看下一期。谢谢大家!














    展开全文
  • 3.实现 #include #include #include #define TRUE 1 #define FALSE 0 /* 将单链表中终端结点的指针端由空指针改为指向头结点,就使... 其实循环链表单链表的主要差异就在于循环的判断空链表的条件上, 原来判断he


    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define TRUE 1
    #define FALSE 0
    /*
    将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表
        注:并不是说循环链表一定要有头结点
        其实循环链表单链表的主要差异就在于循环的判断空链表的条件上,
        原来判断head->next是否为null,现在则是head->next是否等于head
        -初始化部分:ds_init.c
        -插入部分:ds_insert.c
        -删除部分:ds_delete.c
        -返回结点所在位置:ds_search.c
    */
    /*链表存储结构的定义*/
    typedef struct CLinkList
    {
        int data;
        struct CLinkList *next;
    }node;
    
    /*初始化循环链表*/
    void ds_init(node **pNode)
    {
        int item;
        node *temp;
        node *target;
    
        printf("输入结点的值,输入0完成初始化\n");
    
        while(1)
        {
            scanf("%d",&item);
            fflush(stdin);
    
            if(item==0)
                return;
            if(*pNode==NULL)
            /*循环链表中只有一个结点*/
            {
                *pNode=(node *)malloc(sizeof(struct CLinkList));
                if(!(*pNode))
                    exit(0);
                (*pNode)->data=item;
                (*pNode)->next=*pNode;
            }
            else
            {
    
                /*找到next指向第一个结点的结点*/
                for(target=(*pNode);target->next!=(*pNode);target=target->next)
                    ;
                /*生成一个新的结点*/
                temp=(node *)malloc(sizeof(struct CLinkList));
    
                if(!temp)
                    exit(0);
                temp->data=item;
                temp->next=*pNode;
                target->next=temp;
            }
        }
    }
    /*插入结点
    参数:链表的第一个结点,出入位置*/
    void ds_insert(node **pNode,int i)
    {
        node *temp;
        node *target;
        node *p;
        int item;
        int j;
    
        printf("输入要插入结点的值:");
        scanf("%d",&item);
    
        if(i==1)
        {
            temp=(node *)malloc(sizeof(struct CLinkList));
    
            if(!temp)
                exit(0);
            temp->data=item;
    
            /*寻找到最后一个结点*/
            for(target=(*pNode);target->next!=(*pNode);target=target->next)
                ;
            temp->next=(*pNode);
            target->next=temp;
            *pNode=temp;
        }
        else
        {
            target=*pNode;
    
            for(j=1;j<(i-1);++j)
            {
                target=target->next;
            }
    
            temp=(node *)malloc(sizeof(struct CLinkList));
    
            if(!temp)
                exit(0);
            temp->data=item;
            p=target->next;
            target->next=temp;
            temp->next=p;
        }
    }
    /*删除结点*/
    void ds_delete(node **pNode ,int i)
    {
        node *target;
        node *temp;
        int j=1;
    
        if(i==1)
        {
            //删除的是第一个结点
            /*找到最后一个结点*/
            for(target=*pNode;target->next!=*pNode;target=target->next)
                ;
            temp=*pNode;
            *pNode=(*pNode)->next;
            target->next=*pNode;
            free(temp);
        }
        else
        {
            target=*pNode;
    
            for(;j<i-1;j++)
                target=target->next;
            temp=target->next;
            target->next=temp->next;
            free(temp);
        }
    }
    /*返回结点所在的位置*/
    int ds_search(node *pNode,int elem)
    {
        node *target;
        int i=1;
    
        for(target=pNode;target->data!=elem&&target->next!=pNode;target=target->next,++i)
            ;
        if(target->next==pNode)
            return 0;
        else
            return i;
    }
    /*遍历*/
    
    void ds_traverse(node *pNode)
    {
        node *temp;
        temp=pNode;
        printf("***********************链表中的元素***********************\n");
        do
        {
            printf("%d ",temp->data);
        }while((temp=temp->next)!=pNode);
        printf("\n");
    }
    /* 初始条件:线性表PNode已存在。操作结果:若pNode为空表,则返回TRUE,否则返回FALSE */
    int ListEmpty(node *pNode)
    {
        if(pNode->next==pNode)
            return FALSE;
        else
            return TRUE;
    }
    /*链表长度*/
    int ListLength(node *pNode)
    {
        int i=1;
        node *p=pNode->next;
    
        while(p!=pNode)
        {
            i++;
            p=p->next;
        }
        return i;
    }
    /*显示链表操作的说明*/
    void showHomepage()
    {
        puts("请输入你要操作的编号:");
        printf("1.初始化链表    2.插入结点\n");
        printf("3.删除结点      4.返回结点值\n");
        printf("5.遍历链表      6.判断链表是否为空\n");
        printf("7.链表长度      0.退出\n");
    }
    int main()
    {
        node *pHead=NULL;
        char cpp;
        int find;
       showHomepage();
        while(cpp!='0')
        {
            scanf("%c",&cpp);
            switch(cpp)
            {
            case '1':
                ds_init(&pHead);
                printf("\n");
                ds_traverse(pHead);
                showHomepage();
                break;
            case '2':
                printf("请输入要插入的位置:");
                scanf("%d",&find);
                ds_insert(&pHead,find);
                printf("在位置%d插入值后:\n",find);
                ds_traverse(pHead);
                printf("\n");
                showHomepage();
                break;
            case '3':
                printf("输入需要删除的结点位置:");
                scanf("%d",&find);
                ds_delete(&pHead,find);
                printf("删除第%d结点后:\n",find);
                ds_traverse(pHead);
                printf("\n");
                showHomepage();
                break;
            case '4':
                printf("你要查找的值:");
                scanf("%d",&find);
                printf("元素%d所在位置:%d\n",find,ds_search(pHead,find));
                printf("\n");
                showHomepage();
                break;
            case '5':
                ds_traverse(pHead);
                printf("\n");
                showHomepage();
                break;
            case '6':
                if(!ListEmpty(pHead))
                    puts("链表为空!");
                else
                    puts("链表不为空!");
                showHomepage();
                break;
            case '7':
                printf("链表的长度为:%d\n",ListLength(pHead));
                showHomepage();
                break;
            case '0':
                exit(0);
            }
        }
        return 0;
    }
    


    展开全文
  • 循环单链表-带头结点1.头文件及类型定义2.循环单链表结点类型定义3.函数声明4.基本操作4.1 初始化循环单链表4.2 判空4.3 判断表尾结点4.4 按位查找4.5 指定结点后插4.6 创建循环单链表4.7 遍历4.10 main函数5.小结 1...
  • 循环链表2.1 循环单链表2.2 循环双链表2.3 循环链表判空2.3.1 循环单链表2.3.2 循环双链表3. 静态链表4. 顺序表链表比较4.1 存取方式4.2 逻辑结构、物理结构4.3 基本操作4.4 内存空间总结4.5 怎样选择线性表的...
  • 一、单项链表: 以单链表为例,详说写链表的过程: 1、 定义节点,即写结构体
  • 链表 单链表 每个结点中只含有一个指针域 单链表的存储结构: typedef struct LNode{ ElemType data;//数据域 struct LNode *next;//指针域 } 单链表可以包含头结点,也可以直接在头部装入第一个元素。 即,所有...
  •  循环链表---http://blog.csdn.net/ab198604/article/details/8465220 单向链表--http://blog.csdn.net/ab198604/article/details/8253405 双向链表--http://blog.csdn.net/ab198604/article/detai
  • 文章目录链表思维 链表思维 动态创建链表:动态内存申请+模块化设计 创建链表(创建一个表头表示整个链表) 创建结点 插入结点 删除结点 打印遍历链表(测试用一般) 创建链表
  • 题号1:分别以单链表循环链表、双向链表为例,实现线性表的建立、插入、删除、查找等基本操作。 要求:能够把建立、插入、删除等基本操作的过程随时显示输出来。 1.2 软件功能 功能分为三个板块,分别是单链表...
  • 单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域 value)和一个链接域(或者称为指针域next)。这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值。...
  • 链表,是Java中的一种重要的链式数据结构。 众所周知,我们日常用手机电脑收发信息,下载视频和软件,都要进行数据的传输。这些数据都要以一种特定的数据结构来进行传输和存储,否则数据将会是一串毫无意义的0和1,...
  • 循环链表前言一、循环单链表的初始化二、判断是否为空或表尾结点三、循环双链表的初始化四、循环双链表的插入删除 前言 对于循环单链表而言,在进行插入和删除时,可以让指针指向尾部,对于表头(通过尾部找到头部...
  • 链表单链表

    2017-10-16 16:18:40
    链表有多种:静态链表、单链表、双链表、循环链表单链表中的指针域指向下一个元素,最后一个指针指向NULL。 循环链表单链表不同的是最后一个元素的指针域指向了头节点。 双向链表的节点有三部分,其中两部分...
  • class SingleNode(object): """单链表的结点""" def __init__(self,item): # _item存放数据元素 self.item = item # _next是下一个节点的标识 self.next = None
  • /*线性表的单链表存储结构*/ typedef struct Node { ElemType data; struct Node *next; }Node; typedef struct Node *LinkList; /* 定义LinkList */
  • 文章目录循环链表循环单链表循环双链表静态链表说明 循环链表循环链表一般包括循环单链表和循环双链表,如下图所示: 循环单链表   循环单链表与单链表区别在于,表中最后一个结点的指针不是NULL,而改为...
  • 题号1:分别以单链表循环链表、双向链表为例,实现线性表的建立、插入、删除、查找等基本操作。 要求:能够把建立、插入、删除等基本操作的过程随时显示输出来。 1.2 软件功能 功能分为三个板块,分别是单链表...
  • #include #include typedef struct Node { int data; struct Node * next;... //定义链表的结点,链表头 void Initlist (Linklist *CL) //初始化链表 { *CL=(Linklist)malloc(sizeof(Node));
  • 循环链表 1. 循环单链表 单链表和循环单链表区别: typedef struct LNode{ //定义单链表结点类型 ElemType data; //定义节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode, *LinkList; //...
  • 结点只有一个指针域为单链表,首尾相接为循环链表。 头指针指向链表第一个结点,存储第一个数据为首元结点,首元结点前可能附设头结点。 无头结点时,头指针为空则为空表;有头结点时,头结点的指针域为空则为空表...
  • 链表单链表的基本操作详解(C语言)

    万次阅读 多人点赞 2019-06-01 22:02:15
    本文是单链表的C语言实现方法,包括创建单链表结点、创建单链表、显示链表的数据、获取链表长度、在链表指定位置插入结点、删除指定位置的结点、查找链表中指定的数据、修改链表中指定位置结点的值、修改链表中指定...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 52,823
精华内容 21,129
关键字:

循环列表与单链表的区别