线性表
文章目录
- 线性表
- 1、线性结构
- 2、线性表
- 2.1 线性表定义
- 2.2 类型定义
- 2.2 顺序存储结构（Sequence List）
- 2.3 链式存储结构
- 2.3.1 单链表
- 2.3.2 循环链表
- 2.3.3 双链表
- 2.3.4 单链表、循环链表、双向链表的时间效率比较
- 2.3.5 链式存储结构优缺点
- 2.4 顺序表和链表比较
- 3、应用
1、线性结构
线性结构是一个数据元素的有序（次序上的有序）集
基本特征：
- 集合中必存在唯一的一个“第一元素”；
- 集合中必存在唯一的一个“最后元素”；
- 除最后元素外，均有唯一的后继；
- 除第一元素外，均有唯一的前驱；
2、线性表
2.1 线性表定义
线性表是具有相同特性的数据元素的一个有限序列 （n ≥ 0）
2.2 类型定义
抽象数据类型线性表的定义如下：
ADT List {
数据对象： D= { ai, ai ∈ ElemSet, i= 1,2, …, n, n≥0} {D为线性表的表长，n=0时线性表为空表}
数据关系： R1={ <ai-1,ai>lai-1,ai∈D, i=2,…,n } {设线性表为(a1,a2,…,ai,…an),称i为a在线性表中的位序}
基本操作：
结构的初始化
InitList(&L)
操作结果：构造一个空的线性表L结构的销毁
DestroyList(&L)
初始条件：线性表L已存在。
操作结果，销毁线性表L引用型操作 - 操作的结果不改变结构
ListEmpty(L)
初始条件：线性表L已存在。
操作结果：若L为空表，则返回 TRUE, 否则返回 FALSEListLength(L)
初始条件：线性表L已存在。
操作结果：返回L中数据元素个数。PriorElem(L, cur_ e, &pre_ e)
初始条件：线性表L已存在。
操作结果：若 cur_ e是L的数据元素，且不是第一个，则用 pre_ e 返回它的前驱，否则操作
失败， pre_ e无定义。NextElem(L, cur_ e, &next_ e)
初始条件：线性表L已存在。
操作结果：若 cur_ e是L的数据元素，且不是最后一个，则用 next_ e 返回它的后继，否则操
作失败， next_ e 无定义。GetElem(L, i, &e)
初始条件：线性表L已存在， 1≤i≤ListLength(L)
操作结果：用e返回L中第i个数据元素的值。LocateElem(L, e, compare())
初始条件：线性表L已存在， compare() 是数据元素判定函数。
操作结果：返回L中第1个与e满足关系 compare() 的数据元素的位序。若这样的数据元素
不存在，则返回值为 0ListTraverse(L, visit()）
初始条件：线性表L已存在。
操作结果：依次对L的每个数据元素调用函数visit()。一旦 visit() 失败，则操作失败。(visit()用于访问列表中的每个元素)加工型操作 - 操作的结果改变结构
ClearList (&L)
初始条件：线性表L巳存在。
操作结果：将L重置为空表。PutElem(L, i, &e)
初始条件：线性表L已存在， 1≤i≤ListLength(L)。
操作结果：L中第i个元素赋值同e的值。ListInsert (&L, i, e)
初始条件：线性表L已存在，1≤i≤ListLength(L)+1。
操作结果，在L中第i个位置之前插入新的数据元素 e,L 的长度增1。ListDelete(&L, i, &e)
初始条件：线性表L已存在且非空，1≤i≤ListLength(L)。
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。} ADT List
2.2 顺序存储结构（Sequence List）
用一组地址连续的存储单元一次存放线性表中的数据元素
//－－－－－线性表的动态分配顺序存储结构－－－－－ #define LIST_ INIT_SIZE 100 // 线性表存储空间的初始分配量 #define LISTINCREMENT 10 //线性表存储空间的分配增量 typedef struct { ElemType *elem; //存储空间基地址 int length; //当前长度 int listsize;//当前分配的存储容量、以sizeof(ElemType)为单位 }SqList
- 优点:
- 存储密度大(结点本身所占存储量/结点结构所占存储量)
- 可以 随机存取 表中任一元素
- 缺点:
- 在插入、删除某一元素时，需要移动大量元素
- 浪费存储空间
- 属于静态存储形式，数据元素的个数不能自由扩充
#define _CRT_SECURE_NO_WARNINGS *1 #include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define OVERFLOW -1 #define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量 #define LISTINCREMENT 10 // 线性表存储空间的分配增量 typedef int ElemType; typedef int Status; typedef struct { ElemType* elem; int length; int listsize; } SqList; Status InitList_Sq(SqList* L) { // 构造一个空的线性表L L->elem = (ElemType*)malloc(sizeof(ElemType) * LIST_INIT_SIZE); // 存储分配失败 if (!L->elem) exit(OVERFLOW); // 空表长度为0 L->length = 0; //初始存储容量 L->listsize = LIST_INIT_SIZE; return OK; } // 时间复杂度 O(n) Status ListInsert_Sq(SqList* L, int i, ElemType e) { // i 不合法 [1≤ i ≤ListLength.Sq(L) + 1] if (i<1 || i>L->length + 1) return ERROR; // 当前存储空间已满，增加分配 if (L->length >= L->listsize) { ElemType* newbase = (ElemType*)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(ElemType)); // 存储分配失败 if (!newbase) exit(OVERFLOW); // 新基址 L->elem = newbase; // 增加存储容量 L->listsize += LISTINCREMENT; } // q为插入位置 ElemType* q = &(L->elem[i - 1]); ElemType* p = &(L->elem[L->length - 1]); for (p; p >= q; --p) { *(p + 1) = *p;//右移 } *q = e;// 插入e ++L->length;// 表长增1 return OK; } // 时间复杂度 O(n) Status ListDelete_Sq(SqList* L, int i) { // i 不合法 [1≤ i ≤ListLength.Sq(L) + 1] if (i<1 || i>L->length + 1) return ERROR; // p为被删除元素的位置 ElemType* p = &(L->elem[i - 1]); // 被删除元素赋值给e ElemType e = *p; printf("元素%d已被删除\n", e); // 表尾元素的位置 ElemType* q = &(L->elem[L->length - 1]); for (++p; p <= q; ++p) { *(p - 1) = *p;//左移 } --L->length; return OK; } int LocateElem_Sq(SqList* L, ElemType e) { // 在顺序线性表L中查找第1个值与e相等 int i = 1; for (i; i <= L->length; i++) { if (L->elem[i - 1] == e) { return i; } } return 0; } void Print(SqList* L) { int i; printf("List: "); for (i = 0; i < L->length; i++) { if (i == L->length - 1) { printf("%d", L->elem[i]); } else { printf("%d, ", L->elem[i]); } } printf("\n"); } int main() { SqList L; int init_status = InitList_Sq(&L); if (init_status == 1) { ListInsert_Sq(&L, 1, 1); ListInsert_Sq(&L, 1, 2); ListInsert_Sq(&L, 2, 3); ListInsert_Sq(&L, 4, 4); ListInsert_Sq(&L, 5, 1); Print(&L); printf("L.length: %d\n", L.length); ListDelete_Sq(&L, 1); Print(&L); printf("L.length: %d\n", L.length); int index = LocateElem_Sq(&L, 1); printf("1第一次出现的位置：%d", index); } else { printf("初始化线性表失败"); } return 0; }
2.3 链式存储结构
2.3.1 单链表
结点(node)：
数据元素的存储映像
数据域: 存储数据元素信息的域
指针域：存储直接后继存储位置的域称为指针域。指针域中存储的信息称做指针或链。n
链表：
n个结点由指针链组成一个链表
线性链表或单链表：
每个结点中只包含一个指针域
头指针：
指向链表中第一个结点(即第一个数据元素的存储映像)的指针，整个链表的存取必须从头指针开始进行。
头结点：
在单链表的第一个结点之前附设一个结点,称之为头结点。
头结点的数据域可以不存储任何信息,也可存储如线性表的长度等类的附加信息；
头结点的指针域存储指向第一个结点的指针(即第一个元素结点的存储位置)。
若线性表为空表,则头结点的指针域为“空”。
首元结点：
是指链表中存储第一个数据元素a1的结点
最后一个结点的指针：
最后一个数据元素没有直接后继,则线性链表中最后一个结点的指针为“空”(NULL)。
单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名若头指针名是L，则把链表称为表L
假设p是指向线性表中第i个数据元素(结点ai)的指针,则p->next 是指向第i+1个数据元素(结点 ai+1)的指针。换句话说,若p->data=ai,则p->next->data=ai+1。由此,在单链表中,取得第i个数据元素必须从头指针出发寻找（ 顺序存取 法）,因此,单链表是非随机存取的存储结构。
typedef struct LNode{ //声明结点的类型和指向结点的指针类型 ElemType data; struct LNode* next; } LNode, *LinkList; //LinkList为指向结构体LNode的指针类型 //LNode、LinkList都是类型 // 定义链表L LinkList L;（常用） = LNode* L;（不常用） // 定义结点指针p LNode* p;（常用） = LinkList p;（不常用）
#define _CRT_SECURE_NO_WARNINGS *1
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
}Node;
struct Node* head;
void InsertHead(int x) {
//创建一个节点
Node* temp = (Node*)malloc(sizeof(Node));
if (temp != NULL) {
temp->data = x;
temp->next = head;
head = temp;
}
}
void Insert(int data, int n) {
Node* temp1 = (Node*)malloc(sizeof(Node));
if (temp1 != NULL) {
temp1->data = data;
temp1->next = NULL;
if (n == 1) {
temp1->next = head;
head = temp1;
return;
}
Node* temp2 = head;
int i;
for (i = 0; i < n - 2; i++) {
temp2 = temp2->next;
}
temp1->next = temp2->next;
temp2->next = temp1;
}
}
void Delete(int n) {
//if (head == NULL) return;
Node* temp = head;
if (n == 1) {
head = temp->next;
free(temp);
return;
}
int i;
for (i = 1; i < n - 1; i++) {
temp = temp->next;
}
Node* temp1 = temp->next;
temp->next = temp1->next;
free(temp1);
}
//迭代iteration
void Reverse() {
Node* current,* prev,* next;
current = head;
prev = NULL;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
head = prev;
}
//iteration
void Print() {
Node* temp = head;
printf("List is: ");
while (temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
//递归recursion
void ReverseRecursion(Node* p) {
if (p->next == NULL) {
head = p;
return;
}
ReverseRecursion(p->next);
Node* q = p->next;
q->next = p;
p->next = NULL;
}
//recursion - 效率低
void PrintRecursion(Node* p) {
if (p == NULL) {
printf("PrintRecursion: ");
return;
}
PrintRecursion(p->next);
printf("%d ", p->data);
}
int main() {
head = NULL;
//头部插入一个节点
/*printf("How many numbers?\n");
int n, i, x;
scanf("%d", &n);
for (i = 0; i < n; i++) {
printf("Enter the number \n");
scanf("%d", &x);
InsertHead(x);
Print();
}*/
//任意位置插入节点
Insert(2, 1);
Insert(4, 2);
Insert(6, 3);
Insert(5, 4);
Print();
//任意位置删除节点
/*Delete(3);
Print();
Delete(1);
Print();*/
/*
反转链表
head -> 2 | 地址100 -> 4 | 地址200 -> 6 | 地址150 -> 5 | 地址250 -> NULL
NULL <- 2 | 地址100 <- 4 | 地址200 <- 6 | 地址150 <- 5 | 地址250 <- head
*/
Reverse();
Print();
ReverseRecursion(head);
Print();
PrintRecursion(head);
return 0;
}
2.3.2 循环链表
循环链表：
首尾相接的链表（表中最后一个结点的指针域指向头节点，整个链表形成一个环）
终止条件 不是判断p或p->next是否为空，而是判断是否等于头指针
优点：
从表中任一结点出发均可找到表中其他结点
使用更多的是尾指针
2.3.3 双链表
双链表：
每个结点中包含两个指针域
在单链表的每个结点里再增加一个指向其直接前驱的指针域，这样链表中就形成了有两个方向不同的链
特点：
对称性 p ->prior ->next = p = p ->next ->prior
双向循环链表：
- 让头结点的前驱指针指向链表的最后一个结点
- 让最后一个结点的后继指针指向头结点
typedef struct DuLNode { int data; struct LNode* prior; struct LNode* next; } DuLNode, * DuLinkList;
#define _CRT_SECURE_NO_WARNINGS *1
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
struct Node* prev;
}Node;
struct Node* head;
//创建节点
Node* GetNewNode(int x) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = x;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
void InsertAtHead(int x) {
Node* temp = GetNewNode(x);
if (head == NULL) {
head = temp;
return;
}
head->prev = temp;
temp->next = head;
head = temp;
}
void InsertAtTail(int x) {
Node* temp = GetNewNode(x);
if (head == NULL) {
head = temp;
return;
}
Node* temp1 = head;
while (temp1->next != NULL) {
temp1 = temp1->next;
}
temp1->next = temp;
temp->prev = temp1;
}
void Print() {
Node* temp = head;
printf("List: ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
void ReversePrint() {
Node* temp = head;
if (temp == NULL) return;
while (temp->next != NULL) {
temp = temp->next;
}
printf("Reverse: ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->prev;
}
}
int main() {
head = NULL;
InsertAtHead(2);
InsertAtHead(4);
InsertAtHead(6);
InsertAtTail(1);
InsertAtTail(3);
InsertAtTail(5);
Print();
ReversePrint();
return 0;
}
2.3.4 单链表、循环链表、双向链表的时间效率比较
2.3.5 链式存储结构优缺点
链式存储结构的优点
- 结点空间可以动态申请和释放;
- 数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素。
链式存储结构的缺点
- 存储密度小，每个结点的指针域需额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大。（存储密度=结点数据本身占用的空间/结点占用的空间总量。 一般地，存储密度越大，存储空间的利用率就越高，显然，顺序表的存储密度为1(100%)，而链表的存储密度小于1。）
- 链式存储结构是非随机存取结构。对任一结点的操作都要从头指针依指针链查找到该结点，这增加了算法的复杂度。
2.4 顺序表和链表比较
3、应用
-
线性表的合并
问题描述:
假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合A=AUB
La=(7,5,3,11) Lb=(2,6,3) --> La=(7,5,3,11,2,6)
//顺序表 #define _CRT_SECURE_NO_WARNINGS *1 #include <stdio.h> #include <stdlib.h> #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { int* elem; int length; int listsize; }SqList; int InitList_Sq(SqList* L) { L->elem = (int*)malloc(sizeof(int) * LIST_INIT_SIZE); if (!L->elem) exit(0); L->length = 0; //初始存储容量 L->listsize = LIST_INIT_SIZE; return 1; } int InsertList_Sq(SqList* L, int i, int e) { if (i<1 || i>L->length + 1) return -1; if (L->length >= L->listsize) { int* newbase = (int*)realloc(L->elem, sizeof(int) * (L->listsize + LISTINCREMENT)); if (!newbase) return -1; L->elem = newbase; L->listsize += LISTINCREMENT; } int* p = &(L->elem[i - 1]); int* q = &(L->elem[L->length - 1]); for (q; p <= q; --q) *(q + 1) = *q; *p = e; ++L->length; return 1; } int LocateElem(SqList* L, int e) { int j = 1; for (j; j < L->length + 1; j++) { if (L->elem[j - 1] == e) { return 1; } } return 0; } //A∪B 时间复杂度 O(La->length * Lb->length) int Union_Sq(SqList* La, SqList* Lb) { int i=1; for (i; i < Lb->length + 1; i++) { int elem_b = Lb->elem[i - 1]; if (!LocateElem(La, elem_b)) { InsertList_Sq(La, La->length + 1, elem_b); } } } void Print(SqList* L) { int i; printf("List: "); for (i = 0; i < L->length; i++) { if (i == L->length - 1) { printf("%d", L->elem[i]); } else { printf("%d, ", L->elem[i]); } } printf("\n"); } int main() { SqList La, Lb, Lc; InitList_Sq(&La); InsertList_Sq(&La, 1, 7); InsertList_Sq(&La, 2, 5); InsertList_Sq(&La, 3, 3); InsertList_Sq(&La, 4, 11); Print(&La); InitList_Sq(&Lb); InsertList_Sq(&Lb, 1, 2); InsertList_Sq(&Lb, 2, 6); InsertList_Sq(&Lb, 3, 3); Print(&Lb); Union_Sq(&La, &Lb); Print(&La); return 0; } -
有序表的合并
问题描述:
已知线性表La 和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。
La=(1,7,8) Lb=(2,4, 6,8,10,11) --> Lc=(1,2,4,6,7,8,8,10,11)
//顺序表 #define _CRT_SECURE_NO_WARNINGS *1 #include <stdio.h> #include <stdlib.h> #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { int* elem; int length; int listsize; }SqList; int InitList_Sq(SqList* L) { // 构造一个空的线性表L L->elem = (int*)malloc(sizeof(int) * LIST_INIT_SIZE); // 存储分配失败 if (!L->elem) exit(0); // 空表长度为0 L->length = 0; //初始存储容量 L->listsize = LIST_INIT_SIZE; return 1; } int InsertList_Sq(SqList* L, int i, int e) { if (i<1 || i>L->length + 1) return -1; if (L->length >= L->listsize) { int* newbase = (int*)realloc(L->elem, sizeof(int) * (L->listsize + LISTINCREMENT)); if (!newbase) return -1; L->elem = newbase; L->listsize += LISTINCREMENT; } int* p = &(L->elem[i - 1]); int* q = &(L->elem[L->length - 1]); for (q; p <= q; --q) *(q + 1) = *q; *p = e; ++L->length; return 1; } //时间复杂度 O(La->length + Lb->length) //空间复杂度 O(La->length + Lb->length) void Merge(SqList La, SqList Lb, SqList* Lc) { int* pa = La.elem; int* pb = Lb.elem; Lc->length = Lc->listsize = La.length + Lb.length; int* pc = Lc->elem = (int*)malloc(Lc->listsize * sizeof(int)); if (!Lc->elem) exit(0); int* pa_last = La.elem + La.length - 1; int* pb_last = Lb.elem + Lb.length - 1; while (pa <= pa_last && pb <= pb_last) { if (*pa <= *pb) { *pc++ = *pa++; } else { *pc++ = *pb++; } } while (pa <= pa_last) { *pc++ = *pa++; } while (pb <= pb_last) { *pc++ = *pb++; } } void Print(SqList* L) { int i; printf("List: "); for (i = 0; i < L->length; i++) { if (i == L->length - 1) { printf("%d", L->elem[i]); } else { printf("%d, ", L->elem[i]); } } printf("\n"); } int main() { SqList La, Lb, Lc; InitList_Sq(&La); InsertList_Sq(&La, 1, 1); InsertList_Sq(&La, 2, 7); InsertList_Sq(&La, 3, 8); Print(&La); InitList_Sq(&Lb); InsertList_Sq(&Lb, 1, 2); InsertList_Sq(&Lb, 2, 4); InsertList_Sq(&Lb, 3, 6); InsertList_Sq(&Lb, 4, 8); InsertList_Sq(&Lb, 5, 10); InsertList_Sq(&Lb, 6, 11); Print(&Lb); Merge(La, Lb, &Lc); Print(&Lc); return 0; }
参考：
教材：严蔚敏《数据结构》（C语言版）.pdf
视频：
https://www.bilibili.com/video/BV1nJ411V7bd?p=10&vd_source=a89593e8d33b31a56b894ca9cad33d33
https://www.bilibili.com/video/BV1Fv4y1f7T1/?p=19&spm_id_from=333.880.my_history.page.click&vd_source=a89593e8d33b31a56b894ca9cad33d33
