数据结构（二）线性表

线性表

1. 什么是线性表

“线性表”：由同类型数据元素构成有序序列的线性结构

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

2. 线性表的抽象数据类型描述

类型名称：线性表（List）
数据对象集：线性表是 n (≥0) 个元素构成的有序序列（a $_1 </annotation> </semantics> </math>$
操作集：线性表 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

数据结构（二） 线性表

线性表

1. 什么是线性表

2. 线性表的抽象数据类型描述

1. 线性表的顺序存储实现

2. 线性表的链表存储实现

课后编程题题解

数据结构（二）线性表