Ch2 线性表（p12）
# 2.2 顺序表——线性表的顺序存储（p14）
静态分配
#define MaxSize 50 //定义线性表的最大长度
typedef struct { //顺序表定义
ElemType data[MaxSize]; //线性表的元素
int length; //线性表当前长度
} SqList; //顺序表的类型定义
1
2
3
4
5
2
3
4
5
动态分配
#define InitSize 100 //表长度的初始化定义
typedef struct { //动态分配数组顺序表的定义
ElemType *data; //指示动态分配数组的指针
int MaxSize, length; //数组的最大容量和当前个数
} SeqList; //动态分配数组顺序表的类型定义
1
2
3
4
5
2
3
4
5
# 2.2.2 顺序表上基本操作的实现（p15）
(1)插入操作
bool ListInsert(SqList &L,int i,ElemType e){
//本算法实现将元素e插入到顺序表L中第i个位置
if(i<1||i>L.length+1) //判断i的范围是否有效
return false;
if(L.length>=MaxSize) //当前存储空间已满，不能插入
return false;
for(int j=L.length;j>=i;j--)//将第i个元素及之后的元素后移
L.data[j]=L.data[j-1];
L.data[i-1]=e; //在位置i处放入e
L.length++; //线性表长度加1
return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
(2)删除操作
bool ListDelete(SqList &L,int i,ElemType &e){
//本算法实现删除顺序表L中第i个位置的元素
if(i<1||i>L.length) //判断i的范围是否有效
return false;
e=L.data[i-1]; //将被删除的元素赋值给e
for(int j=i;j < L.length;j++)//将第i个位置之后的元素前移
L.data[j-1]=L.data[j];
L.length--; //线性表长度减1
return true;
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
(3)按值查找（顺序查找）
int LocateElem(SqList L,ElemType e){
//本算法实现查找顺序表中值为e的元素，如果查找成功，返回元素位序，否则返回0
int i;
for(i=0;i < L.length;i++)
if(L.data[i]==e)
return i+1; //下标为i的元素值等于e，返回其位序i+1
return 0; //退出循环，说明查找失败
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 2.3 单链表——线性表的链式存储（p26）
单链表中结点类型的描述
typedef struct LNode{ //定义单链表结点类型
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList;
1
2
3
4
2
3
4
# 2.3.2 单链表上基本操作的实现（p27）
1.采用头插法建立单链表
LinkList CreateList1(LinkList &L){
//从表尾到表头逆向建立单链表L，每次均在头结点之后插入元素
LNode *s;int x;
L=(LinkList)malloc(sizeof(LNode)); //创建头结点
L->next=NULL; //初始化为空链表
scanf("%d",&x); //输入结点的值
while(x!=9999){ //输入9999表示结束
s=(LNode*)malloc(sizeof(LNode));//创建新结点
s->data=x;
s->next=L->next;
L->next=s; //将新结点插入表中，L为头指针
scanf("%d",&x);
}//while结束
return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2.采用尾插法建立单链表
LinkList CreatList2(LinkList &L) {
//从表头到表尾正向建立单链表L，每次均在表尾插入元素
int x; //设元素类型为整型
L = (LinkList)malloc(sizeof(LNode));
LNode *s, *r = L; //r为表尾指针
scanf("%d",&x); //输入结点的值
while (x != 9999) { //输入9999表示结束
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s; //r指向新的表尾结点
scanf("%d",&x);
}
r->next = NULL; //尾结点指针置空
return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
3.按序号查找结点值
LNode *GetElem(LinkList L,int i){
//本算法取出单链表L(带头结点)中第i个位置的结点指针
int j=1; //计数，初始化为1
LNode *p=L->next; //头结点指针赋给P
if(i==0)
return L; //若i等于0.则返回头结点
if(i<1)
return NULL; //若i无效，则返回NULL
while(p&&j<i){ //从第1个结点开始找，查找第i个结点
p=p->next;
j++;
}
return p; //返回第i个结点的指针，如果i大于表长，p=NULL,直接返回p即可
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
4.按值查找表结点
LNode *LocateElem(LinkList L,ElemType e){
//本算法查找单链表L(带头结点)中数据域值等于e的结点指针，否则返回NULL
LNode *p=L->next;
while(p!=NULL&&p->data!=e)//从第1个结点开始查找data域为e的结点
p=p->next;
return p; //找到后返回该结点指针，否则返回NULL
}
1
2
3
4
5
6
7
2
3
4
5
6
7
5.插入结点操作
前插
p=GetElem(L,i-1); //查找插入位置的前驱结点
s->next=p->next; //图2-7中操作步骤1
p->next=s; //图2-7中操作步骤2
后插
//将*s结点插入到*p之前的主要代码片段
s->next=p->next; //修改指针域，不能颠倒
p->next=s;
temp=p->data; //交换数据域部分
p->data=s->data;
s->data=temp;
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
6.删除表结点
方法一
p=GetElem(L,i-1); //查找删除位置的前驱结点
q=p->next; //令q指向被删除结点
p->next=q->next; //将*q结点从链中“断开”
free(q); //释放结点的存储空间
方法二
q=p->next; //令q指向*p的后继结点
p->data=p->next->data; //和后继结点交换数据域
p->next=q->next; //将*q结点从链中“断开”
free(q); //释放后继结点的存储空间
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
7.求表长操作
# 2.3.3 双链表（p30）
双链表中结点类型的描述
typedef struct DNode{ //定义双链表结点类型
ElemType data; //数据域
struct DNode *prior,*next; //前驱和后继指针
}DNode,*DLinkList;
1
2
3
4
2
3
4
1.双链表的插入操作
s->next=p->next; //将结点*s插入到结点*p之后
p->next->prior=s;
s->prior=p;
p->next=s;
1
2
3
4
2
3
4
2.双链表的删除操作
p->next=q->next; //图2-11中步骤1
q->next->prior=p; //图2-11中步骤2
free(q); //释放结点空间
1
2
3
2
3
# 2.3.5 静态链表（p32）
静态链表结构类型的描述
#define MaxSize 50 //静态链表的最大长度
typedef struct{ //静态链表结构类型的定义
ElemType data; //存储数据元素
int next; //下一个元素的数组下标
}SLinkList[MaxSize];
1
2
3
4
5
2
3
4
5
编辑 (opens new window)
上次更新: 2021/02/16, 02:45:37