线性表

简单的总结一下数据结构中的线性表

顺序存储

• ElemType *elem;
int length;
• 随机存取
• 判断
  • 位置合理
  • 存储空间已满
• 查找，插入，删除 ⇒ 时间复杂度 O(n)

单链表

• ElemType data; struct LNode *next;
• 数据域 & 指针域
• 头节点
  • 首元结点无需特殊区分
  • 空表和非空表统一判断标准
• 判断
  • 当前指针 or 下个指针存在
  • 链表为空
• 查找前驱 O(n)

循环链表

• 判断尾 p→next == L 而不是 p→next == NULL
• 使用尾指针更方便合并 ⇒ 尾指针下一个为头结点

双向链表

• ElemType data; struct DuLNode *prior; struct DuLNode *next;
• 增删需要同时修改 prior 和 next

空间性能

• 顺序表要预先分配 ⇒ 易浪费 & 溢出
• 指针域 ⇒ 存储密度小 ⇒ 长度有限且事先确定大小时，用顺序表

时间性能

• 顺序表取值效率高
• 链表插入删除效率高

Tips

• 特殊点的排除 ⇒ 极端情况(空链表全部)
  判断 NULL, while 条件
• segmentation fault
  →next 是否存在，下标越界，有没有malloc
• 存在头节点
  不能倒过来print，会 print 出头结点的值
• C语言中，没有true，不能 while(true)
• 就地反转 两个指针，提前记录 next，再从当前指向前一个
• while(p) { p = p→next; } 遍历

程序

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

//链表结构体定义
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

//初始化链表
LinkList InitList(){
    LNode *L;
    L = (LNode*)malloc(sizeof(LNode));
    L->next=NULL;
    return L;
}

void PrintList(LinkList L) {
    if(L->next == NULL) {
        return;
    } else {
        LNode *p = L->next;
        while (1) {
            printf("%d", p->data);
            if (p->next != NULL) {
                printf(" ");
                p = p->next;
            } else {
                break;
            }
        }
    }
}

void CreateList(LinkList L)
{
    L->next = NULL;
    LNode *r;
    r = L;
    ElemType x;

    while(1) {
        scanf("%d",&x);
        if(x == -1) {
            break;
        }
        LNode *p;
        p = (LNode *)malloc(sizeof(LNode));
        p->data = x;
        r->next = p;
        r = p;
    }
    r->next = NULL;
}

int length(LinkList L) {
    LNode *p = L->next;
    int length = 1;
    while(p->next) {
        p = p->next;
        ++length;
    }
    return length;
}

Click Here To View DataStructure Section