【408篇】C语言笔记-第十章（线性表）

#define MaxSize 50  // 定义线性表的长度
typedef struct{
    ElemType data[MaxSize]; // 顺序表的元素
    int len;   // 顺序表的当前长度
}SqList;  // 顺序表的类型定义
1
2
3
4
5

// 判断插入位置i是否合法（满足1<=i<=len+1）
// 判断存储空间是否已满（即插入X后是否会超出数组长度）
for(int j=L.len;j>=i;j--){
    L.data[j]=L.data[j-1]; // 将最后一个元素到第i个元素依次后移一位
}
L.data[i-1]=x;  // 空出的位置i除放入x
L.len++;  // 线性表长度加1
1
2
3
4
5
6
7

// 判断删除位置i是否合法（满足1<=i<=len）
e=L.data[i-1];  // 将被删除的元素赋值给e
for(int j=i;j

#define InitSize 100  // 表长度的初始定义
typedef struct{
    ElemType *data;  // 指示动态分配数组的指针
    int MaxSize,length;  // 数组的最大容量和当前个数
}SeqList;  // 动态分配数组顺序表的类型定义
1
2
3
4
5

L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
1

L.data=new ElemType[InitSize];
1

#include 

#define MaxSize 50
typedef int ElemType;
// 静态分配
typedef struct {
    ElemType data[MaxSize];
    int len;  // 当前顺序表中元素个数
}SqList;

// 插入
// i表示插入的位置，从1开始，e要插入的元素
bool ListInsert(SqList &L,int i,ElemType e){
    if(i<1 || i>L.len+1){  // 判断插入位置是否合法
        return false;
    }
    if(L.len>=MaxSize){  // 判断存储空间是否已满
        return false;
    }
    for(int j=L.len;j>=i;j--){ // 移动顺序表中的元素
        L.data[j]=L.data[j-1];
    }
    L.data[i-1]=e;
    L.len+=1; // 添加一个元素，顺序表元素加1
    return true;
}

// 删除
// i表示删除的位置，从1开始。使用元素e的引用的目的是拿出对应的值
bool ListDel(SqList &L,int i,ElemType &e){
    if(i<1 || i>L.len){ // 判断删除的位置是否合法
        return false;
    }
    e=L.data[i-1]; // 获取顺序表中对应的元素，赋值给e
    for (int j=i;jL.len){ // 判断修改的位置是否合法
        return false;
    }
    L.data[i-1]=e;
    return true;
}

// 打印线性表
void PrintList(SqList L){
    for(int i=0;i

• 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
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83
• 84
• 85
• 86
• 87
• 88
• 89
• 90
• 91
• 92
• 93
• 94
• 95
• 96
• 97
• 98
• 99
• 100
• 101
• 102
• 103
• 104
• 105
• 106
• 107
• 108
• 109
• 110
• 111
• 112
• 113

F:\Computer\Project\practice\10\10.1-linear_table\cmake-build-debug\10_1_linear_table.exe
init Linear table
insert Linear table element
success
  1 50  2  3
delete Linear table element
success
 50  2  3
find Linear table element
success
position is 2
update Linear table element
success
 50 18  3

进程已结束，退出代码为 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

第二节：线性表的链式表示

单链表

逻辑上相邻的两个元素在物理位置上不相邻。

单链表结点的定义：

typedef struct LNode{ // 单链表结点类型
    ElemType data;  // 数据域
    struct LNode *next;  // 指针域
}LNode,*LinkList;
1
2
3
4

头指针：链表中第一个节点的存储位置，用来标识单链表。

头结点：在单链表第一个节点之前附加的一个结点，为了操作上的方便。

若链表有头结点，则头指针永远指向头结点，不论链表是否为空，头指针均不为空，头指针是链表的必须元素，它标识一个链表。

头结点是为了操作的方便而设立的，其数据域一般为空，或者存放链表的长度。有头结点后，对在第一结点前插入和删除第一结点的操作就统一了，不需要频繁重置头指针。但头结点不是必须的。

优缺点对比

插入操作

创建新结点

q=(LNode*)malloc(sizeof(LNode))
q->data=x;
1
2

头插入和中间插入

q->next=p->next;
p->next=q;
1
2

尾插入

p->next=q;
q->next=NULL;
1
2

说明：q是新插入的元素。p是指针指向的元素。

删除操作

p=GetElem(L,i-1); // 查找删除位置的前驱结点
p->next=q->next;
free(q);
1
2
3

说明：q是要删除的元素，p是指针指向的元素。删除完后要释放空间。

代码示例

按序号查找结点值的算法如下：

LNode *p=L->next;
int j=1;
while(p && jnext;
    j++;
}
return p;
1
2
3
4
5
6
7

按值查找结点的算法如下：

LNode *p=L->next;
while(p!=NULL && p->data!=e){
    p=p->next;
}
return p;
1
2
3
4
5

说明：L是头指针，用来指向头结点。