[数据结构与算法]数据结构-双向循环链表（实现增，删，改，查）

循环链表

双向链表创建的过程中，每一个结点需要初始化数据域和两个指针域，一个指向直接前趋结点，另一个指向直接后继结点。

循环链表存储实现

typedef struct node{
	int data;//数据
	struct node *prior;//指向直接前驱
	struct node *next;//指向直接后继
}dlistnode;

例：

dlist.h

//dlist.h
#ifndef _DLIST_H
#define _DLIST_H

#include <strings.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

typedef struct node{
	int data;
	struct node * prior;
	struct node * next;
}dlistnode;

extern dlistnode * dlist_create();//创建
extern void dlist_show(dlistnode * H);//输出
extern int dlist_insert(dlistnode *H,int value,int pos);//增
extern int dlist_delete(dlistnode *H,int pos);			//删
extern int dlist_change(dlistnode *H,int value,int pos);//改
extern dlistnode * dlist_get(dlistnode *H,int pos);		//查

#endif

dlist.c

//dlist.c
#include "dlist.h"
//创建
dlistnode * dlist_create(){
	dlistnode * H,* p,* r;
	int n = -1;
	if((H = (dlistnode *)malloc(sizeof(dlistnode))) == NULL){
		perror("malloc");
		return NULL;
	}
	H->prior = H;
	H->next = H;
	r = H;
	while(1){
		printf("please input(-1 exit):");
		scanf("%d",&n);
		if(n == -1){
			break;
		}

		if((p = (dlistnode *)malloc(sizeof(dlistnode))) == NULL){
		perror("malloc");
		return NULL;
		}
		p->data = n;
		p->prior = r;
		p->next = r->next;
		r->next = p;
		H->prior = p;
		r = p;
	}

	return H;
}
//输出
void dlist_show(dlistnode *H){
	dlistnode *p;
	p = H->next;
	while(p != H){
		printf("%d ",p->data);
		p = p->next;
	}
	puts("");
}

//增
int dlist_insert(dlistnode * H,int value, int pos){
	dlistnode *p,*q;
	p = dlist_get(H,pos);
	if(p == NULL){
		return -1;
	}
	if ((q = (dlistnode *)malloc(sizeof(dlistnode))) == NULL){
		perror("malloc");
		return -1;
	}
	q->data = value;
	q->next = p;
	p->prior->next = q;
	p->prior = q;
	
	return 0;
}
//删
int dlist_delete(dlistnode *H,int pos){
	dlistnode *p;
	p = dlist_get(H,pos);
	if(p == NULL){
		return -1;
	}
	p->prior->next = p->next;
	p->next->prior = p->prior;

	free(p);
	p = NULL;
	return 0;
}
//改
int dlist_change(dlistnode *H,int value,int pos){
	dlistnode *p;
	p = dlist_get(H,pos);
	p->data = value;
	return 0;	
	
}
//查
dlistnode * dlist_get(dlistnode * H,int pos){
	int i = 0;
	dlistnode *p = H;

	if(pos < 0){
		printf("pos < 0,invalid!\n");
		return NULL;
	}
	while (i < pos){
		p = p->next;
		i++;
		if(p == H){
			printf("pos is invalid\n");
			return NULL;
		}
	}
	return p;
}

test.c

//test.c
#include "dlist.h"

int main(int argc,const char **argv){
	dlistnode * H;
	int pos;
//创建
	H = dlist_create();
	
	dlist_show(H);
//增
	dlist_insert(H,6,3);
	
	dlist_show(H);
//删	
	dlist_delete(H,4);
	
	dlist_show(H);
//改
	dlist_change(H,5,4);
	
	dlist_show();
//查
	dlistnode *p;
	while(1){
		printf("input pos(0 exit): ");
		scanf("%d",&pos);
		if(pos == 0){
			return 0;
		}
		p = dlist_get(H,pos);
		if(p){
			printf("%d\n",p->data);
		}
	}
	return 0;
}

Makefile

Makefile的书写可参考这篇文章LINUX-Makefile的创建和使用。

cc = gcc
CFLAGS = -O0 -g -Wall
test:test.o dlist.o
	$(cc) $(CFLAGS) -o $@ $^

.PHONY:clean
clean:
	rm -rf test *.o

运行