线性表和链表

说来惭愧，不是计算机专业出身，发现本科没有数据结构，研究生阶段忙着做一些其他的东西，最基础的课程反而没有理解，现在找工作很多笔试需要数据结构，静下心来好好学习一下数据结构。希望别的同学以后搞嵌入式的时候有时间学习一下数据结构和算法，这对你的编程很有好处。

 

常见的时间复杂度大小排列：

O(1)

 

线性表定义：

#define MAXSIZE 20
typedef int ElemType;
typedef struct
{
ElemType data[MAXSIZE]; /*数组存储数据元素，最大为MAXSIZE*/
int length;}SqList;

获取元素操作：

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
Status GetElem(SqList L,int i,ElemType *e)
{
if(L.length==0 || i<1 || i>L-length)
return ERROR;
*e=L.data[i-1];
return OK;
}

插入元素：

Status ListInsert(SqList *L,int i,ElemType e)
{
int k;
if(L->length==MAXSIZE)
return ERROR;
if(i<1 || i>L-length+1)
return ERROR;
if(i<=L->length)
{
for(k=L->length-1;k>i=i-1;k--)
L->data[k+1]=L->data[k];/*将插入位置后数据元素向后移动一位*/
}
L->data[i-1]=e;
L->length++;
return OK;
}

删除元素：

Status ListDelete（SqList *L,int i,ElemType *e）{
int k;
if(L->length==0) //线性表为空
return ERROR;
if(i<1 || i>L->length)
return ERROR;
*e=L->data[i-1];
if(i<L->length){
for(k=i;k<L->length;k++)
L->data[k-1]=L->data[k];
}
L->length--；
return OK;
}

线性表平均时间复杂度为O(n)，在读入或则存储时复杂度为O(1)，在插入或者删除时时间复杂度为O(n)

单链表定义：

typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *LinkList;

结点由存放数据元素的数据域和存放结点的指针域组成，假设p是指向线性表第i个元素的指针，p->data表示一个数据元素，p->next表示第i+1个元素的指针。

获得链表元素：

 

Status GetElem(LinkList L,int i,ElemType *e)
{
int j;
LinkList p;
p=L->next;
j=1;
while(p && j<i)
{
p=p->next;
++j;
}
if(!p || j>i)
return ERROR;
*e=p->data;
return OK;
}

单链表插入：

1、声明一个结点p指向链表头结点，促使花j从1开始

2、当j

3、若链表末尾p为空，则说明第i个元素不存在

4、否则查找成功，在系统中生成一个空结点s；

5、将数据元素e赋值给s->data；

6、单链表插入标准语句s->next=p->next;p->next=s(不能反过来，反过来后将p->next给覆盖成s的地址，那么s->next=p->next其实就是s->next=s)

7返回成功

Status ListInsert(LinkList *L,int i,ElemType e)
{
int j;
LinkList p,s;
p=*L;
j=1;
while(p &&j<i)
{
p=p->next;
++j;
}
if(!p || j>i)
return ERROR;
s=(LinkList)malloc(sizeof(Node));//生成新节点
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}

单链表删除步骤：

1、声明一个结点p指向链表第一个结点，初始化j从1开始

2、当j

3、若到链表末尾p为空，则说明第i个元素不存在

4、否则查找成功，将欲删除的结点p->next赋值给q；

5、单链表的删除标准语句：p->next=q->next

6、将q结点中的数据赋值给e作为返回

7、释放q结点

8、返回成功

Status ListDelete(LinkList *L,int i,ElemType *e)
{
int j;
LinkList p,q;
p=*L;
j=1;
while(p->next && j<i)
{
p=p->next;
++j;
}
if(!(p->next) || j>i)
return ERROR;
q=p->next;
p->next=q->next;
*e=q->data;
free(q);
return OK;
}

单链表的整表创建算法思路：

1、声明一个结点p和计数变量i

2、初始化一空链表L

3、让L的头结点的指针指向NULL，即建立一个带头结点的单链表。

4、循环：生成一新结点赋值给p；随机生成一数字赋值给p的数据域p->data；将p插入到头结点与前结点之间。

/*随机产生n个元素的值，建立带表头结点的单链表线性表L（头插法）*/
void CreateListHead(LinkList *L,int n){
LinkList p;
int i;
srand(time(0));
*L=(LinkList)malloc(sizeof(Node));//建立一个带头结点的单链表
(*L)->next=NULL;
for(i=0;i<n;i++)
{
p=(LinkList)malloc(sizeof(Node));
p->data=rand()%100+1;
p->next=(*L)->next;
(*L)->next=p;
}
}

插队的办法就是让新结点始终在第一的位置，称为头插法。

每次把新结点都在终端结点的后面称为尾插法。

/*随机产生n个元素的值，建立带表头结点的单链表现行表L（尾插法）*/
void CreateListTail(LinkList *L,int n)
{
LinkList p,r;
int i;
srand(time(0));
*L=(LinkList)malloc(sizeof(Node));
r=*L;//r指向尾部的结点
for(i=0;i<n;i++)
{
p=(Node *)malloc(sizeof(Node));
p->data=rand()%100+1;
r->next=p;//将表尾端结点的的指针指向新结点
r=p;//将当前的新结点定义为尾端结点
}
r->next=NULL;//表示当前链表结束
}

单链表的整表删除：

1、声明一个结点p和q

2、将第一个结点赋值pxunhuan：释放p；将q赋值给p

Status ClearList(LinkList *L)
{
LinkList p,q;
p=(*L)->next;//p指向第一个结点
while(p)
{
q=p->next;
free(p);
p=q;
}
(*L)->next=NULL;//头结点指针域为空
return OK;
}

将单链表中终端结点的指针端由空指针改为指向头结点，就是整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表

循环链表和单链表主要差异在于判断p->next是否为空，单链表p->next为空结束，循环链表p->next头结点结束。

双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在每个双向链表中的结点独有两个指针域，一个指向直接后继，一个指向直接前驱。

typedef struct DulNode
{
ElemType data;
struct DulNode *prior;//直接前驱指针
struct DulNode *next;//直接后继指针
}DulNode,*DulLinkList;

假设元素e的结点是s，要显示将结点s插入到结点p和p->next之间需要执行：

s->prior=p；//把p赋值给s的前驱

s->next=p->next;//把p->next赋值给s的后继

p->next-prior=s;//把s赋值给p->next的前驱

p->next=s;//把s赋值给p的后继

 

假设删除结点p：

p->prior->next=p->next；//把p->net赋值给p->prior的后继

p->next->prior=p->prior；//把p->prior赋值给p->next的前驱

free（p）；

 

阅读(953) | 评论(0) | 转发(0) |

0

上一篇：shell do...done < $config

下一篇：排序