目录
1.线性表的顺序表示
1.1顺序表的基本概念
1.2顺序表的基本操作
1.2.1插入
1.2.2删除
1.2.3查找
2.线性表的链式表示
2.1单链表
单链表的基本概念
2.1.1基本操作
2.1.1.1单链表的建立
2.1.1.2插入
2.1.1.3删除
2.1.1.4查找
2.2双链表
2.2.1基本操作
2.2.1.1插入
2.2.1.2删除
2.2.1.3遍历
2.3循环链表
2.3.1循环单链表
2.3.2循环双链表
2.3.2.1循环双链表的插入
2.3.2.2循环双链表的删除
3.静态链表
4.顺序表和链表的比较
1.线性表的顺序表示
1.1顺序表的基本概念
存储结构：逻辑上相邻的数据元素物理上也相邻。
实现方式分为：静态分配和动态分配
静态分配：使用静态数组实现，大小一旦确定无法改变。
动态分配：使用动态数组实现，顺序表存满时可以用malloc动态扩展顺序表的最大容量，需要将数据元素复制到新的存储区域，并用free函数释放原区域。
1.2顺序表的基本操作
1.2.1插入
最好时间复杂度：O(1)
最坏时间复杂度：O(n)
平均时间复杂度：O(n)
//插入
bool ListInsert(SqList &L,int i,int e)
{if (i < 1 || i > L.length + 1) //判断i是否合法return false;if (L.length >= MaxSize) //判断是否存满return false;for (int j = L.length;j >= i;j--)//插入结点的位置之后的元素依次后移L.data[j] = L.data[j - 1];L.data[i - 1] = e; //插入eL.length++; //顺序表长度加一return true;
}1.2.2删除
最好时间复杂度：O(1)
最坏时间复杂度：O(n)
平均时间复杂度：O(n)
//删除
bool ListDelete(SqList& L, int i, int e)
{if (i < 1 || i > L.length + 1)//判断i是否合法return false;e = L.data[i - 1]; //将删除结点位置的元素值赋给efor (int j = i;j < L.length;j++)//删除结点后面的元素依次前移L.data[j - i] = L.data[j];L.length--; //顺序表长度减一return true;
}1.2.3查找
查找方式有按位查找和按值查找。
按位查找
//按位查找
int GetElem(SqList L, int i)
{return L.data[i - 1];
}按值查找
最好时间复杂度：O(1)
最坏时间复杂度：O(n)
平均时间复杂度：O(n)
//按值查找
int LocateElem(SqList L.int e)
{for (int i = 0;i<L>length;i++)if (L.data[i] == e)return i + 1;return 0;
}注意：C语言中，结构体的比较不能直接用“==”
2.线性表的链式表示
2.1单链表
单链表的基本概念
定义：线性表的链式存储。
两种实现方式：带头结点和不带头结点。
带头结点的空表判断：L->next==NULL
不带头结点的空表判断：L==NULL
头结点和头指针的区分：不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点时带头结点的链表中的第一个结点，结点内通常不存储信息。
2.1.1基本操作
2.1.1.1单链表的建立
头插法
应用：链表的逆置（带头结点的单链表的就地逆置：http://t.csdn.cn/J6bph）
// 头插法建立单链表
LinkList List_HeadInsert(LinkList &L)
{LNode* s;int x;L = (LinkList)malloc(sizeof(LNode));//创建头结点L->next = NULL; //初始为空链表scanf("%d", &x); //输入结点的值while (x != 9999) //循环结束条件，可以自己设置为其他值{s = (LNode*)malloc(sizeof(LNode)); //创建新的结点s->data = x;s->next = L->next; L->next = s; //将新结点插入表中，L为头指针scanf("%d", &x);}return L;
}尾插法
//尾插法
LinkList List_TailInsert(LinkList& L)
{int x;L = (LinkList)malloc(sizeof(LNode));//创建头结点LNode* s, * r = L; //r为表尾指针scanf("%d", &x);while (x != 9999){s = (LNode*)malloc(sizeof(LNode)); //创建新的结点s->data = x;r->next = s; r = s; //r指向新的表尾结点scanf("%d", &x);}r->next = NULL;return L;
}2.1.1.2插入
后插
//插入（后插）
s->next = p->next;
p->next = s;前插
//插入（前插）
s->next = p->next;
p->next = s;
temp = p->data; //交换数据域（偷天换日）
p->data = s->data;
s->data = temp;2.1.1.3删除
按位序删除
p = GetElem(L, i - 1); //查找删除位置的前驱节点
q = p->next; //令q指向被删除结点
p->next = q->next; //将*q结点从链中断开
free(q); //释放结点的存储空间
指定结点删除
如果指定结点是最后一个结点时，需要特殊处理
q = p->next; //令q指向*p的后继结点
p->data = p->next->data; //用后继结点的数据域覆盖
p->next = q->next; //将*q结点从链中断开
free(q); //释放结点的存储空间2.1.1.4查找
按位查找，按值查找，求单链表的长度
2.2双链表
2.2.1基本操作
2.2.1.1插入
1.s->next = p->next;
2.if(p->next!=NULL)p->next->prior = s;
3.s->next = p;
4.p->next = s;上述代码的语句顺序不是唯一，但是1和2必须在4之前，否则会出现断链。
2.2.1.2删除
//删除双链表结点*p的后继结点*q
bool DeleteNextNode(DNode* p)
{if (p == NULL)return false;DNode* q = p->next;//找到p的后继结点qif (q == NULL) //p没有后继return false;p->next = q->next;if(q->next!=NULL) //q不是最后一个结点q->next->prior = p;free(q);return true;
}2.2.1.3遍历
后向遍历
//后向遍历
while (p != NULL)
{p = p->next;
}前向遍历
//前向遍历
while (p != NULL)
{p = p->prior;
}
//前向遍历（跳过头结点）
while (p->prior != NULL)
{p = p->prior;
}2.3循环链表
2.3.1循环单链表
表尾结点的next指针指向头结点
2.3.2循环双链表
表尾结点的next指针指向头结点 ；
表头结点的prior指针指向表尾结点
2.3.2.1循环双链表的插入
//循环双链表的插入
/ bool InsertNextDNode(DNode * p, DNode * s)
{s->next = p->next;p->next->prior = s;s->prior = p;p->next = s;
}2.3.2.2循环双链表的删除
//循环双链表的删除
p->next = q->next;
q->next->prior = p;
free(q);3.静态链表
分配一整片的连续空间，容量固定不变，结束标志：next == -1
优点：增，删操作不需要大量移动元素。
缺点：不能随机存取，只能从头结点开始依次往后查找。
