每個單連結清單都有一個頭指針,有時為了友善操作,還會給連結清單增加一個不存放資料的頭節點(也可以存放表長等資訊)
單連結清單的基本操作
//單連結清單的基本操作
#include <iostream>
#define ElemType int
//連結清單L,L表示該連結清單的名稱或連結清單首位址,又稱為頭指針
typedef struct Lnode {
ElemType data;//每個節點包含兩個域,資料域和指針域
struct Lnode* next;
}Lnode,*LinkList;//将結構體等價于類型名Lnode,指針Linklist
//LinkList為struct Lnode*的别名。Lnode為struct Lnode的别名。
//1.初始化
//指建構一個空表,先建立一個頭節點,不存儲資料,然後令其指針域為空
bool InitList_L(LinkList& L) {
//L表示節點,也即指節點的位址,L->data為節點資料,L->next為下個節點的位址
L = new Lnode;//生成新節點作為頭節點,用頭指針L指向頭節點
if (!L)
return false;
L->next = NULL;//頭節點的指針域置空
return true;
}
//建立
//建立單連結清單分為頭插法和尾插法兩中,頭插法指每次把新節點插入到頭節點後面,尾插法是指每次把新節點連結到連結表的尾部
//頭插法
void CreateList_H(LinkList &L) {
int n;
LinkList s;
L = new Lnode;
L->next = NULL;
std::cout << "請輸入元素個數n" << std::endl;
std::cin >> n;
std::cout << "請依次輸入n個元素" << std::endl;
std::cout << "頭插法建立連結清單"<<std::endl;
while (n--) {
s = new Lnode;
std::cin >> s->data;
s->next = L->next;
L->next = s;
}
}
//尾插法
void CreateList_R(LinkList &L) {
int n;
LinkList s, r;
L = new Lnode;
L->next = NULL;//建立一個帶頭節點的空連結清單
r = L;//尾指針r指向頭節點
std::cout << "請輸入元素個數n" << std::endl;
std::cin >> n;
std::cout << "請依次輸入n個元素" << std::endl;
std::cout << "尾插法建立單連結清單" << std::endl;
while (n--) {
s = new Lnode;
std::cin >> s->data;
s->next = NULL;
r->next = s;//将新節點s插入到尾節點r之後,将r
r = s; //指向新的尾節點s
}
}
//取值
//一個連結清單是由頭指針辨別的,一旦頭指針改動或丢失,這個連結清單就不完整或者就找不到了。
//是以連結清單頭指針不能輕易改動。如果需要指針移動,可定義一個指針變量進行移動。
bool GetElem_L(LinkList L, int i, int& e) {
//在帶頭節點的單連結清單L中查找第i個元素,用e記錄L中第i個元素的值
int j;
LinkList p;
p = L->next;//p指向第一個資料節點
j = 1;//j為計時器
while (j < i && p) {//直到p指向第i個元素或p為空
p = p->next;
j++;
}
if (!p || j > i)
return false;
e = p->data;
return true;
}
//查找
//在單連結清單中查找是否存在元素e
bool LocateElem_L(LinkList L,int e) {
LinkList p;
p = L->next;
while (p && p->data != e)
p = p->next;
if (!p)
return false;
return true;
}
//插入
//在L連結清單第i個元素前插入數值e
bool ListInsert_L(LinkList L,int i,int e) {
int j = 0;
LinkList s, p;
p = L;
while (p && j < i - 1) {
p = p->next;
j++;
}
if (!p || j > i - 1)
return false;
s = new Lnode;
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
//删除
bool ListDelete_L(LinkList &L,int i) {
//删除第i個元素
LinkList p, q;
int j = 0;
p = L;
while ((p->next)&&(j<i-1)) {
p = p->next;
j++;
}
if (!(p->next) || (j > i - 1))
return false;
q = p->next;//臨時儲存被删節點的位址以備釋放空間
p->next = q->next;
delete q;
return true;
}