精华内容
下载资源
问答
  • //双向链表和单链表的区别及其初始化 //相比单链表,多了一个前驱指针域 //初始化的时候,多了一步(详见初始化函数) typedef struct lNode { int data; //数据域 struct lNode *ne...
    #include <iostream>
    #include <cstdlib>
    using namespace std;
    
    //双向链表和单链表的区别及其初始化
    //相比单链表,多了一个前驱指针域
    //初始化的时候,多了一步(详见初始化函数)
    
    typedef struct lNode
    {
        int data;    //数据域
        struct lNode *next;  //后继指针域
        struct lNode *prior; //前驱指针域 
    }LNode, *LinkList;
    
    /******************初始化双向链表*************************/
    void InitList(LinkList &l)
    {
        //初始化生成一个{1,2,3,4,5,6}这样的单链表
        LinkList p , q;
        //成功创建一个头结点(空结点)
        l = (LinkList)malloc(sizeof(LinkList));
        l->next=NULL;
        p=l;
        //开始生成单链表(尾插法,每次插入在最后一个结点后面进行)
        for(int i=1 ; i<=6 ; i++)
        {
            q=(LinkList)malloc(sizeof(LinkList));
            q->data=i;
            p->next =q;
            q->prior=p;  //区别1:与单链表的区别多在这一步
            p=q;
            p->next=NULL;
        }
    }
    
    /******************显示双向链表*************************/
    void Showlist(LinkList &l)
    {
        LinkList p,r;
        //正向显示
        for(p=l->next;p!=NULL;p=p->next)
        {
            cout<<p->data<<"  ";
            r=p; //起标志作用,方便后面反向输出
        }
        cout<<endl;
        //反向显示
        for(r;r!=l;r=r->prior)
            cout<<r->data<<"  ";
    }
    
    int main()
    {
        LinkList l ;
        InitList(l);
        Showlist(l);
        return 0;
    }
    
    
    展开全文
  • 文章目录带头结点的双向循环链表和单链表的区别面试题:写一个双向链表代码实现 带头结点的双向循环链表和单链表的区别   相比我们讲的无头单向非循环的单链表结构,他的插入和删除都是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
    }
    
    展开全文
  • 循环链表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 DNode {
    ElemType data;
    struct DNode *prior, *next;
    }DNode,*DLinklist;
    
    

    1.1 插入操作

    在这里插入图片描述

    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
    

    1.2 删除操作

    准备删除的结点q的后继节点赋给p的后继节点,q结点的下一个结点的前驱结点指向 p
    在这里插入图片描述

    p->next = q->next;
    q->next-> prior = p;
    free(q);
    

    2. 循环链表

    循环链表是一种链式存储结构,它的最后一个结点指向头结点,形成一个环。因此,从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致,差别仅仅在于算法中的循环条件有所不同。

    2.1 循环单链表

    在这里插入图片描述

    2.2 循环双链表

    在这里插入图片描述

    2.3 循环链表判空

    2.3.1 循环单链表

    L->next == L;
    

    2.3.2 循环双链表

    L->next ==L;
    L->prior == L;
    

    3. 静态链表

    静态链表和单链表的区别
    静态链表:把地址改成数组下标,下一个结点地址改为下一个结点的下标
    在这里插入图片描述
    在这里插入图片描述

    #define Maxsize 50
    typedef struct DNode{
    ElemType data;
    int next;
    SLinkList[Maxsize] ;
    
    

    4. 顺序表与链表比较

    4.1 存取方式

    单链表只能顺序存取,顺序表可以通过计算得到相应的数据元素地址从而达到随机存取。

    4.2 逻辑结构、物理结构

    单链表:数据元素存放位置可能相邻可能不相邻
    顺序表:一定相邻

    4.3 基本操作

    插入:
    单链表:修改指针即可
    顺序表:依次向后移位
    删除:
    顺序表:依次向前移位
    单链表:修改结点的指针
    查找:
    1.按值查
    顺序表:依次遍历,O(n)
    单链表:依次遍历,O(n)
    2.按序号查:
    顺序表:数组下标直接查找
    单链表:依次遍历

    4.4 内存空间

    顺序存储:无论静态分配还是非静态都需要预先分配合适的内存空间
    静态分配时预分配空间太大回造成浪费,太小会造成溢出
    动态分配时虽不会溢出但是扩充需要大量移动元素,操作效率低
    链式存储:在需要时分配结点空间即可,高效方便,但指针要使用额外空间

    总结

    区别 顺序表 单链表
    存取方式 顺序表可以实现顺序存取和随机存取 单链表只能实现顺序存取
    逻辑、物理存储 顺序表逻辑相邻物理上也相邻,通过相邻表示逻辑关系 单链表逻辑相邻物理上不一定相邻,通过指针表示逻辑关系
    内存空间 动态分配时扩充效率低 高效、方便
    基本操作 顺序表 单链表
    插入&删除 O{n)且需要大量移动元素 O(1)(节点指针已知);O(n)(节点指针未知),但操作时只需修改指针
    查找(按序) O(1) O(n)
    查找(按值且无序) O(n) O(n)

    4.5 怎样选择线性表的存储结构

    在这里插入图片描述

    4.6 三个常用操作

    在这里插入图片描述

    4.6.1 最值:

    4.6.1.1 顺序表

    顺序表:变量:min、max ,遍历数组分别与最大值最小值比较,如果比最大值大或比最小值小就替换预设变量。时间复杂度:O(n)

    int min = L[O];
    int max = L[O];
    for(int i = o;i < n;i++){
    	if(min > L[O])
    		min = L[O];
    	if(max<L[O])
    		max = L[0];
    
    

    4.6.1.2 单链表

    单链表:设变量,遍历链表,时间复杂度:O(n)

    int min = p-> next ->data;
    int max = p -> next ->data;
    for( ; p != NULL; p = p ->next){
    	if(min > p ->data)
    		min = p ->data;
    	if(max< p ->data)
    		max = p ->data;
    
    

    4.6.2 逆置

    4.6.2.1 顺序表:

    设置标志i、j,分别放到数组的最后和最前,ij的元素交换,i向后移,j向前移。一直到j=i;时间复杂度O(n)
    在这里插入图片描述

    inti= o;
    int j = n-1;
    while(i< j){
    	temp =L[i];
    	L[i]= L[j];
    	L[j]= temp;
    }
    

    4.6.2.2 单链表

    单链表:头结点指针、尾结点指针。头结点插入尾结点,一直到r只向头结点

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    while(p ->next != r){
    temp = p-> next;
    p -> next = temp -> next;
    temp -> next = r-> next;
    r -> next = temp;
    
    

    4.6.3 合并

    4.6.3.1 顺序表

    两个数组依次比较,最小的放入新数组,并且依次后移
    在这里插入图片描述

    int i= 0,j = O;
    int k = O;
    for( ; i<L1_Size &&j <L2_Size; k++){
    	if(L1[i]<L2[j]
    		L[k]=L1[i++];
    	else
    		L[k]= L2[j++];
    }
    while(i<L1_Size)
    	L[k++]=L1[i++];
    while(j<L2_Size)
    	L[k++]=L1[i++];
    
    

    4.6.3.2 单链表

    单链表:两个链表循环比较,移动指针。
    在这里插入图片描述
    在这里插入图片描述

    while(p->next!=NULL &&q->next!=NULL){
    	if(p->next->data < q->next->data){
    		r->next = p->next;
    	p->next= p->next- > next;
    	r= r- >next;
    	}
    	else{
    		r- >next = q->next;
    		q->next= q->next- >next;
    		r = r- >next;
    	}
    }
    if(p->next != NULL) r-> next = p ->next;
    if(q->next != NULL)r-> next = q ->ne
    free(p); free(a);
    
    

    这里与顺序表不同,当一个链表的为空后,只需将下一个链表的指针指向新表,不需要再次循环。

    展开全文
  • 链表跟数组的区别: 数组随机访问性强(通过下标进行快速定位),查找速度快; 链表不能随机查找,必须从第一个开始遍历,查找效率低 数组插入删除效率低(插入删除需要移动数据), 链表插入删除速度快(因为有...
    链表跟数组的区别:

    数组随机访问性强(通过下标进行快速定位),查找速度快;
    链表不能随机查找,必须从第一个开始遍历,查找效率低

    数组插入和删除效率低(插入和删除需要移动数据),
    链表插入删除速度快(因为有next指针指向其下一个节点,通过改变指针的指向可以方便的增加删除元素)

    数组浪费内存(每次创建数组之前必须规定数组的大小,静态分配内存,大小固定),
    链表内存利用率高,不会浪费内存(可以使用内存中的不连续空间,并且可以动态括展空间)

    数组利用下标定位,时间复杂度为O(1),
    链表定位元素时间复杂度O(n);

    数组插入或删除元素的时间复杂度O(n),
    链表的时间复杂度O(1)。

    单链表和双链表的区别:

    单链表只有一个指向下一结点的指针,也就是只能next(单链表只能单向读取)

    双链表除了有一个指向下一结点的指针外,还有一个指向前一结点的指针,可以通过prev()快速找到前一结点
    在这里插入图片描述
    1、删除单链表中的某个结点时,一定要得到待删除结点的前驱(加待删除节点),得到该前驱有两种方法,第一种方法是在定位待删除结点的同时一路保存当前结点的前驱。第二种方法是在定位到待删除结点之后,重新从单链表表头开始来定位前驱。尽管通常会采用方法一。但其实这两种方法的效率是一样的,指针的总的移动操作都会有2*i次。而如果用双向链表,则不需要定位前驱结点。因此指针总的移动操作为i次。

    2、查找时也一样,我们可以借用二分法的思路,从中间节点开始前后同时查找,这样双链表的效率可以提高一倍。

    可是为什么市场上单链表的使用多余双链表呢?
    从存储结构来看,每个双链表的节点要比单链表的节点多一个指针(多存放一个引用),这在一些追求时间效率不高应用下并不适应,因为它占用空间比较大;这时设计者就会采用以时间换空间的做法,选取单链表,这时一种工程总体上的衡量。

    转载:https://www.cnblogs.com/brxHqs/p/9778513.html

    展开全文
  • 循环链表2.1 循环单链表2.2 循环双链表2.3 循环链表判空2.3.1 循环单链表2.3.2 循环双链表3. 静态链表4. 顺序表与链表比较4.1 存取方式4.2 逻辑结构、物理结构4.3 基本操作4.4 内存空间总结4.5 怎样选择线性表...
  • 循环链表2.1 循环单链表2.2 循环双链表2.3 循环链表判空2.3.1 循环单链表2.3.2 循环双链表3. 静态链表4. 顺序表与链表比较4.1 存取方式4.2 逻辑结构、物理结构4.3 基本操作4.4 内存空间总结4.5 怎样选择线性表...
  • 单链表和双链表的区别

    千次阅读 2019-01-23 18:34:33
    双链表既有指向下一个结点指针,也有指向上一个结点指针 二、适用情况不同 单向链表更适合元素增加与删除 双向链表更适合元素查询工作 三、读取不同 单链表只能单向读取 双链表可以双向读取 ...
  • 单链表和双向链表的数据结构都包含指向下一个元素指针 next, 双向链表还包括指向上一个元素指针 previous 单链表只能向后遍历, 双向链表向前向后都可以遍历
  • 文字:独木排版:独木图片:独木— 往期回顾 —数据结构考研学习笔记(二)---顺序表应用数据结构考研学习笔记(一)—顺序表基本操作:插入... 循环链表2.1 循环单链表2.2 循环双链表2.3 循环链表判空2.3.1 循环单链表2...
  • 单链表和双链表都是链表的实现,其中单链表的每个元素都包含一些数据以及到下一个元素的链接,从而可以保持结构。另一方面,双向链接列表中的每个节点也包含指向前一个节点的链接。以下是单链接列表和双链接列表之间...
  • 文字:独木排版:独木图片:独木— 往期回顾 —数据结构考研学习笔记(二)---顺序表应用数据结构考研学习笔记(一)—顺序表基本操作:插入... 循环链表2.1 循环单链表2.2 循环双链表2.3 循环链表判空2.3.1 循环单链表2...
  • 链表单链表

    2019-05-02 00:15:44
    什么是链表?链表的分类? 链表是一种物理存储结构上非连续,非顺序的存储结构,...带头结点不带头结点的区别 带头结点: head->p1->p2->p3 不带头结点: p1->p2->p3 带头结点单链表实现 SList.h ...
  • 单链表双链表,循环链表的区别

    千次阅读 2019-02-18 16:45:06
    单向链表(单链表)  单向链表,它包含两个域,一个信息域一个指针域。这个链接指向表中下一个节点,而最后一个节点则 指向一个空值NULL。...双向链表,(双链表)  双向链表中不仅有指向...
  • 链表——单链表

    2020-04-06 20:53:16
    单链表与顺序表的逻辑存储形式一样,都是线性存储,但是单链表的物理存储缺并不一定连续,它的每个元素之间是由地址指针相连的,所以它的每个单位是由一个存储元素一个地址指针组成的节点,结构图如下: ...

空空如也

空空如也

1 2 3 4 5 ... 16
收藏数 318
精华内容 127
关键字:

双链表和单链表的区别