一.特点：
（1）在单链表上插入，删除一个节点，必须知道其节点的前驱节点。
（2）单链表不具有按序号随机访问的特点，只能从头指针开始依次进行访问
（3）链表上实现的插入和删除运算不用移动节点，仅需修改指针。
二.操作
1.单链表节点的定义
1 //单链表节点的定义2 typedef int ElemType;3 typedef struct node4 {5 ElemType data;6 struct node *next;7 }Lnode,*LinkList; 2.头插法建立单链表
思想：首先申请一个头结点，并且将头结点指针置空，然后每读入一个数据元素则申请一个结点，并插在链表的 头结点之后。时间复杂度为O(n)。
1 //单链表的头插法 2 LinkList Creat_LinkList() 3 { 4 int x; 5 Lnode *s; 6 LinkList H = (LinkList)malloc(sizeof(Lnode)); //生成头结点 7 H->next = NULL; 8 scanf_s("%d", &x); 9 while (x != -1)10 {11 s = (LinkList)malloc(sizeof(Lnode));12 s->data = x;13 s->next = H->next;14 H->next = s;15 scanf_s("%d",&x);16 }17 return H;18 } 3.尾插法建立单链表
思想：首先申请一个头结点，并且将头结点指针置空，头指针H和为指针r都指向头结点，然后按照线性表中元素 的顺序依次读入数据，如果不是结束标志，则申请结点，将心结点插入r所指结点的后面，并使r指向新节点。时间复杂 度为O(n)。
1 //单链表的尾插法 2 LinkList Creat_LinkList() 3 { 4 int x; 5 LinkList H = (LinkList)malloc(sizeof(Lnode)); //生成头结点 6 Lnode *s, *r = H; 7 H->next = NULL; 8 scanf_s("%d", &x); 9 while (x != -1)10 {11 s = (LinkList)malloc(sizeof(Lnode));12 s->data = x;13 H->next = s;14 s->next = NULL;15 r = s;16 scanf_s("%d", &x);17 }18 return H;19 } 4.求单链表的长
时间复杂度为O(n)。
1 //求表长 2 int Length_LInkList(LinkList H) 3 { 4 Lnode *p = H;//指向头结点的指针变量p 5 int j = 0; 6 while (p->next != NULL) 7 { 8 p = p->next; 9 j++;10 }11 return j;12 } 5.查找特定序号的节点的指针
时间复杂度为O(n)。
1 //查找给定节点的指针 2 LinkList Get_LinkList(LinkList H, int k) 3 { 4 LNode *p = H; 5 int j = 0; 6 while (p->next != NULL && j < k) 7 { 8 p = p->next; 9 j++;10 }11 if (j == k)12 return p;13 else14 return NULL;15 }
6.查找特定值所在的位置 时间复杂度为O(n)。
1 Lnode *Locate_LinkList(LinkList H, ElemType x)2 {3 Lnode *p = H->next;4 while (p != NULL && p->data != x)5 {6 p = p->next;7 return p;8 }9 } 7.单链表的插入
时间复杂度为O(n)。
1 int Insert_LinkList(LinkList H,int i,ElemType x) 2 { 3 Lnode *p, *s; 4 p = Get_LinkList(H, i - 1);//查找第一个节点 5 if (p == NULL) 6 { 7 printf("插入位置错误。"); 8 return false; 9 }10 else11 {12 s = (LinkList)malloc(sizeof(Lnode));13 s->data = x;14 s->next = p->next;15 p->next = s;16 return true;17 }18 19 } 8.删除节点
时间复杂度为O(n)。
1 //p指向要删除的节点，q是p的前驱节点 2 int Del_linkList(LinkList H, int i) 3 { 4 LinkList p, q; 5 p = Get_LinkList(H, i - 1);//查找第i-1个节点 6 if (p == NULL) 7 { 8 printf("第i-1个节点不存在。"); 9 return false;10 }11 else12 {13 if (p->next == NULL)14 {15 printf("第i-1个节点不存在。");16 return false;17 }18 else19 {20 q = p->next;21 p->next = q->next;22 free(q);23 return true;24 }25 }26 } 9.单链表的倒置
时间复杂度为O(n)。
1 void Reverse(LinkList H) 2 { 3 Lnode *p,*q; 4 p = H->next; 5 H->next = NULL; 6 while (p) 7 { 8 q = p; 9 p = p->next;10 q->next = H->next;11 H->next = q;12 }13 } 10.单链表删除重复节点
时间复杂度为O(n^2)。
1 void pur_LinkList(LinkList H) 2 { 3 Lnode *p, *q, *r; 4 p = H->next; 5 if (p!=NULL) 6 while (p->next) 7 { 8 q = p; 9 while (q->next)10 {11 if (q->next->data == p->data){12 r = q->next;13 q->next = r->next;14 free(q);15 }16 else 17 {18 q = q->next;19 }20 }21 p = p->next;22 }23 } 11.两个单链表的差
1 void Difference(LinkList LA, LinkList LB) 2 { 3 Lnode *pre,*q, *p, *r; 4 pre = LA; 5 p = LA->next; 6 while (p != NULL) 7 { 8 q = LB->next; 9 while (q != NULL&&q->data != p->data) q = q->data;10 if (q != NULL)11 {12 r = p;13 pre->next = p->next;14 p = p->next;15 free(r);16 }17 else18 {19 pre = p;20 p=p->next;21 }22 }23 } 12.部分方法综合测试
1 #include2 #include "malloc.h" 3 typedef struct node 4 { 5 int val; //数据域 6 struct node *next; //指针域 7 }LNode,*LinkList; 8 9 //头插法建立单链表 10 LinkList Creat_LinkList() 11 { 12 LinkList H = (LinkList)malloc(sizeof(LNode)); 13 H->next = NULL; 14 LNode *s; 15 int x; 16 scanf_s("%d",&x); 17 while (x != -1) 18 { 19 s = (LinkList)malloc(sizeof(LNode)); 20 s->val = x; 21 s->next = H->next; 22 H->next = s; 23 scanf_s("%d", &x); 24 } 25 return H; 26 } 27 28 //单链表的尾插法 29 LinkList Creat_LinkListEnd() 30 { 31 int x; 32 LinkList H =(LinkList) malloc(sizeof(LNode)); 33 H->next = NULL; 34 LNode *s,*r=H; 35 scanf_s("%d",&x); 36 while (x != -1) 37 { 38 s = (LinkList)malloc(sizeof(LNode)); 39 s->val = x; 40 s->next = r->next; 41 r->next = s; 42 r = s; 43 scanf_s("%d",&x); 44 } 45 return H; 46 } 47 48 //求表长 49 int length_LinkList(LinkList H) 50 { 51 LNode *p = H; 52 int j = 0; 53 while (p->next!=NULL) 54 { 55 p = p->next; 56 j++; 57 } 58 return j; 59 } 60 //查找给定节点的指针 61 LinkList Get_LinkList(LinkList H, int k) 62 { 63 LNode *p = H; 64 int j = 0; 65 while (p->next != NULL && j < k) 66 { 67 p = p->next; 68 j++; 69 } 70 if (j == k) 71 return p; 72 else 73 return NULL; 74 } 75 //删除给点节点的值 76 //p指向要删除的节点，q是p的前驱节点 77 int Del_linkList(LinkList H, int i) 78 { 79 LinkList p, q; 80 p = Get_LinkList(H, i - 1);//查找第i-1个节点 81 if (p == NULL) 82 { 83 printf("第i-1个节点不存在。"); 84 return false; 85 } 86 else 87 { 88 if (p->next == NULL) 89 { 90 printf("第i-1个节点不存在。"); 91 return false; 92 } 93 else 94 { 95 q = p->next; 96 p->next = q->next; 97 free(q); 98 return true; 99 }100 }101 }102 103 //打印单链表104 void print(LinkList head)105 {106 LinkList p = head->next;107 while(p)108 {109 printf("%3d",p->val);110 p = p->next;111 }112 printf("\n");113 }114 int main()115 {116 LinkList head = NULL;117 118 //头插法创建119 //head = Creat_LinkList(); 120 //print(head);121 122 //尾插法创建123 //head = Creat_LinkListEnd();124 //print(head);125 126 //求表长127 //head = Creat_LinkListEnd();128 //printf("%d\n", length_LinkList(head));129 //print(head);130 131 //删除位置为5的结点132 head = Creat_LinkListEnd();133 Del_linkList(head,5);134 print(head);135 136 return 0;137 }