数据结构：线性表

线性表

线性表（List）：零个或多个数据元素的有限序列。

首先它是一个序列。也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。

然后，线性表强调是有限的。

顺序表与单链表是线性表的两种最基本的存储结构，而静态链表是两者的完美结合，是系统进行动态存储分配的方法基础。线性表的这三种存储结构不但是其他数据结构（如树形结构、图型结构、集合等）存储方法的重要基础，同时本身也有广泛的应用。

线性表应该有以下基本的操作

• InitList 初始化
• ListEmpty 判空
• ClearList 清空
• GetElem 返回线性表第i个位置的元素
• ListInsert 在线性表第i个位置插入元素
• ListDelete 删除线性表的第i个位置的元素
• ListLength 返回线性表的元素个数

---

顺序存储结构

可能有人第一次见线性表的顺序存储结构的时候，不禁怀疑：“这不就数组吗？这样定义好麻烦啊。有啥用啊？”

确实，在一些小体量的程序时，这样定义使用很麻烦，不如直接用数组。

但是这样封装起来后，程序就会很规范，虽然代码看上去很臃肿。

---

另外要实现的功能：

• 对于已排好序的线性表，删除所有重复元素的算法。
• 线性表“逆置”算法。
• 线性表循环左移/右移 k 位的算法。
• 合并两个已排好序的线性表的算法

下面是代码，结合注释理解

点击查看代码

#include 
#include 
#include 
#include 

#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 
#include 
#include 
#include 
#include 

#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 
#include 
#include 
#include 

#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.

• 线性表
• 顺序存储结构
• 链式存储结构
• 静态链表
• 参考文献

__EOF__