- 1. 基本介绍
- 2. 基本用法
- 3. 线性表L的基本运算
-
包含若干数据元素的一个线性序列，记 L = ( a 0 , ⋯ , a i , ⋯ , a n − 1 ) L=(a_0, cdots, a_i, cdots, a_{n-1}) L=(a0,⋯,ai,⋯,an−1)
L是表名，n是表长，若n=0则为空表 -
线性表L可用二元组形式描述，用数据元素集合D和关系集合R来表示
L = ( D , R ) D = { a i ∣ a i ∈ d a t a t y p e , i = 0 , 1 , 2 , ⋯ , n − 1 } R = { < a i , a i + 1 > ∣ a i , a a + 1 ∈ D , 0 ≤ i ≤ n − 2 } L=(D, R) \ D={a_i|a_iin datatype, i=0, 1, 2, cdots, n-1} \ R={|a_i, a_{a+1}in D, 0le ile n-2} L=(D,R)D={ai∣ai∈datatype,i=0,1,2,⋯,n−1}R={
关系符 < a i , a i + 1 >
表示任意相邻的两个元素之间的一种先后顺序
a i a_i ai是 a a + 1 a_{a+1} aa+1的前驱， a i + 1 a_{i+1} ai+1是 a i a_i ai的后继 -
假设一个顺序表 L = { 1 , 2 , 3 , 4 , 5 , 6 } L={1, 2, 3, 4, 5, 6} L={1,2,3,4,5,6}，使用二元组描述 L = ( D , R ) L=(D, R) L=(D,R)，则
D = { 1 , 2 , 3 , 4 , 5 , 6 } ( n = 6 ) R = { < 1 , 2 > , < 2 , 3 > , < 3 , 4 > , < 4 , 5 > , < 5 , 6 > } D={1, 2, 3, 4, 5, 6}(n=6) \ R={<1, 2>, <2, 3>, <3, 4>, <4, 5>, <5, 6>} D={1,2,3,4,5,6}(n=6)R={<1,2>,<2,3>,<3,4>,<4,5>,<5,6>}我们可以看到表头1无前驱，表尾6无后继， a i a_i ai只有一个直接前驱 a i − 1 a_{i-1} ai−1和一个直接后继 a i + 1 a_{i+1} ai+1
-
若将线性表KaTeX parse error: Can't use function ')' in math mode at position 29: …cdots, a_{n-1}̲)̲中的各元素依次存储于计算机一片连续的空间中
设 L o c ( a i ) Loc(a_i) Loc(ai)为 a i a_i ai的地址， L o c ( a o ) = b Loc(a_o)=b Loc(ao)=b，每个元素占d个单元，则 L o c ( a i ) = b + i ∗ d Loc(a_i)=b+i*d Loc(ai)=b+i∗d -
顺序存储结构的特点
- 优点
- 逻辑上相邻的元素 a i , a i + 1 a_i, a_{i+1} ai,ai+1，其存储位置也是相邻的
- 对数据元素 a i a_i ai的存取为随机存取或按地址存取
- 存储密度高：存储密度D=(元素所占存储空间)/数据占用空间)
- 缺点
- 对表的插入和删除等运算的时间复杂度较高
- 优点
- 线性表在C中的表示
#define N 100 //100代表线性表的长度
typedef anyType data_t; //anyType可以是任意的数据类型
typedef struct{
data_t data[N];
int lastIdx; //顺序表并不是全部都被赋值了，lastIdx代表被赋值的最后一个元素的index
} sqlist, *sqlink;
3. 线性表L的基本运算
- 建立一个空表：create(l)，这个空表需要做三件事
- 申请内存，假设我们的data_t是int，顺序表长度为N，那么我们需要申请N+1个int那么大
- 初始化
- 返回线性表地址
//需要申请内存，初始化，返回线性表的地址
sqlink create(){
sqlink l;
//malloc
l = (sqlink)malloc(sizeof(sqlist));
if (l==NULL){
printf("Malloc failedn");
return l;
}
//init
memset(l, 0, sizeof(sqlist));
l->lastIdx = -1; //结构体指针访问成员
//return
return l;
}
- 置空表：clear(l)
int clear(sqlink l){
if (l == NULL)
return -1;
memset(l, 0, sizeof(sqlist));
l->lastIdx = -1;
return 0;
}
- 判断表是否为空：empty(l)，若为空返回1，否则返回0
int empty(sqlink l){
if (l->lastIdx == -1)
return 1;
else
return 0;
}
- 求表长：len(l)，若表为空，返回-1，若表不为空，返回表长
int len(sqlink l){
if (l == NULL)
return -1;
return l->lastIdx+1;
}
- 定位元素：loc(l, x)。确定元素x在表L中的位置，在返回位置，不在返回位置
int loc(sqlink l, data_t value){
for (int i = 0; i <= l->lastIdx; i++) {
if (l->data[i] == value)
return i;
}
return -1;
}
- 插入：insert(l, x, i)，将元素x插入到表L中第i个元素
a
i
a_i
ai之前，且表长+1。
- 首先先判断表是否满了，若满返回-1
- 若未满判断需要插入的位置是不是在 [ 0 , l a s t I d x + 1 ] [0, lastIdx+1] [0,lastIdx+1]之间，若不是返回-1
- 将需要插入的元素位置空出来，也就是说需要把部分元素后移
- 最后插入元素， l a s t I d x + 1 lastIdx+1 lastIdx+1.
int insert(sqlink l, data_t value, int pos){
// if this is a full list
if (l->lastIdx == N-1){
printf("Not enough space for this entryn");
return -1;
}
// check if this is a valid position
if (pos < 0||pos > l->lastIdx+1){
printf("Invalid positionn");
return -1;
}
//move
for (int i = l->lastIdx; i >= pos; i--){
l->data[i+1] = l->data[i];
}
//insert entry and lastIdx ++
l->data[pos] = value;
l->lastIdx++;
return 0;
}
- 打印顺序表：show(l)
int show(sqlink l){
if (l == NULL)
return -1;
for (int i = 0; i<= l->lastIdx; i++){
printf("%d ", l->data[i]);
}
puts("");
return 0;
}
- 删除表，释放空间：lFree(l)
- 把l所指向的堆空间free掉
- l指向空
int lFree(sqlink l){
if (l == NULL)
return -1;
free(l);
l = NULL;
return 0;
}
- 删除元素：del(l, i)，删除第i个元素，然后表长-1
int del(sqlink l, int pos){
if (l->lastIdx == -1){
printf("This is an empty listn");
return -1;
}
if (pos < 0 || pos > l->lastIdx){
printf("Invalid positionn");
return -1;
}
for (int i=pos; i<=l->lastIdx-1; i++){
l->data[i] = l->data[i+1];
}
l->data[l->lastIdx] = 0;
l->lastIdx--;
return 0;
}
- 求两个顺序表的并集：merge(l1, l2)，l1会被改变，l2不会被改变
- l 1 = l 1 ∪ l 2 l1=l1 cup l2 l1=l1∪l2.
- l 2 i l2_i l2i是否在 l 1 l1 l1中
- 若不在插入
- 循环2-3
int merge(sqlink l1, sqlink l2){
int i = 0, idx;
while(i <= l2->lastIdx){
idx = loc(l1, l2->data[i]);
if (idx == -1){
if (insert(l1, l2->data[i], l1->lastIdx+1) == -1)
return -1;
}
i++;
}
return 0;
}
- 删除重复元素：purge(l)
int purge(sqlink l){
int i = 1, j;
if (l->lastIdx == 0)
return 0;
while (i <= l->lastIdx){
j = i-1;
while (j >= 0) {
if (l->data[i] == l->data[j]){
del(l, i);
break;
}
else
j--;
}
if (j < 0){
i++;
}
}
return 0;
}
- 常见的数据结构往往由两个文件构成，对顺序表来说sqlist.h和sqlist.c，最后用个test.c来测试下。在sqlist.c上通常写定义与运算api，sqlist.c上写具体实现。这样写结构清晰，复用更方便
- sqlist.h
typedef int data_t; // int could be any type
#define N 128 // N is the total length of the sqlist
typedef struct Sqlist_t{
data_t data[N];
int lastIdx;
}sqlist, *sqlink;
sqlink create();
int clear(sqlink l);
int empty(sqlink l);
int len(sqlink l);
int loc(sqlink l, data_t value);
int insert(sqlink l, data_t value, int pos);
int show(sqlink l);
int lFree(sqlink l);
int del(sqlink l, int pos);
int merge(sqlink l1, sqlink l2);
int purge(sqlink l);
- 测试我们写的正确性
#include#include "sqlist.h" int main(int argc, char *argv[]){ sqlink l, l1; l = create(); if (l == NULL) return -1; insert(l, 10, 0); insert(l, 20, 0); insert(l, 20, 0); insert(l, 20, 0); insert(l, 20, 0); insert(l, 30, 0); insert(l, 40, 0); insert(l, 50, 0); insert(l, 60, 0); printf("l: n"); show(l); del(l, 0); printf("ndel(l, 0): n"); show(l); l1 = create(); if (l1 == NULL) return -1; insert(l1, 20, 0); insert(l1, 70, 0); insert(l1, 80, 0); printf("nl1: n"); show(l1); merge(l, l1); printf("nmerge(l, l1): n"); show(l); purge(l); printf("npurge(l): n"); show(l); lFree(l); lFree(l1); }
- 返回
l: 60 50 40 30 20 20 20 20 10 del(l, 0): 50 40 30 20 20 20 20 10 l1: 80 70 20 merge(l, l1): 50 40 30 20 20 20 20 10 80 70 purge(l): 50 40 30 20 10 80 70
- 最后附上完整的sqlist.c
#include#include #include #include "sqlist.h" //需要申请内存，初始化，返回线性表的地址 sqlink create(){ sqlink l; //malloc l = (sqlink)malloc(sizeof(sqlist)); if (l==NULL){ printf("Malloc failedn"); return l; } //init memset(l, 0, sizeof(sqlist)); l->lastIdx = -1; //结构体指针访问成员 //return return l; } int clear(sqlink l){ if (l == NULL) return -1; memset(l, 0, sizeof(sqlist)); l->lastIdx = -1; return 0; } int empty(sqlink l){ if (l->lastIdx == -1) return 1; else return 0; } int len(sqlink l){ if (l == NULL) return -1; return l->lastIdx+1; } int loc(sqlink l, data_t value){ for (int i = 0; i <= l->lastIdx; i++) { if (l->data[i] == value) return i; } return -1; } int insert(sqlink l, data_t value, int pos){ // if this is a full list if (l->lastIdx == N-1){ printf("Not enough space for this entryn"); return -1; } // check if this is a valid position if (pos < 0||pos > l->lastIdx+1){ printf("Invalid positionn"); return -1; } //move for (int i = l->lastIdx; i >= pos; i--){ l->data[i+1] = l->data[i]; } //insert entry and lastIdx ++ l->data[pos] = value; l->lastIdx++; return 0; } int show(sqlink l){ if (l == NULL) return -1; for (int i = 0; i<= l->lastIdx; i++){ printf("%d ", l->data[i]); } puts(""); return 0; } int lFree(sqlink l){ if (l == NULL) return -1; free(l); l = NULL; return 0; } int del(sqlink l, int pos){ if (l->lastIdx == -1){ printf("This is an empty listn"); return -1; } if (pos < 0 || pos > l->lastIdx){ printf("Invalid positionn"); return -1; } for (int i=pos; i<=l->lastIdx-1; i++){ l->data[i] = l->data[i+1]; } l->data[l->lastIdx] = 0; l->lastIdx--; return 0; } int merge(sqlink l1, sqlink l2){ int i = 0, idx; while(i <= l2->lastIdx){ idx = loc(l1, l2->data[i]); if (idx == -1){ if (insert(l1, l2->data[i], l1->lastIdx+1) == -1) return -1; } i++; } return 0; } int purge(sqlink l){ int i = 1, j; if (l->lastIdx == 0) return 0; while (i <= l->lastIdx){ j = i-1; while (j >= 0) { if (l->data[i] == l->data[j]){ del(l, i); break; } else j--; } if (j < 0){ i++; } } return 0; }
