请选择 进入手机版 | 继续访问电脑版

数据结构-表

[复制链接]
二次方先生 发表于 2021-1-3 12:12:50 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题




线性表

根本概念

界说(性质相同的数据元素构成的有限序列)

表长,空表,位序,直接前驱,直接后继

根本操纵(12)

InitList(&L); //构造一个空的线性表L
ListEmpty(L); //判断线性表L是否是空表,若是,则返回TRUE,否则返回FALSE
ListLength(L); //返回线性表L的长度
GetElem(L,i,&e) ; //用e返回线性表L的第i个数据元素的值
LocateElem(L,e,compare());//在线性表L中查找第一个和元素e满意compare关系//的元素,若找到则返回其位序;否则返回0
PriorElem(L,e, &pre_e); //用pre_e返回线性表L中元素e的直接前驱
NextElem(L, e, &next_e); //用next_e返回线性表L中元素e的直接后继
ListInsert(&L,i,e) ; //将数据元素e插入到线性表L的第i个数据元素之前
ListDelete(&L,i,&e); //删除线性表L的第i个数据元素,并将其值用e返回
ListTraverse(L,visit()); //依次对线性表L中的每个元素调用visit举行访问
ClearList(&L); //重置线性表L为空表
DestroyList(&L); //销毁线性表L,大概的话释放其空间
存储布局

顺序表

用一组地点一连的存储单元依次存储线性表的数据元素。用顺序存储布局体现的线性表又称为顺序表。


  • 存储范例界说
  1.   #define LIST_INIT_SIZE 100 //顺序表存储空间的初始分配量  #define LISTINCREMENT 10  //顺序表存储空间的分配增量  typedef struct  {     ElemType *elem;  //存储空间的基地点       int length;    //顺序表的当前长度       int listsize;   //数组存储空间的长度  }SqList;
复制代码


  • 特点

    • 逻辑上相邻的数据元素在物理位置上也相邻
    • 随机存取

  • 根本操纵

    • 初始化顺序表

  1.           Status InitSqList(SqList& L) //顺序表初始化          {            L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));//申请初始分配空间            if (L.elem == NULL) exit(OVERFLOW);//分配失败,返回OVERFLOW            L.length = 0;//初始化表长为零            L.listsize = LIST_INIT_SIZE;//初始化数组存储空间为初始分配空间            return OK;//分配乐成返回OK          }
复制代码
  1. - 销毁顺序表
复制代码
  1.           void DestroySqList(SqList& L)//销毁顺序表          {            if (L.elem != NULL)//如果顺序表存在              free(L.elem);//释放存储空间            L.elem = NULL;//存储空间基址置空          }
复制代码
  1. - 顺序表判空
复制代码
  1.           Status SqListEmpty(SqList L)//顺序表的判空操纵          {            if (L.length == 0)               return TRUE;//表长为零为空表            else               return FALSE;//表长非零不为空          }
复制代码
  1. - 顺序表求表长
复制代码
  1.           int SqListLength(SqList L)//顺序表求表长          {            return L.length;          }
复制代码
  1. - 获取元素
复制代码
  1.           Status GetSqElem(SqList L, int i, ElemType& e)//取第i个元素,用第三个参数e返回           {            if (iL.length)//判断索引是否有效              return ERROR;//无效报错            else            {              e = L.elem[i - 1];//有效则返回元素              return OK;            }          }
复制代码
  1. - 定位操纵
复制代码
  1.           int SqLocateElem(SqList L, ElemType e)//定位元素e,返回元素位序,若元素不存在则返回零          {            int i;            for (i = 1; i next)//从首元节点遍历释放节点空间                    {                      L->next = p->next;//更新头节点指针                      free(p);//释放首元节点                    }                  }
复制代码
  1.         - 单链表取值
复制代码
  1.                   Status GetLinkElem(LinkList L, int i, ElemType& e) //单链表取第i个值,由e返回                  {                    int count;//计数变量                    LinkList p = L;//遍历指针初始为头指针                    for (count = 0; count < i && p != NULL; count++)//计数器置零,遍历到第i个,指针为空异常退出                    {                      p = p->next;                    }                    if (i > count)//判断是否异常退出                      return ERROR;                    else//正常退出返回OK                    {                      e = p->data;                      return OK;                    }                   }
复制代码
  1.         - 单链表定位
复制代码
  1.                   LinkList LinkLocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType))                   //单链表定位操纵,返回第一个满意关系的节点指针,若无满意关系的元素,返回空指针                  {                    LinkList p = L->next;//从首元节点遍历链表                    while (p!=NULL && compare(p->data, e)==FALSE) //直到满意关系或遍历竣事停止遍历                      p = p->next;                    return p;//返回指针                  }
复制代码
  1.         - 单链表插入操纵
复制代码
  1.                   Status LinkListInsert(LinkList& L, int i, ElemType e)//单链表插入操纵                  {                    int count;//计数变量                    LinkList p;//循环指针                    for (count = 0, p = L; count < i - 1 && p != NULL; p = p->next, count++);//定位第i-1个节点                    if (i < 0 || count < i - 1) //判断i取值是否公道                      return ERROR;                    else                    {                      LinkList q;                      q = (LinkList)malloc(sizeof(LNode));//创建待插入节点空间                      q->data = e;                      q->next = p->next;//插入节点指向厥后继                      p->next = q;//毗连其前驱节点                    }                    return OK;                  }
复制代码
  1.         - 单链表删除操纵
复制代码
  1.                   Status LinkListDelete(LinkList& L, int i)                  {                    int count;//计数变量                    LinkList p;//循环指针                    for (count = 0, p = L; count < i - 1 && p != NULL; p = p->next, count++);//定位第i-1个节点                    if (i < 0 || count < i - 1) //判断i取值是否公道                      return ERROR;                    else                    {                      LinkList q = p->next;//指向待删除节点                      p->next = q->next;//前驱节点指针域更新                      free(q);//删除节点                    }                    return OK;                  }
复制代码
  1.         - 遍历单链表
复制代码
  1.                   Status LinkListTraverse(LinkList L,Status(*visit)(ElemType)) //遍历单链表                  {                    LinkList p;                    for (p = L->next; p; p = p->next)                      if (!visit(p->data)) return ERROR;                    return OK;                  }
复制代码
  1. - 应用        - 逆向创建n个元素的单链表
复制代码
  1.                   void CreateList_backward(LinkList &L,int n)                  { //逆向创建n个元素的单链表                     L=( LinkList) malloc(sizeof(LNode));                   L->next=NULL;                   for(i=0; idata);                       p->next=L->next;                      L->next=p;                     }//for                  }// CreateList_backward
复制代码
  1. - 优缺点        - 优点:链表在举行插入和删除操纵时,不再移动大量元素,仅需修改指针;不再需要界说2个常量        - 缺点:元素只能顺序存取;大部门操纵的时间复杂度都为O(n);存储使用率较低(存储元素时要附带存储指针)
复制代码


  • 循环链表

    • 优点:从表中任一结点出发都可找到表中其他结点。
    • 操纵
      和线性链表根本一致,差别在于判空和判表尾条件

      • 判空: L->next==L
      • 表尾:p->next==L
      • 在带头结点的循环链表中设置尾指针可方便某些操纵

        • 查找尾元结点
        • 查找首元结点


    • 应用

      • 两个循环链表归并
        仅设尾指针的循环链表
        p=LA->next;
        LA->next=LB->next->next;
        free(LB->next);
        LB->next=p;
        LA=LB;


  • 双向链表

    • 双向链表C语言形貌

  1.           typedef struct DulNode{            ElemType data;            Struct DulNode *prior;//指向其直接前驱的指针域            Struct DulNode *next; //指向其直接后继的指针域          }DulNode,*DuLinkList;
复制代码
  1. - 操纵  某些操纵算法与线性单链表的操纵相同;  插入、删除等操纵需同时修改两个方向的指针        - 插入
复制代码
  1.                   Status ListInsert_Dul(DuLinklist &L,int i,ElemType e)                  {                    if(!(p=GetElem_DuL(L,i)))                  return ERROR;                  if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))                  return ERROR;                  s->data=e;                  ① s->prior=p->prior;                  ② p->prior->next=s;                  ③ s->next=p;                  ④ p->prior=s;                    return OK;                  }
复制代码
  1.         - 删除
复制代码
  1.                   Status ListDelete_Dul(DuLinklist &L,int i,ElemType &e)                  {                    if(!(p=GetElem_DuL(L,i)))                  return ERROR;                  e=p->data;                  ① p->prior->next=p->next ;                  ② p->next->prior=p->prior;                  ③ free(p);                    return OK;                  }
复制代码
栈和队列



根本概念

栈:限制仅在表的一端举行插入和删除的线性表


  • ADT界说
    ADT Stack {
    数据对象:D={ai| ai  ElemSet, i=1,2,…,n, n0}
    数据关系:R={< ai-1, ai >| ai-1,ai D,i=2,…,n}
    约定an端为栈顶, a1端为栈底
    根本操纵:InitStack(&S); StackEmpty(S);
    StackLength(&S); GetTop(S, &e);
    Push(&S, e); Pop(&S, &e);
    ClearStack(&S);
    StackTraverse(S, visit());
    DestroyStack(&S);
    } ADT Stack
  • 栈顶:允许插入、删除的一端。
  • 栈底:与栈顶相对的另一端。
  • 空栈:表中没有元素的栈
存储布局



  • 顺序栈
    特点:用一组地点一连的存储单元依次存放自栈底到栈顶的数据元素
    栈中元素可动态增删,即栈长是可变的,因此温顺序表一样,用动态分配的一维数组来体现顺序栈

    • 存储布局的界说

  1.           #define STACK_INIT_SIZE 100 //顺序栈存储空间的初始分配量          #define STACKINCREMENT 10  //顺序栈存储空间的分配增量                    typedef struct          {                  SElemType* base; //栈底指针,始终指示存储空间的基址                  SElemType* top; //栈顶指针,指向栈顶元素的下一个位置                  int stacksize;  //数组存储空间的长度          }SqStack;//顺序栈界说
复制代码
  1.         - 栈底指针,始终指示存储空间的基址        - 栈顶指针,指向栈顶元素的下一个位置        - 数组存储空间的长度- 根本操纵        - 构造空栈
复制代码
  1.                   Status InitSqStack(SqStack& S)                  {                           S.base = (SElemType*)malloc((STACK_INIT_SIZE) * sizeof(SElemType));// 栈的一连空间分配                          if (!S.base)                          {                                  exit(OVERFLOW);                          }                          S.top = S.base; //空栈,初始化栈顶指针                          S.stacksize = STACK_INIT_SIZE;                          return OK;                  }//构造一个空栈,该栈由指针S指示
复制代码
  1.         - 销毁栈
复制代码
  1.                   Status DestroySqStack(SqStack& S)                  {                          if (S.base) //栈底指针非空                                  free(S.base);                          S.base = NULL;                          return OK;                  }//销毁栈
复制代码
  1.         - 清空栈
复制代码
  1.                   Status ClearSqStack(SqStack& S)                  {                          S.top = S.base;                          return OK;                  }//清除栈
复制代码
  1.         - 判空
复制代码
  1.                   Status SqStackEmpty(SqStack S)                  {                          return S.top == S.base;                  }//栈的判空操纵
复制代码
  1.         - 求栈长
复制代码
  1.                   int SqStackLength(SqStack S)                  {                          return S.top - S.base;                  }//求栈长
复制代码
  1.         - 取栈顶元素
复制代码
  1.                   Status GetTopSq(SqStack S, SElemType& e)                  {                          if (S.top == S.base) return ERROR;                          e = *(S.top - 1);                          return OK;                  } //用指针e带回栈顶元素
复制代码
  1.         - 入栈
复制代码
  1.                   Status SqPush(SqStack& S, SElemType e)                  {//入栈,插入元素e为新的栈顶元素                          if (S.top - S.base == S.stacksize)//栈满                          {                                  S.base = (SElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));                                  if (!S.base) exit(OVERFLOW);                                  S.top = S.base + S.stacksize;                                  S.stacksize += STACKINCREMENT;                          }//重新分配更大的一连空间                          *S.top++ = e;                          return OK;                  }//Push
复制代码
  1.         - 出栈
复制代码
  1.                   Status SqPop(SqStack& S, SElemType& e)                  {                          if (S.top == S.base) //栈空                                  return ERROR;                          --S.top;                          e = *S.top;                          return OK;                  }//出栈,删除的栈顶元素用指针e指示
复制代码
  1.         - 遍历
复制代码
  1.                   Status SqStackTraverse(SqStack S, Status(*visit)(SElemType))                  {//从栈底到栈顶依次对栈S中的每个数据元素调用visit                   //指向的函数举行访问                          SElemType* p;                          for (p = S.base; p < S.top; p++)                                  if (!visit(*p)) return ERROR;                          return OK;                  }// 栈的遍历
复制代码


  • 链栈

    • 链栈范例界说

  1.           typedef struct SNode{            SElemType data;   //数据域            struct SNode *next; //指针域          }SNode,*LinkStack;
复制代码
  1.         - 由于栈顶的位置特殊,所以链栈的头指针指向栈顶元素所在结点        - 注意:不必设头结点- 根本操纵        - 链栈入栈
复制代码
  1.                   Status Push(LinkStack &S, SElemType e)                  {//插入e到栈S中使之成为新的栈顶元素                   p=( LinkStack)malloc(sizeof(SNode));                     if(!p)                      exit(OVERFLOW);                   p->data=e;                      p->next=S;                     S=p;                     return OK;                  }//Push
复制代码
  1.         - 链栈出栈
复制代码
  1.                   Status Pop(LinkStack &S, SElemType &e)                  {//若栈不空则出栈,删除的栈顶元素用e指示                     if(!S)                      return ERROR; //栈空                    p=S;                     S=S->next;                    e=p->data;                    free(p);                    return OK;                  }//Pop
复制代码
栈的应用



  • 数制转换
  • 括号匹配的查验
  • 迷宫求解
  1.   Typedef struct { //栈的元素范例界说     int ord; //通道块在路径上的“序号”     PosTpye seat ; //通道块在迷宫中的“坐标位置”     int di;  //以后通道块走向下一通道块的“方向”  }SElemType;        Status MazePath(MazeType maze, PosType start, PosType end){     InitStack(s); curpos=start; //设定当前位置为入口位置     curstep =1;     do{       if(Pass(curpos)) { //当前位置可通        FootPrint(curpos);  //留下足迹        e=(curstep, curpos, 1);        push(s,e);      //加入路径        if(curpos==end) return(TRUE); //到达终点        curpos= NextPos(curpos, 1);         //下一位置是当前位置的东邻        curstep++;  //探索下一步      }//if      else { //当前位置不能通过        if (!StackEmpty(S)) {    Pop(S,e);  while(e.di==4 && !StackEmpty(s)){    MarkPrint(e.seat); Pop(s,e);   //留下不能//通过的标志,并退回一步    }//while    if (e.di=0}
  2. 数据关系:R={< ai-1, ai > | ai-1, ai D, i=2,3,…,n}
  3. 约定a1端为队头,an端为队尾
  4. 根本操纵:InitQueue(&Q); QueueEmpty(Q);
  5. QueueLength(Q); GetHead(Q, &e);
  6. EnQueue(&Q, e); DeQueue(&Q, &e);
  7. ClearQueue(&Q);
  8. QueueTraverse(Q, Visit());
  9. DestroyQueue(&Q);
  10. }ADT Queue</p>  队头:允许删除的一端
  11.   队尾:允许插入的一端
  12.   空队列:没有元素的队列
  13.   双端队列:限定插入和删除操纵在表两端举行的线性表
  14.   输出受限队列:一端允许插入和删除,另一端只允许插入。
  15.   输入受限队列:一端允许插入和删除,另一端只允许删除。
  16. </ul> [size=4]存储布局[/size]
  17. [list]
  18. [*] 链队列
  19. 使用二个指针分别记录队头和队尾的当前位置
  20. 设立一个头结点,并令头指针指向头结点,头结点的指针域指向队头元素所在的结点
  21. 链队列的判空条件:头指针和尾指针均指向头结点
  22. [list]
  23. [*]链队列范例界说
  24. [/list]
  25. [/list] [code]          typedef struct QNode{           QElemType data;           struct QNode *next;          }QNode,*QueuePtr;          typedef struct {           QueuePtr front; //头指针           QueuePtr rear;  //尾指针          }LinkQueue;
复制代码
  1. - 根本操纵        - 链队列入队
复制代码
  1.                   Status EnQueue(LinkQueue &Q, ElemType e)                  {                    p=(QueuePtr)malloc(sizeof(QNode));                     if(!p) exit(OVERFLOW);                   p->data=e; p->next=NULL;                     Q.rear->next=p;                     Q.rear=p;  //尾指针指向新的尾结点                   return OK;                  }// EnQueue
复制代码
  1.         - 链队列入出队
复制代码
  1.                   Status DeQueue(LinkQueue &Q, ElemType &e)                  {                    if(Q.rear == Q.front) return ERROR;                    p=Q.front->next;                     e=p->data;                      Q.front->next=p->next;                      if(Q.rear==p) Q.rear=Q.front;                   //若队头元素是队列中唯一的一个元素, 则删除该结点后//还需要修改尾指针,让它指向头结点                    free(p);                     return OK;                       } // DeQueue
复制代码


  • 顺序队列

    • 平凡顺序队列
      用一组地点一连的存储单元依次存储从队头到队尾的数据元素。

      • 顺序队列范例界说


  1.                   #define MAXQSIZE 100                  typedef struct {                    QElemType *base; //存储空间基地点                    int front;//队头指针,指向队头元素                    int rear;//队尾指针,指向队尾元素的下一个位置                  }SqQueue;
复制代码
  1.         - 假上溢现象- 循环队列        - 存储布局界说                - 少用一个元素空间,约定队列头指针在队尾指针下一个位置为队列满
复制代码
  1.                           #define MAXQSIZE 100                          typedef int QElemType;                          typedef struct {                                  QElemType* base; //存储空间基地点                                  int front;//队头指针,指向队头元素                                  int rear;//队尾指针,指向队尾元素的下一个位置                          }SqQueue;
复制代码
  1.                 - 另设标志位区别队列空、满
复制代码
  1.                           typedef struct {                            ElemType *base;                            int front;                            int rear;                            int tag;                          }SqQueue;
复制代码
  1.         - 根本操纵                - 初始化队列
复制代码
  1.                           Status InitSqQueue(SqQueue& Q)//初始化队列                          {                                  Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));                                  if (Q.base == NULL)                                          exit(OVERFLOW);                                  Q.front = Q.rear = 0;//队头队尾指针都指向0                                  return OK;                          }
复制代码
  1.                 - 求队长
复制代码
  1.                           int SqQueueLength(SqQueue Q)//求队长                          {                                  return(Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;                          }
复制代码
  1.                 - 进队
复制代码
  1.                           Status EnSqQueue(SqQueue& Q, QElemType e)//进队操纵                          {                                  if ((Q.rear + 1) % MAXQSIZE == Q.front) //队列满的判断条件(防止队满和队空无法区分,留下一个位置不消                                          return ERROR; //队满直接报错,不再申请更大的内存                                  else                                  {                                          Q.base[Q.rear] = e;                                          Q.rear = (Q.rear + 1) % MAXQSIZE;//队尾指针后移,%MAXQSIZE使下标首尾相接                                          return OK;                                  }                          }
复制代码
  1.                 - 出队
复制代码
  1.                           Status DeQueue(SqQueue& Q, QElemType& e)//出队操纵                          {                                  if (Q.front == Q.rear) //队空的判断条件                                          return ERROR; //队空报错                                  else                                  {                                          e = Q.base[Q.front];                                          Q.front = (Q.front + 1) % MAXQSIZE;                                          return OK;                                  }                          }
复制代码
  1.                 - 判空
复制代码
  1.                           Status SqQueueEmpty(SqQueue Q)//循环队列的判空操纵                          {                                  if (Q.rear == Q.front)                                          return TRUE;                                  else                                          return FALSE;                          }
复制代码
  1.                 - 取队头元素
复制代码
  1.                           Status GetSqHead(SqQueue Q, QElemType& e)//取队头元素                          {                                  if (Q.rear == Q.front)                                          return ERROR;                                  else                                  {                                          e = Q.base[Q.front];                                          return TRUE;                                  }                          }
复制代码
  1.                 - 清空队列
复制代码
  1.                           Status ClearSqQueue(SqQueue& Q)//清空队列                          {                                  Q.rear = Q.front;                                  return OK;                          }
复制代码
  1.                 - 销毁队列
复制代码
  1.                           Status DestroySqQueue(SqQueue& Q)//销毁队列                          {                                  free(Q.base);                                  Q.front = Q.rear = 0;                                  return OK;                          }
复制代码
  1.                 - 队列的遍历
复制代码
  1.                           Status SqQueueTraverse(SqQueue Q, Status (*visit)(QElemType))                          {                                  int i;                          for (i = Q.front; i != Q.rear; i = (i + 1) % MAXQSIZE)                          {visit(Q.base[i]);}                                  return OK;                          }
复制代码


根本概念及术语

概念



  • 串:由零个或多个字符组成的有限序列。记为:s= ‘a1 a2…an’ (n>=0)
  • 串名: s
  • 串值: a1a2a3……an
  • 串长: n
  • 空串:串长为0的串。用Φ体现
  • 子串:串中任意个一连的字符组成的子序列

    • 串是其自身的子串
    • 空串是任意串的子串

  • 主串:包罗子串的串
  • 字符在串中的位置:字符在串中的序号
  • 子串在主串中的位置:子串的第1个字符在主串中的位置
  • 空格串:由一个或多个空格组成的串,其长度为空格个数
  • 串相等:两个串长度相等且各个对应位置的字符也相等
ADT

ADT String {
数据对象:D={ai| ai CharacterSet, i=1,2,…,n, n0}
数据关系:R1={< ai-1 ,ai >| ai-1 , ai  D,i=2,3,…,n}
根本操纵:
StrAssign(&T, chars); StrCopy(&T,S);
StrEmpty(S); StrCompare(S,T);
StrLength(S); ClearString(&S);
Concat(&T,S1,S2); Substring(&Sub, S, pos,len);
Index(S,T,pos); Replace(&S,T,V);
StrInsert(&S, pos, T); StrDelete(&S, pos, len);
DestroyString(&S);
}ADT String;
根本操纵

最小操纵子集



  • 串赋值StrAssign
  • 串比力StrCompare
  • 求串长StrLength
  • 串联接Concat
  • 求子串SubString
其他操纵



  • 串拷贝StrCopy
  • 串判空StrEmpty
  • 定位串Index
  • 串替换Replace
  • 串插入StrInsert
  • 串删除StrDelete
  • 串清空ClearString
  • 销毁串DestroyStr
串的体现方法

顺序存储布局



  • 定长存储布局

    • 特点:用长度固定的一连单元依次存储串值的字符序列
    • 以下标为0的数组分量存放实际串长——PASCAL
    • 串值后加一个不计入串长的竣事标志字符——C、C++中用‘\0’作串的竣事标志

  • 堆分配存储布局

    • 特点:接纳动态字符数组存放串值,此时不必为数组预界说巨细,以串长动态分配数组空间
    • 数据范例界说

  1.           typedef struct {            char *ch;             int length;            }HString;
复制代码
链式存储布局



  • 块链布局

    • 数据范例界说

  1.           #define CHUNKSIZE 80 // 可由用户界说的块巨细           typedef struct Chunk { // 结点布局            char ch[CUNKSIZE];            struct Chunk *next;           } Chunk;           typedef struct { // 串的链表布局             Chunk *head, *tail; //串的头和尾指针,便于联结操纵             int  curlen;      // 串的当前长度           } LString;
复制代码
串的应用

文本编辑



  • 实质:修改字符数据的形式或格式
  • 根本操纵:输入、查找、修改、删除、输出
数组和广义表

数组

数组的界说



  • ADT
    ADT Array {
    数据对象:ji=0, …, bi – 1, i = 1, 2, …, n,
    D={ | ∈ElemSet }
    数据关系:R = {R1, R2, …, Rn}
    Ri={ |0 ≤ jk ≤ bk–1, 1 ≤ k ≤n且
    k!=i, 0 ≤ ji ≤ bi–2, ∈D, i=1,2,…,n}
    根本操纵:
    InitArray(&A, n, bound1, …, boundn)
    DestroyArray(&A)
    Value(A, &e, index1, …, indexn)
    Assign(&A, e, index1, …, indexn)
    }ADT Array
  • n维数组是线性表的扩展

    • 当n=1,n维数组退化成顺序表
    • 当n>1,n维数组可看成表中数据元素是n-1维数组的线性表

数组的顺序体现

因为数组一般不做插入/删除操纵,所以用顺序布局体现数组是很自然的。


  • 特点:用一组地点一连的存储单元按照某种规则存放数组中的数据元素。
  • 2种顺序(顺序存储方式)

    • 以行序为主(低下标优先法)
    • 以列序为主(高下标优先法)

  • 元素地点的盘算

    • 要素

      • ①数组的起始地点(即基地点)
      • ②数组维数和各维的长度;
      • ③数组中每个元素所占的存储单元

    • 盘算方法

      • 二维

        • 行主序:LOC(i,j) = LOC(0,0) + ( b2*i + j ) * L
        • 列主序:LOC(i,j) = LOC(0,0) + ( b1*j + i ) * L
        • 二维数组元素地点的通式

          • 行优先存储时的地点公式为:

            • LOC(aij)=LOC(ac1,c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L

          • 列优先存储的通式为:

            • LOC(aij)=LOC(ac1,c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L



      • 多维

        • 设各维长度分别为b1, b2, b3, …, bn,每个元素占L个存储单元, 起始地点是LOC(0,0,…,0)
        • LOC (j1,j2,…,jn ) = LOC(0,0,…,0) + (b2b3bn * j1+ b3b4*…bn * j2+ ……+ bnjn-1 + jn ) * L


    • 随机存储布局
      数组元素的存储位置是其下标的线性函数,由于盘算各个元素存储位置的时间相等,所以存储数组中任一元素的时间也相等,具有这一特点的存储布局为随机存储布局。

  • 实现
  1.   #define MAX_ARRAY_DIM 8  typedef struct {          ElemType        *base;                //存储空间基址          int        dim;                      //数组维数          int        *bounds;                //数组维界基址          int        *constants;              //数组映象函数常量{Ci}基址  } Array;
复制代码
矩阵的压缩存储

压缩存储:为多个值相同的元素只分配一个存储空间,对零元素不分配空间。


  • 特殊矩阵:值相同的元素或零元素在矩阵中分布有一定规律。如三角矩阵、对角矩阵。

    • 对称矩阵
      n阶矩阵A中元素满意性质a[j]=a[j] (1 ≤i, j≤ n)

      • 压缩存储
        为每一对对称元素分配 个存储空间. n2 n(n+1)/2
        用行主序的下(上)三角阵来存储对称矩阵的元素。
        sa[k](0 ≤ k ≤ n(n+1)/2-1) 为对称矩阵的压缩存储布局

    • 上(下)三角阵
      下(上)三角(不含对角线)元素为常数c或0的n阶矩阵

      • 压缩存储
        存储上(下)三角中的元素和常数c
        用行主序存储上(下)三角阵的元素
        sak 为上(下)三角阵的压缩存储布局

    • 对角矩阵
      所有非零元素都会合在以主对角线为中心的带状区域。其他元素为0。

      • 压缩存储
        用行主序存储带状区域的非0元素


  • 稀疏矩阵:值相同的元素或零元素在矩阵中分布没有一定规律。

    • 稀疏因子
      设m行n列的矩阵含t个非零元素,界说δ=t/(m*n)为稀疏因子,则  0.05 的矩阵为稀疏矩阵。
    • 稀疏矩阵的压缩存储
    • 体现

      • 三元组( i,j,aij )

        • 三元组的C语言形貌



  1.                           typedef struct {                             int i,j;                             ElemType e;                          }Triple;
复制代码
  1.                 - 三元组顺序表的C语言形貌
复制代码
  1.                           #define MAXSIZE 1250                           typedef struct{                             Triple data[MAXSIZE+1]; //data[0]未用                             int mu,nu,tu;                          }TSMatrix;
复制代码
  1.         - 行逻辑链接的顺序表          需求:随机存取任意一行的非0元          方法:记着矩阵每一行第一个非0元在三元组顺序表中的位置          设数组rpos[1..n]:矩阵中每行第一个非零元素的起始位置          rpos[1]=1;             rpos[row]=rpos[row-1]+第row-1行的非零元素个数          第i行所有非0元在data中的位置:rpos[i]..rpos[i+1]-1          行逻辑链接顺序表:在稀疏矩阵的三元组顺序表中设置指示行信息的辅助数组rpos          typedef struct{           Triple data[MAXSIZE+1];           int rpos[MAXRC+1];//各行第1个非零元位置表,rpos[0]未用           int mu,nu,tu;          }RLSMatrix;        - 十字链表- 转置        - 稀疏矩阵转置方法一
复制代码
[code]                  Status TransposeSMatrix(TSMatrix M,TSMatrix &T)                  {  T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;                     if(T.tu)                     {  q=1;                       for(col=1;col
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )