Array

发表于 | 更新于: | 分类于 | 热度: ℃
字数统计: 1,975 | 阅读时长 ≈ 9

线性表

类型定义

简言之，一个线性表是n个数据元素的有限序列。

在复杂的线性表中，一个数据元素可由若干个数据项(item)组成。在这种情况下，常把数据元素称为记录(record)，含有大量记录的线性表又称为文件（file）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ADT List{
  //数据对象
  D = {a1|a2 belong to ElemSet, i=1,2,....,n, n>0}
  //数据关系
  R1 = {<ai-1,ai>|ai-1.ai belong to D,i = 1,2...n}
  //基本操作
  InitList(&L)
    //构造一个空的线性表Ｌ
  DestoryList(&L)
    //销毁线性表Ｌ
  ClearList(&L)
    //将Ｌ重置为空表
  ListEmpty(L)
    //若L为空表，返回True,否则False
  ListLength(L)
    //返回L中数据元素个数
  GetElem(L,i,&e)
    //用e返回L中第i个数据元素的值
  ListInsert(&L,i,e)
    //在Ｌ中第i个位置之前插入新的数据元素e，Ｌ的长度加1。
}

例2.1　LA和LB中的数据元素按值非递减有序排列，要求将LA和LB归并为新的线性表LC，且LC中的数据元素仍然按值非递减有序排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// LA = (3,5,8,11)  LB = (2,6,8,9,11,15,20)
// LC =(2,3,5,6,8,8,9,11,11,15,20)
void MergeList(List La,List Lb,List &Lc){
  InitList(Lc);
  i = j = 1; k=0;
  La_len = ListLength(La); Lb_len = ListLength(Lb);
  while((i<=La_len)&&(j<=Lb_len)){
    GetElem(La,i,ai); GetElem(Lb,j,bj);
    if(ai<=bj){ListInsert(Lc,++k,ai);++i;}
    else{ListInsert(Lc,++k,bj);++j;}
  }
  while(i<=La_len){
    GetElem(La,i,ai);ListInsert(Lc,++k,ai);
  }
  while(j<=Lb_len){
     GetElem(Lb,i,bj);ListInsert(Lc,++k,bj);
  }
}

线性表的顺序表示和实现

线性表的顺序表示指的是用一组地址连续的存储单元以此存储线性表的数据元素。

一般来说，线性表的第$i$个数据元素$a_j$的存储位置为 $LOC(a_i) = LOC(a_1)+(i-1) \times l$

线性表的这种机内表示称作线性表的顺序存储结构或顺序映像(sequential mapping)。

Ｃ语言中可用动态分配的一维数组：

1
2
3
4
5
6
7
8
// －－－－－线性表的动态分配顺序存储结构－－－－－
#define LIST_INIT_SIZE   100  // 线性表存储空间的初始分配量
#define LISTINCREMENT    10　 // 线性表存储空间的分配增量
typedef struct{
  ElemType *elem;       // 存储空间基址
  int      length;      // 当前长度
  int      listsize;    // 当前分配的存储容量
}SqList;

线性表插入和删除操作：

insert

一般情况下，把第$i(1\le i\le n)$个元素之前插入一个元素时，需要将第$n$至第$i$（共$n-i+1$）个元素向后移动一个位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Status ListInsert_Sq(SqList &L,int i,ElemType e){
  if(i<1||i>L.length+1) return ERROR;
  if(L.length>=L.listsize){       //当前存储空间已满，增加分配
    newbase = (ElemType *)realloc(L.elem,               (L.listsize+LISTINCREMENT)*sizeof(ElemType));
    if(!newbase)exit(OVERFLOW);   //存储分配失败
    L.elem = newbase;             //新基址  
    L.listsize+= LISTINCREMENT;   //增加爱存储容量
  }
  q = &(L.elem[i-1]);            //q为插入位置
  for(p = &(L.elem[L.length-1]);p>=1;--p) *(p+1) = *(p);
                                 //插入位置及之后的元素右移
  *q = e;　　　　　　　　　　　　　　//插入e
  ++L.length;                    //表长增１
  return OK;
}                               //时间复杂度Ｏ(n)

线性表删除操作

1
2
3
4
5
6
7
8
9
Status ListDelete_Sq(SqList &L,int i,ElemType e){
  if(i<1||i>L.length+1) return ERROR;
  p = &(L.elem[i-1]);         //p被删除元素的位置
  e = *p;                     //被删除元素的值赋给e
  q = L.elem + L.length-1;    //表尾元素的位置
  for(++p;p<=q;++p) *(p-1) = *p;  //被删除元素之后的元素左移  
  --L.length;                 //表长减1  
  return Ok;
}                            //时间复杂度Ｏ(n)

案例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include "stdio.h"
#define MAXSIZE 100
typedef struct
{
    int NO;
    int score;
}ElemType;
typedef struct 
{
    ElemType elem[MAXSIZE];
    int length;
}SqList;
//初始化
void InitList(SqList *pL)
{
    pL->length =0;
}
//插入
void InsertList(SqList *pL,ElemType e,int i)
{
    if(pL->length >MAXSIZE)
        return;
    pL->elem [i]=e;
    pL->length ++;
}
//排序
void  SortScore(SqList *pL)
{
    for(int i=0;i<pL->length ;i++)
        for(int j=i+1;j<pL->length ;j++)
        {
            if(pL->elem [i].score<pL->elem [j].score )
            {
                ElemType temp=pL->elem [i];
                pL->elem [i]=pL->elem [j];
                pL->elem [j]=temp;
            }
        }
}
void Merge(SqList *pL,SqList *pS,SqList *T)
{
    int i=0,j=0,k=0;
    while(i<pL->length &&j<pS->length )
    {
        if(pL->elem [i].score >pS->elem [j].score )
            T->elem [k++]=pL->elem [i++];
            
        else
    
            T->elem [k++]=pS->elem [j++];
    
    }
    while(i<pL->length )
        T->elem [k ++]=pL->elem [i++ ];
    
    while(j<pS->length )
        T->elem [k ++]=pS->elem [j ++];    
}
//输出
void Printf(SqList *pL)
{
    for(int i=0;i<pL->length ;i++)
        printf("(%2d,%2d)\n",pL->elem [i].NO ,pL->elem [i].score );
}
void main()
{
    SqList L,S,T;
    ElemType e;
    InitList(&L);
    e.NO =5; e.score =60;
    InsertList(&L,e,0);
    e.NO =6; e.score =80;
    InsertList(&L,e,1);
    e.NO =7; e.score =76;
    InsertList(&L,e,2);
    e.NO =8; e.score =50;
    InsertList(&L,e,3);
    printf("顺序表L:\n");
    Printf(&L);
    printf("\n按照成绩大小排序后的顺序表L：\n");
    SortScore(&L);
    Printf(&L);
    InitList(&S);
    e.NO =10; e.score =70;
    InsertList(&S,e,0);
    e.NO =20; e.score =85;
    InsertList(&S,e,1);
    e.NO =30; e.score =75;
    InsertList(&S,e,2);
    e.NO =40; e.score =90;
    InsertList(&S,e,3);
    printf("\n顺序表S:\n");
    Printf(&S);
    printf("\n按照成绩大小排序后的顺序表S：\n");
    SortScore(&S);
    Printf(&S);
    printf("\n\n");
    InitList(&T);
    T.length =L.length +S.length ;
    Merge(&L,&S,&T);
    Printf(&T);
}

线性表的顺序存储结构特点：逻辑关系上相邻的两个单元在物理位置上也相邻。缺点：在作插入或删除操作时，需要移动大量元素。

线性表的链式表现和实现

线性表链式存储结构特点：用一组任意的存储单元(连续或不连续)存储线性表的数据元素 。

如何表示数据元素$a_i$与其直接后继数据元素$a_{i+1}$之间关系:结点｛本身信息+直接后继的存储位置｝

结点包含两个域：数据域＋指针域　　n个结点链结成一个链表。

list_operate

线性单链表：(ZHAO, QIAN, SUN, LI, ZHOU, WU, ZHENG, WANG)

linear_list

1
2
3
4
5
//－－－－－线性表的单链存存储结构－－－－－－
typedef struct LNode{
  ElemType        data;
  struct LNode   *next;
}LNode, *LinkList;

$p->data = a_i$, 则$p->next->data = a_{i+1}$。

GetElem在单链表中的实现

1
2
3
4
5
6
7
8
9
10
11
Status GetElem_L(LinkList L,int i,ElemType &e){
  //L为带头结点的单链表的头指针。
  //当第i个元素存在时，其值赋给e并返回OK，否则返回error。
  p = L->next; j = 1;
  while(p&&j<i){
    p = p->next;++j;
  }
  if(!p||j>i) return ERROR;
  e = p->data;         //取第i个元素
  return OK;
}

单链表插入操作

1
2
3
4
5
6
7
8
9
10
Status ListInsert_L(LinkList &L,int i,ElemType e){
  //在带头结点的单链表Ｌ中第i个位置之前插入元素e
  p = L; j = 0;
  while(p&&j<i-1){p = p->next;++j;}  //寻找第i－１个结点
  if(!p||j>i) return ERROR;
  s = (LinkList)malloc(sizeof (LNode)); //生成新结点
  s->data = e; s->next = p->next;　　　　//插入Ｌ中
  p->next = s;
  return OK;
}　                                 //O(n)

单链表删除操作

1
2
3
4
5
6
7
8
9
10
11
Status ListDelete_L(LinkList &L,int i,ElemType &e){
  //在带头结点的单链表Ｌ中删除第i个元素，并由e返回其值
  p = L;j=0;
  while(p->next&&j<i-1){       //寻找第i个结点，并令p指向其前趋
    p = p->next;++j;
  }
  if(!(p->next)||j>i) return ERROR;
  q = p->next; p->next = q->next;   //删除并释放结点
  e = q->data; free(q);
  return OK;
}                                  //O(n)

两个有序链表合并为一个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
  pa = La->next; pb = Lb->next;
  Lc = pc = La;       //用La的头结点作为Lc的头结点
  while(pa&&pb){
    if(pa->data <= pb->data){
      pc->next = pa; pc = pa; pa= pa->next;
    } 
    else{pa-next = pb; pc=pb; pb = pb->next;}
  }
  pc->next = pa?pa:pb; //插入剩余段
  free(Lb);
}

双向链表：结点有两个指针域，其一指向直接后继，另一指向直接前趋

1
2
3
4
5
6
//－－－－－线性表的双向链表存储结构－－－－－
typedef struct DuLNode{
  ElemType        data;
  struct DuLNode   *prior;
  struct DuLNode   *next;
}

dulnode

结构特性：$d->next->prior = d->prior->next = d$>

双向链表插入操作

1
2
3
4
5
6
7
8
9
10
11
Status ListInsert_DuL(DuLinkList &L,int i,ElemType e){
  //在带头结点的双链循环表Ｌ中第i个位置之前插入元素e
  if(!(p = GetElemP_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
2
3
4
5
6
7
8
9
10
Status ListDElete_DuL(DuLinkList &L,int i,ElemType e){
  //删除带头结点的双链循环表Ｌ第i个元素
  if(!(p = GetElemP_Dul(L,i)))   //在Ｌ中确定插入位置
    return ERROR;
 e = p->data;
  p->prior->next = p->next;
  p->next->prior = p->prior;
  free(p);
  return OK;
}
-------------本文结束感谢您的阅读-------------
很有帮助，打赏感谢！
分享到： QQ好友 微信 新浪微博 有道云笔记 豆瓣 收藏夹 复制网址 一键分享 更多
0%