(本文使用的代码语言均为C语言,由于代码渲染问题改为了C++)
1.线性表的类型定义
线性表(linear_list)是最常用且最简单的一种数据结构。简言之,一个线性表是n个数据元素的有限序列。
在稍微复杂的线性表中,一个数据元素可以由若干个数据项组成。在这种情况下,常把数据元素称为记录,含有大量记录的线性表叫做文件。(前驱元素与后继元素,位序)
抽象数据类型线性表的定义如下:
ADT List{
数据对象: D={ai|ai∈ElemSet, i=l, 2, …, n, n>=0}
数据关系:R=(|ai-1,ai∈D, i=2, …, n}
基本操作:
InitList (&L)
操作结果:构造一个空的线性表L。
DestroyList(&L)
初始条件:线性表L已存在。
操作结果:销毁线性表L。
ClearList (&L)
初始条件:线性表L已存在。
操作结果:将L重置为空表。
ListEmpty(L)
初始条件:线性表L已存在。
操作结果:若L为空表,则返回true, 否则返回false。
ListLength(L)
初始条件:线性表L已存在。
操作结果:返回L中数据元素个数。
GetElem(L,i,&e)
初始条件:线性表L巳存在,且1:,s;i:os;ListLength(L)。
操作结果:用e返回L中第1个数据元素的值。
LocateElem(L,e)
初始条件:线性表L已存在。
操作结果:返回L中第1个 值与e相同的元素在 L中的位置 。若这样的数据元素不存在 ,则返回值为0。
PriorElem(r,cur_e,&pre_e)
初始条件:线性表L已存在。
操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回其前驱,否则操作失败,pre_e无定义。
NextElem(L,cur_e,&next_e)
初始条件:线性表L已存在。
操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回其后继,否则操作失败,next_e无定义。
Listinsert(&L,i,e)
初始条件:线性表L已存在,且1:,s;i:os;ListLength (L) +l。
操作结果:在 L中第1个位置之前插入新的数据元素 e, L的长度加1。
ListDelete(&L,i)
初始条件:线性表L已存在且非空,且l:os;i:os;ListLength(L)。
操作结果:删除L的第1个数据元素,L的长度减1。
TraverseList(L)
初始条件:线性表L已存在。
操作结果:对线性表L进行遍历,在遍历过程中对 L的每个结点访问一次。
} ADT List
2.线性表的顺序表示和实现
线性表的顺序表示是指用一组地址连续的存储单元依次存储线性表的数据元素。
线性表中第i个元素的位置为
3.线性表的链式表示和实现
线性链表
线性表的链式储存结构的特点之一是用一组任意的存储单元存储线性表的数据元素(可连续可不连续)。因此,为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其他后继的信息。这两部分信息组成数据元素ai的存储映像,成为结点(node)。
它包括两个域:其中存储数据元素信息的域称为数据域;存储直接后继存储位置的域成为指针域。指针域中存储的信息称作指针或链。n个结点链结成一个链表。
由于此链表的每一个结点元素只包含一个指针域,故此链表又称为线性链表或单链表。
链表从头指针开始,最后一个结点为空(NULL)。
一个线性链表的存储结构:
typedef struct LNode//定义链表LNode以及指针*linklist { ElemType data; struct LNode *next; }LNode,*LinkList;
状态函数定义:
typedef enum Status { ERROR, SUCCESS }Status;
下面将直接放上链表各种操作的代码:
- 搜索第i个元素用到GetElem函数:
Status GetElem_L(LinkList L,int i,ElemType &e) { //L为头指针,i为搜索的第i个元素,e为数据暂存的变量。 p=L->next;j=1; while(p&&jnext; ++j; } if(!p||j>i) return ERROR; e=p->data; return SUCCESS; }
- 初始化:
Status InitList(LinkedList *L) { *L = (LinkedList)malloc(sizeof(LinkedList)); //给第一个结点申请空间 if(!(*L)) //若申请失败返回错误 return ERROR; (*L)->next = NULL; return SUCCESS; }
- 摧毁链表:
void DestroyList(LinkedList *L) { LinkedList p; while(*L){ p = (*L)->next; free(*L); *L = p; } }
插入元素
Status ListInsert_L(LinkList &L,int i,ElemType e){ p=L;j=0; while(p&&j
next;++j;} if(!p||j>i-1) return ERROR; s=(LinkList)malloc(sizeof(LNode)); s->data=e;s->next=p->next; p->next=s; return SUCCESS; } 删除结点
Status ListDelete_L(LinkList &L,int i,ElemType &e){ p=L;j=0; while(p->next&&j
next;j++; } if(!(p->next)||j>i-1) return ERROR; q=p->next; p->next=q->next; e=q->data; free(q); return SUCCESS; } (头插法)逆向建立单链表
void CreateList_L(LinkList &L,int n) { L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; for(i=n;i>0;i--) { p=(LinkList)malloc(sizeof(LNode)); scanf(&p->data); p->next=L->next;L->next=p; } }
尾插法建立单链表(这个和其余代码参数传递规则不一样,传递了头结点的指针)
void creatlinklistTail(linklist *L)//尾插法较为常用 { int i,n; linklist p1,p2; (*L)=(linklist)malloc(sizeof(LNode)); p2=*L; printf("please input the number of the linklist\n"); scanf("%d",&n); for(i=0;i
ele); p2->next=p1; p2=p1; } p2->next=NULL; } - 归并两个链表
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) { pa=La->next;pb=Lb->next; Lc=pc=pa; while(pa&&pb){ if(pa->data<=pb->data) {pc->next=pa;pc=pa;pa=pa->next;} else{pc->next=pb;pc=pb;pb=pb->next;} } pc->next=pa?pa:pb; free(Lb); }
- 单链表的全部操作(可运行)(参数传递规则不同)
#include
#include typedef int Elemtype;//定义数据类型 typedef enum Status { ERROR, SUCCESS }Status; typedef struct LNode//定义链表LNode以及指针*linklist { Elemtype ele; struct LNode *next; }LNode,*linklist; Status Init(linklist *L)//初始化链表 { *L = (linklist)malloc(sizeof(LNode)); //给第一个结点申请空间 if(!(*L)) //若申请失败返回错误 return ERROR; (*L)->next = NULL; return SUCCESS; } void destory(linklist *L)//摧毁链表 { linklist p; while(*L) { p=(*L)->next; free(*L); (*L)=p; } } void creatlinklistHead(linklist *L)//头插法有点难理解 { int i,n; linklist p; (*L) = (linklist)malloc(sizeof(LNode)); (*L)->next=NULL; printf("please input the number of the linklist\n"); scanf("%d",&n); for(i=0;i ele); //注意理解以下两行内容 p->next=(*L)->next; (*L)->next=p; } } void creatlinklistTail(linklist *L)//尾插法较为常用 { int i,n; linklist p1,p2; (*L)=(linklist)malloc(sizeof(LNode)); p2=*L; printf("please input the number of the linklist\n"); scanf("%d",&n); for(i=0;i ele); p2->next=p1; p2=p1; } p2->next=NULL; } int Lengthlist(linklist *L)//长度 { int length=0; linklist p; p=(*L)->next; while (p) { length++; p=p->next; } return length; } void Getelement(linklist *L,int i) { linklist p=(*L)->next; int k=1; while(k!=i&&p) { p=p->next; k++; } if(!p) { printf("不存在\n"); return; } else { printf("%d\n",p->ele); return; } } void Insertelementfront(int i,linklist *L,Elemtype ele)//前插入第i个元素的后面 { linklist p1,p2=(*L)->next; int k=1; p1=(linklist)malloc(sizeof(LNode)); p1->ele=ele; while (p2&&knext; k++; } if(!p2) { printf("不存在\n"); return; } p1->next=p2->next; p2->next=p1; } void Deleteelement(linklist *L,int i) { linklist p1,p2; int k=1; p1=(*L)->next; p2=*L; while (p1&&knext; k++; } if(!p1) { printf("不存在\n"); return; } p2->next=p1->next; free(p1); } void printlist(linklist *L) { linklist p; p=(*L)->next; if(p==NULL) { printf("NULL\n"); } while(p) { printf("%d->",p->ele); p=p->next; } printf("\n"); } int main() { linklist L; Init(&L); creatlinklistTail(&L); printlist(&L); } 当然我们也可以用一维数组来描述线性链表。
与指针型链表不同,此种链表空间固定,不能动态分配,故又称为静态链表。结构:
#define MAXSIZE 1000 typedef struct{ ElemType data; int cur; }component,SLinkList[MAXSIZE];
循环链表
与普通链表区别在于,算法中的循环条件不是p或者p->next为空,而是他们是否等于头指针。
另外,有的时候会设置尾指针而不设置头指针,会简化部分操作。
双向链表
双向链表的结点有两个指针域,其一指向直接后继,另一指向直接前驱
结构:
typedef struct DuLNode{ ElemType data; struct DuLNode *prior; struct DuLNode *next; }DuLNode,*DuLinkList;
双向链表也可以有循环表。
4.一元多项式的表示及相加
注意点:顺序存储和次方存储。
别的没啥挺简单的…
最后来说一下抽象数据类型Polynomial
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
#include /* malloc()等 */
#include /* EOF(=^Z或F6),NULL */
#include /* exit() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
//#define OVERFLOW -2
/* ----------------------- 抽象数据类型Polynomial的实现 ------------------------*/
typedef struct /* 项的表示,多项式的项作为LinkList的数据元素 */
{
float coef; /* 系数 */
int expn; /* 指数 */
}term, ElemType;
/* 两个类型名:term用于本ADT,ElemType为LinkList的数据对象名 */
/* ----------------------- 带头结点的线性链表类型存储结构 ------------------------*/
typedef struct LNode /* 结点类型 */
{
ElemType data;
struct LNode *next;
}LNode, *Link, *Position;
typedef struct LinkList /* 链表类型 */
{
Link head, tail; /* 分别指向线性链表中的头结点和最后一个结点 */
int len; /* 指示线性链表中数据元素的个数 */
}LinkList;
typedef LinkList polynomial;
/* -----------------------------------------------------------------------------------------*/
/* -------------------- 需要用到的 具有实用意义的线性链表的基本操作 ---------------------------*/
Status MakeNode(Link *p, ElemType e)
{ /* 分配由p指向的值为e的结点,并返回OK;若分配失败。则返回ERROR */
*p = (Link)malloc(sizeof(LNode));
if (!*p)
return ERROR;
(*p)->data = e;
return OK;
}
void FreeNode(Link *p)
{ /* 释放p所指结点 */
free(*p);
*p = NULL;
}
Status InitList(LinkList *L)
{ /* 构造一个空的线性链表 */
Link p;
p = (Link)malloc(sizeof(LNode)); /* 生成头结点 */
if (p)
{
p->next = NULL;
(*L).head = (*L).tail = p;
(*L).len = 0;
return OK;
}
else
return ERROR;
}
Status ClearList(LinkList *L)
{ /* 将线性链表L重置为空表,并释放原链表的结点空间 */
Link p, q;
if ((*L).head != (*L).tail)/* 不是空表 */
{
p = q = (*L).head->next;
(*L).head->next = NULL;
while (p != (*L).tail)
{
p = q->next;
free(q);
q = p;
}
free(q);
(*L).tail = (*L).head;
(*L).len = 0;
}
return OK;
}
Status InsFirst(LinkList *L, Link h, Link s) /* 形参增加L,因为需修改L */
{ /* h指向L的一个结点,把h当做头结点,将s所指结点插入在第一个结点之前 */
s->next = h->next;
h->next = s;
if (h == (*L).tail) /* h指向尾结点 */
(*L).tail = h->next; /* 修改尾指针 */
(*L).len++;
return OK;
}
Status DelFirst(LinkList *L, Link h, Link *q) /* 形参增加L,因为需修改L */
{ /* h指向L的一个结点,把h当做头结点,删除链表中的第一个结点并以q返回。 */
/* 若链表为空(h指向尾结点),q=NULL,返回FALSE */
*q = h->next;
if (*q) /* 链表非空 */
{
h->next = (*q)->next;
if (!h->next) /* 删除尾结点 */
(*L).tail = h; /* 修改尾指针 */
(*L).len--;
return OK;
}
else
return FALSE; /* 链表空 */
}
Status Append(LinkList *L, Link s)
{ /* 将指针s(s->data为第一个数据元素)所指(彼此以指针相链,以NULL结尾)的 */
/* 一串结点链接在线性链表L的最后一个结点之后,并改变链表L的尾指针指向新 */
/* 的尾结点 */
int i = 1;
(*L).tail->next = s;
while (s->next)
{
s = s->next;
i++;
}
(*L).tail = s;
(*L).len += i;
return OK;
}
Position PriorPos(LinkList L, Link p)
{ /* 已知p指向线性链表L中的一个结点,返回p所指结点的直接前驱的位置 */
/* 若无前驱,则返回NULL */
Link q;
q = L.head->next;
if (q == p) /* 无前驱 */
return NULL;
else
{
while (q->next != p) /* q不是p的直接前驱 */
q = q->next;
return q;
}
}
ElemType GetCurElem(Link p)
{ /* 已知p指向线性链表中的一个结点,返回p所指结点中数据元素的值 */
return p->data;
}
Status ListEmpty(LinkList L)
{ /* 若线性链表L为空表,则返回TRUE,否则返回FALSE */
if (L.len)
return FALSE;
else
return TRUE;
}
Position GetHead(LinkList L)
{ /* 返回线性链表L中头结点的位置 */
return L.head;
}
Position NextPos(Link p)
{ /* 已知p指向线性链表L中的一个结点,返回p所指结点的直接后继的位置 */
/* 若无后继,则返回NULL */
return p->next;
}
Status LocateElemP(LinkList L, ElemType e, Position *q, int(*compare)(ElemType, ElemType))
{ /* 若升序链表L中存在与e满足判定函数compare()取值为0的元素,则q指示L中 */
/* 第一个值为e的结点的位置,并返回TRUE;否则q指示第一个与e满足判定函数 */
/* compare()取值>0的元素的前驱的位置。并返回FALSE。(用于一元多项式) */
Link p = L.head, pp;
do
{
pp = p;
p = p->next;
} while (p && (compare(p->data, e) < 0)); /* 没到表尾且p->data.expndata, e) > 0) /* 到表尾或compare(p->data,e)>0 */
{
*q = pp;
return FALSE;
}
else /* 找到 */
{
*q = p;
return TRUE;
}
}
/* ---------------------- 抽象数据类型Polynomial 基本操作的函数原型说明 -----------------------*/
void CreatPolyn(polynomial *P, int m); /* 算法2.22 */
Status DestroyPolyn(polynomial *P);
void PrintPolyn(polynomial P);
int PolynLength(polynomial P);
void AddPolyn(polynomial *Pa, polynomial *Pb);
void AddPolyn1(polynomial *Pa, polynomial *Pb);
void SubtractPolyn(polynomial *Pa, polynomial *Pb);
void MultiplyPolyn(polynomial *Pa, polynomial *Pb);
/* -----------------------------------------------------------------------------------------------*/
int cmp(term a, term b)
{ /* 依a的指数值<、=或>b的指数值,分别返回-1、0或+1 */
if (a.expn == b.expn)
return 0;
else
return (a.expn - b.expn) / abs(a.expn - b.expn);
}
/* ----------------------------- 抽象数据类型Polynomial 基本操作的实现 -----------------------------*/
void CreatPolyn(polynomial *P, int m) /* 算法2.22 */
{ /* 输入m项的系数和指数,建立表示一元多项式的有序链表P */
Position q, s;
term e;
int i;
InitList(P);
printf("请依次输入%d个系数,指数:\n", m);
for (i = 1; i <= m; ++i)
{ /* 依次输入m个非零项(可按任意顺序) */
scanf_s("%f,%d", &e.coef, &e.expn);
if (!LocateElemP(*P, e, &q, cmp)) /* 当前链表中不存在该指数项,cmp是实参 */
if (MakeNode(&s, e)) /* 生成结点并插入链表 */
InsFirst(P, q, s);
}
}
Status DestroyPolyn(polynomial *P)
{ /* 销毁线性链表L,L不再存在 */
ClearList(P); /* 清空链表 */
FreeNode(&(*P).head);
(*P).tail = NULL;
(*P).len = 0;
return OK;
}
void PrintPolyn(polynomial P)
{ /* 打印输出一元多项式P */
Link q;
q = P.head->next; /* q指向第一个结点 */
printf(" 系数 指数\n");
while (q)
{
printf("%f %d\n", q->data.coef, q->data.expn);
q = q->next;
}
}
int PolynLength(polynomial P)
{ //返回线性链表L中元素个数
return P.len;
}
void AddPolyn(polynomial *Pa, polynomial *Pb) /* 算法2.23 */
{ /* 多项式加法:Pa=Pa+Pb,并销毁一元多项式Pb */
Position ha, hb, qa, qb;
term a, b;
ha = GetHead(*Pa);
hb = GetHead(*Pb); /* ha和hb分别指向Pa和Pb的头结点 */
qa = NextPos(ha);
qb = NextPos(hb); /* qa和qb分别指向Pa和Pb中当前结点(现为第一个结点) */
while (qa && qb)
{ /* qa 和 qb 均为非空 */
a = GetCurElem(qa);
b = GetCurElem(qb); /* a和b为两表中当前比较元素 */
switch (cmp(a, b))
{
case -1:ha = qa; /* 多项式Pa中当前结点的指数值小 */
qa = NextPos(ha); /* ha和qa均向后移一个结点 */
break;
case 0: qa->data.coef += qb->data.coef;
/* 两者的指数值相等,修改Pa当前结点的系数值 */
if (qa->data.coef == 0) /* 删除多项式Pa中当前结点 */
{
DelFirst(Pa, ha, &qa);
FreeNode(&qa);
}
else
ha = qa;
DelFirst(Pb, hb, &qb);
FreeNode(&qb);
qb = NextPos(hb);
qa = NextPos(ha);
break;
case 1: DelFirst(Pb, hb, &qb); /* 多项式Pb中当前结点的指数值小 */
InsFirst(Pa, ha, qb);
ha = ha->next;
qb = NextPos(hb);
}
}
if (!ListEmpty(*Pb))
{
Append(Pa, qb); /* 链接Pb中剩余结点 */
}
DestroyPolyn(Pb); /* 销毁Pb */
}
void AddPolyn1(polynomial *Pa, polynomial *Pb)
{ /* 另一种多项式加法的算法:Pa=Pa+Pb,并销毁一元多项式Pb */
Position qb;
term b;
qb = GetHead(*Pb); /* qb指向Pb的头结点 */
qb = qb->next; /* qb指向Pb的第一个结点 */
while (qb)
{
b = GetCurElem(qb);
OrderInsertMerge(Pa, b, cmp);
qb = qb->next;
}
DestroyPolyn(Pb); /* 销毁Pb */
}
void Opposite(polynomial Pa)
{ /* 一元多项式系数取反 */
Position p;
p = Pa.head;
while (p->next)
{
p = p->next;
p->data.coef *= -1;
}
}
void SubtractPolyn(polynomial *Pa, polynomial *Pb)
{ /* 多项式减法:Pa=Pa-Pb,并销毁一元多项式Pb */
Opposite(*Pb);
AddPolyn(Pa, Pb);
}
void MultiplyPolyn(polynomial *Pa, polynomial *Pb)
{ /* 多项式乘法:Pa=PaPb,并销毁一元多项式Pb */
polynomial Pc;
Position qa, qb;
term a, b, c;
InitList(&Pc);
qa = GetHead(*Pa);
qa = qa->next;
while (qa)
{
a = GetCurElem(qa);
qb = GetHead(*Pb);
qb = qb->next;
while (qb)
{
b = GetCurElem(qb);
c.coef = a.coef*b.coef;
c.expn = a.expn + b.expn;
OrderInsertMerge(&Pc, c, cmp);
qb = qb->next;
}
qa = qa->next;
}
DestroyPolyn(Pb); /* 销毁Pb */
ClearList(Pa); /* 将Pa重置为空表 */
(*Pa).head = Pc.head;
(*Pa).tail = Pc.tail;
(*Pa).len = Pc.len;
}
Status OrderInsertMerge(LinkList *L, ElemType e, int(*compare)(term, term))
{ /* 按有序判定函数compare()的约定,将值为e的结点插入或合并到升序链表L的适当位置 */
Position q, s;
if (LocateElemP(*L, e, &q, compare)) /* L中存在该指数项 */
{
q->data.coef += e.coef; /* 改变当前结点系数的值 */
if (!q->data.coef) /* 系数为0 */
{ /* 删除多项式L中当前结点 */
s = PriorPos(*L, q); /* s为当前结点的前驱 */
if (!s) /* q无前驱 */
s = (*L).head;
DelFirst(L, s, &q);
FreeNode(&q);
}
return OK;
}
else /* 生成该指数项并插入链表 */
if (MakeNode(&s, e)) /* 生成结点成功 */
{
InsFirst(L, q, s);
return OK;
}
else /* 生成结点失败 */
return ERROR;
}
void main()
{
polynomial p, q;
int m;
printf("请输入第一个一元多项式的非零项的个数:");
scanf_s("%d", &m);
CreatPolyn(&p, m);
printf("请输入第二个一元多项式的非零项的个数:");
scanf_s("%d", &m);
CreatPolyn(&q, m);
AddPolyn(&p, &q);
printf("两个一元多项式相加的结果:\n");
PrintPolyn(p);
printf("请输入第三个一元多项式的非零项的个数:");
scanf_s("%d", &m);
CreatPolyn(&q, m);
AddPolyn1(&p, &q);
printf("两个一元多项式相加的结果(另一种方法):\n");
PrintPolyn(p);
printf("请输入第四个一元多项式的非零项的个数:");
scanf_s("%d", &m);
CreatPolyn(&q, m);
SubtractPolyn(&p, &q);
printf("两个一元多项式相减的结果:\n");
PrintPolyn(p);
printf("请输入第五个一元多项式的非零项的个数:");
scanf_s("%d", &m);
CreatPolyn(&q, m);
MultiplyPolyn(&p, &q);
printf("两个一元多项式相乘的结果:\n");
PrintPolyn(p);
DestroyPolyn(&p);
}