公司网站的建站要点,一个网站不兼容ie怎么做,泰安电视台新闻综合频道,不同程序建的网站风格线性表 线性表的基本概念线性表的顺序存储线性表顺序存储的类型定义线性表基本运算在顺序表上的实现顺序表实现算法的分析 线性表的链接存储单链表的类型定义线性表的基本运算在单链表上的实现 其他运算在单链表上的实现建表删除重复结点 其他链表循环链表双向循环链表 顺序实现… 线性表 线性表的基本概念线性表的顺序存储线性表顺序存储的类型定义线性表基本运算在顺序表上的实现顺序表实现算法的分析 线性表的链接存储单链表的类型定义线性表的基本运算在单链表上的实现 其他运算在单链表上的实现建表删除重复结点 其他链表循环链表双向循环链表 顺序实现与链接实现的比较小试牛刀 线性表的基本概念
线性表是一种线性结构由nn0个数据元素组成的有序序列数组元素称为结点n称为表长线性表通常可表示为a1a2,…,an),a1称为起始结点an称为终端结点。对任意一对相邻结点ai和·ai1(1in)ai称为ai1的直接前驱ai1称为ai的直接后继基本特征结点具有一对一的关系结点数不为零则除起始结点没有直接前驱外其他每个结点有且仅有一个直接前驱除终端结点没有直接后继外其他结点有且仅有一个直接后继线性表的基本运算及其功能描述 初始化Initiate(L):建立一个空表LL不含数据元素求表长Length(L):返回线性表L的长度读表元素Get(L,i):返回线性表第i个数据元素当i不满足1iLenght(L)时返回一特殊值定位Locate(L,x):查找线性表中数据元素等于x的数据结点序号若有多个则取第一个插入Insert(L,x,i):在线性表L的第i个元素之前插入一个值为x的新数据元素表长度加1删除 Delete(L,i删除线性表L的第i个数据元素ai表长度减1
线性表的顺序存储
线性表顺序存储的类型定义
线性表存储的方法将表中结点依次存放在计算机内存中一组连续的存储单元中用顺序存储实现的线性表称为顺序表
线性表基本运算在顺序表上的实现
插入在i处插入x,即ai——an向后移一位将x置于i,表长1算法描述如下
void InsertSeqList L,DataType x,int i)
{
if (L.lengthMaxsize) exit(表已满)
if (i1 || iL.length1) exit(位置错)
for(jL.length;ji;j--) //从后往前一个一个挪L.data[i-1]x;L.length;
}图解如下
删除删除第i个元素表长减1
void DeleteSeqList(SeqList L,int i)
{
if(i1||iL.length)exit(非法位置)
for(ji;jL.length;j)L.data[j-1]L.data[j];
L.length--;
}图示如下
定位查找线性表中值等于x结点序号的最小值找不到返回0
void LocateSeqlist(Seqlist L,DataType x)
{
int i0;
while((iL.length)(L.data[i]!x))i;
if(iL.length) return i1
else return 0;
}顺序表实现算法的分析
插入算法最坏时间复杂度为On,平均时间复杂度为On删除算法最坏时间复杂度为On,平均时间复杂度为On定位算法最坏时间复杂度为On,平均时间复杂度为On)求表长和读表元素算法时间复杂度均为O1
线性表的链接存储
单链表的类型定义
单链表——线性表的数据元素用指针链接起来的存储结构指针表示数据元素之间的逻辑关系各个结点在内存中的存储位置并不一定连续 注单链表可以比作火车有一个火车头头指针变量该变量的值是指向单链表的第一个结点的指针。判断单链表是否为空指针的条件如下head——nextNULL或head——nextNULL 线性表的基本运算在单链表上的实现
初始化——创建一个头指针并将其指针域设为NULL即创建一个空单链表
LinkList InitiateLinkList()
{
LinkList head; //头指针
headmalloc(sizeof(Node)); //动态构建一结点为头结点
headhead-nextNULL;
return head;
}求表长——设计一个工作指针p,初始指向头结点并设置一个计数器cnt初值设为0p每移动一个结点cnt加1直到p-nextNULL
int LengthLinklist(LinkList head)
{
Node *phead;
int cnt0;
while(p-next!NULL)
{pp-next;cnt;
}
return cnt;
}读表元素——从头开始直到找到给定序号下的元素
Node * GetLinklist(LinklList head,int i)
{
Node *p;
phead-next;;
int c1;
while ((ci)(p!NULL))
{pp-next;c;}
if(ic) return p;
else return NULL;
}定位——给出值找到该元素位置按值查找
int LocateLinklist(LinkList head,DataType x)
{
Node *phead;
pp-next;
int i0;
while((p!NULL)(p-data!x))
{
i;
pp-next;
}
if(p!NULL) return i1;
else return 0;
}插入——值为x的元素插入到第i个结点之前 步骤如下
1.q指针指向i-1结点p指针指向待加入结点x 2.p指针指向q的直接后继:p-nextq-next; 3. q指针指向p:q-nextp;
void InsertLinklist(LinkList head,DataType x,int i)
{
Node *p,*q;
if(i1) qhead;;
else qGetLinklist(head,i-1);
if(qNULL)exit(找不到插入位置)
else{pmalloc(sizeof(Node));p-datax;p-nextq-next;q-nextp;}
}删除将第i个结点删除 void DeleteLinklist(LinkList head,int i)
{
Node *p;
if(i1)qhead;
else qGetLinklist(head,i-1); //找到待删除结点的直接前驱
if(qNULL q-next!NULL)
{
pq-next;
q-nextp-next;
free(p); //释放已经移出结点p的空间
}
else exit(找不到要删除的结点)
}其他运算在单链表上的实现
建表
通过插入算法加入新结点
LinkList CreatLinklist1(){
Linklist head;
int x,i;
headInitiateLinklist(); //建立空表
i1;
scanf(%d,x)
while(x!0);
{
InsertLinklist(head,x,i);
i;
scanf(%d,x); //读下一元素
}
return head;
}
时间复杂度为On2
通过一个指向尾结点的指针将新结点插入到表尾
LinkList CreateLinklist2()
{
Linklist head;
Node *q,*t;
int x;
headmalloc(sizeof(Node)) //生成头结点
qhead;
scanf(%d,%x);
while(x!0)
{
tmalloc(sizeof(Node));t-datax; //生成一个新结点
q-nextt; //新结点t链入
qt //修改尾指针q指向新的尾结点
scanf(%d,x);
}
q-nextNULL;return head; //q指向尾结点置尾结点结束
}时间复杂度为On
始终将新增加的结点插入到头结点之后
LinkList CreateLinklist3()
{
Linklist head;
Node *p;
int x;
headmalloc(sizeof(Node)); //生成头结点
head-nextNULL;
scanf(%d,x);
while(x)
{
pmalloc(sizeof(Node));
p-datax;
p-nexthead-next; //前插插入到头结点之后第一个结点之前
head-nextp;
scanf(%d,x);
}
return head;
}时间复杂度为On
删除重复结点
一个指针用来确定和谁比较一个指针移动使得每一项都与之比较永远指向待删结点的直接前驱,一个指针用于删除
void PurgeLinklist(LinkList head)
{
Node *p,*q,*r
qhead-next; //q指向首结点
while(q!NULL){pq; //p指向*qwhile(p-next!NULL)if(p-next-dataq-data) //若重复{rp-next; //r指向待删除结点p-nextr-next; //p的直接后继等于r的直接后继移出待删结点free(r); //释放}else pp-next; //检查下一个qq-next; //更新检查结点}
}其他链表
循环链表 尾结点的指针域指向第一个结点即构成循环链表 双向循环链表 在单链表的每个结点中再设置一个指向其直接前驱结点的指针域prior即为双向循环链表 双向循环链表的对称性可以用下列等式表示
pp-nextp-next-prior删除设置一个指针p指向待删结点待删结点的前驱指向p的直接后继待删结点的后继指向p的前驱;均由P表示
p-next-priorp-next;
p-next-priorp-prior;
free(p);插入
t-priorp;
t-nextp-next;
p-next-priort;
p-nextt;顺序实现与链接实现的比较
对于按位置查找顺序表时间复杂度为O1单链表是On对于定位运算时间复杂度均为On对于插入删除运算顺序表链表单链表平均时间复杂度均为On单链表每个结点包括数据域和指针域指针域需要占用额外空间顺序表需要预分配存储空间过大浪费过小上溢单链表不用预先分配空间
小试牛刀
设r指向单链表的最后一个结点要在最后一个结点之后插入s所指的结点需要执行的语句序列为
______;
rs;
r-nextNULL;在单链表中指针p所致结点为最后一个结点的条件是_____;带头结点的双向循环链表L为空的条件是_____。在双向循环链表中在指针p所指结点前插入指针s所指的结点需要执行下列语句
s-nextp;
s-priorp-prior;
p-priors;
_______s。从逻辑关系 来看一个数据元素的直接前驱为0个或1个的数据结构只能是______。单链表中增加头结点的目的是为了______。
