数据结构学习笔记--线性表

Updated on May 15, 2024 with 0 views and 0 comments

一、简介

线性表是n个数据元素的有限序列，例如英文字母的字母表(A,B,C......,Z)。

同一个线性表中的元素必定有相同特性，即属于同一数据对象，相邻数据元素之间存在序偶关系，若将线性表记作(a₁,...,a_i-1,a_i,a_i+1,...,a_n)，将a_i-1称为a_i的直接前驱，a_i+1称为a_i的直接后继

线性表中元素的个数n(n>=0)定义为线性表的长度，n=0时称为空表

二、线性表的顺序表示和实现

2.1 顺序表的内存

线性表的顺序表示就是用一组地址连续的存储单元一次存储线性表的数据元素；

假设线性表中每个元素占用l个存储单元，并以所占据的第一个存储单元作为数据元素的存储位置，则LOC(a_i+1) = LOC(a_i)+l，一般来说线性表第i个数据元素的存储位置为LOC(a_i) = LOC(a₁)+(i-1)*l

2.2 添加元素

向线性表中添加一个元素时，线性表长度会加1，且添加元素的为序的后续元素都会在内存中向后移动一位，删除则需要把后续元素都往前移动一位

2.3 删除元素

删除一个元素时，被删除元素的后续元素都会向前移动一位

2.4 根据下标查询元素

因为是数组实现，直接访问数组下标就可以了

2.5 时间复杂度

添加和删除的时间复杂度都是O(n)，查询的时间复杂度为O(1)

2.6 代码实现

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef enum Status  { OK, MEMORY_OVERFLOW, ERROR, OUT_OF_INDEX } Status;

// 线性表存储空间的初始分配量
#define LIST_INIT_SIZE 4
// 线性表存储空间的分配增量
#define LIST_INCREMENT 8

// 定义顺序线性表结构体
typedef struct ArrayList {
    ElemType* elem; //存储空间地址
    int length; // 当前长度
    int listSize; // 当前分配的容量(以sizeof(ElemType)为单位)
} ArrayList;

// 构造一个空的线性表
Status initArrayList(ArrayList* list) {
    list->elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (list->elem == NULL) {
        printf("内存初始化失败");
        return MEMORY_OVERFLOW;
    }
    list->length = 0;
    list->listSize = LIST_INIT_SIZE;
    return OK;
}

/*
 * 在第i个元素位置上插入元素e(下标都是从1开始)
 * @param list 线性表
 * @param insertIndex 要插入的线性表位置
 * @param e 要插入的值
 * */
Status ArrayList_Insert(ArrayList* list, int insertIndex, ElemType e) {
    if (insertIndex<1 || insertIndex>(list->length + 1)) return OUT_OF_INDEX;
    // 容量超了需要在分配空间
    if (list->length >= list->listSize) {
        ElemType* newElem = (ElemType*)realloc(list->elem,
            (list->listSize + LIST_INCREMENT) * sizeof(ElemType));
        if (newElem == NULL) {
            printf("扩容失败");
            free(newElem);
            return MEMORY_OVERFLOW;
        }
        list->elem = newElem; 
        list->listSize += LIST_INCREMENT;
    }
    // 从数组的末尾开始，将每个元素向后移动一位
    for (int index = list->length; index >= insertIndex - 1; index--) {
        list->elem[index] = list->elem[index - 1];
    }
    list->elem[insertIndex - 1] = e;
    list->length++;
    printf("插入成功\n");
    return OK;
}

/*
 * 删除第i个位置上的元素e(下标都是从1开始)
 * @param list 线性表
 * @param index 要删除的线性表位置
 * @param e 指针指向删除的元素值
 * */
Status ArrayList_Delete(ArrayList* list, int deleteIndex, ElemType* e) {
    if (deleteIndex < 1 || deleteIndex > list->length) return OUT_OF_INDEX;
    *e = list->elem[deleteIndex - 1];
    for (int index = deleteIndex - 1; index < list->length; index++) {
        list->elem[index] = list->elem[index + 1];
    }
    --list->length;
    printf("删除成功\n");
    return OK;
}

void printArrayList(ArrayList* list) {
    for (int index = 0; index < list->length; index++) {
        printf("%d ",list->elem[index]);
    }
    printf("\n");
}

Status ArrayList_FindByIndex(ArrayList* list, int index, ElemType* e) {
    if (index < 1 || index > list->length) return OUT_OF_INDEX;
    *e = list->elem[index-1];
    return OK;
}

int main() {
    ArrayList list;
    initArrayList(&list);
    ArrayList_Insert(&list, 1, 1);
    ArrayList_Insert(&list, 1, 2);
    ArrayList_Insert(&list, 2, 3);
    ArrayList_Insert(&list, 4, 4);
    ArrayList_Insert(&list, 1, 5);
    printArrayList(&list);

    // 查询第一个元素
    ElemType e;
    ArrayList_FindByIndex(&list, 1, &e);
    printf("查询到元素%d\n", e);

    // 删除第1个元素
    ElemType e1;
    ArrayList_Delete(&list, 1, &e1);
    printf("%d\n", e1);
    printArrayList(&list);


    // 删除第4个元素
    ElemType e2;
    ArrayList_Delete(&list, 4, &e2);
    printf("%d\n", e2);
    printArrayList(&list);

    // 删除第2个元素
    ElemType e3;
    ArrayList_Delete(&list, 2, &e3);
    printf("%d\n", e3);
    printArrayList(&list);

    // 删除第1个元素
    ElemType e4;
    ArrayList_Delete(&list, 1, &e4);
    printf("%d\n", e4);
    printArrayList(&list);


    // 删除第1个元素
    ElemType e5;
    ArrayList_Delete(&list, 1, &e5);
    printf("%d\n", e5);
    printArrayList(&list);

    return 1;
}

三、线性表的链式表示和实现

3.1 线性链表

线性表的链式存储的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。

对每个元素a_i,除了要存储自身数据，还需要一个直接后继的存储位置，这两部分信息组成数据元素a_i的存储映像，成为节点。它包括两个域：其中存储数元素信息的域称为数据域，存储直接后继存储位置的域称为指针域，指针域中存储的信息称作指针或链。

n个节点链接称一个链表就是线性链表，因为每个节点只包含一个指针域，所以又称为单链表或线性链表

3.1.1 查找元素

查找元素必须从线性表的起始位置开始遍历，假设p是指向第i个数据元素的指针，则p->next是指向第i+1个元素的指针

3.1.2 添加元素

如下在a₁和a₂之间增加一个a₃节点，需要以下几个步骤

创建a₃节点
a₃->next = a₁->next
a₁->next = a₃

3.1.3 删除元素

删除a₂时有以下操作

a₂ ->next = a₂->next
a₂ ->next = NULL;
释放a₂ >占用的内存

3.1.4 时间复杂度

添加和删除的时间复杂度都是O(1)，查询的时间复杂度为O(n)

3.1.5 代码实现

#include <stdio.h>
#include<stdlib.h>

typedef int ElemType;
/*
* 链式线性表节点包含一个数据节点，一个指针节点
*/
typedef struct LNode {
	ElemType data;
	struct LNode* next;
}LNode;
/*
* 链式线性表，存储当前线性表长度和第一个节点
*/
typedef struct LinkedList {
	ElemType length;
	LNode* head;
}LinkedList;
typedef enum Status { OK, MEMORY_OVERFLOW, ERROR, OUT_OF_INDEX } Status;


Status initLinkedList(LinkedList* list) {
	list->head = NULL;
	list->length = 0;
	return OK;
}

/*
* 查找第index个数据元素
*/
Status LinkedList_FindByIndex(LinkedList* const list, int index, ElemType* e) {
	if (index > list->length) {
		printf("第%d个元素不存在\n", index);
		return OUT_OF_INDEX;
	}
	LNode *currentNode = list->head;
	int currentIndex = 1;
	while (currentNode !=  NULL && currentIndex < index) {
		currentNode = currentNode->next;
		currentIndex++;
	}
	if (currentNode == NULL) return ERROR;
	*e = currentNode->data;
	return OK;
}
/*
 * 在第index个元素位置上插入元素e(下标都是从1开始)
 * @param list 线性表
 * @param insertIndex 要插入的线性表位置
 * @param newData 要插入的值
 * */
Status LinkedList_Insert(LinkedList* list, int index, ElemType newData) {
	// 新建节点
	LNode* newNode = (LNode*)malloc(sizeof(LNode));
	if (newNode == NULL) {
		return MEMORY_OVERFLOW;
	}
	newNode->data = newData;
	newNode->next = NULL;
	// 若链表还没有节点
	if (list->head == NULL && index == 1) {
		list->head = newNode;
		list->length++;
		printf("保存成功\n");
		return OK;
	}
	// 在第一个位置插入
	if (index == 1) {
		newNode->next = list->head;
		list->head = newNode;
		list->length++;
		printf("保存成功\n");
		return OK;
	}

	// 找到第i-1个节点
	LNode* currentNode = list->head;
	int currentIndex = 1;
	while (list != NULL && currentIndex < index-1) {
		currentNode = currentNode->next;
		currentIndex++;
	}
	if (currentNode == NULL || currentIndex > index - 1) return ERROR;

	newNode->next = currentNode->next;
	currentNode->next = newNode;
	list->length++;
	printf("保存成功\n");
	return OK;
}

/*
 * 删除第index个位置上的元素e(下标都是从1开始)
 * @param list 线性表
 * @param index 要删除的线性表位置
 * @param *deleteData 指针指向删除的元素值
 * */
Status LinkedList_Delete(LinkedList* list, int index, ElemType* deleteData) {
	if (index > list->length) return OUT_OF_INDEX;


	if (index == 1) {
		LNode* head = list->head;
		list->head = head->next;
		head->next = NULL;
		*deleteData = head->data;
		free(head);
		list->length--;
		printf("删除成功\n");
		return OK;
	}

	// 找到待删除元素的前一个元素
	int currentIndex = 1;
	LNode* currentNode = list->head;
	while (currentNode != NULL && currentIndex < index - 1) {
		currentIndex++;
		currentNode = currentNode->next;
	}

	// 这才是要删除的节点
	LNode* deleteNode = currentNode->next;

	currentNode->next = deleteNode->next;
	deleteNode->next = NULL;
	*deleteData = deleteNode->data;
	free(deleteNode);
	list->length--;
	printf("删除成功\n");
	return OK;
}

void printLinkedList(LinkedList* list) {
	LNode *currentNode = list->head;
	while (currentNode != NULL) {
		printf("%d ", currentNode->data);
		currentNode = currentNode->next;
	}
	printf("\n");
}
int main() {
	LinkedList list;
	initLinkedList(&list);
	LinkedList_Insert(&list, 1, 1);
	LinkedList_Insert(&list, 1, 2);
	LinkedList_Insert(&list, 3, 3);
	LinkedList_Insert(&list, 4, 4);
	LinkedList_Insert(&list, 5, 5);
	printLinkedList(&list);


	ElemType a1;
	LinkedList_Delete(&list, 1, &a1);
	printf("%d已删除\n", a1);
	printLinkedList(&list);


	ElemType a2;
	LinkedList_Delete(&list, 3, &a2);
	printf("%d已删除\n", a2);
	printLinkedList(&list);

	ElemType a3;
	LinkedList_Delete(&list, 3, &a3);
	printf("%d已删除\n", a3);
	printLinkedList(&list);


	ElemType a4;
	LinkedList_Delete(&list, 2, &a4);
	printf("%d已删除\n", a4);
	printLinkedList(&list);


	ElemType a5;
	LinkedList_Delete(&list, 1, &a5);
	printf("%d已删除\n", a5);
	printLinkedList(&list);
}

3.2、循环单链表

循环链表的操作起始和单链表操作一致，区别只是单链表的尾节点指向链表的头节

3.2.1 查找元素

查找元素可以从线性表的任意位置开始遍历，假设p是指向第i个数据元素的指针，则p->next是指向第i+1个元素的指针

3.2.2 时间复杂度

删除、查询、添加元素时间复杂度与单链表相同

3.3 双向链表

单链表只能总节点头开始往后查询其他节点，若要查询节点的直接前驱，也需要从表头出发，再单链表中，查询后继得时间复杂度为O(1)，而查询前驱得时间复杂度为O(n)

双链表有两个指针域，一个指向后继节点，一个指向前驱节点

3.3.1 查找元素

双向链表可以从头节点开始向后遍历查找，也可以从尾节点开始向前遍历查找

3.3.2 添加元素

3.3.3 删除元素

3.3.4 时间复杂度

添加和删除的时间复杂度都是O(1)，查询的时间复杂度为O(n)

3.3.5 代码实现

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
/*
* 双链表节点包含一个数据节点，两个指针节点，一个指向前驱，一个指向后继
*/
typedef struct DLNode {
	ElemType data;
	struct DLNode* next;
	struct DLNode* pre;
}DLNode;

/*
* 存储当前线性表长度和第一个节点以及最后一个节点
*/
typedef struct DoubleLinkedList {
	int length;
	DLNode* head;
	DLNode* tail;
}DoubleLinkedList;
typedef enum Status { OK, MEMORY_OVERFLOW, ERROR, OUT_OF_INDEX } Status;

Status initDoubleLInkedList(DoubleLinkedList* list) {
	list->head = NULL;
	list->tail = NULL;
	list->length = 0;
	return OK;
}

void printDoubleLinkedList(DoubleLinkedList* list) {
	DLNode* currentNode = list->head;
	while (currentNode != NULL) {
		printf("%d ", currentNode->data);
		currentNode = currentNode->next;
	}
	printf("\n");
}

Status DoubleLinkedList_FindByIndex(DoubleLinkedList* const list, int index, ElemType* e) {
	if (index > list->length) {
		printf("第%d个元素不存在\n", index);
		return OUT_OF_INDEX;
	}
	DLNode* currentNode = list->head;
	int currentIndex = 1;
	while (currentNode != NULL && currentIndex < index) {
		currentNode = currentNode->next;
		currentIndex++;
	}
	if (currentNode == NULL) return ERROR;
	*e = currentNode->data;
	return OK;
}

/*
 * 在第index个元素位置上插入元素e(下标都是从1开始)
 * @param list 双链表
 * @param insertIndex 要插入的双链表位置
 * @param newData 要插入的值
 * */
Status DoubleLinkedList_Insert(DoubleLinkedList* const list, int index, ElemType e) {
	// 给新节点申请内存空间
	DLNode* newNode = (DLNode*)malloc(sizeof(DLNode));
	if (newNode == NULL) {
		return MEMORY_OVERFLOW;
	}
	newNode->data = e;
	newNode->pre = NULL;
	newNode->next = NULL;

	// 若双链表还没有节点
	if (list->head == NULL && index == 1) {
		list->head = newNode;
		list->tail = newNode;
		list->length++;
		printf("保存成功\n");
		return OK;
	}

	//在第一个位置插入
	if (index == 1) {
		DLNode* oldFirst = list->head;

		oldFirst->pre = newNode;
		newNode->next = oldFirst;

		list->head = newNode;
		list->length++;
		printf("保存成功\n");
		return OK;
	}

	// 找到第i-1个节点
	DLNode* currentNode = list->head;
	int currentIndex = 1;
	while (list != NULL && currentIndex < index-1) {
		currentNode = currentNode->next;
		currentIndex++;
	}
	if (currentNode == NULL || currentIndex > index-1) return ERROR;

	// 若当前节点是尾节点
	currentNode->next = newNode;
	newNode->pre = currentNode;
	if (currentNode == list->tail) {
		list->tail = newNode;
	}
	else {
		DLNode* nextNode = currentNode->next;
		newNode->next = nextNode;
		nextNode->pre = newNode;
	}

	list->length++;
	printf("保存成功\n");
	return OK;

}


/*
 * 删除第index个位置上的元素e(下标都是从1开始)
 * @param list 双链表
 * @param index 要删除的双链表位置
 * @param *deleteData 指针指向删除的元素值
 * */
Status DoubleLinkedList_Delete(DoubleLinkedList* list, int index, ElemType* deleteData) {
	if (index > list->length) return OUT_OF_INDEX;
	if (index == 1) {
		DLNode* headNode = list->head;
		if (headNode == list->tail) {
			list->head = NULL;
			list->tail = NULL;
		}
		else {
			DLNode* nextNode = headNode->next;
			nextNode->pre = NULL;
			list->head = nextNode;
		}
		*deleteData = headNode->data;
		free(headNode);
		list->length--;
		printf("删除成功\n");
		return OK;
	}

	// 找到待删除元素的元素
	int currentIndex = 1;
	DLNode* currentNode = list->head;
	while (currentNode != NULL && currentIndex < index) {
		currentIndex++;
		currentNode = currentNode->next;
	}
	// 若删除的是尾节点
	DLNode* preNode = currentNode->pre;
	if (currentNode == list->tail) {
		preNode->next = NULL;
		currentNode->pre = NULL;
		list->tail = preNode;
	}
	else {
		DLNode* nextNode = currentNode->next;
		currentNode->next = NULL;
		currentNode->pre = NULL;
		preNode->next = nextNode;
		nextNode->pre = preNode;
	}

	*deleteData = currentNode->data;
	free(currentNode);
	list->length--;
	printf("删除成功\n");
	return OK;
}
int main() {
	DoubleLinkedList list;
	initDoubleLInkedList(&list);
	DoubleLinkedList_Insert(&list, 1, 1);
	DoubleLinkedList_Insert(&list, 1, 2);
	DoubleLinkedList_Insert(&list, 3, 3);
	DoubleLinkedList_Insert(&list, 4, 4);
	DoubleLinkedList_Insert(&list, 5, 5);
	printDoubleLinkedList(&list);
	printf("%d",list.head->data);
	printf("%d\n", list.tail->data);


	ElemType a1;
	DoubleLinkedList_Delete(&list, 1, &a1);
	printf("%d已删除\n", a1);
	printDoubleLinkedList(&list);
	printf("%d", list.head->data);
	printf("%d\n", list.tail->data);


	ElemType a2;
	DoubleLinkedList_Delete(&list, 3, &a2);
	printf("%d已删除\n", a2);
	printDoubleLinkedList(&list);
	printf("%d", list.head->data);
	printf("%d\n", list.tail->data);

	ElemType a3;
	DoubleLinkedList_Delete(&list, 3, &a3);
	printf("%d已删除\n", a3);
	printDoubleLinkedList(&list);
	printf("%d", list.head->data);
	printf("%d\n", list.tail->data);


	ElemType a4;
	DoubleLinkedList_Delete(&list, 2, &a4);
	printf("%d已删除\n", a4);
	printDoubleLinkedList(&list);
	printf("%d", list.head->data);
	printf("%d\n", list.tail->data);

	ElemType a5;
	DoubleLinkedList_Delete(&list, 1, &a5);
	printf("%d已删除\n", a5);
	printDoubleLinkedList(&list);

}

3.4 双向循环链表

双向循环链表如下

3.4.1 查找元素

查找元素可以从线性表的任意位置开始遍历，假设p是指向第i个数据元素的指针，则p->next是指向第i+1个元素的指针

3.4.2 时间复杂度

删除、查询、添加元素时间复杂度与双链表相同

3.5 静态链表

3.5.1 定义

静态链表借助数组来描述线性表的链式存储结构，节点有数据域和指针域，这里的指针域村的是节点的数组下标

，静态链表也需要先分配一块连续的内存空间，左图的静态链表等价于右图的单链表

四、线性表和顺序表对比

4.1 性能对比

存储(读写方式)
- 顺序表可以顺序存取，也可以随机存取，链表只能从表头开始顺序存取元素
逻辑结构和物理结构
- 顺序存储中，逻辑上相邻的元素物理存储位置也相邻
- 链式存储中，逻辑上相邻的元素物理存储位置上不一定响铃，逻辑关系通过指针表示
查找、插入和删除操作
- 若元素存储无序，则顺序表和链表按值查询速度都为O(n)
- 按序号查找时，顺序表时间复杂度为O(1)，链表时间复杂度为O(n)
- 插入删除时，顺序表时间复杂度为O(n)，链表时间复杂度为O(1)
内存分配
- 顺序表只能是连续的内存空间，动态扩容需要移动大量元素且浪费资源
- 链表只要内存有空间就可以分配，操作灵活、高效

4.2 实际应用

基于存储考虑
- 存储规模难以确认时，使用链表
- 存储规模确认时，有限使用线性表
基于操作考虑
- 如果查询操作多，则优先使用线性表
- 如果增删操作多，则有限使用链表

标题：数据结构学习笔记--线性表
作者：wenyl
地址：http://www.wenyoulong.com/articles/2024/04/25/1714021601836.html

一、简介
二、线性表的顺序表示和实现
2.1 顺序表的内存
2.2 添加元素
2.3 删除元素
2.4 根据下标查询元素
2.5 时间复杂度
2.6 代码实现
三、线性表的链式表示和实现
3.1 线性链表
3.1.1 查找元素
3.1.2 添加元素
3.1.3 删除元素
3.1.4 时间复杂度
3.1.5 代码实现
3.2、循环单链表
3.2.1 查找元素
3.2.2 时间复杂度
3.3 双向链表
3.3.1 查找元素
3.3.2 添加元素
3.3.3 删除元素
3.3.4 时间复杂度
3.3.5 代码实现
3.4 双向循环链表
3.4.1 查找元素
3.4.2 时间复杂度
3.5 静态链表
3.5.1 定义
四、线性表和顺序表对比
4.1 性能对比
4.2 实际应用

Share WeiBo Twitter QZone WeChat ← → ↑ ↓