顺序线性表

线性表的顺序表示和实现

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。

线性表的第一个数据元素a1的存储位置,通常称作线性表的起始位置或基地址。

只要确定了存储线性表的起始位置,线性表中任一数据元素都可随机存取,所以线性表的顺序存储结构是一种随机存取的存储结构。

数组类型有随机存取的特性,因此通常都用数组来描述数据接哦故中的顺序存储结构。由于线性表的长度可变,且所需最大存储空间随问题不同而不同,在C语言中可用动态分配的一维数组,如下描述。

/* 线性表的动态分配顺序存储结构 */
#define LIST_INIT_SIZE 100   /* 线性存储空间的初始分配量 */
#define LISTINCREMENT  10   /* 线性存储空间的分配增量 */

typedef struct {
     ElemType *elem;        /* 存储空间基址 */
     int length;            /* 当前长度 */
     int listsize;          /* 当前分配的存储容量(以sizeof(ElemType)为单位) */
} SqList;

在上述定义中,数组指针elem指示线性表的基地址,length指示线性表的当前长度。顺序表的初始化操作就是为顺序表分配一个预定定义大小的数组空间,并将线性表的当前长度设为“0”。listsize指示顺序表当前分配的存储空间大小,一旦因插入元素而空间不足时,可进行再分配,即为顺序表增加一个大小为存储LISTINCREMENT个数据元素的空间。

要特别注意的是,C语言中数组的下标是从“0”开始,因此,若L是SqList类型的顺序表,则表中第i个数据元素是L.elem[i-1]。

1 //构造一个空的线性表
2 Status InitList_Sq(SqList &L) {
3     L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
4     if (!L.elem) exit(OVERFLOW);
5     L.length = 0;                //空表长度为0
6     L.listsize = LIST_INIT_SIZE; //初始存储容量
7     return OK;
8 }

一般情况下,在第i(1<= i <= n)个元素之前插入一个元素时,需将第n至第i(共n-i+1)个元素向后移动一个位置。如下算法:

 1 //在线性表中插入元素
 2 //在顺序线性表L中第i个位置之前插入新的元素e, i的合法值为 1<= i <= ListLength_Sq(L) + 1
 3 Status ListInsert_Sq(SqList &L, int i, ElemType e) {
 4     ElemType *newbase = NULL;
 5     ElemType *p = NULL;
 6     ElemType *q = NULL;
 7     if (i <1 || i >L.length + 1) return ERROR;
 8     if (L.length >= L.listsize) {
 9         newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
10         if (!newbase) exit(OVERFLOW);
11         L.elem = newbase;
12         L.listsize += LISTINCREMENT;
13     }
14     q = &(L.elem[i - 1]);  //q为插入位置
15     for (p = &(L.elem[L.length - 1]); p >= q; --p) 
16         *(p + 1) = *p; //插入位置及之后的元素右移  
17     *q = e;
18     ++L.length;
19     return OK;
20 }

删除第i(1<= i <= n)个元素时需将从第i+1至第n(共n-i)个元素依次向前移动一个位置。如下算法:

 1 //删除线性表中的元素
 2 //在顺序线性表L中删除第i个元素, 并用e返回其值, i的合法值为 1<= i <= ListLength_Sq(L)
 3 Status ListDelete_Sq(SqList &L, int i, ElemType &e) {
 4     ElemType *p = NULL;
 5     ElemType *q = NULL;
 6     if ((i < 1) || (i > L.length)) return ERROR;
 7     p = &(L.elem[i - 1]);   //p为被删除元素的位置
 8     e = *p;
 9     q = L.elem + L.length - 1;    //表尾元素位置
10     for (++p; p <= q; ++p) *(p - 1) = *p; //被删除元素之后的元素左移
11     --L.length;   //表长减1
12     return OK;
13 }

在顺序表L中查访是否存在和e相同的数据元素的最简便的方法是,令e和L中的数据元素逐个比较。如下算法:

 1 int LocateElem_Sq(SqList L , ElemType e , Status (*compare)(ElemType , ElemType))
 2 {
 3     //在顺序线性表L中查找第1个值与e满足compare()的元素的位序
 4     //若找到,则返回其在L中的位序,否则返回0
 5     i = 1;     //i的初值为第1个元素的位序
 6     p = L.elem;     //p的初值为第1个元素的存储位置
 7     while(i <= L.length && !(*compare)(*p++ , e))
 8         ++i;
 9     if(i <= L.length)    return i;
10     else
11         return 0;
12 }

顺序线性表的实现代码如下:

  1 //线性表的顺序表示与实现 
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 
  5 /******************************************************************************
  6 /* 数据类型和常量定义
  7 /******************************************************************************/
  8 #define TURE         1
  9 #define FALSE        0
 10 #define OK           1
 11 #define ERROR        0
 12 #define OVERFLOW    -2
 13 
 14 typedef int Status;
 15 typedef int ElemType;
 16 
 17 /******************************************************************************
 18 /* 数据结构声明
 19 /******************************************************************************/
 20 /* 线性表的动态分配顺序存储结构 */
 21 #define LIST_INIT_SIZE 2   /* 线性存储空间的初始分配量 */
 22 #define LISTINCREMENT  1   /* 线性存储空间的分配增量 */
 23 
 24 typedef struct {
 25     ElemType *elem;        /* 存储空间基址 */
 26     int length;            /* 当前长度 */
 27     int listsize;          /* 当前分配的存储容量(以sizeof(ElemType)为单位) */
 28 } SqList;
 29 
 30 
 31 
 32 //构造一个空的线性表
 33 Status InitList_Sq(SqList &L) {
 34     L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
 35     if (!L.elem) exit(OVERFLOW);
 36     L.length = 0;                //空表长度为0
 37     L.listsize = LIST_INIT_SIZE; //初始存储容量
 38     return OK;
 39 }
 40 
 41 
 42 //在线性表中插入元素
 43 //在顺序线性表L中第i个位置之前插入新的元素e, i的合法值为 1<= i <= ListLength_Sq(L) + 1
 44 Status ListInsert_Sq(SqList &L, int i, ElemType e) {
 45     ElemType *newbase = NULL;
 46     ElemType *p = NULL;
 47     ElemType *q = NULL;
 48     if (i <1 || i >L.length + 1) return ERROR;
 49     if (L.length >= L.listsize) {
 50         newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
 51         if (!newbase) exit(OVERFLOW);
 52         L.elem = newbase;
 53         L.listsize += LISTINCREMENT;
 54     }
 55     q = &(L.elem[i - 1]);
 56     for (p = &(L.elem[L.length - 1]); p >= q; --p) *(p + 1) = *p;
 57     
 58     *q = e;
 59     ++L.length;
 60     return OK;
 61 }
 62 
 63 //删除线性表中的元素
 64 //在顺序线性表L中删除第i个元素, 并用e返回其值, i的合法值为 1<= i <= ListLength_Sq(L)
 65 Status ListDelete_Sq(SqList &L, int i, ElemType &e) {
 66     ElemType *p = NULL;
 67     ElemType *q = NULL;
 68     if ((i < 1) || (i > L.length)) return ERROR;
 69     p = &(L.elem[i - 1]);
 70     e = *p;
 71     q = L.elem + L.length - 1;    //表尾元素位置
 72     for (++p; p <= q; ++p) *(p - 1) = *p; //被删除元素之后的元素左移
 73     --L.length;
 74     return OK;
 75 }
 76 
 77 
 78 //遍历线性表
 79 Status ListTraverse_Sq(SqList &L, Status (*Visit)(ElemType)) {
 80     ElemType *p = NULL;
 81     ElemType *q = NULL;
 82     if (L.length == 0) return ERROR;
 83     p = &(L.elem[0]);
 84     q = L.elem + L.length - 1;    //表尾元素位置
 85     for (; p <= q; ++p) Visit(*p);
 86     return OK;
 87 }
 88 
 89 
 90 //访问线性表中的元素
 91 Status Visit(ElemType e)
 92 {
 93     printf("%d ", e);
 94     return OK;
 95 }
 96 
 97 
 98 // 测试函数
 99 void main()
100 {
101     SqList L;  InitList_Sq(L); ElemType e;
102 
103     //遍历空表
104     if (OK == ListTraverse_Sq(L, Visit)) printf("visit succeed!\n");
105 
106     //插入元素
107     if (OK == ListInsert_Sq(L, 1, 10)) printf("insert succeed!\n");
108     if (OK == ListInsert_Sq(L, 2, 20)) printf("insert succeed!\n");
109     if (OK == ListInsert_Sq(L, 1, 30)) printf("insert succeed!\n");
110     if (OK == ListInsert_Sq(L, 2, 40)) printf("insert succeed!\n");
111     if (OK == ListInsert_Sq(L, 1, 50)) printf("insert succeed!\n");
112     
113     //遍历非空表
114     if (OK == ListTraverse_Sq(L, Visit)) printf("visit succeed!\n");
115 
116     //删除元素
117     if (OK == ListDelete_Sq(L, 1, e)) printf("delete %d succeed!\n", e);
118     if (OK == ListDelete_Sq(L, 3, e)) printf("delete %d succeed!\n", e);
119     if (OK == ListDelete_Sq(L, 2, e)) printf("delete %d succeed!\n", e);
120 
121     //遍历非空表
122     if (OK == ListTraverse_Sq(L, Visit)) printf("visit succeed!\n");
123 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

Leetcode 34 Search for a Range

Given a sorted array of integers, find the starting and ending position of a gi...

22290
来自专栏老马说编程

(32) 剖析日期和时间 / 计算机程序的思维逻辑

本节和下节,我们讨论在Java中如何进行日期和时间相关的操作。 日期和时间是一个比较复杂的概念,Java API中对它的支持不是特别好,有一个第三方的类库反而特...

219100
来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(四)No.52

这是本坑的第四篇,之前已经说了关于 HashSet 、BitMap 、Bloom Filter 布隆过滤器了,本篇主要讲B-树。要是还不知道前面讲了啥的,可以点...

21770
来自专栏Android知识点总结

看得见的数据结构Android版之二分搜索树篇

10440
来自专栏WD学习记录

牛客网 二叉树中和为某一值的路径

输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在...

10330
来自专栏猿人谷

双向链表

双向链表       在线性链式存储结构的结点中只有一个指示直接后继的指针域,由此,从某个结点出发只能顺指针往后寻查其他结点。若要寻查结点的直接前趋,则需从表...

28250
来自专栏xingoo, 一个梦想做发明家的程序员

程序猿的日常——Java中的集合列表

列表对于日常开发来说实在是太常见了,以至于很多开发者习惯性的用到数组,就来一个ArrayList,根本不做过多的思考。其实列表里面还是有很多玩法的,有时候玩不...

21660
来自专栏尾尾部落

[剑指offer] 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

16410
来自专栏架构之路

离线Tarjan算法-最近公共祖先问题

转载自Tarjan算法 LCA问题(Least Common Ancestors,最近公共祖先问题),是指给定一棵有根树T,给出若干个查询LCA(u, v)(通...

43250
来自专栏猿人谷

单链表反转的分析及实现

我先画一个单链表,这个单链表有4个元素。我的思路就是,每次把第二个元素提到最前面来。比如下面是第一次交换,我们先让头结点的next域指向结点a2,再让结点a1...

1.6K100

扫码关注云+社区

领取腾讯云代金券