单链表

完整代码实现

#include<stdio.h> #include<stdlib.h> //定义结点类型 typedef struct Node{ int data; //数据类型，可以把int型的data换成任意数据类型，包括结构体 struct等 struct Node *next; //单链表的指针域 }Node,*LinkedList; //单链表的初始化 LinkedList LinkedListInit(){ Node *L; L = (Node *)malloc(sizeof(Node)); //申请结点空间 if(L==NULL){ //判断申请空间是否失败 exit(0); //如果失败则退出程序 } L->next=NULL; //将next设置为NULL，初始长度为0的单链表 return L; } //单链表的建立1，头插法建立单链表 LinkedList LinkedListCreatH(){ Node *L; L = (Node *)malloc(sizeof(Node)); //申请结点空间 L->next = NULL; //初始化一个空链表 int x; //x为链表数据域中的数据 while(scanf("%d",&x) != EOF){ Node *p; p = (Node *)malloc(sizeof(Node)); //申请新的结点 p->data = x; //结点数据域赋值 p->next = L->next; //将结点插入到表头L-->|2|-->|1|-->NULL L->next = p; } return L; } //单链表的建立2，尾插法建立单链表 LinkedList LinkedListCreatT(){ Node *L; L = (Node *)malloc(sizeof(Node)); //申请头结点空间 L->next = NULL; //初始化一个空链表 Node *r; r = L; //r始终指向终端结点，开始时指向头结点 int x; //x为链表数据域中的数据 while(scanf("%d",&x) != EOF){ Node *p; p = (Node *)malloc(sizeof(Node)); //申请新的结点 p->data = x; //结点数据域赋值 r->next = p; //将结点插入到表头L-->|1|-->|2|-->NULL r = p; } r->next = NULL; return L; } //单链表的插入，在链表的第i个位置插入x的元素 LinkedList LinkedListInsert(LinkedList L,int i,int x){ Node *pre; //pre为前驱结点 pre = L; int tempi = 0; for (tempi = i; tempi < i; tempi++){ pre = pre->next; //查找第i个位置的前驱结点 } Node *p; //插入的结点为p p = (Node *)malloc(sizeof(Node)); p->data = x; p->next = pre->next; pre->next = p; return L; } //单链表的删除，在链表中删除值为x的元素 LinkedList LinkedListDelete(LinkedList L,int x){ Node *p,*pre; //pre为前驱结点，p为查找的结点 p = L->next; while(p->data != x) { //查找值为x的元素 pre = p; p = p->next; } pre->next = p->next; //删除操作，将其前驱next指向其后继。 free(p); return L; } //链表内容的修改，再链表中修改值为x的元素变为为k。 LinkedList LinkedListReplace(LinkedList L,int x,int k) { Node *p = L->next; int i=0; while(p){ if(p->data == x){ p->data = k; } p = p->next; } return L; } //便利输出单链表 void printList(LinkedList L){ Node *p = L->next; int i=0; while(p){ printf("第%d个元素的值为:%d\n",++i,p->data); p=p->next; } } int main() { //创建 LinkedList list; printf("请输入单链表的数据：以EOF结尾\n"); list = LinkedListCreatT(); //list=LinkedListCreatT(); printList(list); //插入 int i; int x; printf("请输入插入数据的位置："); scanf("%d",&i); printf("请输入插入数据的值："); scanf("%d",&x); LinkedListInsert(list,i,x); printList(list); //修改 printf("请输入修改的数据："); scanf("%d",&i); printf("请输入修改后的值："); scanf("%d",&x); LinkedListReplace(list,i,x); printList(list); //删除 printf("请输入要删除的元素的值："); scanf("%d",&x); LinkedListDelete(list,x); printList(list); return 0; }

链表中第一个结点的存储位置叫做头指针。 在单链表的第一个结点前附设一个结点叫做头结点。 区别：头指针是指向第一个结点的指针，若链表有头结点，则是指向头结点的指针（无论链表是否为空，头指针均不为空）。头结点放在第一元素的结点之前，其数据域一般无意义，也可存放链表的长度（可有可无）。

空链表：

/*线性表的单链表存储结构*/ typedef struct Node { ElemType data; struct Node *next; }Node; typedef struct Node *LinkList; /*定义LinkList*/

结点由存放数据元素的数据域和存放后继结点地址的指针域组成。 p->data：一个数据元素 p->next：一个指针

一、单链表的读取

获得链表第i个数据的算法思路： 1、指针p指向第一个结点，初始化 j 从1开始 2、j<i 时遍历链表，指针p依次向后移动，j 累加1 3、若p移到末尾为空，说明第i个结点不存在 4、否则查找成功，返回结点p的数据

/*初始条件：顺序线性表L已存在，1<=i&&i<=ListLength(L)*/ /*操作结果：用e返回L中第i个数据元素的值*/ Status GetElem(LinkList L,int i,ElemType *e) { int j; LinkList p; /*声明指针p*/ p=L->next; /*p指向第一个结点*/ j=1; /*j计数*/ while(p&&j<i) /*p不为空且j还没有等于i时，循环继续*/ { p=p->next; /*p向后移动，即指向下一结点*/ ++j; } if(!p||j>i) return ERROR; /*第i个结点不存在*/ *e=p->data; /*取第i个结点的数据*/ return OK; }

结论：从头开始找，直到第i个结点为止。 当i=1时，不需遍历，直接取出数据；i=n时，遍历n-1次，时间复杂度为O(n).

二、单链表的插入

结点s插入到结点p和p->next之间。把p的后继结点改成s的后继结点，再把结点s变成p的后继结点。 注意：s->next=p->next; p->next=s;

单链表第i个数据插入结点的算法思路： 1、声明指针p指向链表头结点，初始化 j 从1开始 2、j < i 时，就遍历链表，p指针向后移动，j 累加1 3、若遍历到末尾p为空，说明第 i 个结点不存在 4、否则查找成功，生成一个空结点s 5、将数据元素e赋值给s->data 6、单链表插入标准语句s->next=p->next; p->next=s; 7、返回成功

/*初始条件：顺序线性表L已存在，1<=i&&i<=ListLength(L)*/ /*操作结果：在L中第i个结点位置之前插入新的数据元素e，L的长度加1*/ Status ListInsert(LinkList *L,int i,ElemType e) { int j; LinkList p,s; p=*L; j=1; while(p&&j<i) /*寻找第i-1个结点*/ { p=p->next; ++j; } if(!p||j>i) return error; /*第i个结点不存在*/ s=(LinkList)malloc(sizeof(Node)); /*生成新结点*/ s->data=e; s->next=p->next; p->next=s; return OK; }

三、单链表的删除

将要删除结点p的指针绕过，指向它的后继结点。 q=p->next; p->next=q->next;

单链表第i个数据插入结点的算法思路： 1、声明指针p指向链表头结点，初始化 j 从1开始 2、j < i 时，就遍历链表，p指针向后移动，j 累加1 3、若遍历到末尾p为空，说明第 i 个结点不存在 4、否则查找成功，将欲删除的结点p->next赋值给q 5、单链表的删除标准语句p->next=q->next; 6、将q结点中的数据赋值给e，作为返回 7、释放q结点 8、返回成功

/*初始条件：顺序线性表L已存在，1<=i&&i<=ListLength(L)*/ /*操作结果：删除L的第i个结点，并用e返回其值，L的长度减1*/ Status ListDelete(LinkList *L,int i,ElemType *e) { int j; LinkList p,q; p=*L; j=1; while(p->next&&j<i) /*遍历寻找第i-1个结点*/ { p=p->next; ++j; } if(!(p->next)||j>i) { return ERROR; /*第i个结点不存在*/ } q=p->next; p->next=q->next; *e=q->data; free(q); /*让系统回收此结点，释放内存*/ return OK; }

四、单链表的整表创建

单链表整表创建的算法思路： 1、声明一指针p和计数器变量i 2、初始化一空链表L 3、让L的头结点的指针指向NULL，即建立一个带头结点的单链表 4、循环： 生成一新结点赋值给p； 随机生成一数字赋值给p的数据域p->data； 将p插入到头结点与前一新结点之间

1、头插法：

/*随机产生n个元素的值，建立带头结点的单链线性表L（头插法）*/ void CreateListHead(LinkList *L,int n) { LinkList p; int i; srand(time(0)); /*初始化随机数种子*/ *L=(LinkList)malloc(sizeof(Node)); (*L)->next=NULL; /*先建立一个带头结点的单链表*/ for(i=0;i<n;i++) { p=(LinkList)malloc(sizeof(Node));/*生成新结点*/ p->data=rand()%100+1; /*随机生成100以内的数字*/ p->next=(*L)->next; (*L)->next=p; /*插入到表头*/ } }

2、尾插法

/*随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法）*/ void CreateListTail(LinkList *L,int n) { LinkList p,r; int i; srand(time(0)); /*初始化随机数种子*/ *L=(LinkList)malloc(sizeof(Node)); /*整个线性表*/ r=*L; /*r为指向尾部的结点*/ for(i=0;i<n;i++) { p=(Node *)malloc(sizeof(Node)); /*生成新结点*/ p->data=rand()%100+1; /*随机生成100以内的数字*/ r->next=p; /*将表尾终端结点的指针指向新结点*/ r=p; /*将当前的新结点定义为表尾终端结点*/ } r->next=NULL; /*表示当前链表结束*/ }

五、单链表的整表删除

单链表整表删除的算法思路： 1、声明一结点p和q 2、将第一个结点赋值给p 3、循环： 将下一结点赋值给q； 释放p； 将q赋值给p

/*初始条件：顺序线性表L已存在，操作结果：将L重置为空表*/ Status ClearList(linkList *L) { LinkList p,q; p=(*L)->next; /*p指向第一个结点*/ while(p) /*没到表尾*/ { q=p->next; free(q); p=q; } (*L)->next=NULL; /*头结点指针域为空*/ return OK; }