美文网首页
03数据结构-顺序存储与链式存储结构

03数据结构-顺序存储与链式存储结构

作者: 小猪也浪漫 | 来源:发表于2020-04-03 18:09 被阅读0次

    一、顺序存储

    • 顺序存储结构: 数据元素存放在一组存储地址连续的存储单元里，其数据元素间的逻辑关系和物理关系是一致的

    1.0 我们对 数据结构、状态、类型和一些常数进行定义

    
//线性表的最大容量
#define MAXSIZE 100
//操作状态-成功
#define SUCCESS 1
//操作状态-失败
#define ERROR 0
#define TRUE 1
#define FALSE 0

//表内元素的类型 假设为 int
typedef int ItemType;
//返回各个函数的操作码
typedef int Status;
//顺序表
typedef struct {
//    指向一块连续的内存空间来存储数据
    ItemType *data;
//    表的长度
    int length;
}List;

    1.1 初始化

    为线性表开辟一段连续的内存空间。

    
Status initList(List *l){
//    开辟一段连续的空间给顺序表
    l->data = malloc(sizeof(ItemType) * MAXSIZE);
//    如果存储分配失败，则退出
    if (!l->data) exit(ERROR);
    
    l->length = 0;
    return SUCCESS;
        
}

    1.2 输出

    访问并输出线性表的各个元素。线性表的元素访问可以直接通过下标来访问。

    
//遍历并打印线性表
Status listPrint(List l){
    if (!l.length) {
        printf("Empty list.");
        return ERROR;
    }
    printf("数组输出：");
    for (int i = 0; i < l.length; i++) {
        printf("%d ",l.data[I]);
    }
    printf("\n");
    return SUCCESS;
}

    1.3 增

    为特定位置添加新的元素。注意需要对线性表的length进行操作，还要进行一定的容错判断。

    
/// 在i位置插入新的元素 e
/// @param l 数组
/// @param I 位置
/// @param e 新元素
Status listInsert(List *l, int i, ItemType e){
//    插入位置是否合法
    if (i < 1 || i > l->length + 1) return ERROR;
//    是否还有剩余空间
    if (l->length == MAXSIZE) return ERROR;
    
    if (i <= l->length) {
        for (int j = l->length-1; j >= i - 1; j--) {
//            将插入位置以及之后的位置向后移动一位
            l->data[j+1] = l->data[j];
        }
    }
//    将新元素放入i位置
    l->data[i-1] = e;
//    长度+1
    l->length++;
    return SUCCESS;
}

    1.4 删

    删除特定位置的元素。注意需要对线性表的length进行操作，还要进行一定的容错判断，删除元素需要带回。

    
/// 删除 i 位置的原素
/// @param l 数组
/// @param I 位置
/// @param e 删除元素带回
Status listDelete(List *l, int i, ItemType *e){
    if (i < 1 || i > l->length ) return ERROR;
//    保留原值
    *e = l->data[i-1];
    for (int j = i; j < l->length; j++) {
//        被删除元素之后的元素向前移动一位
        l->data[j-1] = l->data[j];
    }
//    表长度减一
    l->length--;
    return SUCCESS;
}

    1.5 查

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

    int LocateElem(Sqlist L,ElemType e)
{
    int I;
    if (L.length==0) return 0;
    
    for(i=0;i<L.length;i++)
    {
        if (L.data[i]==e)
            break;
    }
  
    if(i>=L.length) return 0;
    return I+1;
}

    1.6 清空

    清空顺序表

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

    1.7 调用情况

    int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, Data Structure!\n");
    
    Sqlist L;
    Sqlist Lb;
    ElemType e;
    Status iStatus;
    
    //1.1 顺序表初始化
    iStatus = InitList(&L);
    printf("初始化L后: L.Length = %d\n", L.length);
    
    //1.2 顺序表数据插入
    for(int j = 10; j > 0; j--){
        iStatus = ListInsert(&L, L.length, j);
    }
    printf("插入数据L长度: %d\n",L.length);
//
//    //1.3 顺序表取值
//    GetElem(L, 5, &e);
//    printf("顺序表L第5个元素的值为:%d\n",e);
//
//    //1.4 顺序表删除第1个元素
//    ListDelete(&L, 1);
//    printf("顺序表删除第%d元素,长度为%d\n",1,L.length);
//

    
    
//    //1.5 清空顺序表
//    iStatus = ClearList(&L);
//    printf("清空后,L.length = %d\n",L.length);
//
//    //1.6 判断List是否为空
//    iStatus=ListEmpty(L);
//    printf("L是否空：i=%d(1:是 0:否)\n",iStatus);
//
//    //1.8 TraverseList
//    for(int j=1; j <= 5;j++){
//        iStatus = ListInsert(&L, 1, j);
//    }
//    TraverseList(L);
    
    
    return 0;
}

    二、 链式存储

    • 链式存储结构: 数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的

    2.0 我们对 数据结构、状态、类型和一些常数进行定义

    #define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */

//定义结点
typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node *LinkList;

    2.1 初始化单链表线性表

    Status InitList(LinkList *L){
    *L = (LinkList)malloc(sizeof(LinkList) * MAXSIZE);
    if (*L == NULL) return ERROR;
    (*L)->next = NULL;
    return OK;
}

    2.2 单链表插入

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

    2.3 单链表取值

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

    2.4 单链表删除元素

    /*
 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
 */

Status ListDelete(LinkList *L,int i,ElemType *e){
    int j = 1;
    LinkList p = (*L)->next;
    while (p && j < (i-1)) {
        p = p->next;
        j ++;
    }
    if(!(p->next) || j > (i-1)) return ERROR;
    
    LinkList s = p->next;
    *e = s->data;
    p->next = s->next;
    free(s);
    return OK;
}

    2.5 数据遍历

    /* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(LinkList L)
{

    LinkList p = L->next;
    while (p) {
        printf("%d \n",p->data);
        p = p->next;
    }
    return OK;
}

    2.6将L重置为空表

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

    2.7 单链表前插入法

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

    2.8 单链表后插入法

    /* 随机产生n个元素值,建立带表头结点的单链线性表L(后插法)*/
void CreateListTail(LinkList *L, int n){
    LinkList s = malloc(sizeof(LinkList));
    s->data = n;
    s->next = NULL;
    LinkList p = *L;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = s;
}

    2.9 调用情况

    int main(int argc, const char * argv[]) {
    Status iStatus;
    LinkList L,L2,L3;
    ElemType e;
     //2.1 单链表初始化
    iStatus = InitList(&L);
    printf("L1是否初始化成功:%d\n",iStatus);
    
    //2.2 单链表插入数据
    for(int j = 1;j<=10;j++)
    {
        iStatus = ListInsert(&L, 1, j);
    }
    printf("L 插入后\n");
    ListTraverse(L);
    
    //2.3 单链表获取元素
    GetElem(L,5,&e);
    printf("第5个元素的值为：%d\n",e);
    
    //2.4 删除第5个元素
      iStatus = ListDelete(&L,7, &e);
      printf("删除第7个元素值为:%d\n",e);
      ListTraverse(L);
    
//    //3.1 前插法整理创建链表L
//
//    CreateListHead(&L, 20);
//    printf("整理创建L的元素(前插法):\n");
//    ListTraverse(L);
//
//    //3.2 后插法整理创建链表L
//    CreateListTail(&L, 99);
//    printf("整理创建L的元素(后插法):\n");
//    ListTraverse(L);
    

    return 0;
}

    三、 单链表与顺序表的对比

    • 存储方式：顺序表用一组连续的存储单元依次存储线性表的数据元素；而单链表用一组任意的存储单元存放线性表的数据元素。

    • 时间性能：采用循序存储结构时查找的时间复杂度为O(1)，插入和删除需要移动平均一半的数据元素，时间复杂度为O(n)。采用单链表存储结构的查找时间复杂度为O(n)，插入和删除不需要移动元素，时间复杂度仅为O(1）。

    • 空间性能：采用顺序存储结构时需要预先分配存储空间，分配空间过大会造成浪费，过小会造成问题。采用单链表存储结构时，可根据需要进行临时分配，不需要估计问题的规模大小，只要内存够就可以分配，还可以用于一些特殊情况，如一元多项的表示。

    相关文章

      网友评论

          本文标题：03数据结构-顺序存储与链式存储结构

          本文链接：https://www.haomeiwen.com/subject/qplkphtx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|03数据结构-顺序存储与链式存储结构|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！