4

数据结构：线性表 - 江水为竭

 1 year ago
source link: https://www.cnblogs.com/Az1r/p/16720710.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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

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

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

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

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

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

顺序存储结构

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

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

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

另外要实现的功能：

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

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

点击查看代码

highlighter- arduino
#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 位的算法。
  • 合并两个已排好序的线性表的算法

点击查看代码

highlighter- arduino
#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

所有它的大小也取决于最先开始建立的数组大小。

这里插入一张《大话数据结构》的图片

632c2a8b16f2c2beb14356e8.jpg

实现基本功能和逆置的静态链表：

点击查看代码

highlighter- cpp
#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] 存储该节点代表的边的权重

highlighter- cpp
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__


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK