單鏈表上的基本操作
1.頭插法建立單鏈表
T(n) = O(n)- 如果沒有設立頭結點，則每次插入新節點后，將結點的地址賦值給
L， - 生成單鏈表中資料元素的順序與插入順序相反，
LinkList list_HeadInsert(LinkList &L, int n)
{
LNode *p; int x;
L = (LinkList)malloc(sizeof(LNode)); //創建頭結點
L -> next = NULL;
for (int i = 0; i < n; i ++)
{
p = (LNode *)malloc(sizeof(LNode)); //生成新節點
scanf("%d", &x);
p -> data = https://www.cnblogs.com/adios/p/x;
p -> next = L -> next;
L -> next = p;
}
return L;
}
2.尾插法建立單鏈表
T(n) = O(n)- 增加一個 尾指標
r，
LinkList list_TailInsert(LinkList &L, int n)
{
LNode *p, *r; int x;
L = (LinkList)malloc(sizeof(LNode));
L -> next = NULL;
r = L;
for (int i = 0; i < n; i ++ )
{
p = (LNode *)malloc(sizeof(LNode));
scanf("%d", &x);
p -> data = https://www.cnblogs.com/adios/p/x;
r -> next = p;
r = p;
}
r -> next = NULL; //尾結點指標置空
return L;
}
3.按序號查找結點值
- 查找第
i個結點的值,如果找到，將其保存到e中， T(n) = O(n)
bool GetElem(LinkList L, int i, ElemType &e);
{
int j = 1;
LNode *p = L -> next; //p指向首元結點
while(p && j < i)
{
p = p -> next;
j ++;
}
if (!p || j > i) //p為空即i > n 或 i <= 0
return false;
e = p -> data;
return true;
}
4.按值查找結點
T(n) = O(n)
LNode *LocateElem(LinkList L, ElemType e)
{
LNode *p = L -> next; //p指向首元結點
while (p && p -> data != e)
{
p = p -> next;
}
return p; //查找成功回傳結點e的地址p，查找失敗回傳NULL
}
5.插入
方法：
-
圖示：
-
合法的插入位置：
1 <= i <= n +1， -
T(n) = O(n)
bool LisTInsert(LinKList &L, int i, int e)
{
LNode *p = L, *s; int j = 0;
while (p && j < i - 1)
{
p = p -> next;
j ++;
}
if (!p || j > i - 1) //p為空即 i > n + 1 或 i < 1;
s = (LNode *)malloc(sizeof(LNode));
s -> data = https://www.cnblogs.com/adios/p/e;
s -> next = p -> next;
p -> next = s;
return true;
}
拓展：
- 將插入結點
*s放到插入位置*p之后，然后交換*s與*p的值，
s -> next = p -> next;
p -> next = s;
temp = p -> data;
p -> data = https://www.cnblogs.com/adios/p/s -> data;
s -> data = temp;
6.洗掉
方法：
- 圖示：
bool ListDelete(LinKList &L, int i)
{
LNode *p = L, *q; int j= 0;
while((p -> next) && (j < i - 1)) //p -> next：p的后繼結點可能不存在
{
p = p -> next;
j ++;
}
if (!(p -> next)||(j > i -1))
return false;
q = p -> next; //臨時存盤被洗掉結點的地址
p -> next = q -> next;
free(q); //釋放洗掉結點的空間
return true;
}
拓展
- 將待洗掉結點的后繼結點的值賦予其自身，之后洗掉后繼結點，
q = p -> next;
p -> data = https://www.cnblogs.com/adios/p/q -> data;
p -> next = q -> next;
free(q);
7.求表長
int ListLenth(LinkList L)
{
LNode *p = L;
int length = 0;
while (!p)
{
p = p -> next;
length ++;
}
return length;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/65482.html
標籤：其他