1.链表的介绍

1.1 什么是单链表

单链表是用一组任意的存储单元来存放线性表的结点，这组存储单元既可以是连续的，的，也可以是不连续的，甚至零散地分布在内存中的任何位置上。为了能正确表示结点的逻错关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址(或位置)息，这个信息称为指针或链。这两部分信息组成了链表中的结点结构。

讯享网

链式存储结构的优点：

（1）空间利用率高需要一个空间就分配一个空间

（2）数据元素的逻辑次序靠节点的指针来指示，插入和删除时不需要移动数据结点,任意位置插入删除时间复杂度为O(1) 

单链表的定义：

typedef struct SListNode { DateType data; //结点的数据域 struct SListNode *next; //结点的指针域 }SListNode; 

结点空间开辟：执行 SListNode*p之后，该指针变量指向的结点变量并未开辟空间，程序执行过程中，当需要时才产生，需要执行

讯享网p=(SListNode*)malloc(sizeof(SListNode))

后分配一个类型为ListNode的结点变量的空间。

结点空间释放：当p指向的结点变量不再需要的时候，可以通过执行free(p)释放。 

1.2 什么是循环链表

循环链表是一种特殊的链表数据结构，与单向链表或双向链表相比，循环链表的最后一个节点的下一个节点指向第一个节点，从而形成一个环形结构。因此，循环链表可以在最后一个节点后继续添加节点，并且可以像单向链表或双向链表一样遍历、查找和删除节点。循环链表通常有一个头指针和一个尾指针，它们指向第一个节点和最后一个节点，以便在添加或删除节点时快速定位。 

循环链表可以用于解决某些问题，例如模拟一个环形队列，或者用于实现循环播放的音乐列表等。循环链表的优点在于它具有链表的灵活性，同时可以避免在添加或删除节点时需要遍历整个链表的缺点 

循环链表的任意元素都有一个前驱和一个后继，所有数据元素在关系上构成逻辑上的环。循环链表是一种特殊的单链表，尾结点的指针指向首结点的地址。

循环链表的逻辑关系图如下：

1.3 单链表和循环列表的区别

（1）循环链表的操作和单链表基本一致。

（2）差别仅在于：当遍历链表时，判别当前指针P是否指向表尾结点的终止条件不同。

（3）由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像单链表那样判断p或p->next是否为空，而是判断它们是否等于头指针。

2.循环链表的基本运算

循环链表的基本运算包括以下几种：
（1）. 初始化链表：创建一个空的链表。
（2）. 插入结点：在链表中插入一个新的结点。
（3）. 删除结点：从链表中删除一个指定的结点。
（4）. 遍历链表：遍历链表中的所有结点，并对每个结点执行某些操作。
（5）. 查找结点：在链表中查找一个指定的结点。
（6）. 修改结点：修改链表中一个指定的结点的数据。
这些基本运算可以帮助我们实现各种不同的链表应用，例如实现栈、队列、优先队列等数据结构。

3.代码的实现

循环链表的初始化

int init(SingleLinkList Head) { if(Head != NULL) { /*申请内存*/ (*Head) = (SingleLinkList*)malloc(sizeof(SingleLinkList)); /*判断内存申请是否成功*/ if(*Head == NULL) { printf("申请内存错误， 初始化失败！[]\n"); return ; } // (*Head)->next = NULL; /*循环链表*/ /* (*Head)->next = *Head; */ (*Head)->next = *Head; return 0; } else { printf("该链表已经初始化！请删除后再执行此操作！[]\n"); return ; } } 

插入元素之头插法

讯享网int insert_head(SingleLinkList Head, DataType x) { SingleLinkNode *newNode; if(0) { printf("链表未初始化！[]\n"); return ; } newNode = (SingleLinkNode*)malloc(sizeof(SingleLinkNode)); if(!newNode) { printf("申请节点内存空间失败！[]\n"); return ; } newNode->data = x; newNode->next = (*Head)->next; (*Head)->next = newNode; return 0; }

插入元素之尾插法

int insert_tail(SingleLinkList Head, DataType x) { SingleLinkNode *newNode; SingleLinkNode *p; if(0) { printf("链表未初始化！[]\n"); return ; } newNode = (SingleLinkNode*)malloc(sizeof(SingleLinkNode)); if(!newNode) { printf("申请节点内存空间失败！[]\n"); return ; } newNode->data = x; // newNode->next = NULL; /* 循环链表 newNode->next = *Head; */ newNode->next = *Head; p = (*Head); while(p->next != NULL && p->next != *Head) { p = p->next; } p->next = newNode; return 0; }

插入元素，在位置i处插入元素x

讯享网int insert(SingleLinkList Head, int i, DataType x) { int j; SingleLinkNode *p; SingleLinkNode *newNode; /*对i进行判断，0<i<=length+1*/ if(i<1 || i>length(*Head)+1) { printf("位置i不是链表有效位置！[]\n"); return ; } p = (*Head); j = 1; while(j<i) { j++; p = p->next; } newNode = (SingleLinkNode*)malloc(sizeof(SingleLinkNode)); /*此处省略检测newNode是否申请成功*/ newNode->data = x; newNode->next = p->next; p->next = newNode; return 0; } 

查找值为x的元素，返回位置i

int find(SingleLinkList *Head, DataType x) { int i; SingleLinkNode *p; i = 1; p = Head->next; while(p && p->data != x) /*while( p!= Head && p->data != x) */ { i++; p = p->next; } if(!p) /* if(p->next == Head) */ { return 0; } else { return i; } }

链表长度

讯享网int length(SingleLinkList *Head) { int len=0; SingleLinkNode *p; p = Head->next; // while(p) /* while(p!=Head) */ while(p!=Head) { len++; p = p->next; } return len; }

输出链表

void print(SingleLinkList *Head) { SingleLinkNode *p; int i=0; p = Head->next; if(!p) /* if(p!=Head) */ { printf("链表为空！\n"); return; } // while(p!=Head) // { // p = p->next; // } // while(p) /* while(p!=Head) */ while(p != Head) { printf("Node[%d]. = %d\n", ++i, p->data); p = p->next; } }

 删除元素值为x的元素

讯享网int delete(SingleLinkList Head, DataType x) { int i; int j; SingleLinkNode *p; SingleLinkNode *q; /*要删除的元素x*/ i = find(*Head,x); if(!i) { printf("元素x【%d】不存在！\n", x); return ; } p = (*Head); j=1; while(j<i) { j++; p = p->next; } q = p->next; p->next = q->next; free(q); /*释放内存*/ return 0; } 

4.完整的demo

main.c

#include stdio.h #include string.h #include SingleLinkList.c #include welcome.h int main(int argc, char argv[]) { SingleLinkList Head; DataType x; int i,m,n,cmd; for(i=0;istrlen(welcome);i++) { printf(%c,welcome[i]); for(m=0;m1000;m++) for(n=0;n1000;n++) { ; } } printf(-----------简单链表演示程序----------n); do { printf(1. 初始化链表表n); printf(2. 插入元素（头插法）n); printf(3. 插入元素（尾插法）n); printf(4. 插入元素（在位置i插入）n); printf(5. 查找元素xn); printf(6. 求链表长度n); printf(7. 输出链表n); printf(8. 删除元素n); printf(10. 帮助n); printf(0. 退出n); printf(请输入您要进行的操作（1~6,0退出）：); scanf(%d, &cmd); switch(cmd) { case 1 if(!init(&Head)) { printf(链表已初始化！n); } break; case 2 printf(请输入插入元素x：x=); scanf(%d,&x); if(!insert_head(&Head,x)) { printf(元素（%d）已插入n, x); } break; case 3 printf(请输入插入元素x：x=); scanf(%d,&x); if(!insert_tail(&Head,x)) { printf(元素（%d）已插入n, x); } break; case 4 printf(请输入插入元素位置i和元素x（i，x）：); scanf(%d,%d, &i, &x); if(!insert(&Head, i, x)) { printf(已在位置（%d）插入元素（%d）！n,i, x); } break; case 5 printf(请输入要查找的元素x：); scanf(%d, &x); if((i = find(Head,x))) { printf(元素%d存在，在链表位置%d.n, x, i); } else { printf(在链表中未找到元素x。n); } break; case 6 printf(链表的长度为：%dn, length(Head)); break; case 7 print(Head); break; case 8 printf(请输入要删除的元素x：); scanf(%d, &x); if(!delete(&Head, x)) { printf(元素x【%d】已删除!n, x); } break; case 10 printf( 本程序为链表的演示程序，由张亚辉设计开发，程序完成了链表运算功能！。。。n); break; } }while(cmd != 0); return 0; }

 SingleLinkList.c

讯享网/* SingleLinkList.c */ #include "SingleLinkList.h" #include <stdlib.h> #include <stdio.h> /*1. 初始化*/ int init(SingleLinkList Head) { if(Head != NULL) { /*申请内存*/ (*Head) = (SingleLinkList*)malloc(sizeof(SingleLinkList)); /*判断内存申请是否成功*/ if(*Head == NULL) { printf("申请内存错误， 初始化失败！[]\n"); return ; } // (*Head)->next = NULL; /*循环链表*/ /* (*Head)->next = *Head; */ (*Head)->next = *Head; return 0; } else { printf("该链表已经初始化！请删除后再执行此操作！[]\n"); return ; } } /*2. 插入元素,头插法*/ int insert_head(SingleLinkList Head, DataType x) { SingleLinkNode *newNode; if(0) { printf("链表未初始化！[]\n"); return ; } newNode = (SingleLinkNode*)malloc(sizeof(SingleLinkNode)); if(!newNode) { printf("申请节点内存空间失败！[]\n"); return ; } newNode->data = x; newNode->next = (*Head)->next; (*Head)->next = newNode; return 0; } /*2. 插入元素， 尾插法*/ int insert_tail(SingleLinkList Head, DataType x) { SingleLinkNode *newNode; SingleLinkNode *p; if(0) { printf("链表未初始化！[]\n"); return ; } newNode = (SingleLinkNode*)malloc(sizeof(SingleLinkNode)); if(!newNode) { printf("申请节点内存空间失败！[]\n"); return ; } newNode->data = x; // newNode->next = NULL; /* 循环链表 newNode->next = *Head; */ newNode->next = *Head; p = (*Head); while(p->next != NULL && p->next != *Head) { p = p->next; } p->next = newNode; return 0; } /*2. 插入元素，在位置i处插入元素x */ int insert(SingleLinkList Head, int i, DataType x) { int j; SingleLinkNode *p; SingleLinkNode *newNode; /*对i进行判断，0<i<=length+1*/ if(i<1 || i>length(*Head)+1) { printf("位置i不是链表有效位置！[]\n"); return ; } p = (*Head); j = 1; while(j<i) { j++; p = p->next; } newNode = (SingleLinkNode*)malloc(sizeof(SingleLinkNode)); /*此处省略检测newNode是否申请成功*/ newNode->data = x; newNode->next = p->next; p->next = newNode; return 0; } /*3. 删除元素, 删除值为x的元素*/ int delete(SingleLinkList Head, DataType x) { int i; int j; SingleLinkNode *p; SingleLinkNode *q; /*要删除的元素x*/ i = find(*Head,x); if(!i) { printf("元素x【%d】不存在！\n", x); return ; } p = (*Head); j=1; while(j<i) { j++; p = p->next; } q = p->next; p->next = q->next; free(q); /*释放内存*/ return 0; } /*5. 查找值为x的元素，返回位置i */ int find(SingleLinkList *Head, DataType x) { int i; SingleLinkNode *p; i = 1; p = Head->next; while(p && p->data != x) /*while( p!= Head && p->data != x) */ { i++; p = p->next; } if(!p) /* if(p->next == Head) */ { return 0; } else { return i; } } /*4. 链表长度*/ int length(SingleLinkList *Head) { int len=0; SingleLinkNode *p; p = Head->next; // while(p) /* while(p!=Head) */ while(p!=Head) { len++; p = p->next; } return len; } /*6.输出链表*/ void print(SingleLinkList *Head) { SingleLinkNode *p; int i=0; p = Head->next; if(!p) /* if(p!=Head) */ { printf("链表为空！\n"); return; } // while(p!=Head) // { // p = p->next; // } // while(p) /* while(p!=Head) */ while(p != Head) { printf("Node[%d]. = %d\n", ++i, p->data); p = p->next; } }

 SingleLinkList.h

/* SingleLinkList.h */ typedef int DataType; typedef struct node { DataType data; /*数据域*/ struct node *next; /*指针域*/ }SingleLinkList, SingleLinkNode; /*1. 初始化*/ int init(SingleLinkList Head); /*2. 插入元素,头插法*/ int insert_head(SingleLinkList Head, DataType x); /*2. 插入元素， 尾插法*/ int insert_tail(SingleLinkList Head, DataType x); /*3. 删除元素*/ /*6.输出链表*/ void print(SingleLinkList *Head);

welcome.h

讯享网char welcome[] = "\n\ /\ \n\ ( *)======/\==== \n\ )( / \ \n\ __________/ ) / \ \n\ \___ / / \"\" \ \n\ \____ _/ / () \ \n\ / \__/ (----------) \n\ /____|__//_ ( 送给您- ) \n\ | ( 亲爱的 ) \n\ | ( )\n\ | (____)\n\ _|__\n\ \\ ☆新年 . 快乐☆\n\n";

5.知识拓展——一元多项式设计及加法运算

#include <stdio.h> #include<stdlib.h> typedef struct node//一元多项式定义 { float coef; // 系数 int expn; // 指数 struct node *next; // 后继 } pnode, *polynomial; // 一元多项式的创建 polynomial createpolyn(polynomial p, int m) { int i; polynomial q, pre, s; // 节点 q，pre，s p = (polynomial)malloc(sizeof(pnode)); // 生成新节点 p->next = 0; // 先建立一个头节点的单链表 p->expn = -1; // 头节点指数值设为-1 for (i = 0; i < m; i++) // 依次输入m个非零值 { s = (polynomial)malloc(sizeof(pnode)); // 生成新节点 printf("输入系数和指数："); scanf("%f%d", &s->coef, &s->expn); // 输入系数和指数 pre = p; // pre来保存q的前驱 q = p->next; // q初值为首节点 while (q && q->expn <= s->expn) // 找到第一个大于输入项指数的项q { pre = q; q = q->next; } s->next = q;pre->next = s; // 将输入项s，插入到q和pre之间 } printf("--创建成功--\n"); return p; }// 一元多项式打印 void pri(polynomial p) { polynomial q; int id = 1; q = p->next; // 第一项（首结点） printf("加法运算后结果为:\n"); while (q) { printf("第%d个结点：系数%f,指数%d\n", id, q->coef, q->expn); // 结点后移 q = q->next; id++; } // 一元多项式相加 return ; } polynomial addpolyn(polynomial pa, polynomial pb) { polynomial p1, p2, p3, q; int sum; // 系数和 sum p1 = pa->next;p2 = pb->next; p3 = pa; // p3 指向和多项式的当前结点 while (p1 && p2) // p1和p2均非空 { if (p1->expn == p2->expn) // 指数相同 { sum = p1->coef + p2->coef; // sum 保存两项的系数和 if (sum) // 系数和不为0 { p1->coef = sum; // 修改结点p1的系数值 p3->next = p1; p3 = p1; // 将修改后的结点p1链在p3之后 p1 = p1->next; // p1 指向后一项 q = p2; p2 = p2->next;free(q); // 删除pb当前结点q } else // 系数和为0 { q = p1; p1 = p1->next;free(q); // 删除pa当前结点pl q = p2; p2 = p2->next; free(q); // 删除pb当前结点p2 } } else { if (p1->expn <= p2->expn) // pa当前结点p1的指数值小 { p3->next = p1; // 将p1链在p3之后 p3 = p1; // p3 指向pl p1 = p1->next; // p1 指向后一场 } else { p3->next = p2; // pb当前结点p2的指数值小 p3 = p2; // 将p2链接在p3之后 p2 = p2->next; // p2指向后一项 } } } p3->next = p1 ? p1 : p2; // 插入非空多项式的剩余段 free(pb); // 释放pb的头结点 return pa; // 返回和多项式 } main() { printf("==================一元多项式演示程序（由张亚辉完成）==================\n\n\n"); int m; polynomial pa, pb, pc; // 声明一元多项式 printf("==================创建一元多项式==================\n"); printf("创建 A 项数:\n"); scanf("%d", &m); // 创建pa项数 pa = createpolyn(pa, m); // 创建一元多项式pa printf("创建 B 项数:\n"); scanf("%d", &m); // 创建pb项数 pb = createpolyn(pb, m); // 创建一元多项式pb printf("==================一元多项式相加==================\n"); pc = addpolyn(pa, pb); // 一元多项式相加 pri(pc); // 打印一元多项式 printf("=======================END=======================\n"); }

6.小结

 对于我这个刚学数据结构和C语言的萌新来说，这次的任务难度是有点大，看课本就像看天书一样，然后又去网上搜索各种资料和相关知识，结合老师在课堂上所讲的内容，并在线下与室友讨论，总算有了一点点的了解。

7.参考文献

《数据结构（C语言版）》

百度百科，CSDN，知乎，菜鸟教程

无所不能的互联网