文字描述：
为了表示前后两个数据元素的逻辑关系，对于每个数据元素，除了存储其本身的信息之外(数据域)，还需存储一个指示其直接后继的信息(即直接后继的存储位置，指针域)。
示意图：
算法分析：
在单链表中插入和删除元素时，主要是改变指针的值，其时间复杂度为1。而顺序存储的话，其时间复杂度为n。
在单链表中求长度时不如顺序存储结构，其时间复杂度为n； 而顺序存储是1。故可以在链表头结点中设置一个长度值，在插入数据元素时加1，在删除数据元素时减1。
在单链表中查找指定数据元素时，其时间复杂度和顺序存草时一样，乱序情况下为n。
代码实现(动态单链表)：
//
// Created by lady on 19-1-26.
// #include <stdlib.h>
#include <stdio.h>
#include <string.h> //线性表的动态单链表存储结构
typedef struct ElemType{
char data[];
}ElemType;
typedef struct LNode{
ElemType e;
struct LNode *next;
}LNode, *LinkList; /*
* 倒序法输入n个元素的值，建立带表头结点的单链表线性表L
*/
static int CreateList_L(LinkList *L, int n, char name[])
{
printf("以倒插入法创建单链表存储结构的线性表%s:\n", name);
//先建立一个带头结点的单链表
if((*L=(LinkList)malloc(sizeof(LNode))) == NULL){
return -;
}
(*L)->next = NULL;
int i = ;
LinkList p = NULL;
for(i=n; i>; --i){
//生成新的结点
p = (LinkList)malloc(sizeof(LNode));
//输入元素值
printf("输入第%d个元素:", i);
scanf("%s[^\\n]", p->e.data);
//插入到表头
p->next = (*L)->next;
(*L)->next = p;
}
return ;
} /*依次对L的每个数据元素调用函数fun。一旦fun失败，则操作失败*/
static int ListTraverse_L(LinkList L, int (*fun)(ElemType,int), char info[])
{
printf("%s", info);
//跳过头结点
LNode *p = L->next;
int i = ;
while(p){
if(fun(p->e, i++)){
printf("Err:when traverse(e,%d) wrong!\n",i);
}
p = p->next;
}
printf("\n");
} /*
* L为带头结点的单链表的头指针
* 当第i个元素存在是，其值赋给e并返回0,否则返回-1
*/
static int GetElem_L(LinkList L, int i, ElemType *e)
{
//初始化，p指向第一个结点
LNode *p = L->next;
//j为计数器
int j = ;
while(p && j<i){
//顺指针向后查找，知道p指向第i个元素或者p为空
p = p->next;
j+=;
}
if(!p || j>i){
//第i个元素不存在
return -;
}
//取第i个元素
*e = p->e;
return ;
} /*
* 在带头结点的单链表线性表L中第i个位置之前插入元素e
*/
static int ListInsert_L(LinkList *L, int i, ElemType e)
{
LNode *p = (LNode *)(*L);
int j = ;
while(p && j<i-){
//寻找第i-1个结点
p = p->next;
++j;
}
//i小于1或者大于表长+1
if(!p || j>i)
return -;
//生成新的结点
LinkList s = (LinkList)malloc(sizeof(LNode));
s->e = e;
//将新结点插入到链表L中
s->next = p->next;
p->next = s;
return ;
} /*
* 在带头结点的单链线性表L中，删除第i个元素，并有e返回其值
*/
static int ListDelete_L(LinkList *L, int i, ElemType *e)
{
LNode *p = (LNode *)(*L);
LNode *q = NULL;
int j = ;
while(p->next && (j<i-)){
//寻找第i个结点，并令p指向其前趋
p = p->next;
++j;
}
if(!(p->next) || (j>i-)){
//删除位置不合理
return -;
}
//删除该结点
q = p->next;
p->next = q->next;
*e = q->e;
//释放该结点的占用空间
free(q);
return ;
} /*
* 输入元素e的数据和位置
*/
static int printE(ElemType e, int location)
{
printf("%3d=%-10s", location, e.data);
return ;
} /*
* 已知单链线性表La和Lb的元素按值非递减排列
* 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列
*/
static void MergeList_L(LinkList La, LinkList Lb, LinkList *Lc)
{
LNode *pa = La->next;
LNode *pb = Lb->next;
LNode *pc = NULL;
LNode *p;
//用La的头结点作为Lc的头结点
pc = (LNode*)La;
*Lc = La; while(pa && pb){
if(atoi(pa->e.data) <= atoi(pb->e.data)){
//需要将当前的pa结点插入到pc结点
if(pc->next == pa){
//pc结点正好在pa链表
pc = pc->next;//移动pc结点到下一个结点
pa = pa->next;//移动pa结点到下一个结点
}else{
//需要将pa结点插入到pc结点后，插入后pc、pa结点要后移动
p = pa;
pa = pa->next;
p->next = pc->next;
pc->next = p;
pc = pc->next;
}
}else{
if(pc->next == pb){
pc = pc->next;
pb = pb->next;
} else{
p = pb;
pb = pb->next;
p->next = pc->next;
pc->next = p;
pc = pc->next;
}
}
}
//插入剩余段
pc->next = pa?pa:pb;
//释放Lb的头结点
free(Lb);
} /*
* 释放链表L
*/
static int DestoryList_L(LinkList *L)
{
if(L == NULL){
return -;
}
if(*L == NULL){
return -;
}
LNode *p, *q;
p = (LNode*)(*L);
while(p){
q = p;
free(q);
p = p->next;
}
*L = NULL;
return ;
} int main(int argc, char *argv[])
{ ElemType e;
int location = ; LinkList L;
CreateList_L(&L, , "L");
ListTraverse_L(L, printE, "L:"); printf("insert a data and print, please input (location, data):");
scanf("%d,%s[^\\n]", &location, e.data);
ListInsert_L(&L, location, e);
ListTraverse_L(L, printE, "L:");
printf("\n"); printf("delete a data through location and print, please input (location):");
scanf("%d[^\\n]", &location);
ListDelete_L(&L, location, &e);
printf("location %d, data %s is deleted from List\n", location, e.data);
ListTraverse_L(L, printE, "init:");
printf("\n"); printf("locate/find a data through location, please input (location):");
scanf("%d[^\\n]", &location);
GetElem_L(L, location, &e);
printf("the data of what location is %d, is %s\n", location, e.data);
printf("\n"); printf("Merge LA and LB to LC!\n");
LinkList La, Lb, Lc;
//create La
CreateList_L(&La, , "La");
ListTraverse_L(La, printE, "La:");
//create Lb
CreateList_L(&Lb, , "Lb");
ListTraverse_L(Lb, printE, "Lb:");
//merge La and Lb to Lc
MergeList_L(La, Lb, &Lc);
ListTraverse_L(Lc, printE, "Lc:"); DestoryList_L(&L);
DestoryList_L(&La);
DestoryList_L(&Lb);
}
动态单链表
代码运行(动态单链表)：
/home/lady/CLionProjects/untitled/cmake-build-debug/untitled
以倒插入法创建单链表存储结构的线性表L:
输入第4个元素:ZHAO
输入第3个元素:QIAN
输入第2个元素:SUN
输入第1个元素:LI
L: 1=LI 2=SUN 3=QIAN 4=ZHAO
insert a data and print, please input (location, data):2,ZHOU
L: 1=LI 2=ZHOU 3=SUN 4=QIAN 5=ZHAO delete a data through location and print, please input (location):3
location 3, data SUN is deleted from List
init: 1=LI 2=ZHOU 3=QIAN 4=ZHAO locate/find a data through location, please input (location):3
the data of what location is 3, is QIAN Merge LA and LB to LC!
以倒插入法创建单链表存储结构的线性表La:
输入第4个元素:11
输入第3个元素:8
输入第2个元素:5
输入第1个元素:3
La: 1=3 2=5 3=8 4=11
以倒插入法创建单链表存储结构的线性表Lb:
输入第7个元素:20
输入第6个元素:15
输入第5个元素:11
输入第4个元素:9
输入第3个元素:8
输入第2个元素:6
输入第1个元素:2
Lb: 1=2 2=6 3=8 4=9 5=11 6=15 7=20
Lc: 1=2 2=3 3=5 4=6 5=8 6=8 7=9 8=11 9=11 10=15 11=20 Process finished with exit code 0
代码实现(带头结点的单向动态链表)
#include <stdio.h>
#include <stdlib.h>
#include <string.h> //带头结点的线性链表类型定义如下
typedef struct ElemType{
char data[];
}ElemType;
typedef struct LNode{//结点类型
ElemType e;
struct LNode *next;
}*Link, *Position;
typedef struct {//链表类型
Link head,tail;//分别指向线性链表中的头结点和最后一个结点
int len;//指示线性链表中数据元素的个数
}LinkList; /*
*依次对L的每个元素调用visit函数，一旦失败，则操作失败
*/
static int ListTraverse(LinkList L, int (*visit)(ElemType,int), const char note[])
{
printf("遍历线性表%s:", note);
Link p = L.head->next;
int i = ;
while(p){
if(visit(p->e,i)<){
return -;
}
if(p==L.tail)
break;
p = p->next;
}
printf("\n");
return ;
} static int print(ElemType e, int loc)
{
printf("%3d=%-6s", loc, e.data);
return ;
} //构造一个空的线性链表L
static int InitList(LinkList *L)
{
if(L==NULL){
return -;
}
Link p = (Link)malloc(sizeof(struct LNode));
memset(p->e.data, , sizeof(p->e.data));
p->next = p;
L->len = ;
L->head = L->tail = p;
return ;
} //返回p指示线性链表L中第i个结点的位置并返回0 i值不合法时返回-1
static int LocatePos(LinkList *L, int i, Link *p)
{
if(L==NULL || p==NULL){
return -;
}
*p=L->head;
int index = ;
while((index<L->len) && (*p != L->tail)){
(*p) = (*p)->next;
index +=;
if(index == i)
break;
}
return (index==i)?:-;
} //创建一个值为e的结点， 其地址为p; 成功则返回0, 失败就返回-1
static int MakeNode(Link *p, ElemType e)
{
if(p==NULL){
return -;
}
if(((*p) = (Link)malloc(sizeof(struct LNode))) == NULL){
return -;
}
(*p)->next = NULL;
(*p)->e = e;
return ;
} //已知h指向线性链表的头结点，将s所指结点插入在第一个结点之前
static int InsFirst(Link *h, Link *s)
{
if(h==NULL || s==NULL){
return -;
}
if(*h == NULL || *s == NULL){
return -;
}
(*s)->next = (*h)->next;
(*h)->next = (*s);
return ;
} //在带头结点的单链线性表L的第i个元素之前插入元素e
static int ListInsert_L(LinkList *L, int i, ElemType e)
{
Link h = NULL;
Link p = NULL;
if(LocatePos(L, i-, &h)<){
//i值不合法
return -;
}
if(MakeNode(&p, e)<){
//结点存储分配失败
return -;
}
//对于从第i个结点开始的链表，第i-1个结点是它的头结点
InsFirst(&h, &p);
//如果是在链表的最后一个结点上插入， 那么和改变链表的尾结点指针
if(L->tail == h){
p->next = L->head;
L->tail = p;
}
//链表长度+1
L->len += ;
return ;
} //创建一个长度为n的带头结点的单项链表L
static int CreateList(LinkList *L, int n, char note[])
{
printf("创建一个长度为%d的带头结点的单向线性链表%s!\n", n, note);
if(L==NULL){
return -;
}
if(InitList(L)<){
return -;
}
ElemType e;
int i = ;
for(i=; i<=n; i++){
printf("输入第%d个元素:", i);
scanf("%s[^\\n]", e.data);
if(ListInsert_L(L, i, e)<){
return -;
}
}
} //返回链表L的头结点
static Link GetHead(LinkList *L){
if(L==NULL){
return NULL;
}
return L->head;
} //返回链表L中结点p的后继
static Link NextPos(LinkList *L, Link p)
{
if(L == NULL || p==NULL){
return NULL;
}
return p->next;
} //返回结点p中的数据元素
static ElemType GetCurElem(Link p)
{
return p->e;
} //释放结点p
static void FreeNode(Link p)
{
if(p)
free(p);
return;
} //将指针s所指的一串结点连接到线性链表L的最后一个结点
static int Append(LinkList *L, Link *s)
{
if(L == NULL || s==NULL || *s==NULL){
return -;
}
L->tail->next = (*s);
Link p = *s;
Link t = p;
int count = ;
while(p){
count += ;
t = p;
p = p->next;
}
L->len += count;
t->next = L->head;
L->tail = t;
return ;
} //已知h指向线性链表的头结点，删除链表中的第一个结点并以求返回
static int DelFirst(Link *h, Link *q)
{
if(h==NULL || q==NULL){
return -;
}
if(*h == NULL || *q == NULL){
return -;
}
(*q) = (*h)->next;
(*h)->next = (*q)->next;
(*q)->next = NULL;
return ;
} //已知单链线性表La和Lb的元素按值非递减排列
//归并La和Lb得到新的单链线性表Lc Lc的元素也按值非递减排列
static int MergeList_L(LinkList *La, LinkList *Lb, LinkList *Lc, int (*compare)(ElemType,ElemType),const char note[])
{
printf("%s\n", note);
if(InitList(Lc)<){
//存储空间分配失败
return -;
}
Link ha = GetHead(La);//ha指向La的头结点
Link hb = GetHead(Lb);//hb指向Lc的头结点
if(ha==NULL || hb==NULL){
return -;
}
Link pa = NextPos(La, ha);//pa指向La中第一个结点
Link pb = NextPos(Lb, hb);//pb指向Lb中第一个结点
Link p; ElemType a;
ElemType b; Link q;
while(pa && pb){
//La和Lb均非空
//a和b为两表中当前比较元素
a = GetCurElem(pa);
b = GetCurElem(pb);
if(compare(a, b)<=){//a<=b
DelFirst(&ha, &q);
Append(Lc, &q);
if(pa == La->tail){
pa = NULL;
break;
}
pa = NextPos(La, ha);
}else{//a>b
DelFirst(&hb, &q);
Append(Lc, &q);
if(pb == Lb->tail){
pb = NULL;
break;
}
pb = NextPos(Lb, hb);
}
}
if(pa){
//链接La中剩余结点
p = pa;
while(p){
if(p == La->tail){
p->next = NULL;
break;
}
p = p->next;
}
Append(Lc, &pa);
}else{
//链接Lb中剩余结点
p = pb;
while(p){
if(p == Lb->tail){
p->next = NULL;
break;
}
p = p->next;
}
Append(Lc, &pb);
}
//释放La和Lb的头结点
FreeNode(ha);
FreeNode(hb);
return ;
} /*
* 将元素a和b转换成整数a和整数b
* 返回-1：整数a > 整数b
* 返回0：整数a = 整数b
* 返回1：整数a < 整数b
*/
static int compare(ElemType a, ElemType b)
{
int i_a = atoi(a.data);
int i_b = atoi(b.data);
if(i_a<i_b){
return -;
}else if(i_a == i_b){
return ;
}else{
return ;
}
} int main(int argc, char *argv[])
{
LinkList La; //3,5,8,11
LinkList Lb; //2,6,8,9,11,15,20
if((CreateList(&La, , "La")<) || (ListTraverse(La, print, "La")<)){
return -;
}
if((CreateList(&Lb, , "Lb")<) || (ListTraverse(Lb, print, "Lb")<)){
return -;
}
LinkList Lc;
if((MergeList_L(&La, &Lb, &Lc, compare, "归并La和Lb到Lc！")<) || (ListTraverse(Lc, print, "Lc")<)){
return -;
}
return ;
}
带头结点的单项动态链表
代码运行(带头结点的单向动态链表)
/home/lady/CLionProjects/untitled/cmake-build-debug/untitled
创建一个长度为4的带头结点的单向线性链表La!
输入第1个元素:3
输入第2个元素:5
输入第3个元素:8
输入第4个元素:11
遍历线性表La: 1=3 1=5 1=8 1=11
创建一个长度为7的带头结点的单向线性链表Lb!
输入第1个元素:2
输入第2个元素:6
输入第3个元素:8
输入第4个元素:9
输入第5个元素:11
输入第6个元素:15
输入第7个元素:20
遍历线性表Lb: 1=2 1=6 1=8 1=9 1=11 1=15 1=20
归并La和Lb到Lc！
遍历线性表Lc: 1=2 1=3 1=5 1=6 1=8 1=8 1=9 1=11 1=11 1=15 1=20 Process finished with exit code 0
代码实现(静态单链表)：
//
// Created by lady on 19-1-27.
// #include <stdio.h>
#include <stdlib.h>
#include <string.h> //---------------线性表的静态单链表存储结构-----------
#define MAXSIZE 12 //链表的最大长度
typedef struct ElemType{
char data[];
}ElemType;
typedef struct{
ElemType e;
int cur;
}component,SLinkList[MAXSIZE]; /*
* 依次打印静态链表space中的数据
*/
static void Debug_Print(SLinkList space, char note[])
{
printf("%s\n", note);
int i = ;
for(i=; i<MAXSIZE; i++){
printf("\tindex %-5d[data:%-5s,cur:%-2d]\n", i, space[i].e.data, space[i].cur);
}
} /*
* 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针， “0”表示空指针。
*/
static void InitSpace_SL(SLinkList space)
{
int i = ;
for(i=; i<MAXSIZE-; ++i){
memset(space[i].e.data, , sizeof(space[i].e.data));
space[i].cur = i+;
}
memset(space[MAXSIZE-].e.data, , sizeof(space[MAXSIZE-].e.data));
space[MAXSIZE-].cur = ;
return ;
} /*
* 如果备用空间链表非空，则返回分配的结点下标，否则返回0
*/
static int Malloc_SL(SLinkList space)
{
int i = ;
i = space[].cur;
if(space[].cur)
space[].cur = space[i].cur;
return i;
} /*
* 将下标为k的空闲结点回收到备用链表。
*/
static int Free_SL(SLinkList space, int k)
{
space[k].cur = space[].cur;
space[].cur = k;
return ;
} /*
* 依次输入集合A和B的元素，在一维数组space中建立表示集合 (A-B)U(B-A)的静态链表，S为其头指针。
* 假设备用空间够大，space[0].cur为备用空间的头指针
*/
static void difference(SLinkList space, int *S)
{
printf("用静态链表算集合(A-B)U(B-A):\n");
InitSpace_SL(space); //将space整个初始化成备用空间
(*S) = Malloc_SL(space);//生成S的头结点
int r = *S;//r始终指向静态链表S的最后一个元素。
int m, n;
int i, j;
char str[] = {};
printf("step1\t:依次输入A和B集合的元素个数(m,n):");
scanf("%d,%d[^\\n]", &m, &n);
printf("step2.1\t:依次输入A中的元素到集合S:\n");
for(j=; j<=m; ++j){
i = Malloc_SL(space);
printf("\t输入A中第%d/%d个元素:", j, m);
scanf("%s[^\\n]", space[i].e.data);
//插入到表尾巴
space[r].cur = i;
r = i;
}
space[r].cur = ;
Debug_Print(space, "step2.2\t:创建集合A后的集合S值"); printf("step3\t:依次输入B中的元素，同时查找S表，如果已经存在则从S中删除之，否则加入到S!\n");
ElemType b;
int p;
int k;
for(j=; j<=n; ++j){
memset(b.data, , sizeof(b.data));
printf("\t输入B中第%d/%d个元素:", j, n);
scanf("%s[^\\n]", b.data);
p = (*S);
k = space[p].cur; //k指向集合A中第一个结点
while(k!=space[r].cur && strncmp(space[k].e.data, b.data, sizeof(b.data))){
//在当前表中查找
p = k;
k = space[k].cur;
}
if(k == space[r].cur){
//当前表中不存在该元素， 插入在r所值结点后，且r的位置不变。
i = Malloc_SL(space);
space[i].e = b;
space[i].cur = space[r].cur;
space[r].cur = i;
snprintf(str, sizeof(str), "step3.1\t:元素%s在S中不存在，插入之!",b.data);
Debug_Print(space, str);
}else{
//该元素已在表中，则删除之
space[p].cur = space[k].cur;
Free_SL(space, k);
if(r == k){
//如果删除的是r所指结点，则需修改尾指针。
r = p;
}
snprintf(str, sizeof(str), "step3.1\t:元素%s在S中存在，删除之!",b.data);
Debug_Print(space, str);
}
}
} int main(int argc, char *argv[])
{
SLinkList space;
int s;
//求(A-B)U(B-A)
difference(space, &s);
return ;
}
静态链表
代码运行(静态单链表)：
/home/lady/CLionProjects/untitled/cmake-build-debug/untitled
用静态链表算集合(A-B)U(B-A):
step1 :依次输入A和B集合的元素个数(m,n):6,4
step2.1 :依次输入A中的元素到集合S:
输入A中第1/6个元素:c
输入A中第2/6个元素:b
输入A中第3/6个元素:e
输入A中第4/6个元素:g
输入A中第5/6个元素:f
输入A中第6/6个元素:d
step2.2 :创建集合A后的集合S值
index 0 [data: ,cur:8 ]
index 1 [data: ,cur:2 ]
index 2 [data:c ,cur:3 ]
index 3 [data:b ,cur:4 ]
index 4 [data:e ,cur:5 ]
index 5 [data:g ,cur:6 ]
index 6 [data:f ,cur:7 ]
index 7 [data:d ,cur:0 ]
index 8 [data: ,cur:9 ]
index 9 [data: ,cur:10]
index 10 [data: ,cur:11]
index 11 [data: ,cur:0 ]
step3 :依次输入B中的元素，同时查找S表，如果已经存在则从S中删除之，否则加入到S!
输入B中第1/4个元素:a
step3.1 :元素a在S中不存在，插入之!
index 0 [data: ,cur:9 ]
index 1 [data: ,cur:2 ]
index 2 [data:c ,cur:3 ]
index 3 [data:b ,cur:4 ]
index 4 [data:e ,cur:5 ]
index 5 [data:g ,cur:6 ]
index 6 [data:f ,cur:7 ]
index 7 [data:d ,cur:8 ]
index 8 [data:a ,cur:0 ]
index 9 [data: ,cur:10]
index 10 [data: ,cur:11]
index 11 [data: ,cur:0 ]
输入B中第2/4个元素:b
step3.1 :元素b在S中存在，删除之!
index 0 [data: ,cur:3 ]
index 1 [data: ,cur:2 ]
index 2 [data:c ,cur:4 ]
index 3 [data:b ,cur:9 ]
index 4 [data:e ,cur:5 ]
index 5 [data:g ,cur:6 ]
index 6 [data:f ,cur:7 ]
index 7 [data:d ,cur:8 ]
index 8 [data:a ,cur:0 ]
index 9 [data: ,cur:10]
index 10 [data: ,cur:11]
index 11 [data: ,cur:0 ]
输入B中第3/4个元素:n
step3.1 :元素n在S中不存在，插入之!
index 0 [data: ,cur:9 ]
index 1 [data: ,cur:2 ]
index 2 [data:c ,cur:4 ]
index 3 [data:n ,cur:8 ]
index 4 [data:e ,cur:5 ]
index 5 [data:g ,cur:6 ]
index 6 [data:f ,cur:7 ]
index 7 [data:d ,cur:3 ]
index 8 [data:a ,cur:0 ]
index 9 [data: ,cur:10]
index 10 [data: ,cur:11]
index 11 [data: ,cur:0 ]
输入B中第4/4个元素:f
step3.1 :元素f在S中存在，删除之!
index 0 [data: ,cur:6 ]
index 1 [data: ,cur:2 ]
index 2 [data:c ,cur:4 ]
index 3 [data:n ,cur:8 ]
index 4 [data:e ,cur:5 ]
index 5 [data:g ,cur:7 ]
index 6 [data:f ,cur:9 ]
index 7 [data:d ,cur:3 ]
index 8 [data:a ,cur:0 ]
index 9 [data: ,cur:10]
index 10 [data: ,cur:11]
index 11 [data: ,cur:0 ] Process finished with exit code 0