数据结构之链表及应用
2016-03-22 本文已影响449人
Albert_Sun
**程序 = 数据结构 + 算法 **
数据结构的设计对于程序的结构和性能都至关重要。合理的数据结构不仅可以降低算法的复杂性，使程序更易于理解和维护，并且可以极大地提升程序的性能。
数据结构综述.png
上图已经列出了常用的数据结构和基本的操作，本文主要讲述线性结构的链表的创建和增删改查等基本操作。
首先明确几个名词和其对应的英文单词:
list（表）、queue（队列）、stack（栈）、tree（树）、graph（图）
link（链式）、sequence（顺序）、node（节点）
- 顺序表
顺序表比较简单，不是本文的重点，在这里只做简单的介绍。比较着急的童鞋可直接跳到第二部分。
顺序表和数组其实是差不多的，只不过数组是存储在栈空间，而表需要在堆空间申请内存空间(请参考这篇介绍：内存管理).
定义顺序表的结构体：
typedef struct _seqlist_
{
int *data;//可以理解为int data[tlen],指向内存片段的首地址
int clen;//顺序表当前长度
int tlen;//顺序表总长度
}seqlist_st;
顺序表基本操作：
- 初始化函数
seqlist_st *seqlist_init(int len)//传入表的总长度，类似于数组的大小
{
seqlist_st *list = NULL;
list = (seqlist_st *)malloc(sizeof(seqlist_st));//向内存申请表头结构体的内存空间
list->data = (int *)malloc(sizeof(int) * len);//申请顺序表的内存大小，类似于 int data[len]
list->clen = 0;//表的当前长度
list->tlen = len;//表的总长度
return list;
}
- 销毁函数
int seqlist_destroy(seqlist_st *list)
{
free(list->data);//先把结构体内部申请到的内存释放
free(list);//再释放表头结构体的内存地址
return 0;
}
- 增
顺序表的插入操作：由于顺序表的内存地址是连续的，所以插入操作比较麻烦，需要将插入位置及之后位置的数值全部后移一位。这里只简单地将元素插入尾部。
int seqlist_insert(seqlist_st *list,int value)
{
if(list->clen >= list->tlen)//判断链表长度是否超过申请的内存大小
return -1;
list->data[list->clen++] = value;//clen记得要执行 +1 操作噢！
return 0;
}
- 删
顺序表的删除操作同样需要将之后的元素全部前移一个位置：
int seqlist_delete(seqlist_st *list, int value)
{
int i, j;
for(i=0; i < list->clen; i++)
{
if(list->data[i] == value)//删除表中所以得value单元
{
for(j=i; j+1 < list->clen; j++)//将value元素之后的所以单元前移一个位置
list->data[j] = list->data[j+1];
list->clen--;//将当前长度 -1
i--;//请认真理解此处为何要 -1
}
}
return 0;
}
- 改
将表中的第一个old替换为new,若不存在old则返回 -1
int seqlist_modify(seqlist_st *list,int old,int new)
{
int i;
for(i = 0;i < list->clen;i++)
{
if(list->data[i]== old)//找到第一个old并将其替换为new
break;
}
if(i>=list->clen)
return -1;
list->data[i]=new;
return 0;
}```
- 查
看表中是否存在此值
int seqlist_search(seqlist_st *list,int value)
{
int i;
for(i = 0;i<list->clen;i++)
{
if(list->data[i]==value)//查找第一个vlaue值
break;
}
if(i>=list->clen)
return 0;
return 1;
}
这里给出一个show()函数和main()函数以方便测试顺序表的基本操作是否正确：
int seqlist_show(seqlist_st *list)
{
int i=0;
for(i=0;i<list->clen;i++)
printf("%5d ",list->data[i]);
printf("\n");
return 0;
}```
int main(int argc, const char *argv[])
{
seqlist_st *list = NULL;
int value = 100;
list = seqlist_init(10);
while(0 == seqlist_insert(list,value))
value += 100;
seqlist_show(list);
seqlist_delete(list,600);
seqlist_show(list);
printf("search(300)= %d \n",seqlist_search(list,300));
printf("modify(200,300)= %d \n",seqlist_modify(list,200,300));
seqlist_show(list);
printf("search(200)= %d \n",seqlist_search(list,200));
seqlist_delete(list,300);
seqlist_show(list);
seqlist_destroy(list);
return 0;
}
- 链表
链表和顺序表的本质区别在于：链式表在堆内存中不是顺序存储的，而是链式存储的，即相邻的两个单元在物理位置上并不相邻，也即地址并不连续。而是前一个节点里面存储的后一个节点的内存地址，通过此种方式实现存储和访问。
链式表的创建和基本的操作我们直接在下面的完整的程序中进行说明：
链表的内存视图
#include <stdio.h>
#include <stdlib.h>
typedef struct _linknode_//链表的节点结构体
{
int data;//存储节点的值
struct _linknode_ *next;//存储后续单元的地址
}linknode_t;
typedef struct _linklist_//链表的结构体
{
struct _linknode_ *head;//链表头的地址
int clen;//链表当前的长度
int tlen;//链表的总长度
}linklist_t;
int linklist_destroy(linklist_t *list);
linklist_t *linklist_init(int len);
int linklist_insert(linklist_t *list,int value);
linknode_t *creat_linknode(int value);
int linklist_show(linklist_t *list);
int linklist_delete(linklist_t *list,int value);
linknode_t * linklist_search(linklist_t *list,int value);
int linklist_modify(linklist_t *list,int old,int new);
int linklist_insertend(linklist_t *list,int value);
int linklist_insertmid(linklist_t *list,int local_value,int destin_value);
int main(int argc, const char *argv[])
{
int value = 100;
linknode_t *ret=NULL;
linklist_t *list = NULL;//链表首地址
list = linklist_init(10);//初始化链表，传入链表长度
while(0 == linklist_insertend(list,value))//使用尾差法将值插入表中
value +=100;
linklist_show(list);//查看表
linklist_delete(list,600);//删除表中值为600的节点
linklist_show(list);
ret = linklist_search(list,600);//查找链表中值为600的节点，返回其结构体地址
if(ret == NULL)
printf("search : NULL \n");
else
printf("%d \n",ret->data);
linklist_modify(list,500,543);//修改
ret = linklist_search(list,543);
if(ret == NULL)
printf("search : NULL \n");
else
printf("%d \n",ret->data);
linklist_insertmid(list,400,678);//将678插入在400的下一节点
linklist_show(list);
linklist_destroy(list);//一定记得要销毁链表释放内存噢，不然会产生内存泄露喔。
return 0;
}
linklist_t *linklist_init(int len)//链表的初始化
{
linklist_t *list = NULL;
list = (linklist_t *)malloc(sizeof(linklist_t));//链表的结构体地址
list->head = creat_linknode(0);//链表的头结点，
list->clen = 0;
list->tlen = len;
return list;
}
int linklist_destroy(linklist_t *list)//链表的销毁
{
linknode_t *p = list->head;
linknode_t *temp = NULL;
while(NULL != p)
{
temp = p;//从头结点开始逐个释放申请到的内存空间
p = p->next;
free(temp);
}
free(list);
return 0;
}
int linklist_insert(linklist_t *list,int value)//链表擦头插发，即将value值插入链表的第一个位置(头结点之后)
{
linknode_t *new = NULL;
if(list->clen>=list->tlen)
return -1;
new = creat_linknode(value);
new->next=list->head->next;//新建节点的next指向原头节点的后继节点
list->head->next=new;//头结点的next指向新建的节点，则完成了头插法
list->clen++;
return 0;
}
linknode_t *creat_linknode(int value)
{
linknode_t *node = NULL;
node = (linknode_t *)malloc(sizeof(linknode_t));//申请内存空间，创建节点，链式表只在需要用时才去动态申请内存空间，顺序表和数组都是在一开始即初始化就申请了所需的全部内存
node->data = value;
node->next = NULL;
return node;//返回申请到的节点的内存空间地址
}
int linklist_show(linklist_t *list)//辅助函数，顺序打印链表的值
{
int i;
linknode_t *p = list->head->next;
for(i=0;i<list->clen;i++)
{
printf("%5d ",p->data);
p=p->next;
}
putchar('\n');
return 0;
}
int linklist_delete(linklist_t *list,int value)
{
linknode_t *p = list->head;
linknode_t *tmp = NULL;
while(NULL != p->next)//找到需要删除的节点的地址：注意，我们需要定位到其前一个节点，即 p->next->data == value 的p，请认真思考为什么
{
if(p->next->data == value)//
break;
p=p->next;
}
if(NULL == p->next)
return -1;
tmp = p->next;//将要删除的节点的地址（p->next）先暂存
p->next = tmp->next;//将其前一个节点p的next指向其后继节点，现在才可以释放其内存
free(tmp);
list->clen--;
return 0;
}
linknode_t * linklist_search(linklist_t *list,int value)
{
linknode_t *p = list->head->next;
while(NULL != p)
{
if(p->data == value)//搜索链表中值为value的节点，并将其地址返回，如不存在，则返回null
return p;
p=p->next;
}
return NULL;
}
int linklist_modify(linklist_t *list,int old,int new)
{
linknode_t *p = list->head->next;
while(NULL != p)
{
if(p->data == old)//找到old节点，将其data值替换为指定的new
{
p->data = new;
break;
}
p=p->next;
}
if(NULL == p)//若没有找到old节点， 即链表中不存在值为old的结点，则返回-1
return -1;
return 0;
}
int linklist_insertend(linklist_t *list,int value)
{
linknode_t *p = list->head;
linknode_t *new = NULL;
while(NULL != p->next)//找到最后一个节点
p = p->next;
if(list->clen >= list->tlen)
return -1;
new = creat_linknode(value);//创建新的节点
p->next = new;//将找到的最后一个节点的next指向新创建的节点，这样新创建的节点就添加在整个链表的最后了
list->clen++;
return 0;
}
int linklist_insertmid(linklist_t *list,int local_value,int destin_value)
{
linknode_t *p = list->head->next;
linknode_t *new = NULL;
linknode_t *tmp = NULL;
if(list->clen >= list->tlen)
return -1;
while(NULL != p)
{
if(p->data == local_value)//找到值为local_value的节点的地址
{
tmp = p->next;//先将其后继节点的地址存储起来
new = creat_linknode(destin_value);//创建新的节点
p->next = new;//使local节点的next指向新插入的节点
new->next = tmp;//新创建的节点的next指向原local的后继节点，完成了插入操作
list->clen++;
break;
}
p = p->next;
}
return 0;
}
上述实现的链表是单向链表，即只能从前一个节点找到后一节点，此外还有双向链表(即能从前一个节点找到后一个节点，也能从后一个节点找到前一个节点，即一个节点结构体不仅存了前一个节点的地址还存了后继节点的地址)、循环链表(即尾节点的next不为null,而是存了第一个节点的地址)等。只需在此基础上稍加修改即可实现。我们可以根据具体的需求来选择相应的数据结构。
