• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

数据结构(C语言版)-第2章线性表

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

 

#define  MAXSIZE 100     //最大长度
typedef  struct {
  ElemType  *elem;     //指向数据元素的基地址
  int  length;          //线性表的当前长度                                                      
 }SqList;

例子

#define MAXSIZE 10000    //图书表可能达到的最大长度 
typedef struct            //图书信息定义
{ 
   char no[20];            //图书ISBN
   char name[50];        //图书名字
   float price;             //图书价格
}Book; 
typedef struct
{ 
   Book *elem;    //存储空间的基地址 
   int length;        //图书表中当前图书个数 
}SqList;        //图书表的顺序存储结构类型为SqList

1.  初始化    2.  取值   3.  查找    4.  插入   5.  删除

初始化线性表L (参数用引用)

Status InitList_Sq(SqList &L){    //构造一个空的顺序表L
    L.elem=new ElemType[MAXSIZE];   //为顺序表分配空间
    if(!L.elem) exit(OVERFLOW);       //存储分配失败
    L.length=0;                      //空表长度为0
    return OK;
}

初始化线性表L (参数用指针)

Status InitList_Sq(SqList *L){    //构造一个空的顺序表L
    L-> elem=new ElemType[MAXSIZE];   //为顺序表分配空间
    if(! L-> elem) exit(OVERFLOW);       //存储分配失败
    L-> length=0;                      //空表长度为0
    return OK;
}

销毁线性表L

void DestroyList(SqList &L)
{
  if (L.elem) delete[]L.elem;    //释放存储空间
}

清空线性表L

void ClearList(SqList &L) 
{
   L.length=0;                //将线性表的长度置为0
}

判断线性表L是否为空

int IsEmpty(SqList L)
{
  if (L.length==0) return 1;      
   else return 0;
}

获取线性表L中的某个(第i 个)数据元素的内容

int GetElem(SqList L,int i,ElemType &e)
{
  if (i<1||i>L.length) return ERROR;   
   //判断i值是否合理,若不合理,返回ERROR
  e=L.elem[i-1];   //第i-1的单元存储着第i个数据
  return OK;
}

在线性表L中查找值为e的数据元素

int LocateELem(SqList L,ElemType e)
{
  for (i=0;i< L.length;i++)
      if (L.elem[i]==e) return i+1; //返回是第几个元素               
  return 0;
}

在线性表L中第i个数据元素之前插入数据元素e

Status ListInsert_Sq(SqList &L,int i ,ElemType e){
   if(i<1 || i>L.length+1) return ERROR;             //i值不合法
   if(L.length==MAXSIZE) return ERROR;    //当前存储空间已满     
   for(j=L.length-1;j>=i-1;j--) 
       L.elem[j+1]=L.elem[j];    //插入位置及之后的元素后移
    L.elem[i-1]=e;                     //将新元素e放入第i个位置
  ++L.length;                 //表长增1
  return OK;
}
//见下图

(1)判断插入位置i 是否合法。
(2)判断顺序表的存储空间是否已满。     
(3)将第n至第i 位的元素依次向后移动一个位置,空出第i个位置。
(4)将要插入的新元素e放入第i个位置。
(5)表长加1,插入成功返回OK。

若插入在尾结点之后,则根本无需移动(特别快);若插入在首结点之前,则表中元素全部后移(特别慢);若要考虑在各种位置插入(共n+1种可能)的平均移动次数,该如何计算?

 将线性表L中第i个数据元素删除

Status ListDelete_Sq(SqList &L,int i){
   if((i<1)||(i>L.length)) return ERROR;     //i值不合法
   for (j=i;j<=L.length-1;j++)                   
    L.elem[j-1]=L.elem[j];       //被删除元素之后的元素前移  
   --L.length;                         //表长减1
  return OK;
}

(1)判断删除位置i 是否合法(合法值为1≤i≤n)。
(2)将欲删除的元素保留在e中。     
(3)将第i+1至第n 位的元素依次向前移动一个位置。
(4)表长减1,删除成功返回OK。

若删除尾结点,则根本无需移动(特别快);若删除首结点,则表中n-1个元素全部前移(特别慢);若要考虑在各种位置删除(共n种可能)的平均移动次数,该如何计算?

查找、插入、删除算法的平均时间复杂度为O(n),顺序表的空间复杂度S(n)=O(1)(没有占用辅助空间)

2.5 线性表的链式表示和实现

链式存储结构:结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻。线性表的链式表示又称为非顺序映像或链式映像。

各结点由两个域组成:
数据域:存储元素数值数据
指针域:存储直接后继结点的存储位置

结点:数据元素的存储映像。由数据域和指针域两部分组成

单链表、双链表、循环链表:
结点只有一个指针域的链表,称为单链表或线性链表
有两个指针域的链表,称为双链表
首尾相接的链表称为循环链表

循环链表:

 

有头结点时,当头结点的指针域为空时表示空表

头结点的数据域可以为空,也可存放线性表长度等附加信息,但此结点不能计入链表长度值。

2.5.1 单链表的定义和实现

单链表是由表头唯一确定,因此单链表可以用头指针的名字来命名
若头指针名是L,则把链表称为表L

typedef struct LNode{
     ElemType   data;       //数据域
     struct LNode  *next;   //指针域
}LNode,*LinkList;   // *LinkList为Lnode类型的指针

若p->data=ai, 则p->next->data=ai+1

2.5.2 单链表基本操作的实现

1.  初始化   2.  取值      3.  查找       4.  插入       5.  删除

1.初始化(构造一个空表 )
【算法步骤】
(1)生成新结点作头结点,用头指针L指向头结点。
(2)头结点的指针域置空。

Status InitList_L(LinkList &L){ 
   L=new LNode;                        
   L->next=NULL;     
   return OK; 
}

销毁

Status DestroyList_L(LinkList &L){
    LinkList p;
       while(L)
        {
            p=L;  
            L=L->next;
            delete p;  
        }
     return OK;
}

清空(链表仍在)

Status ClearList(LinkList & L){
  // 将L重置为空表 
   LinkList p,q;
   p=L->next;   //p指向第一个结点
   while(p)       //没到表尾 
      {  q=p->next; delete p;     p=q;   }
   L->next=NULL;   //头结点指针域为空 
   return OK;
}

求表长

int  ListLength_L(LinkList L){
//返回L中数据元素个数
    LinkList p;
    p=L->next;  //p指向第一个结点
     i=0;             
     while(p){//遍历单链表,统计结点数
           i++;
          p=p->next;    } 
    return i;                             
}

判断表是否为空

int ListEmpty(LinkList L){
//若L为空表,则返回1,否则返回0
   if(L->next)   //非空
     return 0;
 
else
     return 1;
}

2. 取值(根据位置i获取相应位置数据元素的内容)

链表的查找:要从链表的头指针出发,顺着链域next逐个结点往下搜索,直至搜索到第i个结点为止。因此,链表不是随机存取结构

//获取线性表L中的某个数据元素的内容
Status GetElem_L(LinkList L,int i,ElemType &e){ 
    p=L->next;j=1; //初始化
     while(p&&j<i){    //向后扫描,直到p指向第i个元素或p为空 
       p=p->next; ++j; 
     } 
     if(!p || j>i)return ERROR; //第i个元素不存在 
     e=p->data; //取第i个元素 
     return OK; 
}//GetElem_L
//在线性表L中查找值为e的数据元素
int LocateELem_L (LinkList L,Elemtype e) {
//返回L中值为e的数据元素的位置序号,查找失败返回0 
  p=L->next; j=1;
  while(p &&p->data!=e)  
        {p=p->next;  j++;}                  
  if(p) return j; 
  else return 0;
}

3. 插入(插在第 i 个结点之前)

//在L中第i个元素之前插入数据元素e 
Status ListInsert_L(LinkList &L,int i,ElemType e){ 
     p=L;j=0; 
      while(p&&j<i−1){p=p->next;++j;}    //寻找第i−1个结点 
      if(!p||j>i−1)return ERROR;    //i大于表长 + 1或者小于1  
      s=new LNode;            //生成新结点s 
      s->data=e;                         //将结点s的数据域置为e 
      s->next=p->next;                     //将结点s插入L中 
      p->next=s; 
      return OK; 
}//ListInsert_L

5. 删除(删除第 i 个结点)

//将线性表L中第i个数据元素删除
 Status ListDelete_L(LinkList &L,int i,ElemType &e){
    p=L;j=0; 
    while(p->next &&j<i-1){//寻找第i个结点,并令p指向其前驱 
        p=p->next; ++j; 
    } 
    if(!(p->next)||j>i-1) return ERROR; //删除位置不合理 
    q=p->next; //临时保存被删结点的地址以备释放 
    p->next=q->next;     //改变删除结点前驱结点的指针域 
    e=q->data;     //保存删除结点的数据域 
    delete q;     //释放删除结点的空间 
 return OK; 
}//ListDelete_L

单链表的建立(前插法)

void CreateList_F(LinkList &L,int n){ 
     L=new LNode; 
      L->next=NULL; //先建立一个带头结点的单链表 
      for(i=n;i>0;--i){ 
        p=new LNode; //生成新结点 
        cin>>p->data; //输入元素值 
        p->next=L->next;L->next=p;     //插入到表头 
     } 
}//CreateList_F

单链表的建立(尾插法)


void CreateList_L(LinkList &L,int n){ 
      //正位序输入n个元素的值,建立带表头结点的单链表L 
      L=new LNode; 
      L->next=NULL;     
      r=L;     //尾指针r指向头结点 
      for(i=0;i<n;++i){ 
        p=new LNode;         //生成新结点 
        cin>>p->data;           //输入元素值 
        p->next=NULL; 
       r->next=p;             //插入到表尾 
        r=p;     //r指向新的尾结点 
      } 
}//CreateList_L

2.5.3 循环链表

 

对循环链表,有时不给出头指针,而给出尾指针可以更方便的找到第一个和最后一个结点

开始结点:rear->next->next
终端结点:rear

循环链表的合并


2.5.4 双向链表

typedef struct DuLNode{
    ElemType   data;              
    struct DuLNode  *prior;  
    struct DuLNode  *next;  
}DuLNode, *DuLinkList


 

双向链表的插入

Status ListInsert_DuL(DuLinkList &L,int i,ElemType e){
   if(!(p=GetElemP_DuL(L,i))) return ERROR;
    s=new DuLNode; 
   s->data=e;
   s->prior=p->prior;  
   p->prior->next=s;
   s->next=p;  
   p->prior=s;
   return OK;
}

双向链表的删除

Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e){
   if(!(p=GetElemP_DuL(L,i)))     return ERROR;
   e=p->data;
   p->prior->next=p->next;
   p->next->prior=p->prior;
   delete p; 
   return OK;
}

总结


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
c++数字与字符串的相互转换发布时间:2022-07-14
下一篇:
用C#调用CMD.exe,执行DOS命令,编码FLV发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap