线性表的链式存储求表长,查找,插入,删除

 1 typedef struct LNode *List;
 2 
 3 struct LNode {
 4 
 5   ElementType Data;  //节点对应的数据
 6   List Next;  //下一个节点位置
 7 };
 8 
 9 struct LNode L;
10 
11 List PtrL;

1.求表长

 1 int Length (List PtrL){
 2 
 3   List p = PtrL;  //p指向表的第一个结点,临时的指针p
 4 
 5   int j = 0;
 6 
 7   while (p) {  //指针不等于NULL
 8 
 9     p = p->Next;
10 
11     j++;
12 
13   }
14 
15   return j;  //j的值代表表长的值
16 
17 }

2.查找

(1)按序号查找(遍历)

 1 List FindKth (int K, List PtrL){  //第K个位置上的数
 2 
 3   List p = PtrL;  //设为链表的表头
 4 
 5   int i = 1;  //i代表第一个元素
 6 
 7   while (p!=NULL && i<K){
 8 
 9     p = p->Next;
10 
11     i++;
12 
13   }
14 
15   if (i==K) return p;  //找到第K个,返回指针
16 
17   else return NULL;  //没找到,返回空
18 
19 }

(2)按值查找(通过数X找到这个数的位置)

 1 List Find (ElementType X, List PtrL){
 2 
 3   List p = PtrL;
 4 
 5   while (p!=NULL && p->Data !=X){
 6 
 7     p = p->Next;
 8 
 9   }
10 
11   return p;
12 
13 }

3.插入(在第i-1个结点后插入一个值为X的新结点)

要知道插的结点的前面一个是谁

(1)先构造一个新的结点,用s指向

(2)再找到链表的第i-1个结点,用p指向

(3)修改指针,插入结点(p之后插入新结点是s)

平均查找次数是n/2;

 1 List Insert(ElementType X, int i, List PtrL){
 2 
 3   List p, s;
 4 
 5   if (i==1){  //i=1即证明将新结点插在表头
 6 
 7     s = (List)malloc(sizeof(struct LNode));  //申请新结点
 8 
 9     s->Data = X;
10 
11     s->Next = PtrL;
12 
13     return s;  //返回新表头指针
14 
15   }
16 
17   p = FindKth (i-1, PtrL);  //查找第i-1个结点
18 
19   if (p==NULL){  //第i-1个不存在,不能插入
20 
21     printf("参数i错");
22 
23     return NULL;
24 
25   }
26 
27   else {
28 
29     s = (List)malloc(sizeof(struct LNode));
30 
31     s->Data = X;
32 
33     s->Next = p->Next;
34 
35     p->Next = s;
36 
37     return PtrL;
38 
39   }

4.删除(删除链表第i个位置的结点

(1)先找到链表的第i-1个结点,用p指向;

(2)用指针s指向要被删除的结点(p的下一个结点);

(3)修改指针,删除s所指结点

(4)最后释放s所指结点的空间

平均时间复杂度是n/2;

 1 List Delete (int i, List PtrL){
 2 
 3   List p, s;
 4 
 5   if (i==1){  //若要删除表的第一个结点
 6 
 7     s = PtrL;  //s指向第一个结点
 8 
 9     if(PtrL!=NULL)  PtrL = PtrL->Next;
10 
11     else  return NULL;  //本身链表就是空的
12 
13     free(s);  //释放空间
14 
15     return PtrL;
16 
17   }
18 
19   p = FindKth(i-1, PtrL);  //查找第i-1个结点
20 
21   if (p==NULL)
22 
23     printf("第%d个结点不存在", i-1);  return NULL;
24 
25   else if (p->Next==NULL)
26 
27     printf("第%d个结点不存在", i);  return NULL;
28 
29   else {
30 
31     s = p->Next;  //s指向第i个结点
32 
33     p->Next = s->Next;  //从链表中删除
34 
35     free(s);
36 
37     return PtrL;
38 
39   }
40 
41 }
原文地址:https://www.cnblogs.com/zhengxin909/p/12465085.html