C语言编程数据结构线性表之顺序表和链表原理分析

线性表的定义

线性表是由n(n>=0)个数据元素a1、a2、...、an组成的有限序列，通常用(a1, a2, ..., an)表示，其中a1是线性表的第一个元素，an是线性表的最后一个元素。线性表中的元素个数n称为线性表的长度，当n=0时，线性表为空表。

线性表的分类

根据存储结构，线性表可以分为顺序表和链表两种。

顺序表

顺序表即为按照线性顺序将元素存放在一组连续的存储单元里。

实现顺序表需要使用一块连续的内存空间存储。

在顺序表中，数据元素之间的关系是通过它们在存储空间中的位置相邻而建立的，所以顺序表的存储结构也叫做线性存储结构。

下面是一段创建顺序表的代码示例：

#define MaxSize 50

typedef struct{
    int data[MaxSize];
    int length;
}SqList;

void InitList(SqList &L) {
    L.length = 0;
}

bool InsertList(SqList &L, int i, int e) {
    if(i<1 || i>L.length+1 || L.length==MaxSize)   return false;  // i不合法或者表满
    for(int j=L.length; j>=i; j--)   L.data[j] = L.data[j-1];  // 元素后移
    L.data[i-1] = e;    // 插入新元素
    L.length++; // 长度增加
    return true;
}

bool DeleteList(SqList &L, int i, int &e) {
    if(i<1 || i>L.length)   return false;  // i不合法
    e = L.data[i-1];    // 删除元素
    for(int j=i; j<L.length; j++)    L.data[j-1] = L.data[j];  // 元素前移
    L.length--; // 长度减少
    return true;
}

int GetElem(SqList L, int i) {
    if(i<1 || i>L.length)   return -1;   // i不合法
    return L.data[i-1];
}

链表

链表即为将数据元素分散存储在内存中的不连续的存储单元中。

链表由每个元素的数据域和指向下一个元素的指针域组成，数据域存储元素的数据，指针域存储下一个元素的地址。

下面是一段创建链表的代码示例：

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

void InitList(LinkList &L) {
    L = NULL;
}

bool InsertList(LinkList &L, int i, int 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; int j=1;
    p = L;
    while(p!=NULL && j<i-1) {
        p = p->next;
        j++;
    }
    if(p==NULL) return false;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

bool DeleteList(LinkList &L, int i, int &e) {
    if(L==NULL || i<1)  return false;
    if(i==1) {  // 头结点
        LNode *p = L;
        e = p->data;
        L = L->next;
        free(p);
        return true;
    }
    LNode *p; int j=1;
    p = L;
    while(p!=NULL && j<i-1) {
        p = p->next;
        j++;
    }
    if(p==NULL || p->next==NULL) return false;
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

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

总结

顺序表和链表是数据结构中很基础的内容，在实际应用中也比较常见。当需要经常进行插入和删除操作时，链表的效率就会比较高；当需要进行随机存取操作时，顺序表的效率就会比较高。因此，在实际应用中，需要根据具体的需求来选择使用哪种存储结构。