特殊链表(循环单链表,循环双链表,静态链表)

简介: 特殊链表(循环单链表,循环双链表,静态链表)

1.循环单链表的初始化

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
bool InitList(LinkList &L)
{
    L=(LNode*)malloc(sizeof(LNode));//建立一个空表分配一个头结点
    if(L==NULL)
        return false;
    L->next=L;//头结点next指向头结点
    return true;
}
//判断循环单链表是否为空
bool Empty(LinkList L)
{
    if(L->next==L)
        return ture;
    else
        return false;
}
//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L,LNode *p)
{
    if(p->next==L)
        return true;
    else
        return false;
}
L->next=L;



2.循环双链表


typedef int ElemType;
typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
}
bool InitDLinkList(DLinkList &L)
{
    L=(DNode*)malloc(sizeof(DNode));
    if(L==NULL)
        return false;
    L->prior=L;
    L->next=L;
    return true;
}
//判断循环双链表是否为空表
bool Empty(DLinkList L)
{
    if(L->next==L)
        return true;
    else
        return false;
}
//判断结点p是否为循环双链表的表尾结点
bool isTail(DLinkList L,DNode *p)
{
    if(p->next==L)
        return true;
    else
        return false;
}
void testLinkList()
{
    DLinkList L;
    InitDLinkList(L);
   
}


对于普通双链表的插入操作而言


s->next=p->next;


p->next->prior=s;//是有错误的


s->prior=p;


p->next=s;



但是对于循环双链表而言是正确的


对于普通链表的删除操作而言


p->next=q->next;


q->next->prior=p;//要删除的结点q是最后一个结点,这里就会存在问题


free(q);



但是对循环双链表而言是正确的


3. 静态链表


单链表和静态链表的区别


1.单链表的指针是指明了具体的内存地址,静态链表的游标指的是下一个元素的数组下标,例如0号结点,他的游标是2,那么第一个元素就是下标为2的元素,即1


2.单链表的表尾元素是指向NULL的,而静态链表中最后一个结点的游标可以设为-1


3.如图所示,如果每个数据元素4B,每个游标4B(每个结点是8B),e1的地址就是(0号结点的地址)+8*2(要寻找的结点的数组下标)


#define MaxSize 10
typedef int ElemType;
struct Node{
    ElemType data;
    int next;
};
void testLinkList(){
    struct Node a[MaxSize];  //a是一个Node型数组
}
//也可以写为
typedef struct{
    ElemType data;
    int next;
}SLinkList[MaxSize];
   
void testLinkList(){
    SLinkList a;//a是一个数组,这个数组有10个元素  
//这里a是一个静态链表
}


测试代码


#include<stdio.h>
#include<stdlib.h>
#define MaxSize 10
struct Node{
  int data;
  int next;
};
typedef struct{
  int data;
  int next;
}SLinkList[MaxSize];
int main()
{
  struct Node x;
  printf("sizeX=%d\n",sizeof(x));
  struct Node a[MaxSize];
  printf("sizeA=%d\n",sizeof(a));
  SLinkList b;
  printf("sizeB=%d\n",sizeof(b));
  return 0;
}

结果



可以看到


struct Node a[MaxSize]等价于LinkList a


(1)静态链表的初始化

对于单链表而言,初始化就是将结点指向NULL


所以对于静态链表的初始化就是将头结点指向-1


(2)静态链表的插入

①找到一个空的结点,存入数据元素


②从头结点出发找到位序为i-1的结点


③修改新节点的next


④修改i-1的结点的next


举个例子


#include <stdio.h>
#define MaxSize 100
typedef struct {
  int data;
  int next;
} SLinkList[MaxSize];
// 初始化静态链表
void InitList(SLinkList list) {
  for (int i = 0; i < MaxSize; i++) {
    list[i].next = -1;  // 初始化指针域为-1,表示空节点
  }
}
// 插入元素到静态链表的末尾
void Insert(SLinkList list, int data) {
  int index = 0;
  while (list[index].next != -1) {
    index = list[index].next;  // 找到最后一个节点
  }
 
  // 创建新节点
  list[index].next = index + 1;  // 设置最后一个节点的指针指向新节点
  list[index + 1].data = data;  // 设置新节点的数据域
  list[index + 1].next = -1;  // 新节点的指针域设置为-1
}
// 打印静态链表
void PrintList(SLinkList list) {
  int index = list[0].next;
  while (index != -1) {
    printf("%d ", list[index].data);
    index = list[index].next;
  }
  printf("\n");
}
int main() {
  SLinkList list;
  InitList(list);
  // 在静态链表中插入元素
  Insert(list, 10);
  Insert(list, 20);
  Insert(list, 30);
 
  // 打印静态链表
  PrintList(list);
  return 0;
}


静态链表的优点


增删操作不需要大量的移动元素


静态链表的缺点


不能随机存取,只能从头结点开始一次往后查找


容量固定不变


目录
相关文章
|
1月前
|
存储 算法 C语言
C语言手撕实战代码_循环单链表和循环双链表
本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作;以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段,展示了每种算法的实现思路与步骤,帮助读者深入理解并掌握这些数据结构的基本操作方法。
|
4月前
|
存储
链表入门(单链表讲)
链表入门(单链表讲)
链表入门(单链表讲)
|
3月前
链表4(法二)------7-4 sdut-C语言实验-单链表中重复元素的删除
链表4(法二)------7-4 sdut-C语言实验-单链表中重复元素的删除
29 0
|
5月前
|
存储 编译器
单链表与双链表实现
单链表与双链表实现
|
4月前
|
存储
【海贼王的数据航海】链表—单链表
【海贼王的数据航海】链表—单链表
28 0
|
4月前
|
算法
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
58 0
|
4月前
|
存储 算法
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
32 0
|
5月前
|
Java
DAY-1 | Java数据结构之链表:删除无头单链表中等于给定值 val 的所有节点
力扣203题解:使用时间复杂度为O(n)的思路删除链表中所有值为key的元素。引入辅助指针pre,记录cur的前一个节点,遍历链表时,若cur.val!=key,pre和cur同时前进;若cur.val==key,则pre.next=cur.next,cur继续前进,确保pre不急于跟随以处理连续相同值的情况。遍历结束后,处理头节点可能需要删除的特殊情况。
43 0
|
5月前
|
存储 算法 索引
数据结构与算法④(第二章下)链表概念+单链表的实现
数据结构与算法④(第二章下)链表概念+单链表的实现
38 0
|
4月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表