首页 计算机科学 数据结构

顺序表 (顺序存储)：

  • 优点：可随机存取，存储密度高
  • 缺点：要求大片连续空间，改变容量不方便

单链表 (链式存储)：

  • 优点：不要求大片连续空间，改变容量方便
  • 缺点：不可随机存取，要耗费一定空间存放指针

# 代码定义单链表

typedef struct LNode { //定义单链表节点类型
    ElemType data; //每个节点存放一个数据元素
    struct Lnode *next; //指针指向下一个节点
}LNode,*LinkList;
struct LNode* p=(struct LNode*)malloc(sizeof(struct LNode))
LinkList L;
LNode* L;

# 单链表初始化

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

bool InitList(LinkList &L){ //不带头结点初始化
    L=NULL;
    return true;
}
bool InitList(LinkList &L){ //带头节点初始化
    L=(LNode*)malloc(sizeof(LNode));
    if(L==NULL)
        return false;
   	L->next=NULL;
    return true;
}
bool Empty(LinkList L){ //不带头结点检查
    if(L==NULL)
        return true;
  	else
        return false;
}
bool Empty(LinkList L){
    if(L->next==NULL)
        return true;
   	else
        return false;
}
void test(){
    LinkList L;
    InitList(L);
}

# 插入

带头结点按位序插入：

bool ListInsert(LinkList &L,int i,ElemType e) {
    if(i<1)
        return false;
   	LNode *p; //指针p指向当前扫描到的节点
    int j=0; //当前p指向的是第几个节点
    p=L; //L指向头结点，头结点是第0个节点（不存数据）
    while(p!=NULL && j<i-1){ //循环找到第i-1个节点
        p=p->next;
        j++;
    }
    if(p==NULL) //i值不合法
        return false;
    LNode *s=(LNode*)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s; //将结点s插入到p之后
    return true;
}

不带头结点按位序插入：

bool ListInsert(LinkList &L,int i,ElemType e) {
    if(i<1)
        return false;
    if(i==1){ //插入第一个节点的操作与其他结点操作不同
        LNode *s=(LNode*)malloc(sizeof(LNode));
        s->data=e;
        s->next=L;
        L=s;
        return true;
    }
   	LNode *p; //指针p指向当前扫描到的节点
    int j=0; //当前p指向的是第几个节点
    p=L; //L指向头结点，头结点是第0个节点（不存数据）
    while(p!=NULL && j<i-1){ //循环找到第i-1个节点
        p=p->next;
        j++;
    }
    if(p==NULL) //i值不合法
        return false;
    LNode *s=(LNode*)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s; //将结点s插入到p之后
    return true;
}

指定节点后插操作

bool InsertNextNode(LNode* p,ElemType e){
    if(p==NULL)
        return false;
    LNode *s=(LNode*)malloc(sizeof(LNode));
    if(s==NULL) //内存分配失败
        return false;
    s->data=e;  //用节点s保存数据元素e
    s->next=p->next;
    p->next=s;
    return true;
}

指定节点的前插操作

bool InsertPriorNode(LNode *p,ElemType e){
    if(p==NULL)
        return false;
   	LNode *s=(LNode*)malloc(sizeof(LNode));
    if(s==NULL)
        return false;
    s->next=p->next;
    p->next=s;
    s->data=p->data; //本质上就是先后插，再交换前一个节点和当前节点的值
    p->data=e;
    return true;
}

# 删除

带头结点按位序删除：

bool ListDelete(LinkList &L,int i,ElemType &e){
    if(i<1)
        return false;
    LNode *p;
    int j=0;
    p=L;
    while(p!=NULL && j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL)
        return false;
    if(p->next==NULL) //第i-1个结点之后已无其他结点
        return false;
    LNode *q=p->next; //令q指向被删除节点
    e=q->data; //用e返回元素的值
    p->next=q->next; //将*q结点从链中断开
    free(q); //释放结点的储存空间
    return true;
}

指定节点的删除：

bool DeleteNode(LNode *p){
    if(p==NULL)
        return false;
    LNode *q=p->next; //令q指向*p的后继点
    p->data=p->next->data; //和后继结点交换数据
    p->next=q->next; //将*q结点从链中断开
    free(q); //释放存储空间
    return false;
}

# 查找

按位查找：

LNode* GetElem(LinkList L,int i){
	if(i<0)
        return false;
    LNode *p;
    int j=0;
    p=L;
    while(p!=NULL && j<i){
        p=p->next;
        j++;
    }
    return p;
}

按值查找

LNode *LocateElem(LinkList L,ElemType e){
    LNode *p=L->next;
    //从第1个节点开始查找数据域为e的节点
    while(p!=NULL && p->data!=e){
        p=p->next;
    }
    return p;
}

# 单链表建立

尾插法建立单链表：

LinkList List_TailInsert(LinkList &L){
    int x;
    L=(LinkList)malloc(sizeof(LinkList));
    LNode *s,*r=L; //r为表尾指针
    scanf("%d",&x);
    while(x!=114514){  //输入114514示结束，也可以用其他数字
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }
    r->next=NULL;
    return L;
}

头插法建立单链表：(应用：链表的逆置)

LinkList List_HeadInsert(LinkList &L){
    LNode *s;
    int x;
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    scanf("%d",&x);
    while(x!=9999){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
    }
    return L;
}

# 双链表

结构体定义：

typedef struct DNode {
    ElemType data;
    struct DNode *prior,*next;
}DNode,*DLinkList;

创建双链表及判空：

bool Empty(DLinkList L){
    if(L->next==NULL)
        return true;
   	else
        return false;
}
bool InitDLinkList(DLinkList &L){
    L=(DNode*)malloc(sizeof(DNode));
    if(L==NULL)
        return false;
   	L->prior=NULL;
    L->next=NULL;
    return true;
}

双链表的插入：

bool InsertNextDNode(DNode *p,DNode *s){
    if(p==NULL || s==NULL)
        return false;
    s->next=p->next;
    if(p->next!=NULL)
    	p->next-prior=s;
    s->prior=p;
    p->next=s;
    return true;
}

双链表的删除：

bool DeleteNextDNode(DNode *p){
    if(p==NULL)
        return false;
    DNode *q=p->next;
    if(q==NULL)
        return false;
    p->next=q->next;
    if(q->next!=NULL)
        q->next->prior=p;
    free(q);
    return true;
}

销毁双链表：

void DestoryList(DLinkList &L){
    while(L->next!=NULL)
        DeleteDNode(L);
   	free(L);
    L=NULL;
}

双向链表的遍历：

//前向遍历
while(p!=NULL)
    p=p->next;
//后向遍历
while(p!=NULL)
    p=p->prior;
//前向遍历(跳过头结点)
while(p->prior!=NULL)
    p=p->prior;

# 循环单链表

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;
    return true;
}
bool Empty(LinkList L){ //判断链表是否为空
    if(L->next==L)
        return true;
    else
        return false;
}
bool isTail(LinkList L,LNode *p){ //判断是否为尾结点
    if(p->next==L)
        return true;
    else
        return false;
}

很多时候对链表操作对头部或尾部，可以让 L 指向表尾元素

# 循环双链表

typedef struct DNode {
    ElemType data;
    struct DNode *prior,*next;
}DNode,*DLinkList;

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;
}
bool isTail(DLinkList L,DNode *p){ //判断是否为尾结点
    if(p->next==L)
        return true;
    else
        return false;
}

循环双链表插入与删除：

bool InsertNextDNode(DNode *p,DNode *s){
    s->next=p->next;
    p->next-prior=s;
    s->prior=p;
    p->next=s;
    return true;
}
bool DeleteNextDNode(DNode *p){
    DNode *q=p->next;
    p->next=q->next;
    q->next->prior=p;
    free(q);
    return true;
}

# 静态链表

单链表：各个节点在内存中星罗棋布、散落天涯

静态链表：分配一整片连续的内存空间，各个节点集中安置（用数组的方式实现的链表）

定义：

#define MaxSize 10
typedef struct {
    ElemType data;
    int next;
}SLinkList[MaxSize];

查找：从头结点出发挨个往后遍历节点

插入位序为 i 的节点：

  • 找到一个空的节点，存入数据元素
  • 从头结点找到位序为 i-1 的节点
  • 修改新节点的 next
  • 修改 i-1 号节点的 next

优点：增、删操作不需要大量移动元素

缺点：不能随机存取，只能从头结点开始依次往后查找；容量固定不可变

适用场景：

  • 不支持指针的低级语言
  • 数据元素数量固定不变的场景 (如操作系统的文件分配表 FAT)

# 顺序表与链表对比

逻辑结构：都属于线性表，都是线性结构

存储结构：

  • 顺序表（顺序存储）
    • 优点：支持随机存数、存储密度高
    • 缺点：大片连续空间分配不方便，改变容量不方便
  • 链表（链式存储）
    • 优点：离散的小空间分配方便，改变容量方便
    • 缺点：不可随机存取，存储密度低

基本操作：

  • 创
    • 静态分配：静态数组
    • 动态分配；动态数组（malloc,free）
顺序表链表
弹性（可扩容）较差较优
增、删较差较优
查较优较差