技術文章 » 資料結構：線性表

資料結構：線性表

2022-09-22 21:01:30

線性表

線性表（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.