线性表

由同类数据元素构成有序序列的线性结构

  • 表中元素个数称之为线性表的长度
  • 线性表没有元素时称为空表
  • 表起始位置称表头 ，表结束位置称表尾

类型名称 ：线性表(List)

数据对象集 ：线性表是n(>=0)个元素构成的有序序列

操作集 ：

  1. List MakeEmpty() 初始化一个空表
  2. ElementType FindKth() 根据位序K，返回相应元素
  3. int Find(ElementType X, List Ptrl) 在线性表L中查找X的第一次出现位置
  4. void Insert(ElementType X,int i,List Ptrl) 在位序i前插入一个新元素
  5. void Delete(int i,List L) 删除指定位序i的元素
  6. int Length(List L) 返回线性表L的长度
  7. ......

线性表的顺序存储实现

用数组的连续储存空间顺序存放线性表的个元素

代码

1
2
3
4
5
6
7
typedef struct LNode *List;	//用*List指针代替LNode
struct LNode{	//定义LNode结构体
    ElementType Data[MAXSIZE];
    int Last;	//数组最后一个元素的位置
};
struct LNode L;	//声明L为LNode类型的结构体
List PtrL;	//ptrl为List型指针

访问下标为 i 的元素，L.Data[i] 或 PtrL->Data[i]

线性表的长度：L.Last + 1 或 PtrL->Last + 1

List MakeEmpty()

初始化一个空表

代码

1
2
3
4
5
6
List MakeEmpty(){   //初始化一个空表
    List Ptrl;
    Ptrl = (List) malloc (sizeof(struct LNode));    //申请出一个空表的空间
    Ptrl->Last = -1;    
    return Ptrl;
}

Last = -1: 因为表长为Last + 1，所以Last = -1 表示空表。

ElementType FindKth()

根据位序K，返回相应元素

代码

1
2
3
4
5
6
7
8
void ElementType_FindKth(int i){	//根据位序K，返回相应元素
    if (i < 0 || i > Ptrl->Last + 1){   //检查输入位置的合法性
        printf(" 位置不合法 ");
        return;
    }
    else
        return Ptrl->Data[i-1]; //位置合法，返回结果
}

int Find(ElementType X, List Ptrl)

在线性表L中查找X的第一次出现位置

代码

1
2
3
4
5
6
7
8
9
int Find(ElementType X, List Ptrl){ //在线性表L中查找X的第一次出现位置
    int i = 0;
    while (i <= Ptrl->Last && Ptrl->Data[i] != X)   //限定查找条件(不越界，没找到)
        i++;
    if (i > Ptrl->Last)
        return -1;  //没找到，返回-1
    else
        return i;   //找到，返回位置i
}

void Insert(ElementType X,int i,List Ptrl)

在位序i前插入一个新元素

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Insert(ElementType X,int i,List Ptrl){  //在位序i前插入一个新元素(先移动，再插入)
    int j;
    if (Ptrl->Last == MAXSIZE - 1){ //表空间已满，不能插入
        printf(" 表满 ");
        return;
    }
    if (i < 1 || i > Ptrl->Last+2){ //检查插入位置的合法性
        printf(" 位置不合法 ");
        return;
    }
    for (j = Ptrl->Last;j >= i - 1;j--)
        Ptrl->Data[j + 1] = Ptrl->Data[j];  //将a[i]~a[n]倒序向后移动
    Ptrl->Data[i - 1] = X;  //插入新元素
    Ptrl->Last++;   //Last仍指向最后元素
    return;
}

void Delete(int i,List L)

删除指定位序 i 的元素

代码

1
2
3
4
5
6
7
8
9
10
11
12
void Delete(int i,List L){  //删除指定位序i的元素
    int j;

    if (i > Ptrl->Last + 1 || i < 1){ //检查空表及删除位置的合法性
        printf(" 不存在第%d个元素 ",i);
        return;
    }
    for (j = i;j <= Ptrl->Last;j++)
        Ptrl->Data[j - 1] = Ptrl->Data[j];  //将a[i + 1]~a[n]倒序向前移动
    Ptrl->Last--;   //Last仍指向最后元素
    return;
}

int Length(List L)

返回线性表L的长度

代码

1
2
3
int Length(List L){ //返回线性表L的长度
    return L.Last + 1;
}

线性表的链式储存实现

代码

1
2
3
4
5
6
7
typedef struct LNode *List;
struct LNode{
    ElementType Data;   // 节点所储存的数据
    List Next;  // 下一个节点的位置 List 指针
};
struct LNode L;
List PtrL;

用链表实现：

Data 用来储存结点的数据

Next 用来放下一节点的指针

int Length(List PtrL)

求表长

代码

1
2
3
4
5
6
7
8
9
int Length(List PtrL){  // 求表长
    List p = PtrL;  // p 指向表的第一个结点
    int j = 0;
    while (p){  // 遍历链表 直到p指针为null
        p = p->Next;
        j++;    // 当前p指向第j个结点
    }
    return j;
}

List FindKth(int K, List PtrL)

按序号查找

代码

1
2
3
4
5
6
7
8
9
10
11
12
List FindKth(int K, List PtrL) {    //按序号查找
    List p = PtrL;
    int i = 1;
    while (p != NULL && i < K){ // 排除错误序号及遍历链表 直到第K个为止
        p = p->Next;
        i++;
    }
    if (i == K)
        return p;   //  找到第k个，返回指针
    else
        return NULL;    // 否则返回空
}

while循环条件：

指针不为空，且查找的序号小于要查找的序号

List Find(ElementType X,List PtrL)

按值查找

代码

1
2
3
4
5
6
List Find(ElementType X,List PtrL){ // 按值查找
    List p = PtrL;
    while (p != NULL && p->Data != X)   // 遍历链表
        p = p->Next;
    return p;
}

List Insert(ElementType X,int i,List PtrL)

插入结点

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
List Insert(ElementType X,int i,List PtrL){ // 插入结点
    List p,s;
    if (i == 1){    // 新结点插在表头
        s = (List)malloc(sizeof(struct LNode)); // 申请装填结点
        s->Data = X;
        s->Next = PtrL;
        return s;   // 返回表头指针
    }
    p = FindKth(i - 1,PtrL);    // 查找第i-1个结点
    if (p == NULL){ // i-1个结点不存在 不能输入
        printf(" 参数i错误 ");
        return NULL;
    }
    else{
        s = (List)malloc(sizeof(struct LNode));
        s->Data = X;
        s->Next = p->Next;  // 新结点指向下一个结点
        p->Next = s;    // n-1个结点指向新结点
        return PtrL;
    }
}

List Delete(int i,List PtrL)

删除结点

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
List Delete(int i,List PtrL){   // 删除结点
    List s,p;
    if (i == 1){    // 如果删除第一个结点
        s = PtrL;   // s指向第一个结点
        if (PtrL != NULL)   // 删除该节点
            PtrL = PtrL->Next;
        else
            return NULL;
        free(s);    // 释放被删除结点
        return PtrL;
    }
    p = FindKth(i-1, PtrL); // 查找第i-1个结点
    if (p == NULL){
        printf("第%d个结点不存在",i-1);
        return NULL;
    }
    else if (p->Next == NULL){
        printf("第%d个结点不存在",i);
        return NULL;
    }
    else{
        s = p->Next;    // s指向第i个结点
        p->Next = s->Next;  // 从链表中删除
        free(s);
        return PtrL;
    }
}
1
p->Next = s->Next

s->Next 为n+1结点的指针

p->Next 为n-1结点的指针

直接将n-1点的指针指向n+1点，也就是删除掉了n结点