目录

0. 前言

1. 单链表的存储结果的描述、定义

2.单链表的初始化

2.头插法建表

 3.尾插法建表

4.访问输出单链表

 5.求单链表中元素的个数

6.求表中第i个元素的值

7.在表中特定位置插入元素

8 .删除表中特定位置上的元素

9.寻找表中特定元素值的位置

10.销毁该单链表

11.将表置为空表

12.单链表的排序

13.单链表自身的逆置

14.单链表的排序

15.对两个非递减单链表进行合并，使其成为一个新的、非递减的单链表

16.单链表的应用--求两个集合的对称差

0. 前言

在计算机中主要有两种基本的存储结构用与存放线性表：顺序存储结构和链式存储结构。本文主要介绍链式存储结构的基本操作，即单链表的相关操作。

1. 单链表的存储结果的描述、定义

#define ElemType int        //ElemType为抽象数据类型，可以为int、char、struct等任意类型//为了方便，本文的ElemType为int类型
struct Node {ElemType data;            struct Node* next;        //结构体指针类型
};
typedef struct Node Node,* LinkList; 

 在这里，上述表示可以简化成

#define ElemType int
typedef struct Node {ElemType data;struct Node* next;
}Node,*LinkList;

2.单链表的初始化

注意，在对单链表的操作中，一般的函数要传递结构体的指针，例如我们在主函数里声明了结构体指针

LinkList L;        //L为结构体指针类型的变量

但是在初始化该结构体的时候，我们要malloc一块内存空间，然后让指针L指向这一块空间。

这就要求我们对指针L操作（L为LinkList类型，即结构体指针类型），因此我们要传递指针的指针，即我们要传递LinkList*类型的变量，所以初始化函数的函数原型为

void InitList(LinkList* L);                        //也可以写成 void InitList(Node**L); 二者等价

#include
void InitList(LinkList*);void InitList(LinkList* L)
{(*L) = (Node*)malloc(sizeof(Node));	//注意，malloc的头文件为#includeif (*L == NULL) {printf("Fail to initialize the list\n");exit(0);}(*L)->next = NULL;
}

2.头插法建表

为了方便，我们把ElemType看为int类型。头插法较为简单，但是插入的顺序是倒叙，例如我们输入1，2，3，在访问的时候会依次打印3，2，1。

scanf()!=EOF在不同的编译器里有不同的模拟方式，例如在DevC++里是在新的一行里键入Ctrl+Z后再次回车，在vs里是连续三次在新的一行里键入Ctrl+Z后回车。

void CreatFromHead(LinkList L)
{Node* s = NULL;int ch;while (scanf("%d", &ch) != EOF) {s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("Fail to creat new room\n");exit(0);}s->data = ch;s->next = L->next;L->next = s;}
}

 3.尾插法建表

尾插法建表比头插法稍微麻烦一点，但是实际上的效果更好，建议采用尾插法建表。

void CreatFromTail(LinkList L)
{Node* s = L, * r = NULL;int ch;while (scanf("%d",&ch) != EOF) {r = (Node*)malloc(sizeof(Node));if (r == NULL) {printf("Fail to creat new room\n");exit(0);}r->data = ch;r->next = s->next;s->next = r;s = r;}
}

4.访问输出单链表

由于在之前我们定义了ElemType为int类型，所以在打印的时候为%d

void Visit(LinkList L)
{Node* p = L->next;if (!p) {printf("LinkList is empty\n");exit(0);}while (p) {printf("%d ",p->data);p = p->next;}printf("\n");
}

 5.求单链表中元素的个数

int ListLength(LinkList L)
{Node* p = L;int count = 0;while (p->next) {p = p->next;count++;}return count;
}

6.求表中第i个元素的值

Node* GetData(LinkList L, int i)
{Node* p = L;int j = 0;while (p && j < i) {p = p->next;j++;}return p;
}

如果找不到第i个元素，则会返回空指针NULL，我们可以在主函数里加以判断。

7.在表中特定位置插入元素

void InsList(LinkList L, int i, ElemType e)
{Node* pre = L;int count = 0;while (pre && count < i - 1) {pre = pre->next;count++;}if (!pre) {printf("Illegal location\n");exit(0);}Node* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("Fail to creat new room\n");exit(0);}s->data = e;s->next = pre->next;pre->next = s;
}

8 .删除表中特定位置上的元素

void DelList(LinkList L, int i, ElemType* e)
{int count = 0;Node* pre = L;while (pre->next && count < i) {pre = pre->next;count++;}if (pre->next == NULL ) {printf("Illegal location\n");exit(0);}Node* temp = pre->next;pre->next = temp->next;free(temp);
}

9.寻找表中特定元素值的位置

Node* Locate(LinkList L, ElemType e)
{Node* p = L->next;while (p && p->data != e) {p = p->next;}//如果p为NULL,即没有找到元素e时，函数会返回NULL(此时p==NULL)//如果p->data为e，则找到了元素e，函数会返回其指针preturn p;
}

10.销毁该单链表

void DestroyList(LinkList* L)
{Node* p = *L;Node* temp = NULL;while (p) {temp = p->next;free(p);p = temp;}*L = NULL;
}

11.将表置为空表

void ClearList(LinkList L)
{Node* p = NULL;while (L->next) {p = L->next;L->next = p->next;free(p);}
}

12.单链表的排序

这里采用插入排序的方法，对单链表的元素按照升序排序

void SortList(LinkList L)
{if (L->next == NULL)	exit(0);Node* pre, * p;Node* s = L->next->next;Node* temp = NULL;L->next->next = NULL;while (s) {pre = L;p = L->next;while (p && p->data <= s->data) {pre = pre->next;p = p->next;}temp = s->next;pre->next = s;s->next = p;s = temp;}
}

13.单链表自身的逆置

void ReverseList(LinkList L)
{if (L->next == NULL) exit(0);Node* p = L->next->next;L->next->next = NULL;Node* temp = NULL;while (p) {temp = p->next;p->next = L->next;L->next = p;p = temp;}
}

14.单链表的排序

void SortList(LinkList L)
{if (L->next == NULL)	exit(0);Node* pre, * p;Node* s = L->next->next;Node* temp = NULL;L->next->next = NULL;while (s) {pre = L;p = L->next;while (p && p->data <= s->data) {pre = pre->next;p = p->next;}temp = s->next;pre->next = s;s->next = p;s = temp;}
}

15.对两个非递减单链表进行合并，使其成为一个新的、非递减的单链表

当我们传递两个非递减单链表的指针后（可以利用上面的函数SortList()来使单链变成非递减），该函数会返回给一个合并后的链表的指针，但是并没有开辟新 的空间来存放合并的单链表。

LinkList MergeList(LinkList LA, LinkList LB)
{LinkList LC = LA;Node* pa, * pb, * pc;pa = LA->next;pb = LB->next;pc = LC;LC->next = NULL;while (pa && pb) {if (pa->data > pb->data) {pc->next = pb;pc = pb;pb = pb->next;}else {pc->next = pa;pc = pa;pa = pa->next;}}if (!pa)pc->next = pb;else pc->next = pa;free(LB);return LC;
}

16.单链表的应用--求两个集合的对称差

集合LA和LB的对称差：所有属于LA但是不属于LB的元素的集合。

思路：我们可以遍历LA的元素，对LA的每一个元素，判断此元素是否在LB中存在；若存在这把LA中的这个元素删除，若不存在，则保留不动，继续判断LA下一个元素是否在LB中存在，如此循环。

void Difference(LinkList LA, LinkList LB)
{Node* pre = LA;Node* pb = NULL;Node* temp = NULL;while (pre->next) {pb = LB->next;while (pb && pb->data != pre->next->data)pb = pb->next;if (pb) {temp = pre->next;pre->next = temp->next;free(temp);}else {pre = pre->next;}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！