摘要:由于太久没有复习数据结构了,导致该忘的都忘了,所以在这里记录重新学习数据结构的笔记,以备以后查看。
双链表
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
存储结构
typedef struct DLNode{
ElemType data;
struct DLNode *prior; //指向前驱的指针
struct DLNode *next; //指向后继的指针
}DLNode;
与单链表的区别就是定义了一个指向前驱的指针。
初始化结点
DLNode *create_node(ElemType data)
{
DLNode *ret = (DLNode*)malloc(sizeof(DLNode));
ret->data = data;
ret->prior = NULL;
ret->next = NULL;
return ret;
}
尾插法创建双链表
DLNode *create_link_tail(DLNode *L,ElemType data[],int n)
{
DLNode *s,*r;
int i;
L = create_node(NULL);
r = L;
for(i = 0;i < n ; i++){
s = create_node(data[i]);
s->prior = r;
r->next = s;
r = r->next;
}
r->next = NULL;
return L;
}
查找结点某个位置的指针
//查找某个位置的结点的指针
DLNode *find_elem_node(DLNode *L,int p)
{
int i,count = 0;
DLNode *ret = L->next;
if(p<0 || p > link_length(L))
return 0;
for(i = 1;i< p ; i++){
ret = ret->next;
}
return ret; //这样写如果未找到也会返回NULL
}
在某个结点后面插入结点
//在某个结点后面插入结点
int insert_elem(DLNode *L,ElemType data,int index)
{
DLNode *s,*p;
if(index < 0|| index>link_length(L))
return 0;
p = find_elem_node(L,index);
s = create_node(data);
if(index != link_length(L)){
s->next = p->next;
s->prior = p;
p->next = s;
s->next->prior = s;
}
else{
p->next = s;
s->prior=p;
}
return 1;
}
此处记得判断是否是最后一个结点插入。
删除结点
//删除某个结点并返回
DLNode *delete_node(DLNode *L,int index)
{
DLNode *ret;
if(index < 0|| index>link_length(L))
return 0;
ret = find_elem_node(L,index);
if(index != link_length(L)){
ret->next->prior = ret->prior;
ret->prior->next = ret->next;
}
else{
ret->prior->next = NULL;
}
return ret;
}
获取链表长度
int link_length(DLNode *L)
{
int count = 0;
while(L->next){
count++;
L = L ->next;
}
return count;
}
打印双链表
int printf_link(DLNode *L)
{
while(L->next){
L = L ->next;
printf("%3d",L->data);
}
printf("\n\n");
}
完整函数(包含测试)
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
//定义双链表的节点类型
typedef struct DLNode{
ElemType data;
struct DLNode *prior; //指向前驱的指针
struct DLNode *next; //指向后继的指针
}DLNode;
DLNode *create_node(ElemType data)
{
DLNode *ret = (DLNode*)malloc(sizeof(DLNode));
ret->data = data;
ret->prior = NULL;
ret->next = NULL;
return ret;
}
//尾插法
DLNode *create_link_tail(DLNode *L,ElemType data[],int n)
{
DLNode *s,*r;
int i;
L = create_node(NULL);
r = L;
for(i = 0;i < n ; i++){
s = create_node(data[i]);
s->prior = r;
r->next = s;
r = r->next;
}
r->next = NULL;
return L;
}
//查找某个位置的结点的指针
DLNode *find_elem_node(DLNode *L,int p)
{
int i,count = 0;
DLNode *ret = L->next;
if(p<0 || p > link_length(L))
return 0;
for(i = 1;i< p ; i++){
ret = ret->next;
}
return ret; //这样写如果未找到也会返回NULL
}
//在某个结点后面插入结点
int insert_elem(DLNode *L,ElemType data,int index)
{
DLNode *s,*p;
if(index < 0|| index>link_length(L))
return 0;
p = find_elem_node(L,index);
s = create_node(data);
if(index != link_length(L)){
s->next = p->next;
s->prior = p;
p->next = s;
s->next->prior = s;
}
else{
p->next = s;
s->prior=p;
}
return 1;
}
//删除某个结点并返回
DLNode *delete_node(DLNode *L,int index)
{
DLNode *ret;
if(index < 0|| index>link_length(L))
return 0;
ret = find_elem_node(L,index);
if(index != link_length(L)){
ret->next->prior = ret->prior;
ret->prior->next = ret->next;
}
else{
ret->prior->next = NULL;
}
return ret;
}
//双链表长度
int link_length(DLNode *L)
{
int count = 0;
while(L->next){
count++;
L = L ->next;
}
return count;
}
//打印双链表
int printf_link(DLNode *L)
{
while(L->next){
L = L ->next;
printf("%3d",L->data);
}
printf("\n\n");
}
int main()
{
DLNode *A;
DLNode *local;
int i;
ElemType data1[] = {1,2,3,4,5};
//尾插法
A = create_link_tail(A,data1,5);
printf_link(A);
//长度
printf("A链表长度为:%d.\n\n",link_length(A));
//查找结点
local = find_elem_node(A,2);
printf("查找到第2位结点为:%d.\n\n",local->data);
//指定结点后插入元素
insert_elem(A,6,5);
printf_link(A);
//删除某个结点
local = delete_node(A,6);
printf("删除的结点为:%d\n\n",local->data);
printf_link(A);
return 0;
}
循环链表
循环单链表和循环双链表是由对应的单链表和双链表改造而来,只需要在终点结点和头结点间建立联系即可。循环单链表终端结点的next结点指针指向头结点。循环双链表终端结点的next指针指向表头结点,头节点的prior指针指向表尾节点即可。
tips:
如果P指针沿着循环链表行走,则判断p走到尾节点的条件是p->next == head。循环链表的操作均与非循环链表类似。
Comments | 0 条评论