线性表

线性表的主要运算（C++版本） Listinit(&L)：初始化，构造一个空的线性表L Listdestory(&L)：如果线性表L存在，则将其销毁 Listclear(&L)：将已经存在的线性表L置为空表 Listlength(L)：对于给定的线性表L，求其线性表的长度，也就是返回元素个数 Locatelem(L,x)：在线性表L中，返回第一个值为x的元素在线性表中的位序，如果不存在返回0 Listinsert(&L,i,e)：在线性表L中第i个元素之前插入新元素e，i的合法值大于等于1且小于等于线性表长度+1；插入后，线性表长度加一 Listdelete(&L,i,&e)：从线性表L中删除第i个元素，并用e返回其值，i的合法值大于等于1且小于等于线性表长度；删除后，线性表长度减一。

顺序表和单链表

顺序表

和数组类似，逻辑上相邻的结点物理位置也相邻，这里主要记录单链表

单链表

单链表重点在于理解，头结点和头指针 每个结点只含有一个指针的链表是单链表 它不要求逻辑上相邻的元素在物理位置上一定是相邻的，因此是非顺序存储结构

头结点： 头结点不一定存在 头节点存放在第一个元素的结点之前 它的数据域一般没有意义，（但也可以存储标题、日期、建表人等信息） 头结点的存在是为了在某些时候更方便的处理链表 如对第一个元素前进行插入或者删除该结点，头结点能帮我们找到第一个元素的位置，因为它指向第一个元素。头结点的指针域指向第一个元素。

头指针： 头指针是必须存在 因为我们需要知道元素的位置，这个必须由指针来决定！

头指针是指向链表第一个结点的指针！

无论链表是否为空链表，头指针一定要有！

知道了头指针，也可以知道链表其他元素的位置！

头指针也就是平常所说的标识

————————————————————————————— 如图： 不带头结点，但头指针必须存在！

下图：带头结点的单链表 重点在于理解 比如第二幅图 头指针q指向头结点，那么它已经代表了头结点的位置 那么头结点的数据域 q->data 就是为头结点的数据

q->next 代表指向保存第一个元素的结点 q->next-data 就代表第一个结点的元素 q->next->next 代表指向保存第二个元素的结点

单链表实现

（另外一种模式） 在构建链表时，需要逐个创建结点，并且把生成的每个结点加入到链表中。创建结点包括3个步骤：

1.为结点分配内存单元； 2.把数据存储到结点中； 3.把结点插入到链表中。 —————— 借用“指针”数据类型来描述链表：

#include <iostream> #include<malloc.h>//包含malloc()、realloc()函数 using namespace std; typedef int status;//status 为整形 typedef int elementype;//elemengtype 为整形 typedef struct node { elementype data;//data为整形 因为elementype 为int的意思 struct node *next;//指向链表中的下一个结点 }node, *linklist;//*LinkList表示的是一个结构体指针变量 //而 &LinkList 则表示引用，注意，这里是C++里面的内容，C里面不支持这种写法，在C编译下会报错，而在C++编译环境下则不会。

这种链表称为动态链表，线性表中的结点类型为node，而linklist为指向结点的指针类型。

构造带头结点的空链表

//构造一个带头结点的空链表 int Initlist_l(linklist &l)//l为单链表的头指针，头指针可以表示一个确定的单链表 { if (l = (node*)malloc(sizeof(node))) return 0; l->next = NULL;//头结点指向下一个为空 return 1; }

(node*)malloc(sizeof(node))的意思是分配一个大小为node类型的内存，并将这个内存地址转化为node*型，然后将赋给l，所以l为地址。

创建具有n个结点的线性表

//创建具有n个结点的线性表 status createlist_l(linklist &l, int n)//不清楚这里要不要带& &是取地址值 { linklist q, p;//定义指针变量q,p int i; q = l;//l代表首地址 for (i = 1; i <= n; i++) { p = (linklist)malloc(sizeof(node));//每次申请新的结点 printf("请依次输入链表："); scanf_s("%d", &p->data);//输入下一个结点的数据 q->next = p;//使得前驱指针指向下一个新的结点 q = p;//p往后移 } q->next = NULL;//知道n个结点输入完毕，指针域指向NULL跳出 return 1; }

打印输入的线性表

//打印输入的线性表 void prinlist_l(linklist l) { linklist p;//一般先把首地址赋予一个指针变量 int i = 0; p = l->next;//l代表首地址 取下一个 就是第一个结点的位置 while (p != NULL) { i++;//从第一个开始到最后一个元素 printf("第%d个元素是：", i); printf(" %d \n", p->data);//第一个结点的元素 p = p->next;//找到该结点的元素后转向下一个结点 } }

在第i个位置插入结点e

//在第i个位置插入结点e status linklist_l(linklist l, int i, elementype e) { linklist p, s; int j; p = l, j = 0;//l为头指针 while (p&&j < i - 1) { p = p->next;//寻找第i-1个结点，循环之后到达i-1所在位置的数据域 ++j; } if (!p || j > i - 1)//i如果超出链表范围或者j大于等于i 则无效 { printf("输入错误！\n"); return 0; } s = (node*)malloc(sizeof(node));//创造新的结点 s->data = e;//e保存在s结点的数据域中 s->next = p->next;//将新的结点s->next定为 p->next位置的结点 也就是使得s->next 为 i结点，此时i中元素有e p->next = s;//指向下一个结点 //输出新的链表 p = l;//l始终为首地址 头指针 p = p->next; printf("得到新的链表：\n"); while (p != NULL) { printf(" %d ", p->data); p = p->next; } printf("\n"); return 1; }

将第i个位置的结点删除

//将第i个位置的结点删除 status listdelete_l(linklist l, int i) { linklist p, q; int j, e; p = l; j = 0; while (p->next&&j < i - 1)//使得p->next结点在i-1位置上 { p = p->next; ++j;//p->next 赋予 p } if (!(p->next) || j > i - 1) { printf("输入错误！\n"); return 0; } q = p->next; //i位置结点为q p->next = q->next;//i+1位置的结点取代i位置的结点 free(q);//释放q p = l->next; printf("你将得到新的链表\n"); while (p != NULL) { e = p->data; printf(" %d ", e); p = p->next; } printf("\n"); return 1; }

整体实现

#include <iostream> #include<malloc.h>//包含malloc()、realloc()函数 using namespace std; typedef int status;//status 为整形 typedef int elementype;//elemengtype 为整形 typedef struct node { elementype data;//data为整形 因为elementype 为int的意思 struct node *next;//指向链表中的下一个结点 }node, *linklist; //构造一个带头结点的空链表 int Initlist_l(linklist &l)//l为单链表的头指针，头指针可以表示一个确定的单链表 { if (l = (node*)malloc(sizeof(node))) return 0; l->next = NULL;//头结点指向下一个为空 return 1; } //创建具有n个结点的线性表 status createlist_l(linklist &l, int n)//不清楚这里要不要带& &是取地址值 { linklist q, p;//定义指针变量q,p int i; q = l;//l代表首地址 for (i = 1; i <= n; i++) { p = (linklist)malloc(sizeof(node));//每次申请新的结点 printf("请依次输入链表："); scanf_s("%d", &p->data);//输入下一个结点的数据 q->next = p;//使得前驱指针指向下一个新的结点 q = p;//p往后移 } q->next = NULL;//知道n个结点输入完毕，指针域指向NULL跳出 return 1; } //打印输入的线性表 void prinlist_l(linklist l) { linklist p;//一般先把首地址赋予一个指针变量 int i = 0; p = l->next;//l代表首地址 取下一个 就是第一个结点的位置 while (p != NULL) { i++;//从第一个开始到最后一个元素 printf("第%d个元素是：", i); printf(" %d \n", p->data);//第一个结点的元素 p = p->next;//找到该结点的元素后转向下一个结点 } } //在第i个位置插入结点e status linklist_l(linklist l, int i, elementype e) { linklist p, s; int j; p = l, j = 0;//l为头指针 while (p&&j < i - 1) { p = p->next;//寻找第i-1个结点，循环之后到达i-1所在位置的数据域 ++j; } if (!p || j > i - 1)//i如果超出链表范围或者j大于等于i 则无效 { printf("输入错误！\n"); return 0; } s = (node*)malloc(sizeof(node));//创造新的结点 s->data = e;//e保存在s结点的数据域中 s->next = p->next;//将新的结点s->next定为 p->next位置的结点 也就是使得s->next 为 i结点，此时i中元素有e p->next = s;//指向下一个结点 //输出新的链表 p = l;//l始终为首地址 头指针 p = p->next; printf("得到新的链表：\n"); while (p != NULL) { printf(" %d ", p->data); p = p->next; } printf("\n"); return 1; } //将第i个位置的结点删除 status listdelete_l(linklist l, int i) { linklist p, q; int j, e; p = l; j = 0; while (p->next&&j < i - 1)//使得p->next结点在i-1位置上 { p = p->next; ++j;//p->next 赋予 p } if (!(p->next) || j > i - 1) { printf("输入错误！\n"); return 0; } q = p->next; //i位置结点为q p->next = q->next;//i+1位置的结点取代i位置的结点 free(q);//释放q p = l->next; printf("你将得到新的链表\n"); while (p != NULL) { e = p->data; printf(" %d ", e); p = p->next; } printf("\n"); return 1; } void main() { linklist l; int a, n, i; elementype e; cout << "构造一个带头结点的空链表" << endl; Initlist_l(l); cout << "创建具有n个结点的线性表" << endl; cin >> n; createlist_l(l,n); cout << "打印输入的线性表" << endl; prinlist_l(l); cout << "在第i个位置插入结点e" << endl; cout << "输入i" << endl; cin >> i; cout << "输入e" << endl; cin >> e; linklist_l(l, i, e); cout << "将第i个位置的结点删除" << endl; cout << "输入i" << endl; cin >> i; listdelete_l(l, i); }

静态链表

用结构数组来描述链表 数组的下标代替指针，指示结点在数组中的位置 o下标作为头结点

线性表做插入与删除时只需修改相应下标就行，但需要预先分配一个较大的存储空间

双向链表

单链表的每个结点只带有一个指针 每个结点含有两个或两个以上的指针域的链表称为多重链表

双向链表 一个结点两个指针域

一个存放它的直接前驱结点的信息 一个存放它的直接后继结点的信息

左指针域和右指针域 数据域在其中间 | 左指针 | 数据域 | 右指针 |

typedef struct { elementype data; struct dnode *llink; struct dnode *rlink; }dnode,*dulinklist;

例：在双向链表中，若p是指向表中任意一结点的指针，则有

p=(p->llink)->rlink=(p->rlink)->llink

即两个结点直接可以互相用指针指向 这样对于插入和删除工作变得简单，但是付出了空间的代价