數據結構:線性表
線性表
線性表(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.