考研数据结构-线性表

杨利霞

考研数据结构-线性表
线性表的基本概念与实现

1.线性表的定义

线性表是具有相同特征数据元素的一个有限序列。

元素个数叫做线性表的长度，n(n>=0)表示,n=0(空表)

2.线性表的逻辑特性

只有一个表头元素，只有一个表尾元素。表头无前驱，表尾无后继，除表头和表尾外，其他元素只有一个直接前驱，也只有一个直接后继。

3.线性表的存储结构

顺序存储结构（顺序表）和链式存储结构（链表）两种。

顺序表

​        连续存储、顺序存储。

链表

​        不仅有元素的信息，还有逻辑关系的信息（后继结点的地址信息）。

两种存储结构的比较

顺序表：

​        随机访问特性、占用连续的存储空间。

​        插入：需要移动多个元素。

链表：

​        不支持随机访问、存储空间利用率较顺序表稍低、支持存储空间的动态分配。

​        插入：无需移动元素。

链表的5种形式：

单链表：

带头结点的单链表（头结点不存信息）：head->next==Null,链表为空。

不带头的单链表：head==Null,链表为空。

双链表：多了一个前驱结点

循环单链表：

单链表最后一个指针域（空指针）指向第一个结点。若循环结点戴头结点，则最后一个指针域（空指针）指向头结点。

循环双链表：

head==Null,不带头结点的循环双链表为空。

带头结点，空状态下，head->next和head->prior都必然等于head。

以下四句任何一句为真都可以判断循环双链表为空。

head->next==head;
head->priot==head;
head->next==head && head->priot==head;
head->next==head || head->priot==head;
1
2
3
4
静态链表

指针指示的是链表中下一元素在数组中的地址。

与顺序表相比优点是便于插入和删除。

说明：考研中经常考到顺序表和链表的比较，给出全面答案。

基于空间的比较

存储方式的分配：

顺序表的存储空间是一次性分配的，链表的存储空间是多次分配的。

存储密度（存储密度=结点值域所占的存储量/结点结构所占的存储总量）

顺序表的存储密度=1，链表的存储密度<1（因为结点中有指针域）

基于时间的比较

存取方式

顺序表可以随机存取;

链表只能顺序存取（遍历之前的元素）

插入/删除时移动元素的个数:

顺序表平均需要移动近一半元素；

链表不需要移动元素，只需要改变指针。

​        n和元素的顺序表删除和插入施加复杂度分析：

求概率

插入位置随机，n个插入位置，任一位置插入概率 p = 1/n

对应位置需要移动的元素个数

插在第i个元素之后，移动元素n-i个。

移动元素的数学期望E:

E = p(n+(n-1)+(n-2)+……+0) = (n-1)/2; O(n)

2.2线性表的结构体定义和基本操作

线性表的结构体定义

#define maxSize 100
1
1.顺序表的结构体定义

typedef struct{
    int data[maxSize];
    int length;
}Sqlist;
1
2
3
4
说明：考试中用的最多的线性表的定义是如下形式（因为简洁）：

int A[maxSize];
int n;//长度为n
1
2
2.单链表结点定义

typedef struct LNode{
int data;
struct LNode* next;
}LNode;

推荐这种。黄色线标注的写成一样多好。

3.双链表定义

typedef struct LNode{
        int data;
        struct LNode* prior;
        struct LNode* next;
}LNode;
1
2
3
4
5
说明：分配链表结点空间时，定义一个指针，指针指向结点，常用这个指针的名称来作为结点的名称。

LNode *A = (LNode*)malloc(sizeof(LNode))

int p = (int)malloc(sizeof(int))

typedef struct node{
    int x;
    int y;
}node;
int p = (int)malloc(sizeof(int));//ok
node n = (node)malloc(sizeof(node));//不ok
node no = new node;//不ok
node *No = new node[5];//ok
//上述几个不ok得原因没有想通。
1
2
3
4
5
6
7
8
9
‘*’和‘->’的区别：

​        结构体变量取分量用’.’

LNode a;
a.data;
1
2
​        指向结构体变量的指针取分量用’->’

LNode *b;
b->data;
//(*b)就变成了结构体变量可以用'.'
(*b).data;
1
2
3
4
描述解释：

“p指向q”，p指代指针，因为p既是指针名又是结点名，但是结点不能指向结点，因此p指代指针。又如“用函数free()释放p的空间”，此时p指代结点，因为p既是指针名又是结点名，但是指针变量自身所需的存储空间时系统分配，不需要用户调用函数free()释放，只有用户分配的存储空间才需要用户自己释放，所以p指代结点。

补充：（仅作补充,便于加深理解。）

有的同学可能和我一样有疑问，这个LNode，在main函数中我偏不申明为LNode*指针，非要试试声明为LNode;

我们通过代码得出的结论是：确实结点不能指向结点，因为Lnode内的next属性是指针，我们只能让LNode*的指针来指向LNode* next（实践出真知！）;

#include <iostream>
#include<stdlib.h>
using namespace std;
typedef struct LNode{
    int data;
    struct LNode* next;
}LNode;
void creat_LNode(LNode &L);
void print(LNode L);
int  main() {
    LNode L;
    creat_LNode(L);
    print(L);
    return 0;
}
void creat_LNode(LNode &L){
    LNode *temp = &L;
    for(int i =0;i<10;i++){
        temp->data = i;
        LNode* temp2 = (LNode*)malloc(sizeof(sizeof(LNode)));
        temp->next = temp2;
        temp = temp2;
    }
    temp->next = NULL;
    //free(temp);此处不能free();
}
void print(LNode L){
    LNode *temp = &L;
    while(temp->next!=NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}
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
顺序表的初始化：

void initList(Sqlist &L){
        L.length = 0;
}
1
2
3
“引用&的辨析”：

顺序表插入:在p位置上插入e之后,p不正确返回0。

void insertElem(Sqlist &L,int p,int e);

‘&’是引用，不要理解成地址，因为L本身需要改变所以用引用，把修改后的值带回去。如果不用引用，函数内修改的值是带不回去的。

//p的检查
if(p<0 || p>L.length || L.length == maxSize)
    return 0;
1
2
3
链表插入:

链表尾插x

void insertElem(LNode *L,int x)

我们对单链表L进行了修改，但是没有用&L

void insertElem(LNode* &L,int x);

L内部数据的更改和==&==没有关系。

加了引用表示允许修改L指针的指向，然后把它带回到main函数中。

如果不加引用，即使我们在插入函数内，让L重新指向一个新的指针，L修改后的值是带不到main函数中的。比如：在下列的print()函数中，函数内已经修改了L=L->next,修改后的值没有带回去。

#include <iostream>
using namespace std;
typedef struct LNode{
    int data;
    struct LNode* next;
}LNode;
void insertElem(LNode *L,int x){
    while(L->next!=NULL){
        L=L->next;
    }
    //此时L的下一个为NULL
    L->next = (LNode*)malloc(sizeof(sizeof(LNode)));
    L->next->data = x;
    L->next->next = NULL;
}
void print(LNode *L){
    while (L->next!=NULL){
        L = L->next;
        cout<<L->data<<" ";
    }
    cout<<endl;
}
int  main() {
    LNode *L;
    L->data = -1;//头结点
    L->next = NULL;
    for(int i=0;i<10;i++){
        insertElem(L,i);
    }
   print(L);
    return 0;
}
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
逆置问题（408重要考点）

void reverse(int a[],int left,int right,int k){
        int temp;
    for(int i=left,j=right;i<left+k && i<j;i++,j--){
        temp = a;
        a = a[j];
        a[j] = temp;
    }
}
1
2
3
4
5
6
7
8
把长度n数组的前端k(k<n)个元素逆序到数组后端，数据不丢失，其余元素的位置无关紧要。

reverse(a,0,n - 1,k);

把长度n数组的前端k(k<n)个元素保持原序移动到数组后端，数据不丢失，其余元素的位置无关紧要。

先逆序前k个再重复1的过程

reverse(a,0,k-1,k);

reverse(a,0,n-1,k);

数组中元素(X0,X1,…,Xn-1)变为(Xp,Xp+1,…,Xn-1,X0,X1,…,Xp-1),即循环左移p个位置。

“前扔后”

要求：

123456789 -> 456789123

或者把123看成一个整体

=>321456789

=>321987654

=>456789123

reverse(a,0,p-1,p);
reverse(a,p,n-1,n-p);
reverse(a,0,n-1,n);
1
2
3
“后提前”

要求：

123456789 -> 789123456

把123456看成一个整体

=> 654321789

=>654321987

=> 789123456

reverse(a,0,n-p-1,n-p);
reverse(a,n-p,n-1,p);
reverse(a,0,n-1,n);
————————————————
版权声明：本文为CSDN博主「tiffany3344」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/sjxgghg/article/details/105594813

chace

谢谢分享

2863358207

好好好好好好好好好好好好啊发表回复