博客

线性表是最常用且最简单的一种数据结构。它是n个数据元素的有限序列。

线性表的顺序储存结构称为顺序表，顺序表中相邻的元素在计算机内有着相邻的存储位置。

顺序表是一种能够随机存取的存储结构。

下面列出顺序线性表的建立、插入元素、删除元素的实现。

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

#define ElemType int        
//数据元素的数据类型
#define LIST_INIT_SIZE 100  
//线性表储存空间的初始分配量
#define LISTINCREMENT 10    
//线性表储存空间的分配增量

typedef int Status;

/*--建立list线性表结构体--*/
typedef struct Sq{
    ElemType *elem;         //存储空间基址
    int length;             //当前长度
    int listsize;           //当前分配的储存容量
}SqList;

/*--构造一个空的线性表L--*/
Status InitList_Sq(SqList &L){
    L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!L.elem){
        return 0;
    }
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;
    return 1;
}

/*--在顺序线性表L中第i个位置之前插入一个新的元素e--*/
Status ListInsert_Sq(SqList &L, int i, ElemType e){  
    ElemType *p;
    if(i < 1 || i > L.length+1){
        return 0;
    }
    if(L.length >= L.listsize){
    // 当前存储空间已满，增加容量
    ElemType *newbase = (ElemType *)realloc(L.elem,
                  (L.listsize+LISTINCREMENT)*sizeof (ElemType));
    if(!newbase){
        return 0;                 // 存储分配失败
    }
    L.elem = newbase;             // 新基址
    L.listsize += LISTINCREMENT;  // 增加存储容量
    }
    ElemType *q = &(L.elem[i-1]); // q为插入位置
    for (p = &(L.elem[L.length-1]); p>=q; --p) *(p+1) = *p;
                                  // 插入位置及之后的元素右移
    *q = e;                       // 插入e
    ++L.length;                   // 表长增1
    return 1;
}

/*--在顺序线性表L中删除第i个元素，并用e返回其值--*/
Status ListDelete_Sq(SqList &L, int i, ElemType &e) {  
    ElemType *p, *q;
    if (i<1 || i>L.length){
        return 0;
    }
    p = &(L.elem[i-1]);
    e = *p;
    q = L.elem+L.length-1;
    for(++p; p<=q; ++p){
        *(p-1) = *p;     // 被删除元素之后的元素左移
    }
    --L.length;          // 表长减1
    return 1;
}

/*--遍历输出顺序线性表--*/
void out(SqList &L){
    int k;
    for(k=0;k<L.length;++k){
        printf("%d ",L.elem[k]);
        if(k == L.length-1){
            printf("\n");
        }
    }
}

int main(){
    int i,j,e,lo,temp;
    SqList *L=(SqList*)malloc(sizeof(SqList));
    InitList_Sq(*L);
    printf("请输顺序表的长度:\n");
    scanf("%d",&L->length);
    printf("请输入顺序表的各个元素:\n");
    for(i=0;i<L->length;++i){
        scanf("%d",&L->elem[i]);
    }
    printf("输入的顺序表是:\n");
    out(*L);
    printf("请输入插入的位置以及节点:\n");
    scanf("%d%d",&j,&e);
    ListInsert_Sq(*L,j,e);
    printf("插入后的顺序表为:\n");
    out(*L);
    printf("请输入要删除数据元素的的位置：");
    scanf("%d",&lo);
    ListDelete_Sq(*L,lo,temp);
    out(*L);
    free(L);
    return 0;
}

仅用于互相参考学习，欢迎大家留言探讨学习^-^!

Andrew Liang