线性表及其实现
什么是线性表？
谈到线性表，我们先来做个题目！
用结构体数组表示一元多项式，并且实现加法操作。
一元多项式
大家想好了吗？ 这个题目的代码在最后面，好了，可以开始线性表了。
同类型数据元素构成有序序列的线性结构
- 表中元素的个数称为
线性表的长度 - 线性表没有元素时，成为
空表 - 表起始位置成为
表头，表结束位置称为表尾 - 头指针：指向头结点的指针
- 头结点：头结点的数据域可以不存储任何信息，头结点的指针域存储指向开始结点的指针（即第一个元素结点的存储位置）
- 第一个节点：就是头结点之后的第一个结点，也就是线性表
有效结点
总结：头结点可以没有，但不能没有头指针，因为头指针是链表的一个起始地址。
头结点的作用：
- 防止单链表为空的而设的.当链表为空的时候,带头结点的头指针就指向头结点.如果当链表为空的时候,单链表没有带头结点,那么它的头指针就为NULL.
- 是为了方便单链表的特殊操作,插入在表头或者删除第一个结点.这样就保持了单链表操作的统一性!
- 单链表加上头结点之后，无论单链表是否为空，头指针始终指向头结点，因此空表和非空表的处理也统一了，方便了单链表的操作，也减少了程序的复杂性和出现bug的机会。
- 对单链表的多数操作应明确对哪个结点以及该结点的前驱。不带头结点的链表对首元结点、中间结点分别处理等；而带头结点的链表因为有头结点，首元结点、中间结点的操作相同 ,从而减少分支，使算法变得简单 ,流程清晰。对单链表进行插入、删除操作时，如果在首元结点之前插入或删除的是首元结点，不带头结点的单链表需改变头指针的值，在C 算法的函数形参表中头指针一般使用指针的指针(在C+ +中使用引用 &)；而带头结点的单链表不需改变头指针的值，函数参数表中头结点使用指针变量即可。
线性表的抽象数据类型描述
类型名称：线性表（List）
数据对象集：线性表是 n（>=0）个元素构成的有序序列（a1,a2,a3,....,an）
操作集：线性表L∈List , 整数 i 表示位置 ，元素X∈ElementType，线性表的操作有
-
List MakeEmpty();初始化一个空线性表 -
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
线性表的顺序存储实现
利用数组的 连续存储空间顺序存放 线性表的各元素
线性存储
不多说，上代码！
#include <stdio.h>
// 为了包含exit函数
#include <stdlib.h>
#include <malloc.h>
#define MAXSIZE 100
typedef struct LNode *List;
typedef int ElementType;
struct LNode
{
ElementType Data[MAXSIZE]; //顺序存储的数组空间
int Last; //有效数值的最大数组下标
};
//初始化一个顺序存储的线性表
List MakeEmpty()
{
//定义一个顺序表结构体指针
List Ptrl;
//动态开辟空间
Ptrl = (List)malloc(sizeof(struct LNode));
if(!Ptrl)
{
printf("分配内存失败！！\n");
exit(-1);
}
//初始化最大下标
Ptrl->Last = -1;
return Ptrl;
}
//在线性表中找出数据元素X的位置
int Find(ElementType X, List Ptrl)
{
int i=0;
//遍历查找，时间复杂度为O(n)
while(i < Ptrl->Last && Ptrl->Data[i]!=X)i++;
if(i>Ptrl->Last) return -1; //没找到返回-1
else return i; //找到了返回索引值
}
//在线性表中返回第K个元素的数值
ElementType FindKth(int K , List L)
{
if(K > L->Last+1 || K<1 )printf("查找位置不合法！\n");
else
return L->Data[K-1];
}
//在线性表中第i个位置之后插入一个同类型数据X
void Insert(ElementType X , int i , List L)
{
int last;
//判断表是否装满
if(L->Last == MAXSIZE-1)
{
printf("表满！\n");
return;
}
//判断插入位置是否合法
if(i > L->Last+1 || i<0 )printf("插入位置不合法！\n");
//插入算法
else
{
last = ++L->Last;
//插入之前，从最后一个元素往表尾挪动一个单位
while(last!=i){
L->Data[last] = L->Data[last-1];
last--;
}
//移动完成之后，赋值插入
L->Data[i] = X;
}
}
//删除线性表中位置为i的元素
void Delete(int i , List L)
{
if( i-1 > L->Last || i<1 )printf("删除失败，该位置不存在!\n");
else
{
while( i < L->Last+1)L->Data[i-1] = L->Data[i++];
L->Last--;
}
}
//求长度
int Length(List L)
{
return L->Last+1;
}
//输出线性表
void putList(List L)
{
int i;
if(L->Last==-1)
{
printf("空表，长度为0\n");
return ;
}
printf("该顺序表输出为:");
for(i=0;i<L->Last+1;i++)
{
printf("%d,",L->Data[i]);
}
printf("\n该顺序表的元素个数为%d\n",L->Last+1);
}
//函数入口
int main()
{
//定义数组，方便赋值
int a[12] = {1,2,3,85,41,23,69,54,265,232,36,32},i;
//创建新表
List p = MakeEmpty();
putList(p);
// 用数组a给线性表插值
for(i=0;i<12;i++)
{
Insert(a[i],p->Last+1,p);
putList(p);
}
for(i=0;i<12;i++)
{
printf("在第%d号位置插入%d",i,i*8);
Insert(i*8,i,p);
putList(p);
}
for(i=0;i<12;i++)
{
printf("%d在%d位置\n",a[i],Find(a[i],p));
}
for(i=0;i<12;i++)
{
printf("第%d个元素是什么？%d\n",i+1,FindKth(i+1,p));
}
for(i=0;i<36;i++)
{
printf("删除第%d个元素",i+1);
Delete(i+1,p);
putList(p);
}
}
线性表的链式存储实现
原理：不要求逻辑上相邻的两个元素物理上也相邻，通过 “链” 建立起数据元素之间的逻辑关系
- 插入、删除不需要移动数据元素，只需要修改 “链”。
链表图：
链表
结构体定义：
typedef struct LNode *List;
struct LNode
{
ElementType Data; // 链表的数据域
List Next; //链表的指针域
};
主要操作的实现：
求表长：
int Length( List P )
{
List p = P; // p指向标的第一个结点; 直接操作P也是可以的
int len = 0;
while(p) // 当p为NULL的时候，代表已经到达表尾，循坏也结束
{
p = p->Next; // p指向下一个结点
len++; //当前p指向的是第len个结点
}
return len;
}
查找
1.按序号查找
List FindKth(int K , List Ptrl)
{
List p = Ptrl;
int i = 1;
while(p!=NULL && i<K)
{
p=p->Next;
i++;
}
if(i == K)return p;
else return NULL
}
2.按值查找
List Find(ElementType X , List Ptrl)
{
List p = Ptrl;
while(p!=NULL && p->Data!=X)
p = p->Next;
return p;
}
插入
在第i-1（1 < i < n+1）个节点后插入一个值为X的新节点
- 先构造一个新节点，用s指向；
- 再找到链表的第i-1个节点，用p指向;
- 然后修改指针，插入节点（p之后插入新节点是s）
插入
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; //直接让新节点指向表头节点
}
p = FindKth(i-1,Ptrl); //查找第I-1个节点
if(P==NULL) //第i-1个不存在，不能插入
{
printf("参数错误！");
return NULL;
}
else
{
s = (List)malloc(sizeof(struct LNode)); /*申请、填装节点*/
s->Data = X;
s->Next = p->Next; //新节点插入在第i-1个节点的后面
p-Next = s;
return Ptrl;
}
}
删除
删除链表的第 i（1 < i < n）个位置上的节点
- 先找到链表的第 i-1个节点，用p指向；
- 再用指针s指向要被删除的节点（p的下一个节点）；
- 然后修改指针，删除s所指向的节点;
- 最后释放s所指向节点的空间
删除节点图
代码实现：
List Delete(int i, List Ptrl)
{
List p , s;
if(i==1) //若要删除表的第一个节点
{
s = Ptrl; //s指向第一个节点
if(Ptrl!=NULL) Ptrl = Ptrl->Next;
else return NULL;
free(s);
return Ptrl;
}
p = FindKth(i-1,Ptrl);
if(p == NULL)
{
printf("该节点不存在");
return NULL;
}
else if(p->Next = NULL)
{
printf("不存在");
return NULL
}
else
{
s = p->Next;
p->Next = s->Next;
free(s);
return Ptrl;
}
}
整体代码如下：
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
/* 查找 */
#define ERROR NULL
Position Find( List L, ElementType X )
{
Position p = L; /* p指向L的第1个结点 */
while ( p && p->Data!=X )
p = p->Next;
/* 下列语句可以用 return p; 替换 */
if ( p )
return p;
else
return ERROR;
}
/* 带头结点的插入 */
/*注意:在插入位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是链表结点指针，在P之前插入新结点 */
bool Insert( List L, ElementType X, Position P )
{ /* 这里默认L有头结点 */
Position tmp, pre;
/* 查找P的前一个结点 */
for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ;
if ( pre==NULL ) { /* P所指的结点不在L中 */
printf("插入位置参数错误\n");
return false;
}
else { /* 找到了P的前一个结点pre */
/* 在P前插入新结点 */
tmp = (Position)malloc(sizeof(struct LNode)); /* 申请、填装结点 */
tmp->Data = X;
tmp->Next = P;
pre->Next = tmp;
return true;
}
}
/* 带头结点的删除 */
/*注意:在删除位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是拟删除结点指针 */
bool Delete( List L, Position P )
{ /* 这里默认L有头结点 */
Position tmp, pre;
/* 查找P的前一个结点 */
for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ;
if ( pre==NULL || P==NULL) { /* P所指的结点不在L中 */
printf("删除位置参数错误\n");
return false;
}
else { /* 找到了P的前一个结点pre */
/* 将P位置的结点删除 */
pre->Next = P->Next;
free(P);
return true;
}
}
广义表
广义表由二元多项式引申而出，表示一个二元多项式
二元多项式
可以把上述二元多项式看成X的一元多项式
变化
链表结构如下：
结构
广义表的概念：
- 广义表是线性表的推广
- 对于线性表而言，n个元素都是基本的单元素
- 广义表中，这些元素不仅可以是一个单元素也可以是另一个广义表
表数据结构如下
标示图
typedef struct GNode *Glist;
struct GNode
{
int Tag; //标志域，0表示结点是单元素，1表示结点是广义表
union{ // 字表指针域Sublist与单元数据域Data复用，即共用存储空间
ElementType Data;
Glist Sublist;
}URegion;
Glist Next; //指向后继结点
}
多重链表
链表中的结点可能同时隶属于多个链
- 多重链表中结点的指针域会有多个，如果前面例子包含了Next和Sublist两个指针域；
- 但包含两个指针域的链表并不一定是多重链表，比如在双向链表中不是多重链表
多重链表有广泛的用途；基本上如树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储
例子如下：矩阵可以用二维数组表示，但是二维数组表示有两个缺陷
- 数组的大小要事先确定
- 对于“稀疏矩阵”，将造成大量的存储空间浪费
采用一种典型的多重链表——十字链表，来存储稀疏矩阵
- 只存储矩阵非零元素项
节点的数据域：行坐标，列坐标，数值 - 每个节点通过两个指针域，把同行同列串起来
行指针（或称为右指针）Right
列指针（或称为向下指针）Down
矩阵表示示意图
- 用一个标识符Tag来区分头结点和非0元素节点
- 头结点的标示值为“Head”，矩阵非0元素的节点的标识值为“Term”.
拆分结构图
下面代码是用结构体数组写的多项式表示及相加:
#include <stdio.h>
#include <malloc.h>
typedef struct Polynomial Nomial;
//多项式结构体
struct Polynomial
{
int coef; //多项式的系数
int expon; //多项式的指数
};
//打印多项式(结构体数组)
/**
* length 表示的是结构体数组的长度
*/
void PrintPoly(Nomial *p , int length)
{
int i;
printf("该多项式为 : ");
for(i=0;i<length;i++)
{
//按照A1x+A2x^2+A3x^3+....+Anx^n格式书写 ，对于符号以及系数为零的处理
if((p+i)->coef>0 && i!=0) //系数大于0并且不是第一项
(p+i)->expon!=0 ? printf("+%dx^%d",(p+i)->coef,(p+i)->expon):printf("+%d",(p+i)->coef);
else if((p+i)->coef == 0) //系数等于0
continue;
else
(p+i)->expon!=0 ? printf("%dx^%d",(p+i)->coef,(p+i)->expon):printf("%d",(p+i)->coef);
}
printf("\n");
}
//给单个结构体赋值
void addData(Nomial *p1 , int coef , int expon)
{
p1->coef = coef;
p1->expon = expon;
}
//给结构体数组赋值
void addDataArray(Nomial *p , int coef[] , int expon[] , int length)
{
int i;
for(i=0;i<length;i++)
{
p->coef = coef[i];
p->expon = expon[i];
p++;
}
}
//结构体数组相加 （其实是归并排序算法）
void add(Nomial p1[] , Nomial p2[] , Nomial res[] , int length1 , int length2 , int length3)
{
int i=0,j=0,k=0;
//两个数组，一次比较，把较大的存入新数组
while(j<length2 && i<length1)
{
if( p1[i].expon > p2[j].expon )res[k] = p1[i++];
else if( p1[i].expon < p2[j].expon )res[k] = p2[j++];
else
{
res[k]=p1[i];
res[k].coef = p1[i++].coef+p2[j++].coef;
}
k++;
}
//当p2比完之后，p1余量处理
while(i<length1)res[k++]=p1[i++];
//当p1比完之后，p2余量处理
while(j<length2)res[k++]=p2[j++];
//将res数组空闲内存初始化 为 0
for(;k<length3;k++)
{
res[k].coef = 0;
res[k].expon = 0;
}
}
int main()
{
Nomial P1[3] , P2[4] , P3[6] , res[20]; // 定义结构体数组
//定义系数数组 和 指数数组
int coef1[3] = {9,15,3} , expon1[3] = {12,8,2};
int coef2[4] = {26,-4,-13,82} , expon2[4] = {19,8,6,0};
int coef3[6] = {26,9,11,-13,3,82} , expon3[6] = {19,12,8,6,2,0};
addDataArray(P1,coef1,expon1,3);
PrintPoly(P1,3);
addDataArray(P2,coef2,expon2,4);
PrintPoly(P2,4);
addDataArray(P3,coef3,expon3,6);
PrintPoly(P3,6);
add(P1,P2,res,3,4,20);
PrintPoly(res,20);
add(res,P3,res,20,6,20);
PrintPoly(res,20);
return 0;
}
大家可以考虑一下，用线性链表怎么实现多项式相加相乘。
