线性表
定义
具有
相同
数据类型的n个数据元素的
有限
序列（有次序）
几个概念：
- ai是线性表中“第i个”元素线性表中的位序
- a1是表头元素，an是表尾元素
- 除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。
基本运算
顺序存储（顺序表）
定义：用
顺序存储
的方式实现的线性表。
顺序存储：逻辑上相邻的元素存储在物理位置上也相邻的存储单元中。
如何计算一个数据元素的大小？
答：C语言中的sizeof(** **)函数
静态分配
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef int datatype;
typedef struct{
datatype a[MAXSIZE];
int size;
}sqlist;
//初始化
void InitList(sqlist *slt)
{
slt->size=0;
}
//在顺序表后进行插入
void append(sqlist *slt,datatype x)
{
if(slt->size==MAXSIZE)
{
printf("顺序表满了！");
exit(1);
}
slt->a[slt->size]=x;
slt->size=slt->size+1;
}
//打印顺序表各个结点的值
void display(sqlist slt)
{
int i;
if(!slt.size) printf("\n顺序表是空的~");
else
for(i=0;i<slt.size;i++)
printf("%5d",slt.a[i]);
printf("\n");
}
//判断顺序表是否为空
int empty(sqlist slt)
{
return (slt.size==0?1:0);
}
//查找顺序表中值为x的节点位置
int find(sqlist slt,datatype x)
{
int i=0;
while(i<slt.size&&slt.a[i]!=x) i++;
return (i<slt.size?i:-1);
}
//取得顺序表中第i个结点的值
datatype get(sqlist slt,int i)
{
if(i<0|| i>=slt.size)
printf("指定位置结点不存在");
else
return slt.a[i];
}
//插入相指定数字在相应位置的
void insert(sqlist *slt,datatype x,int position)
{
int i;
if(slt->size==MAXSIZE)
{
printf("\n顺序表是满的，没法插入！");
exit(1);
}
if(position<0 || position >slt->size)
{
printf("\n指定插入位置不存在！");
exit(1);
}
for(i=slt->size;i>position;i--)
{
slt->a[i]=slt->a[i-1];
}
slt->a[position]=x;
slt->size++;
}
//删除指定位置的元素
void dele(sqlist *slt,int position)
{
int i;
if(slt->size==0)
{
printf("顺序表是空的！");
exit(1);
}
if(position<0 || position >slt->size)
{
printf("\n指定插入位置不存在！");
exit(1);
}
for(i=position;i<slt->size-1;i++)
{
slt->a[i]=slt->a[i+1];
}
slt->size--;
}
int main()
{
sqlist slt;
int num;
// 初始化并打印
InitList(&slt);
// 输入顺序表内容
printf("请输入顺序表的内容，以0结尾：");
scanf(" %d",&num);
while(slt.size<MAXSIZE && num!=0)
{
append(&slt,num);
scanf(" %d",&num);
}
display(slt);
// 在第一个位置插入5（从0开始）
insert(&slt,5,1);
display(slt);
// 删除第一个位置
dele(&slt,1);
display(slt);
return 0;
}
如果数组存满了怎么办。因为存储空间是静态的所以顺序表的表长在刚开始确定后就无法更改。
如果一开始声明一个很大的内存空间，则容易产生大量的浪费。
- 关于insert函数的时间复杂度
- 关于dele函数的时间复杂度
- 关于get函数的时间复杂度
O(1)
- 关于find函数的时间复杂度
注意：
“ == ”不能用于比较两个结构型变量
，需要依次对比各个分量来判断两个结构体是否相等或者可以另写函数判断。
动态分配
由于需要将数据复制到新区域，但是时间开销大。
#include <stdio.h>
#include <stdlib.h>
#define InitSize 10
typedef struct{
int *data;
int MAXSIZE;
int length
} sqlist;
void InitList(sqlist *slt)
{
slt->data = (int *)malloc(InitSize*sizeof(int));
slt->length = 0;
slt->MAXSIZE = InitSize;
}
void IncreaseSize(sqlist *slt,int len)
{
int *p = slt->data;
int i;
slt->data = (int *)malloc((slt->MAXSIZE+len)*sizeof(int));
for(i=0;i<slt->length;i++)
{
slt->data[i] = p[i];
}
slt->MAXSIZE = slt->MAXSIZE+len;
free(p);
}
int main() {
sqlist slt;
InitList(&slt);
printf("\nslt.maxsize = %d",slt.MAXSIZE);
IncreaseSize(&slt,5);
printf("\nslt.maxsize = %d",slt.MAXSIZE);
return 0;
}
特点
- 随机访问。即可以在O(1)时间内找到第i个元素
- 存储密度高，每个节点只存储数据元素
- 拓展容量不方便
- 插入删除操作不方便，需要移动大量元素
单链表
用
链式存储
（存储结构）实现了线性结构（逻辑结构）
各结点之间的先后关系用一个指针表示
我们默认：
不带头结点的插入函数，第一个数据从索引1开始。
带头结点的头节点索引位置为0，第一个数据索引从1开始。
不带头节点
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct link_node{
datatype info;
struct link_node *next;
}node;
//建立一个不带头结点空链表
node *init()
{
return NULL;
}
//打印单链表中各个结点的值
void display(node *head)
{
node *p;
p=head;
if(!p) printf("\n单链表是空的！");
else
{
printf("\n单链表各个结点是：");
while(p)
{
printf("%5d",p->info);
p=p->next;
}
}
}
//在单链表中查找第i个结点的存放地址
node *find(node *head,int i)
{
int j=1;
node *p=head;
if(i<1) return NULL; //若第i个结点小于1说明比第一个结点的位置还靠前 return null
while(p && j!=i) //找到当前链表已存放数据长度内，第i个结点的存放地址。若刚好为已存放数据中最后一个的下一个数据位为第i个结点，则p为空后return null
{
p=p->next;
j++;
}
return p;
}
//在第i个位置插入x
//宗旨就是找到从1开始的第i-1个结点，然后插入第i-1个结点之后
node *insert(node *head,datatype x,int i)
{
node *q=head;
q=find(head,i-1);//找到第i-1个结点的位置
if(!q && i<1) printf("找不到第%d个位置",i); //若i小于1说明根本插入位置不对
else
{
node *p = (node *)malloc(sizeof(node));
p->info = x;
if(i==1) //如果i为1说明存放的为第一个结点，把head指针进行重定向一下即可
{
p->next = head;
head = p;
}
else
{
if(q) //找到i-1结点位置，将x插入第i-1结点之后
{
p->next = q->next;
q->next = p;
}
else //i-1结点根本找不到，说明i超出了链表已存数据的长度范围
{
return head;
}
}
}
return head;
}
node *dele(node *head,datatype x)
{
node *pre=NULL,*p;
if(!head)
{
printf("单链表是空的");
return head;
}
// 不带头结点
p=head;
while(p&&p->info!=x)
{
pre=p;p=p->next;
}
if(p)
{
if(!pre) head=head->next; //删除第一个结点
else pre->next = p->next;
free(p);
}
return head;
}
int main(int argc, char *argv[]) {
node *lklist;
lklist = init();
display(lklist);
lklist = insert(lklist,1,1);
lklist = insert(lklist,2,2);
lklist = insert(lklist,3,3);
lklist = insert(lklist,4,4);
lklist = insert(lklist,5,5);
lklist = insert(lklist,9,9);
lklist = insert(lklist,7,3);
/*lklist = linkinsert(lklist,1,1);
lklist = linkinsert(lklist,2,2);
lklist = linkinsert(lklist,3,3);
lklist = linkinsert(lklist,4,4);
lklist = linkinsert(lklist,5,5);
lklist = linkinsert(lklist,9,9);
lklist = linkinsert(lklist,7,3);*/
display(lklist);
lklist = dele(lklist,10);
lklist = dele(lklist,2);
display(lklist);
return 0;
}
将find和insert函数合并可以写成一个listinsert函数
node *linkinsert(node *head,datatype x,int i)
{
if(i<=0) return head;
if(i==1)
{
node *s=(node *)malloc(sizeof(node));
s->info = x;
s->next = head;
head=s;
return head;
}
node *p=head;
int j=1;
while(p!=NULL && j<i-1)//宗旨就是找到从1开始的第i-1个结点，然后插入第i-1个结点之后
{
p=p->next;
j++;
}
if(p==NULL) return head;
node *s=(node *)malloc(sizeof(node));
s->info = x;
s->next = p->next;
p->next=s;
return head;
}
这里一般插入要考虑四种情况：
- 当i小于1，说明不满足插入位置的情况
- 当i为1，说明插入的数据为head指向的第一个位置
- 当第i-1未超过链表整体长度且能够找到第i个位置的前驱节i-1的情况
- 当i-1超过了链表的整体长度以至于p指向null表示插入位置不合法
带头结点
头节点可以看成是第0个结点
#include <stdio.h>
#include <stdlib.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
typedef int datatype;
typedef struct link_node{
datatype info;
struct link_node *next;
}node;
//建立一个带头结点空链表
node *init()
{
node *head = (node *)malloc(sizeof(node));
head->info = 0;
head->next = NULL;
return head;
}
//打印单链表中各个结点的值
void display(node *head)
{
node *p;
p=head->next;
if(!p) printf("\n单链表是空的！");
else
{
printf("\n单链表各个结点是：");
while(p)
{
printf("%5d",p->info);
p=p->next;
}
}
}
//在单链表中查找第i个结点的存放地址
node *find(node *head,int i)
{
int j=0; //注意不带头结点的j从1开始，j的1 代表head指向的第一个数据
//而带头结点j从0开始，代表head的头节点。
node *p=head;
// if(i<1) return NULL; 不带头节点
if(i<0) return NULL; //带头节点的单链表
else if(i==0) return p;//i=0返回的是头节点
while(p && i!=j)
{
p=p->next;
j++;
}
return p;
}
//在第i个位置插入x
node *insert(node *head,datatype x,int i)
{
node *q;
q=find(head,i-1);
if(!q) printf("找不到第%d个位置",i);
else
{
node *p = (node *)malloc(sizeof(node));
p->info = x;
p->next = q->next;
q->next = p;
}
return head;
}
node *dele(node *head,datatype x)
{
node *pre=head,*p;
p=head->next;
while(p&&p->info!=x)
{
pre=p;p=p->next;
}
if(p)
{
pre->next = p->next;//带头结点不用分类讨论
free(p);
}
return head;
}
int main(int argc, char *argv[]) {
node *lklist;
lklist = init();
display(lklist);
lklist = insert(lklist,0,0);
lklist = insert(lklist,1,1);
lklist = insert(lklist,2,2);
lklist = insert(lklist,3,3);
lklist = insert(lklist,4,4);
lklist = insert(lklist,5,5);
lklist = insert(lklist,9,9);
lklist = insert(lklist,7,3);
/*lklist = linkinsert(lklist,1,1);
lklist = linkinsert(lklist,2,2);
lklist = linkinsert(lklist,3,3);
lklist = linkinsert(lklist,4,4);
lklist = linkinsert(lklist,5,5);
lklist = linkinsert(lklist,9,9);
lklist = linkinsert(lklist,7,3);*/
display(lklist);
lklist = dele(lklist,10);
lklist = dele(lklist,2);
display(lklist);
return 0;
}
将find和insert函数合并可以写成一个listinsert函数
node *linkinsert(node *head,datatype x,int i)
{
if(i<1)
{
printf("插入位置不合法。");
return head;
}
node *p;
int j=0; //不带头节点的j初始为1
p = head;
while(p!=NULL && j<i-1) //特找到第i-1的结点位置p
{
p=p->next;j++;
//此时的p可能为head索引为0的头结点，而不带头结点的p只可能是head指向的索引为1的第一个数据节点
}
if(p==NULL)//i-1超出链表已存数据长度范围
{
printf("插入位置不合法。");
return head;
}
node *s = (node *)malloc(sizeof(node));
s->info = x;
s->next = p->next;
p->next = s;
return head;
}
这里一般插入要考虑三种情况：
- 当i小于1，说明不满足插入位置的情况
- 当第i-1未超过链表整体长度且能够找到第i个位置的前驱节点p的情况
- 当i-1超过了链表的整体长度以至于p指向null表示插入位置不合法。
指定节点的前插操作
当我们通过遍历找到指定节点的pre结点时再插入所需要的时间复杂度是O(n)
但是如果我们把指定节点后插一个结点并把二者的info互换的话，那么时间复杂度就是O(1)
指定结点p的删除
当我们通过遍历找到指定结点的pre结点再删除所需要的时间复杂度是O(n)
但是如果我们把指定节点p后一个结点q的内容移到前一个结点p上，并使得p->next连接上q->next再释放q的话，那么时间复杂度就是O(1)。
但是如果q为null则会有bug
封装
当我们找到i-1的位置结点的p可能为空也可以不为空，此时封装除一个InsertNextNode对p的分类讨论则体现了代码的健壮性。
特点
优点：离散的小空间分配方便，改变容量方便
缺点：不可随机存取，存储密度低
查找特性
单链表不具有随机访问的特性，只能依次扫描。按位查找，按值查找，求单链表长度的时间复杂度都是O(n)。
从键盘读入数据存入单链表
尾插
如果是键盘输入长度，然后通过while循环去控制length长度每次输入数去listinsert插入。那么时间复杂度是O(n^2)
步骤：
-
初始化单链表
-
设置单链表长度length并记录链表长度
-
while循环{
每次取一个数据元素e，linkinsert（head,x,length+1)插入到尾部,length++
}
但是如果用以下方式，通过r去记录每次单链表尾部结点，那么时间复杂度就是O(n)
//带头结点
int main(int argc, char *argv[]) {
node *lklist,*r;
int num;
lklist = init();//初始化带头节点空表
r = lklist;
display(lklist);
printf("请输入单链表的内容用空格间隔，输入-1结束：");
scanf("%d",&num);
while(num!=-1)
{
node *s = (node *)malloc(sizeof(node));
s->info = num;
r->next = s;
r = s;
scanf("%d",&num);
}
r->next = NULL;
display(lklist);
return 0;
}
//不带头结点
int main(int argc, char *argv[]) {
node *lklist,*r;
int num;
lklist = init();//初始化不带头节点空表
r = lklist;
display(lklist);
printf("请输入单链表的内容用空格间隔，输入-1结束：");
scanf("%d",&num);
while(num!=-1)
{
node *s = (node *)malloc(sizeof(node));
s->info = num;
if(r)
{
r->next = s;
}
else
{
lklist = s;
}
r=s;
scanf("%d",&num);
}
r->next = NULL;
display(lklist);
return 0;
}
头插
如果需要链表逆置可以考虑头插法
//带头结点
int main(int argc, char *argv[]) {
node *lklist;
int num;
lklist = init();
display(lklist);
printf("请输入单链表的内容用空格间隔，输入-1结束：");
scanf("%d",&num);
while(num!=-1)
{
node *s = (node *)malloc(sizeof(node));
s->info = num;
s->next = lklist->next;
lklist->next = s;
scanf("%d",&num);
}
display(lklist);
return 0;
}
//不带头结点
int main(int argc, char *argv[]) {
node *lklist,*r;
int num;
lklist = init();//初始化不带头节点空表
display(lklist);
printf("请输入单链表的内容用空格间隔，输入-1结束：");
scanf("%d",&num);
while(num!=-1)
{
node *s = (node *)malloc(sizeof(node));
s->info = num;
if(r)
{
s->next = lklist;
lklist = s;
}
else
{
s->next=NULL;
lklist = s;
}
scanf("%d",&num);
}
display(lklist);
return 0;
}
双链表
插入结点
//在p之后插入s
bool insertnextnode(node *p,node *s)
{
if(p==NULL || s==NULL) return false;
s->next = p->next;
if(p->next!=NULL) p->next->prior = s; //注意最后一个结点next为空的情况
s->prior = p;
p->next = s;
return true;
}
删除结点
//删除p的后继结点
bool deletnextnode(node *p)
{
if(p==NULL) return false;
node *q = p->next;
if(q==NULL) return false;//p没有后继
p->next=q->next;
if(q->next!=NULL) q->next->prior=p;
free(q);
return true;
}
清空双链表
void destroylist(node *p)
{
while(p->next!=NULL) deletnextnode(p);
free(p);
}
遍历
通过p->next或p->prior实现后向遍历，前向遍历。
查找特性
不可随机存储，按位查找，按值查找操作都只能用遍历的方式实现，时间复杂度为O(n)
循环单链表双链表
循环单链表
初始化时要将头节点的next指向头节点
判断循环单链表是否为空：L->next==L
判断p是否为循环单链表表尾结点：p->next==L
优势
：单链表从一个结点出发只能找到后续各个结点。循环单链表从一个结点出发可以i找到其他任何一个结点。
从头节点找到尾部，时间复杂度时O(n)，从尾部找头部时O(1)
应用
：对链表操作都在头部尾部时,可以让链表的指针l指向表尾，但同时也要及时修改l的指向。
循环双链表
初始化时要将头节点的next指向头节点，prior指向头节点
判断循环单链表是否为空：L->next==L
判断p是否为循环单链表表尾结点：p->next==L
优势
：在p结点插入s结点时，双链表在表尾会有为空的分类讨论。而循环双链表不用分类讨论。删除操作同理。
静态链表
单链表各个结点在内存中星罗棋布。
静态链表分配一整片连续的内存空间，各个结点集中安置。其实是用数组的方式实现的链表、
优点：增删操作不需要大量移动元素
缺点：不能随机存取，只能从头节点开始依次往后查找，容量固定不可变。
应用：不支持指针的低级语言，数据元素数量固定不变的场景