线性表
1. 什么是线性表
“线性表”：由同类型数据元素构成有序序列的线性结构
-
表中元素个数称为线性表的
长度
-
线性表没有元素时，称为
空表
-
表起始位置称为
表头
，表结束位置称
表尾
2. 线性表的抽象数据类型描述
-
类型名称：线性表（List）
-
数据对象集：线性表是 n (≥0) 个元素构成的有序序列（a
1_1
1
,a
2_2
2
,…,a
n_n
n
) -
操作集：线性表 L ∈ List，整数 i 表示位置，元素 X ∈ ElementType
线性表基本操作主要有：
-
List MakeEmpty()
： 初始化一个空线性表 L -
ElementType FindKth(int K,List L)
：根据位序 K，返回相应元素 -
int Find(ElementType X,List L)
：在线性表 L 中查找 X 的第一次出现位置 -
void Insert(ElementType X,int i,List L)
：在位序 i 前插入一个新元素 X -
void Delete(int i,List L)
：删除指定位序 i 的元素 -
int Length(List L)
：返回线性表 L 的长度 n
-
1. 线性表的顺序存储实现
利用数组的连续存储空间顺序存放线性表的各元素
注：顺序存储中是序号是下标，从 0 开始
#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 100 // MAXSIZE 定义为 Data 数组的大小
typedef int ElementType; // ElementType 可定义为任意类型
typedef struct LNode *List;
struct LNode{
ElementType Data[MAXSIZE];
int Last; // Last 定义线性表的最后一个元素
};
List L;
//访问下标为 i 的元素：L->Data[i]
//线性表的长度：L->Last+1
List MakeEmpty(); //初始化顺序表
int Find(ElementType X,List L); //查找 X 第一次出现的下标
void Insert(ElementType X,int i,List L); //在下标为 i 的地方插入 X
void Delete(int i,List L); //删除下标为 i 的当前值
ElementType FindKth(int K,List L); //返回下标为 K 的当前值
int Length(List L); //返回顺序表的长度
//初始化
List MakeEmpty(){
List L;
L = (List)malloc(sizeof(struct LNode));
L->Last = -1;
return L;
}
// 按值查找
int Find(ElementType X,List L){
int i=0;
while(i <= L->Last && L->Data[i] != X)
i++;
if(L->Last < i) //如果没找到，返回 -1
return -1;
else // 找到后返回下标
return i;
}
// 插入
void Insert(ElementType X,int i,List L){
int j;
if(L->Last == MAXSIZE-1){ //位置已满
printf("表满");
return;
}
if(i < 0 || L->Last+1 < i){ //位置越界，如果将数插入 L->Data[L->Last+1]，下面都不用腾位置了
printf("位置不合法");
return;
}
for(j=L->Last;j>=i;j--) // 从后往前依次向后挪一个，给 a[i]腾出位置
L->Data[j+1] = L->Data[j];
L->Data[i] = X; //新元素插入
L->Last++; // Last仍然指向最后元素
return;
}
//删除
void Delete(int i,List L){
int j;
if(i < 0 || L->Last <i){ //位置越界，而删除最多到 L->Data[L->Last]
printf("L->Data[%d]不存在元素",i);
return;
}
for(j=i;j<=L->Last;j++) // 从前往后依次向前挪一个，将 a[i] 覆盖了
L->Data[j-1] = L->Data[j];
L->Last--; // Last仍然指向最后元素
return;
}
// 按序查找
ElementType FindKth(int K,List L){
if(K < 0 || L->Last < K){ //位置越界
printf("L->Data[%d]不存在元素",K);
return;
}
return L->Data[K];
}
//表长
int Length(List L){
return L->Last+1;
}
int main(){
int i=0;
L = MakeEmpty();
Insert(11,0,L);
printf("在线性表L-Data[0]插入11\n");
Insert(25,0,L);
printf("在线性表L-Data[0]插入25\n");
Insert(33,0,L);
printf("在线性表L-Data[0]插入33\n");
Insert(77,0,L);
printf("在线性表L-Data[0]插入77\n");
printf("此时的线性表为：");
for(i=0;i<Length(L);i++)
printf("%d ",L->Data[i]);
printf("\n");
printf("查找值为12的下标是：%d\n",Find(12,L));
printf("下标为3的线性表的值是：%d\n",FindKth(3,L));
Delete(2,L);
printf("删除线性表中下标为2的元素\n");
Delete(2,L);
printf("删除线性表中下标为2的元素\n");
printf("此时的线性表为：");
for(i=0;i<Length(L);i++)
printf("%d ",L->Data[i]);
printf("\n");
return 0;
}
2. 线性表的链表存储实现
不要求逻辑上相邻的两个元素物理上也相邻，通过”链”建立起数据之间的逻辑关系
- 插入、删除不需要移动数据元素，只需要修改”链”
注：链表存储中序号从 1 开始
#include<stdio.h>
#include<malloc.h>
typedef int ElementType; // ElementType 可定义为任意类型
typedef struct LNode *List;
struct LNode{
ElementType Data; //数据域
List Next; // 下一个链表的地址
};
List L;
List MakeEmpty(); //初始化链表
int Length(List L); // 以遍历链表的方法求链表长度
List FindKth(int K,List L); // 按序号查找
List Find(ElementType X,List L); // 按值查找
List Insert(ElementType X,int i,List L); //将 X 插入到第 i-1(i>0) 个结点之后
List Delete(int i,List L); // 删除第 i(i>0) 个结点
void Print(List L); // 输出链表元素
// 初始化链表
List MakeEmpty(){
List L = (List)malloc(sizeof(struct LNode));
L = NULL;
return L;
}
//求表长
int Length(List L){
List p = L;
int len=0;
while(p){ // 当 p 不为空
p = p->Next;
len++;
}
return len;
}
// 按序查找
List FindKth(int K,List L){
List p = L;
int i = 1; //从 1 开始
while(p && i<K){
p = p->Next;
i++;
}
if(i == K) // 找到了
return p;
else // 未找到
return NULL;
}
// 按值查找
List Find(ElementType X,List L){
List p = L;
while(p && p->Data!=X)
p = p->Next;
// 找到了，返回 p
// 未找到，返回 NULL，此时 p 等于 NULL
return p;
}
/* 插入
1. 用 s 指向一个新的结点
2. 用 p 指向链表的第 i-1 个结点
3. s->Next = p->Next，将 s 的下一个结点指向 p 的下一个结点
4. p->Next = s，将 p 的下一结点改为 s */
List Insert(ElementType X,int i,List L){
List p,s;
if(i == 1){ // 新结点插入在表头
s = (List)malloc(sizeof(struct LNode));
s->Data = X;
s->Next = L;
return s; //插入的结点为头结点
}
p = FindKth(i-1,L); // 找到第 i-1 个结点
if(!p){ // 第 i-1 个结点不存在
printf("结点错误");
return NULL;
}else{
s = (List)malloc(sizeof(struct LNode));
s->Data = X;
s->Next = p->Next; //将 s 的下一个结点指向 p 的下一个结点
p->Next = s; // 将 p 的下一结点改为 s
return L;
}
}
/* 删除
1. 用 p 指向链表的第 i-1 个结点
2. 用 s 指向要被删除的的第 i 个结点
3. p->Next = s->Next，p 指针指向 s 后面
4. free(s)，释放空间
*/
List Delete(int i,List L){
List p,s;
if(i==1){ //如果要删除头结点
s = L;
if(L) // 如果不为空
L = L->Next;
else
return NULL;
free(s); // 释放被删除结点
return L;
}
p = FindKth(i-1,L); // 查找第 i-1 个结点
if(!p || !(p->Next)){ // 第 i-1 个或第 i 个结点不存在
printf("结点错误");
return NULL;
}else{
s = p->Next; // s 指向第 i 个结点
p->Next = s->Next; //从链表删除
free(s); // 释放被删除结点
return L;
}
}
// 输出链表元素
void Print(List L){
List t;
int flag = 1;
printf("当前链表为：");
for(t = L;t;t =t->Next){
printf("%d ",t->Data);
flag = 0;
}
if(flag)
printf("NULL");
printf("\n");
}
int main(){
L = MakeEmpty();
Print(L);
L = Insert(11,1,L);
L = Insert(25,1,L);
L = Insert(33,2,L);
L = Insert(77,3,L);
Print(L);
printf("当前链表长度为：%d\n",Length(L));
printf("此时链表中第二个结点的值是：%d\n",FindKth(2,L)->Data);
printf("查找22是否在该链表中：");
if(Find(22,L))
printf("是！\n");
else
printf("否！\n");
printf("查找33是否在该链表中：");
if(Find(33,L))
printf("是！\n");
else
printf("否！\n");
L = Delete(1,L);
L = Delete(3,L);
printf("----------删除后-----\n");
Print(L);
return 0;
}
课后编程题题解
两个有序链表序列的合并
一元多项式的乘法与加法运算
Reversing Linked List
Pop Sequence