本文最后更新于:41 分钟前
线性表 顺序存储结构和链式存储结构
线性表存储数据可细分为以下 2 种:
将数据依次存储在连续的整块物理空间中,这种存储结构称为顺序存储结构(简称顺序表); 数据分散的存储在物理空间中,通过一根线保存着它们之间的逻辑关系,这种存储结构称为链式存储结构(简称链表);
也就是说,线性表存储结构可细分为顺序存储结构和链式存储结构。
线性表常用术语
数据结构中,一组数据中的每个个体被称为“数据元素”(简称“元素”)。
另外,对于具有“一对一”逻辑关系的数据,我们一直在用“某一元素的左侧(前边)或右侧(后边)”这样不专业的词,其实线性表中有更准确的术语:
某一元素的左侧相邻元素称为“直接前驱”,位于此元素左侧的所有元素都统称为“前驱元素”; 某一元素的右侧相邻元素称为“直接后继”,位于此元素右侧的所有元素都统称为“后继元素”;
顺序表 顺序表存储数据时,会提前申请一整块足够大小的物理空间,然后将数据依次存储起来,存储时做到数据元素之间不留一丝缝隙,将“具有 ‘一对一’ 逻辑关系的数据按照次序连续存储到一整块物理空间上”的存储结构就是顺序存储结构。
顺序表的初始化 使用顺序表存储数据之前,除了要申请足够大小的物理空间之外,为了方便后期使用表中的数据,顺序表还需要实时记录以下 2 项数据:
顺序表申请的存储容量;
顺序表的长度,也就是表中存储数据元素的个数;
提示:正常状态下,顺序表申请的存储容量要大于顺序表的长度。
因此,我们需要自定义顺序表,C 语言实现代码如下:
typedef struct Table { int * head; int length; int size; }table;
注意,head 是我们声明的一个未初始化的动态数组,不要只把它看做是普通的指针。
接下来开始学习顺序表的初始化,也就是初步建立一个顺序表。建立顺序表需要做如下工作:
给 head 动态数据申请足够大小的物理空间;
给 size 和 length 赋初值;
因此,C 语言实现代码如下:
table initTable(){ table t; t.head = (int*)malloc(Size * sizeof(int));// 构造一个空的顺序表,动态申请存储空间 if (!t.head) // 如果申请失败,作出提示并直接退出程序 { printf("初始化失败" ); exit (0 ); } t.length = 0 ;// 空表的长度初始化为0 t.size = Size;// 空表的初始存储空间为Size return t; }
顺序表初始化过程中,要注意对物理空间的申请进行判断,对申请失败的情况进行处理
顺序表插入元素
向已有顺序表中插入数据元素,根据插入位置的不同,可分为以下 3 种情况:
插入到顺序表的表头; 在表的中间位置插入元素; 尾随顺序表中已有元素,作为顺序表中的最后一个元素;
虽然数据元素插入顺序表中的位置有所不同,但是都使用的是同一种方式去解决,即:通过遍历,找到数据元素要插入的位置,然后做如下两步工作:
将要插入位置元素以及后续的元素整体向后移动一个位置; 将元素放到腾出来的位置上;
顺序表插入数据元素的 C 语言实现代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 table addTable (table t, int elem, int add) { int i; if (add > t.length + 1 || add < 1 ) { printf ("插入位置有问题" ); return t; } if (t.length == t.size) { t.head = (int *)realloc (t.head, (t.size + 1 ) * sizeof (int )); if (!t.head) { printf ("存储分配失败" ); return t; } t.size += 1 ; } for (i = t.length - 1 ; i >= add - 1 ; i--) { t.head[i + 1 ] = t.head[i]; } t.head[add - 1 ] = elem; t.length++; return t; }
注意,动态数组额外申请更多物理空间使用的是 realloc 函数。
顺序表删除元素
从顺序表中删除指定元素,实现起来非常简单,只需找到目标元素,并将其后续所有元素整体前移 1 个位置即可。 后续元素整体前移一个位置,会直接将目标元素删除,可间接实现删除元素的目的。
因此,顺序表删除元素的 C 语言实现代码为:
table delTable(table t, int add) { int i; if (add > t.length || add < 1 ) { printf("被删除元素的位置有误" ); exit (0 ); } // 删除操作 for (i = add; i < t.length; i++) { t.head[i - 1 ] = t.head[i]; } t.length--; return t; }
顺序表更改元素
顺序表更改元素的实现过程是: 找到目标元素; 直接修改该元素的值;
顺序表更改元素的 C 语言实现代码为:
table amendTable(table t , int elem , int newElem ) { int add = selectTable(t , elem ) ; t.head[add - 1 ] = newElem; return t; }
顺序表查找元素
顺序表中查找目标元素,可以使用多种查找算法实现,比如说二分查找算法、插值查找算法等。
这里,我们选择顺序查找算法,具体实现代码为:
int selectTable(table t , int elem ) { int i; for (i = 0 ; i < t.length; i++) { if (t.head[i ] == elem) { return i + 1 ; } } return -1 ; }
完整的实现代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 #include <stdio.h> #include <stdlib.h> #define Size 5 typedef struct Table { int * head; int length; int size; }table;table initTable () { table t; t.head = (int *)malloc (Size * sizeof (int )); if (!t.head) { printf ("初始化失败" ); exit (0 ); } t.length = 0 ; t.size = Size; return t; }table addTable (table t, int elem, int add) { int i; if (add > t.length + 1 || add < 1 ) { printf ("插入位置有问题" ); return t; } if (t.length >= t.size) { t.head = (int *)realloc (t.head, (t.size + 1 ) * sizeof (int )); if (!t.head) { printf ("存储分配失败" ); } t.size += 1 ; } for (i = t.length - 1 ; i >= add - 1 ; i--) { t.head[i + 1 ] = t.head[i]; } t.head[add - 1 ] = elem; t.length++; return t; }table delTable (table t, int add) { int i; if (add > t.length || add < 1 ) { printf ("被删除元素的位置有误" ); exit (0 ); } for (i = add; i < t.length; i++) { t.head[i - 1 ] = t.head[i]; } t.length--; return t; }int selectTable (table t, int elem) { int i; for (i = 0 ; i < t.length; i++) { if (t.head[i] == elem) { return i + 1 ; } } return -1 ; }table amendTable (table t, int elem, int newElem) { int add = selectTable (t, elem); t.head[add - 1 ] = newElem; return t; }void displayTable (table t) { int i; for (i = 0 ; i < t.length; i++) { printf ("%d " , t.head[i]); } printf ("\n" ); }int main () { int i, add; table t1 = initTable (); for (i = 1 ; i <= Size; i++) { t1.head[i - 1 ] = i; t1.length++; } printf ("原顺序表:\n" ); displayTable (t1); printf ("删除元素1:\n" ); t1 = delTable (t1, 1 ); displayTable (t1); printf ("在第2的位置插入元素5:\n" ); t1 = addTable (t1, 5 , 2 ); displayTable (t1); printf ("查找元素3的位置:\n" ); add = selectTable (t1, 3 ); printf ("%d\n" , add); printf ("将元素3改为6:\n" ); t1 = amendTable (t1, 3 , 6 ); displayTable (t1); return 0 ; }
程序运行结果为:
原顺序表: 1 2 3 4 5 删除元素1: 2 3 4 5 在第2的位置插入元素5: 2 5 3 4 5 查找元素3的位置: 3 将元素3改为6: 2 5 6 4 5
链表 链表的节点
链表中每个数据的存储都由以下两部分组成:
数据元素本身,其所在的区域称为数据域; 指向直接后继元素的指针,所在的区域称为指针域;
头节点,头指针和首元节点
一个完整的链表需要由以下几部分构成:
头指针:一个普通的指针,它的特点是永远指向链表第一个节点的位置。很明显,头指针用于指明链表的位置,便于后期找到链表并使用表中的数据;
节点:链表中的节点又细分为头节点、首元节点和其他节点:
头节点:其实就是一个不存任何数据的空节点,通常作为链表的第一个节点。对于链表来说,头节点不是必须的,它的作用只是为了方便解决某些实际问题;
首元节点:由于头节点(也就是空节点)的缘故,链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓,没有实际意义;
其他节点:链表中其他的节点;
注意:链表中有头节点时,头指针指向头节点;反之,若链表中没有头节点,则头指针指向首元节点。
链表中每个节点的具体实现,需要使用 C 语言中的结构体,具体实现代码为:
typedef struct Link { char elem; struct Link * next ; }link;
提示,由于指针域中的指针要指向的也是一个节点,因此要声明为 Link 类型(这里要写成 struct Link* 的形式)。
链表的创建(初始化)
创建一个链表需要做如下工作: 声明一个头指针(如果有必要,可以声明一个头节点); 创建多个存储数据的节点,在创建的过程中,要随时与其前驱节点建立逻辑关系;
例如,创建一个存储 {1,2,3,4} 且无头节点的链表,C 语言实现代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 link * initLink() { int i; link * p = NULL ; link * temp = (link *)malloc(sizeof(link )); temp->elem = 1 ; temp->next = NULL ; p = temp; for (i = 2 ; i < 5 ; i++) { link *a = (link *)malloc(sizeof(link )); a->elem = i; a->next = NULL ; temp->next = a; temp = temp->next; } return p; }
如果想创建一个存储 {1,2,3,4} 且含头节点的链表,则 C 语言实现代码为:
link * initLink(){ int i; link * p=(link *)malloc(sizeof(link ));// 创建一个头结点 link * temp=p;// 声明一个指针指向头结点, //生成链表 for (i=1 ; i<5 ; i++) { link *a=(link *)malloc(sizeof(link )); a->elem=i; a->next =NULL; temp->next =a; temp=temp->next ; } return p; }
链表插入元素
同顺序表一样,向链表中增添元素,根据添加位置不同,可分为以下 3 种情况: 插入到链表的头部(头节点之后),作为首元节点; 插入到链表中间的某个位置; 插入到链表的最末端,作为链表中最后一个数据元素;
虽然新元素的插入位置不固定,但是链表插入元素的思想是固定的,只需做以下两步操作,即可将新元素插入到指定的位置: 将新结点的 next 指针指向插入位置后的结点; 将插入位置前结点的 next 指针指向插入结点;
链表插入元素的操作:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 //p为原链表,elem表示新数据元素,add表示新元素要插入的位置link * insertElem(link * p, int elem, int add) { link * temp = p;// 创建临时结点temp link * c = NULL; int i = 0 ; //首先找到要插入位置的上一个结点 for (i = 1 ; i < add; i++) { if (temp == NULL) { printf ("插入位置无效\n" ); return p; } temp = temp->next ; } //创建插入结点c c = (link *)malloc(sizeof(link )); c->elem = elem; //向链表中插入结点 //链表插入元素的操作必须是先步骤 1 ,再步骤 2 ;反之,若先执行步骤 2 ,会导致插入位置后续的部分链表丢失,无法再实现步骤 1 。 c->next = temp->next ; // ① temp->next = c; // ② return p; }
提示,insertElem 函数中加入一个 if 语句,用于判断用户输入的插入位置是否有效。例如,在已存储 {1,2,3} 的链表中,用户要求在链表中第 100 个数据元素所在的位置插入新元素,显然用户操作无效,此时就会触发 if 语句。
链表删除元素
从链表中删除指定数据元素时,实则就是将存有该数据元素的节点从链表中摘除,同时对不再利用的存储空间要及时释放。因此,从链表中删除数据元素需要进行以下 2 步操作:
将结点从链表中摘下来; 手动释放掉结点,回收被结点占用的存储空间;
其中,从链表上摘除某节点的实现非常简单,只需找到该节点的直接前驱节点 temp,执行一行程序:
temp->next=temp->next->next;
因此,链表删除元素的 C 语言实现如下所示:
//p为原链表,add为要删除元素的值link * delElem(link * p, int add) { link * temp = p; link * del = NULL; int i = 0 ; //temp指向被删除结点的上一个结点 for (i = 1 ; i < add; i++) { temp = temp->next ; } del = temp->next ;// 单独设置一个指针指向被删除结点,以防丢失 temp->next = temp->next ->next ;// 删除某个结点的方法就是更改前一个结点的指针域 free(del);// 手动释放该结点,防止内存泄漏 return p; }
我们可以看到,从链表上摘下的节点 del 最终通过 free 函数进行了手动释放。
静态链表 静态链表存储数据,数据全部存储在数组中(和顺序表一样),但存储位置是随机的,数据之间”一对一”的逻辑关系通过一个整形变量(称为”游标”,和指针功能类似)维持(和链表类似)。
静态链表中的节点
静态链表存储数据元素也需要自定义数据类型,至少需要包含以下 2 部分信息: 数据域:用于存储数据元素的值; 游标:其实就是数组下标,表示直接后继元素所在数组中的位置;
因此,静态链表中节点的构成用 C 语言实现为:
typedef struct { int data; int cur; }component;
备用链表
静态链表中,除了数据本身通过游标组成的链表外,还需要有一条连接各个空闲位置的链表,称为备用链表。
备用链表的作用是回收数组中未使用或之前使用过(目前未使用)的存储空间,留待后期使用。也就是说,静态链表使用数组申请的物理空间中,存有两个链表,一条连接数据,另一条连接数组中未使用的空间。 通常,备用链表的表头位于数组下标为 0(a[0]) 的位置,而数据链表的表头位于数组下标为 1(a[1])的位置。
静态链表中设置备用链表的好处是,可以清楚地知道数组中是否有空闲位置,以便数据链表添加新数据时使用。比如,若静态链表中数组下标为 0 的位置上存有数据,则证明数组已满。
静态链表的实现 假设使用静态链表(数组长度为 6)存储 {1,2,3},则需经历以下几个阶段。
在数据链表未初始化之前,数组中所有位置都处于空闲状态,因此都应被链接在备用链表上,当向静态链表中添加数据时,需提前从备用链表中摘除节点,以供新数据使用。
备用链表摘除节点最简单的方法是摘除 a[0] 的直接后继节点;同样,向备用链表中添加空闲节点也是添加作为 a[0] 新的直接后继节点。因为 a[0] 是备用链表的第一个节点,我们知道它的位置,操作它的直接后继节点相对容易,无需遍历备用链表,耗费的时间复杂度为 O(1)。
下面给出了创建一个不带头结点的静态链表的 C 语言实现代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 #include <stdio.h> #define maxSize 6 typedef struct { int data; int cur; }component;void reserveArr (component *array) ;int initArr (component *array) ;void displayArr (component * array, int body) ;int mallocArr (component * array) ;int main () { component array[maxSize]; int body = initArr (array); printf ("静态链表为:\n" ); displayArr (array, body); return 0 ; }void reserveArr (component *array) { int i = 0 ; for (i = 0 ; i < maxSize; i++) { array[i].cur = i + 1 ; array[i].data = 0 ; } array[maxSize - 1 ].cur = 0 ; }int mallocArr (component * array) { int i = array[0 ].cur; if (array[0 ].cur) { array[0 ].cur = array[i].cur; } return i; }int initArr (component *array) { int tempBody = 0 , body = 0 ; int i = 0 ; reserveArr (array); body = mallocArr (array); array[body].data = 1 ; array[body].cur = 0 ; tempBody = body; for (i = 2 ; i < 4 ; i++) { int j = mallocArr (array); array[j].data = i; array[tempBody].cur = j; tempBody = j; } array[tempBody].cur = 0 ; return body; }void displayArr (component * array, int body) { int tempBody = body; while (array[tempBody].cur) { printf ("%d,%d\n" , array[tempBody].data, array[tempBody].cur); tempBody = array[tempBody].cur; } printf ("%d,%d\n" , array[tempBody].data, array[tempBody].cur); }
代码输出结果为:
静态链表添加元素
void insertArr(component * array , int body , int add , int num ) { int tempBody = body; int i = 0 , insert = 0 ; for (i = 1 ; i < add; i++) { tempBody = array [tempBody ] .cur; } insert = mallocArr(array ) ; array [insert ] .data = num; array [insert ] .cur = array [tempBody ] .cur; array [tempBody ] .cur = insert; }
静态链表删除元素
静态链表中删除指定元素,只需实现以下 2 步操作:
将存有目标元素的节点从数据链表中摘除; 将摘除节点添加到备用链表,以便下次再用;
比较特殊的是,对于无头结点的数据链表来说,如果需要删除头结点,则势必会导致数据链表的表头不再位于数组下标为 1 的位置,换句话说,删除头结点之后,原数据链表中第二个结点将作为整个链表新的首元结点。
若问题中涉及大量删除元素的操作,建议在建立静态链表之初创建一个带有头节点的静态链表,方便实现删除链表中第一个数据元素的操作。
如下是针对无头结点的数据链表,实现删除操作的 C 语言代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 int deletArr(component * array , int body , int num ) { int tempBody = body; int del = 0 ; int newbody = 0 ; while (array [tempBody ] .data != num) { tempBody = array [tempBody ] .cur; if (tempBody == 0 ) { printf("链表中没有此数据" ); return; } } del = tempBody; tempBody = body; if (del == body) { newbody = array [del ] .cur; freeArr(array , del ) ; return newbody; } else { while (array [tempBody ] .cur != del) { tempBody = array [tempBody ] .cur; } array [tempBody ] .cur = array [del ] .cur; freeArr(array , del ) ; return body; } }
静态链表中更改数据
更改静态链表中的数据,只需找到目标元素所在的节点,直接更改节点中的数据域即可。
实现此操作的 C 语言代码如下: void amendElem(component * array , int body , int oldElem , int newElem ) { int add = selectNum(array , body , oldElem ) ; if (add == -1 ) { printf("无更改元素" ); return; } array [add ] .data = newElem; }
静态链表查找元素
静态链表查找指定元素,由于我们只知道静态链表第一个元素所在数组中的位置,因此只能通过逐个遍历静态链表的方式,查找存有指定数据元素的节点。
静态链表查找指定数据元素的 C 语言实现代码如下:int selectNum(component * array, int body , int num) { while (array[body ].cur != 0 ) { if (array[body ].data == num) { return body ; } body = array[body ].cur; } if (array[body ].data == num) { return body ; } return -1 ; }
总结
这里给出以上对静态链表做 “增删查改” 操作的完整实现代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 #include <stdio.h> #define maxSize 7 typedef struct { int data; int cur; }component; void reserveArr(component * array ) ;int initArr(component * array ) ; void insertArr(component * array , int body , int add , int num ) ;int deletArr(component * array , int body , int num ) ;int selectNum(component * array , int body , int num ) ; void amendElem(component * array , int body , int oldElem , int newElem ) ; void displayArr(component * array , int body ) ;int mallocArr(component * array ) ; void freeArr(component * array , int k ) ;int main() { component array [maxSize ] ; int body = initArr(array ) ; int selectAdd; printf("静态链表为:\n" ); displayArr(array , body ) ; printf("在第3的位置上插入元素4:\n" ); insertArr(array , body , 3, 4) ; displayArr(array , body ) ; printf("删除数据域为1的结点:\n" ); body = deletArr(array , body , 1) ; displayArr(array , body ) ; printf("查找数据域为4的结点的位置:\n" ); selectAdd = selectNum(array , body , 4) ; printf("%d\n" , selectAdd); printf("将结点数据域为4改为5:\n" ); amendElem(array , body , 4, 5) ; displayArr(array , body ) ; return 0 ; } void reserveArr(component * array ) { int i = 0 ; for (i = 0 ; i < maxSize; i++) { array [i ] .cur = i + 1 ; } array [maxSize - 1 ] .cur = 0 ; }int initArr(component * array ) { int tempBody = 0 , body = 0 ; int i = 0 ; reserveArr(array ) ; body = mallocArr(array ) ; array [body ] .data = 1 ; array [body ] .cur = 0 ; tempBody = body; for (i = 2 ; i < 4 ; i++) { int j = mallocArr(array ) ; array [j ] .data = i; array [tempBody ] .cur = j; tempBody = j; } array [tempBody ] .cur = 0 ; return body; } void insertArr(component * array , int body , int add , int num ) { int tempBody = body; int i = 0 , insert = 0 ; for (i = 1 ; i < add; i++) { tempBody = array [tempBody ] .cur; } insert = mallocArr(array ) ; array [insert ] .data = num; array [insert ] .cur = array [tempBody ] .cur; array [tempBody ] .cur = insert; }int deletArr(component * array , int body , int num ) { int tempBody = body; int del = 0 ; int newbody = 0 ; while (array [tempBody ] .data != num) { tempBody = array [tempBody ] .cur; if (tempBody == 0 ) { printf("链表中没有此数据" ); return; } } del = tempBody; tempBody = body; if (del == body) { newbody = array [del ] .cur; freeArr(array , del ) ; return newbody; } else { while (array [tempBody ] .cur != del) { tempBody = array [tempBody ] .cur; } array [tempBody ] .cur = array [del ] .cur; freeArr(array , del ) ; return body; } }int selectNum(component * array , int body , int num ) { while (array [body ] .cur != 0 ) { if (array [body ] .data == num) { return body; } body = array [body ] .cur; } if (array [body ] .data == num) { return body; } return -1 ; } void amendElem(component * array , int body , int oldElem , int newElem ) { int add = selectNum(array , body , oldElem ) ; if (add == -1 ) { printf("无更改元素" ); return; } array [add ] .data = newElem; } void displayArr(component * array , int body ) { int tempBody = body; while (array [tempBody ] .cur) { printf("%d,%d " , array [tempBody ] .data, array [tempBody ] .cur); tempBody = array [tempBody ] .cur; } printf("%d,%d\n" , array [tempBody ] .data, array [tempBody ] .cur); }int mallocArr(component * array ) { int i = array [0 ] .cur; if (array [0 ] .cur) { array [0 ] .cur = array [i ] .cur; } return i; } void freeArr(component * array , int k ) { array [k ] .cur = array [0 ] .cur; array [0 ] .cur = k; }
程序运行结果为:
静态链表为:1,2 2,3 3 ,0 在第3 的位置上插入元素4 :1,2 2,3 3,4 4,0 删除数据域为1 的结点:2,3 3,4 4 ,0 查找数据域为4 的结点的位置:4 将结点数据域为4 改为5 :2,3 3,4 5 ,0
循环链表(约瑟夫环)的建立及C语言实现 循环链表实现约瑟夫环
约瑟夫环问题,是一个经典的循环链表问题,题意是:已知 n 个人(分别用编号 1,2,3,…,n 表示)围坐在一张圆桌周围,从编号为 k 的人开始顺时针报数,数到 m 的那个人出列;他的下一个人又从 1 开始,还是顺时针开始报数,数到 m 的那个人又出列;依次重复下去,直到圆桌上剩余一个人。
如图 2 所示,假设此时圆周周围有 5 个人,要求从编号为 3 的人开始顺时针数数,数到 2 的那个人出列:
http://data.biancheng.net/uploads/allimg/170718/2-1FGQ54403413.png
图 2 循环链表实现约瑟夫环
出列顺序依次为:
编号为 3 的人开始数 1,然后 4 数 2,所以 4 先出列; 4 出列后,从 5 开始数 1,1 数 2,所以 1 出列; 1 出列后,从 2 开始数 1,3 数 2,所以 3 出列; 3 出列后,从 5 开始数 1,2 数 2,所以 2 出列; 最后只剩下 5 自己,所以 5 胜出。
约瑟夫环问题有多种变形,比如顺时针转改为逆时针等,虽然问题的细节有多种变数,但解决问题的中心思想是一样的,即使用循环链表。
通过以上的分析,我们可以尝试编写 C 语言代码,完整代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 #include <stdio.h> #include <stdlib.h> typedef struct node { int number; struct node * next ; }person;person * initLink (int n) { int i = 0 ; person * head = NULL , *cyclic = NULL ; head = (person*)malloc (sizeof (person)); head->number = 1 ; head->next = NULL ; cyclic = head; for (i = 2 ; i <= n; i++) { person * body = (person*)malloc (sizeof (person)); body->number = i; body->next = NULL ; cyclic->next = body; cyclic = cyclic->next; } cyclic->next = head; return head; }void findAndKillK (person * head, int k, int m) { person * p = NULL ; person * tail = head; while (tail->next != head) { tail = tail->next; } p = head; while (p->number != k) { tail = p; p = p->next; } while (p->next != p) { int i = 0 ; for (i = 1 ; i < m; i++) { tail = p; p = p->next; } tail->next = p->next; printf ("出列人的编号为:%d\n" , p->number); free (p); p = tail->next; } printf ("出列人的编号为:%d\n" , p->number); free (p); }int main () { int n = 0 , k = 0 , m = 0 ; person * head = NULL ; printf ("输入圆桌上的人数:" ); scanf ("%d" , &n); head = initLink (n); printf ("从第几个人开始报数(k>1且k<%d):" , n); scanf ("%d" , &k); printf ("数到几的人出列:" ); scanf ("%d" , &m); findAndKillK (head, k, m); return 0 ; }
输出结果:
输入圆桌上的人数:5 从第几个人开始报数(k>1且k<5):3 数到几的人出列:2 出列人的编号为:4 出列人的编号为:1 出列人的编号为:3 出列人的编号为:2 出列人的编号为:5
最后出列的人,即为胜利者。当然,你也可以改进程序,令查找出最后一个人时,输出此人胜利的信息。
总结
循环链表和动态链表唯一不同在于它的首尾连接,这也注定了在使用循环链表时,附带最多的操作就是遍历链表。
在遍历的过程中,尤其要注意循环链表虽然首尾相连,但并不表示该链表没有第一个节点和最后一个结点。所以,不要随意改变头指针的指向。
双向链表及其创建 双向链表中各节点包含以下 3 部分信息:
指针域:用于指向当前节点的直接前驱节点; 数据域:用于存储数据元素; 指针域:用于指向当前节点的直接后继节点。
双链表的节点结构用 C 语言实现为:
typedef struct line { struct line * prior; int data; struct line * next; }line ;
双向链表的创建
同单链表相比,双链表仅是各节点多了一个用于指向直接前驱的指针域。因此,我们可以在单链表的基础轻松实现对双链表的创建。
和创建单链表不同的是,创建双向链表的过程中,每一个新节点都要和前驱节点之间建立两次链接,分别是:
将新节点的 prior 指针指向直接前驱节点; 将直接前驱节点的 next 指针指向新节点;
这里给出创建双向链表的 C 语言实现代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 line* initLine (line * head) { int i = 0 ; line * list = NULL ; head = (line*)malloc (sizeof (line)); head->prior = NULL ; head->next = NULL ; head->data = 1 ; list = head; for (i = 2 ; i <= 5 ; i++) { line * body = (line*)malloc (sizeof (line)); body->prior = NULL ; body->next = NULL ; body->data = i; list->next = body; body->prior = list; list = list->next; } return head; }
双向链表添加节点
根据数据添加到双向链表中的位置不同,可细分为以下 3 种情况:
添加至表头 将新数据元素添加到表头,只需要将该元素与表头元素建立双层逻辑关系即可。
换句话说,假设新元素节点为 temp,表头节点为 head,则需要做以下 2 步操作即可: temp->next=head; head->prior=temp; 将 head 移至 temp,重新指向新的表头;
添加至表的中间位置
同单链表添加数据类似,双向链表中间位置添加数据需要经过以下 2 个步骤:
新节点先与其直接后继节点建立双层逻辑关系; 新节点的直接前驱节点与之建立双层逻辑关系;
添加至表尾
与添加到表头是一个道理,实现过程如下:
找到双链表中最后一个节点; 让新节点与最后一个节点进行双层逻辑关系;
参考代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 line * insertLine(line * head, int data , int add) { line * temp = (line*)malloc(sizeof(line)); temp ->data = data ; temp -> prior = NULL; temp -> next = NULL; if (add == 1 ) { temp -> next = head; head -> prior = temp; head = temp; } else { int i = 0 ; line * body = head; for (i = 1 ; i < add - 1 ; i++) { body = body-> next; if (body == NULL) { printf("插入位置有误\n" ); break; } } if (body) { if (body-> next == NULL) { body -> next = temp; temp -> prior = body; } else { body ->next -> prior = temp; temp ->next = body-> next; body -> next = temp; temp -> prior = body; } } } return head; }
双向链表删除节点
双链表删除结点时,只需遍历链表找到要删除的结点,然后将该节点从表中摘除即可。
双向链表删除节点的 C 语言实现代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 line * delLine(line * head, int data ) { line * temp = head; while (temp) { if (temp->data == data ) { temp ->prior ->next = temp-> next; temp ->next ->prior = temp-> prior; free(temp); return head; } temp = temp-> next; } printf("链表中无该数据元素\n" ); return head; }
双向链表更改节点
更改双链表中指定结点数据域的操作是在查找的基础上完成的。实现过程是:通过遍历找到存储有该数据元素的结点,直接更改其数据域即可。
实现此操作的 C 语言实现代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 //更新函数,其中,add 表示更改结点在双链表中的位置,newElem 为新数据的值line *amendElem(line * p, int add , int newElem) { int i = 0 ; line * temp = p; //遍历到被删除结点 for (i = 1 ; i < add ; i++) { temp = temp ->next; if (temp == NULL ) { printf("更改位置有误!\n"); break; } } if (temp ) { temp ->data = newElem; } return p; }
双向链表查找节点
通常,双向链表同单链表一样,都仅有一个头指针。因此,双链表查找指定元素的实现同单链表类似,都是从表头依次遍历表中元素。
C 语言实现代码为:
int selectElem (line * head, int elem) { line * t = head; int i = 1 ; while (t) { if (t->data == elem) { return i; } i++; t = t->next; } return -1 ; }
总结
这里给出双链表中对数据进行 “增删查改” 操作的完整实现代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 #include <stdio.h> #include <stdlib.h> typedef struct line { struct line * prior ; int data; struct line * next ; }line;line* initLine (line * head) ;line * insertLine (line * head, int data, int add) ;line * delLine (line * head, int data) ;int selectElem (line * head, int elem) ;line *amendElem (line * p, int add, int newElem) ;void display (line * head) ;int main () { line * head = NULL ; printf ("初始链表为:\n" ); head = initLine (head); display (head); printf ("在表中第 3 的位置插入新元素 7:\n" ); head = insertLine (head, 7 , 3 ); display (head); printf ("删除元素 2:\n" ); head = delLine (head, 2 ); display (head); printf ("元素 3 的位置是:%d\n" , selectElem (head, 3 )); printf ("将第 3 个节点存储的数据改为 6:\n" ); head = amendElem (head, 3 , 6 ); display (head); return 0 ; }line* initLine (line * head) { int i = 0 ; line * list = NULL ; head = (line*)malloc (sizeof (line)); head->prior = NULL ; head->next = NULL ; head->data = 1 ; list = head; for (i = 2 ; i <= 3 ; i++) { line * body = (line*)malloc (sizeof (line)); body->prior = NULL ; body->next = NULL ; body->data = i; list->next = body; body->prior = list; list = list->next; } return head; }line * insertLine (line * head, int data, int add) { line * temp = (line*)malloc (sizeof (line)); temp->data = data; temp->prior = NULL ; temp->next = NULL ; if (add == 1 ) { temp->next = head; head->prior = temp; head = temp; } else { int i = 0 ; line * body = head; for (i = 1 ; i < add - 1 ; i++) { body = body->next; if (body == NULL ) { printf ("插入位置有误\n" ); break ; } } if (body) { if (body->next == NULL ) { body->next = temp; temp->prior = body; } else { body->next->prior = temp; temp->next = body->next; body->next = temp; temp->prior = body; } } } return head; }line * delLine (line * head, int data) { line * temp = head; while (temp) { if (temp->data == data) { temp->prior->next = temp->next; temp->next->prior = temp->prior; free (temp); return head; } temp = temp->next; } printf ("链表中无该数据元素\n" ); return head; }int selectElem (line * head, int elem) { line * t = head; int i = 1 ; while (t) { if (t->data == elem) { return i; } i++; t = t->next; } return -1 ; }line *amendElem (line * p, int add, int newElem) { int i = 0 ; line * temp = p; for (i = 1 ; i < add; i++) { temp = temp->next; if (temp == NULL ) { printf ("更改位置有误!\n" ); break ; } } if (temp) { temp->data = newElem; } return p; }void display (line * head) { line * temp = head; while (temp) { if (temp->next == NULL ) { printf ("%d\n" , temp->data); } else { printf ("%d->" , temp->data); } temp = temp->next; } }
程序执行结果为:
初始链表为:1 ->2 ->3 在表中第 3 的位置插入新元素 7 :1 ->2 ->7 ->3 删除元素 2 :1 ->7 ->3 元素 3 的位置是:3 将第 3 个节点存储的数据改为 6 :1 ->7 ->6