一、插入操作
（一）按位序插入（帶頭結點）
ListInsert(&L,i,e)：插入操作，在表L的第i個位置上插入指定元素e，- 找到第i-1個結點，將新結點插入其后
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
//在第i個位置插插入元素e（帶頭結點）
bool ListInsert(LinkList &L, int i, ElemType e){
if(i<1)
return false;
LNode *p; //指標p指向當前掃描到的結點
int j=0; //當前p指向的是第幾個結點
p = L; //L指向頭結點，頭結點是第0個結點（不存資料）
while(p != NULL && j<i-1){ //回圈找到第i-1個結點
p = p -> next;
j++;
}
if( p == NULL) //i值不合法
return false;
//1.malloc申請新的結點空間
LNode *s = (LNode *)malloc(sizeof(LNode));
//2.將引數e存入新結點里面
s -> data = e;
//3.將s指向新結點e的next指標指向p結點next指向的位置
s -> next = p -> next;
//4.將p結點的next指標指向新的結點
p -> next = s; //將結點s連到p之后
return true;//插入成功
}
- 分析：
①、如果i=1（插在表頭）
- 注意：要先復制p結點next曾經指向的位置，然后再讓p結點next指向新的結點，順序不能顛倒，
- ②、如果i=3（插在表中）
while(p!=NULL && j<i-1){//回圈找到第2個結點
p = p -> next;
j++;
}
- ③、如果i=5（插在表尾）
- ④、如果i=6（i > Length）
- 運行動態圖:
（二）按位序插入（不帶頭結點）
ListInsert(&L,i,e)：插入操作，在表L的第i個位置上插入指定元素e，- 找到第i-1個結點，將新結點插入其后，
- 不存在“第0個”結點，因此i=1時需要特殊處理，
- ②、如果i>1…
1. 指定結點的后插操作
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
//后插操作：在p結點之后插入元素e
bool InsertNextNode(LNode *p, ElemType e){
if(p==NULL)
return false;
//1.malloc申請空間
LNode *s = (LNode *)malloc(sizeof(LNode));
if(s == NULL) //記憶體分配失敗
return false;z
//2.將資料元素e填到新結點當中
s -> data = e; //用結點s保存資料元素e
//3.將p的next指向下一個元素賦值給新資料元素e的next指向下一個元素
s -> next = p -> next;
//4.將p的next指向新資料元素e
p -> next = s; //將結點s連接到p之后
return true;
}
2. 指定結點的前插操作
- 如何找到p結點的前驅結點？
（1）通過傳入頭指標的方式實作
（2）通過復制插入位置的結點方式實作
二、洗掉操作
（一）按位序洗掉（帶頭結點）
ListDelete(&L,i,&e)：洗掉操作，洗掉表L中第i個位置的元素，并用e回傳洗掉元素的值，- 找到第 i-1 個結點，將其指標指向第i+1個結點，并釋放第i個結點
- 頭結點可以看作“第0個”結點
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
bool ListDelete(LinkList &L, int i, ElemType &e){
if(i<1)
return false'
LNode *p; //指標p指向當前掃描到的結點
int j=0; //當前p指向的是第幾個結點
p = L; //L指向頭結點，頭結點是第0個結點（不存盤資料）
while(p != NULL && j<i-1){ //回圈找到第i-1個結點
p = p->next;
j++;
}
if(p == NULL) //i值不合法
return false;
if(p -> next == NULL) //第i-1個結點之后已沒有其他結點
return false;
LNode *q = p -> next; //令q指向被洗掉結點
e = q -> data; //用e回傳元素的值
p -> next = q -> next; //將*q結點從鏈中“斷開”
free(q); //釋放結點的存盤空間
return true; //洗掉成功
}
- 洗掉的結點如果i=4：
（二）指定結點的洗掉
//洗掉指定結點 p
bool DeleteNode(LNode *p)
- 洗掉結點p，需要修改其前驅結點的 next 指標
1. 傳入頭指標，回圈尋找 p 的前驅結點
- 動態運行圖：
- 如果p是最后一個結點：
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/282663.html
標籤：其他