线性表是指具有相同数据类型的n(n>=0)个数据元素的有限序列,它具有一个表头元素和一个表尾元素,并且每一个数据元素最多只有一个直接前驱和一个直接后继。

线性表的顺序存储也叫作顺序表,它的特性是地址连接、依次存储。

顺序表的定义有静态建表和动态建表两种。

静态建表的实现方法为:

#define MaxSize 50             //定义线性表的最大长度
typedef int ElemType; //假定表中元素类型是int
typedef struct{
ElemType data[MaxSize]; //顺序表的元素(数组)
int length; //顺序表的当前长度
}SqList;

动态建表的实现方法为:

typedef int ElemType;
typedef struct{
ElemType *data; //指示动态分配数组的指针
int MaxSize,length; //数组的最大容量个当前个数
}SeqList;

在动态建表中,内存的分配语句为:

#define InitSize 100
SeqList L;
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);

描述或定义一个顺序表需要:①存储空间的起始位置;②顺序表的最大存储量;③顺序表当前的长度。

对于顺序表第i位置插入值e操作实现:

bool ListInsert(SqList&L,int i,ElemType e){
if(i<||i>L.length+) return false; //判断i的范围是否有效
if(L.length>=MaxSize) return false; //当前存储空间已满,不能插入
for(int j=L.length;j>=i;j--) L.data[j]=L.data[j-]; //将第i个元素及之后的元素后移
L.data[i-]=e;
L.length++;
return true;
}

对于顺序表第i位置删除值操作实现:

bool ListDel(SqList &L,int i,ElemType &e){
if(i<||i>L.length) return false; //判断i的范围是否有效
e=L.data[i-]; //将被删除的元素赋值给e
for(int j=i;j<L.length;j++) L.data[j-i]=L.data[j]; //将第i个位置之后的元素前移
L.length--;
return true;
}

根据数组的特性,如果想向顺序表中进行插入和删除的操作时需要移动插入/删除点后的所有值,浪费了很多的系统资源。同时,存储顺序表需要一大块连续的地址空间,使得空间利用率下降。因此,我们引入链式存储的线性表,也叫作链表。

对于链表中最简单的单链表,其定义为:

typedef struct LNode{                 //定义单链表节点类型
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList;

对于一个新建立的单链表,向其中加入结点有两种方法:

①头插法建立单链表:将新结点插入到当前链表的表头(向前建表);

LinkList CreatList1(LinkList &L){
LNode *s; //辅助指针
int x; //存储插入结点数据的值
L=(LinkList)malloc(sizrof(LNode)); //创建头结点
L->next=NULL; //初始为空链表
scanf("%d",&x); //输入结点的值
while(x!=){ //输入9999表示结束
s=(LNode*)malloc(sizeof(LNode)); //创建新的结点
s->data=x; //对新结点的数据赋值
s->next=L->next; //新结点的后继指向第一个结点
L->next=s; //头结点的后继指向新结点
scanf("%d",&x); //读入下一个结点值
}
return L;
}

②尾插法建立单链表:将新结点插入到当前链表的表尾(向后建表);

LinkList CreatList1(LinkList &L){
int x; //存储插入结点数据的值
L=(LinkList)malloc(sizrof(LNode)); //创建头结点
LNode *s,*r=L; //辅助指针,r为表尾指针
scanf("%d",&x); //输入结点的值
while(x!=){ //输入9999表示结束
s=(LNode*)malloc(sizeof(LNode)); //创建新的结点
s->data=x; //对新结点的数据赋值
r->next=s; //新结点在尾结点的后面
r=s; //r指向新的表尾结点
scanf("%d",&x); //读入下一个结点值
}
r->next=NULL; //尾结点指针置空
return L;
}

对于单链表的查找也有两种方法:

①按序号查找结点:在单链表中从第一个结点出发,顺指针next域逐个往下搜索,知道找到第i个结点为止,否则返回最后一个结点指针域NULL;

LNode *GetElem(LinkList L,int i){
int j=; //计数,初始为1
LNode *p=L->next; //第一个结点指针赋值给p
if(i==) return L; //若i等于0,则返回头结点
if(i<) return NULL; //若i无效,则返回NULL
while(p&&j<i){ //从第1个结点开始找,查找第i个结点
p=p->next;
j++;
}
return p;
}

②按值查找结点:从单链表的第一个结点开始,由前向后依次比较表中各结点数据域的值,若结点数据域的值等于给定值e,则返回该结点的指针,若没有则返回NULL。

LNode *LocateElem(LinkList L,ElemType e){
LNode *p=L->next;
while(p!=NULL&&p->data!=e) //从第1个结点开始查找data域为e的结点
p=p->next;
return p; //找到后返回该结点指针,否则返回NULL
}

单链表的插入操作:

①取指向插入位置的前驱结点的指针 p=GetElem(L,i-1);

②令新结点*s的指针域指向*p的后继结点 s->next=p->next;

③令新结点*p的指针域指向新插入的结点*s p->next=s。

单链表的删除操作:

①p=GetElem(L,i-1);

②q=p->next;

③p->next=q->next;

④free(q).

对于单链表,对数据结点的前驱访问比较困难,所以我们引入双链表,其定义为:

typedef struct DNode{                 //定义双链表节点类型
ElemType data; //数据域
struct DNode *prior,*next; //指针域 (前驱+后继)
}DNode,*DLinkList;

双链表的插入操作:

①s->next=p->next;

②p->next->prior=s;

③s->prior=p;

④p->next=s.

双链表的删除操作:

①p->next=q->next;

②q->next->prior=p;

③free(q).

循环单链表:①最后一个结点的指针指向头结点;②从任何一个结点出发都能访问到链表的每一个元素;③判空的条件是头结点的后继为头指针;④对循环单链表仅设置尾指针使得操作效率更高。

循环双链表:①尾结点的后继指向头结点,头结点前驱指向尾结点;②当循环双链表为空表时,其头结点的前驱和后继都为头结点。

静态链表:是借助数组来描述线性表链式存储结构的一种链表,结点中也包含数据域data和指针next,与前面链表中的指针不同的是,这里的指针是结点的相对地址(数组下标),又称为游标。

对于一个a->b->c->d的数据链表,它的静态链表的表示形式为:

数组下标 data next
0 2
1 b 6
2 a 1
3 d -1(结束)
4    
5    
6 c 3

对静态链表的插入、删除操作与动态链表一样,只需要修改指针,而不需要移动元素。

静态链表的定义为:

#define MaxSize 50                  //定义静态链表的最大长度
typedef int ElemType //假定表中元素类型是int
typedef struct{ //静态链表结构类型的定义
ElemType data; //存储数据元素
int next; //下一个元素的数组下标
}SLinkList[MaxSize];

最新文章

  1. iOS多线程之1.从Thread看多线程的生命周期
  2. 关于Javascript的使用参考
  3. robotframework笔记17
  4. js----全局变量和局部变量部分讲解
  5. fltk_hello world
  6. Thinkphp 文本编辑器
  7. 基于jQuery的Jsonp跨域[Get方式]
  8. Xamarin.Android 如何使用Assets目录下的文件
  9. HTTP协议(超文本传输协议)
  10. floor()函数 向下取整 ceil()函数向上取整
  11. IDEA+Java:Selenium+Maven+TestNG基本WebUI自动化测试环境搭建
  12. 201521123011 《Java程序设计》第4周学习总结
  13. JVM的Server与Client运行模式区别与切换
  14. MySQL安全配置向导mysql_secure_installation详解
  15. oracle控制文件问题
  16. Salesforce Invoking Http Callouts and Testing Http Callouts
  17. Confluence 6 用户目录图例 - 使用 LDAP 授权的内部目录
  18. 通用triggerEvent方法
  19. LeetCode 349 Intersection of Two Arrays 解题报告
  20. Jquery DataTable基本使用

热门文章

  1. BZOJ 1503: [NOI2004]郁闷的出纳员
  2. 报错:org.hibernate.AssertionFailure: null id in com.tt.hibernate.entities.News entry (don&#39;t flush the Session after an exception occurs)
  3. netcat使用
  4. 认识Activity,创建第一个android应用-Hello Word
  5. 学习C++.Primer.Plus 7 函数
  6. 利用 Rational ClearCase ClearMake 构建高性能的企业级构建环境
  7. Jquery 1.11.1 Checkbox checked 判断
  8. RGB同步信号 DCLK/HS/VS/DE信号介绍
  9. JS获取图片上传地址
  10. .NET基础拾遗(5)反射2
  11. [转载]浅析Windows安全相关的一些概念
  12. Gradle学习系列之一——Gradle快速入门(转)
  13. hibernate 管理 Session(单独使用session,不spring)
  14. go 监听系统信号
  15. POJ 1515 Street Directions (边双连通)
  16. JVM即时编译器
  17. A The Empire Age
  18. 申请Office 365一年免费的开发者账号攻略(2018年10月份版本)
  19. Linux之SSH免密登录
  20. 零基础爬虫----python爬取豆瓣电影top250的信息(转)