线性表（Linear List）
基本概念
线性表是由n（n>=0）个类型相同数据元素组成的有限序列。数据元素可由若干个数据对象组成，且一个线性表中的数据元素必须属于同一数据对象。
线性表示n个类型相同数据元素的有限序列，对n>0,除第一个元素无直接前驱，最后一个元素无直接后继外，其余的每个数据元素只有一个直接前驱和直接后继。
线性表的逻辑结构如图：
线性表具有如下特点：
同一性：线性表由同类数据元素组成，每个元素必须属于同一数据类型。
有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。
线性表中相邻数据元素之间存在着序偶关系。
线性表的顺序存储
线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在连续的物理存储单元中，即通过数据元素物理存储的连续性来反映数据元素逻辑上的相邻关系。
采用顺序存储结构存储的线性表通常简称为顺序表。可将顺序表归纳为：关系线性化，结点顺序化。
顺序存储表示
定义
用c语言定义线性表的顺序存储结构：
typedef struct{ char data[MAXSIZE];
int len; //数据长度 }List;那么线性表的存储地址是如何计算的呢？
假设线性表中有n个元素,每个元素占 sizeof(ElemType)个单元,则第一个元素的地址为 LOC(A) ,则第n个元素的地址为： LOC(n) = LOC(A) + (n-1)* sizeof(ElemType) 。
顺序表的存储结构如下：
我们只是定义了顺序表，还没有创建呢！
创建
//初始化顺序表 List* initList(List *L){ int num, i; char ch; //输入顺序表长度
printf("请输入顺序表长度（0<len<100): ");
scanf("%d", &num);
L->len = num;
//输入数据
for(i = 0; i < L->len; i++){
getchar();
printf("请输入第 %d 个数：", i);
scanf("%c", &ch);
L->data[i] = ch;
} return L;
}
基本操作
线性表的基本操作有查找，插入，删除。
查找
查找分为两种：1.可以按序号查找 getAsNum(L,i) :查找线性表L中第i个数据元素。2.按内容查找 getAsContent(L, content) :查找顺序表L中的和Content相等的数据元素
【算法思想】：按内容查找运算可采用顺序查找，即从第一个元素开始，依次将表中元素content相比较，若想等，则查找成功，返回该元素在表中的序号；若都不想等，则查找失败，返回-1
【算法描述】按内容查找算法
//按内容查找int getAsContent(List L, char content){
unsigned int i = 0;
while(i >= 0 || i <= L.len - 1){ //顺序扫描表，找到对应元素，或者扫描完则退出
if(L.data[i] != content){
i++;
}else{
break;
}
} if(i <= L.len - 1){ //找到则输出并返回序号
printf("按内容查找成功，第 %d 个位置元素为 %c \n\n", i, L.data[i]); return i;
}else{ //未找到
printf("查找失败，没有你所找的元素！\n\n"); return ERROR;
}
}
小结：查找时要注意判断表中没有你要查找的元素的情况，此算法时间复杂度为O(n)。
插入
插入操作指在第i个元素之前插入一个新的元素，这时线性表的长度就变成了n+1了。
【算法思想】：用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将原表位置的n，n-1，……，i上的结点依次后移一个位置（此时原表移动对应得位置为n+1，n，……，i+1），空出第i个位置，然后在该位置插入新结点。注意插入的位置为表尾时的情况。
【算法描述】顺序表的插入运算
int insertList(List *L, int i, char content){ int k;
//插入的位置不在表的范围
if(i < 0 || i >= L->len){
printf("插入位置不合法！\n\n"); return ERROR;
}
//考虑表满的情况
if(L->len == MAXSIZE){
printf("表已满！无法插入！\n\n"); return ERROR;
}else if(i >= 0 && i <= L->len - 1){
//插入位置后的元素向后移动
for(k = L->len - 1; k >= i; k--){
L->data[k+1] = L->data[k];
}
L->data[i] = content; //表长度加一
L->len++;
printf("插入成功！\n\n");
print(L); return OK;
}
}
小结：设E为在长度为n的表中插入一元素所需移动元素的平均次数，假设为在第i个元素之前插入元素的概率，并假设在任何位置上插入的概率相等，即 , i = 1, 2, ……, n+1, 则有：
删除
线性表的删除操作指的是将表的第i个（1<=i<=n）个元素删去，使长度为n的线性表变成长度为n-1的线性表
【算法思想】：类似于插入操作，用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，空出第i个位置就要将原表位置的上的结点依次前移一个位置。
【算法描述】顺序表的删除运算
//删除 int deleteList(List *L, int i, char *content){ int k;
//删除位置不合法则推出
if(i < 0 || (i >= L->len)){
printf("删除位置不合法！\n\n"); return ERROR;
}
//删除的表已空
if(L->len == 0){
printf("表已空！\n\n"); return ERROR;
}else{ *content = L->data[i];
//前移
for(k = i; k <= L->len - 2; k++){
L->data[k] = L->data[k+1];
}
//删除成功后表长度减一
L->len--;
printf("删除成功！\n\n");
print(L); return OK;
}
}
小结：与插入算法类似，删除运算也要移动结点。设E为删除一个元素所需移动元素的平均移动次数， 为 删除第i个元素的概率，并假设在任何位置上删除的概率相等，即 ，i=1，2，……，n 。则有：
最后的汇总代码如下：
顺序表
执行结果：
线性表的链式存储
链表：链表使用一组任意的存储单元来存放线性表的结点，这组存储单元可以是连续的，也可以是非连续的，甚至是零散分布在内存的任何位置。
采用链式存储结构的线性表称为线性链表。从链接方式看，链表可分为单链表，循环链表，双链表（也叫循环双链表，双向链表）。从实现角度看可分为动态链表和静态链表。
结点：结点包括两个域：数据域和指针域。数据域存放数据，指针域指向其他结点的地址。两个域的数量视具体情况而定。
单链表和循环单链表有一个指针域，双链表有连个指针域。
单链表
单链表中每个结点的存储地址存放在其前驱结点的指针域中，由于线性表的第一个结点无前驱，通常设一个头指针header指向第一个结点。
定义：
单链表的存储结构如下：
typedef struct Node{ char ch; int len; //表长度
struct Node *next;
}Node, *linkList;
创建
单链表的创建有两种：头插法和尾插法
和 
代码在这里：
//尾插法建立表 linkList createFromTail(linkList L){
Node *s, *r; //r指针始终指向链表尾部
char ch; int flag = 1;
r = L;
printf("尾插法建立表,请输入数据并以'#'结束输入：\n"); while(flag){
printf("输入数据: ");
scanf("%c", &ch);
getchar(); if(ch == '#'){ //若输入 # 则退出
flag = 0;
r->next = NULL;
}else{
s = (linkList)malloc(sizeof(Node));
s->ch = ch;
r->next = s;
r = s;
(L->len)++;
flag = 1;
}
}
print(L); return L;
}
基本操作
其基本操作和顺序表一样：查找，插入，删除。
查找
这里也只讲按值查找
【算法思想】：从单链表的头指针指向的头结点出发，顺链逐个将结点值和给定值作比较。
【算法描述】
//按内容查找linkList getAsContent(linkList L){
Node *p; char ch; int i = 1;
p = L->next;
printf("\n请输入查找内容：");
scanf("%c", &ch);
getchar();
//遍历完表且未找到数据退出循环， 找到数据时退出函数
while(p != NULL){ if(p->ch == ch){
printf("按内容查找成功，第 %d 个位置的数据为 %c\n", i, p->ch); return p;
}
p = p->next;
i++;
}
//未找到数据
if(p == NULL){
printf("按内容查找失败！未在表中找到数据！\n");
}
}
插入
【算法思想】：首先要找到插入位置i的前一个结点，并用指针pre指向它，然后申请新结点s，通过修改pre和s的指针域将新结点插入链表。
【算法描述】
//插入linkList insertList(linkList L){
Node *pre, *s; int k, i; char ch;
pre = L;
k = 0;
printf("\n请输入你要插入的位置和内容(格式: address content)：");
scanf("%d %c", &i, &ch);
getchar();
//插入位置不可能为负
if(i <= 0){
printf("插入失败！插入位置不合法！插入位置不能为负\n"); return NULL;
}
////遍历完表且未找到插入位置(此时i大于表的长度) 或 找到插入位置时退出函数 退出循环
while(pre != NULL && k < i - 1){
pre = pre->next;
k++;
}
if(pre == NULL){
// 未找到插入位置(此时i大于表的长度)
printf("插入失败！插入位置不合法！插入位置超出表的长度\n"); return NULL;
}else{
//找到插入位置并插入数据
s = (linkList)malloc(sizeof(Node));
s->ch = ch;
s->next = pre->next;
pre->next = s;
L->len++;
printf("插入成功！");
print(L); return L;
}
}
删除
【算法思想】：通过计数方式找到删除位置的前一个结点并用pre指针指向它，然后删除结点并释放空间。
【算法描述】
//删除linkList delList(linkList L){
Node *pre, *r; int k = 0, i; char *ch;
pre = L;
printf("请输入删除的数据的位置(格式：address)：");
scanf("%d", &i);
getchar();
//删除的位置必须合法
if(i > L->len || i<= 0){
printf("删除的位置超出了链表的长度!\n"); return;
}
// 找到删除位置退出
while(pre->next != NULL && k < i - 1){
pre = pre->next;
k++;
}
//删除操作
r = pre->next;
pre->next = r->next; free(r);
L->len--;
printf("删除成功！\n");
print(L); return L;
}
这是最后的完整算法：
单链表
运行结果如图：
循环单链表
定义
循环链表是一个首尾相接的链表。将单链表最后一个结点的指针域有NULL改为指向表头结点，就得到了单链形式的循环链表，并成为循环单链表。
对于循环单链表，若经常要在首尾两端进行操作，则可以设一个为指针在表尾（如下图中C）。
c语言定义如下：
typedef struct cNode{ char data; int len; //表长
struct cNode *next;
}Node, *cNode;创建
和前面一样，这里只讲尾插法创建
//尾插法建立表 cNode createFromTail(cNode L){
Node *s, *r; int i = 0, flag = 1; char data;
r = L;
printf("尾插法建立表,请输入数据并以'#'结束输入：\n"); while(flag){
printf("输入数据: ");
scanf("%c", &data);
getchar(); if(data != '#'){
s = (cNode)malloc(sizeof(Node));
s->data = data;
s->next = r->next;
r->next = s;
r = s;
L->len++;
}else{
printf("结束输入...\n");
flag = 0;
}
}
r->next = L;
print(L); return L;
}
基本操作
查找
//按内容查找cNode searchAsContent(cNode L){
Node *p; char data; int i = 1;
p = L->next;
printf("\n请输入查找内容：");
scanf("%c", &data);
getchar();
//遍历完表且未找到数据退出循环， 找到数据时退出函数
while(p != L){ if(p->data == data){
printf("按内容查找成功，第 %d 个位置的数据为 %c\n", i, p->data); return p;
}
p = p->next;
i++;
}
//未找到数据
if(p == L){
printf("按内容查找失败！未在表中找到数据！\n");
}
}
插入
//插入cNode insertCNode(cNode L){
Node *pre, *s;
int k, i; char data;
pre = L->next;
k = 1;
printf("\n请输入你要插入的位置和内容(格式: address content)：");
scanf("%d %c", &i, &data);
getchar();
//插入位置不可能为负
if(i <= 0){
printf("插入失败！插入位置不合法！插入位置不能为负\n"); return NULL;
}
////遍历完表且未找到插入位置(此时i大于表的长度) 或 找到插入位置时退出函数 退出循环
while(pre != L && k < i - 1){
pre = pre->next;
k++;
}
if(pre == L){
// 未找到插入位置(此时i大于表的长度)
printf("插入失败！插入位置不合法！插入位置超出表的长度\n"); return NULL;
}else{
//找到插入位置并插入数据 ，注意:pre指向插入位置的前一个结点
s = (cNode)malloc(sizeof(Node));
s->data = data;
s->next = pre->next;
pre->next = s;
L->len++;
printf("插入成功！");
print(L); return L;
}
}
删除
//删除 cNode delList(cNode L){
Node *pre, *r; int k = 0, i;
pre = L;
printf("请输入删除的数据的位置(格式：address)：");
scanf("%d", &i);
getchar();
//删除的位置必须合法
if(i > L->len || i<= 0){
printf("删除的位置超出了链表的长度!\n"); return;
}
// 找到删除位置退出
while(pre->next != L && k < i - 1){
pre = pre->next;
k++;
}
//删除操作
r = pre->next;
pre->next = r->next; free(r);
L->len--;
printf("删除成功！\n");
print(L); return L;
}
完整代码：
循环单链表
运行结果：
双向链表
定义
双向链表的的指针域在前面说过，它有两个指针域，一个指针域指向本结点的直接前驱，另一个则指向直接后继
定义:
typedef struct DNode{ char data; int len; struct DNode *prior; struct DNode *next;
}DNode, *DList;
创建
//尾插法创建 DList createFromTail(DList L){
DNode *s, *r; int flag = 1; char data;
r = L;
printf("尾插法建立表,请输入数据并以'#'结束输入：\n"); while(flag){
printf("输入数据: ");
scanf("%c", &data);
getchar(); if(data == '#'){ //若输入 # 则退出
flag = 0;
}else{
s = (DList)malloc(sizeof(DNode));
s->data = data;
s->prior = r;
s->next = L;
r->next = s;
r = s;
L->prior = r;
(L->len)++;
flag = 1;
}
http://www.cnblogs.com/libra-yong/p/6374696.html延伸阅读
- 集合结合数据结构来看看(二) 2017-07-26 16:38:18.65
- 数据结构3——浅谈zkw线段树 2017-07-25 17:12:04.977
- 数据结构与算法 2017-07-21 16:33:51.887
- STL的使用和背后数据结构 2017-07-18 13:51:33.87
- 数据结构从零开始之线性表 2017-07-13 16:36:56.85
- Cesium原理篇：3D Tiles（2）数据结构 2017-06-20 15:15:52.25
- 串的数据结构表——顺序串与链式串 2017-06-17 10:34:17.827
- 【数据结构】数据结构的概述 2017-05-27 16:20:23.43
- JS高级-数据结构的封装 2017-05-23 16:43:26.347
- 【开源.NET】 轻量级内容管理框架Grissom.CMS（第二篇前后端交互数据结构分析） 2017-05-17 16:32:03.813
集合结合数据结构来看看(二)