c语言实现 双链表的操作——头插法、尾插法、查找、插入、删除

双链表的插入操作：

#include <stdio.h>
#include<malloc.h>
typedef struct DNode {
	int data;
	struct DNode* prior, * next;
}DNode, * DLinkList;

//-------头插法---------
DLinkList insert_head(DLinkList DL) {
	DL = (DLinkList)malloc(sizeof(DNode));
	DL->next = NULL;	DL->prior = NULL;
	DLinkList s;
	int x;	scanf_s("%d", &x);
	while (x != -1) {
		s = (DLinkList)malloc(sizeof(DNode));
		s->data = x;
		s->next = DL->next;
		//插入第一个结点不需要此操作
		if (DL->next != NULL) {
			DL->next->prior = s;
		}
		DL->next = s;
		s->prior = DL;
		scanf_s("%d", &x);
	}

	return DL;
}

//-------尾插法---------
DLinkList insert_rear(DLinkList DL) {
	DL = (DLinkList)malloc(sizeof(DNode));
    //需要一个指针r始终指向尾结点
	DLinkList s, r = DL;		int x;
	DL->prior = NULL;
	scanf_s("%d", &x);
	while (x != -1) {
		s = (DLinkList)malloc(sizeof(DNode));
		s->data = x;
		r->next = s;
		s->prior = r;
		r = s;
		scanf_s("%d", &x);
	}
	//!!!!!!最后别忘了把r的next指针指向NULL
	r->next = NULL;

	return DL;
}

void printDNode(DLinkList DL) {
	DLinkList p = DL->next;
	while (p) {
		printf("%d\n", p->data);
		p = p->next;
	}
}
// 1 2 3 -1
int main() {
	DNode n;
	//DLinkList DL = insert_head(&n);
	DLinkList DL = insert_rear(&n);
	printDNode(DL);

	return 0;
}

 双链表按序号查找元素：

DLinkList findByID(DLinkList DL, int i) {
	//查找第i个位置的元素，从0开始
	DLinkList p=DL->next;
	int j = 0;
	if (i < 0) return NULL;
	while ( p && j < i) {
		p = p->next;
		j++;
	}
	return p;
}

int main() {
	DNode n;
	DLinkList DL = insert_rear(&n);
	printDNode(DL);

	DLinkList search = findByID(DL, 2);
	printf("a[i]=%d", search->data);
	return 0;
}

在链表中第i个位置插入元素：

void insertByID(DLinkList DL, int i, int x) {
	//在第i个位置插入x，下标从0开始；
	DLinkList s = DL;
	DLinkList p;	//指向要插入的结点
	p = (DLinkList)malloc(sizeof(DNode));
	p->data = x;
	if (i < 0)		return;
	int j = 0;
	while (j < i) {
		s = s->next;
		j++;
	}
	p->next = s->next;
	s->next -> prior = p;
	s->next = p;
	p->prior = s;

}

int main() {
	DNode n;
	DLinkList DL = insert_rear(&n);

	insertByID(DL, 0, 100);
	printDNode(DL);
	return 0;
}

 或者利用findByID()函数找出第i-1个元素，并把他的指针返回给s

void insertByID(DLinkList DL, int i, int x) {
	//在第i个位置插入x，下标从0开始；
	DLinkList s;
	if (i == 0) s = DL;
	else s = findByID(DL, i - 1);
	DLinkList p;	//指向要插入的结点
	p = (DLinkList)malloc(sizeof(DNode));
	p->data = x;
	if (i < 0)		return;

	p->next = s->next;
	s->next -> prior = p;
	s->next = p;
	p->prior = s;

}

删除第i个元素：

void deleteByID(DLinkList DL, int i) {
	//删除第i个元素，从0开始计数
	DLinkList p;
	if (i == 0)	p = DL;
	else p = findByID(DL, i - 1);
	DLinkList q = p->next;
	//删除元素不存在
	if (q == NULL)	return;
	//假如删除最后一个结点，则不需要此操作
	if(q->next!=NULL)
		q->next->prior = p;
	p->next = q->next;
	free(q);

}

int main() {
	DNode n;
	DLinkList DL = insert_rear(&n);
	printf("-----delete-----\n");
	deleteByID(DL, 0);
	printDNode(DL);

	return 0;
}