【数据结构】线性表

知识目录

顺序表

• 概念：用一组地址连续的存储单元依次存储线性表的数据元素，这种存储结构的线性表称为顺序表。

• 特点：逻辑上相邻的数据元素，物理次序也是相邻的。

只要确定好了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的储存结构，因为高级语言中的数组类型也是有随机存取的特性，所以通常我们都使用数组来描述数据结构中的顺序储存结构，用动态分配的一维数组表示线性表。

---

定义以及初始化

#define MaxSize 50//顺序表的最大长度
typedef char ElemType;
typedef struct
{
    ElemType data[MaxSize];//顺序表的元素
    int length;//顺序表的当前长度
}SqList;

//初始化顺序表
void InitList(SqList *l){
    l->length = 0;//长度赋值为0
}
1
2
3
4
5
6
7
8
9
10
11
12

---

顺序表的插入操作

bool ListInsert(SqList *l,int i,ElemType e){//参数分别是：顺序表、插入的位置以及插入的元素
    //判断i的范围是否有效
    if (i<1||i>l->length+1)
        return false;
    //当前存储空间已满，不能插入
    if (l->length>=MaxSize)
        return false;
    //将第i个以及之后的元素后移
    for (int j = l->length; j >= i; j--)
    {
        l->data[j] = l->data[j-1];
    }
    l->data[i-1] = e;//赋值
    l->length = l->length + 1;//顺序表的长度+1
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

删除操作

bool ListDelect(SqList *list,int i){
    //判断i的合法性
    if(i<1||i>list->length+1) return false;
    for(int j = i;j<=list->length;j++)//将第i后的元素前移
        list->data[j-1]=list->data[j];
    list->length--;//长度自减1
    return true;
}
1
2
3
4
5
6
7
8

---

按值查找，返回第一个位置

int locateElem(SqList list,ElemType e){//
    for (int j = 0; j < list.length; j++)
    {
        if (list.data[j]==e) return j+1;
    }
    return 0;//没有找到
}
1
2
3
4
5
6
7

---

按位查找

ElemType GetElem(SqList list,int i){
    return list.data[i-1];
}
1
2
3

---

按照顺序输出元素

void PrintList(SqList l){
    for (int i = 0; i < l.length; i++)
    {
         printf("%c\n",l.data[i]);
    }
    printf("************************\n");
}
1
2
3
4
5
6
7

---

链式存储

单链表

初始化

typedef char ElemType;

typedef struct LNode
{
    ElemType data;//data域
    struct LNode* next;//指针域
}LNode;

//初始化链表
void InitLNode(LNode *node){
    node = (LNode*)malloc(sizeof(LNode));//初始化新的node节点
    node->data = NULL;//给数值赋予初值
    node->next = NULL;//赋予下一个结点的指针
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

头插法

//头插法插入节点
bool LNodeHeadInsert(LNode* node,ElemType e){
    LNode* tempNode = (LNode*)malloc(sizeof(LNode));//开辟新的空间
    tempNode->data = e;//存储值
    tempNode->next = node->next;//指向第一个节点
    node->next = tempNode;//将头节点的下一个指针指向新的第一个节点
    return true;
}
1
2
3
4
5
6
7
8

---

尾插法

//尾插法插入
bool LNodeTailInsert(LNode* list,ElemType e){
    LNode* node = (LNode*)malloc(sizeof(LNode));//开辟空间，新建节点
    node->data = e;//data给到新建节点的数据域
    node->next = NULL;//新建节点指向NULL
    while(list->next)//寻找最后一个节点
    {
        list=list->next;
    }
    list->next=node;//最后一个节点指向新建节点
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12

---

删除

//删除
void LNodedelete(LNode* list,ElemType data)//删除
{
    LNode* pre=list;//保存头节点，它是current的前一个节点
    LNode* current=list->next;//保存第一个节点开始，从它开始遍历
    while(current)//遍历,可使用头节点data进行for循环遍历
    {
        if(current->data==data)//找到data
        {
            pre->next=current->next;//将前一个节点指向要要删除节点的下一个节点
            free(current);//释放要铲除节点的堆内存空间
            break;//退出循环
        }
        pre = current;//未找到data则往后继续遍历
        current = current->next;//未找到data则往后继续遍历
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

双链表

初始化

typedef char ElemType;
//定义结点信息 
typedef struct DNode{
	struct DNode *prior;
	ElemType data;
	struct DNode *next;
}DNode; 

void InitDNode(DNode *node){
    node = (DNode*)malloc(sizeof(DNode));//开辟空间
    node->data = NULL;
    node->prior = NULL;
    node->next = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

添加节点

//增加节点
void DNodeInsert(DNode *node,ElemType e){
    DNode *l = (DNode*)malloc(sizeof(DNode));//开辟空间
    l->data = e;
    l->next = node->next;
    node->next->prior = l;
    l->prior = node;
    node->next = l;
}
1
2
3
4
5
6
7
8
9

---

删除

//删除节点
void DNodeDelete(DNode *node,ElemType e){
    while (node->next)
    {
        if (node->data==e)
        {
           node->prior->next = node->next;
           node->next->prior = node->prior;
           break;
        }
        node = node->next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---