#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define TRUE 1
#define ERROR -1
#define FALSE -1
#define OVERFLOW -2
#define ElemType int
#define Status int
//線性單連結清單 初始化 插入 取出 頭插法 合并升序排列
//-------------------------------線性單連結清單
typedef struct LNode{ //封裝一個線性單連結清單
ElemType data; //資料域
struct LNode *next; //指針域
}LNode, *LinkList;//類型重定義struct LNode為Lnode,類型重定義 Lnode的*指針 為LinkList
Status InitList_L(LinkList &L) { //初始化線性連結清單
L = (LinkList)malloc(sizeof(LNode)); //新開辟記憶體,傳回指針L
L->next = Null;//L->//對于指針p p->a 被定義為 (*p).a (不成文的标準)
return TRUE;
}
Status GetElem_L(LinkList L,int i,ElemType &e){ //取出元素,i是序号,e為值
//L為帶頭結點的單連結清單的頭指針
//當第i個元素存在時,将值傳回給e,傳回TRUE, 否則FALSE
p = L->next; j = ;//初始化,p指向第一個結點,j為計數器
while (p && j<i) { //p指針非空,j計數器<i,是以循環的終點是i
p = p->next; ++j;//指針後移一個,計數器+1一個
}
if (!p || j>i) return FALSE;//第i個元素不存在
e = p->data;//取出第i個元素,值為e
return TRUE;
}//GetElem_L
Status ListInsert_L(LinkList &L, int i, ElemType e) { //在帶head的單連結清單L中第i個位置之前插入元素e
p = L; j = ;//p為指針,被插入的previous Node
while (p && j < i - ) { p = p->next; ++j; }//尋找第i個結點,指針下移,j最後停在i
if (!p || j>i) return FALSE;
s = (LinkList)malloc(sizeof(LNode));//生成新節點,開辟記憶體空間 傳回指針s,insert
s->data = e;//s->data域的指派 assignment
s->next = p->next;//指針操作 ,=右往左,指針 指向
p->next = s;
}
Status ListDelete_L(LinkList &L, int i, ElemType &e) { //在帶head的單連結清單L中第i個位置 删除元素e
p = L; j = ;//p為指針,被插入的previous Node
while (p && j < i - ) { p = p->next; ++j; }//尋找第i個結點,下标最後是i-1,指針下移,j最後停在i
if (p->next || j>i - ) return FALSE;//删除位置不合理
q = p->next; //q是被删除的節點
p->next = q->next;//P的next,指向q->next
e = q->data; //取出 值為e
free(q);//傳回值,釋放空間
}
LNode * LocateElem_L(LinkList L, ElemType e) { //在L中找到第一個值和e相同的結點,傳回其位址,若不存在,傳回空值NULL。
if (!L) return NULL;
p = L;
while (p&&p->data != e) { p = p->next };//if(!p) p=null;
return p;//時間複雜度O(n)
}
void CreateList_L(LinkList &L, int n) { //頭插法 生成單連結清單
//逆位序輸入n個元素的值,建立帶表頭結點的單鍊線性表L
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;//L->next表示頭結點的指針,先建立一個帶頭結點的單連結清單
for (i = n; i > ; --i) {
p = (LinkList)malloc(sizeof(LNode));
scanf(&p->data);//輸入元素值
p->next = L->next;//挪動 頭指針的後繼
L->next = p;//挪動 頭指針的後繼
}
}
void MergeList_L(LinkList &La, LinkList &Lb,) {
//已知La和Lb升序排列
//合并得到新的單連結清單Lc,Lc的元素也按值非遞減排列
pa = La->next;
pb = Lb->next;
q = La;//存放臨時指針,q就是pa的前驅元素,q必須始終作為pa的前驅元素
while (pa && pb) {
if (pa->data <= pb->data) {//如果小于=,pc指針指向pa
q = pa;//q下移
pa = pa->next;//pa下移
}
else {//如果>,pc指針指向pb
t = pb;// t 下移
pb = pb->next;//pb下移
t->next = pa;//t插入pa的前面
q->next = t;
q = t;//q必須始終作為pa的前驅元素,是以t指派給q
}//2個結合起來就是小者排前面,這個代碼寫的真差,不是人類看的,因為C在A和B隻見跳來跳去,臨時pc變量拆成2個就容易了解了
}
if (pb) q->next = pb;
}//MergeList_L
//-------雙向連結清單 Y
typedef struct LNode { //封裝 線性單連結清單
ElemType data; //資料域
struct LNode *next; //指針域
} *Link, *Position;//類型重定義struct LNode * 為Link,Link * 為 Position
Status MakeNode(Link &p, ElemType e){}
void FreeNode(Link &p)
typedef struct DuLNode { //封裝 雙向連結清單
ElemType data;
struct DuLNode *prior;//前驅
struct DuLNode *next;//後繼
}DuLNode, *DuLinkList;
//------靜态連結清單 X 使用數組實作連結清單,可以在沒有指針的程式設計語言中實作連結清單結構
#define MAX_SIZE 1000
typedef struct { //封裝 靜态連結清單
ElemType data;//資料
int cur; //遊标(Cursor)
} Component, StaticLinkList[MAX_SIZE]; //聲明為StaticLinkList[MAX_SIZE]
typedef Component SLinkList[MAX_SIZE];
Status InitList_SL(StaticLinkList &space) { //初始化靜态連結清單
int i;
//将一維數組space中各分量連結成一個備用連結清單,space[0].cur為頭指針。
//“0”表示空指針
for (i = ; i < MAX_SIZE - ; i++)
space[i].cur = i + ;
//頭遊标和尾遊标 的資料區不存放資料
//頭遊标儲存第一個沒有資料位置的遊标 尾遊标儲存第一個有資料位置的遊标
//最後一個有數值的分量的cursor遊标為0
//未使用的數組元素成為備用連結清單
//除了頭遊标和尾遊标 每個遊标儲存存放下一個節點的邏輯位置序号
space[MAX_SIZE - ].cur = ;//給最後的遊标指派
return TRUE;
}
int LocateElem_SL(SLinkList S, ElemType e) { //查找,傳回空閑分量的下标
//在靜态單鍊線性表L中查找第1個值為e的元素
//若找到,則傳回它在L中的依序,否則傳回0
i = S[].cur;//i模拟指針 ,i訓示表中第一個結點
while (i && S[i].data != e)//在表中順鍊查找
i = S[i].cur;//指針下移
return i;
}
int Malloc_SLL(StaticLinkList space) { //擷取目前空閑量的下标,傳回空閑分量的下标,未被使用,用getCur更好了解,
i = space[].cur;//i模拟指針 ,i訓示表中第一個結點
if(space[].cur) //非0,為0就是空連結清單,末尾
space[].cur = space[i].cur;//指針下移,空閑分量指針下移,0下标的遊标指派為i下标對應的遊标
return i;
}
void Free_SLL(SLinkList &space, int k) { //釋放節點
//将下标為k的空閑結點回收到備用連結清單
space[k].cur = space[].cur;
space[].cur = k;
}//Free_SLL
Status ListInsert(StaticLinkList L, int i, ElemType e) {
int j, k, l;//l是計數器
k = MAX_SIZE - ;//k表示數組的最後一個元素
if (i< || i>ListLength(L) + ) { //ListLength為計算連結清單長度的函數
return FALSE;
}
j = Malloc_SLL(L);//j表示空閑分量的下标,是目前節點下标指針
if (j)
{
L[j].data = e;//寫入資料
k = L[k].cur;//最後一個元素的遊标指向第一個元素
for (l = ; l <= i - ; l++) 找到第i個位置
{
k = L[k].cur;//傳回的是第i個下标節點的遊标
}
//執行插入後,指針的變化
L[j].cur = L[k].cur; //翻譯成連結清單 j->next = p->next 目前下标節點指針下移
L[k].cur = j;//翻譯成連結清單 p->next = j
return TRUE;
}
return TRUE;
}