线性表是最常用且最简单的一种数据结构 (这句话是抄书的). 因为我的第二专业才是计科, 在面对数据结构时也经历了地狱一般的理解阶段, 所以希望这篇文章可以足够简单地记下自己的所学, 也方便大家去理解.
顺序表, 书上的定义时指用一组连续的存储单元依次存储线性表的数据元素. 通俗理解也就是一张表格, 在里头放数据 (难道还需要其它解释吗?), 你可以想象表格的格子在计算机里面的位置都是连续的, 大家排排坐吃果果, 跟幼儿园的小朋友一样.
因为顺序表的特点, 学过数列的我们都知道, 第一个元素 a1 = a1, 第二个元素 a2 = a1 + d (d 是 a1 的长度, 这里的长度是指元素所占的 d 个存储单元), 由此我们得知 ai = a1 + (i-1) * d. 即第 i 个元素的存储位置.
好, 接下来上代码:
- typedef struct
- {
- int *elem; // 线性表元素
- int length; // 线性表现有长度
- int listsize; // 线性表最大容量
- }SqList;
这串代码构建了一个名为 SqList 的数据类型, 它的内部属性含有一个元素, 一个长度和一个容量.
C 语言可以通过 typedef struct 定义一个新的数据类型, 自我感觉这个东西有很多的可能性. 之前数据结构的课程上老师丝毫没有提及这个东西, 弄得我看着这串代码抓瞎.(估计是数据结构老师觉得 C 语言老师会讲, 而 C 语言老师觉得这个东西考试不考没必要讲......).
实现以下五个函数块:
- SqList InitList_Sq(SqList L) // 初始化顺序表
- SqList ListInsert(SqList L, int i, int e) // 插入元素
- SqList ListDelete(SqList L, int i) // 删除顺序表第 i 个元素
SqList unionAandB(SqList LA, SqList LB) // 将 A 表和 B 表拼一起
SqList ListShow(SqList L) // 打印顺序表
五个基本操作, 不骚, 陈独秀同志可以站起来看; 跟所有变量一样, 这个表在定义出来后需要经历初始化, 赋值, 运算和打印的过程, 这里就不多加赘述了, 以下是完整代码:
- #include <stdio.h>
- #include <malloc.h>
- #define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量
- #define LISTINCREMENT 10 // 线性表存储空间的分配增量 (这里可以不用那么死板)
- typedef struct
- {
- int *elem; // 线性表元素
- int length; // 线性表现有长度
- int listsize; // 线性表最大容量
- }SqList;
- SqList InitList_Sq(SqList L) // 初始化顺序表
- {
- // 构造一个空的线性表
- //SqList L;
- L.elem = (int*)malloc(LIST_INIT_SIZE*sizeof(int)); // 给 L 中元素分配足够的空间
- //if(! L.elem) exit(OVERFLOW);
- if(!L.elem) exit(0);
- L.length = 0;
- L.listsize = LIST_INIT_SIZE;
- return L;
- }
- SqList ListInsert(SqList L, int i, int e) // 插入元素
- {
- int j;
- if( L.length == L.listsize )
- {
- printf("表满 \ n");
- exit(0);
- }
- if( i<1 || i>L.listsize )
- {
- printf("插入位置错误 \ n");
- exit(0);
- }
- for(j=L.length-1; j>=i-1; j--)
- {
- L.elem[j+1] = L.elem[j];
- }
- L.elem[i-1] = e;
- L.length++;
- return L;
- }
- SqList ListDelete(SqList L, int i) // 删除顺序表第 i 个元素
- {
- int j;
- if( i<1 || i>L.length )
- {
- printf("求你找个好位置再来 \ n");
- exit(0);
- }
- for(j=i; j<=L.length-1; j++)
- {
- L.elem[j-1] = L.elem[j];
- }
- L.length--;
- return L;
- }
- SqList unionAandB(SqList LA, SqList LB) // 将 A 表和 B 表拼一起
- {
- SqList L;
- L.length = 0;
- int i=0, j=0, k=-1;
- while( i<LA.length && j<LB.length )
- {
- if(LA.elem[i]<=LB.elem[j])
- {
- L.elem[++k] = LA.elem[i++];
- }
- else
- {
- L.elem[++k] = LB.elem[j++];
- }
- }
- if(i<LA.length)
- {
- while(i<LA.length)
- {
- L.elem[++k] = LA.elem[i++];
- }
- }
- else
- {
- while(j<LB.length)
- {
- L.elem[++k] = LB.elem[j++];
- }
- }
- L.length = k+1;
- return L;
- }
- SqList ListShow(SqList L) // 打印顺序表
- {
- int i;
- if(!L.elem) exit(0);
- for(i=0; i<L.length; i++)
- {
- printf("%d\n", L.elem[i]);
- }
- }
- int main(int argc, char const *argv[]) // 测试
- {
- int i, j;
- SqList L;
- L = InitList_Sq(L);
- L = ListInsert(L,1,1);
- L = ListInsert(L,2,2);
- printf("the List is L:\n");
- ListShow(L);
- SqList L2;
- L2 = InitList_Sq(L2);
- L2 = ListInsert(L2,1,3);
- L2 = ListInsert(L2,2,4);
- L2 = ListInsert(L2,3,5);
- printf("the next List is L2:\n");
- ListShow(L2);
- SqList L3;
- L3 = InitList_Sq(L3);
- L3 = unionAandB(L,L2);
- printf("the last List is L3:\n");
- ListShow(L3);
- //printf("%d\n", L3.length);
- return 0;
- }
这个逻辑结构还是比较浅显易懂的, 大神那么多我就不必再献丑了, 如有意见建议, 欢迎指出~
来源: http://www.bubuko.com/infodetail-2608935.html