线性表
线性表概念
线性表定义:具有相同特性数据元素的有限序列。
线性表的逻辑结构:线性结构。只有一个表头，只有一个表尾。表头元素没有前驱，表尾元素没有后继。其余都有一个直接前驱与后继。
线性表的物理结构:顺序存储结构和链式存储结构
- 顺序表:将元素按照其逻辑顺序，依次存储在指定位置开始的一片连续的存储空间中。
- 链表：在内存中可以不连续。每个结点中不止包括所存元素的信息，还有元素之间逻辑关系的信息。如单链表中后继结点。
两种储存结构的比较：
顺序表:
- 随机访问性 (知道0点位置。就可以在o（1）时间找到想要的元素)
- 占用连续的存储空间
- 静态分配:一旦分配好，操作过程中不会发生改变
- 做操作需要移动多个元素
链表:
1.不支持随机访问（必须遍历）
2.结存的存储空间利用率较顺序表较低（多了结点逻辑信息）
3.动态分配
4.做操作无须移动元素
链表的五种形式
1.单链表
此处输入图片的描述
带头结点 ：head->始终不为空，head->next为NULL时为空链表
不带头结点:head为NUll时是空链表
带头结点的单链表的优点:
在链表第一个位置上进行的操作（插入、删除）和其它位置上的操作一致,无须进行特殊处理;
无论链表是否为空，head一定不为空，这使得空表和非空表的处理一致。
2.双链表
此处输入图片的描述
比单链表在结点上多了个前驱结点。使得可以从后向前访问。
3.循环单链表
此处输入图片的描述
最后一个指针域指向开始结点。
可以做到从任何一个结点出发，访问任何一个结点。
空链表:head = head->next
4.循环双链表
此处输入图片的描述
空链表：head = head->next或head = head->prior
5.静态链表
此处输入图片的描述
顺序表
顺序表基本操作:
初始化
插入
删除
查找
打印
求指定位置元素
代码:
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
int data[100];
int length;
}sqList;//顺序表的结构体定义
/**顺序表操作**/
//查找
int findElem(sqList L,int x)//查找
{
for(int i = 0;i<L.length;++i)
{
if(x == L.data[i])
return i;
}
return -1;
}
//插入
int insertElem(sqList *L,int p,int x)
{
int i;
if(p<0||p>L->length||L->length == 100)//顺序表超过最大允许值
return 0;
for(i = L->length -1;i>=p;--i)
L->data[i+1]=L->data[i];
L->data[p] = x;
++(L->length);
return 1;
}
//删除
int deleteElem(sqList *L,int p ,int *x)//将被删除的元素赋值给x，可以不要这个步骤
{
int i;
if(p<0||p>L->length-1)
return 0;
*x = L->data[p];
for(i = p;i<L->length-1;++i)
L->data[i]=L->data[i+1];
--(L->length);
return 1;
}
//初始化
void initList(sqList *L)
{
L->length = 0;
}
//求指定位置元素
int getElem(sqList L,int p,int *x)
{
if(p<0||p>L.length-1)
return 0;
*x =L.data[p];
return 1;
}
//打印
void printList(sqList L)
{
for(int i =0;i<L.length;++i)
printf("%d ",L.data[i]);
}
int main()
{
sqList A;
int x=0;
initList(&A);
insertElem(&A,0,1);
insertElem(&A,1,2);
insertElem(&A,1,3);
printf("before delete:\n",x);
printList(A);
deleteElem(&A,1,&x);
printf("\n after delete:\n",x);
printList(A);
printf("删除的值是%d\n",x);
getElem(A,1,&x);
printf("取的值是%d\n",x);
printf("元素位置是%d\n",findElem(A,1));
return 0;
}
/**
输出如下
before delete:
1 3 2
after delete:
1 2 删除的值是3
取的值是2
元素位置是0
**/
单链表
单链表基本操作:
创建链表
插入链表（头、尾插法）
删除链表
打印链表
查找链表
代码实现:
//------------单链表-------------------
//单链表结点定义
typedef struct lNode
{
int data;
struct lNode *next;//在此语句时lNode别名还未生效,所以需要用struct lNode来声明结构体变量
}lNode;
//创建表头
void createListR(lNode **c)
{
(*c) =(lNode*)malloc(sizeof(lNode));
(*c)->next=NULL;
}
//尾插入
lNode *r = NULL;//全局变量尾指针
void insertLnodeR(lNode **c,int data)
{
lNode *s;
if(r==NULL)
r = (*c);
s = (lNode*)malloc(sizeof(lNode));
s->data = data;
r->next=s;
r=r->next;
r->next=NULL;
}
//打印链表
void printListLnode(lNode *headNode)
{
lNode* pMove = headNode->next;
printf("数据如下:\n");
while(pMove)
{
printf("%d\n",pMove->data);
pMove = pMove->next;
}
}
//删除链表
void deleteLNode(lNode **c,int x)
{
lNode *p,*pf;
p = (*c)->next;
pf =(*c);//指向头指针
if(p == NULL)
printf("无法删除链表为空");
while(p->data != x)//如果不为x，使指向前驱结点的pf和该节点p指针向后移动
{
pf = p;
p = p->next;
if(p == NULL)
{
printf("没有找到相关信息\n");
return;
}
}
pf->next = p->next;//将p结点从链表中移除
free(p);//释放p结点空间
int main()
{
lNode *c;
createListR(&c);//以地址的地址为参数，需要取指针的地址(&c)，而不是指针(c)
insertLnodeR(&c,2);
insertLnodeR(&c,3);
printListLnode(c);
deleteLNode(&c,3);
printListLnode(c);
return 0;
}
}
