线性表-顺序表与单链表

顺序表

线性表的顺序存储，是逻辑相邻，物理存储地址也相邻。 顺序存储结构示意图.jpg

结构定义

typedef int ElemType;
typedef int Status;

typedef struct {
     ElemType *data;
     int length;
}Sqlist;

• 顺序表的初始化

//顺序表初始化
Status InitList(Sqlist *list) {
    list->data = malloc(sizeof(ElemType) * MAXSIZE);
    if (!list) {
        return ERROR;
    }
    list->length = 0;
    return OK;
}

• 顺序表的插入

//顺序表的插入
/*
 初始条件：顺序线性表L已存在,1≤i≤ListLength(L);
 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
 */
Status InsertList(Sqlist *list, int i, ElemType e) {

    if (i < 1 || i > list->length + 1) {
        return ERROR;
    }
    if (MAXSIZE == list->length) {
        return ERROR;
    }
    
    if (i <= list->length) {
        for (int j = list->length; j >= i; j--) {
            list->data[j] = list->data[j-1];
        }
    }
    list->data[i-1] = e;
    ++list->length;
    return OK;
}

• 顺序表的取值

//顺序表的取值
Status getElem(Sqlist list, int i, ElemType *elem) {
    if (i < 1 || i > list.length) {
        return ERROR;
    }
    if (list.length == 0) {
        return ERROR;
    }
    *elem = list.data[i-1];
    return OK;
}

• 顺序表删除

//顺序表删除
/*
 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 操作结果: 删除L的第i个数据元素,L的长度减1
 */
Status listDelete(Sqlist *list, int i) {
    if (i < 1 || i > list->length) {
        return ERROR;
    }
    if (i == list->length) {
        --list->length;
        return OK;
    }
    for (int j = i; j < list->length - 1; j++) {
        list->data[j] = list->data[j+1];
    }
    --list->length;
    
    return OK;
}

• 顺序表清空

//清空顺序表
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status cleanList(Sqlist *list) {
    list->length = 0;
    return OK;
}

• 顺序表输出

//顺序输出List
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
void Print(Sqlist list) {
    if (0 == list.length) {
        printf("链表为空");
        return;
    }
    printf("链表元素：\n");
    for (int i = 0; i < list.length; i++) {
        printf("%d\n",list.data[i]);
    }
}

• 顺序表查找元素并返回位置

 //顺序表查找元素并返回位置
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int GetIndexFromList(Sqlist list, ElemType e) {
    for (int i = 0; i < list.length; i++) {
        if (e == list.data[i]) {
            return i + 1;
        }
    }
    return -1;
}

单链表

结构定义

typedef int Status;
typedef int ElemType;

typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

单链表的逻辑状态

单链表逻辑状态.jpg

有头结点的单链表的逻辑状态

有头结点的单链表逻辑状态.jpg

添加头结点的意义：
1.便于首元结点的处理
2.便于空表和非空表的统一处理

• 有头结点的单链表的初始化

//初始化单链表线性表
Status InitList(LinkList *list) {
    *list = (LinkList)malloc(sizeof(Node));
    if (NULL == *list) {
        return ERROR;
    }
    (*list)->next = NULL;
    return OK;
}

• 单链表的取值

//单链表取值
/*
 初始条件: 顺序线性表L已存在,1≤i≤ListLength(L);
 操作结果：用e返回L中第i个数据元素的值
 */
Status getElm(LinkList list, int i , LinkList *node) {
    LinkList p = list->next;
    int j = 1;
    while (p->next && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i) {
        return ERROR;
    }
    *node = p;
    return OK;
}

• 单链表删除

//单链表删除元素
/*
 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
 */
Status deleteElm1(LinkList *list, int i, ElemType *e) {
    LinkList p = (*list)->next;
    int j = 1;
    while (p->next && j < i-1) {
        p = p->next;
        j++;
    }
    if (!(p->next) || j > i-1) {
        return ERROR;
    }
    LinkList q = p->next;
    *e = q->data;
    p->next = q->next;
    free(q);
    return OK;
}

• 单链表清空

/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status cleanList(LinkList *list) {
    LinkList p = (*list)->next;
    LinkList q;
    while (p) {
        q = p;
        p = q->next;
        free(q);
    }
    (*list)->next = NULL;
    return OK;
}

• 单链表输出

/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status Print(LinkList list) {
    if (NULL == list->next) {
        printf("链表为空\n");
        return OK;
    }
    LinkList p = list->next;
    printf("链表元素为：\n");
    while (p) {
        printf("%d\n",p->data);
        p = p->next;
    }
    return OK;
}

• 单链表的插入

//单链表插入
/*
 初始条件:顺序线性表L已存在,1≤i≤ListLength(L);
 操作结果：在L中第i个位置之后插入新的数据元素e，L的长度加1;
 */
Status insertList(LinkList *list, int i, ElemType e) {
    LinkList p = *list;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (NULL == p || j > i) {
        return ERROR;
    }
    LinkList s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;

    return OK;
}

• 前插法创建单链表

//单链表前插入法
/* 随机产生n个元素值,建立带表头结点的单链线性表L(前插法)*/
void CreateListHead(LinkList *list, int n) {
    LinkList q;
    
    *list = (LinkList)malloc(sizeof(LinkList));
    (*list)->next = NULL;
    
    for (int i = 0 ; i < n; i++) {
        q = (LinkList)malloc(sizeof(LinkList));
        q->data = i;
        q->next = (*list)->next;
        (*list)->next = q;
    }
}

• 后插法创建单链表

//单链表后插入法
/* 随机产生n个元素值,建立带表头结点的单链线性表L(后插法)*/
void CreateListRear(LinkList *list, int n) {
    *list = (LinkList)malloc(sizeof(LinkList));
    (*list)->next = NULL;
    
    LinkList q;
    LinkList r =  (*list);
    
    for (int i = 0; i < n; i++) {
        q = (LinkList)malloc(sizeof(LinkList));
        q->data = i;
        r->next = q;
        r = q;
    }
    r->next = NULL;
}

附上单链表删除和操作的基本思路示意图：

单链表插入示意图.jpg 单链表删除示意图.jpg

总结：顺序表操作的时候，长度使用length来操作，找指定位置用下标方式查找；单链表的长度判断需要借助最后一个元素指向NULL判断，利用指针域来进行查找。

链表结构与顺序存储结构的优缺点比较：

• 存储分配方式
  顺序存储结构用一段连续的存储单元一次存储线性表的数据元素；
  单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素；
• 时间性能
  查找 顺序存储 O(1) 与 单链表 O(n)
  插入和删除 顺序存储 O(n) 与 单链表 O(1) 顺序表存储结构需要平均移动一个表长一半的元素；单链表查找某个位置的指针后，插入和删除只需要一次操作
• 空间性能
  顺序存储结构需要预先分配存储空间，分太大，浪费空间；分太小，发生溢出
  单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制