数据结构单链表的插入与删除 _数据结构

单链表是一种线性数据结构，与顺序表占据一段连续的内存空间不同，链表是用一组地址任意的存储单元来存储数据，每个存储单元分散在内存的任意地址上，存储单元之间用指针连接。在链表中，每个数据元素都存放到链表的一个结点，结点之间由指针串联在一起，这样就形成了一条如同“链”的结构，故称作链表。
通过下面的代码可定义一个单链表：

typedef struct node{
ElemType data; //数据域
struct node * next; //指针域
} LNode,*LinkList;

其实上面这段代码定义的是一个单链表的结点。每一个结点包括两部分：数据域和指针域。其中数据域用来存放数据元素本身的信息，指针域用来存放后继结点的地址。
上面使用typedef将结构体struct node定义为LNode类型，表示链表中每个结点的类型为LNode，它等价于结构体类型struct node 。另外，*LinkList是指向LNode类型的指针类型，当定义一个指向LNode类型数据的指针变量时，LNode *L与LinkList L是等价的。
一个链表只要得到了头指针就可以操作链表上的每一个结点，因此把LinkList类型抽象地看作是单链表类型。也就是说，只要得到了LinkList类型的链表头结点指针，就可以操作整个单链表。
单链表的操作包括单链表的创建、结点插入、删除、链表销毁等，下以的实例就包括了这些方面的操作。
先看运行效果：

文章插图
代码：

文章插图

对于线性表（顺序表和单链表）的遍历，注意指针移动的细微区别。在顺序表中，申请一个指针p后，p指示数据元素的存储位置，用*p可取得该数据的值，用p++可以顺序进到物理上下一个元素的位置。在单链表的情形下，指针p指示链表的结点地址，用*p不能取得该结点数据的值，用p++也不能进到下一个结点位置，只能使用p->data取得结点数据的值，用p=p->next进到下一个结点。

结点元素的插入，分为两种情况：
I 插入到单链表的最前面：

文章插图

文章插图
II 插入到中间位置:

文章插图

文章插图
结点元素的删除，也分两种情况：

如果是删除头节点，只需要将将头节点的next指针赋值给单链表指针即可：*list = q->next;
如果是删除中间位置的节点：

文章插图

文章插图
【数据结构单链表的插入与删除】源码：

#include "stdio.h"
#include "malloc.h"
typedef struct node{
int data;
struct node *next;
}LNode,*LinkList;
LinkList GreatLinkList(int n)
{
/*建立一个长度为n的链表*/
LinkList p, r, list = NULL;
int e;
int i;
for (i=1;i<=n;i++){
printf("请输入第%d个结点值（共%d）个：",i,n);
scanf("%d",&e);/*获取链表结点中的数据元素*/
p=(LinkList)malloc(sizeof(LNode));/*分配一个新的链表结点*/
p->data=http://www.baifabohui.com/smjk/e;
p->next=NULL;
if (list == NULL) {
list = p;/*list指向第一个结点，list是头指针*/
} else {
r->next = p;/*将新结点连接到链表的尾部*/
}
r = p;/*指针r始终指向链表的最后一个结点*/
}
return list;/*返回链表的头指针*/
}
void insertListInOrder(LinkList *list,int e)
{
/*向按值有序(递增序列)的链表list中插入包含元素e的结点*/
LinkList p, q, r;
q = *list;
p=(LinkList)malloc(sizeof(LNode));/*生成一个新结点，由p指向它*/
p->data=http://www.baifabohui.com/smjk/e;/*向该结点的数据域赋值e*/
if (*list == NULL || e < (*list)->data) {
p->next = *list;
*list = p;
} else {
while(q != NULL && e >= q->data) {/*循环找到插入结点的位置*/
r = q;/*r指向q的前驱结点*/
q = q->next;/*q指针向后移动*/
}
p->next= q; /*插入新的结点*/
r->next = p;
}
}
void delLink(LinkList *list, LinkList q) {
LinkList r;
if (q == *list) {
*list = q->next;/*如果q指向的结点即为第1个结点，则需要修改list的值*/
free(q);/*释放被删除结点的空间*/
} else {
r = *list;
while ((r->next != q)&&(r->next != NULL)) {
r = r->next;/*通过循环找到q所指结点的前驱结点*/
}
if (r->next != NULL) {
r->next = q->next;/*删除q所指向的结点*/
free(q);/*释放被删除结点的空间*/
}
}
}
void deleteLinkList(LinkList *list) {
LinkList p = *list;/*p指向第一个结点*/
while (p != NULL) {
*list = p ->next;/* list指向p的下一个结点 */
free(p);/*释放掉p指向结点的内存空间*/
p = *list;/*p再指向第一个结点*/
}
}
void printLink(LinkList list) {
while (list != NULL) {
printf("%3d",list->data);/*打印出每个结点中的数据data*/
list = list->next;
}
printf("\n");
}
void main() {
int i;
LinkList q,list = NULL;
list = GreatLinkList(10); /*创建一个长度为10的链表*/
printf("The elems of this linklist is\n");
printLink(list); /*打印出链表的内容*/
printf("插入元素3\n");
insertListInOrder(&list,3);/*插入元素3*/
printf("The elems of this linklist is\n");
printLink(list); /*打印出链表的内容*/
printf("插入元素0\n");
insertListInOrder(&list,0);/*插入元素0*/
printf("The elems of this linklist is\n");
printLink(list); /*打印出链表的内容*/
printf("插入元素11\n");
insertListInOrder(&list,11);/*插入元素10*/
printf("The elems of this linklist is\n");
printLink(list); /*打印出链表的内容*/
printf("删除链表中的第5个元素：\n");
q=list;
for (i=0; i<4; i++) {
q = q->next;/*指针q指向链表中第5个元素*/
}
delLink(&list, q);/*删除q指向的结点*/
printLink(list);/*打印出链表中的内容*/
deleteLinkList(&list);/*销毁该链表*/
if (list == NULL) {
printf( " This Linklist have been deleted\n");
}
system("pause");
}

－End－