线性表（List）：零个或多个数据元素的有限序列。
首先它是一个序列。也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。
然后，线性表强调是有限的。
线性表应该有以下基本的操作
- InitList 初始化
- ListEmpty 判空
- ClearList 清空
- GetElem 返回线性表第i个位置的元素
- ListInsert 在线性表第i个位置插入元素
- ListDelete 删除线性表的第i个位置的元素
- ListLength 返回线性表的元素个数
顺序存储结构
可能有人第一次见线性表的顺序存储结构的时候，不禁怀疑：“这不就数组吗？这样定义好麻烦啊。有啥用啊？”
确实，在一些小体量的程序时，这样定义使用很麻烦，不如直接用数组。
但是这样封装起来后，程序就会很规范，虽然代码看上去很臃肿。
另外要实现的功能：
- 对于已排好序的线性表，删除所有重复元素的算法。
- 线性表“逆置”算法。
- 线性表循环左移/右移 k 位的算法。
- 合并两个已排好序的线性表的算法
下面是代码，结合注释理解
点击查看代码
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxlenglth 1000
#define OK 1
#define ERROR 0
using namespace std;
typedef int Elemtype;
typedef int Status;
typedef int Position;
struct SeqList
{
Elemtype data[maxlenglth];
int lenth;
};// 线性表的定义
Status Display(SeqList L);//打 印
SeqList InitList();// 初始化
Position End(SeqList L); // 返回最后的位置
Status Insert(Elemtype t, Position p, SeqList &L); // 在位置p插入元素t
Status Delete(Elemtype t, SeqList &L); //删除所有元素t
Status Sort(SeqList &L); //排序
Status Unique(SeqList &L); //对排完序去重
Status ReverseList(SeqList &L); //翻转（逆置）
Status Merge(SeqList &L1, SeqList L2); //合并两个排好序的
Status Move(SeqList &L, int flag, int step); //移动
int main()
{
// basic test
int n1, n2;
SeqList L1 = InitList();
SeqList L2 = InitList();
cout << "please input L1's lenth:"; cin >> n1;
cout << "please input L1's data:" << "\n";
for(int i = 1; i <= n1; i ++ )
{
int x; cin >> x;
Insert(x, L1.lenth + 1, L1);
}
Display(L1);
cout << "----Delete----" << "\n";
Elemtype temp;
cin >> temp;
Delete(temp, L1);
Display(L1);
cout << "----Sorted----" << "\n";
Sort(L1);
Display(L1);
cout << "----Uniqued----" << "\n";
Unique(L1);
Display(L1);
// merge test
cout << "please input L2's lenth:"; cin >> n2;
cout << "please input L2's data:" << "\n";
for(int i = 1; i <= n2; i ++ )
{
int x; cin >> x;
Insert(x, L2.lenth + 1, L2);
}
Display(L2);
cout << "----Merged----" << "\n";
Merge(L1, L2);
Display(L1);
// move test
int flag, step;
cout << "left(1) right(0):"; cin >> flag;
cout << "move step:"; cin >> step;
Move(L1, flag, step);
Display(L1);
cin >> n1;
return 0;
}
Status Display(SeqList L)
{
for(int i = 1; i <= L.lenth; i ++ ) cout << L.data[i] << " \n"[i == L.lenth];
}
SeqList InitList()
{
SeqList List;
List.lenth = 0;
return List;
}
Position End(SeqList L)
{
return L.lenth;
}
Status Insert(Elemtype t, Position p, SeqList &L)
{
if(L.lenth + 1 == maxlenglth)
{
cout << "Full list!" << "\n";
return 1;
}
if(p > L.lenth + 1 || p < 1)
{
cout << "Invalid Position!" << "\n";
return 1;
}
L.lenth += 1;
for(int i = L.lenth; i > p; i -- )
{
L.data[i] = L.data[i - 1];
}
L.data[p] = t;
return 0;
}
Status Delete(Elemtype t, SeqList &L)
{
Position idx = 0;
for(int i = 1; i <= L.lenth; i ++ )
{
if(L.data[i] != t)
{
idx ++;
L.data[idx] = L.data[i];
}
}
L.lenth = idx;
return 0;
}
Status Sort(SeqList &L)
{
sort(L.data + 1, L.data + L.lenth + 1);
return 0;
}
Status Unique(SeqList &L)
{
Position idx = 0;
Elemtype last = 0;
for(int i = 1; i <= L.lenth; i ++)
{
if(i == 1)
{
last = L.data[i];
idx ++;
L.data[idx] = L.data[i];
}else
{
if(last != L.data[i])
{
idx ++;
L.data[idx] = L.data[i];
last = L.data[i];
}
}
}
L.lenth = idx;
return 0;
}
Status ReverseList(SeqList &L)
{
for(int i = 1, j = L.lenth; i < j; i ++, j -- )
{
swap(L.data[i], L.data[j]);
}
return 0;
}
Status Merge(SeqList &L1, SeqList L2)
{
if(L1.lenth + L2.lenth + 1 >= maxlenglth)
{
cout << "Overflow!" << "\n";
return 1;
}
for(int i = L2.lenth + 1, j = 1; j <= L1.lenth; j ++ , i ++)
{
L2.data[i] = L1.data[j];
}
Position idx = 0;
Position i, j;
for(i = 1, j = L2.lenth + 1; i <= L2.lenth && j <= L1.lenth + L2.lenth;)
{
if(L2.data[i] <= L2.data[j])
{
idx ++;
L1.data[idx] = L2.data[i];
i ++;
}else
{
idx ++;
L1.data[idx] = L2.data[j];
j ++;
}
}
while(i <= L2.lenth)
{
idx ++;
L1.data[idx] = L2.data[i];
i ++;
}
while(j <= L2.lenth + L1.lenth)
{
idx ++;
L1.data[idx] = L2.data[j];
j ++;
}
L1.lenth += L2.lenth;
return 0;
}
Status Move(SeqList &L, int flag, int step)
{
static SeqList temp = InitList();
temp.lenth = L.lenth;
if(temp.lenth == 0)
{
return 1;
}
for(int i = 1; i <= temp.lenth; i ++ )
{
temp.data[i] = L.data[i];
}
step = step % L.lenth;
if(flag == 0)
{
flag = 1;
}else
{
flag = -1;
}
for(int i = 1; i <= temp.lenth; i ++ )
{
int j = i + flag * step;
if(j > temp.lenth)
{
j -= temp.lenth;
}
if(j < 1)
{
j += temp.lenth;
}
L.data[j] = temp.data[i];
}
return 0;
}
链式存储结构
关于链表，有三种经典类型：单链表，双向链表，循环链表
而每种类型又有很多考法
但其核心都是指针域的用法
另外要实现的功能：
- 对于已排好序的线性表，删除所有重复元素的算法。
- 线性表“逆置”算法。
- 线性表循环左移/右移 k 位的算法。
- 合并两个已排好序的线性表的算法
点击查看代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#define OK 0
#define ERROR 1
using namespace std;
typedef int Elemtype;
typedef int Status;
struct Node{
Elemtype data;
Node * next;
};//链表定义
typedef Node * Position;
typedef Node * LIST;
void Creat(LIST head,int size);//创建
void ForwardInsert(LIST head,Elemtype x);//头插
void BackInsert(LIST head,int x);//尾插
void Travel(LIST head);//遍历
Status IsEmpty(LIST head);//判空
void AllDelete(LIST head);//删除
void SomeDataDelete(LIST head,Elemtype x);//删除一个数
void SomeDataInsert(LIST head,Elemtype x,int num);//在某位置插入一个数
void Sort(LIST head, int (*cmp)(Elemtype, Elemtype));//冒泡排序
int Ascend(Elemtype x, Elemtype y);//升序
int Descend(Elemtype x, Elemtype y);//降序
Position Locate(Elemtype x, LIST head);
void Unique(LIST head);//去重
Status Reverse(LIST head);//翻转
Status Move(LIST head, int flag, int step);//循环移动
Status Merge(LIST head1, LIST head2);//合并两个排好序的链表
int Len(LIST head);//求链表长
void MergeTest();//合并的测试
int main()
{
LIST head = (LIST)malloc(sizeof(Node));//头节点
head->next = NULL;
int num, i;
Elemtype temp;
cout << "list num:";
cin >> num;
Creat(head,num);
Travel(head);
cout << "Insert forwarddata:";//头插
cin >> temp;
ForwardInsert(head,temp);
Travel(head);
cout << "Insert backdata:";//尾插
cin >> temp;
BackInsert(head,temp);
Travel(head);
cout << "Somedata delete:";//删除
cin >> temp;
SomeDataDelete(head,temp);
Travel(head);
cout << "SomeDataInsert:(data and which):"; //某一位置插入某个数（BUG不可尾插）
cin >> temp >> i;
SomeDataInsert(head,temp,i);
Travel(head);
// 排序测试
cout << "----Sorted----" << "\n";
Sort(head,Descend);
Travel(head);
//去重测试
cout << "----Uniqued----" << "\n";
Unique(head);
Travel(head);
// 翻转测试
cout << "----Reversed----" << "\n";
Reverse(head);
Travel(head);
// 循环左(右)移测试
cout << "----Move----" << "\n";
int flag ,step;
cout << "(right, left)(0,1)---(step)" << "\n";
cin >> flag >> step;
Move(head, flag, step);
Travel(head);
// 合并测试
MergeTest();
AllDelete(head);
Travel(head);
free(head);//free掉头节点
return 0;
}
void MergeTest()
{
int num;
cout << "----Merge----" << "\n";
LIST h1 = (LIST)malloc(sizeof(Node));
h1->next = NULL;
cout << "list1 num:";cin >> num;
Creat(h1,num);
Sort(h1, Descend);
LIST h2 = (LIST)malloc(sizeof(Node));
h2->next = NULL;
cout << "list2 num:";cin >> num;
Creat(h2,num);
Sort(h2, Descend);
Merge(h1, h2);
cout << "Merged list:" << "\n";
Travel(h1);
AllDelete(h1);
free(h1);
free(h2);
}
Status Merge(LIST head1, LIST head2)
{
LIST p1 = head1->next, p2 = head2->next;
LIST temp = head1;
while(p1 != NULL && p2 != NULL)
{
if(p1->data < p2->data)
{
temp->next = p1;
p1 = p1->next;
}else
{
temp->next = p2;
p2 = p2->next;
}
temp = temp->next;
}
while(p1 != NULL)
{
temp->next = p1;
p1 = p1->next;
temp = temp->next;
}
while(p2 != NULL)
{
temp->next = p2;
p2 = p2->next;
temp = temp->next;
}
temp->next = NULL;
return OK;
}
Status Move(LIST head, int flag, int step)
{
int len = Len(head);
step = step % len;
if(step == 0)
{
return OK;
}
if(flag == 0)
{
step = len - step;
}
LIST p, q, s;
p = q = s = head;
p = p->next;
int idx = 0;
while(s->next != NULL)
{
idx ++;
s = s->next;
if(idx == step)
{
q = s;
}
}
head->next = q->next;
s->next = p;
q->next = NULL;
return OK;
}
int Len(LIST head)
{
LIST p = head;
int cnt = 0;
while(p->next != NULL)
{
cnt ++;
p = p->next;
}
return cnt;
}
void Unique(LIST head)
{
Elemtype last;
LIST p, q;
p = head->next;
if(p == NULL || p->next == NULL)
{
return;
}
last = p->data;
q = p->next;
while(q != NULL)
{
if(q->data == last)
{
p->next = q->next;
free(q);
if(p->next == NULL)
{
q = NULL;
}else
{
q = p->next;
}
}else
{
last = q->data;
q = q->next;
p = p->next;
}
}
}
Status Reverse(LIST head)
{
LIST p, q, s;
p = q = s = head->next;
q = p->next;
while(q != NULL)
{
p->next = q->next;
q->next = s;
s = q;
q = p->next;
}
head->next = s;
return OK;
}
Position Locate(Elemtype x, LIST head)
{
Position p = head;
while(p->next != NULL)
{
if(p->data == x)
{
return p;
}else
{
p = p->next;
}
}
return p;/* 如果没有找到 */
}
int Descend(Elemtype x, Elemtype y)
{
return x > y;
}
int Ascend(Elemtype x, Elemtype y)
{
return x < y;
}
void Sort(LIST head, int(*cmp)(Elemtype, Elemtype))
{
if(head->next == NULL)
{
cout << "Empty Node!\n";
return;
}
if(head->next->next==NULL)
{
cout << "Only one element!\n";
return;
}
LIST p1;
LIST p2;
for (p1 = head->next; p1->next != NULL; p1 = p1->next)
{
for (p2 = p1->next; p2!=NULL; p2 = p2->next)
{
if ((*cmp)(p1->data, p2->data))
{
swap(p1->data, p2->data);
}
}
}
}
void Creat(LIST head, int size)
{
LIST p = head;
for(int i = 1;i <= size; i ++)
{
LIST newnode =(LIST)malloc(sizeof(Node));
newnode->next = NULL;
cin >> newnode->data;
p->next = newnode;
p = newnode;
}
}
void ForwardInsert(LIST head, Elemtype x)
{
LIST newhead = (LIST)malloc(sizeof(Node));
newhead->data = x;
newhead->next = head->next;
head->next = newhead;
return;
}
void Travel(LIST head)
{
LIST p = head;
while(p->next != NULL)
{
p = p->next;
cout << p->data << " ";
}
cout << "\n";
return;
}
void BackInsert(LIST head, Elemtype x)
{
LIST p = head;
LIST back = (Node*)malloc(sizeof(Node));
back->next = NULL;
back->data = x;
while(p->next != NULL)
{
p = p->next;
}
p->next = back;
return;
}
Status IsEmpty(LIST head)
{
if(head->next == NULL)
{
cout << "is Empty!" << "\n";
return OK;
}else
{
cout << "not Empty!" << "\n";
return ERROR;
}
}
void AllDelete(LIST head)
{
LIST p = head->next;
LIST temp = head;
while(p != NULL)
{
temp = p;
p = p->next;
free(temp);
}
head->next = NULL;
return;
}
void SomeDataDelete(LIST head, Elemtype x)
{
LIST p = head->next;
LIST last = head;
LIST temp = NULL;
while(p != NULL)
{
if(temp != NULL)
{
free(temp);
temp = NULL;
}
if(p->data == x)
{
last->next = p->next;
temp = p;
}else
{
last = last->next;
}
p = p->next;
}
return;
}
void SomeDataInsert(LIST head,Elemtype x,int num)
{
LIST p = head;
LIST last = head;
int idx = 0;
while(p->next != NULL)
{
p = p->next;
idx ++;
if(idx == num)
{
LIST NewNode = (LIST)malloc(sizeof(Node));
NewNode->data = x;
last->next = NewNode;
NewNode->next = p;
}
last = last->next;
}
}
静态链表
静态链表其实就是将指针域用游标来代替指针。
游标： Cursor
所有它的大小也取决于最先开始建立的数组大小。
这里插入一张《大话数据结构》的图片
实现基本功能和逆置的静态链表：
点击查看代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define OK 1
#define ERROR 0
#define MAXSIZE 1000
using namespace std;
typedef int Status;
typedef int ElemType;
typedef struct
{
ElemType data;
int cur; /* 游标(Cursor) ，为0时表示无指向 */
} Component,StaticLinkList[MAXSIZE];
/* 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，"0"表示空指针 */
Status InitList(StaticLinkList space)
{
for(int i = 0; i < MAXSIZE - 1; i ++ )
space[i].cur = i + 1;
space[MAXSIZE - 1].cur = 0; /* 目前静态链表为空，最后一个元素的cur为0 */
return OK;
}
/* 若备用空间链表非空，则返回分配的结点下标，否则返回0 */
int Malloc_SSL(StaticLinkList space)
{
int i = space[0].cur; /* 当前数组第一个元素的cur存的值 */
/* 就是要返回的第一个备用空闲的下标 */
if (space[0]. cur)
space[0]. cur = space[i].cur; /* 由于要拿出一个分量来使用了， */
/* 所以我们就得把它的下一个 */
/* 分量用来做备用 */
return i;
}
/* 将下标为k的空闲结点回收到备用链表 */
void Free_SSL(StaticLinkList space, int k)
{
space[k].cur = space[0].cur; /* 把第一个元素的cur值赋给要删除的分量cur */
space[0].cur = k; /* 把要删除的分量下标赋值给第一个元素的cur */
}
/* 初始条件：静态链表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(StaticLinkList L)
{
int j = 0;
int i = L[MAXSIZE-1].cur;
while(i)
{
i = L[i].cur;
j ++;
}
return j;
}
/* 在L中第i个元素之前插入新的数据元素e */
Status ListInsert(StaticLinkList L, int i, ElemType e)
{
int j, k, l;
k = MAXSIZE - 1; /* 注意k首先是最后一个元素的下标 */
if (i < 1 || i > ListLength(L) + 1)
return ERROR;
j = Malloc_SSL(L); /* 获得空闲分量的下标 */
if (j)
{
L[j].data = e; /* 将数据赋值给此分量的data */
for(l = 1; l <= i - 1; l++) /* 找到第i个元素之前的位置 */
k = L[k].cur;
L[j].cur = L[k].cur; /* 把第i个元素之前的cur赋值给新元素的cur */
L[k].cur = j; /* 把新元素的下标赋值给第i个元素之前元素的ur */
return OK;
}
return ERROR;
}
/* 删除在L中第i个数据元素 */
Status ListDelete(StaticLinkList L, int i)
{
int j, k;
if (i < 1 || i > ListLength(L))
return ERROR;
k = MAXSIZE - 1;
for (j = 1; j <= i - 1; j++)
k = L[k].cur;
j = L[k].cur;
L[k].cur = L[j].cur;
Free_SSL(L, j);
return OK;
}
Status ListTraverse(StaticLinkList L)
{
int j = 0;
int i = L[MAXSIZE-1].cur;
while(i)
{
cout << L[i].data << " ";
i=L[i].cur;
j++;
}
cout << "\n";
return OK;
}
Status Reverse(StaticLinkList L)
{
int i = L[MAXSIZE-1].cur;
int j = 0;
int k;
while(i)
{
k = L[i].cur;
L[i].cur = j;
j = i;
i = k;
}
L[MAXSIZE-1].cur = j;
}
int main()
{
StaticLinkList L;
Status i;
i=InitList(L);
cout << "--- Creat ---" << "\n";
cout << "num: ";
int n;cin >> n;
for(int i = 1; i <= n ; i ++ )
{
int e; cin >> e;
ListInsert(L, i, e);
}
ListTraverse(L);
cout << "--- Reverse ---" << "\n";
Reverse(L);
ListTraverse(L);
return 0;
}
说到静态链表，就不得不说它的一个应用：邻接表。
邻接表可以用作图的存储，可以存储有向图或无向图
-
idx 游标，可认为是第idx的意思
-
h[N] 有N个顶点，每个点都可能会连有边，h[i]存储顶点i的所有出边指向的点的集合
-
e[N] 存储该节点的出边指向的顶点
-
ne[N] 存储该节点的下一个节点的游标
-
w[N] 存储该节点代表的边的权重
int h[N], e[N], ne[N], idx;
// 添加一条边a->b
void add(int a, int b) //a到b添加一条边 事实上是 头插法
{
e[idx] = b;//节点idx存储顶点b
ne[idx] = h[a];//将节点idx指向的节点 指向 a顶点所指向的节点（头节点）
h[a] = idx ++ ; //将头指针的指向为新的头节点
}
// 初始化
idx = 0;
memset(h, -1, sizeof h); //初始化 所有的头指针指向-1
//这样当遍历的时侯,因为游标不可能出现-1，就可以当作遍历终止条件
参考文献
- 程杰. 大话数据结构：溢彩加强版[M]. 北京: 清华大学出版社, 2020.