数据结构不挂科 2 线性表


数据结构不挂科 2 线性表

正文

模块1 线性表的定义

⼩节1 基本概念

线性表的定义

(a1, a2, a3, ... , an−1, an, an+1)

0->1->2->3->4->5->6

ai−1 是 ai的直接前驱元素， ai+1是 ai 的直接后驱元素

是一个有限序列，表中各个元素是相继排列的，且每两个相邻元素之间都有直接前驱和直接后继的逻辑关系。

  • 例题2-1 线性表是具有n个()队有限序列

A.数据表 B.字符 C. 数据元素 D.数据项

线性表的四大特点

1.存在唯一的第一个元素和最后一个元素。

2.除第一个元素外，其他元素有且仅有一个直接前驱。

3.除最后一个元素外，其他元素有且仅有一个直接后继。

4.线性表中的每一个元素都具有相同的数据类型，且不能按子表那样再分割。

color={‘red’,’orange’,’yellow’,’green’,’blue’,’black’} 
score={‘667’,’664’,’659’,’662’,’610’,’632’,’’651}
  • 例题2-2 以下()是一个线性表。

A.由n个实数组成的集合 B.由100个字符组成的序列 C.所有整数组成的序列 D.邻接表

  • 例题2-3 在线性表中，除开始元素外，每个元素()。

A.只有唯一的前驱元素。 B.只有唯一的后继元素。 C.有多个前驱元素。 D.有多个后继元素。

⼩节2 线性表基本操作

1.InitList(&L)

int initList(SqList *L)
{
    L->length = 0;
    return 1;
}

操作结果：构造一个空的线性表L

2.printList(L)

int printList(SqList L)
{
    if (L.length == 0) {
        printf("链表为空\n");
        return 0;
    }
    
    int i;
    for(i = 0; i < L.length; i++)
    {
        printf("data[%d] = %d\n", i, L.data[i]);
    }
    
    printf("\n");
    
    return 1;
}

操纵结果：打印一个顺序表，方便测试操作是否正确

data[0] = 0
data[1] = 1
data[2] = 2
data[3] = 3
data[4] = 4
data[5] = 5
data[6] = 6
data[7] = 7
data[8] = 8
data[9] = 9

3.getlength(L)

int getlength(SqList L)
{
    return L.length;
}

操作结果：获取顺序表的长度

4.createList(&L，int length)

int createList(SqList *L, int length)
{
    srand(time(0));
    int i;
    for(i = 0; i < length; i++) 
    {
        L->data[i] = rand() % 100;
        L->length++;
    }
    
    return 1;
}

操作结果：创建一个顺序表，每个元素的值随机赋值

5.insertList(&L, int pos, ElemType elem)

int insertList(SqList *L, int pos, ElemType elem)
{
    int i;
    if (pos < 1 || pos > L->length) {
        printf("插入的位置有误，无法插入数据\n");
        return 0;
    }
    
    for(i = L->length - 1; i >= pos - 1; i--) 
    {
        L->data[i+1] = L->date[i];
    }
    L->date[pos-1] = elem;
    L->length++;
    
    return 1;
}

操作结果：在指定位置处插入一个新的元素

6.locateElem(L，ElemType e)

int locateElem(SqList L, ElemType e)
{
    int i;
    for(i = 0; i < L.length; i++) 
    {
        if (L.data[i] == e) {
            printf("在pos[%d]位置处，查找到了元素elem:%d\n", i+1, e);
            return 1;
        }
    }
    
    return 0;
}

操作结果：查找在线性表中是否含有指定元素

  • 例题2-4 假设利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A = A U B。这就要求对线性表作如下操作： 扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到LA中去。 只要从线性表LB中依次取得每个数据元素，并依值在线性表LA中进行查访，若不存在，则插入之。

模块2 顺序表

⼩节1 顺序表的定义和特点

顺序表的定义

顺序表结构体的定义

# define MaxSize 100  // 最大空间

typedef struct
{
    ElemType *elem;
    int length;
} Sqlist;

ElemType 元素类型，需要什么类型就写什么类型

*elem 基地址，前面加*号表示取地址的内容

length 表示顺序表的长度

结构体定义后，若想要定义一顺序表L，可以这样写： SqList L

⼩节2 顺序表主要操作的实现

顺序表的插入

// 新元素x插入到表中第i个位置
int insertList(SqList &L, int i, DataType &x)
{
    // 表满的情况
    if (L.n == L.maxSize) {
        return 0;
    }
    
    // 参数i不合理的情况
    if (i < 0 || i > L.n+1) {
        return 0;
    }
    
    // i+1之后的位置都依次后移
    for(int j = L.n; j >= i; j--) 
    {
        L.data[j] = L.date[j-1];
    }
    // 插入该值
    L.data[i-1] = x;
    // 表长加1
    L.n++;
    
    // return：成功则返1 不成功返0
    return 1;
}

顺序表的删除

int remove(SqList &L, int i, DataType &x)
{
    // 表空的情况
    if (!L.n) {
        return 0;
    }
    
    // 参数i不合理的情况
    if (i < 1 || i > L.n) {
        return 0;
    }
    
    // 把要被删除的值存起来
    x = L.data[i-1];
    
    // 依次前移
    for(int j = i; j < L.n; j++) 
    {
        L.data[j-1] = L.date[j];
    }
    // 表长减1
    L.n--;
    
    return 1;
}

⼩节3 顺序表的应用举例

  • 例题2-5 两个顺序表LA和LB，把它们当作集合来使用，完成集合”并“运算的实现,结果存于LA，重复元素只留一个。

  • 例题2-6 做集合的“交”运算，求LA，LB中的共有元素，结果存于LA。

  • 例题2-7 将顺序表 (a1，a2，… ，an) 重新排列为以 a1 为界的两部分：a1 前面的值均比 a1 ⼩， a1 后面的值都比 a1 大(这里假设数据元素的类型具有可比性, 不妨设为整型)。 这一操作称为划分。a1 也称为基准。

模块3 单链表

⼩节1 单链表的定义和特点

单链表

当一个序列中只含有指向它的后继节点的链接时，就称该链表为单链表。

data | next

head- > 1 |- > 2 |- > … n |^

带头结点的单链表

头指针head指向头结点，头结点的值域不含任何信息，从头结点的后继结点开始存储数据信息。 头指针head始终不等于NULL，head->next等于NULL时，链表为空。

不带头结点的单链表

头指针head直接指向开始结点。 当head等于NULL时，链表为空。

如何从线性表中得到单链表？

链表是一个动态的结构，它不需要提前分配空间，因此⽣成链表的过程是一个结点“逐个插入” 的过程。

单链表的结构定义

typedef int DataType;
typedef struct node    // 链表结点
{
    DataType data;    // 数据域
    struct node *link;    // 链接指针域
} LinkNode, *LinkList;
  • 例题2-8 单链表中，增加一个头结点的目的是为了()

A.使单链表⾄少有一个结点 B.标识表结点中首结点的位置 C.方便运算的实现 D.说明单链表是线性表的链式存储

⼩节2 单链表主要操作

单链表的插入「在表头插入」

(1) 创建一个新的结点q。

(2) 将此结点的数据域赋值为e，并将它的 next 指针指向第一个结点，即L。

(3) 将L修改为指向新的结点q。

1.q->data=e; 
2.q->next=L->next; 
3.L->next=q;

单链表的插入「在表间插入」

(1)创建一个新的结点q。

(2)将此结点的数据域赋值为e，并将它的next指针指向p。

(3)查找到p的前驱结点pre。

(4)将pre的next指针指向新创建的结点q

1. q-data=e; 
2. q-next=p->next; 
3. p->next=q;

单链表的删除「在表头删除」

删除链表中的某个元素e，如果e在链表中出现不⽌一次，将删除第一次出现的e，否则什么也不做。 用p找到元素e所在的结点：

(1)将L指向p->next。

(2)释放p。

1.L->next=L->next->next; 
2.delete p;  // or delete L-next

单链表的删除「在表间删除」

删除链表中的某个元素e，如果e在链表中出现不⽌一次，将删除第一次出现的e，否则什么也不做。 用p找到元素e所在的结点：

(1)找到p的前驱结点pre。

(2)将pre->next指向p->next。

(3)释放p。

1.pre->next=p->next;  // pre->next=pre->next->next; 
2.delete p;  // or delete L-next

单链表的创建「头插法」

头插法：把后建⽴的结点插在头部

头插法建⽴起来的链表的实际顺序与输入顺序刚好相反，输出时为倒序。

p->next=L-next; 
L->next=p;

单链表的创建「尾插法」

头插法与尾插法相反，建⽴起来的链表的实际顺序与输入顺序相同，输出时为顺序。

p->next=q; 
p=q;

p=q到作用是只要有新结点插入，那么就会变成尾部结点，然后不断循环此操作。

⼩节3 单链表的应用举例

单链表的输出

void display(struct node *head)
{
    // 此处不能为head != NULL
    while (head->next != NULL)  
    {
        printf("%d", (head->next)->data);
        head = head->next;
    }
}

因为下面的printf输出的是当前位置的下一个结点的数据，若写成head != NULL， 则指针指到NULL前个结点时，(head->next)->data无法输出。

求链表的元素个数

思路：遍历链表去统计元素个数

size_t LinkListSize(LinkNode* head)
{
    if (head == NULL) {
        return 0;
    }
    size_t size = 0;
    LinkNode* cur = head;
    while(cur != NULL)
    {
        size++;
        cur = cur->next;
    }
    
    return size;
}
  • 例题2-9 已知单链表H，写一算法将其倒置。

模块4 循环链表和双向链表

⼩节1 循环链表

循环链表的定义

最后一个结点的指针域的指针⼜指回第一个结点的链表。

和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。

  • 例题2-10

在设尾指针的单循环链表上实现将两个线性表(a1，a2，a3，…an)和(b1，b2，b3，…bn)链接成一个线性表的运算。

⼩节2 双向链表

双向链表的定义

双向链表的每个数据结点都有两个指针，分别指向直接后继和直接前驱。 所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

typedef struct DuLNode
{
    ElemType data;  // 数据域
    struct DuLNode *prior;  // 指向前驱的指针域
    struct DuLNode *next;  // 指向后继的指针域
} DuLNode, *DuLinkList;

双向链表的操作特点

”查询”和单链表相同

“插入”和“删除”时需要同时修改两个方向上的指针。

双向链表的插入

1.s->prior=p->prior; 
2.p->prior->next=s; 
3.s->next=p; 
4.p->prior=s;

双向链表的删除

1.找到即将被删除的结点p；

2.将p的前驱的后继指向p的后继；

3.将p的后继的前驱指向p的前驱；

4.删除结点p即delete p；

p->prior->next = p->next; 
p->next->prior = p->prior;
  • 例题2-11 与单链表相比。双链表的优点之一是()。

A.插入、删除操作更方便 B.可以进行随机访问 C.可以省略表头指针或者表尾指针 D.访问前后相邻结点更灵活

静态链表

借助数组来描述线性表的链式存储结构，这里的指针是结点的相对地址（数组下标）。 与顺序表一样，静态链表需要预先分配一块连续的存储空间。

#define MaxSize 50  // 静态链表的最大长度
typedef struct{   // 静态链表结构类型的定义
    ElemType data;  // 存储数据元素
    int next;    // 下一个元素的数组指针
}SLinkList[MaxSize]
  顺序表 链表
存取方式 顺序存取/随机存取 从表头顺序存取
逻辑结构与物理结构 逻辑相邻即物理相邻 逻辑相邻物理不一定相邻
存储密度 =1 <1
空间分配 预先分配 需要时申请分配
  • 例题2-12 若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为了提高效率，应采用()的存储方式

A.单链表 B.双向链表 C.单循环链表 D.顺序表

例题解析

  • 解析2-1 C

线性表是由具有相同数据类型的有限个数据元素组成的，数据元素是由数据项组成的。

  • 解析2-2 B

A.指定的是集合，而集合中的各元素没有前后驱关系。 C.线性表的定义要求为有限序列，而C中序列的元素个数是无穷多个的。 D.邻接表属于存储结构，线性表是一种逻辑结构，不可将二者混为一谈。

  • 解析2-3 A

线性表中，除最后一个元素外，每个元素只有唯一的后继元素。

  • 解析2-4
void union (List &La, List Lb)
{
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);
    for (i=1; i<=Lb_len; i++) 
    {
        GetElem(Lb, i, e);
        if (!LocateElem(La, e, equal)) {
            ListInsert(La, ++La_len, e);
        }
    }
}
  • 解析2-5
void Merge(SqList &LA, SqList &LB)
{
    int n = Length(LA), m = Length(LB), i, k, x;
    for (i = 1; i <= m; i++) 
    {
        x = LB.data[i-1];  // 在LB中取一个元素
        k = Search(LA, x);  // 在LA中查找它
        // 若在LA中未找到则将它插入LA中
        if (k = 0) {
            Insert(LA, n+1, x);  // 插入到第n个元素之后
            n++;
        }        
    }
}
  • 解析2-6
void Intersection(SqList &LA, SqList &LB)
{
    int n = Length(LA), m = Length(LB), i = 1, k, x;
    while (i <= n) 
    {
        x = LA.data[i-1];  // 在LA中取一个元素
        k = Search(LB, x);  // 在LB中查找它
        / 若在LB中未找到则将它从LA中删除掉
        if (k == 0) {
            Remove(LA, i, x);
            n--;
        } else {
            i++;
        }
    }
}
  • 解析2-7

基本思路： 从第二个元素开始到最后一个元素，逐一向后扫描： （1）当前数据元素 ai 比 a1 大时，表明它已经在 a1 的后面，不必改变它与 a1 之间的位置，继续比较下一个。 （2）当前结点若比 a1 ⼩，说明它应该在 a1 的前面，此时将它上面的元素都依次向下移动一个位置，然后将它 置入最上方。

void part(SqList &l)
{
    int i, j;
    Elemtype x, y;
    x = L.elem[0];
    for (i = 1; i < L.length; i++) 
    {
        if (L.elem[i] < x) {
            y = L.elem[i];
            for (j = i -1; j >= 0; j--) 
            {
                L.elem[j+1] = L.elem[j];
                L.elem[0] = y;
            }
        }
    }
}
  • 解析2-8 C

方便运算体现在两个方面，第一，有头结点后，插入和删除数据元素的算法统一了不再需要判断是否在第一个元素之前插入或删除第一个元素； 第二，不论链表是否为空，其头指针是指向头结点的⾮空指针，链表的头指针不变，因此空表和⾮空表的处理统一了。

  • 解析2-9

算法思路： 依次取原链表中的每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向当前结点，p为空时结束。

算法如下：

void reverse(LinkLIst &H)
{
    LNode *p, *q;
    p = H->next;  // p指向第一个数据结点
    H->next = NULL;  // 将原链表置为空表H*
    while(p)
    {
        q = p;
        p = p->next;
        q->next = H->next;  // 将当前结点插到头结点的后面
        H->next = q;
    }
}

该算法只是对链表中顺序扫描一边即完成了倒置，所以时间性能为O(n)。

  • 解析2-10
linklist connect(linklist A, linklist B)
{
    linklist p = A->next;
    A->next = (B->next)->next;
    free(B->next);
    B->next = p;
    A = B;
    return(A);
}
  • 解析2-11 D

在双链表中可以快速访问任何一个结点的前后相邻结点，而在单链表中只能快速访问任何一个结点的后继结点。

  • 解析2-12 D

要求能够最快存取i-1，i，i+1个元素值，ABC都只能从头结点依次顺序查找，时间复杂度为O(n)，只有顺序表可以随机存取，时间复杂度为O(1)。






参考资料

返回