# 線性表
## 概念
線性表是具有相同特性的數據元素的一個有限序列。
### 邏輯特征
線性表中的元素位置是有序的，這種位置關系構成了一種線性關系，因此線性表是一個線性結構，即對于至少含有一個數據元素的線性表，除起始元素外均有且僅有一個前驅，除終端元素外均有且僅有一個后繼。若線性表中的元素按照某種順序排列，則稱該線性表為有序表。
### 存儲結構
有順序和鏈式兩種存儲結構，分別稱為順序表和鏈表。鏈表的每個節點包含數據域和指針域，第一個節點的存儲位置稱為頭指針，如果鏈表帶有頭結點，那頭指針為頭結點的地址，否者為起始節點。
## 順序表
定義
```c
#define MaxSize 50
typedef struct
{
ElemType data[MaxSize];
int length;
}SqList;
```
初始化順序表
```C
void InitList(SqList &L)
{
L.length = 0;
}
```
求指定位置元素
```C
int GetElem(SqList L, int i, ElemType &e)
{
if(i < 1 || i > L.length)
return 0;
e = L.data[i-1];
return 1;
}
```
按元素查找
```C
int LocateElem(SqList L, int &n, ElemType e)
{
if(L == NULL)
return 0;
int i = 0;
while(L.data[i] != e && i < L.length)
i++;
if(i == L.length)
return 0;
n = i+1;
return 1;
}
```
插入數據元素（插到第 i 個位置上）
```C
int ListInsert(SqList &L, ElemType e, int i)
{
if(i < 1 || i > L.length+1)
return 0;
L.length++;
int j;
for(j = L.length-1; j >= i; j--)
L.data[j] = L.data[j-1];
L.data[j] = e;
return 1;
}
```
刪除數據元素
```C
int ListDelete(SqList &L, int i, ElemType &e)
{
if(i < 1 || i > L.length)
return 0;
e = L.data[i-1];
for(int j = i-1; j < L.length-1; j++)
L.data[j] = L.data[j+1];
L.lenght--;
return 1;
}
```
有序順序表的歸并算法
```C
void MergeList(SqList L1, SqList L2, SqList &L3)
{
int i = 0, j = 0, k = 0;
while(i < L1.length && j < L2.length){
if(L1.data[i] < L2.data[j]){
L3.data[k] = L1.data[i];
k++; i++;
}else if(L1.data[i] > L2.data[j]){
L3.data[k] = L2.data[j];
k++; j++;
}else{
L3.data[k] = L1.data[i];
k++; i++; j++;
}
}
while(i < L1.length){
L3.data[k] = L1.data[i];
k++; i++;
}
while(j < L2.length){
L3.data[k] = L1.data[j];
k++; j++;
}
L3.length = k;
}
```
## 單鏈表
定義
```C
typedef struct LNode{
ElemType data;
LNode *next;
}LinkList;
```
頭插法建立單鏈表（次序與原來次序相反）
```C
void CreateListF(LinkList *&L, ElemType a[], int n)
{
LinkList *s; int i;
L = (LinkList *)malloc(sizeof(LinkList)); //創建頭結點
L->next = NULL;
for(i = 0, i < n, i++){
s = (LinkList *)malloc(sizeof(LinkList));
s->data = a[i];
s->next = L->next;
L->next= s;
}
}
```
尾插法建立單鏈表（次序與原來次序相同）
```C
void CreateListR(LinkList *&L, ElemType a[], int n)
{
LinkList *s, *r; int i;
L = (LInkList *)malloc(sizeof(LinkList));
L->next = NULL;
r = L;
for(i=0, i<n, i++){
s = (LinkList *)malloc(sizeof(LinkList));
s->data = a[i];
r->next = s;
r = s;
}
r->next = NULL;
}
```
按元素查找
```C
int LocateElem(LinkList *L, ElemType e)
{
LinkList *p = L->next;
int i = 1;
while(p!=NULL && p->data!=e){
p = p->next;
i++;
}
if(p==NULL)
return 0;
else
return i;
}
```
將 e 插入到單鏈表的第 i 個節點位置上
```C
int InsertElem(LinkList *&L, ElemType e, int n)
{
LinkList *p = L, *s; // p 為第一個節點位置的前一個節點
int j = 0;
while(p!=NULL && j<n-1){
p = p->next;
j++;
}
if(p!=NULL){
s = (LinkList *)malloc(sizeof(LinkList));
s->data = e;
s->next = p->next;
p->next = s;
return 1;
}
else
return 0;
}
```
刪除第 i 個節點位置上的元素
```C
int DeleteElem(LinkList *&L, ElemType &e, int n)
{
LinkList *p = L, *q; // p 為第一個節點位置的前一個節點
int j = 0;
while(p!=NULL && j<n-1){
p = p->next;
j++;
}
if(p!=NULL && p->next!=NULL){
q = p->next;
p->next = q->next;
free(q);
return 1;
}
else
return 0;
}
```
有序單鏈表的歸并（新建單鏈表）
```C
void MergeList1(LinkList *L1, LinkList *L2, LinkList *&L3)
{
LinkList *s1 = L1->next, *s2 = L2->next, *r, *s;
L3 = (LinkList *)malloc(sizeof(LinkList));
L3->next = NULL;
r = L3;
while(s1!=NULL && s2!=NULL){
if(s1->data < s2->data){
s = (LinkList *)malloc(sizeof(LinkList));
s->data = s1->data;
r->next = s;
r = s; s1 = s1->next;
}else if(s1->data > s2->data){
s = (LinkList *)malloc(sizeof(LinkList));
s->data = s2->data;
r->next = s; s2 = s2->next;
r = s;
}else{
s = (LinkList *)malloc(sizeof(LinkList));
s->data = s1->data;
r->next = s;
r = s; s1 = s1->next; s2 = s2->next;
}
}
if(s2!=NULL)
s1 = s2;
while(s1!=NULL){
s = (LinkList *)malloc(sizeof(LinkList));
s->data = s1->data;
r->next = s;
r = s; s1 = s1->next;
}
r->next = NULL;
}
```
有序單鏈表的歸并（要求空間復雜度為 O(1) ，即舍棄原來的兩個單鏈表）
```C
void MergeList(LinkList *L1, LinkList *L2, LinkList *&L3)
{
LinkList *p = L1->next, *q = L2->next;
L3 = (LinkList *)malloc(sizeof(LinkList));
L3 = L1;
free(L2);
r = L3;
while(p!=NULL && q!=NULL){
if(p->data < q->data){
r->next = p;
p = p->next;
}
else if(p->data > q->data){
r->next = q;
q = q->next;
}
else{
r->next = p;
p = p->next;
q = q->next;
}
}
if(q!=NULL)
p = q;
r->next = p;
}
```
## 雙鏈表
雙鏈表頭尾不相接
定義
```C
typedef struct DLinkList{
ElemType data;
DLinkList *next;
DLinkList *prior;
}DLinkList;
```
頭插法建立雙鏈表
```C
void CreateDListF(DLinkList *&L, ElemType a[], int n)
{
DLinkList *s;
L = (DLinkList *)malloc(sizeof(DLinkList));
L->next = L->prior = NULL;
for(int i=0; i<n; i++){
s = (DLinkList *)malloc(sizeof(DLinkList));
s->data = a[i];
s->next = L->next;
if(L->next!=NULL)
L->next->prior = s;
L->next = s;
s->prior = L;
}
}
```
尾插法建立雙鏈表
```C
void CreateDListR(DLinkList *&L, ElemTyoe a[], int n)
{
DLinkList *s, *r;
L = (DLinkList *)malloc(sizeof(DLinkList));
L->next = L->prior = NULL;
r = L;
for(int i=0; i<n; i++){
s = (DLinkList *)malloc(sizeof(DLinkList));
s->data = a[i];
r->next = s;
s->prior = r;
r = s;
}
r->next = NULL;
}
```
查找指定元素節點
```C
int FindNode(DLinkList *L, ElemType e)
{
DLinkList *p = L->next;
int i = 1;
while(p!=NULL && p->data != e){
p = p->next;
i++;
}
if(p!=NULL)
return i;
else
return 0;
}
```
將 e 插入第 n 個節點位置
```C
int InsertNode(DLinkList *&L, ElemType e, int n)
{
DLinkList *p, *s;
int i = 0;
p = L;
while(p!=NULL && i<n-1){
p = p->next;
i++;
}
if(p!=NULL){
s = (DLinkList *)malloc(sizeof(DLinkList));
s->data = e;
s->next = p->next;
s->prior = p;
if(p->next!=NULL){
p->next->prior = s;
p->next = s;
}
return 1;
}
else
return 0;
}
```
刪除第 n 個節點位置的元素
```C
int DeleteNode(DLinkList *&L, ElemType e, int n)
{
DLinkList *p, *q;
int i = 0;
p = L;
while(p!=NULL && i<n-1){
p = p->next;
i++;
}
if(p!=NULL){
q=p->next;
if q==NULL;
return 0;
p->next = q->next;
if(q->next!=NULL)
q->next->prior = p;
free(q);
return 1;
}
else
return 0;
}
```
## 循環鏈表
定義
```C
typedef struct LNode{
ElemType data;
next LNode *next;
}LinkList;
```
頭插法建立循環鏈表
```C
void CreateListF(LinkList *&L, ElemType a[], int n)
{
LinkList *s;
int i;
L = (LinkList *)malloc(sizeof(LinkList));
L->next = L;
for(i=0; i<n; i++){
s = (LinkList *)malloc(sizeof(LinkList));
s->data = a[i];
s->next = L->next;
L->next = s;
}
}
```
尾插法建立循環鏈表
```C
void CreateListR(LinkList *&L, ElemType a[], int n)
{
LinkList *s, *r;
int i;
L = (LinkList *)malloc(sizeof(LinkList));
L->next = L;
r = L;
for(i=0; i<n; i++){
s = (LinkList *)malloc(sizeof(LinkList));
s->data = a[i];
r->next = s;
r = s;
}
r->next = L;
}
```
查找元素值為 e 的節點
```C
int FindNode(LinkList *L, ElemTpye e)
{
LinkList *p = L->next;
int i = 1;
while(p!=L && p->data = e){
p = p->next;
i++;
}
if(p==L)
return 0;
else
return i;
}
```
## 靜態鏈表
```C++
struct Node{
typename data; // 數據域
int next; // 存放下一個結點的數組下標
xxx; // 結點的某些性質
}
```
## 申請動態內存函數
### C 語言
malloc 函數：`typename* p=(typename*)malloc(sizeof(typename));`
對應的內存釋放函數 free ：`free(p);`
### C++
new 函數：`typename* p=new typename;`
對應的內存釋放函數 delete ：`delete(p);`
